Let's say that you have some small number of RSA signatures of known data: you know some pairs $(m_k, c_k)$ such that ${c_k}^e \equiv m_k \pmod n$. If you know $e$, because probably it's one of $\{3, 17, 65537\}$, is it possible to recover $n$?
$\begingroup$
$\endgroup$
1
2 Answers
$\begingroup$
$\endgroup$
5
calculate $$gcd(c_1^e - m_1 , c_2^e- m_2, \dots , c_k^e-m_k)$$
With a bit luck this should get $n$.
It will be an interesting exercise to calculate the probability of success based on the number of cleartect/ciphertext pairs.
-
1$\begingroup$ How does a GCD work with numbers that are in the 134-million-bit range (2048-bit modulus and $e = 65537$)? $\endgroup$– MyriaCommented Nov 4, 2015 at 19:19
-
$\begingroup$ Any algorithm's complexity is some function which depends on the input size of its parameters. I doubt that you find anything more efficient as a gcd calculation. $\endgroup$– user27950Commented Nov 4, 2015 at 21:18
-
1$\begingroup$ Even with just two signatures, the method will spit $n$ most of the times (>60%); and when it does not, it will almost always spit $n$ times a small integer, which is easy to factor out, revealing $n$. In Mathematica, computation time is not worth measuring for $e≤$ 257, and is like 40s for $e=$ 65537 and 2048-bit $n$. Using optimized GCD routines like that of GMP would give significant speedup. $\endgroup$– fgrieu ♦Commented Nov 5, 2015 at 8:45
-
2$\begingroup$ Note: you really want to compute $\gcd(c_1^e -\widetilde{m_1},c_2^e -\widetilde{m_2})$ where $\widetilde{m_j}$ is $m_j$ modified by whatever deterministic padding is used for signature (identity for textbook RSA signature, RSASSA-PKCS1-V1_5..). With randomized padding, the method won't work. $\endgroup$– fgrieu ♦Commented Nov 5, 2015 at 14:47
-
1$\begingroup$ @fgrieu For simplification, I'm assuming that $m$ is the post-padding message, and that I know what it is (i.e. it's deterministic as in PKCS #1 v1.5). $\endgroup$– MyriaCommented Nov 6, 2015 at 2:07
$\begingroup$
$\endgroup$
2
Note: In my answer below I neglected to consider that the the messages for the associated signatures are also known, and that this could enable the existence of a practical algorithm to recover the modulus. While I haven't done the legwork to verify, fgrieu's comment below indicates that recovery of the modulus may very well be practical. I'm leaving my original answer below for those who are curious.
For any practical number of RSA signatures, no, you will not be able to recover the entirety of the modulus $n$. You can however, with enough signatures, come up with a reasonable estimate for the value of the most significant bits of $n$ using Frequentist analysis.
It was exactly this sort of characterization of the RSA modulus that broke the key privacy scheme used on Australia's Health Care Card.
-
1$\begingroup$ In the question, we know not only the signatures, but also the messages, thus we can do much better than Frequentist analysis. The method in this other answer does work (assuming any known deterministic padding scheme), as I just confirmed by experiment with realistic parameters. Even with just two (message, signature) pairs, and regardless of $e$, it will spit $n$ with odds better than 60%; and when it does not, it will almost always spit $n$ times a small factor, that is easily found and removed. $\endgroup$– fgrieu ♦Commented Nov 5, 2015 at 14:37
-
1$\begingroup$ Footnote: if a randomized signature padding is used, e.g. RSASSA-PSS of PKCS#1v2.2, which is increasingly common, then the original answer applies, AFAIK. $\endgroup$– fgrieu ♦Commented Nov 6, 2015 at 6:19
\pmodrather than\mod(thanks to Maarten Bodewes for making just that). Hint: by definition that means $n$ is a divisor of ${c_k}^e-m_k$, and you know or can guess everything in several of these expressions. Note: recovering $n$, which is normally assumed public, hardly qualifies as a key recovery attack. $\endgroup$