Public Key Encryption
Date: 03/29/99 at 11:32:27 From: Jonathan Crowell Subject: Public Key Encryption I have been given a mathematics assignment in my computer science course. The assignment is to write a public key encryption program. I have been doing some research into public key encryption, but most of what I have found is very technical and difficult to understand. My basic question is this: if someone encrypts a message to me using my public key, why is it not possible for someone else, who also knows what my public key is, to decrypt the message by simply running my public key encryption algorithm in reverse? Also, could you please explain exactly how the "mod" function works? I have read some of your answers to questions about the "mod" function, but I do not yet have a clear understanding. Thanks.
Date: 03/29/99 at 12:27:43 From: Doctor Rob Subject: Re: Public Key Encryption The "mod" function can be defined as follows: To compute x (mod n), divide x by n, throw away the quotient, and the remainder is the answer. If you do the division correctly, the remainder should be in the range from 0 to n - 1. The trick with public key encryption is to make it virtually impossible for someone who knows the encryption algorithm to figure out a decryption algorithm. There are various ways to do that, based on the idea that it may be easy to do some operation, but hard to undo it. One such operation is multiplying together two large prime numbers. This is easy. Now, given the product, to find those prime factors is hard. You cannot just "run in reverse" the multiplication! If you think you can, try finding the two prime factors of 247925393283219413785644419. Another such operation is raising a public number to a private power mod(a public number): g^x = y (mod n), where g, n, and y are known, but x is not. If you think this is easy, find x in the equation 2^x = 2094218297454 (mod 2103532971451). Another such operation is raising a private number to a public power mod(a public number): x^e = y (mod n), where e, y, and n are known, but x is not. Here, if you can factor n into its prime factors, you can find x, but otherwise not. - Doctor Rob, The Math Forum http://mathforum.org/dr.math/
Date: 03/30/99 at 14:24:23 From: Jonathan Crowell Subject: Re: Public Key Encryption In your answer, you pointed out that it is easy to multiply two large prime numbers together, but it is difficult to factor out the two prime numbers given just their product. I understand that. But a person who encrypts a message to me using my public key obviously does not have access to the two large prime numbers that my particular algorithm is based on. No part of the process of encrypting a message using a public key involves multiplying together two large prime numbers - that is done beforehand. The person who wants to encrypt a message to me using my public key has access to three numbers: M (the plaintext), E (a number relatively prime to (P-1)(Q-1)), and PQ. P and Q are the two large prime numbers, of course. Now, the encrypter performs some mathematical operations on M using E and PQ to get C (the ciphertext). Anyone else with access to my public key, which is assumed to be everyone in the world, will know what E and PQ are, and will be given C. They will also know that C is M^E (mod PQ), (I think I am right about that, but I am not sure. In any case, having access to the public key entails being able to encrypt messages, so they will know the particular mathematical operations involved in encrypting a message.) But it seems incredible to me that a person can be given C and know E and PQ ahead of time, and know that C = M^E (mod PQ) -- and yet not be able to figure out what M is. Obviously, this is not the case. Can you explain why or where I have made an error? Before I go, I want to solve the second mathematical problem you gave me in your answer to my first question. The problem was this: Find x in the equation 2^x = 2094218297454 (mod 2103532971451) You defined mod as follows: "To compute x (mod n), divide x by n, throw away the quotient, and the remainder is the answer." Now, 2,103,532,971,451 is bigger than 2,094,218,297,454. The quotient would be 0 and the remainder would be 2,094,218,297,454. So now, the problem is reduced to finding x in the equation 2^x = 2,094,218,297,454. I do not have much background in mathematics, but I think this equation can be solved using a base 2 logarithm. Unfortunately, the calculator on my computer only performs natural logarithms and base 10 logarithms, so I am going to have to work it out through trial and error with the x^y function. Okay, I have figured out that x is 44.251477067515 give or take 0.000000000004. It took me about ten minutes. I was not able to narrow down the last little bit because the calculator on my computer does not accept numbers longer than 13 digits in length, but I know the answer is between ...6751 and ....6752. If I had the time to run down to the computer lab, though, I am pretty sure I could write a program that would allow one of the Sun Sparcs down there to solve the problem in a matter of milliseconds. Am I wrong? Thanks for answering my questions.
Date: 03/30/99 at 16:02:16 From: Doctor Rob Subject: Re: Public Key Encryption Multiplying together is an example of an operation that is easy one way and hard the other. In and of itself, it is *not* an example of an encryption method. The RSA Public Key Cryptosystem, which is the one you are discussing in your followup above, depends for its security on the difficulty of Given E, C, and PQ, find a number M such that M^E = C (mod PQ) It may strain your credulity, but it really is difficult! It is conjectured to be about as difficult as factoring PQ. In fact, if you could factor PQ and discover P and Q, then you could compute the decryption exponent D such that D*E = 1 (mod[P-1][Q-1]), and find C^D = M (mod PQ), thereby decrypting the message. If you cannot find P and Q, you cannot find D. Furthermore, the ability to decrypt messages without finding P and Q first probably would allow you to factor PQ using that capability. As an example, suppose E = 3, and PQ = 183487271509, and C = 128879322311. Find M. This is not easy! Finding a perfect cube M^3 which, when divided by PQ leaves remainder C, is not a simple matter. There is only one such M smaller than PQ. Try a smaller example. Without factoring PQ, let E = 3, PQ = 47083, C = 46440. Finding M is hard. It turns out that the only M smaller than PQ which works is M = 11111. Then 11111^3 = 1371700960631. When divided by 47083, the quotient is 29133677, and the remainder is 46440. In the problem I gave you, Find x in the equation 2^x = 2094218297454 (mod 2103532971451) x has to be an integer. Perhaps I should have written it in the form Find integer x such that 2094218297454 = 2^x (mod 2103532971451) where 2^x will be a VERY large number, which, when divided by 2103532971451, will give a VERY large quotient (irrelevant) and the remainder 2094218297454. As an example, 2^3854 is a number with 1161 decimal digits. When you divide it by 2103532971451, the quotient has 1148 decimal digits, and the remainder is 375356427471. And 3854, a four-digit exponent, is really a very small exponent to use; it could have had twelve digits! The function x |--> 2^x (mod 2103532971451) is a very complicated one. It is pretty easy to compute that, but hard to compute its inverse. The same is true of the map M |--> M^E (mod PQ) used in the RSA Public Key Cryptosystem. - Doctor Rob, The Math Forum http://mathforum.org/dr.math/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.