Score:1

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

br flag
aac

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?

cn flag
"division" is just a name/notation, not an algorithm. In some sense it is "just" a division problem.
aac avatar
br flag
aac
I see what you're saying, but what I mean is, why then can't we just divide the public key by the base point to get the private key? I know it's obviously not that simple, so what basic thing have I missed?
kelalaka avatar
in flag
That is the [discrete logarithm problem](https://crypto.stackexchange.com/q/76230/18298) on Elliptic Curves.
kelalaka avatar
in flag
And [scalar multiplication](https://crypto.stackexchange.com/a/68595/18298) that you confuse it with multiplication. It is not!
aac avatar
br flag
aac
@kelalaka ah, so, the point doubling is not the same as multiplying x and P?
kelalaka avatar
in flag
doubling is just $[2]P = P+P$
poncho avatar
my flag
Where $P + P$ means performing the elliptic curve addition formula with inputs $P$ and $P$ - this is not the addition operation you learned in gradeschool
Score:1
in flag

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

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.

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

aac avatar
br flag
aac
thank you very much!
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.