Public Key Cryptography

Date: 05/13/97 at 10:27:55
From: William Garry
Subject: public key cryptography

I have to explain public key cryptography and I am having a hard time 
finding sources. I have found several on the Internet, but have not 
been able to easily understand the material. Can you give an easy 
example of how public key cryptograhy works and perhaps some other 
sources?

Date: 05/17/97 at 18:46:28
From: Doctor Daniel
Subject: Re: public key cryptography

Hi William,

You asked a question about public key cryptography.  I'm going to 
start by giving you a good reference for it, which should be fairly 
easy for you to find. There's a fairly technical, but still very 
clear explanation of RSA cryptography, which is the "standard" public 
key cryptosystem in _Introduction to Algorithms_, by Corman, Leiserson 
and Rivest, starting on p. 831. This book is a very well-used 
textbook for algorithms courses, so if there's a university or college 
anywhere near you, it's very likely it'll be in the library.  It is a 
fairly pricey book ($60 or so).  Ron Rivest of MIT is the "R" in 
"RSA;" he's the primary inventor of the RSA system.

I don't know much about on-line resources for this topic; you might do 
well to look at the PGP site at MIT or at the company PGP Systems 
itself.

Anyhow, I'll also try to answer your question here myself. 
Specifically, let's suppose that a person S wants to send a message m 
to a person R.  To make life much easier, let's suppose that m is a 
"small" positive integer; that is, it's only a few hundred bits long.  
It's not too hard to imagine how to send any message that way; maybe, 
take blocks of the letters in a text message and turn them into a 
string of bits, using the ASCII encoding, maybe, and then just convert 
that string of bits into an integer by viewing it as a very large 
number. So one large text message might turn into a bunch of integer 
messages, each of which is sent separately. (This should be fairly 
easy to understand, but if not, just suppose that the message is one 
smallish integer.)

So S wants to send m to R.  Moreover, S doesn't want O, an outsider, 
to be able to understand m, or to be able to use m's encoding to help 
him understand further messages, either.

There are basically two ways this problem has traditionally been 
attacked: standard shared-key cryptosystems, and public-key 
cryptosystems. I'll try to explain each of these in turn, starting 
with the more familiar shared-key systems.

Suppose that S and R have already met and agreed on some "code book" 
which, for every possible input message, m, identifies the value, 
e(m), which S should send to R. It should be clear that no two input 
messages m1 and m2 can have the same code value, or else decrypting 
that value won't be possible. Then whenever S wants to send m to R, 
he looks m up in the book, finds e(m), sends e(m) to R, and R looks up 
e(m) in a "reverse code book" to find m. There are lots of problems 
with that, however:

1) The code book will be ENORMOUS.  If we give an explicit code value 
for every input value, and there's many billions of them, that will 
take up a very large amount of memory.

2) If, instead, the code book is made small, by having few possible
messages, it might be easy for O to decrypt messages, just by having 
some idea of the frequency with which various strings come out of S.  
An extreme example of this would be something like newspaper 
cryptograms, which work on the same general principle; if messages 
are, say, 3 letters long, and the message number 2712 keeps coming 
fairly often, that might correspond to "the," for example.  

So this method is not feasible; either the code is fairly easy to 
decrypt, or the code book takes up too much memory.

A reasonable compromise to that is the shared-key system, which works 
like this:

S and R agree on some fairly complicated function f, which is used to
change m into e(m). However, f takes as its input two values: the 
message m, and another piece of information called the key, k; that 
is, e(m) = f(m,k). Maybe f is even made fairly public knowledge, so 
that even O might know what it is. However, without knowing k, it's 
still very hard for anyone besides S and R to figure out the message.  
Also, the inverse function to f is also dependent on k. As a very 
simple example, suppose we had the code that just adds k to every 
received message. Then r, who knows k, just subtracts it from the 
received message. And O can't just try lots of input messages to find 
out what S is sending. (This is, of course, a toy example.)  

This is how DES, the Data Encryption Standard works.  S and R agree on 
some smallish number as a key, m is put through some complicated 
machine that includes the key, and the result is decrypted by R using 
some other complicated machine that also requires the key.

This seems like a much better idea. We have secure communication that 
doesn't require acres of space.  What's wrong with this idea?  
Three things:

1) Suppose that S and R are on different continents. How do they 
exchange keys? The whole point is that O could be listening on the 
channel _at any time_, including any time they might send the key!  
So they'd have to meet face-to-face. Also, if the security of R is 
ever compromised, R would need to get new security codes face-to-face 
for _everyone_ R communicates with.  What a pain!

2) R needs to store secret codes for everyone he communicates with.  
This isn't usually a problem, but suppose R is a bank, say.  Then, it 
might be a huge number of these codes, which have to be EXTREMELY 
secure!  This might be expensive.

3) S and R have to plan ahead about communicating. Suppose that R 
posts something really intriguing to a maillist that S reads, and 
that S wants to reply securely. But S and R haven't yet exchanged 
keys, so that's not possible!

So shared key cryptosystems are a problem because keys need to be 
exchanged well in advance and because a communicant must store keys 
for everyone he/she communicates with.  

A public-key cryptosystem is an attempt to work around this problem.
Suppose that "everyone" has a function, which is very easy to compute,
associated with them, and that all S has to do in order to communicate 
with R securely is to download R's function, f, compute f(m), and send 
it to R. Also, assume that f is a "one-way" function. That is, knowing 
f(m), it's very hard to compute m; it's hard to compute f-inverse, 
even if you know how to compute f.

Then O is powerless to understand S's message; O can compute f, but 
not f-inverse.  But suppose that R knows enough to easily compute 
f-inverse. Then R can easily turn f(m) back into m, and read the 
message.

That's the idea behind public-key cryptosystems. There's a family of
functions, each of which takes a key, k, called the public key.  
Whenever S wants to send to R, S finds out what R's public key is, and 
computes f(m,k), and sends it to R. O can't understand the message, 
even though he can download R's key as well. R receives the message 
and, using the information necessary to decode the message, called the 
private key, computes f-inverse(f(m)) = m.  

So all we need is a family of functions which have that property, and 
we're set. I think I'll point you to the reference for that. The way 
RSA does is it is to notice that it's very easy to compute the product 
of two large prime numbers; that takes roughly time proportional to 
the number of bits necessary to store the numbers. On the other hand, 
it takes enormous amounts of time to factor a product of two large 
numbers; the best known algorithm will take roughly time proportional 
to the fourth-root of the product. So, for example, if we take two 
100-digit prime numbers, it takes roughly 100 time units to multiply 
them, but 10,000,000,000,000,000,000,000,000 time units to factor 
their product! So, in RSA, the public key, k, is related to the 
product of the two numbers, while the private key is related to the 
two numbers themselves. Therefore it's very hard to figure out the 
private key from the public key.  

Now, we see that we've answered all of the previous problems:

S and R don't need to meet to share keys; S must simply find some way 
to download R's key.  

Also, R only needs to store R's private key in a secure place; other 
keys can be gotten from the download point on the fly. 

However, we have a couple new problems:

It's a lot more difficult to make these 1-way functions that are hard 
to invert than you might think. One method which was popular for a 
while turned out not to be very secure, because it was possible to 
guess the private key based on the values of the function at certain 
specific points. So that's not so easy.

Also, there are patent problems: the idea of public key cryptography 
is patented, and there's much messiness there.  

More of a problem, suppose that O is able to substitute his own key 
for R's key when S downloads R's public key. Let's think of what a 
sinister O might do: O could download R's key, substitute his own, 
wait until S sends an encoded version of m to R, intercept that 
message, decrypt m, substitute a whole new message, encrypt that 
message in a way R will understand, and send it to R. Now, R has an 
entirely different message, and it seems like S sent it!  

Turns out that there are ways around _that_, too; basically, they deal 
with yet another encryption concept called "digital signatures," which 
allow R to be "certain" that S sent R the message.  But that gets even 
farther afield.

So basically, the public key system works by allowing S to look R's 
key up in a database, and making sure R is the only person who can 
understand messages sent to him, even though anyone is able to send R 
messages securely.

I do hope this answers your question. As you've no doubt become aware
through this message, public-key cryptography is kind of confusing.  
But it's also vital. I hope you are able to learn more about this 
important subject.

Good luck!

-Doctor Daniel,  The Math Forum
 Check out our web site!  http://mathforum.org/dr.math/