Classical Cryptanalysis

Introduction to
Cryptography

Historical
Cryptosystems

3rd Class – 20 3 2018 Introduction to

Cryptanalysis

Dr. Sattar B. Sadkhan Breaking Historical

Cryptosystems
 Cryptanalysis
• The general assumption is that an opponent, Eve, Introduction to
Cryptography
knows the cryptosystem being used. This is referred
to as Kerchkhoffs’ principle. Historical
Cryptosystems

Introduction to
• Goal of a cryptanalyst is to recover the original Cryptanalysis
plaintext message without knowing the key being
Breaking Historical
used or to deduce the key itself. Cryptosystems

• Common attack models are:

– Ciphertext only attack
– Known plaintext attack
– Chosen plaintext attack
– Adaptive-chose plaintext attack
– Chosen ciphertext attack
– Adaptive-chosen ciphertext attack
2
 Ciphertext Only Attack
Introduction to
Cryptography
• The cryptanalyst possesses a string of ciphertext.
Historical
Cryptosystems

• Given: c = ek(p) Introduction to

Cryptanalysis

Determine: p or k (the key being used) Breaking Historical

Cryptosystems

• Any cryptosystem vulnerable to this type of attack is

considered to be completely insecure.

3
 Known Plaintext Attack
Introduction to
Cryptography
• The cryptanalyst possesses a plaintext message
and corresponding ciphertext. Historical
Cryptosystems

Introduction to
• Given: p and c = ek(p) Cryptanalysis

Breaking Historical
Determine: Cryptosystems
k (the key used for encrypting the plaintext
message)

or a function that would produce correct

plaintext for a given ciphertext

4
 Chosen and Adaptive-chosen Ciphertext
Attack
• The cryptanalyst can choose a ciphertext and Introduction to
Cryptography
obtain corresponding plaintext message. In case of
adaptive-chosen ciphertext attack, the Historical
Cryptosystems
cryptanalyst has obtained temporary access to the
decryption machine. So he can select ciphertext Introduction to
Cryptanalysis
based on previously achieved results.
Breaking Historical
Cryptosystems
• Given:
c1, p1 = dk(c1), c2, p2 = dk(c2), …, cn, pn = dk(cn)
Determine:
k (the key used for encrypting the plaintext
message)

or a function that would produce correct

plaintext for a given ciphertext

5
 Breaking Historical Cryptosystems
Introduction to
Cryptography

Historical
Cryptosystems
• Statistical properties of English language, since it
Introduction to
is being used by many techniques of cryptanalysis. Cryptanalysis

Breaking Historical
Cryptosystems

H.W. 1) Find the

•Statistical properties of Arabic language

6
 Statistics of the language
• Following are statistics for single letters:
Introduction to
Cryptography

letter prob letter prob letter prob Historical

A .082 J .002 S .063 Cryptosystems
B .015 K .008 T .091
C .028 L .040 U .028 Introduction to
D .043 M .024 V .010 Cryptanalysis
E .127 N .067 W .023
F .022 O .075 X .001 Breaking Historical
G .020 P .019 Y .020
Cryptosystems
H .061 Q .001 Z .001
I .070 R .060

• Most common digrams are: TH, HE, IN, ER, AN,

RE, ED, ON, ES, ST, EN, AT, TO, NT, HA, ND, OU,
EA, NG, AS, OR, TI, IS, ET, IT, AR, TE, SE, HI, OF
• Most common trigrams are: THE, ING, AND, HER,
ERE, ENT, THA, NTH, WAS, ETH, FOR, DTH

H.W. 2) Find the

•Most Common “ Diagrams”, and “ trigrams”of Arabic
7
language
 Example : Cryptanalysis of
the Substitution Cipher
Introduction to
Cryptography
• We will try to break the Substitution Cipher using
ciphertext-only attack. Historical
Cryptosystems

Introduction to
• Here is the intercepted ciphertext: Cryptanalysis

Breaking Historical
BTLDXFETMDGLGMVMYFQEMQAPMVBZQMXZQEGZVXFTL Cryptosystems
XGUWFVXBFWDYUXUQFQXUBGQZBMYMBBFHQXFPXGU
VHISUBXZVCMGQVXGUBFAUITUMCUTVXGZVIFFCXTMBUV
BTLDXFETMDGLPTFWZXVZQZXZMYMQAYZWZXUAHVUIL
XGUUELDXZMQVVFWUPFHTXGFHVMQALUMTVMEFXFXGU
XKUQXZUXGBUQXHTLKGUTUZXDYMLUAMBTHBZMYTFYU
ZQXGUFHXBFWUFPIFXGKFTYAKMTVBFWDYUXUAZQ
QZQUXUUQVZJXLXGTUUXGUIFFCBFOUTVXGFVUMVDUBXV
FPXGUGZVXFTLKGZBGKUTUWFVXVZEQZPZBMQXXFXGU
AUOUYFDWUQXFPXGUVHISUBX

8
 Example: Cryptanalysis of
the Substitution Cipher
Introduction to
Cryptography
• Statistics for single letter of the ciphertext
letter prob letter prob letter prob Historical
A .023 J .003 S .005 Cryptosystems
B .054 K .015 T .054
C .010 L .030 U .120 Introduction to
D .026 M .061 V .066 Cryptanalysis
E .018 N .000 W .023
F .090 O .005 X .118 Breaking Historical
G .066 P .020 Y .028
Cryptosystems
H .023 Q .059 Z .064
I .018 R .000

• Most common digrams are: XG (16), GU (11), XF

(8), QX (7), VX (7), BF (6), UX (6), ZQ (6)
• Most common trigrams are: XGU (10), BFW, FPX,
FXG, GZV, LDX, LXG, MQA, PXG, UBX, UQX,
UXU, VXG - all appear three times in the text

9
 Example: Cryptanalysis of
the Substitution Cipher
Introduction to
Cryptography
• Now we can make a few assumptions. U and X
Historical
appear the most often in the ciphertext. We can Cryptosystems
assume that this letters correspond with E and T in
Introduction to
the original message. Cryptanalysis

Breaking Historical
• The most common digram in the ciphertext is XG. Cryptosystems
That means X = T and then G = H. THE is the most
common trigram in English, so we can conclude that
U = E.

• XF is a common digrams. We know that X = T. So

XF can be TO or TI. O is a bit more frequent in
English than I, so F = O.

10
 Example: Cryptanalysis of
the Substitution Cipher
Introduction to
Cryptography
• Now our ciphertext looks as follows:
Historical
Cryptosystems
BTLDtoETMDhLhMVMYoQEMQAPMVBZQMtZQEhZVtoTL
Introduction to
theWoVtBoWDYeteQoQteBhQZBMYMBBoHQtoPthe Cryptanalysis
VHISeBtZVCMhQVtheBoAeITeMCeTVthZVIoCtTMBeV
Breaking Historical
BTLDtoETMDhLPToWZtVZQZtZMYMQAYZWZteAHVeIL
Cryptosystems
theeELDtZMQVVoWePoHTthoHVMQALeMTVMEotothe
tKeQtZethBeQtHTLKheTeZtDYMLeAMBTHBZMYToYe
ZQtheoHtBoWeFPIothKoTYAKMTVBoWDYeteAZQ
QZQeteeQVZJtLthTeetheIooCBFOeTVthFVeMVDeBtV
oPthehZVtoTLKhZBhKeTeWoVtVZEQZPZBMQttothe
AeOeYoDWeQtoPtheVHISeBt

• X = T, G = H, U = E, F = O

11
 Example: Cryptanalysis of
the Substitution Cipher
Introduction to
Cryptography

• Let’s analyze QX and UQX. QX can be AT, NT, or Historical

IT. However if we consider UQX trigram, we can Cryptosystems
see that most likely Q = N. Introduction to
Cryptanalysis

• MQA is a common trigram. Taking into account that Breaking Historical

Q = N, we say that MQA = AND. Hence M = A and Cryptosystems

A = D.

• By now we know that Q = N, M = A, A = D, X = T,

G = H, U = E, F = O. Proceeding in the same way it
is not difficult to recover the complete message.

12
 Example: Cryptanalysis of
the Substitution Cipher
Introduction to
• The recovered plaintext message (with spaces Cryptography
added) is: Historical
“ cryptography has a long and fascinating history Cryptosystems

the most complete nontechnical account of the Introduction to

subject is kahns the codebreakers this book traces Cryptanalysis

cryptography from its initial and limited use by Breaking Historical

the egyptians some four thousand years ago to the Cryptosystems

twentieth century where it played a crucial role

in the outcome of both world wars completed in
nineteen sixty three the book covers those aspects
of the history which were most significant to the
development of the subject “

(Taken from Handbook of Applied Cryptography, by A. Menezes, P. van

Oorschot, and S. Vanstone)

13
 Example: Cryptanalysis of the Vigenère
Cipher
Introduction to
Cryptography
• The Vigenère Cipher is polyalphabetic, so additional Historical
cryptoanalysis techniques should be used. Cryptosystems

Introduction to
• The ciphertext is: Cryptanalysis

Breaking Historical
MRGFNIATXZQVFFNUXFFYBTCETYXIIXGZKACJLRGKQYEIX Cryptosystems
OYYAUAPXYIJLHPRGVTSFPAYNNYURZOPHXWYXLFRNUTZBR
FKAHFWFZESYUWZMOLLBSBZBJHFPLXKHVIVMZTZHUIWAET
IUEDFGLXDIEXIYJIUXPNNEIXABVCINTVCIEZYYDAZGZIW
TYXJIKTRZLMFFKALGZNVKZXIIMXUUNAPGVXFUSMISKHVY
VOCRVXRIWTYXZOIRFNUXZNXLDUDPZGVHVOWMOYJERLAUG
LVTUXTHRBUQZTYTXORNKBASFFXGHQVDSHUYJSYHDYUWYX
YYKHVTUCDACAHXSEVGJIEFZGLXRSBXSYKOEPPNYAKTUAC
EFYILFWEAHCIAUALLZNXMVCKLRRHGFNXMOYUESKPM

14
 Cryptanalysis of the Vigenère Cipher
Introduction to
Cryptography
• As mentioned above, the Vigenère Cipher makes
use of a keyword of length m. Historical
Cryptosystems

Introduction to
• Our first step is to determine the key. After that Cryptanalysis
decryption of the message is easy.
Breaking Historical
Cryptosystems
• There are two techniques that can be employed.
Namely the Kasiski test and the index of
coincidence.

15
 Cryptanalysis of the Vigenère Cipher
Introduction to
Cryptography
• The Kasiski test method is based on the
Historical
observation that two identical segments of Cryptosystems
plaintext will be encrypted to the same
Introduction to
ciphertext as long as they are δ positions Cryptanalysis
apart ( δ ≡ 0 (mod m) ).
Breaking Historical
Cryptosystems

• The 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 divides the greatest
common divisor of the δi’s.

16
 Cryptanalysis of the Vigenère Cipher
Introduction to
• In the ciphertext trigram TYX occurs 3 times. The Cryptography
starting positions are 25, 181, and 235. The
distance between the first and the second is 156 Historical
Cryptosystems
symbols, between the first and the third 210. The
gcd of these two numbers is 6, so we can assume Introduction to
that the keyword length is also 6. Cryptanalysis

Breaking Historical
Cryptosystems
• 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 = x1x2 ...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.
17
 Cryptanalysis of the Vigenère Cipher
Introduction to
Cryptography
• If we denote the frequencies of A, B, C, …, Z in x by f1,
ænö Historical
f2, f3, …, f25. We can choose two elements of x in ç ÷ ways. Cryptosystems
è2ø
There are æç fi ö÷ ways of choosing two same elements. Introduction to
è2ø
Cryptanalysis
Hence, we have the formula
Breaking Historical
Cryptosystems
25
æ fi ö 25
å ç ÷ å fi (fi - 1)
i =0 è 2 ø
Ic ( x ) = = i =0
ænö n(n - 1)
ç ÷
è2ø

18
 Cryptanalysis of the Vigenère Cipher
Introduction to
• Index of coincidence of a string written in English is Cryptography
approximately equal to 0.065.
25 Historical
Ic ( x ) » å p = 0.065
2
i
Cryptosystems
i =0
Introduction to
Cryptanalysis

Breaking Historical
Cryptosystems

19
 Cryptanalysis of the Vigenère Cipher

• On the other hand, if m is not the keyword length, Introduction to

Cryptography
the strings ci would look much more random. A
completely random string would have Historical
Cryptosystems
2
æ 1 ö 1
Ic » 26 ç ÷ = = 0.038 Introduction to
è 26 ø 26 Cryptanalysis
• Following table contains Ic for different values of m:
Breaking Historical
m Ic Cryptosystems
1 0.043
2 0.052; 0.051
3 0.05; 0.059; 0.045
4 0.049; 0.053; 0.052; 0.051
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

• This method also shows that m = 6.

20
Cryptanalysis of the Vigenère Cipher
• The recovered plaintext message (with spaces Introduction to
Cryptography
added) is:
Historical
Cryptosystems
many traces we found of him in the boggirt island
Introduction to
where he had hid his savage ally a huge drivingwheel Cryptanalysis
and a shaft halffilled with rubbish showed the
position of an abandoned mine beside it were the Breaking Historical
crumbling remains of the cottages of the miners Cryptosystems
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)

21
 Exercise 1
• Calculate: Introduction to
Cryptography

Historical
1547 mod 31 Cryptosystems

Introduction to
-1547 mod 31 Cryptanalysis

Breaking Historical
Cryptosystems
28 mod 31

-28 mod 31

22
 Exercise 2
• Your are given the following ciphertext: Introduction to
Cryptography
KYVUVMZCJRXVEKJDRPSVFWIWCVJYREUSCFFUDRPKY
VPEFKKYVIVRIVKNFHLVJKZFEJNRZKZEXWFILJRKKY Historical
Cryptosystems
VFLKJVKKYVFEVZJNYVKYVIREPTIZDVYRJSVVETFDD
ZKKVURKRCCKYVJVTFEUZJNYRKZJKYVTIZDVREUYFN Introduction to
NRJZKTFDDZKKVU Cryptanalysis
letter prob letter prob letter prob
Breaking Historical
A .000 J .073 S .017 Cryptosystems
B .000 K .129 T .028
C .028 L .017 U .039
D .045 M .006 V .140
E .056 N .034 W .017
F .073 O .000 X .011
G .000 P .022 Y .073
H .006 Q .000 Z .067
I .039 R .079

• Please determine what cipher was used to encrypt

the message. Find the key and the original plaintext.

23
 H.W
Introduction to
Cryptography
If you have the Arabic language oriented as follows :
Historical
Cryptosystems
‫) أبجحخدذهطظكلمنتثصضسشطظرزوؤئعغ‬
( ‫فق‬ Introduction to
Cryptanalysis

( ‫ﺷﻔر اﻟرﺳﺎﻟﺔ اﻻﺗﯾﺔ ) اﺣﻣد ذھب اﻟﻰ اﻟﻣدرﺳﺔ ﺻﺑﺎﺣﺎ ﺳﯾرا ﻋﻠﻰ اﻻﻗدام‬ Breaking Historical
.( ‫ ﻋﻠﻣﺎ ان اﻟﻣﻔﺗﺎح اﻟﻣﺳﺗﺧدم ﻛﺎن ) ﻗﻠم‬Vigenere ‫ﺑﺎﺳﺗﺧدام طرﯾﻘﺔ‬ Cryptosystems

‫ﻣﺎ ھو اﻟﻧص اﻟﻣﺷﻔر ؟‬

‫ ﻋﻠﻰ‬Index of Coincidence ‫ وال‬Kasiski ‫ھل ﯾﻣﻛن ان ﺗطﺑق طرﯾﻘﺔ‬

‫اﻟﻧص اﻟﻣﺷﻔر اﻟذي ﺣﺻﻠت ﻋﻠﯾﮫ ؟‬

24