Cryptography - Lecture 4 - Classical Substitution Ciphers cont

This lesson continues the discussion of substitution ciphers, such as vigenère, beaufort, variant-beaufort, and general, showing how they're used, as well as the techniques used to break them.

Objectives

Preliminary Reading

Lecture Content

Polyalphabetic Ciphers

1. Polyalphabetic Ciphers
   • an approach to improving security is to use multiple cipher alphabets
   • hence the name polyalphabetic ciphers
   • makes cryptanalysis harder since have more alphabets to guess
   • and because flattens frequency distribution
   • use a key to select which alphabet is used for each letter of the message
   • ith letter of key specifies ith alphabet to use
   • use each alphabet in turn
   • repeat from start after end of key is reached

     One approach to reducing the "spikyness" of natural language text is used the Playfair cipher which encrypts more than one letter at once. We now consider the other alternative, using multiple cipher alphabets in turn. This gives the attacker more work, since many alphabets need to be guessed, and because the frequency distribution is more complex, since the same plaintext letter could be replaced by several ciphertext letters, depending on which alphabet is used.

2. Vigenère Cipher
   • simplest polyalphabetic substitution cipher is the Vigenère Cipher
   • is multiple caesar ciphers
   • key is multiple letters long K = k₁ k₂ ... k_d
   • ith letter specifies ith alphabet to use
   • use each alphabet in turn
   • repeat from start after d letters in message
   • can describe this mathematically as the function:

     Encryption is done using

     E_ki(a): a -> a + k_i (mod 26)

     Decryption is done using

     D_ki(a): a -> a - k_i (mod 26)

     Simple create a set of caesar cipher translation alphabets, then use each in turn, as shown next.

3. Vigenère Example
   • write the plaintext out
   • under it write the keyword repeated
   • then using each key letter in turn as a caesar cipher key
   • encrypt the corresponding plaintext letter

     Plaintext       THISPROCESSCANALSOBEEXPRESSED
     Keyword         CIPHERCIPHERCIPHERCIPHERCIPHE
     Plaintext       VPXZTIQKTZWTCVPSWFDMTETIGAHLH
     

     In this example have the keyword "CIPHER". Hence have the following translation alphabets:

     C ->  CDEFGHIJKLMNOPQRSTUVWXYZAB
     I ->  IJKLMNOPQRSTUVWXYZABCDEFGH
     P ->  PQRSTUVWXYZABCDEFGHIJKLMNO
     H ->  HIJKLMNOPQRSTUVWXYZABCDEFG 
     E ->  EFGHIJKLMNOPQRSTUVWXYZABCD
     R ->  RSTUVWXYZABCDEFGHIJKLMNOPQ
     
           ABCDEFGHIJKLMNOPQRSTUVWXYZ
     to map the above plaintext letters.
     

     Hence, map the plaintext message as follows:

     'T'	uses key 'C'	maps to 'V'
     'H'	uses key 'I'	maps to 'P'
     'I'	ises key 'P'	maps to 'X'
     etc
     

4. Crypto Aids
   • several simple aids assist with en/decryption
   • a Saint-Cyr Slide is a simple manual aid
   • has a slide with repeated alphabet
   • line up plaintext 'A' with key letter, eg 'C'
   • then can read off any desired mapping for that key letter

       +--------------------------+
       |ABCDEFGHIJKLMNOPQRSTUVWXYZ|
     +----------------------------------------------------+
     |ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZ|
     +----------------------------------------------------+
       |                          |
       +--------------------------+
     

   • can bend round into a cipher disk
   • or expand into a Vigenère Tableau

     The "Saint-Cyr Slide" was popularised and named by Jean Kerckhoffs, who published a famous early text "La Cryptographie Militaire" (Miltary Cryptography) in 1883. He named the slide after the French National Military Academy where the methods were taught. He also noted that any slide can be expanded into a tableau, or bent round into a cipher disk. cf. Kahn Ch 8 pp230-239.

5. Vigenère Tableau
   • a simple aid for using Vigenère Ciphers
   • identify desired cipher row
   • then map plaintext letter at top to corresponding letter

                  Plaintext Letter
             ABCDEFGHIJKLMNOPQRSTUVWXYZ
          +-----------------------------+
        A |  ABCDEFGHIJKLMNOPQRSTUVWXYZ |
        B |  BCDEFGHIJKLMNOPQRSTUVWXYZA |
        C |  CDEFGHIJKLMNOPQRSTUVWXYZAB |
        D |  DEFGHIJKLMNOPQRSTUVWXYZABC |
        E |  EFGHIJKLMNOPQRSTUVWXYZABCD |
     K  F |  FGHIJKLMNOPQRSTUVWXYZABCDE |
     e  G |  GHIJKLMNOPQRSTUVWXYZABCDEF |
     y  H |  HIJKLMNOPQRSTUVWXYZABCDEFG |
        I |  IJKLMNOPQRSTUVWXYZABCDEFGH |
     L  J |  JKLMNOPQRSTUVWXYZABCDEFGHI |
     e  K |  KLMNOPQRSTUVWXYZABCDEFGHIJ |
     t  L |  LMNOPQRSTUVWXYZABCDEFGHIJK |
     t  M |  MNOPQRSTUVWXYZABCDEFGHIJKL |
     e  N |  NOPQRSTUVWXYZABCDEFGHIJKLM |
     r  O |  OPQRSTUVWXYZABCDEFGHIJKLMN |
        P |  PQRSTUVWXYZABCDEFGHIJKLMNO |
        Q |  QRSTUVWXYZABCDEFGHIJKLMNOP |
        R |  RSTUVWXYZABCDEFGHIJKLMNOPQ |
        S |  STUVWXYZABCDEFGHIJKLMNOPQR |
        T |  TUVWXYZABCDEFGHIJKLMNOPQRS |
        U |  UVWXYZABCDEFGHIJKLMNOPQRST |
        V |  VWXYZABCDEFGHIJKLMNOPQRSTU |
        W |  WXYZABCDEFGHIJKLMNOPQRSTUV |
        X |  XYZABCDEFGHIJKLMNOPQRSTUVW |
        Y |  YZABCDEFGHIJKLMNOPQRSTUVWX |
        Z |  ZABCDEFGHIJKLMNOPQRSTUVWXY |
          +-----------------------------+
     

6. Beauford Cipher
   • similar to Vigenère but with alphabet written backwards
   • can describe this mathematically as the function:

     Encryption is done using

     E_ki(p): p -> k_i - p (mod 26)

     Decryption is done using

     D_ki(c): c -> k_i - c (mod 26)

   • eg. if using a single key letter of 'd' have translation alphabet

     Plain:  ABCDEFGHIJKLMNOPQRSTUVWXYZ
     Cipher: DCBAZYXWVUTSRQPONMLKJIHGFE
     

     Here are using a backwards alphabet. Note that the same function is used for decryption (unlike Vigenère). The effect of the cipher is to reverse the order of the plaintext letters, and then right shift them.

7. Variant-Beauford Cipher
   • like the Vigenère, but shifting alphabet to left
   • really just the inverse of the Vigenère (decrypts it)
   • can describe this mathematically as the function:

     Encryption is done using

     E_ki(a): a -> a - k_i (mod 26)

     Decryption is done using

     D_ki(a): a -> a + k_i (mod 26)

   • will always have a Vigenère key with same effect
   • eg. Variant-Beauford key 'c' (shift left 2 places)
   • same as Vigenère key 'y' (shift right 24 places)

     Vigenère and Variant-Beauford Ciphers are mutual inverses. The translation used to encrypt one, decrypts the other. Also always have equivalent pairs of keys, since shifting left i places MUST be the same as shifting right by 26-i places. This also means that when analysing, have no way of distinguishing a Vigenère from a Variant-Beauford cipher, except that possibly with one the key is a valid word, otherwise is random letters.

8. General Polyalphabetic Cipher
   • generalisation of the General Monoalphabetic Cipher
   • have multiple translation alphabets
   • each constructed using a keyword
   • hence overall key is a phrase
9. Unicity Distances of Polyalphabetic Ciphers
   • can generalise the equation for a single shifted alphabet, ie. Vigenère or Beauford ciphers
   • if using d possible alphabets, then:

     N = H(K)/D = log2 26d/3.2 = d log2 26/3.2 = 1.5d 

   • hence theoretically only need about 2 letters per alphabet to break
   • can similarly generalise the equation for the general monoalphabetic ciphers to get 27.6d

   Moving to polyalphabetic ciphers does improve the security, but not dramatically. Each additional alphabet adds the same amount of work to break, but doesn't dramatically improve the security.

10. Autokey Cipher
    • if more alphabets helps to improve the security
    • at limit want as many alphabets as letters in message
    • but how to transfer such a key
    • Vigenère proposed the autokey cipher
    • where the keyword is prefixed to the message
    • and then that is used as the key for the message
    • knowing keyword can recover the first few letters
    • then use these in turn on the rest of the message
    • eg. given key "DECEPTIVE" and message "WE ARE DISCOVERED SAVE YOURSELF"

      key:         DECEPTIVEWEAREDISCOVEREDSAV
      plaintext:   WEAREDISCOVEREDSAVEYOURSELF
      ciphertext:  ZICVTWQNGKZEIIGASXSTSLVVWLA
      

      See that the key used is the keyword "DECEPTIVE" prefixed to as much of the message "WEAREDISCOVEREDSAV" as is needed. When deciphering, recover the first 9 letters using the keyword "DECEPTIVE". Then instead of repeating the keyword, start using the recovered letters from the message "WEAREDISC". As recover more letters, have more of key to recover later letters.

11. Book Cipher
    • another method of creating a key as long as a message
    • is to use words from a book to specify the translation alphabets
    • key used is then the book and page and paragraph to start from
12. Problems with Autokey and Book Ciphers
    • both Autokey and Book ciphers look like having good characteristics
    • but problem is that the same language characteristics are used by the key as the message
    • ie. a key of 'E' will be used more often than a 'T' etc
    • hence an 'E' encrypted with a key of 'E' occurs with probability (0.1275)2 = 0.01663, about twice as often as a 'T' encrypted with a key of 'T'
    • have to use a larger frequency table, but it exists
    • given sufficient ciphertext this can be broken
    • if a truly random key as long as the message is used, the cipher will be secure
    • called a Vernam Cipher or One-Time pad, we meet this later

Kasiski Method and the Index of Coincidence

1. Kasiski Method and the Index of Coincidence
   • want to cryptanalyse polyalphabetic ciphers
   • first problem is determining how many alphabets were used
   • two possible approaches: Kasiski Method and the Index of Coincidence
2. Kasiski Method
   • original method developed by Babbage and Kasiski
   • use repetitions in ciphertext to give clues as to period
   • look for same plaintext an exact period apart
   • which results in the same ciphertext
   • of course, could also be random fluke
   • eg.

     Plaintext:   TOBEORNOTTOBE
     Key:         NOWNOWNOWNOWN
     Ciphertext:  GCXRCNACPGCXR
     

   • see repeated ciphertext "GCXR"
   • since repeats are 9 chars apart, guess period is 3 or 9
   • in general find a number of duplicated sequences
   • collect all their distances apart, look for common factors
   • remembering that some will be random flukes and need to be discarded

     As we saw previously, it was this discovery by Babbage & Kasiski which broke the previously "unbreakable" cipher. Like most advances in cryptology, it came from looking at the problem in a different and "new" way - in this case, realising that repeated runs of plaintext letters, that "happened" to line up with the same keyword letters, would generate the same run of ciphertext letters. This was the chink in the armour needed.

3. Index of Coincidence
   • introduced in 1920s by William Friedman
   • a measure of the variation of frequencies of letters in ciphertext
     • period = 1 => simple subs => variation is high, IC high
     • period > 1 => poly subs => variation is reduced, IC low
   • develop IC from the idea of a Measure of Roughness as follows

     The Index of Coincidence (IC) is a critical statistic used in analysing classical polyalphabetic substitution ciphers. Note that William F Friedman is one of the great cryptographers of the early 20C, and wrote several of the seminal works (classified until recently) on military cryptanalysis, now published by Aegean Park Press - look him up as an author in the ADFA library catalog. The critical idea is to get an estimate of the number of alphabets used, by looking at how "spiky" or not, the distribution of letters in the ciphertext is, since we know that the more alphabets used, the flatter it gets. The development of the IC formula comes from first developing the idea of a "Measure of Roughness", and then equating that formula to the observed frequencies in the ciphertext letters, as shown next.

4. Measure of Roughness (MR)
   • a measure of the variation of frequencies of individual characters
   • relative to a uniform distribution
   • for English, with 26 letters, have:

          i='z' 
     MR = SUM   ( pi - 1/26)2
          i='a' 
     

   • where pi is the probability that any randomly chosen letter is the ith letter
   • must have all the pi's summing to 1 (must be some letter in the alphabet)

     i='z' 
     SUM   pi = 1
     i='a' 
     

     The full derivation of the MR and IC is given in Sinkov Ch 3 pp63-70, and a briefer version in Seberry 1/e Ch3 pp71-74.

5. Measure of Roughness (MR) cont
   • by expanding and rearranging the equation, we can get

          i='z' 
     MR = SUM   pi2 - 0.038
          i='a' 
     

     or

                  i='z' 
     MR + 0.038 = SUM   pi2
                  i='a' 
     

   • which gives the probability that two arbitrary letters in the analysed text are the same
6. Measure of Roughness (MR) cont
   • can compute MR for plaintext using characteristic letter frequencies
   • eg. MR for English is 0.028
   • can also compute MR for a flat distribution is 0
   • when analysing ciphertext the plaintext letter probabilities and period are unknown
   • hence cannot compute MR, but can estimate it from ciphertext
7. Estimating MR from Ciphertext
   • want an approximation for the SUM of pi2
   • but what does it mean?
   • well pa2 is the probability that two arbitrarily selected letters are both 'a'
   • similarly pb2 is probability both are 'b'
   • hence the sum is the probability that two arbitrarily selected letters are the same (regardless of their value)
8. Estimating MR from Ciphertext cont
   • the number of pairs of letters that can be chosen from ciphertext of length N is N choose 2:

     [N]
     | | = 1/2 N (N-1)
     [2]
     

   • if Fi is the frequency of the ithletter in the ciphertext
   • then the number of pairs containing just the ith letter is

     Fi(Fi-1)
     -------
        2
     

   • and if there's a total of N letters in the ciphertext, then

     i='z'
     SUM  Fi = N
     i='a'
     

9. Index of Coincidence
   • now define the Index of Coincidence (IC)
   • the probability that two letters chosen at random from the ciphertext are actually the same letter
   • eg. both A's

          i='z' Fi(Fi-1)
     IC = SUM   -------
          i='a'  N(N-1)
     

   • use the IC estimate in the MR formulae to get

     MR + 0.038 = IC
     

   • since know that the MR varies from 0 (uniform) to 0.028 (English)
   • will have IC varying from 0.038 (many alphabets) to 0.066 (single alphabet)
   • other languages will have different values (different number of letters, different frequency distributions)

     Now have a way to approximate the MR using the IC, which calculated from the observed ciphertext letter frequencies, and compare to the expected values for any given language. The values here are for English, see Seberry for values for other languages.

10. IC and the Number of Alphabets
    • know that as we increase the number of alphabets will get a more uniform distribution
    • probability theory gives the following equation for a cipher of period d the expected value of the IC is

                     1 N-d           [d-1]  N
      Expected(IC) = - --- (0.066) + |   | --- (0.038)
                     d N-1           [ d ] N-1
      

11. IC and the Number of Alphabets Table
    • can compute this for d from 1 to 20 in English and get:

      Period (No of Alphabets)	Expected IC
      1	0.0660
      2	0.0520
      3	0.0473
      4	0.0450
      5	0.0436
      6	0.0427
      7	0.0420
      8	0.0415
      9	0.0411
      10	0.0408
      11	0.0405
      12	0.0403
      13	0.0402
      14	0.0400
      15	0.0399
      ...	...
      Infinite	0.0380

      See Seberry 1/e Fig3.4 p74 for example program code to compute these values. Again, this is for English, but by substituting suitable values for number of letters (N) and range of IC values can get equivalent table for other languages. Given this table, you first compute the IC for some sample ciphertext, and then lookup that value in the table to get an estimate of the number of alphabets that would have been used to get such an IC. Note that this is a statistical measure - so the estimate may well be out. But it provides an idea of the range it might be.

Cryptanalysis of Polyalphabetic Ciphers

1. Cryptanalysis of Polyalphabetic Ciphers
   • in order to break a polyalphabetic cipher must
   • first determine how many alphabets were used: Kasiski method & IC help estimate period d
   • then separate ciphertext into d sections
   • if compute IC on each of these separately, should get monoalphabetic value (if not, have a wrong guess)
   • then solve each as a monoalphabetic cipher using frequency distribution, common double & triple letters and word boundaries
   • taking care to identify which alphabet each letter in a group comes from

Summary

1. Summary
   • polyalphabetic ciphers: vigenère, beauford, variant-beauford, autokey
   • kasiski method & index of coincidence
   • cryptanalysis of polyalphabetic ciphers and the krypto program

Exercises

1. Exercises
   1. encrypt and then decrypt by hand, the text below using each of the following ciphers:
      1. Vigenère with a key of DOG
      2. Beauford with a key of DOG
      3. Variant-Beauford with a key of DOG

      this terminal is no more it has ceased to be its expired and gone
      to meet its maker this is a late terminal its a stiff bereft of
      life it rests in peace if you hadnt nailed it to the bench it
      would be pushing up the daisies this is an xterminal
      

Additional References