CRYPTOGRAPHY

Classical
Cryptography
 Classical
Cryptosystems
(Polyalphabetic)
 Polyalphabetic Ciphers
• The simple substitution cipher is weak because the attacker can exploit
the fact that:
– The letter frequency distribution of the ciphertext will match the letter
frequency distribution of the plaintext
– These will generally follow the letter frequency distribution of the
plaintext language
• A simple way to defeat frequency analysis is to encipher each plaintext
letter with a different substitution alphabet

• The use of multiple substitution alphabets will mean that a plaintext letter
can encrypt to different ciphertext letters, thus causing the letter frequency
distribution to appear “flatter” (the individual letter frequencies are
averaged out)

• A cipher that uses multiple substitution alphabets is called a

polyalphabetic substitution cipher. The Vigenere Cipher and Hill Cipher are
examples of alphabetic ciphers
 1. The Viginere Cipher

Suppose key length (m)=6

Possible
Key word (K) = C I P H E R = (2,8,15,7,4,17)
keys= 26m
Plaintext (P) = thiscryptosystemisnotsecure
P t h i s c r y p t o s y

19 7 8 18 2 17 24 15 19 14 18 24
K 2 8 15 7 4 17 2 8 15 7 4 17
21 15 23 25 6 8 0 23 8 21 22 15
C V P X Z G I A X I V W P
P s t e m i s n o t s e c u R e
18 19 4 12 8 18 13 14 19 18 4 2 20 17 4
K 2 8 15 7 4 17 2 8 15 7 4 17 2 8 15
20 1 19 19 12 9 15 22 8 25 8 19 22 25 19
C U B T T M J P W I Z I T W Z T

Ciphertext (C) = VPXZGIAXIVWPUBTTMJPWIZITWZI

1. The Viginere Tableau
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
 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 A
 C D E F G H I J K L M N O P Q R S T U V W X Y Z A B
 D E F G H I J K L M N O P Q R S T U V W X Y Z A B C
 E 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
 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
 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
 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
 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
 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
 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
 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
 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
 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
 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
 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
 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
 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
 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
 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
 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
 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
 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
 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
 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
 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
Cryptanalysis of the Vigenère
Cipher
• The Vigenère Cipher makes use of a keyword of length m. The
number of possible key words of length m is 26m. e.g. Take
m=5, the key space has size 265=1.1 x 107, an exhaustive key
search would require long time

• So,
First step: determine the key length=m,
Second step: determine the key (word) itself
After that decryption of the message is easy.
 Cryptanalysis of the
Vigenère Cipher

Determine Key length

• There are two techniques that can be employed to

determine key length.
– Kasiski test
– Index of coincidence.
 Kasiski Test

• The Kasiski test was introduced in 1863 by a Prussian

military officer Friedrich Kasiski

• The method is based on the observation that two identical

segments of plaintext will be encrypted to the same
ciphertext as long as they are δ positions apart (δ ≡ 0 (mod
m)).

• Our goal is to find several identical pieces of text, each of

length at least three, and record the distance between their
starting position. m divides all of the distances δ1, δ2, …, δn.
Hence m be the greatest common divisor of the δi’s.
 Kasiski Test
• In the ciphertext trigram TYX occurs 3 times. The starting positions are 25,
181, and 235. The distance between the first and the second is 156
symbols, between the first and the third 210. The gcd of these two numbers
is 6, so we can assume that the keyword length is also 6.

MRGFNIATXZQVFFNUXFFYBTCE25TYXIIXGZKACJLRGKQYEIX
OYYAUAPXYIJLHPRGVTSFPAYNNYURZOPHXWYXLFRNUTZBR
FKAHFWFZESYUWZMOLLBSBZBJHFPLXKHVIVMZTZHUIWAET
IUEDFGLXDIEXIYJIUXPNNEIXABVCINTVCIEZYYDAZGZIW
181
TYXJIKTRZLMFFKALGZNVKZXIIMXUUNAPGVXFUSMISKHVY
VOCRVXRIW235TYXZOIRFNUXZNXLDUDPZGVHVOWMOYJERLAUG
LVTUXTHRBUQZTYTXORNKBASFFXGHQVDSHUYJSYHDYUWYX
YYKHVTUCDACAHXSEVGJIEFZGLXRSBXSYKOEPPNYAKTUAC
EFYILFWEAHCIAUALLZNXMVCKLRRHGFNXMOYUESKPM
 Index of Coincidence
• Now we will use the index of coincidence to see if it gives the same result.
• The index of coincidence is defined as follows:

Suppose x  x1x 2 ...xn is a string of n alphabetic

characters. The index of coincedence of x,
denoted Ic ( x ), is defined to be the probability that
two random elements of x are identical.

• If we denote the frequencies of A, B, C, …, Z in x by f1, f2, f3, …, f25. We can

n  fi 
choose two elements of x in  2 ways. There are  2  ways of choosing two same
elements. Hence, we have the formula
25
 fi  25
    fi (fi  1)
i 0 2
Ic ( x )     i 0
n n(n  1)
 
2
 Index of Coincidence
• Index of coincidence of a string written in English is approximately
equal to 0.065. Table 1

25
Ic ( x )   i  0.065
p 2

i 0

• Every language has such an IC, for example:

– Russian: 0.0529
– German: 0.0762
– Spanish: 0.0775

• Index of coincidence of a random string in English is approximately

equal to 2
 1  1
Ic  26    26  0.038
 26 
 Index of Coincidence
• Now we rewrite the ciphertext c in the following way
c1  c1cm 1c2 m 1 ...
c2  c 2cm  2cm  2 ...
...
cm  c m c 2 m c3 m ...
• If c1, c2, …, cm are constructed in such a way that m is the keyword length,
then each Ic(ci) should be approximately equal to 0.065

• Following table contains Ic for different values of m:

m Ic
1 0.043
2 0.052; 0.051
3 0.05; 0.059; 0.045 This method also
4 0.049; 0.053; 0.052; 0.051 shows that m = 6
5 0.034; 0.05; 0.048; 0.038; 0.045
6 0.063; 0.07; 0.083; 0.062; 0.071; 0.048
7 0.033; 0.041; 0.038; 0.046; 0.041; 0.04; 0.047
Example to calculate IoC
Cryptanalysis of the Vigenère
Cipher
Determine the Key Word

• To determine the keyword itself we use a method similar to the

index of coincidence.
• Each substring ci was produced using a monoalphabetic cipher.
Thus defining a shift g we can use the following formula
25 p f
Mg   i i g For values of pi, consult Table 1
i 0 n
where f1, f2, …, fi denotes the frequencies of A, B, …, Z in the
substring ci, and n is the length of the substring.
• If g is the correct shift value, Mg would be roughly equal to 0.065
• Now we have to determine the most suitable value of Mg for
each of the substrings.
 Cryptanalysis of the
Vigenère Cipher
i Mg
0.062; 0.042; 0.033; 0.035; 0.041; 0.039; 0.030; 0.040; 0.036; 0.039; 0.026; 0.040;
1 0.043; 0.046; 0.038; 0.046; 0.032; 0.033; 0.042; 0.043; 0.037; 0.029; 0.047; 0.035;
0.032; 0.036
0.033; 0.037; 0.035; 0.035; 0.046; 0.042; 0.048; 0.040; 0.032; 0.028; 0.043; 0.040;
2 0.038; 0.046; 0.037; 0.026; 0.042; 0.065; 0.037; 0.033; 0.041; 0.044; 0.029; 0.036;
0.038; 0.034
0.038; 0.030; 0.038; 0.029; 0.043; 0.041; 0.052; 0.034; 0.041; 0.041; 0.036; 0.033;
3 0.040; 0.040; 0.028; 0.050; 0.031; 0.025; 0.036; 0.073; 0.039; 0.035; 0.034; 0.044;
0.033; 0.038
0.040; 0.043; 0.034; 0.047; 0.038; 0.031; 0.042; 0.064; 0.037; 0.027; 0.030; 0.042;
4 0.036; 0.036; 0.038; 0.039; 0.043; 0.041; 0.040; 0.034; 0.044; 0.042; 0.040; 0.033;
0.027; 0.034
0.030; 0.037; 0.034; 0.030; 0.046; 0.047; 0.041; 0.036; 0.035; 0.043; 0.047; 0.035;
5 0.038; 0.035; 0.033; 0.036; 0.049; 0.034; 0.027; 0.044; 0.065; 0.037; 0.026; 0.044;
0.045; 0.028
0.031; 0.039; 0.041; 0.041; 0.038; 0.044; 0.044; 0.034; 0.030; 0.037; 0.039; 0.036;
6 0.035; 0.039; 0.034; 0.034; 0.042; 0.059; 0.043; 0.029; 0.036; 0.043; 0.037; 0.033;
0.039; 0.035

• We have found the keyword, which is ARTHUR.

 Cryptanalysis of the
Vigenère Cipher
• The recovered plaintext message (with spaces added) is:

many traces we found of him in the boggirt island where he had

hid his savage ally a huge driving wheel and a shaft half filled with
rubbish showed the position of an abandoned mine beside it were
the crumbling remains of the cottages of the miners driven away
no doubt by the foul reek of the surrounding swamp in one of
these a staple and chain with a quantity of gnawed bones showed
where the animal had been confined a skeleton with a tangle of
brown hair adhering to it lay among the debris.

(Taken from Hound of the Baskervilles, by Arthur Conan Doyle)

 The Hill Cipher

• As well as Vigenère, this cipher is polyalphabetic.

• It was invented by Lester S. Hill in 1929.

 The Hill Cipher
• To encrypt a message using the Hill Cipher one should perform the
following sequence of steps:
– Using the Table (below), plaintext message has to be expressed
as sequence of integers in such a way that p = (p1, …, pm)
– The key is an m×m matrix
– The resulting ciphertext c = ek(p) = p×k will be a string (c1, …,
cm) of length m
• To decrypt the ciphertext one should apply the inverse linear
transformation. In other words
p = c× k-1, where k k-1 mod 26 = I.

A B C D E F G H I J K L M N 0 P Q R S T U V W X Y Z
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
 The Hill Cipher
Example:
• Encrypting a message using the Hill Cipher is very simple. Decryption however is more challenging.
• Suppose the key (K) is

• We can compute K-1, which is, 11 8 

k   
 3 7 

• We are given the following plaintext “july”, we need to encrypt two pieces of plaintext ju (9,20) and ly (11,24):
 7 18 
k   
 23 11 

• Hence the encryption of july is DELW

11 8 
9 20   99  60, 72  40  3, 4 
 3 7
and
11 8 
11 24   121  72, 88  168  11 22 
• After k-1 is found, it is easy to find the 3 7
 corresponding
 plaintext, which is “matrix” in our case.
 The Hill Cipher
Example:
• To decrypt, we use K-1, following computation are made:

 7 18 
3 4   21  92, 54  44  9, 20
and  23 11 
 7 18 
11 22
• Hence the correct plaintext is obtained
  77  506, 198  242  11, 24
• In order to decrypt, it is needed  23
the 11  of K to satisfy:
determinant
gcd( det(K), 26) =1=(53, 26)

To calculate inverse, the usual formula is:

1
a b  1  d  b
    
c d  ad  bc   c a 
Cryptanalysis of the Hill
Cipher
• The Hill Cipher is difficult to break using only ciphertex but it
can be easily broken using known plaintext attack

• Suppose we possess m distinct plaintext-ciphertext pairs pj =

(p1,j , p2,j , …, pm,j) and cj = (c1,j, c2,j, …, cm,j), where m is the key
dimension. Let us define two m×m matrices X = (ci,j) and Y =
(pi,j). Then Y = X k.

Now it is easy to find the key, k = X-1Y,

where X X-1 mod 26 = I.

Cryptanalysis of the Hill
Cipher
• Assume we have ciphertext “IKNQYB” and we know that the
plaintext is “cipher”.
• Assume m = 2. ek(2, 8) = (8, 10), ek(15, 7) = (13, 16), and ek (4,
17) = (24, 1). Using the second and the third plaintext-ciphertext
pairs, we come up with the following equation in the form Y = X k
 13 16   15 7 
  k
 24 1   4 17 
• To find the key, we need inverse modulo of X
1
 15 7   5 1
   
 4 17   8 9 
• Now
 5 1   13 16   11 3 
k    
 8 9  24 1   8 7 
 The Permutation Cipher

• This cryptosystem is really old.

• It was described in book by Giovanni Porta written in 1563.

• “Rail-fence” cipher is an example of permutation cipher.

 The Permutation Cipher
• In order to use the cipher a permutation has to be
defined. Let us use the following permutation as
example:

x 1 2 3 4 5 6 c 1 2 3 4 5 6
π(x) 5 1 6 3 2 4 π-1(c) 2 5 4 6 1 3

• Since m = 6, the original message has to be broken on

n groups of six letters each. If last group is shorter,
necessary number of dummy letters can be appended
to the end.
• Each group is rearranged according to the permutation
defined previously.
• To decrypt a ciphertext message inverse permutation
should be applied in a similar way.
 The Permutation Cipher
Suppose m=6, and the key is the following permutation π:

x 1 2 3 4 5 6
π(x) 3 5 1 6 4 2

• Now suppose we are given the plaintext:

shesellsseashellsbytheseashore
• We first partition it into a group of 6:
shesel lsseas hellsb ythese ashore
• Now each group of 6 letters is rearranged according to the permutation table
π:
EESLSH SALSES LSHBLE HSYEET HRAEOS
• This is ciphertext, which can be decrypted in a similar fashion using inversion
permutation π-1
x 1 2 3 4 5 6
Π-1(x) 3 6 1 5 2 4