Cryptography - Lecture 5 - Classical Transposition Ciphers

Objectives

Preliminary Reading

Lecture Content

Using the Krypto Program

1. Using the Krypto Program
   • a program to help compute and solve simple substitution and transposition ciphers
   • originally written by Michael Coyne in 80's in C.
   • rewritten in Java with both command-line and GUI interfaces
   • can en/decrypt Vigenère, Beauford and Variant-Beauford ciphers
   • as well as Row and Column Transpositions
   • can compute IC's and frequency counts for letters or groups
   • can graph letter frequencies
   • can display text as is or in fixed sized letter groups
   • an extremely useful tool for analysing classical ciphers
2. Command-line Interface
   • krypto [file] (Unix version)
   • jkrypto [file] (Java version)
   • repeatedly prompted to enter a command (? to list)
   • note that jkrypto has a slightly different set of commands
3. GUI Interface
   • a new GUI interface has been supplied with this version
   • it provides a button and menu access to the various options
   • used if the program is run as jkrypto -g [file]

Transposition Ciphers

1. Transposition Ciphers
   • now consider classical transposition or permutation ciphers
   • these hide the message by rearranging the letter order
   • without altering the actual letters used

     Transposition Ciphers form the second basic building block of ciphers. The core idea is to rearrange the order of basic units (letters/bytes/bits) without altering their actual values.

2. Scytale cipher
   • an early Greek transposition cipher
   • a strip of paper was wound round a staff
   • message written along staff in rows, then paper removed
   • leaving a strip of seemingly random letters
     
   • not very secure as key was width of paper & staff

     Works by spacing adjacent letters of the message at intervals down the strip of paper.

3. Reverse (Mirror) cipher
   • write the message backwards

     Plain:	I CAME I SAW I CONQUERED
     Cipher:	DEREU QNOCI WASIE MACI
     

4. Rail Fence cipher
   • write message with letters on alternate rows
   • read off cipher row by row

     Plain:	I A E S W C N U R D
              C M I A I O Q E E 
     Cipher:	IAESW CNURD CMIAI OQEE
     

5. Geometric Figure
   • write message following one pattern and read out with another Sinkov, Fig 20, p143
6. Key Concept for Transposition Ciphers
   • in a transposition cipher the key idea is that you:
   • write the message out in columns according to some rule
   • read the letters off to form the ciphertext according to another rule
   • key used to find order to: read off the cipher, write in the plaintext, or both

     All of the above are examples of how we can rearrange our basic units, here letters. Each has a rule saying how this is done, with the key specifying the particular variant of the rules used.

Row Transposition ciphers

1. Row Transposition ciphers
   • group the message and shuffle letters within each group
   • more formally write letters across rows
   • then reorder the columns before reading off the rows
   • always have an equivalent pair of keys (Read off vs Write In)

     Plain:	 THESIMPLESTPOSSIBLETRANSPOSITIONSXX
     Key (R): 2 5 4 1 3	
     Key (W):                4 1 5 3 2 	
     
              T H E S I	S T I E H 	
              M P L E S	E M S L P 	
              T P O S S	S T S O P 	
              I B L E T	E I T L B 	
              R A N S P	S R P N A 	
              O S I T I	T O I I S 	
              O N S X X	X O X S N 
     Cipher:	 STIEH EMSLP STSOP EITLB SRPNA TOIIS XOXSN
     

     Example - Davies p26 Fig 2.14

     Note that the Krypto program and Sinkov use different conventions as to what sort of key is used (read off vs write in), so take care not to be confused. Specifically note that krypto uses a read-off key.

2. Using a Row Transposition cipher
   • can use a word, with letter order giving sequence, rather than numbers
   • to specify the order used to write in the plaintext; or read off the cipher

     
     Plain:	 ACONVENIENTWAYTOEXPRESSTHEPERMUTATION
     Key (W): C O M P U T E R
     Key (W): 1 4 3 5 8 7 2 6
      	
              A N O V I N C E
              E W T A O T N Y
     	 E R P E T S X S
              H E P R T U E M
              A O I N Z Z T Z
     
     Cipher:  ANOVI NCEEW TAOTN YERPE TSXSH EPRTU EMAOI NZZTZ
     

     Example - Davies p26 Fig 2.15
3. Example Row Transposition
   • using (read out) key sorcery encipher the following:

     Key(R):	sorcery => 6 3 4 1 2 5 7
     laser beams can be modulated to carry more intelligence than radio waves
     ==>
     erasb lecam snabd umole atoed ctamo ryrre elntl iicee ntgha dnria oesav w
     

4. Decryption of a Row Transposition cipher
   • consists of:
     • writing the message out in columns
     • reading off the message by reordering columns
     • (use T command in krypto, uses read out keys)
   • hint - its not a good idea to leave message in groups matching the size of your key!!!
5. Cryptanalysis of Row Transposition ciphers
   • a frequency count will show a normal language profile
   • hence know have letters rearranged
   • basic idea is to guess period, then look at all possible permutations in period, and search for common patterns (eg t command in krypto)
   • use lists of common pairs & triples & other features
   • if row transposition then letters rearranged within row
   • and must be same rearrangement for each group of letters
   • ability to anagram words helps a lot here
6. Example Cryptanalysis
   • given: LDWOE HETTS HESTR HUTEL OSBED EFIEV NT
   • try successive periods, looking at all rearrangements of first few letters
   • 2: LD WO EH ET TS HE ST RH UT EL OS BE DE FI EV NT - NO
   • 3: LDW OEH ETT SHE STR HUT ELO SBE DEF IEV NT - NO
   • 4: LDWO EHET TSHE STRH UTEL OSBE DEFI EVNT - NO
   • 5: LDWOE HETTS HESTR HUTEL OSBED EFIEV NT - NO
   • 6: LDWOEH ETTSHE STRHUT ELOSBE DEFIEV NT - YES!!!
   • note 2nd group suggests "THESET" or "TTHESE"
   • 8 keys could give these patterns
   • key 5,6,1,4,2,3 recovers English text:
   • WEHOLD THESET RUTHST OBESEL FEVIDE NT or
   • WE HOLD THESE TRUTHS TO BE SELF EVIDENT
   • Example - Seberry 1/e p67-8

     For each possible length have to try all ways of permuting that sized block, to see if we can recover English text. For 2 there's just 1 possibiity DL OW clearly wrong. For 3 clear that LDW cannot make a word. For 4 have 16 ways, but none work. For 5 have 5! ways, but anagramming first two blocks just can't make words. Come to 6, and see that 2nd block suggests some possibilities. List the 8 permutations that could give either, and finally find the one that decrypts the ciphertext.

7. Unicity Distance for Row Transposition ciphers
   • compute unicity distance to determine complexity of the cipher
   • given blocks of period d, there are d! keys, hence

     N = H(K) / D
       = log2 d! / D
       = d log2(d/e) / 3.2
     

     d	N
     3	0.12804
     4	0.66877
     5	1.31885
     6	2.05608
     7	2.86579

   • this shows that the theoretical security is not high

Summary

1. Summary
   • have discussed:
   • concept of transpostion ciphers
   • Row Transposition ciphers

Exercises

1. Exercises
   1. encrypt and then decrypt by hand, the text below using a row transposition cipher 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:

      onind aseni huaot iiret vhsea usies aadrw ginon wnfee turip
      onocs iucnr ofgmr tecrn alavj osaum etnrm vpaoi ncloa cuval
      oongl ssimt tnooi girtn cehta tviyi rasey eisnd nstti eehnd
      yespl lpoau aetrd haeos blued eawor spfso ebidl enarg yhtse
      nyaci seria ygnfl uereq utnrs eafac odnlv iaccn mrtoe rsrea
      ucorc wniig lhtoc odufs kmseo lnaad av
      

Additional References