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/