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/
trystimuli@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).