10
$\begingroup$

It seems to be possible to retrieve the (public) key used for creating an ECDSA signature just from the signature alone.

This seems like an interesting property; as far as I know, RSA doesn't share it.

Depending on the application, this can both be an advantage (shorter messages, as the public key or a key id doesn't have to be attached) and a disadvantage (if confidentiality is required, the signature has to be encrypted).

Which other cryptographic signature schemes have that property? I'm especially interested in RSA, Ed25519 and (non-elliptic) DSA.

Improve this question
$\endgroup$
3
  • $\begingroup$ Why would you want to extract the public key from a signature ? If you don't a prior knowledge of the public key/Identity link then using signature scheme adds no security $\endgroup$
    – Alexandre Yamajako
    Aug 23 '13 at 13:41
  • $\begingroup$ One use case would be Bitcoin transaction verification; here is a discussion on bitcointalk that partially motivated this question: bitcointalk.org/index.php?topic=6430.0 $\endgroup$
    – lxgr
    Aug 23 '13 at 16:48
  • $\begingroup$ That link is broken. Here's an updated, working link: secg.org/sec1-v2.pdf $\endgroup$
    – Lane Rettig
    Dec 17 '20 at 17:37
12
$\begingroup$

Well, lets go through the issues:

It seems to be possible to retrieve the (public) key used for creating an ECDSA signature just from the signature alone

Nope, not quite. You also need the message being signed. And, with that, it doesn't give you the unique public key; it does allow you to narrow it down to two possibilities (assuming you're using a curve with a cofactor of 1; almost always the case nowadays), however from a single signature, you don't know which of the two possiblities it is.

In some circumstances, the private key can be recovered as well

I should certainly hope not. If you can recover the private key with a signature and the message being signed (and you can throw in the public key if you want), then the signature scheme is "broken"; I rather doubt that Mr. Brown claims that ECDSA is broken.

this can be an advantage (shorter messages, as the public key or a key id doesn't have to be attached)

Well, it's not that much of an advantage; not only does the verifier need to know what the public key is, he also needs to know that it's the correct public key; that is, it is the public key whose private key is held by the person you think is signing the message. There are a number of ways a verifier can ascertain that; however he must do so; just passing a public key somehow (either explicitly or implicitly) doesn't cut it.

this can be a disadvantage (if confidentiality is required, the signature has to be encrypted)

Not so much; if confidentiality (rather, anonymity) is required (specifically, you don't want an evesdropper to be able to verify who signed the message), then you need to hide the signature anyways. If you don't, then the evesdropper does get a copy of Alice's public key, and has a guess for the message can simple check if the message is from Alice by running the signature verification method using his copy of Alice's public key. This doesn't require any special properties of the signature method.

Which other cryptographic signature schemes have that property?

I'll go through the ones you listed:

  • RSA; if the public exponent isn't large, and you use a deterministic padding method, then you can recover the RSA public key from two signatures (of two different messages)

  • Ed25519; I don't believe that you can recover the public key. The verification process involves a hash of data including the public key; there's no way to quickly check which public key would make the hash come out correctly.

  • DSA: I don't believe that you can recover the public key. The distinction between DSA and ECDSA is that the DSA verification process involves an outer "mod q" operation; that operation discards information that would be needed to recover the public key.

Improve this answer
$\endgroup$
4
  • $\begingroup$ With "recovering the private key", I was referring to the troubles with ECDSA and reused nonces that somewhat famously resulted in Sony's PS3 master keys being published and about 55 Bitcoins being stolen. Of course, when using a proper random nonce, this is not possible. One might say that it's only the implementor's fault, but proper randomness can sometimes be hard to acquire... I've now removed that sentence; vaguely referencing ECDSA's security model probably doesn't add anything to the question. $\endgroup$
    – lxgr
    Aug 23 '13 at 16:42
  • $\begingroup$ Thanks for the detailed comments on all my assumptions, seems like the property isn't as useful/dangerous as I originally thought. $\endgroup$
    – lxgr
    Aug 23 '13 at 16:51
  • $\begingroup$ @Ixgr: if you need to generate DSS/ECDSA signatures, and you don't have entropy (or you don't trust the entropy you have), you can consider RFC6979 (which tells you how to generate signatures securely without any randomness) $\endgroup$
    – poncho
    Aug 23 '13 at 17:27
  • $\begingroup$ I didn't know about RFC6979 yet; it seems like a really good idea. Thanks! $\endgroup$
    – lxgr
    Aug 23 '13 at 20:22

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.