As mentioned above, public-key cryptosystems rely on one magic ingredient: the one-way function. At the time that Diffie and Hellman wrote their first paper they did not have any particular function in mind. Shortly thereafter Ralph Merkle, a student of Hellman’s, proposed one, which eventually proved to be unsatisfactory because it was not as hard to reverse as it initially appeared. It was left to another troika of mathematicians to invent a one-way function that was both simple and resistant to attack, and their invention remains the most popular public-key system to this day.

The RSA cryptosystem, devised in 1977 by Ronald Rivest, Adi Shamir, and Leonard Adleman, rests on the idea that multiplying numbers is easy, but finding their divisors is hard. To make things as hard as possible for the computer, you should make sure your initial numbers are prime numbers. These are the numbers, such as 2, 3, 5, 7, and so forth that have no divisors aside from themselves and 1. Any desktop computer can multiply two 150-digit numbers together and print out the 300-digit result in a fraction of a second. But if you feed that 300-digit number to the biggest and fastest computer in the world, it will be unable to discover the two 150-digit numbers that you used to create it.

Thus, the simple act of multiplying two prime numbers together has all the hallmarks of a one-way function: It is easy to do, and hard to undo. But how do you tranform it into a public-key cryptosystem? The answer is far from obvious, and a great tribute to the ingenuity of Rivest, Shamir, and Adleman.

Their system exploits a subtle difference between prime numbers and composite (non-prime) numbers that was first noticed around 1640 by the French mathematician Pierre de Fermat. Suppose you pick any number, n, and any other number a that is smaller than n. (As we shall see later, in the RSA system, n is a public key and a is the plaintext; but for Fermat they were just numbers.) Now multiply a by itself, over and over. To keep the numbers from getting too big, at each step divide by n and take the remainder. (This is called “reduction modulo n.”) Figure 2 shows what happens with n = 13 and a = 2: The sequence starts out 1, 2, 4, 8, 3 (the sequence always starts with 1 and is then multiplied by a repeatedly; here, the sequence goes as 1, 1 × 2 = 2, 2 × 2 = 4, 4 × 2 = 8, 8 × 2 = 16—which reduces to 3 modulo 13—and so on), and after 13 steps, it comes back to 2 again.

According to Fermat, this is no accident. When n is prime, the repeated-multiplication trick always cycles back to its starting point after n steps. (Mathematicians say this as follows: a^n is congruent to a modulo n. The symbol a^n refers to a multiplied by itself n times, or a to the n-th power.) But when n is not prime, the number of steps needed to cycle around is usually not equal to n. Predicting just how many steps it will take is hard: To do it, you need to know what the divisors of n are. (Remember that whenever n is not prime, it will have divisors.)

Until the 1970s, number theorists had never suspected that this repeated-multiplication trick (called “Fermat’s little theorem,” to distinguish it from the more famous “Fermat’s last theorem”) could be used for cryptography. Rivest, Shamir, and Adleman’s unprecedented insight was this: If the number a is thought of as a message, then multiplying it repeatedly, say e times by itself (i.e., raising it to the e-th power) and then reducing modulo n is a way of scrambling the message. To unscramble the ciphertext, you don’t have to reverse the process: Instead, you just keep on multiplying a^e by itself! After some additional number of steps (say, d steps), the message a will magically pop out again.

Figure 3 shows in detail how Rivest, Shamir, and Adleman incorporated this idea into a cryptosystem. Remember that, in public-key cryptography, message recipients are responsible for generating their own public and private keys. First, Bob chooses two very large prime numbers p and q, say 150 digits long each, for his private key. Aside from the restriction that they are prime, they can be chosen completely arbitrarily. His public key consists of n, which is p times q (and is therefore not prime), and e, the encoding key, which must satisfy a few mild conditions relating to the factors of n. These conditions do not pose any difficulty for Bob, because he knows p and q. Finally he computes the unique decoding key d that will work in the manner described in the last paragraph. That is, when any number a is multiplied by itself e times modulo n, and the result (a^e) is multiplied by itself d more times modulo n, the original number a results. This number d also becomes part of the private key, and can only be computed by someone who is privy to the secret values of p and q. These calculations are shown in detail in figure 3.

To send Bob the message “HELP” using Bob’s public key, Alice first converts the letters into numbers using a scheme such as A = 1, B = 2, etc. (Punctuation and spaces can also be converted, for example by using the standard ASCII codes that are used by computer word processors. This is not part of the RSA cryptosystem per se.) If necessary, she splits the complete text of the converted message into chunks that are no larger than n. Then she multiplies each chunk by itself e times and reduces it modulo n. The resulting number is the ciphertext. To recover the original message, Bob multiplies the ciphertext by itself d more times and reduces it modulo n.

Now consider the predicament of an eavesdropper whom we will call Eve. If n were a prime number, Fermat’s little theorem would tell her exactly how many multiplications would unscramble Alice’s message. But because n is not prime, she needs to know its divisors to figure that out (since the private key d is derived from the divisors of n as shown in figure 3)—and that would force her to reverse a one-way function. Nor can she undo Alice’s e multiplications, because undoing multiplications, even modulo n, is difficult. She can’t even use trial and error, multiplying the ciphertext by itself until a coherent message pops out, because in practice d is too large for that to work.

Figure 4 shows how modular computation works. In this example, Bob knows that d = 64 and 2^64 will yield the message. He can take a short cut while Eve has a much more laborious job. By repeated squaring, Bob finishes the calculation after only 6 multiplications as shown in the figure. But Eve, who has to check each power of 2 to see if she gets a message or only gibberish, would need to do one multiplication at a time until she gets to 2^64 and will hence take 64 steps. And Bob’s advantage over Eve grows bigger and bigger as d gets larger. So Eve is stuck, and Alice’s secret is safe.

The RSA technique is vulnerable when the sender encrypts precisely the same message (e.g., "SELL") more than once, resulting in the same ciphertext. An eavesdropper could note this and, perhaps, guess the message content even without figuring out the key. Thus, in practice, the message is usually scrambled first by a fast symmetric-key cipher as described in the example of secure websites. This will produce a different ciphertext each time, because the symmetric key will change.