Thus far, we have discussed ways in which data can be encoded to detect errors or correct errors in transmission. In many situations, there is also a desire for security against unauthorized interpretation of coded data (that is, a desire for secrecy). The process of disguising data is called encryption.

Historically, encryption was used primarily for military and diplomatic transmissions (see Spotlights 17.6 through 17.8, starting on page 724). Today, encryption is essential for securing electronic transactions of all kinds. Cryptography is what allows you to have a website safely receive your credit card number. Cryptographic schemes prevent hackers from charging calls to your cell phone. Cryptography is also used for authenticating electronic transactions. In 1998, history was made when President Bill Clinton and Ireland’s Prime Minister Bertie Ahern used digital signatures to sign an intergovernmental document. Each leader had a unique signing code and a digital certificate that served as a “digital ID,” thereby ensuring that the document truly was approved by them. Although modern encryption schemes are extremely complex, we will illustrate the fundamental concepts involved with a few simple examples.

Among the first known cryptosystems is the Caesar cipher, used by Julius Caesar to send messages to his troops. To encrypt a message with the method employed by Caesar, we use the following table to replace each letter in the top row with the letter below it:

For example, the message ATTACK AT DAWN is encrypted as DWWDFN DW GDZQ.

715

To decrypt the message, replace each letter with the letter above it in the table. Obviously, it would not require much effort for someone to “crack” this code, but it might be good enough to use on your friends who are not mathematically inclined.

To describe more sophisticated schemes for transmitting messages secretly, it is convenient to introduce a special kind of arithmetic used in cryptography. Recall that if we divide a positive integer by a positive integer , there are unique integers and such that , where is nonnegative and less than . The number is called the quotient and is called the remainder. For any positive integers and , we define (read “ modulo ” or just “") to be the remainder when is divided by . For negative integers , we can find by adding exactly enough multiples of to so that the sum is nonnegative (this works because modulo , ). Thus, because .

Arithmetic involving is called modular arithmetic. Although this arithmetic may appear unfamiliar, you often unconsciously use it. For example, if it is now September, what month will it be 25 months from now? Of course, you answer “October,” but the interesting fact is that you didn’t arrive at the answer by starting with September and counting off 25 months. Instead, without even thinking about it, you simply observed that so that , and you added one month to September.

716

Similarly, if it is now Wednesday, you know that in 23 days, it will be Friday. This time, you arrived at your answer by noting that (that is, ), so you added 2 days to Wednesday instead of counting off 23 days. Because , if it is now 1 P.M., in 51 hours, it will be 4 P.M. (). If you travel east 390 degrees, you end up 30 degrees east of where you began (). Applications of modular arithmetic include the check-digit schemes described in Chapter 16, where arithmetic mod 7, 9, 10, and 11 were used. The parity-check sums (discussed in Section 17.2) use addition . An application of modular arithmetic to genetics is described in Spotlight 17.5.

With modular arithmetic, we can describe the Caesar cipher easily as follows. Begin by saying that the letter is in position 0, is in position 1, is in position 2, and so on. Then the Caesar cipher replaces the letter in position with the letter in position . This formula expresses the fact that the Caesar cipher shifts each letter from through three positions to the right, while , , and are replaced with , , and , respectively. (Think of , , and as “wrapping” around to the beginning of the alphabet.) It is customary to use the term Caesar cipher for any encryption scheme that shifts each letter a fixed number of positions. When the shift is anything other than three positions, we will specify the amount of the shift.

Decimation Cipher

Rather than encrypting a message by adding a fixed number to the position of every letter and using modular arithmetic, as is done in the Caesar cipher, another simple way to encrypt a message is to multiply each position by a fixed number and use modular arithmetic. This method of encryption is called the decimation cipher.

717

To begin, we assign the 26 letters the numbers 0 through 25, in order, and select any odd integer between 3 and 25 except 13. (For the method to work, and 26 must have no prime divisors in common.) Then, in the message, a letter with numerical value is replaced with the letter with numerical value modulo 26. For example, if is 5, then is replaced with because has value 3 and , which is assigned to . When exceeds 26, we use modulo 26 arithmetic to determine the replacement for the letter. Thus, is replaced by because has the value 9 and and and has value 19. The value of is called the key.

To decode an encrypted message, we use the same method except that we multiply the numerical value for each encrypted letter by 21. The number 21 is used to decrypt the message because it has the property that and . As a consequence, for any integer , we have equals . Thus, multiplying an integer by 5 and then the result by 21 gets us back to when we use modulo 26. In general, if a number is used to encrypt a message modulo 26, the value used to decrypt the message has to be chosen so that . Given a particular value for , we can find the corresponding by trial and error. Table 17.4 shows the values corresponding to each choice of .

718

Linear Cipher

We can combine the methods used in the Caesar cipher and the decimation cipher easily by replacing the letter represented by the integer with the letter corresponding to the integer , where is any allowable decimation key and is the shift we want. For example, choosing and , the letter , which corresponds to 3, is replaced by , which corresponds to 13, because . This method is called a linear cipher.

To decrypt a message that has been created using the linear cipher formula , we must undo shifting by by shifting by , as well as undo the step of multiplying by the encryption value by multiplying by the decryption value corresponding to given in Table 17.4. In our example of encoding the letter with the numerical value with the formula , we can determine the starting value of that results in 13 by solving the equation : We subtract 6 from both sides to get , which reverses the shift of 6; then we multiply by 19, which we see from Table 17.4 reverses multiplying by 11, to get . Because and , this simplifies to , which corresponds to the letter . In cases where working backward results in a negative value after the reverse shift such as , Google still gives the correct answer.

Undoing a message letter encrypted by multiplying by and shifting by is tantamount to using the formula , where is the decryption value for given in Table 17.4 (notice that we undo the two steps in reverse order).

719

In most cases, the encryption algorithm requires that a message be changed to a particular format that is still readable. Such messages are called plaintext. An encrypted version of a message is called ciphertext. Our next cipher provides an example of a plaintext format.

Permutation Cipher

Another easy-to-use cipher is the permutation cipher. For an integer greater than 1, a permutation of the integers is a reordering of those integers. To specify a reordering, we list the integers in the top row of a 2-by- array and the reordered integers in the bottom row. For , one possible permutation is

To use the permutation to encrypt the message ATTACK AT DAWN, we first break up the message into blocks of three letters each, ignoring the spaces between the words to obtain the plaintext ATT ACK ATD AWN. (This has the added advantage of disguising the lengths of each word, which makes breaking the code more difficult.) We then use the permutation to reorder the three letters in each block in the same way we reordered the integers 1, 2, and 3. That is, the first letter is put in the third position, the second letter is put in the first position, and the third letter is put in the second position. Doing this for each block we have TTA CKA TDA WNA. Messages encrypted with permutations are popularly called anagrams.

To decrypt a message encrypted by any permutation of the integers , we use the permutation (called inverse) that reverses the effect of by reading from bottom to top. That is, we create the 2-by- permutation array as follows. The top row of is . The first entry in the bottom row of is the integer in the top row of that is above 1; the second entry in the bottom row of is the integer in the top row of above 2; and continuing in this way, the nth entry of the bottom row of is the integer in the top row of above . For , We have . Applying to the ciphertext

yields the plaintext

Notice that when moves a letter in a block to a new position, moves that letter back to its original position. In effect, “undoes” . Of course, the recipient of the encrypted message must disentangle the blocks to figure out the words involved by seeing which possibilities make sense.

720

In cases of messages encrypted with a permutation of where there are not enough letters to fill the last block, we add extra nonsense letters like , , and as filler. Thus, when the message is ATTACK AT DAWN and is 5, the last block could be WNXQZ or WNQXX. The recipient of the message will recognize the nonsense letters as padding needed to complete the last block.

Although linear ciphers and permutation ciphers are simple to use, they have the serious flaw of preserving the frequency of the encrypted letters. That is, the frequency of each letter in the plaintext is the same as the frequency of its replacement in the ciphertext. When letter frequency is preserved, it is easy to deduce the method of encryption for long messages.

The next two ciphers we discuss are the type that encode the same letter in more than one way. For these ciphers, letters that occur frequently in the message may not correspond to letters that occur frequently in the ciphertext and vice versa.

Playfair Cipher

The Playfair cipher was invented in 1854 by the British scientist Charles Wheatstone; it was then popularized by Baron Lyon Playfair. The cipher was used in the Boer War during 1899–1902 and World War II (1939–1945). The Playfair cipher uses a 5-by-5 matrix and three rules for converting plaintext to ciphertext. Since the matrix accommodates only 25 letters, the letter Q is omitted in all plaintext and keywords (some authors retain Qs but replace all occurrences of the letter J in a plaintext or keyword with I). To encode a message, the sender groups successive letters into pairs. Because the method requires that each pair of letters be distinct letters, in situations where the same letter would occur twice, the letter X is inserted between them [if the duplicate pair is XX, a Z is inserted between them—the X (or Z) is ignored after the ciphertext has been decoded]. If this process results in a plaintext with an odd number of letters, an X is added at the end (or a Z if the last letter is X). Thus, the message CALL IT QUITS yields the plaintext pairs CA LX LI TU IT SX. To create the cipher, the sender selects a keyword and inserts it in the matrix starting in the first row and continuing as necessary with no letter used more than once. The keyword MATHEMATICS would yield the matrix entries

721

The remaining slots of the matrix are filled with the unused letters in the alphabet in their usual order. In our case, the cipher matrix is

The rules for transforming each pair of plaintext letters to ciphertext letters are as follows.

Playfair Encryption Rules

Note that with the Playfair cipher, the same letter in plaintext can be encoded more than one way in ciphertext (in Example 17, the first L becomes J and the second L becomes F). This means that letters appearing with high frequency in English may not encode to letters with high frequency—which makes breaking the cipher more difficult. Of course, to decrypt a ciphertext we must reverse the encryption steps as demonstrated in the next example.

722

Vigenère Cipher

Modular arithmetic also provides the basis for a more sophisticated cryptosystem called the Vigenère cipher. For this method, we first select a keyword, which can be any word. The letters of the keyword are then used to determine the amount of shifting for each letter of our message. As before, we say A is in position 0, B is in position 1, and so on.

The Vigenère square in Table 17.6 provides a quick way to use the Vigenère cipher to encrypt messages with any keyword. Use the left column for each letter of the keyword and the top row for the corresponding letter of the message to be encrypted. The letter at the intersection of that row and column is the shifted letter. For example, if the message letter is and the corresponding letter from the keyword is , then the letter at the intersection of the row that begins with and the column that begins with is the encrypted letter for .

724

Jefferson Wheel Cipher

In 1795 Thomas Jefferson, who became the third president of the United States in 1801, invented an encryption device known as the Jefferson wheel cipher. Employing the idea underlying the Vigenère square, the Jefferson cipher consists of a set of 26 disks with a hole in the center, each with the 26 letters of the alphabet arranged around the edge (see the figure below), scrambled in a random way from the approximately 40,329,146,000,000,000,000,000,000 choices. The disks numbered from 1 to 26 are mounted on the axle in any order desired. Rather than using a keyword, the order in which the disks are arranged on the axle is the cipher key. Both sender and receiver must arrange the disks in the same order. The sender rotates each disk up and down to spell out the desired message on one row and then selects any row to determine the approprite substitutions. To decrypt the coded message, the receiver rotates the disks so that they spell out the encrypted message on one row and then looks for another row that make sense. In the very unlikely case of two sensible messages, the receiver can request the message to be re-encrypted.

The same system was independently invented in 1891 by Etienne Bazeries, who used 20 disks. It was used by the United States Army from 1923 until 1942.

725

726

Encrypting Credit Card Data on the Web

Suppose that you want to purchase a compact disc from Amazon.com. Should you be concerned that a hacker will intercept your credit card number during the transaction? As you might expect, your credit card number is sent to Amazon in encrypted form to protect the data.

To describe one way that this encryption can be done, we need to perform addition of binary strings. We add two binary strings and as follows:

where if and if . Equivalently, . (Add and in the ordinary way, but replace 2 by 0.)

727

We can now explain one way to send credit card numbers over the Web securely. When you place an order with Amazon, the company sends your computer a randomly generated string of 0s and 1s called a key. This key has the same length as the binary string corresponding to your credit card number, and the two strings are added (think of this process as “locking” the data). The resulting sum is then transmitted to Amazon. Amazon in turn adds the same key to the received string, which then produces the original string corresponding to your credit card number. (Adding the key a second time “unlocks” the data.)

To illustrate the idea, say you want to send an eight-digit binary string such as to Amazon (actual credit card numbers have very long strings), and Amazon sends your computer the key . Your computer returns the string to Amazon, and Amazon adds to this string to get , which is the string representing your credit card number. If someone intercepts the number during transmission, it is of no value without knowing . This method works because of the property of binary addition that if and only if the two strings are identical. Thus, . The method is secure because the key sent by Amazon is randomly generated and used only one time.

You can tell when you are using an encryption scheme on a web transaction by looking to see if the web address begins with “https” rather than the customary “http.” You will also see a small padlock in the status bar at the bottom of the browser window.

Even with sophisticated encryption schemes and security precautions, however, computer system breaches are still common. See Spotlight 17.9 for a highly publicized instance.