Cryptography - Lecture 6 - Classical Transposition and Product Ciphers

Objectives

Lecture Content

Block (Columnar) Transposition Ciphers

1. Block (Columnar) Transposition ciphers
   • another class of transposition ciphers
   • message is written in rows, but read off by columns
   • order of columns read off is given by key
2. Using a Block (Columnar) Transposition cipher
   • can use B command in krypto to en/decrypt
   • for ease of recovery may insist matrix is filled

     Key(R): s o r c e r y        s o r c e r y
     Key(R): 6 3 4 1 2 5 7        6 3 4 1 2 5 7
     
             l a s e r b e        l a s e r b e
             a m s c a n b        a m s c a n b
             e m o d u l a        e m o d u l a
             t e d t o c a        t e d t o c a
             r r y m o r e        r r y m o r e 
             i n t e l l i        i n t e l l i
             g e n c e t h        g e n c e t h
             a n r a d i o        a n r a d i o
             w a v e s            w a v e s q r
     
     matrix  incomplete           complete
     

   • giving ciphertext (by reading off cols 4, 5, 2, 3, 6, 1, 7)

     ecdtm ecaer auool edsam merne nasso dytnr
     vbnlc rltiq laetr igawe baaei hor
     

     Note that the left example has an incomplete matrix, which means that manual decrpytion requires a bit more care in filling in the columns, but which gives a more secure cipher, since there's no hints for the cryptanalyst as to the size. The right example has been filled with rubbish letters "qr" at the end, making recovery easier, but also leaving a hint as to the size, since 63 letters only divide up as 7x11 or 11x7 (ie a keylength of 7 or 11).

3. Decryption of a Block (Columnar) Transposition cipher
   • calculating the number of rows used
   • (by dividing message length by key length)
   • writing out message down columns in order given by key
   • reading off original message across rows
   • Example - Sinkov p148 #74 - decipher using key ROYALTY

     TNGTH CYIIL HEIHP ANCAA HGROU FOAEM ITELS OIPIN DSRRO EARER
     ANEEE FTILM SEAEA NSCES ONE
     

     When drawing the blank grid out to fill in, if the key size doesn't divide exactly into the number of letters, must be careful to shorten the last columns filled appropriately

4. Cryptanalysis of Block Transposition ciphers
   • know must be a transposition, guess perhaps a block transposition
   • try to guess size of matrix by looking at factors of message length
   • otherwise simply have to try each size in turn
   • write message out in columns
   • look for ways of reordering pairs of columns to give common pairs or triples (very much trial & error)
   • more generally, use automated tool to try all permutations
   • eg. b command in krypto
   • and can suggest displaying only permutations matching a pattern
   • pattern could be guessed word
   • or could just assume have enough text that common words occur
   • eg. the and (preferably repeated)
5. Example Cryptanalysis
   • given:

     HADVF NITHB CTSBE HTEGE SRYRN AMINR IAIST TETOO ETSAN GLIET
     GTDRS CYGAI TANAH FLNAU ETIEM EOHUE AELYR IIS
     

   • assuming have failed attempts as a row transposition
   • so guess may be a column
   • try searching possible key sizes, looking for THE
   • try 2, use command b 2 /THE - none match
   • try 3, use command b 3 /THE - none match
   • try 4, use command b 4 /THE - 2 matches, both rubbish
   • try 5, use command b 5 /THE - 1st match gives answer

     -> b 5 /THE
     THEGR EATES TDISC OVERY OFMYG ENERA TIONI STHAT AHUMA NBEIN
     GCANA LTERH ISLIF EBYAL TERIN GHISA TTITU DES
     Accept (y/n/q)?y
     

     Note that must be careful with case - here the ciphertext is in uppercase, so must the search string. When the right permutation is found, krypto doesn't tell you the key. Knowing the answer, you have to manually write the message out in columns and work out the permutation used. Also note that if you have more ciphertext, will get lots of flase matches on a single word like THE. Really need to search for 2 or more. This means using regular expressions for the search string, rather than just a simple word, like: /the.*the or /the.*and (krypto only).

Nihilist & Diagonal Ciphers

1. Nihilist ciphers
   • more complex transposition cipher using both row and column transpositions
   • write message in rows in order controlled by the key (as for a row cipher)
   • then read off by rows, but in order controlled by the key, this time written down the side
   • uses a period of size the square of the key length
2. Diagonal Cipher
   • for more complexity can vary readout algorithm
   • write message out as per Nihilist Cipher
   • diagonal cipher reads out on fwd diag (/) in alternate directions
   • (up diag, down diag etc), ie a zig-zag read out
3. Examples

   Plaintext: NOWISTHETIMEFORALLGOODMEN
   
   Key (W):          L E M O N
                     2 1 3 5 4
              L 2    O N W S I
              E 1    H T E I T
              M 3    E M F R O
              0 5    L A L O G
              N 4    D O M N E
   
   Nihilist Cipher: HTEIT ONWSI EMFRO DOMNE LALOG
   
   Diagonal Cipher: ONHET WSEML DAFII TRLOM OOGNE
   

   Example - Davis Fig2.16 p27
4. Cryptanalysis
   • attacking these cipher depends on column and row rearrangement
   • with much trial and error

Product ciphers

1. Increasing Cipher Security
   • ciphers based on just substitutions or transpositions are not secure
   • have seen how these can be attacked
   • because they do not sufficient obscure the underlying language structure
   • hence consider using several ciphers in succession to make harder, but:
     • two substitutions are really only one more complex substitution
     • two transpositions are really only one more complex transposition
     • but a substitution followed by a transposition makes a new much harder cipher
2. Product ciphers
   • are substitution-transposition combinations chained together
   • in general are far too hard to do by hand
   • however one famous product cipher ADFGVX cipher was used in WW1
   • more generally, wider used use had to wait for the cipher machines
3. ADFGVX Product Cipher
   • named since only letters ADFGVX are used
   • chosen since have very distinct morse codes
   • used by the German's and broken by the English in WW1
   • see Kahn pp339-350 or Singh pp103-104
   • uses a fixed substitution table to map each plaintext letter to a letter pair (row-col index)
   • then uses a keyed block transposition to split letter pairs up
   • ciphertext then written in blocks and sent
4. ADFGVX Substitution Table

   
   \\    A     D     F     G     V     X     
   A     K     Z     W     R     1     F     
   D     9     B     6     C     L     5     
   F     Q     7     J     P     G     X     
   G     E     V     Y     3     A     N     
   V     8     O     D     H     0     2     
   X     U     4     I     S     T     M     
   

5. Example ADFGVX Encryption

   Plaintext:	PRODUCTCIPHERS
   	
   Intermediate Text:
   		FG AG VD VF XA DG XV
   		DG XF FG VG GA AG XG
   
   Keyed Block Columnlar Transposition Matrix
   
   D     E     U     T     S     C     H        Key                     
   2     3     7     6     5     1     4        Sorted Order            
   F     G     A     G     V     D     V                                
   F     X     A     D     G     X     V                                
   D     G     X     F     F     G     V                                
   G     G     A     A     G     X     G                                
   
   Ciphertext:	DXGX FFDG GXGG VVVG VGFG CDFA AAXA
   

Summary

1. Summary
   • have discussed:
   • concept of transpostion ciphers
   • Row Transposition ciphers
   • Block (Columnar) Transposition ciphers
   • Nihilist & Diagonal Ciphers
   • Product ciphers

Exercises

1. Exercises
   1. encrypt and then decrypt by hand, the text below using a block (column) transposition with a key of SNEAKY:

      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
      

   2. break the following ciphertext:

      sgsog gnesh otrtb alvyi tayev
      hagwl hyine aieon moeai etddi
      bmtgd eurni ermhl wbeet rtlth
      dalwn rraos bidts ebele osmha
      

   3. encrypt and then decrypt by hand, the text below using the ADFGVX cipher with a key of SNEAKY:

      to see victory only when it is
      within the ken of the common herd
      is not the acme of excellence
      

Additional References