Associated Topics || Dr. Math Home || Search Dr. Math

### 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,

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.

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,
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

Also, R only needs to store R's private key in a secure place; other

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.
important subject.

Good luck!

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

Associated Topics:
High School Projects

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search