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.

  • $\begingroup$ 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? $\endgroup$ – poncho Jun 8 '15 at 21:12
  • $\begingroup$ 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. $\endgroup$ – Glushiator 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.

  • 1
    $\begingroup$ 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... $\endgroup$ – poncho Jun 8 '15 at 21:18
  • $\begingroup$ On a more practical note: before doing this calculation you must first calculate $m_i$ by performing the right padding mechanism. $\endgroup$ – Maarten Bodewes Jun 8 '15 at 22:34
  • $\begingroup$ 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). $\endgroup$ – Maarten Bodewes Jun 9 '15 at 14:15
  • 2
    $\begingroup$ 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. $\endgroup$ – Samuel Neves Jun 11 '15 at 2:14
  • 1
    $\begingroup$ @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. $\endgroup$ – Glushiator Jun 11 '15 at 12:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.