# 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? 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. Jun 9 '15 at 22:14

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... 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. 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). Jun 9 '15 at 14:15