The Risks of 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 \).

To enhance the interference effect of QFT and amplify the probability amplitude, \( M \), which can represent a number significantly exceeding \( N \), is created in superposition by increasing the number of qubits, thereby forming a larger address space.

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

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{M}} \sum_{k=0}^{M-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{M}} \sum_{k=0}^{M-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. Why ECDSA(secp256k1) Are Not Quantum-Resistant

Secp256k1 inherit the vulnerabilities of ECDSA since both depend on scalar multiplication and the elliptic curve discrete logarithm problem.

Scalar Multiplication:
Vulnerable to Shor's algorithm.

Public Key Exposure:
Quantum computers can derive private keys from public keys.

4. Transition to Quantum-Resistant Schemes

Given the vulnerability of ECDSA(secp256k1), it is critical to transition to quantum-resistant cryptographic schemes, such as:
Hash-Based Signatures (e.g., SPHINCS+)
Lattice-Based Cryptography (e.g., Kyber, Dilithium)
Code-Based Cryptography (e.g., McEliece)

5. 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.