Week 2

Week2
Playfair cipher. The best-known multiple-letter encryption cipher is the Playfair, which
treats diagrams in the plaintext as
ciphertext diagrams.
single
units
and
translates
these
units
into
The Playfair algorithm is based on use of a 5x5 matrix of letters constructed using a
keyword. Here is an example:
M
C
E
L
U
O
H
F
P
V
N
Y
G
Q
W
A
B
I/J
S
X
R
D
K
T
Z
In this case, the keyword is monarchy. The matrix is constructed by filling in the letters of
the keyword from left to right and from top to bottom and then filling the remainder of
the matrix with the remaining letters in alphabetic order. The letters I and J count as
one letter. Plaintext is encrypted two letters at a time, according to the following rules:
1. Repeating plaintext letters that would fall in the same pair are separated with a
filler letter, such as x, so that balloon would be enciphered as ba lx lo on .
2. Plaintext letters that fall in the same row of the matrix are each replaced by the
letter to the right, with the first element of the row circularly following the
last. For example, ar is encrypted as RM.
3. Plaintext letters that fall in the
same column each replaced by the letter
beneath, with the top element of the row circularly following the last. For example,
my is encrypted as CM.
4. Otherwise, each plaintext letter is replaced by the letter that lies in its own row
and the column occupied by the other plaintext letter. Thus, hs becomes BP and ea
becomes IM (or JM, as the encipherer wishes).
5. The Playfair cipher is a great advance over simple monoalphabetic ciphers.
Identification
of individual diagrams is difficult in Plairfair cipher, since there
26 × 26 = 676 diagrams. The relative frequencies of individual letters exhibit a
much greater range than that of diagrams, so identification
difficult.
of
letters
is
more
For these reasons, the Playfair cipher was for a long time considered
unbreakable. It was used as the standard field system by the British Army in
World War I and still enjoyed considerable in the U.S. Army and other allied forces
during World War II.
Example
Plain:
re
Pe
at
Plain:
at
Sa
me wo
ar
Es
ep
Cipher:
Cipher:
Plain:
MK LF RS
RS
XB CL
Cypher: RM IL
The Playfair
Identification
cipher
of
is
FL
a
individual
in
GA
VN
er
gp
la
in
te
Xt
le
tx
te
rs
th
ul
df
al
li
Nt
he
sa
me pa
Ir
ed
wi
th
Af
il
le
FQ
MU HK MS SE
at
KM RS
great
SM GA LK ZS
KS
advance
XG
LK
RQ CF XB CL
PD OI
over
UL SZ
IS
R
AT PD
SO KA
UL M
simple monoalphabetic
ciphers.
diagrams is difficult in Plairfair cipher, since there
26 × 26 = 676 diagrams. The relative frequencies of individual letters exhibit a much
greater range than that of diagrams, so identification of letters is more difficult. For
these reasons, the Playfair cipher was for a long time considered unbreakable. It was
used as the standard field system by the British Army in World War I and still
enjoyed considerable in the U.S. Army and other allied forces during World War II.
Despite this level of confidence in its security, the Playfair cipher is relatively easy to
break because it still leaves much of the plaintext structure. A few hundred letters of
ciphertext are generally sufficient.
Hill cipher.
Hill cipher was developed by its inventor Lester Hill in 1929. Hill cipher is known to be the
first polygraphic cipher. The method is based on linear matrix transformation of a message
space. Given a plaintext message 𝑝 = (𝑝1 , 𝑝2 , … ) where 𝑝𝑖 is a letter in some alphabet and
invertible 𝑚 × 𝑚
matrix 𝐻, Hill cipher represents 𝑝𝑖 by numeric value 𝑥𝑖 ∈ 𝑍𝑛 (𝑍𝑛 =
{0,1, … , 𝑛 − 1}) and encrypts plaintext as 𝑦 = 𝐻 ∙ 𝑥 (mod 𝑛), where 𝑥 and 𝑦 are plaintext and
ciphertext column vectors. Similarly, 𝑦 is decrypted as 𝑥 = 𝐻 −1 ∙ 𝑦 (mod 𝑛), where 𝐻 −1 is the
inverse of 𝐻. That is, 𝐻 ∙ 𝐻 −1 = 𝐻 −1 ∙ 𝐻 = 𝐼 holds, where 𝐼 is the identity matrix.
The following exemplifies Hill cipher for 𝑛 = 26,
6 24 1
8
5 10
𝐻 = �13 16 10�, 𝐻 −1 = �21 8 21�.
20 17 15
21 12 8
The plaintext 𝑥 = (𝐴𝐴𝐴) = (0 2 19) is encrypted as 𝑦 = 𝐻 ∙ 𝑥 (mod 26) = (15 14 7) = (𝑃𝑃𝑃).
Likewise, the ciphertext 𝑦 = (15 14 7) is decrypted as 𝑥 = 𝐻 −1 ∙ 𝑦 (mod 26) = (0 2 19) =
(𝐴𝐴𝐴).
Hill cipher is vulnerable to cryptanalysis. The cryptanalyst usually sits in tight loop and tries
to possess the plaintext of some messages and the corresponding ciphertext of those
messages to deduce the key. If cryptanalyst succeeds with gaining access to the flow of
messages then he can easily decrypt any new messages encrypted with the same key. The
system can be obviously broken, knowing only 𝑚distinct plaintext and ciphertext pairs (𝑥, 𝑦)
and by computing 𝐻 = 𝑌 ∙ 𝑋 −1 (mod 𝑛), where 𝑋 and 𝑌 are the matrices composed of 𝑚
columns of 𝑥 and 𝑦, respectively. Whenever 𝑋 is invertible the opponent can obviously
compute the unknown key as 𝐻 = 𝑌 ∙ 𝑋 −1 (mod 𝑛) and consequently break the cipher. If the 𝑋
is not invertible then cryptanalyst keeps on collecting 𝑚 plaintext and ciphertext pairs until
the resulting matrix is invertible. When 𝑚 is unknown, cryptanalyst might try the procedure
for 𝑚 = 2,3,4 until the key is found.
The affine Hill cipher was proposed to overcome this drawback. The affine Hill cipher is a
secure variant of Hill cipher in which the concept is extended by mixing it with an affine
transformation. Similar to the Hill cipher the affine Hill cipher is polygraphic cipher,
encrypting/decrypting 𝑚 letters at a time. Given key matrix 𝐻 and vector 𝑉, in affine Hill
cipher the encryption expression is represented by 𝑦 = 𝐻 ∙ 𝑥 + 𝑉 (mod 𝑛). Similarly, the
decryption is performed by 𝑥 = 𝐻 −1 ∙ (𝑦 − 𝑉)(mod 𝑛). The following example illustrates the
way encryption and decryption is performed in affine Hill cipher. The following example
exemplifies affine Hill cipher. Let 𝑛 = 26,
6 24 1
8
5 10
5
𝐻 = �13 16 10�, 𝐻 −1 = �21 8 21� and 𝑉 = �0�.
20 17 15
21 12 8
7
The encryption 𝑥 = (𝐴𝐴𝐴) = (0 2 19)is possessed by
6 24 1
0
20
5
𝑦 = 𝐻 ∙ 𝑥 + 𝑉 (mod 26) = �13 16 10� � 2 � + �0� (mod 26) = �14�.
20 17 15 19
14
7
Likewise, the decryption is performed as follows:
0
8
5 10
15
𝑥 = 𝐻 −1 ∙ (𝑥 − 𝑉) (mod 26) = �21 8 21� ∙ �14� (mod 26) = � 2 �.
19
21 12 8
7
Suppose Alice chooses affine Hill cipher to send confidential message to Bob. Firstly, she
selects a pair (𝐻, 𝑉) to encrypt the plaintext. Then she sends ciphertext as well as (𝐻, 𝑉) to
Bob. When Bob receives ciphertext and a pair (𝐻, 𝑉) he creates 𝐻 −1, and then decrypts the
ciphertext with (𝐻 −1 , 𝑉).
In 2000, Saeednia proposed an interesting modification of Hill cipher. The main idea behind
of his algorithm is to modify the key matrix each time Hill cipher is implemented. Encrypting
a message by a one-time used matrix would make the algorithm more secure compared to the
original Hill cipher and affine Hill cipher.
Assume Alice decides to send confidential message of size 𝑚 × 𝑠 to Bob, and she chooses
Saeednia’s algorithm to encrypt the message. Then she firstly selects random permutation 𝜋
of size 𝑚 and creates 𝑚 × 𝑚 permutation matrix 𝑃𝜋 by permuting the rows of same size
identity matrix. Such a matrix is always row equivalent to an identity matrix. Then she creates
its inverse 𝑃𝜋−1 by permuting the columns of the identity matrix. Likewise, 𝑃𝜋−1 is column
equivalent to the row-permuted matrix. After that, she creates one-time used matrix 𝐻𝜋 from
the key matrix 𝐻 as 𝐻𝜋 = 𝑃𝜋−1 ∙ 𝐻 ∙ 𝑃𝜋 . She further encrypts 𝑥 as 𝑦 = 𝐻𝜋 ∙ 𝑥 (mod 𝑛 ) and sends
a pair (𝑦, 𝜋 ′ ) to Bob where 𝜋 ′ = 𝐻 ∙ 𝜋 (mod 𝑛). Upon receipt of the message, Bob computes
permutation 𝜋 from 𝜋 ′ and 𝐻 −1 as follows 𝜋 = 𝐻 −1 ∙ 𝜋 ′ (mod 𝑛). Bob next calculates
(𝐻 −1 )𝜋 = 𝑃𝜋−1 ∙ 𝐻 −1 ∙ 𝑃𝜋 , and decrypts the ciphertext as 𝑥 = (𝐻𝜋 )−1 ∙ 𝑦 (mod 𝑛) keeping in
mind that (𝐻𝜋 )−1 = (𝐻 −1 )𝜋 .
It should be noticed that the permutation of any pair of rows (or columns) of matrix 𝐻 yields
a matrix whose inverse is obtained by the permutationof the same columns (or rows) of 𝐻 −1.
This is the reason why Bob does not need to use transposition algorithm to find (𝐻𝜋 )−1 ; it can
be easily obtained from equality (𝐻𝜋 )−1 = (𝐻 −1 )𝜋 . This observation essentially decreases
computational cost of Saeednia’s algorithm.
Below we exemplify encryption and decryption with Saeednia’s algorithm for
6 24 1
0
123
𝜋=�
�, 𝐻 = �13 16 10� and 𝑥 = � 2 �.
213
19
20 17 15
0 1 0
0 1 0
By using permutation matrix 𝑃𝜋 = �1 0 0� and its inverse 𝑃𝜋−1 = �1 0 0� we obtain
0 0 1
0 0 1
𝐻𝜋 =
𝑃𝜋−1
0 1 0
6 24 1
0 1 0
16 13 10
∙ 𝐻 ∙ 𝑃𝜋 = �1 0 0� ∙ �13 16 10� ∙ �1 0 0� = �24 6
1 �.
0 0 1
20 17 15
0 0 1
17 20 15
After that we encrypt the plaintext as follows
16 13 10
0
8
𝑦 = 𝐻𝜋 ∙ 𝑥 (mod 𝑛 ) = �24 6
1 � ∙ � 2 � (mod 26) = � 5 �.
17 20 15
19
13
Decryption is carried out as follows
0 1 0
8
5
(𝐻𝜋 )−1 = (𝐻 −1 )𝜋 = 𝑃𝜋−1 ∙ 𝐻 −1 ∙ 𝑃𝜋 = �1 0 0� ∙ �21 8
0 0 1
21 12
0 1 0
10
21� ∙ �1 0 0�.
0 0 1
8
It was reported in that Saeednia’s algorithm has the same problem as the original Hill cipher.
By collecting𝑚 pairs of (𝜋, 𝜋 ′ ) and simultaneously solving 𝑚 equations 𝜋 = 𝐻 ∙ 𝜋 ′ , a
cryptanalyst can obtain the key matrix 𝐻. Further, he can use 𝑃𝜋 and 𝑃𝜋−1 to calculate 𝐻𝜋 . In
the same paper it was noticed that Saeednia’s algorithm is time consuming since it is based on
frequent use of matrix operations. Matrix operations require a lot of time to compute when
the matrix size is large enough.
The main steps of Hill cipher are indicated below:
Encryption
1. Select invertible matrix 𝐻.
2. Calculate 𝑦 = 𝐻 ∙ 𝑥 (mod 𝑛).
3. Alice sends (𝑦, 𝐻) to Bob.
Decryption
1. Calculate 𝐻 −1 .
2. Calculate 𝑥 = 𝐻 −1 ∙ 𝑦 (mod 𝑛).
The affine Hill cipher is represented by the following steps:
Encryption
1. Select invertible matrix 𝐻.
2. Select vector 𝑉.
3. Calculate 𝑦 = 𝐻 ∙ 𝑥 + 𝑉 (mod 𝑛).
Alice sends 𝐻, 𝑉, 𝑦 to Bob.
The main steps of Saeednia’smethod are as follows:
Encryption
1. Select random permutation 𝜋.
2. Select matrix 𝐻.
Decryption
1. Calculate 𝐻 −1 .
2. Calculate 𝑥 = 𝐻 −1 (𝑦 − 𝑉).
3. Calculate permutation matrix 𝑃𝜋 by permuting the rows of identity matrix 𝐼.
4. Calculate permutation matrix 𝑃𝜋−1 by permuting the columns of identity matrix 𝐼.
5. Calculate 𝐻𝜋 = 𝑃𝜋−1 ∙ 𝐻 ∙ 𝑃𝜋 .
6. Calculate 𝑦 = 𝐻𝜋 ∙ 𝑥 (mod 𝑛)
7. Calculate 𝜋 ′ = 𝐻 ∙ 𝜋 (mod 𝑛)
Alice sends 𝜋 ′ , 𝐻, 𝑦 to Bob.
Decryption
1. Calculate 𝐻 −1 .
2. Calculate 𝜋 = 𝐻 −1 ∙ 𝜋 ′ (mod 𝑛).
3. Calculate permutation matrix 𝑃𝜋 by permuting the rows of identity matrix 𝐼.
4. Calculate permutation matrix 𝑃𝜋−1 by permuting the columns of identity matrix 𝐼.
5. Calculate (𝐻 −1 )𝜋 = 𝑃𝜋−1 ∙ 𝐻 ∙ 𝑃𝜋 .
6. Calculate 𝑥 = (𝐻𝜋 )−1 ∙ 𝑦 (mod 𝑛)
Polyalphabetic ciphers. All polyalphabetic techniques have the following features in
common:
1. A set of related monoalphabetic substitution rules are used.
2. The key determines which particular rule is chosen for a given transformation.
The best-known and one of the simplest polyalphabetic algorithms is referred to as the
Vigenere cipher. In this scheme, the set of related monoalphabetic substitution rules
consists of the 26 Caesar ciphers, with shifts of 0 to 25. Each cipher is denoted by a key
letter, which is ciphertext letter that substitutes for the plaintext letter a. Thus, a Caesar
cipher with a shift of 3 is denoted by the key value d.
The process of encryption is easy: Given a key letter x and the plaintext letter y, we
pick up a letter that is at the intersection of the row and column pointed out by x and y,
respectively. In this case the cipherletter is V.
Obviously, to encrypt the plaintext a key is needed that is as long as the message. Usually, the
key is a repeating keyword. For example, if the keyword is DECEPTIVE, the message “we are
discovered save yourself” is encrypted as follows:
Key:
deceptivedeceptivedeceptive
Plaintext:
e
ZICVTWQNGRZGVTWAVZHCQYGLMGL
f
G
h
i
j
k
L
m n
o
p
q
r
s
t
u
v
w X
y
z
A B C
D E
F
G
H
I
J
K
L
M N
O
P
Q
R
S
T
U
V
W X
Y
Z
C
F
J
K
L
M N
O
Q
R
S
T
U
V
W X
Y
A
B
M N
O
Q
W X
Y
A
O
Q
W X
Y
A
W X
Y
A
W X
Y
A
W X
Y
A
W X
Y
A
Y
A
a
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
Ciphertext:
wearediscoveredsaveyourself
B
b
C
c
D E
D E
D E
F
E
F
G
H I
F
J
J
O
J
M N
O
Q
M N
O
Q
M N
O
Q
M N O P
Q
J
J
J
Q R S
T
Q
Q R S
Q R S
T
T
T
U
U V
U V
I
K
L
M N
Q R
Q R S
Q R S
K
M N O
M N O P
N O P
J
K L
K L
K L
K L
H
G H I
M N O P
O P
G
G H I
M N O P
P
F
G H I
K L
K L
L
M N
G H I
H I
I
d
P
R
S
T
U
V
J
L
P
Q
R
S
T
U
V
W X
W X
R S T U V W X Y Z
S T U V W X Y Z
T U V W X Y Z
K
W X
Y
W X
Y
A B
W X
Y
A
W X
Y
A
W X
Y
A
W X
Y
A
W X
Y
A
Y
A
P
R
S
T
U
V
Z
L
P
R
S
T
U
V
Z
P
R
S
T
U
V
Z
B
T
U
V
Z
B
C
A B C D E F
W X Y Z A B C D E F
X Y Z A B C D E F
Z A B C D E F
A B C D E F
S
S
T
U
V
Z
B
C
D
A B C D E F
V W X Y Z A B C D E F
Z
R
R
R
S
T
U
V
Z
B
C
D
E
A B C D E F
U V W X Y Z A B C D E F
Y
P
P
P
G H I
G H I
J
J
J
J
J
U
V
Z
B
C
D
E
F
T
U
V
Z
B
C
D
E
F
G
S
U
V
Z
B
C
D
E
F
G
H
G H I
J
J
J
T
V
Z
B
C
D
E
F
G
H
I
J
U
Z
B
C
D
E
F
G
H
I
J
V
Z
B
C
D
E
F
G
H
I
J
K
K L
K L
K L
K L
K L
K L
K L
K L
K L
T
G H I
G H I
G H I
S
R
G H I
G H I
G H I
Q
Z
B
C
D
E
F
G
H
I
J
K
L
Z
B
C
D
E
F
G
H
I
J
K
L
Z
B
C
Z
C
D
D E
E
F
G
H
F
G
H I
I
J
J
K
K L
L
C
D
E
F
G
H
I
J
K
L
M
M N
M N
M N O
O
P
M N O P Q
M N O P Q R
M N O P Q R S
M N O P Q R S
T
M N O P Q R S T U
M N O P Q R S
M N O P Q R S
M N O P Q R S
M N O P Q R S
T U V
T U V W
T U V W X
T U V W X
Decyption is equally simple. The key letter again identifies the row. The position of
the ciphertext letter in that row determines the column, and the plaintext letter is at the
top of that column.
A
Y
A cryptanalyst catches the ciphertext and tries to determine whether the ciphertext was
created using a monoalphabetic substitution or a Vigenere type cipher. A simple test can be
performed to make sure on this matter. If the statistical properties of the ciphertext are
similar to those of a language used to encrypt the plaintext, e.g., English, then plaintext was
encrypted using monoalphabetic substitution. Otherwise plaintext was encrypted using a
polyalphabetic cipher.
If, on the other hand, polyalphabetic substitution like Vigenere cipher is suspected, then
progress depends on determining the length of the keyword. Let us concentrate on how the
keyword length can be determined. The important insight that leads to a solution is
the following: if two identical sequences of plaintext letters occur at a distance that is an
integer multiple of the keyword length,
they will generate
identical
ciphertext
sequences. In the foregoing example, two instances of the sequence RED are separated by
nine character positions. Consequently, in both cases, R is encrypted using key letter E, E is
encrypted using key letter P, and d is encrypted using key letter T. Thus, in both cases the
ciphertext would detect the repeated sequence VTW.
An analyst looking at only the ciphertext would detect the repeated sequences VTW
at a displacement of 9 and make the assumption that the key is either 3 or 9 letter in
length. If the message is long enough then there will be such repeated fragments. By
calculating the factors in the displacements of the various sequences, the analyst should
be able to make a good guess of the keyword length. Solution of the cipher now depends on
an important insight.
If the keyword
length is N, then the cipher,
in effect,
consists of N monoalphabetic substitution ciphers. For example, if the keyword is
DECEPTIVE then the letters in positions 1, 10, 19, and so on are all encrypted with the
same monoalphabetic cipher. Thus we can use the known frequency characteristics of the
plaintext language to attack each of the monoalphabetic ciphers separately.
Another example of Vinegere cipher is illustrated below
a b c
k K L M
e E F G
y Y Z
d
N
H
A
e
O
I
B
f
P
J
C
g
Q
K
D
h
R
L
E
i
S
M
F
j
T
N
G
k
U
O
H
this is a message
Plaintext:
keykeykeykeykeyke
Ciphertext:
CLFBDFBDYJQBBWYQI
Keyword:
l
V
P
I
m
W
Q
J
n
X
R
K
o
Y
S
L
p Q r s t
Z
A B C
T U V W X
M N O P Q
u
D
Y
R
v w x y z
E F G H I J
Z
A B C D
S T U V W X
In this example, t , the first letter of the plaintext is intersected with the alphabet pointed
by the letter k . The result is the ciphertext letter C. Such a process, though slow to
do by hand, can be done very quickly on a computer. The complexity of the cipher
can be raised by increasing the number of unique letters in the keyword, and
hence increasing the number of alphabets used. As a result, it is important for
cryptanalysits to learn how many alphabets are being used.
Transposition techniques. All the techniques examined so far involve the substitution
of a ciphertext symbol for a plaintext symbol. A very different kind of mapping is
achieved by performing some sort of permutation on the plaintext letters. This technique
is referred to as transposition cipher.
The simplest such cipher is provided by so called rail fence technique. In rail fence
technique the plaintext is written down as a sequence of diagonals and then read off as a
sequence of rows. For instance to encipher the message MEETMEAFTERTHETOGAPARTY
with a rail fence of depth 2, we write the following
m
e
e
t
m
e
a
t
f
e
r
t
h
e
t
o
The encrypted message is MEMATRHTGPRYETEFETEOAAT.
g
a
p
a
r
t
y
This sort encryption obviously is trivial. Instead, we could add more depth into the
algorithm by writing the plaintext row by row, reading it column by column, and
meantime permuting the order of columns. The order of columns then becomes the
key to the algorithm. For example,
Key:
Plaintext:
Ciphertext:
4
3
1
2
5
6
7
a t t a c k p
o s t p o n e
d u n t i l t
w o a m x y z
TTNAAPTMTSUOAODWCOIXKNLYPETZ
A pure transposition cipher is easily recognized because it has the same letter
frequencies as the original plaintext. For the type of columnar transposition just shown,
cryptanalysis is fairly straightforward and involves laying out the ciphertext in a
matrix and playing around with columnar positions. Diagram and triagram frequency
tables can be useful.
The transposition cipher can be made significantly more secure if we perform more than
one stage of transposition. The result is a more complex permutation that is not easily
reconstruct. Thus, if the foregoing message is reencypted using the same technique,
then the result would be
Key:
Plaintext:
Ciphertext:
4
3
1
2
5
6
7
t t n a a p t
m t s u o a o
d w c o i x k
n l y p e t z
NSCYAUOPTTWLTMDNAO