Welcome to the new Woodmann RCE Messageboards Regroupment
Please be patient while the rest of the site is restored.

To all Members of the old RCE Forums:

The old vBulletin forum was converted to phpBB format, requiring the passwords to be reset. If this is a problem for some because of a forgotten email address, please feel free to re-register with a new username. We are happy to welcome old and new members back to the forums! Thanks.

All new accounts are manually activated before you can post. Any questions can be PM'ed to Kayaker.

## recover RSA primes p and q if we have n,d,e

To discuss DES MD5 El-Gamal RSA PGP and others....
Solomon
Posts: 358
Joined: Tue Sep 11, 2001 12:35 am
Location: Heaven
Contact:

### recover RSA primes p and q if we have n,d,e

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?
mike
Posts: 491
Joined: Tue Mar 06, 2001 12:00 pm
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.
Solomon
Posts: 358
Joined: Tue Sep 11, 2001 12:35 am
Location: Heaven
Contact:

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 mike
Posts: 491
Joined: Tue Mar 06, 2001 12:00 pm
Where does the conclusion "k^phi(n) = 1 mod n" come from?
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.
Aquatic
Senior Member
Posts: 176
Joined: Thu Dec 12, 2002 7:56 am
Wow, I never knew "phi" was involved in RSA. Very interesting.
mike
Posts: 491
Joined: Tue Mar 06, 2001 12:00 pm
"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 )
Aquatic
Senior Member
Posts: 176
Joined: Thu Dec 12, 2002 7:56 am
So "Euler's totient function" has nothing to do with 1.618 (The golden ratio)? Or is there some connection?
mike
Posts: 491
Joined: Tue Mar 06, 2001 12:00 pm
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/teac ... uc_rsa.htm

or

http://www.funet.fi/pub/crypt/old/ghost/LUC/luc_vs_rsa
Aquatic
Senior Member
Posts: 176
Joined: Thu Dec 12, 2002 7:56 am
mike wrote: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/teac ... uc_rsa.htm

or

http://www.funet.fi/pub/crypt/old/ghost/LUC/luc_vs_rsa
edit: ok, I understand.