Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

It is possible to recover the public key from an ECDSA signature (R,S).

Please explain me how this works.

share|improve this question

2 Answers 2

up vote 6 down vote accepted

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.

share|improve this answer
    
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. –  Jan Moritz Lindemann Aug 12 at 17:05
1  
@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. –  poncho Aug 12 at 17:24
    
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? –  Jan Moritz Lindemann Aug 12 at 17:32
    
@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 –  poncho Aug 12 at 18:03

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$.

share|improve this answer
    
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. –  Jan Moritz Lindemann Jul 15 at 6:04
    
"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. –  Jan Moritz Lindemann Jul 15 at 6:05
1  
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. –  Steve Mitchell Jul 15 at 22:02

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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