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?

Welcome to the new

Please be patient while the rest of the site is restored.

In order to log in, it will be necessary to reset your forum login password ("I forgot my password") using the

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.

**Woodmann RCE Messageboards Regroupment**Please be patient while the rest of the site is restored.

**To all Members of the old RCE Forums:**In order to log in, it will be necessary to reset your forum login password ("I forgot my password") using the

*original email address*you registered with. You will be sent an email with a link to reset your password for that member account.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

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

:DWARNING: Shareware authors are reading your detailed discussions without paying you!:D

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.

That's how RSA works. Let f=phi(n).Where does the conclusion "k^phi(n) = 1 mod n" come from?

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.

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

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