From: Jason Coombs [jasonc@science.org]
Sent: Friday, January 10, 2003 8:46 PM
To: Kenneth Buchanan; 'Tom Arseneault'; Chris Matthews; 'Frank Knobbe'
Cc: secprog@securityfocus.com
Subject: RE: PGP scripting...

The RSA key generation algorithm as described by Prof. Bernd-Peter Paris at

http://thalia.spec.gmu.edu/~pparis/classes/notes_101/node63.html

is slightly different than was transcribed and posted to the list by Tom
Arseneault. Here is the correctly-transcribed algorithm, note that e*d must
be ((a multiple of z) + 1) not (a multiple of (z+1)) which could be more
clearly explained than it is on the Web page listed above, and I've replaced
the period with the asterisk to indicate multiplication. Also, Tom's
transcription left out the special conditional requirement for e, making it
seem as though d and e were chosen arbitrarily and completely independent of
one another:

Algorithm:
1. Select two prime numbers p and q
2. Let n=p*q
3. Let z=(p-1)*(q-1)
4. Choose a number d that does not divide z (z modulo d != 0)
5. Choose a number e such that e*d = (a multiple of z) + 1

Example:
1. Choose primes p=3,q=11
2. n=33 (n=3*11)
3. z=20 (z=(3-1)*(11-1))
4. Choose d=7 (20 modulo 7 != 0)
5. Choose e=3 (3*7=(1*20)+1, 20 modulo 20 = 0)

Tom Arseneault wrote:
"e and n are published as the public key while d is kept secret as the
private key."

therefore the public key in this example is {e=3,n=33} and it's coincidence
that e=p based on the small primes chosen for the example, normally e!=p.

Example 2 is more clear in this respect:
1. Choose primes p=11,q=17
2. n=187 (n=11*17)
3. z=160 (z=(11-1)*(17-1))
4. Choose d=51 (160 modulo 51 != 0)
5. Choose e=91 (91*51=(29*160)+1, 4640 modulo 160 = 0)

therefore the public key in this example is {e=91,n=187} and the private key
is d=51.

to get p=11 and q=17 from d=51 is obviously impossible, but there's more to
the private key than just d=51, isn't there? don't you have to have both p
and q in addition to d in order to have a functional private key that can be
used for cryptographic transformations? Most importantly, doesn't the
private key include the value 29 as one of its parameters based on the
second example? That is,

91*51=(29*160)+1, and since 29*160=4640 and 4640 modulo z = 0, 91 is an
acceptable e

If this value 29, the multiple of z that makes e valid for use as part of
this key pair, is included in the private key data then you DO know BOTH e
and n automatically if you have a copy of the private key.

Worst-case, if a private key contains only p and q in addition to d then the
n portion of the public key is known, which leaves only e unknown but e is
easily derived when p, q, d and n are known and you are in possession of a
sample of the ciphertext produced using {e,n} -- thus anyone who possesses a
private key can derive the corresponding public key if the public key is
ever used to produce ciphertext.

The cryptanalysis would look something like this, based on reversing the key
generation algorithm:

(the potential e is labeled x here, since z is known but e is not I'm using
variable x to represent the search for e)

a potential e is found when ((x*d)-1) modulo z = 0
for range {x=z*1, ..., x=z*(((d*e)-1)/z)}
(this list of potential e's for all {d,z}'s could be precomputed and stored
in a database prior to cryptanalysis)

use x in place of e along with n to encrypt the plaintext to find out if you
get the same ciphertext as the public key holder did, and you're done.

the smaller the ratio e/z the easier the cryptanalysis for any RSA public
key for which you are in possession of p, q, d and n, since the number of
iterations required to exhaust the search for e is smaller when z is a
larger percentage of e, and starting from x=1 you only have to try
((d*e)-1)/z iterations before you are guaranteed to find e. You won't know
what e is when you start out, but you won't have to search anything close to
the entire key space to discover e.

This, in a nutshell, is why I thought (still do think?) there was (is?) a
difference between the private and the public key in an RSA key pair and
that you could NOT arbitrarily choose which of the two keys you wanted to
use as the public key.

I'm probably still confused/mistaken, so I would appreciate some additional
enlightenment. I really thought I understood this clearly before I spent
time thinking about it again.

Sincerely,

Jason Coombs
jasonc@science.org