Cryptography Tutorial - Transposition Ciphers


























  

Cryptography >
Transposition Ciphers (45 min.) 
     




Objectives:
1) Understand what
Transposition Ciphers are and how they work.
2) Encrypt using the
Reverse and the Rail Rence Cipher and Fractionation
Systems. 
3) Learn how to break
Transposition Ciphers.
Classical ciphers can be grouped into two categories:
"Transposition Ciphers" and "Substitution Ciphers". I will first introduce
you to the Transposition Ciphers. 
Definition: In Transposition Ciphers plain letters are
simply rearranged. 
 
Example 1: Encode "MEETMEATNOON" below
and explain how this particular Transposition Cipher
works: 

Related web
sources:
Yahoo's Encryption & Security
Britannica.com
Dictionary.com
Glossary
PBS
Online
Introduction to Cryptography
Enigma and the Codebreakers
Enigma History
Enigma Emulator
 
 
 





Plain text
 
Cipher text









 
 



 
 


Cipher text
 
Plain text








 
 



Notice that
MEETMEATNOON becomes NOONTAEMTEEM. I am sure you saw that the
letters were simply reversed. Notice that no letter was replaced,
they were simply rearranged. This cipher is called the "Reverse
Cipher". Reversing the letters is the simplest example of a
transposition cipher: 


 
Exercise
1: Use the Reverse
Cipher to encode "A man a plan a canal Panama" by hand. amanaplanacanalpanamaExercise 2: Decode the ciphertext
"yhpargotpyrc".  cryptography


 


Example 2: The Rail Fence Cipher was used
by the Spartans to send messages to Greek warriors. Here, the plaintext is
staggered between rows and the rows are then read sequentially to give the
cipher. The key is the number of rows used to encode. In example, a rail
fence with two rows turns the message      "transposition ciphers can
easily be broken"                           into






t
a
s
o
i
i
n
i
h
r

c

n
a
i
y
e
r
k
n

  r
 n
 p
  s
  t
 o
 c
 p
  e
  s
  a
  e
  s
  l
  b
  b
  o
  e

and creates the cipher text            
"tasoiinihrcnaiyerknrnpstocpesaeslbboe"
 Verify it below.
Afterwards, encode using the keys 3, 4 and 5. 










(Avoid blanks)

Select key


 




Exercise 3: Use the
Rail Fence Cipher with key 2 to encode
"A man a plan a canal" by hand. 
aaalncnlmnpaaaa

Exercise 4: Test various keys to break
"tnotnprrlsaierssichseailprapioieacscchs". "transpositionciphersareclassicalciphers" 
with key 3.  

Exercise
5: This
exercise leads to the weakness of transposition ciphers.
Independent of how we transpose the plain letters, we
only shuffle and never replace any letters. Thus, breaking the
above transposition cipher is not difficult if only we try the
possible transposition. Certainly, a computer can be a great
assistance.  However, how could you find out that a
cipher was encoded using transpositions? What property of the
original text remains intact despite shuffling the letters.
The answer to this question touches a very important tool in
cryptoanalyzing ciphers messages. Thus, think thoroughly.
 The letter
frequencies don't change. Therefore, we expect the cipher
letter frequencies to be close to the letter frequencies of
the English language.  

The Spartans used another encryption method that is
similar to the Rail Fence Cipher: It is called "Skytale
Cipher". In the 5th century B.C., the Spartans wrapped a
thin sheet of papyrus around a staff (skytale). Messages were
written down the length of the staff, and the papyrus was
unwrapped. In order to read the message, the papyrus had to be
wrapped around a staff of equal diameter. Without the right
staff, it would be difficult to decode the message using the
techniques available at that time. To further increase the
secrecy of the message, the messenger placed the staff inside
his belt.   
 


 
1) How can Transposition Ciphers be
broken? 
In order to encrypt a message using the
Transposition Cipher, the letters can be shuffled without any
system. Otherwise, the recipient has no idea how to decrypt the
message. However, by choosing a system to rearrange the letters it
allows an eavesdropper to be successful with his work. Testing many
conceivable rearrangement will eventually the original
message. 
Step 1: (Realization that the
ciphertext was encrypted using a transposition cipher.) Computing
the relative frequencies of the cipher letters reveals that cipher
letters occur with the same frequency as plain letters. An
eavesdropper realizes that plain letters were simply
rearranged. 
Step 2: Transposition ciphers
are broken by testing possible rearrangements. First, try to read
the cipher text backwards. If that does not yield the plain text
then try the rail fence of depth two, then of depth three, then of
depth four, etc. If that does not yield the plain text check if
two consecutive letters were switched. With today's computer power
possible transpositions can be checked quickly. In conclusion: the
transposition ciphers don't offer any
security.    
 
 
2) How can the Security of
Transposition Ciphers be increased? 
The Rail Fence is the simplest example
of a class of transposition ciphers called "Route Ciphers". These
were quite popular in the early history of cryptography. Generally,
in Route Ciphers the elements of the plaintext (here single letters)
are written on a pre-arranged route into a matrix agreed upon by the
sender and the receiver. The introductory example uses a 2 (rows) by
19 (columns) matrix in which the plaintext is entered sequentially
by columns, the encryption route is therefore to read the top row
and then the lower.
To gain an acceptable level of
security, the route would have to be more complicated than the one
in this example. One form of transposition that has enjoyed
widespread use relies on identifying the route by means of an easily
remembered keyword. Say we choose the keyword "cat" a matrix can be
written out like the one below. We choose the letter "x" to fill the
remaining spots in the matrix.



C
t
n
o
t
n
p
r
a
e
o
n
s
y

A
r
s
s
i
c
h
s
n
b
k
e
i
x

T
a
p
i
o
i
e
c
b
r
e
a
l
x
The order in which the rows are read
out to form the ciphertext is determined by the alphabetical order
of the letters in the keyword "cat".
This matrix therefore yields the
ciphertext:        
"rssichsnbkeixtnotnpraeonsyapioiecbrealx"
 
To decode, the recipient simply fills 3
rows evenly with the ciphertext according to the alphabetical order
of the letters in the shared keyword "cat". 
The security of transposition ciphers
can be further improved by re-encrypting the resulting cipher using
another transposition. Because the product of the two transpositions
is also a transposition, the effect of multiple transpositions is to
further increase the complexity of the route through the matrix.
However, although the plaintext gets more and more shuffled the
plaintext letters are still part of the ciphertext and sufficient
patience and experience in cryptoanalysis will eventually yield the
original plaintext. 
In modern cryptography transposition
cipher systems serve mainly as one of several methods used as a step
in forming a product cipher.
 
 
3) Fractionation Systems: Further
Improving the Security Level 
In fractionation systems, letters are
both substituted (which we will study in detail in the next lesson)
and transposed yielding a superencryption. First, the plain letters
are substituted by selected letters (commonly pairs of
letters are used, in which case the cipher is called a "biliteral
cipher"). Secondly, such letters are then super-encrypted by a
transposition. Let's study an example of a Fractionation
System.
 







 

A

D

F

G

V

X


A
o
r
a
n
g
e


D
b

c

d

f

h

i


F

j

k

l

m

p

q


G

s

t

u

v

w

x


V

y

z

0

1

2

3


X

4

5

6

7

8

9

Example1:
(ADFGVX Cipher) One of the most famous field ciphers ever was
a fractionation system - the ADFGVX Cipher which
was employed by the German Army during the first world war.
This system was so named because it used a 6 by 6 matrix to
substitution-encrypt the 26 letters of the alphabet and 10
digits into pairs of the symbols A, D, F, G, V and X. The
variable setup of the matrix is guaranteed through the choice
of a keyword (here orange) that precedes the remaining letters
and digits. The resulting bi-literal cipher is only an
intermediate cipher, it is then written into a rectangular
matrix and transposed to produce the final cipher which is the
one which was transmitted.
For instance, let's encrypt
"cryptography" using the key word "orange". The first letter "c"
becomes "DD" as the starting letters of the row and the column in
which "c" appears. Similarly, the next letter "r" turns into "AD",
etc. 



 

A

D

F

G

V

X


A
o
r
a
n
g
e


D
b

c

d

f

h

i


F

j

k

l

m

p

q


G

s

t

u

v

w

x


V

y

z

0

1

2

3


X

4

5

6

7

8

9
 




Plaintext:
c
r
y
p
t
o
g
r
a
p
h
y


Ciphertext:
DD
AD
VA
FV
GD
AA
AV
AD
AF
FV
DV
VA
This intermediate ciphertext then fills
the columns (left to right) of a transposition matrix using the
keyword "water". Since "water" consists of 5 letters the matrix
contains 5 rows. Note that the matrix is filled up with AA at the
bottom right.  




w
5
D
A
A
D
D


a

1

D
F
A
A
V


t

4

A
V
A

F

V


e

2

D
G
V

F

A


r

3

V
D
A

V

A
The final cipher is read as rows based
on the alphabetical order of the letters of the key
"water": 
         
     
"DFAAVDGVFAVDAVAAVAFVDAADD".
 
To decode, the recipient sets up the
two matrices based on the two keywords to first undo the
transposition and to finally undo the ADFGVX-substitution. Although
this superencryption offers more security, it can be broken in
steps. First, the ADFGVX - Substitution Cipher has to be deciphered
- I will show you how on the following  "Substitution Cipher"
page. Secondly, the remaining transpositions can be undone by
testing many possible transpositions. 
 

Exercise
6:  Superencrypt "Steganography" by
using the keywords "math" for the ADFGVX substitution (a matrix with
4 rows) and "sand" for the transposition matrix. "DDDGAVAFGFGDGAADFDAAAGDAFGFV"





 top

back 
next