From msuinfo!caen!malgudi.oar.net!witch!cyberg!fb Tue Jan 11 22:02:44 1994 Path: msuinfo!caen!malgudi.oar.net!witch!cyberg!fb Newsgroups: sci.crypt Message-ID: <46@cyberg.win.net> Reply-To: fb@cyberg.win.net (Francis Barrett) From: fb@cyberg.win.net (Francis Barrett) Date: Sat, 08 Jan 1994 05:18:32 GMT Subject: Re: Factoring N+P*Q when (e,N,d) is known. Lines: 115 Theo Van Dinter writes... > Hello. Excuse me for jumping in the conversation, but the topic > is something I am currently working on. Also excuse me because > I'm a novice at RSA type encryption. Would you be able to > explain, or tell me where to find a description of how > (generalistic ally or precisely) the method works? There's a nice explanation in "Cryptography: A Primer" by Konheim if you want all the gory details but I can easily give you a simple example. > from what I've read, you take E (odd number), and P and Q > (primes). get N by multiplying Q and P, and then find D by > taking (p-1)(q-1)(e-1)+1 all divided by E. Some of that is correct. More precisely, you pick two distinct odd primes, P and Q. You then multiply them together to get a modulus N = P*Q. If you pick any number E which is relatively prime to (P-1)*(Q-1), exponentiation to E modulo N will be a permutation on the integers modulo N. If D is a number such that E*D = 1 MOD (P-1)(Q-1), exponentiation to D modulo N will be the inverse of that permutation. > I have tried this with significantly small values of the numbers > (E as 5, P as 3 and Q as 5), and the method doesn't work. N = 15 works fine, although it is somewhat less exciting because E always equals D and raising to the 5th power modulo 15 is the identity transformation. The smallest modulus you can pick where something interesting happens is 33, which is 11*3. Then you can pick E to be 3 and D to be 7. (P-1)*(Q-1) is 10*2 or 20. Observe that E*D = 7*3 = 21 which is 1 mod 20. You could also have used 13 and 17 for E and D because 13*17 is 221 which is also 1 mod 20. Raising the numbers 0...32 to the third power modulo 33 yields... 0 1 8 27 31 26 18 13 17 3 10 11 12 19 5 9 4 29 24 28 14 21 22 23 30 16 20 15 7 2 6 25 32 Raising the numbers 0...32 to the seventh power modulo 33 yields... 0 1 29 9 16 14 30 28 2 15 10 11 12 7 20 27 25 8 6 13 26 21 22 23 18 31 5 3 19 17 24 4 32 These two permutations are inverses of each other. Looking up a number in the first table and then looking up that number in the second will give you back the number you started with. > I would try larger values, but my computer tends to not like > things such as 66 to the 7th power mod 35.. (at least I > haven't found the method to do this yet.) This is because 66^7 is about 5 trillion. When doing modular exponentiation, it is necessary to modulo frequently to keep things within range. Then everything works nicely. If you make yourself a little table of geometrically increasing powers of 66 modulo 35, like this... 66 ^1 MOD 35 = 31 66 ^2 MOD 35 = 16 66 ^4 MOD 35 = 11 66 ^8 MOD 35 = 16 66^16 MOD 35 = 11 66^32 MOD 35 = 16 66^64 MOD 35 = 11 Then you can calculate 66 to any power by simply selecting the entries corresponding to the bits of the exponent and multiplying them together modulo 35. For instance... 66^7 = 66^1*66^2*66^4 = 31*16*11 = 31 MOD 35 This method of modular exponentiation works nicely even when the modulus and the exponent are many hundreds of bits in length. Now let's encrypt something using RSA with a modulus of 33. Our public key will be (E,N) or (3,33). Our secret key will be (D,N) or (7,33). Our plaintext will be the familiar C string "Hello World.\n", which is the following hexadecimal integer... 48656C6C6F20576F726C642E0A A quick conversion to base 33 yields... 2 14 22 27 18 31 6 23 0 4 4 21 31 21 15 20 13 10 16 1 31 Raising this modulo 33 to the power of the public exponent E=3 yields... 8 5 22 15 24 25 18 23 0 31 31 21 25 21 9 14 19 10 4 1 25 And now back to hexadecimal to yield the ciphertext... F1F4A7DEFC4E7FFE546F94B09F We now send this data to the owner of the secret key who reverses the process by converting to base 33, raising each number to the power of his secret exponent D=7, and upon conversion back gets the familiar message "Hello World.\n". Of course in real life, we use much larger numbers for P, Q, E, and D. Also, since RSA is somewhat slow when encrypting large messages, we use a strong product cipher like DES or IDEA with a random session key to encrypt the message, and then encrypt the session key with RSA. Since the session key is usually much smaller than the modulus, we don't have to go through a base conversion, but simply pad with additional random data in unused bit positions. That's RSA in a nutshell. --------------------------------------------------------------- Francis Barrett, F.R.C. | Thou canst not travel on the path | The Cybernetics Guild | before thou hast become the Path | fb@cyberg.win.net | itself. | ---------------------------------------------------------------