1
$\begingroup$

I know that generally it's infeasible to find the private for any given public key. But I also came across the question "Find ECDSA PrivKey to PubKey = 0", in which it was explained that the private key for a public key 0x0000...0000 can be easily derived.

From the answer to that question it appears that public key 0x0000...0000 is the only public key for which this is the case, but haven't understood it well enough to know for sure.

So the question is, are there any other possible public keys (e.g. 0xffff...ffff or 0x0000...0001) for which it is easy to derive the corresponding private key?

$\endgroup$
0
1
$\begingroup$

Preamble

One side of the security of the ECDSA depends on the Discrete logarithm security of the used Elliptic Curve ( call it $E$). Elliptic curves form an additive algebraic group of order $n$. If the group formed by the used curve is a generic group then the best classical attack is $\mathcal{O}(\sqrt{2^n})$ - Pollard's Rho.

ECDSA

The private key $k$ is calculated as a random integer in the interval $[1,n-1]$ and kept secret all the time. Note that the private key $k$ is an integer, not a point on the curve $E$.

The public key $P$, on the other hand, is calculated as a point $p = [k]G$ where $G$ is the base point of the curve defined in the standards and the operation $[k]G$ is called the scalar multiplication defined as;

$$[k]G : = \underbrace{G + G + \cdots + G}_{k-times}$$

This should not be confused with multiplication, no this is what we write to simplify the $k$-times additions.

The $[k]P$ can be calculated at least with double-and-add algorithm to fasten the calculation in $\mathcal{O}(\log k)$-time.

The points

Now as we can see, even the $k=0$ is not a problem in ECDSA since it is not a valid value for $k$.

If the discrete log is easy

  • If the discrete log is easy on this curve, that is finding $k$ given $[k]G$, then every value is easily derived.

  • If the curve is backdoored with another base point $H$, i.e. someone can solve the discrete logarithm to the base $H$ on the curve group. Then they can use this to solve the Dlog on the base $G$ very easily;

    • They calculate $G = [t]H$ for $t \in [1,n-1]$ only once
    • They solve $P =[k\cdot a]G$ to the base $H$ for $a \in [0,n-1]$. Once $ka$ is found the $k$ can be calculated as $k = a \cdot k \cdot a^{-1}$ since we know the $a$ and $a^{-1} \cdot a = 1 \bmod n$.

If the discrete log is not easy

In this case, one can calculate some of them up to their maximal power. Let assume you can use the supercomputer Summit and you have the power to calculate $2^{70}$ double-and-add for a given number $t$. They calculate and set up a hash table to fast query for the existence of the discrete log in the range $[1,2^{70}]$. The run in one year, and the required storage is $2^{70}*256*3$-bits (~147574 Petabyte). Well, storage is one of the problems and the other is hash table may not be $\mathcal{O}(1)$ anymore. Let assume that you have solved this problem, then what is the probability that you can find a given private key from the public key. The exact value depends on the curve group, assume one uses a curve group of size $2^{256}$ to be secure against the standard Dlog attacks. The hit probability is $$\frac{2^{70}}{2^{256}} = \frac{1}{2^{186}}.$$ This even has far less probability than $\dfrac{1}{100}$, so we say it-is-not-going-to-happen!

Does Instead of sequential random choices of $t$s change the result, NO!


Special note 1:0x0000...0000 is the usual encoding of the $\mathcal{O}(n)$ since $(0,0)$ is not on the curve. This is not accepted as a valid public key in SEC 1 Ver. 2.0 section 3.2.2.1.


Special note 2: Some elliptic curves are prime curves this means that the group they formed has prime order. In this case, every element is a generator, except the identity element. If the order is not prime, like in the Curve25519, then we have the cofactor $h = \#E(K)/n$ where $n$ is the largest prime dividing the order of the curve. If the full group is used, it is easy to notice the small order elements, simply check $[o]P = \mathcal{O}$ or not, where $o$ is the small order. For Curve25519, the $o$ values are $2,4,$ and $8$. This is not a security problem since legitimate users always choose $k \equiv 0 \pmod 8$.

$\endgroup$
2
  • 1
    $\begingroup$ Well, I've written a long answer to say almost no! Shoot me! $\endgroup$
    – kelalaka
    Nov 15 at 21:39
  • $\begingroup$ Thanks for the detailed answer, it's very insightful! $\endgroup$ Nov 17 at 9:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.