I have read Is sharing the modulus for multiple RSA key pairs secure?, which explains an algorithm for factoring an RSA modulus n given only one encryption and decryption exponent tuple. Given multiple such tuples, is there a more efficient way to compute p and q? It seems like we could set up a system of equations using the Chinese Remainder Theorem and then could solve for Euler's totient directly. Once we have Euler's totient, we could solve a system of two equations with N and totient(N) to obtain p and q.
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
Given multiple such tuples, is there a more efficient way to compute p and q?
Possibly, however given how efficient the standard probabilistic method is, we generally don't bother. Now, someone did find a nonprobabilistic algorithm to do so (proving that the problem is in P, not just in RP); however, it's less efficient in practice, and so that isn't used.
It seems like we could set up a system of equations using the Chinese Remainder Theorem and then could solve for Euler's totient directly.
It's a little trickier than that; one issue is that we may have $ed \not\equiv 1 \pmod{(p-1)(q-1)}$; hence what such a series of equations would give might not be $(p-1)(q-1)$, but instead $\text{lcm}(p-1, q-1)$. Now, in practice, $(p-1)(q-1)$ is extremely close to $N$, and hence it should be possible to give a good guess of $(p-1)(q-1)$ given $\text{lcm}(p-1, q-1) = (p-1)(q-1)/\gcd(p-1, q-1)$; however, it is nontrivial to write up an algorithm that will work in general. In contrast, the standard probabilitic method always works (ok, half the time...)
