Solomon

May 14th, 2003, 03:20

If we have n, d and e of RSA, we can encrypt/decrypt without any problems.

But just for curiousness, is it possible to recover p and q from n, d and e?

for RSA, we have the following 4 equations:

n = pq

f = (p-1)(q-1)

gcd(e, f) = 1

de = 1(mod f)

We can factorize (de - 1) to get f, then solve the following equations to get p and q:

pq = n

p+q = n+1- f

But to factorize (de-1) is quite difficult though it has some small factors. Any idea?

But just for curiousness, is it possible to recover p and q from n, d and e?

for RSA, we have the following 4 equations:

n = pq

f = (p-1)(q-1)

gcd(e, f) = 1

de = 1(mod f)

We can factorize (de - 1) to get f, then solve the following equations to get p and q:

pq = n

p+q = n+1- f

But to factorize (de-1) is quite difficult though it has some small factors. Any idea?