A Primer on Public-key Encryption

Source: The Atlantic

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.