A Primer on Public-key Encryption

From "Homeland Insecurity," by Charles C. Mann
More

Public-key encryption, as noted in the profile of cryptographer Bruce Schneier, is complicated in detail but simple in outline. The article below is an outline of the principles of the most common variant of public-key cryptography, which is known as RSA, after the initials of its three inventors; a mathematically detailed explanation of RSA by the programmer Brian Raiter, understandable to anyone willing to spend a little time with paper and pencil, is available here.

A few terms first: cryptology, the study of codes and ciphers, is the union of cryptography (codemaking) and cryptanalysis (codebreaking). To cryptologists, codes and ciphers are not the same thing. Codes are lists of prearranged substitutes for letters, words, or phrases—i.e. "meet at the theater" for "fly to Chicago." Ciphers employ mathematical procedures called algorithms to transform messages into unreadable jumbles. Most cryptographic algorithms use keys, which are mathematical values that plug into the algorithm. If the algorithm says to encipher a message by replacing each letter with its numerical equivalent (A = 1, B = 2, and so on) and then multiplying the results by some number X, X represents the key to the algorithm. If the key is 5, "attack," for example, turns into "5 100 100 5 15 55." With a key of 6, it becomes "6 120 120 6 18 66." (Nobody would actually use this cipher, though; all the resulting numbers are divisible by the key, which gives it away.) Cipher algorithms and cipher keys are like door locks and door keys. All the locks from a given company may work in the same way, but all the keys will be different.

Public-key cryptography is often said to be important because messages enciphered by it are "unbreakable"—that is, people can't randomly try out possible keys and break the cipher, even with powerful computers that try thousands of keys a second. (This assumes that the key has been properly chosen; even the best algorithm will be compromised if the key is something easily guessable.) In fact, though, many types of crypto algorithms are effectively unbreakable. What public-key does—its significant innovation—is to simplify drastically the problem of controlling the keys.

In non-public-key crypto systems, controlling the keys is a constant source of trouble. Cryptographic textbooks usually illustrate the difficulty by referring to three mythical people named Alice, Bob, and Eve. In these examples, Alice spends her days sending secret messages to Bob; Eve, as her name indicates, tries to eavesdrop on those messages by obtaining the key. Because Eve might succeed at any time, the key must be changed frequently. In practice this cannot be easily accomplished. When Alice sends a new key to Bob, she must ensure that Eve doesn't read the message and thus learn the new key. The obvious way to prevent eavesdropping is to use the old key (the key that Alice wants to replace) to encrypt the message containing the new key (the key that Alice wants Bob to employ in the future). But Alice can't do this if there is a chance that Eve knows the old key. Alice could rely on a special backup key that she uses only to encrypt new keys, but presumably this key, too, would need to be changed. Problems multiply when Alice wants to send messages to other people. Obviously, Alice shouldn't use the key she uses to encrypt messages to Bob to communicate with other people—she doesn't want one compromised key to reveal everything. But managing the keys for a large group is an administrative horror; a hundred-user network needs 4,950 separate keys, all of which need regular changing. In the 1980s, Schneier says, U.S. Navy ships had to store so many keys to communicate with other vessels that the paper records were loaded aboard with forklifts.

Public-key encryption makes key-management much easier. It was invented in 1976 by two Stanford mathematicians, Whitfield Diffie and Martin Hellman. Their discovery can be phrased simply: enciphering schemes should be asymmetric. For thousands of years all ciphers were symmetric—the key for encrypting a message was identical to the key for decrypting it, but used, so to speak, in reverse. To change "5 100 100 5 15 55" or "6 120 120 6 18 66" back into "attack," for instance, one simply reverses the encryption by dividing the numbers with the key, instead of multiplying them, and then replaces the numbers with their equivalent letters. Thus sender and receiver must both have the key, and must both keep it secret. The symmetry, Diffie and Hellman realized, is the origin of the key-management problem. The solution is to have an encrypting key that is different from the decrypting key—one key to encipher a message, and another, different key to decipher it. With an asymmetric cipher, Alice could send encrypted messages to Bob without providing him with a secret key. In fact, Alice could send him a secret message even if she had never before communicated with him in any way.

"If this sounds ridiculous, it should," Schneier wrote in Secrets and Lies (2001). "It sounds impossible. If you were to survey the world's cryptographers in 1975, they would all have told you it was impossible." One year later, Diffie and Hellman showed that it was possible, after all. (Later the British Secret Service revealed that it had invented these techniques before Diffie and Hellman, but kept them secret—and apparently did nothing with them.)

To be precise, Diffie and Hellman demonstrated only that public-key encryption was possible in theory. Another year passed before three MIT mathematicians—Ronald L. Rivest, Adi Shamir, and Leonard M. Adleman—figured out a way to do it in the real world. At the base of the Rivest-Shamir-Adleman, or RSA, encryption scheme is the mathematical task of factoring. Factoring a number means identifying the prime numbers which, when multiplied together, produce that number. Thus 126,356 can be factored into 2 x 2 x 31 x 1,019, where 2, 31, and 1,019 are all prime. (A given number has only one set of prime factors.) Surprisingly, mathematicians regard factoring numbers—part of the elementary-school curriculum—as a fantastically difficult task. Despite the efforts of such luminaries as Fermat, Gauss, and Fibonacci, nobody has ever discovered a consistent, usable method for factoring large numbers. Instead, mathematicians try potential factors by invoking complex rules of thumb, looking for numbers that divide evenly. For big numbers the process is horribly time-consuming, even with fast computers. The largest number yet factored is 155 digits long. It took 292 computers, most of them fast workstations, more than seven months.

Jump to comments
Presented by

Charles C. Mann, an Atlantic contributing editor, has been writing for the magazine since 1984. His recent books include 1491, based on his March 2002 cover story, and 1493.

Get Today's Top Stories in Your Inbox (preview)

CrossFit Versus Yoga: Choose a Side

How a workout becomes a social identity


Join the Discussion

After you comment, click Post. If you’re not already logged in you will be asked to log in or register. blog comments powered by Disqus

Video

CrossFit Versus Yoga: Choose a Side

How a workout becomes a social identity

Video

Is Technology Making Us Better Storytellers?

The minds behind House of Cards and The Moth weigh in.

Video

A Short Film That Skewers Hollywood

A studio executive concocts an animated blockbuster. Who cares about the story?

Video

In Online Dating, Everyone's a Little Bit Racist

The co-founder of OKCupid shares findings from his analysis of millions of users' data.

Video

What Is a Sandwich?

We're overthinking sandwiches, so you don't have to.

Video

Let's Talk About Not Smoking

Why does smoking maintain its allure? James Hamblin seeks the wisdom of a cool person.

Writers

Up
Down

More in Technology

More back issues, Sept 1995 to present.

Just In