Jim choate <ravage@bga.com> wrote: | No, again it will allow you to find the secret key, it will not | provide any information about the factors of that number. It might | be used for that but as you have pointed out, it takes a long time. Okay, obviously neither you or Perry know what you're talking about, or you are too busy flaming each other to express your thoughts coherently. Finding the secret key WILL allow you to factor the modulus (assuming you know the public key). Therefore, solving for the secret exponent is equivilent to factoring. This has been discussed before. I thought you have been on the list long enuff to remember it, but it is obviously necessary to restate the explanation for those who haven't seen it before. Assume we have: Two (unknown) prime numbers p and q, a known modulus n, where n is the product of p and q, and known public key exponent e. Now, suppose someone discovers the corresponding secret key d. Now assuming the case where de=(p-1)(q-1)+1, we have two equations with two unknowns: pq = n de = (p-1)(q-1) + 1 Solving for p and q is simply a matter of solving simeltaneous equations. First, we rewrite the second equation: de = pq - p - q + 2 Now we substitute the known values for de and pq and do some simple algebra: p = n - de + 2 - q Substitute p in the original equation: q(n-de+2-q) = n q(n-de+2) - qq = n -qq + q(n-de+2) - n = 0 qq - q(n-de+2) + n = 0 Now solve for q using the quadratic formula. q=((n-de+2)+((n-de+2)^2-4)^(.5))/2 P can then be found (of course) by dividing n by the now-known value for q. Now, there is the possibility that (p-1)(q-1)+1 will not equal d*e. However, d*e will always be equal to k(p-1)(q-1)+1 where k is an interger. Given PGP's fondness for using 17 for d, and since e < (p-1)(q-1) then de < 17(p-1)(q-1), therefore k<17. It would therefore be fairly easy to find k, since it could only be one of sixteen possible values. Furthermore, (and more importantly), it is not necessary to know the prime factorization to generate key pairs. It is only necessary to know a valid number of the form k(p-1)(q-1). You can find an inverse key for any public key just by finding its multiplicative inverse modulo k(p-1)(q-1) (k, p, & q do not need to be known.) Therefore, if you find one keypair, you can find them all.