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 jasoncat_private
This archive was generated by hypermail 2b30 : Sat Jan 11 2003 - 15:58:38 PST