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?

Yes, it's possible. Remeber that the usual way to factor n is to choose a kth order (k>1) polynomial g(x) and find x,y such that g(x) = g(y). Then gcd(x-y,n) has a high probability of being a factor. Usually they choose g(x) = x^2 mod n.

Consider n=35. If g(x) = x^2 mod n then g(1)=g(29), and 29-1 is a multiple of 7, a factor.

de-1 = phi(n) (f in your post), and *any number k but zero* gives k^phi(n) = 1 mod n. (de-1) = c*phi(n), so k^(de-1) = 1^c = 1 mod n as well.

Since phi(n) = (p-1)(q-1), and p and q are both odd, it's divisible by 4. Calculate m for a few different k:

m=k^((de-1)/4)

m will often be a number other than +/- 1. If you raise one of those m to the 4th power, you know you have to get 1. So in this case, g(x) is x^4 mod n and we have

m^4 = 1^4 mod n

and m-1 is a multiple of p or q. Use gcd(m-1,n) to find the factor.

Thx mike for your explanation.

I still have a few questions.

Where does the conclusion "k^phi(n) = 1 mod n" come from?
and why (m-1) is a multiple of p or q?

Thx

That's how RSA works. Let f=phi(n).

ed=1 mod f, right? So choose a message k, and compute

c=k^e mod n.

c is the ciphertext. Then to decrypt, compute

c^d = k^ed = k^1 = k mod n

since

ed=1 mod f,
ed-1 = 0 mod f,

and

k^(ed-1) = k^0 = 1 mod n

I explained why m-1 is a multiple of a factor in the last post, but here's another try:

1 will have four quartic roots mod p, and four quartic roots mod q. A quartic root is a number r such that r^4 = 1. For example, 6 is a quartic root of 1 mod 35: 6^4 = 1 mod 35.

There will be exactly 4*4=16 different quartic roots of 1 mod n, four from p times four from q.

Since k^(ed-1) = 1, then m=k^((ed-1)/4) has to be one of those 16 numbers, because

m^4 = k^(((ed-1)/4)*4) = k^(ed-1) =1.

Then m^4-1 = (m-1)(m^3+m^2+m+1) = 0 mod n. So either (m-1) or (m^3+m^2+m+1) are multiples of n, and you gain no information about the factors, or one term is a multiple of p and the other is a multiple of q. Using gcd(m-1,n) will pick out the common factor.

Wow, I never knew "phi" was involved in RSA. Very interesting.

"Phi" is a symbol used for different things in different places. Here it means Euler's totient function; one other place you may have seen the symbol is referring to the constant (1+sqrt(5))/2, the "golden ratio". When you have a rectangle L x W such that

(L + W) / L = L / W

then L / W = (1 + sqrt(5)) / 2 = phi.

Phi is also often used as a symbol for phase (3 guesses why )

So "Euler's totient function" has nothing to do with 1.618 (The golden ratio)? Or is there some connection?

Euler's totient function has no direct relation to the golden ratio that I know of, although you can get totient-like behavior if you consider quadratic recurrence relations modulo composites.

The LUC cryptosystem calculates the nth term in a Lucas sequence (a sequence in which the ratio of consecutive terms approaches the golden ratio) rather than raising to the nth power. Since the sequence grows exponentially, it's essentially the same thing.

See
http://math.boisestate.edu/~marion/teaching/crypto2s03/luc_rsa.htm

or

http://www.funet.fi/pub/crypt/old/ghost/LUC/luc_vs_rsa

edit: ok, I understand.