Cryptography
rsa public-key key-recovery
Updated Tue, 14 Jun 2022 00:37:53 GMT

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.

Solution

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.

Comments (5)

  • +1 – 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 08, 2015 at 21:18  
  • +0 – On a more practical note: before doing this calculation you must first calculate $m_i$ by performing the right padding mechanism. — Jun 08, 2015 at 22:34  
  • +0 – 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 09, 2015 at 14:15  
  • +2 – 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. — Jun 11, 2015 at 02:14  
  • +1 – @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. — Jun 11, 2015 at 12:36  

References