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$
$\endgroup$
2
-
$\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$– ponchoCommented Jun 8, 2015 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$– GlushiatorCommented Jun 9, 2015 at 22:14
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
12
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$– ponchoCommented Jun 8, 2015 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 ♦Commented Jun 8, 2015 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 ♦Commented Jun 9, 2015 at 14:15
-
2
-
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$ Commented Jun 11, 2015 at 12:36