5
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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...)

$\endgroup$

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.