Cryptography - Lecture 5 - Classical Transposition Ciphers

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]

4. Transposition Ciphers

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

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

6. Reverse (Mirror) cipher

write the message backwards

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

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

8. Geometric Figure

write message following one pattern and read out with another Sinkov, Fig 20, p143

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

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

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

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

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

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

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

16. 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
  = log₂ d! / D
  = d log₂(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

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

17. Summary

have discussed:
concept of transpostion ciphers
Row Transposition ciphers

18. Exercises

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

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

[Back to CCS3 Lectures]

Lawrie.Brown@adfa.edu.au / 6 Feb 2001