joev
Sophie SchmiegNew blog post: Recovering public keys from signatures. It turns out public keys, are, in fact, public.
https://keymaterial.net/2024/06/15/reconstructing-public-keys-from-signatures/
SpaceLifeFormWhich begs my question: Why is there such a push to create new public signing keys all of the time?
Are they just flat-out admitting that their security is so bad and the private key can be or was leaked?
It should not be leaked in the first place.
@SpaceLifeForm ?!? This post is about recovering public keys. A signature scheme that didn't keep it's private key secure would not be very useful now, would it?
Exactly. Why should the public key have to be recovered in the first place?
Shouldn't I be able to recover the public key from the private key anyway?
trystimuli@SpaceLifeForm
you have *just* a signature, no private key, no public key. you want to find the public key that goes with the signature.
you have *just* a signature, no private key, no public key. you want to find the public key that goes with the signature.
If I do not have the public key, then what good is the signature?
So, if I can derive the public key, and in theory, verify the signature, does this mean I know who created it and can be trusted?
@SpaceLifeForm i mean, sometimes people make protocols that assume that signatures can be sent without revealing the public key. and that’s true for some signature schemes and not for others.
for intentional use, suppose you have a key-value store where you can query by a signature on an item for a particular one, or by public key for the most recent items with matching signatures. if you query by a signature and don’t get any items, you could recover the public key and then query by that, and be assured that any results were signed with the same secret key.
i’m not sure what extent you mean “trusted”, but if you can recover a public key from a signature, you can at least trust that the secret key (that you presumably don’t know) corresponding to that public key is the one that produced the signature.
@tryst @SpaceLifeForm yeah, you can use this to verify signatures once you've reconstructed the public key. You'll need to trust the signatures you use for the reconstruction are valid, but after that you have just a normal public key.
You can also use this for example if you have a large collection of signed payloads, and want to know which payloads share the same sender, at least for the ECDSA case, where you only need a single signature.
@sophieschmieg
thank you for talking about both types of schnorr signatures!
another thing i think about is finding alternative public keys for signatures. it's rarely stated as a requirement (even if it is assumed) and most schemes have it. clearly if you can recover the public key or the public key is hashed in you can't do that, but rsa needing two signatures makes me wonder…
thank you for talking about both types of schnorr signatures!
another thing i think about is finding alternative public keys for signatures. it's rarely stated as a requirement (even if it is assumed) and most schemes have it. clearly if you can recover the public key or the public key is hashed in you can't do that, but rsa needing two signatures makes me wonder…
@tryst I can't see a way of doing it for RSA, but for UOV it is very easy to find a second key under which a specific signature verifies, you can find an alternate one that verifies up to (u+o)(u+o+1)/2 - 1 message/signature pairs using the same method I used to find the actual public key, given that it's polynomial interpolation you would get an underspecified linear system and have extra solutions.
The funny thing about that fake public key is that it would be a public key without a private key necessarily even existing.
@tryst thinking about the RSA case a bit more, a message/signature pair (m, s) will verify if and only if s^e = m mod n. So we have s^e - m = k*n for some integer k. In other words any factor of s^e - m will be a valid RSA public key, but of course factoring a number that large isn't going to be easy and is unlikely to result in a public key of the right size.
@sophieschmieg yeah, thinking about the RSA method you laid out some more, if you attempt it with two messages signed with different keys you’re extremely likely to get a much smaller result with like a… ~55% chance of 1.
i guess this also suggests that you can, with enough factoring, probably recovery the RSA public key from one signature, as you’re unlikely to have more than two prime factors of s^e-m in the right range. and of them are very likely much smaller…
together, i think that implies that you can probably trust the RSA public key you recover from two message-signature pairs is the right one. (and so do the signed payloads checking thing you mentioned).
Frederik Braun �@sophieschmieg cool blog post! Thank you for sharing as I am already looking forward to the promised three other posts ;)
@sophieschmieg I found a minor editing mistake. I believe there is a missing space between the variable `n` and the next words "with generator" (in the sentence starting with "For Schnorr, we have the usual"). Could also be a webkit rendering thing as I am reading this on an iDevice.