Find ECDSA PrivKey to PubKey = 0

I know it should be impossible (or at least infeasible hard) to extract a ECDSA Private Key from a given Public Key (discrete logarithm problem). But I'm not deep enough into ECC to find an answer to this question: is it possible/easier to find the private key if the corresponding public key is Zero? (like "0x000...000")? Of course the curve details (base point, finite field etc) is given too.

Thanks alot!

• What do you mean by PubKey=0? x=0 in weierstrass form? Or the neutral element? Jul 9 '17 at 21:45
• Thanks alot, guys. Last question: is there only one private key related to one public key? Or could it be there is another private key mapping to the public key "0000..."? Jul 12 '17 at 7:31
• @Benedict you may want to have a look at this topic in our help-center.
– SEJPM
Jul 12 '17 at 8:52

Yes, actually it is rather trivial.

First we need to dive a little bit into how elliptic curves work. Take a finite field, usually $\mathbb F_p$ for some fixed prime $p$. We call the set of all pairs $(x,y)\in\mathbb F_p^2$ satisfying the equation $y^2\equiv x^3+ax+b\pmod p$ the elliptic curve $E_{a,b}(\mathbb F_p)$.

First we note that $(0,0)$ is on the curve if and only if $b=0$. However, for practically used curves this is not the case. So we can conclude that your request doesn't actually ask for the point which gets encoded to $(0,0)$ (because it isn't on any curve) but rather for the semantic point $0$ that fullfills the same role as the $0$ for the integers, the rationals, the reals, that is the role of the additive neutral element in a group. The encoding of $\mathcal O$ as all-0x00 bytes is confirmed in SEC 1 v2 section 2.3.3 (PDF).

Now we commonly write the points on an elliptic curves as a group, because we can add them, we can subtract them, they have a neutral element $\mathcal O$ ("the point at infinity") and addition is associative.

Now that we have made use of 3 of the 7 usual parameters for elliptic curves, let's look at the rest. Two parameters encode the base point, that is a point $G=(g_x,g_y)$ on the curve which is fixed and used as the reference element for all cryptographic operations. In fact the private key $d$ to your public key point $Q$ has to satisfy the relation $Q=[d]G$, that is addition of $G$, $d$-times with itself yields $Q$.

So now for the last two parameters. Remember when we talked about the curve being the set of all points? It turns out that we actually need to know how many there are. This is called the order of the curve and is not encoded usually in the domain parameters. However, the order of $n$ of the base-point is encoded and that is precisely the integer such that $\mathcal O=[n]G$, so the "private key" to "0x0000...000" is actually directly encoded in the domain parameters.

To satisfy the curiosity you surely have: The last value encoded is the co-factor, that is the quotient of the curve's order and the base-point's order, we need this for some computations.

If you are now asking yourself, whether $n$ is the private key, then the answer is "no". It is the private key that is smaller or equal to $n$ and larger than $0$, however, any multiple of $n$ will work. That is $d'=2n$ will work just the same as $d''=3n$, because in this setting they designate the same as all scalar factors are reduced $\bmod n$ and $0\equiv n\equiv 2n\equiv 3n\equiv\ldots\pmod n$.

On a final note (as pointed out by @fgrieu in the comments): No sane implementation would accept $\mathcal O$ as a public key (section 3.2.2.1 of SEC 1 v2 (PDF)), because it would offer no security as discussed above. On key generation there's also the standard restriction that $0<d<n$, meaning no sane implementation would ever generate $\mathcal O$ as the public key (section 3.2.1 of SEC 1 v2 (PDF)).

• According to ISO/IEC 14888-3:2016, in EC-DSA, "The signature key of a signing entity is a secretly generated random or pseudo-random integer $X$ such that $0<X< q$."; neither $X=q$ (suggested in the answer) nor $X=0$ are valid private keys per this definition. Further, I'm unsure about if $\mathcal O$ has a valid representation as a public key. Strangely, I failed to find the public key format precisely defined in any reference (free or that money can buy from its original source): ANS X9.62 is no longer sold by ANSI, and NIST test vectors are not a reference.
– fgrieu
Jul 10 '17 at 8:00
• Further, per SEC 1 Ver. 2.0 section 3.2.2.1, the Elliptic Curve Public Key Validation Primitive starts with "Check that $Q\ne\mathcal O$".
– fgrieu
Jul 10 '17 at 12:11
• @fgrieu so the answer should actually read "any sane implementation should immediately reject this public key as it is $\mathcal O$, but if it were to accept it anyways, using this public key would be immediately insecure"?
– SEJPM
Jul 10 '17 at 16:24
• That's my guess.
– fgrieu
Jul 10 '17 at 17:03