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/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.