The Risks of ECDSA(secp256k1)

This document provides a mathematical formulation of the process by which a quantum computer can attack the Elliptic Curve Digital Signature Algorithm (ECDSA) by deriving the private key \( k \) from the public key. The aim is to highlight the vulnerabilities and emphasize the need for quantum-resistant cryptography.

1. Basics of Elliptic Curve Cryptography

The public and private keys in ECDSA are defined as follows:

\begin{equation} P = kG \quad \text{where } P \text{ is the public key, } G \text{ is the generator, and } k \text{ is the private key.} \end{equation}

Here, solving the Elliptic Curve Discrete Logarithm Problem (ECDLP) to find \( k \) from \( P \) and \( G \) is computationally infeasible with classical methods.

The modulus used in the \( kG \) calculation process of ECDSA, as adopted by Bitcoin and others, is \( 2^{256} - 2^{32} - 977 \).
This becomes the prime number of the finite field.

2. Steps for Quantum Computer Attack

The private key \( k \) can be derived using the following quantum algorithm steps:

Step 1: Initialization of Superposition

A quantum state representing all possible private keys is initialized as:

\begin{equation} |\psi_{\text{initial}}\rangle = \frac{1}{\sqrt{N}} \sum_{k=0}^{N-1} |k\rangle |kG\rangle, \end{equation}

where \( N \) is the order of the elliptic curve.
In this case, the \( N \) used in ECDSA, as adopted by Bitcoin and others, is \( 115792089237316195423570985008687907852837564279074904382605163141518161494337 \).

Step 2: Phase Oracle Application

A phase \( \pi \) is applied to the state corresponding to the target public key \( P_{\text{target}} \):

\begin{equation} |\psi_{\phi}\rangle = \frac{1}{\sqrt{N}} \sum_{k=0}^{N-1} e^{i\phi_k} |k\rangle |kG\rangle, \quad \text{where } \phi_k = \begin{cases} \pi & \text{if } kG = P_{\text{target}}, \\ 0 & \text{otherwise}. \end{cases} \end{equation}

Step 3: Quantum Fourier Transform (QFT)

The Quantum Fourier Transform is applied to exploit the periodicity of the scalar multiplication: \begin{equation} |\psi_{\text{QFT}}\rangle = \text{QFT}\Bigg(\frac{1}{\sqrt{N}} \sum_{k=0}^{N-1} e^{i\phi_k} |k\rangle\Bigg) \end{equation}

This step amplifies the frequency components corresponding to the periodicity of \( k \).

Step 4: Measurement and Collapse

Measurement of the quantum state collapses it, yielding the phase information:

\begin{equation} \phi_k = \frac{2\pi k}{r}, \end{equation} where \( r \) is the periodicity of the scalar multiplication.
In this case, the \( r \) is \( N \), therefore, \( r = N \).

Step 5: Derivation of the Private Key \( k \)

Using the extracted phase information, the private key \( k \) can be computed as:

\begin{equation} k = \frac{\phi_k \cdot N}{2\pi}, \quad \text{mod } N \end{equation}

3. Conclusion

This document demonstrates how quantum computers can exploit the periodic structure of elliptic curve scalar multiplication to break ECDSA. The findings emphasize the critical need for transitioning to quantum-resistant cryptographic algorithms, such as hash-based or lattice-based cryptography.