The idea of cryptography is thousands of years old: Greek and Roman generals used cryptography to send coded messages to commanders who were in the field. Those early systems were based on two techniques: substitution and transposition.

Substitution is based on the principle of replacing each letter in the message you wish to encrypt with another one. The Caesar cipher, for example, substitutes the letter “a” with the letter “d,” the letter “b” with the letter “e,” and so on. Some substitution ciphers use the same substitution scheme for every letter in the message that is being encrypted; others use different schemes for different letters.

Transposition is based on scrambling the characters that are in the message. One transposition system involves writing a message into a table row-by-row, then reading it out column-by-column. Double transposition ciphers involve repeating this scrambling operation a second time.

In the early part of the 20th century, a variety of electromechanical devices were built in Europe and the United States for the purpose of encrypting messages sent by telegraph and radio. These systems relied principally on substitution, because there was no way to store a complete message using transposition techniques. Today, encryption algorithms running on high-speed digital computers use both substitution and transposition in combination, as well as other mathematical functions.

Modern cryptographic systems consist of two complementary processes:

Figure 10.1 illustrates how these two processes fit together.

Figure 10-1. A simple example of encryption and decryption

The goal of cryptography is to make it impossible to take a ciphertext and reproduce the original plaintext without the corresponding key and to raise the cost of guessing the key beyond what is practical. Many modern cryptographic systems now easily achieve this goal. Indeed, cryptographic algorithms that have no known flaws are readily available today.

Despite the fact that modern cryptography is fast, easy to use, and well-understood, many political barriers still limit the use of this technology.

Let’s see how cryptography works in practice. Here is a simple piece of plaintext:

SSL is a cryptographic protocol

This message can be encrypted with a popular encryption algorithm known as the Data Encryption Standard (DES). The DES is a symmetric algorithm, which means that it uses the same key for encryption as for decryption. In this case, we shall use the key nosmis:

% des -e < text > text.des
Enter key: nosmis
Enter key again: nosmis
%

The result of the encryption is this encrypted message:^[51]

% cat text.des
Ç`^@%[»FÇ«$TfiP∑|x¿Eûóõщß+ö˜•ÖaÜ″BÆuâw

When this message is decrypted with the key nosmis, the original message is produced:

% des -d < text.des > text.decrypt
Enter key: nosmis
Enter key again: nosmis
% cat text.decrypt
SSL is a cryptographic protocol
%

If you try to decrypt the encrypted message with a different key, such as gandalf, the result is garbage:^[52]

% des -d < text.des > text.decrypt
Enter key: gandalf
Enter key again: gandalf
Corrupted file or wrong key
% cat text.decrypt
±N%EÒRÖf`"H;0ªõO>˝„!_+í∞›

The only way to decrypt the encrypted message and get printable text is by knowing the secret key nosmis. If you don’t know the key, and you need the contents of the message, one approach is to try to decrypt the message with every possible key. This approach is called a key search attack or a brute force attack.

How easy is a key search attack? That depends on the length of the key. The message above was encrypted with the DES algorithm, which has a 56-bit key. Each bit in the 56-bit key can be a 1 or a 0. That means that there are 2⁵⁶, or roughly 72,057,594,037,900,000 different keys. On the other hand, the des command only gives you access to this keyspace when keys are specified as hexadecimal numbers. A typed key will typically only include the 96 printable characters, reducing the keyspace by 90 percent to 7,213,895,789,838,340 (96⁸).

Although DES has a lot of keys, it does not have an impossibly large number of keys. If you can try a billion keys a second and you can recognize the correct key when you find it (quite possible on some modern computers), you can try all possible keys in a little less than 834 days.

We’ll discuss these issues more thoroughly in the section Section 10.2.1 later in this chapter.

For years, cryptography has been primarily considered a military technology— despite the fact that nearly all of the strongest cryptosystems were invented by civilians.^[53]

Why the confusion? Nearly all of the historical examples of cryptography, from Greece and Rome, through France, Germany, and England, and on into the modern age, are stories of armies and spies that used cryptography to shield their messages transmitted by carrier. Examples that remain are either diplomatic, such as Mary, Queen of Scots, using cryptography to protect her messages (unsuccessfully, it turns out), or nefarious, such as a pirate using cryptography to record where he buried his ill-gotten gains.

There is also a tradition of nonmilitary use of cryptography that is many centuries old. There are records of people using cryptography to protect religious secrets, to hide secrets of science and industry, and to arrange clandestine romantic trysts. During World War I, the U.S. Postal Service opened all letters sent overseas. The majority of the letters that were decrypted by Herbert Yardley’s so-called American Black Chamber were not messages being sent from German spies operating within the U.S., but nonmilitary letters being exchanged between illicit lovers.^[54] They used cryptography for the same reasons that the spies did: to assure that, in the event that one of their messages was intercepted or opened by the wrong person, its content would remain secret.

In recent years, cryptography has increasingly become a tool of business and commerce. Ross Anderson, an English cryptographer, believes that in recent years civilian use of cryptography has eclipsed military use. After all, says Anderson, cryptography is used to scramble satellite television broadcasts, to safeguard currency stored on “smart cards,” and to protect financial information that is sent over electronic networks. These uses have all exploded in popularity in recent years.

Thus, like trucks, carbon fibers, and high-speed computers, cryptography is neither exclusively a military nor exclusively a civilian technology. It is instead a dual-use technology, with both civilian and military applications. For all of its users, cryptography is a way of buying certainty and reducing risk in an uncertain world.

There are two basic kinds of encryption algorithms in use today:

Symmetric key algorithms are the workhorses of modern cryptographic systems. They are generally much faster than public key algorithms. They are also somewhat easier to implement. Unfortunately, symmetric key algorithms have a problem that limits their use in the real world: for two parties to securely exchange information using a symmetric key algorithm, those parties must first securely exchange an encryption key.

Public key algorithms overcome this problem. People wishing to communicate create a public key and a secret key. The public key is published. If Sascha wants to send Wendy a confidential message, all he has to do is get a copy of Wendy’s public key (perhaps from her web page), use that key to encrypt the message, and then send it along. Nobody but Wendy can decrypt the message, because only Wendy possesses the matching secret key.

Public key cryptography is also used for creating digital signatures on data, such as electronic mail, to certify the data’s origin and integrity. In the case of digital signatures, the secret key is used to create the digital signature, and the public key is used to verify it. For example, Wendy could write a letter to Sascha and sign it with her digital key. When Sascha receives the letter, he can verify it with Wendy’s public key.

Public key algorithms have a significant problem of their own: they are incredibly slow. In practice, public key encryption and decryption runs between 10 and 100 times slower than the equivalent symmetric key encryption algorithm. For that reason, there is a third kind of system:

Finally, there is a new class of functions that have become popular in recent years and are used in conjunction with public key cryptography:

The following sections look at all of these classes of algorithms in detail.