Cryptography - Lecture 6 - Classical Transposition and Product 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
  

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
  

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
  

6. 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

7. 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

8. 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

9. Cryptanalysis

• attacking these cipher depends on column and row rearrangement
• with much trial and error

10. 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

11. 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

12. 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

13. 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     

14. 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

15. Summary

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

16. 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