Shor's algorithm and ECDSA in Bitcoin - why is finding the private key still difficult when we know the base point?

Question

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?

Answer 1

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.