Reconstructing public keys from signatures
One weird hobby of mine is reasonable properties of cryptographic schemes that nobody promised they do or don’t have. Whether that’s invisible salamanders or binding through shared secrets, anything that isn’t just boring IND-CCA2 or existential unforgeability is just delightful material to construct vulnerabilities with.
Normally, with a signature scheme, you have the public key and want to know whether a given signature is valid. But what if we instead have a message and a signature, assume the signature is valid, and want to know which public key signed it? A rather delightful property if you want to attack anonymity in some proposed “everybody just uses cryptographic signatures for everything” scheme.
This one is so famous it even has it’s own Wikipedia section. In short, yes, it is very much possible to recover a public key from a single valid signature.
An ECDSA signature are two integers such that , where is one of the two points with x coordinate . Two reconstruct the public key, we can just solve for and get , where we compute as the inverse of modulo the order of the elliptic curve.
