From: ghio@cmu.edu (Matthew Ghio)
Date: Sat, 18 Jun 94 02:34:47 PDT
To: cypherpunks@toad.com
Subject: Re: Prime magnitude and keys...a ?
Message-ID: <9406180933.AA00430@toad.com>
MIME-Version: 1.0
Content-Type: text/plain


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.