It is possible to recover the public key from an ECDSA signature values $(r,s)$?
Please explain how this works.
$\begingroup$
$\endgroup$
1
-
$\begingroup$ Sec1 has a section on that. $\endgroup$– fgrieu ♦Commented Nov 14, 2023 at 9:42
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
7
Actually, it is not possible to uniquely recover the public key from an ECDSA signature $(r,s)$. This remains true even if we also assume you know the curve, the hash function used, and you also have the message that was signed.
However, with the signature and the message that was signed, and the knowledge of the curve, it is possible to generate two public keys; one of which will be the public key corresponding to the private key used.
Here's how that works:
First, you find the two points $R$, $R'$ which have the value $r$ as the x-coordinate $r$.
You also compute $r^{-1}$, which is the multiplicative inverse of the value $r$ from the signature (modulo the order of the generator of the curve).
Then, you compute $z$ which is the lowest $n$ bits of the hash of the message (where $n$ is the bit size of the curve).
Then, the two public keys are $r^{-1}(sR - zG)$ and $r^{-1}(sR' - zG)$
It is easy to verify that if you plug either of these values in the ECDSA signature routines as the public keys, the signature validates.
-
$\begingroup$ Actually I am trying to implement this but I think that there is something missing. The first statement don't look complete according to what I've found ( panda.cat/pubkeyrecover.png ) x = r + jn where j >= 0 and j <= h . So x = r only if j = 0. $\endgroup$ Commented Aug 12, 2014 at 17:05
-
1$\begingroup$ @JanMoritzLindemann: I had written it assuming you were in a curve with cofactor 1 (h=1). If you are working with a curve with a larger cofactor, then, yes, you need to iterate through the possible multiples of the cofactor, and reject any point $R$ that isn't a multiple of $G$ -- the link you gave explains how to do that. $\endgroup$– ponchoCommented Aug 12, 2014 at 17:24
-
$\begingroup$ Yes it is a curve with cofactor 1 but even with this kind of curves you have j = 0 and j = 1 . Or did I missed something? $\endgroup$ Commented Aug 12, 2014 at 17:32
-
2$\begingroup$ @JanMoritzLindemann: it appears that the link you gave got it a bit off; you iterate from the values between j=0 and j=h-1; if h=1, that means you need consider only j=0 $\endgroup$– ponchoCommented Aug 12, 2014 at 18:03
-
$\begingroup$ Can you please explain how I can sign a message, skip the pub key and encode it in such a way that the recipient can uniquely determine the key. Assume cofactor is 1 and this is the bitcoin curve. I could not find any documentation about creating recoverable signatures compatible with their core software. $\endgroup$– Jus12Commented Dec 27, 2017 at 5:22
$\begingroup$
$\endgroup$
3
As @poncho says, both keys $Q_1=r^{-1}(sR-zG)$ and $Q_2=r^{-1}(sR'-zG)$ will validate the given signature, i.e., $(s^{-1}zG+s^{-1}rQ_i)_x=r\mod{n}$. For some curves, with small but non-zero probability, we have $n\leq(kG)_x<p$, and neither $Q_1$ nor $Q_2$ will validate other signatures made with the original private key $d$. However, by Hasse's theorem, with high probability $1-O(1/\sqrt{p})$ we have $0\leq(kG)_x<n$. In this case either $R=kG$ or $R'=kG$, so, correspondingly, $Q_1$ or $Q_2$ equals the original public key $Q=dG$.
-
2$\begingroup$ It turned out that in my case (Bitcoin message signature) they append an extra byte to the signature in order to identify which of the two points is the public key. Once this is done they calculate a 160bit hash of the public key. This hash is known as a bitcoin address. Then they check if the generated address is equal with the given one and if it is the message is authenticated. By using this way of doing they win some bytes. $\endgroup$ Commented Jul 15, 2014 at 6:04
-
$\begingroup$ "For some curves, with small but non-zero probability," Bitcoin uses the secp256k1 curve. Is this one of the curves where this small probability exists? I've seen that before returning the signed message they check if they are able to extract the public key correctly. $\endgroup$ Commented Jul 15, 2014 at 6:05
-
6$\begingroup$ I've tested this on a small example with p=23, a=13, b=10, n=19, G=(18, 2) and seen the failure. For secp256k1, we have (p-n)/p=+4e-39, so there is a small chance you will not recover the original public key. But, if the signer knows the recipient will recover the public key this way, s/he can test the key recovery and re-do the signature (choose a new k) in the rare case that it fails. $\endgroup$ Commented Jul 15, 2014 at 22:02
$\begingroup$
$\endgroup$
It is well-known that one can recover the ECDSA public key used from a valid ECDSA signature on a known message, cf. Section 4.6 of https://www.secg.org/sec1-v2.pdf.
