Outline

Our workshop probably won't get to every item in this outline, but this should give you some idea of the material we propose to cover, and the order in which we will consider the topics.

I. Definitions

1. Code vs. cipher. A code works at the level of words, a cipher at the level of letters.
2. Encryption and decryption. We use a system and (usually) a key to map from plaintext to ciphertext and vice versa.
3. Cryptanalysis. Breaking a cipher -- guessing the method and the key -- is quite different from simple decryption.
4. Substitution and transposition. Most of the ciphers we will study fall into one of these two broad categories.

1. Shift ciphers -- Encryption and decryption.
   1. Encryption and decryption by hand; use of a cipher wheel.
   2. Mapping the alphabet to {0, ..., 25} and back.
   3. Modular addition and subtraction; modular addition tables in Excel.
   4. Description of a shift and its inverse in mathematical terms; encryption and decryption in Excel. A shift cipher is implemented by adding a constant to each plaintext letter, and its inverse by subtracting the same constant.
2. Shift ciphers -- Cryptanalysis.
   1. Constructing a frequency table.
   2. Eyeball matching with a standard frequency histogram.
3. Affine ciphers -- Encryption and decryption.
   1. Modular multiplication.
      1. Modular multiplication tables in Excel.
      2. One-to-one functions. The map x ax mod m (a dilation) fails to be one-to-one when a and m have common factors. Shifts are always one-to-one.
      3. (Optional) GCDs and the Euclidean Algorithm. This is a fairly quick way to determine whether two numbers have any common factors.
      4. Multiplicative inverses in modular arithmetic. We can find these by looking through a multiplication table, or by a simple extension of the Euclidean Algorithm.
   2. Modular affine functions. As long as GCD(a,m)=1, the map x ax+b mod m is one-to-one and therefore invertible. We compare this with inversion of ordinary linear functions.
   3. Encryption and decryption of an affine cipher by hand. It's not difficult to make an alphabet table for an affine cipher. In fact, there's a nice short-cut, that also helps with cryptanalysis of affine ciphers.
   4. Encryption and decryption of an affine cipher using Excel. Since we can find the formula for the inverse of an affine function, we can set up spreadsheets for both encryption and decryption.
4. Affine ciphers -- Cryptanalysis.
   1. Frequency counts. We can guess at the most frequent and least frequent letters, but the shape of the frequency histogram will not be the same as the standard one.
   2. Bigram and trigram frequency tables. Each letter's "personality" lets us see through its disguise.
   3. Use of the cipher design in cryptanalysis. The images of two plaintext letters may determine the entire mapping, because we can sometimes solve the system {c₁ = a p₁ + b, c₂ = a p₂ + b} for a and b.
5. Word-key substitution ciphers -- Encryption and decryption.
   1. Creation of a word-key subsitution cipher.
   2. Encryption and decryption of a word-key subsitution cipher by hand. We simply make an alphabet table.
6. Word-key substitution ciphers -- Cryptanalysis.
   1. Application of frequency tables and bigram and trigram frequency tables to idenfity letters in a word-key substitution cipher. Again, the frequency histogram shape will be unfamiliar.
   2. Use of the cipher design in breaking a word-key subsitution cipher. The idea is to reconstruct the keyword.
7. (Optional) Cryptanalysis of monoalphabetic substitution ciphers using cribs and probable words.
   1. Letter-frequency patterns.
   2. Repeated-letter patterns.
8. Comparison of monoalphabetic substitution ciphers.
   1. Complexities of the keys. A simple shift uses a one-element key, and the cipher is broken by fixing just one letter; an affine code uses a two-element key and may be broken by fixing as few as two letters; a word-key substitution cipher has a variable-length key, and requires more work to break.
   2. Discussion of a general monoalphabetic substitution cipher.
      1. The 26! permutations of {A, ..., Z}. How do you remember a random key? Should a key be memorized, or written down?
      2. (Optional) Cycle notation and the order of a permutation. If a permutation has order 2, then encryption and decryption are identical.
      3. Comparison of the times required to break substitution ciphers by brute force.
      4. (Optional) Using nulls to defeat frequency analysis.

1. The Vigenère cipher with a cyclic key -- Encryption and decryption.
   1. Vigenère encryption and decryption by hand. We use a Vigenère table to do this.
   2. Mathematical description of the (cyclic, standard) Vigenère cipher. The mapping is x x + k(t), where k() is the keyword and t is time.
   3. (Optional) Implementation of the (cyclic, standard) Vigenère cipher (and its inverse) in Excel. This requires learning about some rather esoteric features of Excel.
2. The Vigenère cipher with a cyclic key -- Cryptanalysis.
   1. Key length
      1. Repeated cipher groups. The key length is probably a factor of most of the distances between repeated cipher groups.
      2. (Optional) Standard deviation of the frequency table. This gives a (very) rough estimate of key length.
   2. Separating the alphabets. We use the key length to reduce the cyclic Vigenère to a monoalphabetic problem.
   3. Using the cipher design in cryptanalysis. The standard alphabet makes the monoalphabetic matchings easy, and the keyword itself may provide clues to its own reconstruction.
3. Polyalphabetic ciphers with (cycling) non-standard alphabets.
   1. Discussion of encryption and decryption procedures and devices. This kind of cipher is well-suited to special tables or mechanical devices.
   2. Discussion of cryptanalysis techniques. As long as the alphabet is constant, the techniques are not very different from those use to break a standard Vigenère cipher.
   3. (Optional) Cryptanalysis exercise.
4. Some other substitution ciphers.
   1. Polyalphabetic ciphers with very long keys. These have to depend on mechanical devices.
   2. (Optional) Auto-key systems.
   3. The Wheatstone device. An astonishingly simple machine implements a substitution cipher in which the alphabets move irregularly, and the cycle of alphabets is the GCD of the sizes of two wheels.
   4. (Optional) The Thomas Jefferson device.
   5. (Optional) The Playfair cipher.
   6. One-time pads. This is the one cipher that's completely unbreakable, even in theory.
      1. Demonstration of the unbreakability of a one-time pad.
      2. (Optional) Use of a pseudo-random number generator to implement a one-time pad. If two computers use the same pseudo-random number generator with the same seed, then they appear to implement one-time pad communication. It's actually a Vigenère cipher with a very long key; pseudo-random numbers aren't truly random.
      3. (Optional) Discussion of why a one-time pad can't be used more than once.
5. The Enigma machine. This is a polyalphabetic substitution cipher with a very large number (26³) of alphabets, but each alphabet consists entirely of 2-cycles.

1. Examples of transposition ciphers.
   1. Fence-post and other rectangular ciphers.
   2. Rectangular ciphers with keywords. A keyword is just a handy way to remember a permutation of the rows or columns of the grid.
   3. The poem code. This is a transposition code used by the Allied underground in World War II. We can reconstruct how it works from an episode in Between Silk and Cyanide by Leo Marks.
2. Transposition cipher cryptanalysis and security.
   1. Recognition of a transposition cipher by frequency count. If the frequency histogram looks like the standard one, the cipher is probably a transposition.
   2. Factors of the ciphertext length. For a rectangular transposition code, cryptanalysis begins by drawing a grid with the correct dimensions.
   3. Difficulty of breaking a rectangular transposition code. How many possibilities are there?

1. The notion of a public-key system. An on-line company (olc) needs to tell your computer how to encrypt your credit-card number without revealing how to decrypt it.
2. Basic ideas from number theory.
   1. Primes, the Fundamental Theorem of Arithmetic, and the definition of square-free. The public-key system uses numbers that are products of two (distinct) primes.
   2. The Euler function.
      1. Definition. The number (m) is equal to the number of elements of {1, ..., m-1} that have multiplicative inverses modulo m. (From an earlier activity, we know that this is the number of elements of {1, ..., m-1} that have no common factors with m.)
      2. Calculation. If m is prime, then (m) = m-1. If m = pq is a product of (distinct) primes, then (m) = (p-1)(q-1).
   3. Modular power tables. If m is square-free, then every column in a mod-m power table whose number is one more than a multiple of (m) contains the numbers 1 through m-1 in standard order.
   4. Statement of Euler's Theorem: If m is square-free, then a^{n (m)+1} mod m = a.
3. The Public-key cryptography system.
   1. Preparation. The OLC obtains two primes, p and q, and multiplies them together to get m = pq. It chooses a number k between 1 and m. (The number k must have no common factors with (m); otherwise it is chosen essentially at random.)
   2. Encryption. The OLC tells your computer the numbers m and k. Your computer takes your credit-card number x and computes x^k mod m. Call this number y. Your computer sends y back to the OLC.
   3. Decryption. The OLC knows that m = pq, so it can compute (m) = (p-1)(q-1). It now finds a multiplicative inverse for k modulo (m); that is, a number k' such that kk' is one more than a multiple of (m). It computes y^k' mod m. Since y= x^k mod m, the result is (x^k)^k'm = x^kk' mod m = x by Euler's Theorem.
4. Example of public-key cryptography.
5. (Optional.) This history and alternate history of public-key cryptography. There's a nice account in The Code Book by Simon Singh.
6. The security of public-key cryptography. The decryption key, k', is easy to compute (Euclid's algorithm) once you know k and (m). But how can you find (m) from m?

Annotated Bibliography [Outline]

• Helen Fouché Gaines. Cryptanalysis: A Study of Ciphers and their Solution. Dover Publications, New York, 1939.

  Gaines describes many of the classic transposition and substitution ciphers, and provides detailed instructions for their cryptanalysis. As you'd guess from the copyright date, this is all pencil-and-paper stuff.

• Martin Gardner. Codes, Ciphers, and Secret Writing. Dover Publications, New York, 1972.

  This very friendly and relatively short book describes many transposition and substitution ciphers, and includes a fascinating chapter on invisible inks.

• David Kahn. The Codebreakers. Macmillan, New York, 1967.

  This twelve-hundred-page monster traces the use of codes and ciphers throughout history (Western history, mostly). The historical accounts are often gripping (they often include fascinating character sketches), and they are interspersed with very readable discussions of the nuts and bolts of cryptographic techniques of each historical period. One caution, though: this is a big, long book.

• David Kahn. Seizing the Enigma: The Race to break the German U-boat codes, 1939 - 1943. Souvenir, London, 1992.

  This is a very readable account of the activities that allowed the Allies to read a good deal of the communication between the German command and the U-boat fleet during World War II. The characters include brilliant cryptographers, daring spies, and heroic soldiers; the intertwining of so many disparate people and events makes for fascinating reading. The discussion of the Enigma code itself is sketchy, but at least it's present.

• Leo Marks. Between Silk and Cyanide. The Free Press, New York, 1998.

  Marks worked for British intelligence during World War II, trying to reconstruct messages that had been incorrectly enciphered or incorrectly transmitted by underground agents working on the Continent. This is the story of his years in that job, his interactions with the agents, and his attempts to convince his military superiors to switch to a more secure and more robust encryption scheme. It reads like a novel -- sort of a combination of a good spy thriller and Catch-22.

• Ivan Niven, Herbert Zuckerman, and Hugh Montgomery. An Introduction to the Theory of Numbers. John Wiley & Sons, New York, fifth edition, 1991.

  This is a standard textbook on Number Theory, aimed at the advanced undergraduate or beginning graduate student level. It's a good reference for the details behind public-key cryptography, and some of the techniques that contemporary mathematicians use to attack the problem of factoring products of large primes.

• Simon Singh. The Code Book. Anchor Books, New York, 1999.

  This is an excellent and very readable account of the history and practice of cryptography. I recommend it highly.

• Abraham Sinkov. Elementary Cryptanalysis: A Mathematical Approach. Random House and the L. W. Singer Company, New York, 1968.

  The mathematics in this book is very clear and accessible. The book covers many of the same cryptanalysis techniques as the Gaines book, but uses mathematical notation, so that the techniques can be generalized and automated more easily.