In 1940, the outstanding British mathematician G.H. Hardy wrote a small book called A Mathematician’s Apology. In the book Hardy stated (boasted really), that, “No discovery of mine has made, or is likely to make, directly or indirectly, for good or ill, the least difference to the amenity of the world.” Thus Hardy was into “pure” mathematics and proud of it.

As such, Hardy would probably be a bit chagrined to learn that one of his main interests, prime numbers, now plays a vital role in international finance and in 500 billion dollar ecommerce system. Indeed, large parts of the World Wide Web could not function without some magic from this particular part of pure math.

The problem that prime numbers help solve is that of sending secret, confidential information, such as credit card numbers, over the internet. In a sense, this seems to be impossible to do, since the internet can never be assumed to be invulnerable to having messages read by someone on their way to the intended recipient. Suppose, for example, that you order something from amazon.com, and you type in a credit card number to pay for the order. Your computer can encrypt the data in some way before sending it out, but how can amazon.com’s computer unscramble the encrypted data, and yet an eavesdropper cannot unscramble it? After all, both amazon and the eavesdropper can see all the data that passes back and forth – if amazon’s computer can reconstruct the original message, so, it would seem, can the eavesdropper’s computer.

It turns out, of course, that there is a way to do the encryption in a way that only amazon can reconstruct the message, thanks to a brilliant invention called the RSA algorithm. The R, S, and A are the first letters of the inventors’ last names, and they were all at MIT in 1978 when they published the technique. In this post, I will sketch out how RSA works without actually describing the precise details.

To start, one must first understand (or at least accept) the following facts:

1. A plain text message can be encrypted using a key, together with a fairly simple computer program. The key is a very large number, in the neighborhood of a 100 digits, and the encrypted text will appear to be gibberish. For reasons that will be clear shortly, this key is called the Public Key.
2. The encrypted text has the property that one cannot feasibly decrypt such a message (i.e. turn it back into the original text), even if one knows the Public Key used to encrypt it. Instead, one requires another key, called the Private Key, to decrypt it.
3. The public and private keys are a matched set – if one has a Private Key, a simple, quick procedure can be used to compute the corresponding Public Key. However, it is impossible, practically speaking, to compute the Private Key by starting with the Public Key.
4. Anyone who needs to receive private messages (e.g. amazon) will have at the ready a Private Key, and its corresponding Public Key.

Now we can describe what happens when you are about to order your book using a credit card number.

1. The web browser knows that this web page will contain secure information, so it requests the Public Key from amazon. It uses this key to encrypt the data, and then transmits it to amazon.
2. The amazon computer can then decrypt the message, since it has the Private Key. Note, however, that the eavesdropper can’t decrypt it because he doesn’t have the Private Key, and there is no (known) feasible way to derive it from the Public Key.

It’s devilishly ingenious, and it is surprising that in 2,000 years or more of secret messages, no one thought of it sooner.

Now, what does the RSA algorithm have to do with prime numbers?

To begin answering that, consider the problem of factoring a large number – that is, determining its prime factors. The most obvious way to find factors is to successively try dividing prime numbers into it, until we find one that divides evenly into it. For example, if the number is 221, we try dividing by 2, 3, 5, 7, 11, 13 before finding that 13 divides into it evenly. Mathematicians have developed factoring algorithms that are somewhat faster than this brute force method, but very large numbers still cannot be dealt with. If the number we are given is a few hundred digits, then the age of the universe may be insufficient for a computer to find a factor.

This suggests a way for the Public Key, Private Key thing to work – if the Private Key is some very large prime number, we can then multiply it by another large prime to produce a Public key (a computer can do the multiplication in a trice). Then, with only the Public Key, no one can factor it to find the Private Key. Such numbers, by the way, are called semi-prime when they are the products of just two primes.

In basic algebra, we learn about functions and their inverse functions. For example, if y = f(x) = 3x – 7, then x = 1/3 (y + 7) is the inverse function. Given a value of the original function (y), this inverse will give us the x that will produce it in the original function. However, for the prime number function, it is essentially impossible to figure out an inverse for it. For that reason, it is sometimes called a trapdoor function.

Those wanting to know exactly how RSA works can read about it in a number of places, for example, here.

Share/Save

This entry was posted on Tuesday, June 9th, 2009 at 11:41 pm and is filed under Uncategorized. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.