The Mathematics of Secrets: Cryptography from Caesar Ciphers to Digital

Ciphers and Computers • 115 by the symbol ⊕. For example, the digits 10010, which ordinarily rep- resent 18, and the digits 01110, which ordinarily represent 14, would be added: 10010 ⊕01110 11100 This gives 11100, which ordinarily represents 28—not the usual sum of 18 and 14. The big difference between this and the tabula recta polyal- phabetic substitution ciphers we looked at earlier is that the addition is modulo 2 instead of modulo 26. Some of the systems that AT&T was using were equipped to auto- matically send messages using a paper tape, which could be punched with holes in 5 columns—a hole indicated a 1 in the Baudot code and no hole indicated a 0. Vernam configured the teletypewriter to add (mod- ulo 2) each digit represented by the plaintext tape to the corresponding digit from a second tape punched with key characters. The resulting ciphertext is sent over the telegraph lines as usual. At the other end, Bob feeds an identical copy of the tape through the same circuitry. Since 1 ≡ −1 modulo 2, subtraction modulo 2 is the same as addition. Thus the same operation at Bob’s end subtracts the key, and the teletypewriter can print the plaintext. Vernam’s invention and its further developments became extremely important in modern cryptography; we will see these ideas again in Sections 4.3 and 5.2. In general, polyliteral ciphers trade off the advantage of fewer distinct symbols for the disadvantage of longer messages. In some situ- ations, such as holding torches, digital computers, steganography, and telegraphs, the utility of this trade-off is obvious. In other situations it may not be as clear why one would be willing to put up with the longer messages. In the next section, however, we will see one big advantage that can be gained from polyliteral encryption. 4.2 fractionating ciphers The polyliteral ciphers we have been looking at are not very different from simple substitution ciphers. The only trick to attacking them is figuring out how many symbols correspond to each letter, which can

116 • Chapter 4 be done fairly easily by just guessing and starting the attack. With the right guess, Eve can do a frequency analysis just like simple substitu- tion ciphers. In order to make these ciphers secure, something fancier needs to be added. One possibility is simply to scatter some null symbols throughout the message to disrupt the orderly division of the ciphertext into groups. The symbols can be placed in prearranged positions, or, if they are not otherwise used in the cipher, they can be distributed at Alice’s whim and Bob will simply ignore them. This last technique works well with polyliteral ciphers, since they use a smaller set of symbols than the original message anyway. Another possibility is to make different groups different lengths. An example of this is the straddling checkerboard: 01234 5 6789 ab c defg 1hi j k l mnopq 2r s tuvwxyz The letters in the first row are encrypted with a single digit; the let- ters in the other rows are encrypted with 2 digits each. Since there are no 2-digit ciphertext equivalents that start with 3 through 9, it is unambiguous when Bob should pick a letter in the first row as opposed to one of the others. Yet another possibility is to combine a polyliteral cipher with another cipher in such a way as to split up the ciphertext groups. This is often referred to as fractionation. The simplest thing to do is to per- form a transposition after the polyliteral cipher, so that the symbols corresponding to a single plaintext letter are no longer adjacent. Per- haps the “most interesting and practical” of these fractionating product ciphers was the cipher invented by the German officer Lieutenant (later Colonel) Fritz Nebel and used by the German army during World War I. The Germans called this cipher GedeFu 18, short for Geheimschrift der Funker 1918, or Radio Operators’ Cipher 1918. The French, seeing a bunch of cryptograms containing only the letters A, D, F, G, V, and X, called it the ADFGVX cipher. This system starts out with a 6×6 version of the Polybius square, containing both letters and digits in a scrambled order and labeled on the top and side with the letters ADFGVX. For example:

Ciphers and Computers • 117 ADFGVX Ab 5xq j c D6 yrkd7 Fz s le81 G t mf 9 2u Vn g03vo Xh a 4wp i So to encrypt the name Zimmermann, Alice would write plaintext: z i m m e r m a n n ciphertext: FA XX GD GD FG DF GD XD VA VA This was followed by a keyed columnar transposition. For instance, if the keyword for this part of the cipher was germany, then we would have first second ciphertext ciphertext 3264157 g e r ma ny F AXXGDG GAF XDXG DF GDF GD F F DDGGD XDVAVAX VDXAAVX and the final ciphertext would be GFVAF DFDXX DADGA XGVGD X A general method of breaking this cipher was not discovered un- til after the war was over, and an outline was first published in 1925, although during the war Allied cryptanalysts were able to break the ci- pher when they could compare ciphertexts that came from plaintexts with identical beginnings or endings or if the division into columns was easily guessed. That makes the ADFGVX cipher easily one of the most successful ciphers of World War I and one of the most difficult to break of any practical cipher not requiring a machine of some sort.

118 • Chapter 4 The reason that this cipher is so difficult to solve and the reason it is in the chapter on computer ciphers is because it embodies one of the two principles at the heart of all modern ciphers. These are now known as diffusion and confusion, and they were given their modern meanings by Claude Shannon. Shannon was an engineer and math- ematician who is considered the founder of the field of information theory. In defining these principles, he was concerned about statis- tical attacks on a cipher. In a paper written in 1945 and declassified and published in 1949, Shannon defined diffusion as the idea that sta- tistical structures in the plaintext that depend on looking at only a few letters at a time, such as letter frequency or digraph frequency, should be “diffused” in the ciphertext into statistics that require look- ing at long strings of letters. Shannon’s definition of confusion, on the other hand, was the idea that given simple statistics of the ciphertext, it should be very complicated to find the key. In particular, the ci- pher should be resistant to known-plaintext attacks, since information about the frequency of letters and words in English (or any other hu- man language) always allows a certain amount of successful guessing of plaintext. The ADFGVX cipher does a reasonably good job of diffusion. The columnar transposition generally sends the two ciphertext letters cor- responding to each plaintext letter to widely different parts of the final ciphertext, and thus any attempt to use letter frequency information to solve the biliteral substitution cannot succeed until substantial amounts of ciphertext rearranging is done. On the other hand, the usual tech- niques of solving transposition ciphers from Sections 3.6 and 3.7 require information about the original plaintext letters, such as whether they are vowels or consonants and which ones fit into high-frequency digraphs. This information is difficult to obtain before the substitution is solved. On the other hand, Shannon’s aim is not completely satisfied, since the plaintext letters are not truly diffused into a large number of cipher- text letters but merely into two widely separated ones. The ADGFVX cipher also exhibits rather good confusion, especially if the Polybius square part of the key is chosen carefully. If care is taken to avoid high-frequency letters clustering in the square, known-plaintext attacks become very difficult.

Ciphers and Computers • 119 4.3 how to design a digital cipher: sp-networks and feistel networks Shannon himself did not invent any ciphers, but in the same paper where he defined diffusion and confusion, he did outline a technique for building ciphers that might possess these characteristics. In order to talk about his ideas and, in general, about the sort of ciphers designed for use in computers, it will be convenient to talk a little first about how mathematicians think about functions. We already saw some glimpses of this in Section 3.3. You probably already think you know what a function is; you are no doubt familiar with functions like f(x) = x2 and f(x) = sin x. The first thing that pops into your head when you see one of these functions is probably the graph of the function, as in Figure 4.1. You are not alone: in elementary algebra and calculus—and, in fact, in almost every mathematical field developed between the seven- teenth and nineteenth centuries—the study of functions is closely tied to the study of curves in the plane or, sometimes, surfaces in 3 or more dimensions. Toward the end of the nineteenth century, however, mathe- maticians began to think of functions in a somewhat more general way. A function is simply something that “takes in” objects of one type and “spits out” other objects, possibly of the same type and possibly not, according to some definite rule. The rule may be a formula, a set of in- structions, a table, or even a picture, as long as it is unambiguous and always produces the same output from the same input. f(x) = x2 y = x2 f(x) = sin x y y 1.0 25 y = sin x 20 0.5 15 10 ––2π –2π π –32π x 5 2π –5 –4 –3 –2 –1 x –0.5 –5 12345 –1.0 Figure 4.1. The graphs of f(x) = x2 and f(x) = sin x.

120 • Chapter 4 For example, f(x) = x2 is a function that takes in real numbers and spits out real numbers according to a formula. The Caesar cipher, f(P) = “the letter P shifted 3 letters down the alphabet, wrapping around” is a function that takes in letters and spits out letters, according to a set of instructions. The Baudot code is a function that takes in letters and spits out strings of binary digits according to a table. The permutation 1234 2431 can be thought of as a function that takes in numbers between 1 and 4 (representing ciphertext positions) and spits out numbers between 1 and 4 (representing the plaintext letters that go in those positions), according to a table, and so on. Shannon proposed using a mixing function in ciphers to provide diffusion and confusion. This is an idea that Shannon admits cannot be defined precisely for ciphers. “Speaking loosely, however,” he says “we can think of a mixing transformation as one which distributes any rea- sonably cohesive region in the space fairly uniformly over the entire space. If the first region could be described in simple terms, the second would require very complex ones.” If this were a simple substitution ci- pher, for instance, we would want plaintext letters near the beginning of the alphabet to give ciphertext letters scattered in a complex way through the alphabet. We would also want plaintext letters with high probabilities to be scattered in a complex way, and so on. To achieve diffusion, on the other hand, we want to operate on larger blocks of letters. Shannon suggests a function of the form F(P1P2 · · · Pn) = H(S(H(S(H(T(P1P2 · · · Pn)))))), as shown in Figure 4.2, where T is some transposition acting on groups of n letters, H is some Hill cipher on n-letter blocks that is not too complicated, and S is a simple substitution cipher applied to each let- ter of the block. Each step is simple, but it is perfectly believable that the combination and repetition would provide good mixing properties. We have not yet discussed the role of the key. In Shannon’s concep- tion, F is not secret and does not involve a key, so there is no security yet. However, this makes F particularly easy to perform using a com- puter or other machine, which is important because F will be the most