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.

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.

Self Check 6

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 $a$ by a positive integer $n$, there are unique integers $q$ and $r$ such that $a=nq+r$, where $r$ is nonnegative and less than $n$. The number $q$ is called the quotient and $r$ is called the remainder. For any positive integers $a$ and $n$, we define $a\text{ mod }n$ (read “$a$ modulo $n$” or just “$a\text{ mod }n$") to be the remainder when $a$ is divided by $n$. For negative integers $a$, we can find $a\text{ mod }n$ by adding exactly enough multiples of $n$ to $a$ so that the sum is nonnegative (this works because modulo $n$, $n=0$). Thus, $-84\text{ mod }26=20$ because $-84+4\cdot 26=-84+104=20$.

Arithmetic involving $\text{ mod }n$ 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 $25=2\cdot 12+1$ so that $25\text{ mod }12=1$, and you added one month to September.

Modeling the Genetic Code 17.5

The way that genetic material is composed can be conveniently modeled using modulo 4 arithmetic. A DNA molecule is made up of two long strands in the form of a double helix. Each strand is made up of strings of the four nitrogen bases adenine (A), thymine (T), guanine (G), and cytosine (C). Each base on one strand binds to a complementary base on the other strand. Adenine always binds to thymine, and guanine always binds to cytosine. To model this situation, we identify A with 0, T with 2, G with 1, and C with 3. Thus, the DNA segment ACGTAACAGGA and its complementary segment TGCATTGTCCT are identified by 03120030110 and 21302212332.

Using modulo 4 arithmetic, $0+2=2,2+2=0,1+2=3$, and $3+2=1$, we see that adding 2 to any of the integers 0, 1, 2, or 3 interchanges 0 and 2 and 1 and 3. So, for any DNA segment $a_1{a}_2\mathrm{\dots }{a}_n$ represented by strings of 0s, 1s, 2s, and 3s, we see that its complementary segment is represented by $a_1{a}_2\mathrm{\dots }{a}_n\mathrm{+}22...2$, where we add the integers in each component using modulo 4. In particular, $03120030110+22222222222=21302212332$.

Source: Information from Discrete Mathematics by S. Washburn, T. Marlow, and C. Ryan, Addison-Wesley, 1999.

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 $23=3\cdot 7+2$ (that is, $23\text{ mod }7=2$), so you added 2 days to Wednesday instead of counting off 23 days. Because $51=2\cdot 24+3$, if it is now 1 P.M., in 51 hours, it will be 4 P.M. ($51\text{ mod }24=3$). If you travel east 390 degrees, you end up 30 degrees east of where you began ($390\text{ mod }360=30$). 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 $\text{ mod }2$. 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 $A$ is in position 0, $B$ is in position 1, $C$ is in position 2, and so on. Then the Caesar cipher replaces the letter in position $i$ with the letter in position $(i+3)\text{ mod }26$. This formula expresses the fact that the Caesar cipher shifts each letter from $A$ through $W$ three positions to the right, while $X$, $Y$, and $Z$ are replaced with $A$, $B$, and $C$, respectively. (Think of $X$, $Y$, and $Z$ 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.

To begin, we assign the 26 letters the numbers 0 through 25, in order, and select any odd integer $k$ between 3 and 25 except 13. (For the method to work, $k$ and 26 must have no prime divisors in common.) Then, in the message, a letter with numerical value $i$ is replaced with the letter with numerical value $ki$ modulo 26. For example, if $k$ is 5, then $D$ is replaced with $P$ because $D$ has value 3 and $5\times 3=15$, which is assigned to $P$. When $ki$ exceeds 26, we use modulo 26 arithmetic to determine the replacement for the letter. Thus, $J$ is replaced by $T$ because $J$ has the value 9 and $5\times 9=45$ and $45\text{ mod }26=19$ and $T$ has value 19. The value of $k$ 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 $5\times 21=105$ and $105\text{ mod }26=1$. As a consequence, for any integer $x$, we have $(x\times 5\times 21)\text{ mod }26$ equals $(x\times 1)\text{ mod }26=x\text{ mod }26$. Thus, multiplying an integer $x$ by 5 and then the result by 21 gets us back to $x$ when we use modulo 26. In general, if a number $k$ is used to encrypt a message modulo 26, the value $j$ used to decrypt the message has to be chosen so that $kj\text{ mod }26=1$. Given a particular value for $k$, we can find the corresponding $j$ by trial and error. Table 17.4 shows the values corresponding to each choice of $k$.

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 $x$ with the letter corresponding to the integer $(kx+s)\text{ mod }26$, where $k$ is any allowable decimation key and $s$ is the shift we want. For example, choosing $k=11$ and $s=6$, the letter $D$, which corresponds to 3, is replaced by $M$, which corresponds to 13, because $(11\cdot 3+6)\text{ mod }26=13$. This method is called a linear cipher.

To decrypt a message that has been created using the linear cipher formula $(kx+s)\text{ mod }26$, we must undo shifting by $s$ by shifting by $-s$, as well as undo the step of multiplying by the encryption value $k$ by multiplying by the decryption value corresponding to $k$ given in Table 17.4. In our example of encoding the letter with the numerical value $x$ with the formula $(11x+6)\text{ mod }26$, we can determine the starting value of $x$ that results in 13 by solving the equation $(11x+6)\text{ mod }26=13\text{ mod }13$: We subtract 6 from both sides to get $11x\text{ mod }26=7\text{ mod }26$, which reverses the shift of 6; then we multiply by 19, which we see from Table 17.4 reverses multiplying by 11, to get $19\cdot 11x\text{ mod }26=19\cdot 7\text{ mod }26$. Because $19\cdot 11\text{ mod }26=1$ and $19\cdot 7\text{ mod }26=3$, this simplifies to $x=3$, which corresponds to the letter $D$. In cases where working backward results in a negative value after the reverse shift such as $19\cdot (-5)\text{ mod }26$, Google still gives the correct answer.

Undoing a message letter $x$ encrypted by multiplying by $k$ and shifting by $s$ is tantamount to using the formula $k\text{'}(x-s)$, where $k\text{'}$ is the decryption value for $k$ given in Table 17.4 (notice that we undo the two steps in reverse order).

Self Check 7

Self Check 8

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 $n$ greater than 1, a permutation of the integers $1,2,\dots ,n$ is a reordering of those integers. To specify a reordering, we list the integers $1,2,\dots ,n$ in the top row of a 2-by-$n$ array and the reordered integers in the bottom row. For $n=3$, one possible permutation is

To use the permutation $\alpha$ 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 $\alpha$ of the integers $1,2,\dots ,n$, we use the permutation ${\alpha }^{-1}$ (called $\alpha$inverse) that reverses the effect $\alpha$ of by reading $\alpha$ from bottom to top. That is, we create the 2-by-$n$ permutation array as follows. The top row of ${\alpha }^{-1}$ is $1,2,\dots ,n$. The first entry in the bottom row of ${\alpha }^{-1}$ is the integer in the top row of $\alpha$ that is above 1; the second entry in the bottom row of ${\alpha }^{-1}$ is the integer in the top row of $\alpha$ above 2; and continuing in this way, the nth entry of the bottom row of ${\alpha }^{-1}$ is the integer in the top row of $\alpha$ above $n$. For $\alpha =\left[\begin{array}{lll}1\hfill & 2\hfill & 3\hfill \\ 3\hfill & 1\hfill & 2\hfill \end{array}\right]$, We have ${\alpha }^{-1}=\left[\begin{array}{ccc}1& 2& 3\\ 2& 3& 1\end{array}\right]$. Applying ${\alpha }^{-1}$ to the ciphertext

yields the plaintext

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

In cases of messages encrypted with a permutation of $1,2,\dots ,n$ where there are not enough letters to fill the last block, we add extra nonsense letters like $X$, $Q$, and $Z$ as filler. Thus, when the message is ATTACK AT DAWN and $n$ 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

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.

Self Check 9

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 $Q$ and the corresponding letter from the keyword is $M$, then the letter $C$ at the intersection of the row that begins with $M$ and the column that begins with $Q$ is the encrypted letter for $Q$.

Enigma Machines 17.6

Enigma machines were cipher devices used by the Germans in World War II (1939-1945). An Enigma machine had three to five wheels that would scramble the letters of a message in a way similar to the Vigenère method. The machines were easy to use and offered a high degree of security when used properly. Although messages encoded with Enigma machines were difficult to decipher, operator negligence and the capture by the Allied forces of a number of Enigma machines and the tables of wheel settings allowed Polish and British cryptologists to break the code.

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.

Mavis Batey 17.7

Mavis Batey was born Mavis Lever in south London on May 5, 1921. As a linguistics student at a London college during the early days of World War II, she was recruited by the British government to do intelligence work. One of her first assignments was to read the personal ads in the Times of London in search of secret German messages. Following that, she joined a team of code breakers at Bletchley Park, a Victorian estate north of London. Her team’s efforts helped the Allies defeat the Italian navy in 1941. Their cracking of the Enigma codes employed by the German military intelligence service assisted the Allied forces’ 1944 invasion of France to drive out the Germans. Britain’s wartime prime minister, Winston Churchill, called the Bletchley Park code breakers “the geese that laid the golden eggs but never cackled.”

Batey was the model for the code breaker played by Kate Winslet in the 2001 film Enigma. She died in 2013 at age 92. Newspapers in the United States and the United Kingdom carried lengthy obituaries about her.

Alan Turing 17.8

On Time magazine’s list of the 100 most influential people of the 20th century was Alan Turing, a British mathematician born in London in 1912. While a student at Cambridge, Turing imagined a machine that could execute logical processes. The device in his mind-experiment quickly acquired the name “Turing machine.” At the time, no one knew that Turing’s idea would provide a blueprint for what would eventually become the electronic digital computer. Now we know that everyone who opens a spreadsheet or a word-processing program is using an incarnation of a Turing machine.

After graduating from Cambridge, Turing became a crucial member of a team of cryptologists working for the British government who successfully broke the Enigma codes (see Spotlight 17.6 on page 724).

Turing’s life took a tragic turn in 1952 when he admitted that he had engaged in homosexual acts in his home, a felony in Britain at that time. As punishment, he was chemically castrated and subjected to estrogen treatments. Made despondent by this treatment, he committed suicide two years later at the age of 41 by eating an apple laced with cyanide.

Today, Turing is widely honored for his fundamental contributions to computer science and his role in the defeat of Germany in World War II. Many rooms, lecture halls, and buildings at universities around the world have been named in honor of Turing. The annual award for contributions to the computing community, which is widely considered to be equivalent to a Nobel Prize, is called the “Turing Award.” In December 2013, Queen Elizabeth II granted Turing a pardon and issued a statement saying that Turing’s treatment was unjust: “Turing was an exceptional man with a brilliant mind who deserves to be remembered and recognized for his fantastic contribution to the war effort and his legacy to science.”

The 2014 film Imitation Game, loosely based on Turing’s life, starred Benedict Cumberbatch as Turing and Keira Knightley as a member of the code-breaking team; it was nominated for eight Academy Awards.

Information from Time, Vol. 153, Issue 12 (March 29, 1999), p. 147.

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 $a_1{a}_2\mathrm{\dots }{a}_n$ and $b_1{b}_2\mathrm{\dots }{b}_n$ as follows:

where $c_i=0$ if $a_i=b_i$ and $c_i=1$ if $a_i\ne b_i$. Equivalently, $c_i=(a_i+b_i)\text{ mod }2$. (Add $a_i$ and $b_i$ in the ordinary way, but replace 2 by 0.)

Self Check 10

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 $s=10101100$ to Amazon (actual credit card numbers have very long strings), and Amazon sends your computer the key $k=00111101$. Your computer returns the string $s+k=10101100+00111101=10010001$ to Amazon, and Amazon adds $k$ to this string to get $10010001+00111101=10101100$, which is the string representing your credit card number. If someone intercepts the number $s+k=10010001$ during transmission, it is of no value without knowing $k$. This method works because of the property of binary addition that $a_1{a}_2\cdots a_n+b_1{b}_2\cdots b_n=00\dots 0$ if and only if the two strings are identical. Thus, $(s+k)+k=s(k+k)=s+00\cdots 0=s$. 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.

Smart Cards 17.9