# RSA public key recovery from signatures

Is it possible (how) to recover public (512 bit long) RSA key from multiple signatures having corresponding plain texts. Padding is not randomized. I need it to verify any future message comming from the same source.

• That's an odd problem; are you really trying to verify that the signatures are from the same source, even if you don't know what that source is? – poncho Jun 8 '15 at 21:12
• Well, the context is that those plain-text messages signed by an unknown private key are kind of electronic certificates signed by a central authority. Those certificates, extended to parties from a certain context, are used to sign electronic documents. I am one of those parties from that certain context so I have certificates that belong to me that I know are valid but I am unable to truly validate any electronic document from any other party since I can not validate it's certificate since the authority's public key is kept in secret even though it should have been published. – Glushiator Jun 9 '15 at 22:14

## 1 Answer

Suppose you have two message-signature pairs, $(m_1, s_1), (m_2, s_2)$, where $s_i = m_i^d \bmod n$. Suppose we also know the public exponent $e$—it is usually $65537$, $3$, $5$, $17$, or some similar small integer. Then we know that $m_i = s_i^e \bmod n$, or in other words $s_i^e = k_in + m_i$ and it follows that $\gcd(s_1^e - m_1, s_2^e - m_2) = \gcd(k_1, k_2)n$, where $\gcd(k_1, k_2)$ is expected to be small.

• Note that, while Samuel's answer is correct, and shows that an attacker can rederive the public key (at least for small $e$), that might not what you want to do routinely. For $e=65537$, this implies computing the $gcd$ of two bignums each 4 million bytes long -- that might take a while... – poncho Jun 8 '15 at 21:18
• On a more practical note: before doing this calculation you must first calculate $m_i$ by performing the right padding mechanism. – Maarten Bodewes Jun 8 '15 at 22:34
• I am able to understand this answer after some thought, but the fact that it skips over the encoding of $m$ and doesn't explain how to get to the final solution may confuse readers that just get the signature values and know how to code (+ hopefully some basic math skills). – Maarten Bodewes Jun 9 '15 at 14:15
• Vanilla Python will likely be too slow here. Instead, try Sage or, if you do not want a gigantic package, use gmpy to use GMP for the arithmetic. It will be much faster than Python's native quadratic algorithms. – Samuel Neves Jun 11 '15 at 2:14
• @SamuelNeves I am speechless... like for real man... seeing yesterday how long it takes with python to calculate gcd for my numbers I wrote a small ctypes wrapper for openssl's gcd function and it still was eating at the CPU without a pause for minutes (didn't wait)... and then using your advise to look at gmpy I rewrote my code to use it... 3 lines were changed, 2 that prepare those big numbers and a call to gcd... I cliked execute and 12 seconds later I have got the result! The python naive version is still calculating, eating bits away, still 19000000 to go and several hours. – Glushiator Jun 11 '15 at 12:36