Cryptography - Lecture 3 - Classical Substitution Ciphers

This lesson introduces classical cryptographic techniques, which used simple substitution or transposition ciphers. It describes the various types of monoalphabetic substitution ciphers, such as caesar, general, showing how they're used, as well as the techniques used to break them.

Objectives

Preliminary Reading

Lecture Content

Classical Encryption Techniques

1. Classical Encryption Techniques
   • two basic components in classical ciphers: substitution and transposition
   • substitution ciphers - has letters replaced by others
   • transposition ciphers - has letters arranged in a different order
   • these ciphers may be:
   • monoalphabetic - only one substitution / transposition is used, or
   • polyalphabetic - where several substitutions / transpositions are used
   • several such ciphers may be concatentated together to form a product cipher

     The fundamental building blocks of classical ciphers are the substitution and transposition operations. Alone, they form the basis of most classical ciphers. Concatenated together, they can be used to construct a considerably more secure cipher, from which evolved the modern private key block ciphers we use today.

2. Caesar Cipher
   • have met this before, the first documented cipher
   • first attested use in military affairs (cf Gallic Wars)
   • replace each letter by 3rd letter on
   • more generally can use any shift from 1 to 25
   • can describe this mathematically as the function:

     Assign

     A the value 0, B 1, C 2, ... Y 24, Z 25; then

     Encryption is done using

     E_k: i -> i + k (mod 26)

     Decryption is done using

     D_k: i -> i - k (mod 26)

     Substitution ciphers form the first of the fundamental building blocks. The core idea is to replace one basic unit (letter/byte) with another. Whilst the early Greeks described several substitution ciphers, the first attested use in military affairs of one was by Julius Caesar, described by him in Gallic Wars (cf. Kahn pp83-84). Still call any cipher using a simple letter shift a caesar cipher, not just those with shift 3. The mathematical description uses modulo arithmetic (ie clock arithmetic). Here, when you reach Z you go back to A and start again. Mod 26 implies that when you reach 26, you use 0 instead (ie the letter after Z, or 25 + 1 goes to A or 0). Example: HOWDY (7,14,22,3,24) encrypted using key F (5) is MTBID

3. Cryptanalysis of the Caesar Cipher
   • only have 26 possible ciphers
   • A maps to A,B,..Z
   • could simply try each in turn
   • called an exhaustive key search
   • given some ciphertext, just try every shift of letters:

     LIZHZLVKWRUHSODFHOHWWHUV	Original ciphertext
     KHYGYKUJVQTGRNCEGNGVVGTU	try shift of 1
     JGXFXJTIUPSFQMBDFMFUUFST	try shift of 2
     IFWEWISHTOREPLACELETTERS	try shift of 3	*** plaintext
     HEVDVHRGSNQDOKZBDKDSSDQR	try shift of 4
     GDUCUGQFRMPCNJYACJCRRCPQ	try shift of 5
     	.....
     MJAIAMWLXSVITPEGIPIXXIVW	try shift of 25
     

   • eg. break ciphertext "GCUA VQ DTGCM"

     With a caesar cipher, there are only 26 possible keys, of which only 25 are of any use, since mapping A to A etc doesn't really obscure the message! cf. basic rule of cryptanalysis "check to ensure the cipher operator hasn't goofed and sent a plaintext message by mistake"! Can try each of the keys (shifts) in turn, until can recognise the original message. Note: as mentioned before, do need to be able to recognise when have an original message (ie is it English or whatever). Usually easy for humans, hard for computers. Example "GCUA VQ DTGCM" when broken gives "EASY TO BREAK", with a shift of 2 (key C).

Language Redundancy and Cryptanalaysis

1. Language Redundancy and Cryptanalaysis
   • human languages are redundant
   • eg "th lrd s m shphrd shll nt wnt"
   • letters are not equally commonly used
   • in English e is by far the most common letter
   • then T,R,N,I,O,A,S
   • other letters are fairly rare
   • cf. Z,J,K,Q,X
   • have tables of single, double & triple letter frequencies

     As the example shows, we don't actually need all the letters in order to understand written English text. Here vowels were removed, but they're not the only redundancy. cf written Hebrew has no vowels for same reason. Are usually familiar with "party conversations", can hear one person speaking out of hubbub of many, again because of redundancy in aural language also. This redundancy is also the reason we can compress text files, the computer can derive a more compact encoding without losing any information. Basic idea is to count the relative frequencies of letters, and note the resulting pattern.

2. English Letter Frequencies

            ______________________________________________________________
   a  7.25 |*****************************
   b  1.25 |*****
   c  3.50 |**************
   d  4.25 |*****************
   e 12.75 |***************************************************
   f  3.00 |************
   g  2.00 |********
   h  3.50 |**************
   i  7.75 |*******************************
   j  0.25 |*
   k  0.50 |**
   l  3.75 |***************
   m  2.75 |***********
   n  7.75 |*******************************
   o  7.50 |******************************
   p  2.75 |***********
   q  0.50 |**
   r  8.50 |**********************************
   s  6.00 |************************
   t  9.25 |*************************************
   u  3.00 |************
   v  1.50 |******
   w  1.50 |******
   x  0.50 |**
   y  2.25 |*********
   z  0.25 |*
           |______________________________________________________________
   Freq (%)    1   2   3   4   5   6   7   8   9  10  11  12  13  14  15 %
   

   This graph is based on counts done at ADFA in the late 1980's, and used to develop the tables published in Seberry & Pieprzyk.

3. Other Languages
   • natural languages all have varying letter frequencies
   • languages have different numbers of letters (cf. Norwegian)
   • can take sample text and count letter frequencies
   • cf. Seberry 1/e Appendix A has counts for 20 languages: being most European & Japanese & Malay
4. Use in Cryptanalysis
   • calculate letter frequencies for ciphertext being analysed
   • compare counts/plots against known values
   • in particular look for common peaks and troughs
   • peaks at: A-E-I spaced triple, NO pair, RST triple with U shape;
   • troughs at: JK, X-Z
   • key concept - monoalphabetic substitution does not change relative letter frequencies
   • concept was first discovered by Arabian scientists as we saw previously
5. Table of Common English Single, Double and Triple Letters

   Single Letter	Double Letter	Triple Letter
   E	TH	THE
   T	HE	AND
   R	IN	TIO
   N	ER	ATI
   I	RE	FOR
   O	ON	THA
   A	AN	TER
   S	EN	RES

6. Cryptanalysis of a Caesar Cipher
   • can analyse a caesar cipher using frequency counts also
   • eg. given "JXU WHUQJUIJ TYISELUHO EV CO WUDUHQJYED YI JXQJ Q XKCQD RUYDW SQD QBJUH XYI BYVU RO QBJUHYDW XYI QJJYJKTUI"
   • can count letters and plot as:

     
                       *                     *           
                       *                     *           
                       *             *       *       *   
                       *             *       *       *   
                       *             *       *       *   
           *         * *             *       *       *   
           *       * * *             *       *     * *   
           *       * * *             *       *   * * *   
       *   * *     * * *         *   *       *   * * *   
       * * * *     * * * *       *   * * * * * * * * *   
       * * * *     * * * * *     *   * * * * * * * * *   
     a b c d e f g h i j k l m n o p q r s t u v w x y z 
     

   • looking at this graph, the A-E-I triple is pretty clear at Q-U-Y
   • also HIJ triple would fit as RST, DE is then NO though less clear
   • suggests a key of Q was used (A to Q, etc)

     First hand count the relative frequency of each letter, see the language redundancy examples. The graph above is a straight plot of these counts (from krypto program). Having found the key, decrypt the message and recover: "THE GREATEST DISCOVERY OF MY GENERATION IS THAT A HUMAN BEING CAN ALTER HIS LIFE BY ALTERING HIS ATTITUDES"

General Monoalphabetic Cipher

1. Mixed Monoalphabetic Cipher
   • rather than just shifting the alphabet
   • could shuffle (jumble) the letters arbitrarily
   • each plaintext letter maps to a different random ciphertext letter
   • hence key is 26 letters long
   • eg.

     Plain:      ABCDEFGHIJKLMNOPQRSTUVWXYZ
     Cipher:     DKVQFIBJWPESCXHTMYAUOLRGZN
     
     Plaintext:  IFWEWISHTOREPLACELETTERS
     Ciphertext: WIRFRWAJUHYFTSDVFSFUUFYA
     

2. Security of the Mixed Monoalphabetic Cipher
   • now have a total of 26! ~ 4 x 1026 keys
   • with so many keys, might think this is secure
   • but would be !!!WRONG!!!
   • problem is that still have the characteristic language statistics
   • have to find some way of obscuring them
3. General Monoalphabetic Cipher
   • the Mixed Monoalphabetic Cipher has a 26 letter key
   • the General Monoalphabetic Cipher is a special form
   • with an easier way to specify key
   • given a keyword:
     • write key (with repeated letters deleted)
     • then write all remaining letters in columns underneath
     • then read off by columns to get ciphertext equivalents
4. General Monoalphabetic Cipher Example
   • eg. given the keyword "STARWARS"
   • remove repeated letters to get "STARW"
   • write out and fill in remaining letters as follows:

     STARW
     BCDEF
     GHIJK
     LMNOP
     QUVXY
     Z
     

   • then read off by columns to get the translation alphabet

     Plain:  ABCDEFGHIJKLMNOPQRSTUVWXYZ
     Cipher: SBGLQZTCHMUADINVREJOXWFKPY
     

   • can then use this to en/decrypt, eg.

     Plaintext:  I KNOW ONLY THAT I KNOW NOTHING
     Ciphertext: H UINF NIAP OCSO H UINF INOCHIT
     

5. Cryptanalysis of General Monoalphabetic Ciphers
   • as with a caesar cipher, analyse using frequency counts
   • but instead of being shifted, the letters are jumbled
   • hence must identify what each letter has been mapped to
   • made much easier if word boundaries have been left in
   • since know single words are 'A' or 'I'
   • common 3 letter words are "THE" and "AND"
   • otherwise just use common double and triple letters
   • also use knowledge of rarely used letters
6. Cryptanalysis of General Monoalphabetic Ciphers cont.
   • can even recover the original keyword
   • since its construction often leaves successive letters
   • the column width apart
   • eg. in the above example, if have recovered the mapping:

     Plain:  ABCDEFGHIJKLMNOPQRSTUVWXYZ
     Cipher: SBGLQZTCHMUADINVREJOXWFKPY
              ^ *   ^ *  ^ *  ^ *  ^ *
     

   • see pattern "BCDEF" and "LMNOP"
   • can then reconstruct the table
   • and recover keyword "STARW"

     nb. the "BCDEF" pattern is marked with ^, "LMNOP" with *. Also notice the change in jump from 6 to 5 after the 2nd letter, gives away that first column is longer. Main idea is to line up successive letters in the same row, filling columns out as necessary, and remembering that some letters are missing, because they're up in the keyword. Once have grid written out, then can read keyword off the top row. This technique can be used even if have only found a partial mapping - and may well then give some or all of the rest of the mapping.

Entropy and Unicity Distance

1. Entropy
   • Claude Shannon a key researcher
   • important results about information content of languages in 1949
   • defined entropy
   • of a message H(X) is related to the number of bits needed to encode the message X
   • wont exceed log2 n bits for n if have n possible randomly chosen messages
   • since if messages random, best can do is give each a (binary) number
   • if messages aren't random, can do better with variable length coding, cf compressing messages
2. Rate of Langauge
   • denotes the average number of bits in each character for messages of length k

     D = H(M)/k 

   • rate of English is about 3.2 bits/letter

     Claude Shannon gave us the theoretical foundations to explain language redundancy, and is regarded as the father of the field of "information theory". Entropy provides a definition of the "amount of information" needed to encode a message optimally. If all messages are equally random (which natural language messages aren't!), then the best you could do is to give each message a number. And the entropy is then the number of bits needed to represent those numbers in binary. eg. if you had 32 equally likely messages, you'd need 5 bits (gives you 32 numbers). 64 messages would need 6 bits, etc. If messages aren't random, then you can use a variable length coding to do better. eg. lets say most of the time the message is "all is okay". You could send that as a single bit message '0'. then lets say if all's not well, you have 15 possible things that're wrong, so send them as '1XXXX' a 5 bit message. But if most of the time the message is just '0', then on average, the message size is quite small, rather than being always 4 bits, as it would have been if they're all random. Its this behaviour that is also used to compress files on information. If you sample large amounts of a language, eg English, and work out an optimal coding for it, and then determine the average number of bits per letter using it, you get a figure of 3.2 bits/letter.

3. Unicity Distance
   • also defined by Claude Shannon
   • as a quantatative measure for a cipher of:
     • the security of a cipher (must not be too small)
     • the amount of ciphertext N needed to break it

       N = H(K)/D 

       where H(K) is entropy (amount of info) of the key,
       and is D the rate of the language used (eg 3.2 for English)

     Unicity Distance is a measure of about how much ciphertext is theoretically needed to break a cipher (formally the minimum message length that forces the key equivocation (uncertainty) to 0). It can be roughly approximated by dividing the entropy of the key (which had better be randomly chosen!) by the rate of the language.

4. Unicity Distances of a Caesar Cipher

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

   • hence theoretically only need 2 letters to break

     Applying this in practice: A Caesar cipher has 26 keys, which needs approx 4.7 bits / 3.2 = 1.5 roughly. Intuitively, if you've guessed 'E', then you don't need much else to verify, since all letters are just shifted.

5. Unicity Distances of a General Monoalphabetic Substitution Cipher

   • N = H(K)/D = log2 n!/D = log2 26!/3.2
         = 26 log2 (26/e)/3.2 = 27.6 

   • hence theoretically only need 27 or 28 letters to break

     A General cipher has 26! keys, and using an approximation for log226! we get the formula shown, and the value of 27.6. Intuitively, must see most of the 26 letters, since they've been shuffled.

Summary

1. Summary
   • have discussed:
   • classic substitution ciphers
   • monoalphabetic ciphers: caesar, general
   • language redundancy and its use in cryptanalysis
   • entropy and unicity distances

Exercises

1. Exercises
   1. encrypt and then decrypt by hand, the text below using a general monoalphabetic cipher with a key of "NIFTY":

      the cat only grinned when it saw
      alice it looked good natured she
      thought still it had very long claws
      and a great many teeth so she felt
      that it ought to be treated with respect
      

Additional References