- public-key elliptic-curves dsa secp256k1 shors-algorithm
- Updated Fri, 20 May 2022 02:14:46 GMT

I'm learning about Shor's algorithm and how it can be applied to break ECDSA. I've clearly missed something basic here - I thought I understood that the challenge ECDSA presented was to find the private key given the public key, as follows:

$x\cdot P = X$ (where $x$ is the large and randomly-generated private key, $P$ is the secp256k1 base point, and $X$ is the public key).

Since we know the base point for secp256k1, given in xy-coords as (55066263022277343669578718895168534326250603453777594175500187360389116729240, 32670510020758816978083085130507043184471273380659243275938904335757337482424), why is this still a difficult problem that only Shor's algorithm could solve and not simply a division problem?

What is confusing you is that you consider the **scalar multiplication** (in your notation $x\cdot P$) as **multiplication** on a Finite field. Actually;

The **scalar multiplication** on Elliptic curves $[x]P$ actually means adding the $P$ itself $x$-times. This is how a public point is calculated, from a private key, the former is a point on the curve the latter is an integer. More formally;

let $x \in \mathbb{N}\backslash\{ 0\}$

\begin{align} [x]:& E \to E\\ &P\mapsto [x]P=\underbrace{P+P+\cdots+P}_{\text{$x$ times}}.\end{align}

Here the $P+P =[2]P\;(=2\cdot P)$ means the **point addition** and has special formulas derived from the tangent-chord rule. With this point addition, for the curve defined over a finite field, the points form a finite abelian group and with the scalar multiplication, we have a $Z$-module.

When we talked about given $[x]P$ and $P$ finding $x$ is the **discrete logarithm problem** on the Elliptic Curves. On some curves, it is easy, however, on secp256k1 it is not easy and classical attack has a cost of $\mathcal{O}(\sqrt{n}$) while $n = order(P)$ with Pollard's Rho. The best-implemented attack has used a parallel version of Pollard's kangaroo algorithm on $2^{114}$ interval.

**Shor's algorithm** (if ever implemented for the real size and all the problems are solved) can solve the discrete logarithm in polynomial time. An estimate of the attack can be found here

- 2017 Quantum Resource Estimates for Computing Elliptic Curve Discrete Logarithms by Roetteler et al.

Actually, one doesn't need the $y$ coordinate for the attack. There can be at most two $y$ values for given $x$ as long as $x$ is the coordinate of point satisfying the curve equation.

**Standard ECDSA**, on the other hand, some other real issues than Pollard's Rho and Shor's period finding algorithm.

Repeat of the nonce: private key is immediately leaked.

Bias on the random number generator for the nonce, lattice attacks reveals the key. Even tiny bias;

- 2020 LadderLeak: Breaking ECDSA With Less Than One Bit Of Nonce Leakage by Aranha et al.

Short random, yes that existed in Bitcoin;

- 2019 - Biased Nonce Sense: Lattice Attacks against Weak ECDSA Signatures in Cryptocurrencies Breitner and Heninger2

We have a better alternative, deterministic ECDSA by Thomas Pornin and Bitcoin and other started to use.

External links referenced by this document:

- https://crypto.stackexchange.com/a/66296/18298
- https://datatracker.ietf.org/doc/html/rfc6979
- https://en.wikipedia.org/wiki/Pollard's_rho_algorithm_for_logarithms
- https://eprint.iacr.org/2019/023.pdf
- https://eprint.iacr.org/2020/615
- https://github.com/JeanLucPons/Kangaroo
- https://www.iacr.org/archive/asiacrypt2017/106240342/106240342.pdf