# Recovering Public Key from ECDSA signature- why is it required at all?

I am looking at SEC 1: Elliptic Curve Cryptography

4.1.6 Public Key Recovery Operation

Given an ECDSA signature $$(r, s)$$ and EC domain parameters, it is generally possible to determine the public key $$Q$$, at least to within a small number of choices.

I am unable to figure out why recovering Public Key from the Signature is a useful option at all?

The Document says

This is also useful in bandwidth constrained environments, when transmission of public keys cannot be afforded

But the whole idea of signatures is that the verifier needs to already need to know the public key - else the whole verification becomes meaningless.

Let us say Alice signs a message & sends the message & the signature to Bob. Now Bob knows her Public Key & he can check if the message has indeed been signed by someone who has the private key corresponding to the public key he knows for sure is Alice's Public Key.

Let's say Mallory intercepts Alice's message & signature. He changes the message & signs it with his own private key. Now Bob gets the tampered message & the signature. Bob doesn't have Alice's Public Key - so Bob recovers what he thinks is Alice's Public key from the signature - then verifies if the message is signed by who ever has the Private Key corresponding to that public key. Now the Public Key Bob recovers is actually Mallory's & not Alice's. So Bob will never know that the message has been tampered. So what is the point of the signature?

• A possible use is to have Bob save only 64 bits of the public key, for instance, and then check if the public key of the message matches it. This is quite weird, though, and does lower the security. Commented Aug 8 at 15:11
• There might be a case where you don't know yet from who the message is, but have multiple possible senders. Extracting the key from the signature might be a useful option then. Commented Aug 8 at 23:52
• Isn't it 256 bits usually? (And can be compressed to 128) Commented Aug 9 at 3:12
• @CommandMaster yes - my bad! So you were saying that the device stores a truncated public key? Commented Aug 9 at 3:35
• I'm saying this is a possibility, I have no idea what's actually happening Commented Aug 9 at 3:36

I'm not actually convinced that this is actually useful to save bandwidth in constrained environments. Sometimes, in specifications, sentences like “it is useful in this scenario” get written in even though the scenario is hypothetical.

However, I am familiar with environments where a system will verify a signature, yet does not store the key. There are secure environments that do not have any rewritable persistent storage, but have some ROM code (identical on all devices of the same model) plus a very small amount of one-time writable memory (a typical amount would be a little over 256 bits). During manufacturing, the vendor burns a hash of its root CA public key (and also a secret key that never escapes the secure environment). To make the secure environment do something, you send it code and data signed by a key that comes with a certificate chain from the vendor's CA. The device checks that the hash of the public key at the root of the chain corresponds with the reference hash in its one-time writable memory. On the devices that I'm familiar with, the amount of data that you'd need to upload is large enough that saving the transmission of the public key would be negligible and not worth the extra complexity.

I would imagine that recovering the public key from a signature is more useful in environments that manipulate a large amount of data because they store a large number of signatures. Blockchains come to mind. But that's not a domain that I'm very familiar with.

In any case, it is of course useful to know that it's possible to recover the public key, because it means that ECDSA signatures offer no privacy.

• I don't fully understand the ROM scenario you described above - won't you required a signed public key to be recoverable from the signature for the usefulness you described - rather than just being able to recover the public key? Commented Aug 9 at 3:06
• @user93353 I wanted to give an example where, in principle, we could use the public key recoverability to save bandwidth (but we don't because it's not worth the trouble). We send the message, a signature S1 by the operational CA, a certificate C1 of the operational CA by the root CA, and a root CA certificate C0. We could skip the operational CA public key in C1 since it's recoverable from the signature S1 and verifiable using C0, and we could skip the root CA public key in C0 since it's recoverable from C1 and verifiable using the hash in one-time writable memory. Commented Aug 9 at 6:20

But the whole idea of signatures is that the verifier needs to already need to know the public key - else the whole verification becomes meaningless.

That's not true. Somewhere in the verification process it is required that the public key is trusted. This is why leaf (and parent CA certificates) are - for example - included in higher level signature schemes such as CMS (aka PKCS#7). As long as a trust path can be established to a trust anchor then the signature can be verified to have come from a specific entity that controls the private key.

This is assuming that the other information in the certificate is also valid and that the certificate is used for the correct purpose; I'll leave the finer details of PKI out of the answer if you don't mind.

Let us say Alice signs a message & sends the message & the signature to Bob. Now Bob knows her Public Key & he can check if the message has indeed been signed by someone who has the private key corresponding to the public key he knows for sure is Alice's Public Key.

Yes, that's correct.

Let's say Mallory intercepts Alice's message & signature. He changes the message & signs it with his own private key. Now Bob gets the tampered message & the signature. Bob doesn't have Alice's Public Key - so Bob recovers what he thinks is Alice's Public key from the signature - then verifies if the message is signed by who ever has the Private Key corresponding to that public key. Now the Public Key Bob recovers is actually Mallory's & not Alice's. So Bob will never know that the message has been tampered. So what is the point of the signature?

Same as it always was, but without a pre-distributed key. In the example above it is assumed that Mallory cannot obtain a valid certificate, so any public key / certificate containing (or implying a specific public key) cannot be produced by Mallory.

This was just an example using PKI, schemes may and willuse other methods to establish trust. In this case the various crypto-coin standards are probably more on topic.

• In the document, it's just recovering the public key from the signature - not a signed public key - i.e. not a certificate - so how does Bob trust the public key he got from the signature? Commented Aug 8 at 14:47
• You can still sign the encoded public key even if it is only available after retrieving it from a signature. Commented Aug 8 at 16:06
• I don't understand - who can sign the public key after recovering it from the signature? Your original answer said that the usefulness of a recoverable signature is in the fact that it can be checked against the signer. But that is possible only if the public key recovered is a signed public key rather than just a naked public key Commented Aug 9 at 3:07
• You sign the public key before it is put into the signature. Then the party that needs to verify first performs the verification of the signature, retrieves the public key and now can also verify the signature over the public key. This is about reducing data in transport, rather than when adding trust to the public key. Anyone who can verify the signature will also get the public key anyway... so where's the problem? The only issue is that the signature verification happens before the rest of a certificate (etc.) can be verified. Commented Aug 9 at 13:48
• You sign the public key before it is put into the signature` - I don't think that is the kind of recovery of public key they are talking about - I think they are talking about mathematically recovering the public key from the signature. Consider the "it is generally possible to determine the public key Q, at least to within a small number of choices" - if a public key (signed by issuer or otherwise) was just getting appended to the signature, there why would there be a small number of choices - there would just be 1 signature. Commented Aug 9 at 14:01