CLO 1

Lecture#02
Classical Encryption Techniques
Course: Cryptography & Network Security (CE-408)
Course Teacher: Ms. Rukaiya

Contact Info:

Room No: BS-02, CED

Email: [email protected]

1
 Definitions
• PLAINTEXT: An original message
• CIPHERTEXT: A coded/unintelligent/transformed/scrambled message
• ENCIPHERING/ENCRYPTION: The process of converting from
plaintext to ciphertext.
• DECIPHERING/DECRYPTION: Restoring the plaintext from the
ciphertext
• CRYPTOGRAPHY: The area of study of many schemes used for
encryption (crypto – secret graphy – writing)
• CRYPTOGRAPHIC SYSTEM/CIPHER: A scheme used for encryption
process
• CRYPTANALYSIS: Techniques used for deciphering a message without
any knowledge of the enciphering details (“breaking the code”)
• CRYPTOLOGY: The areas of cryptography and cryptanalysis

2
Figure: Simplified Model of Symmetric Encryption

3
 Symmetric Cipher Model

• There are two requirements for secure use of

conventional encryption:

1. A strong encryption algorithm

2. Sender and receiver must have obtained copies of the

secret key in a secure fashion and must keep the key
secure

4
 ^
X
Cryptanalyst
^
K

Message X Encryption Decryption X

Destination
Source Algorithm Y = E(K, X) Algorithm

Secure Channel
Key
Source

Figure: Model of Symmetric Cryptosystem

Figure 3.2 Model of Symmetric Cryptosystem

5
 Cryptographic Systems
• Characterized along three independent dimensions

The type of operations

The number of keys The way in which the
used for transforming
used plaintext is processed
plaintext to ciphertext

Symmetric,
single-key,
Substitution secret-key, Block cipher
conventional
encryption

Asymmetric,
two-key, or
Transposition Stream cipher
public-key
encryption

6
 Cryptanalysis and Brute-force Attack

Cryptanalysis
• Attack relies on the nature of the algorithm plus some knowledge
of the general characteristics of the plaintext

• Attack exploits the characteristics of the algorithm to attempt to

deduce a specific plaintext or to deduce the key being used

Brute-force attack
• Attacker tries every possible key on a piece of ciphertext until
an intelligible translation into plaintext is obtained

• On average, half of all possible keys must be tried to achieve

success

7
Types of Attacks on Encrypted Messages

e.g., Headers/preambles, copyright information

e.g., Hashing can prevent it

8
 Encryption Scheme Security
• The users of an encryption algorithm can strive for is an
algorithm that meets following criteria:
• Unconditionally secure
 No matter how much time an opponent has, it is impossible
for him or her to decrypt the ciphertext simply because the
required information is not there
• Computationally secure
 The cost of breaking the cipher exceeds the value of the
encrypted information
 The time required to break the cipher exceeds the useful
lifetime of the information
 E.g., OTP (One Time Pad)

9
 Brute-Force Attack

Involves trying every possible key until an

intelligible translation of the ciphertext into
plaintext is obtained

On average, half of all possible keys must be

tried to achieve success

To supplement the brute-force approach, some

degree of knowledge about the expected plaintext
is needed, and some means of automatically
distinguishing plaintext from garble is also
needed

10
Key Strength

Key Size (bits) No. of alternative Time required at

Keys 𝟏𝟎𝟔 Decryption
32 232 = 4.3 × 109 2.15 msec
56 256 = 7.2 × 1016 10 hrs
128 2128 = 3.4 × 1038 5.4 × 1018 years
168 2168 = 3.7 × 1050 5.9 × 1030 years

11
 Strong Encryption
• It refers to encryption schemes that make it impractically difficult
for unauthorized persons or systems to gain access to plaintext
that has been encrypted

• Properties that make an encryption algorithm strong are:

 Appropriate choice of cryptographic algorithm
 Use of sufficiently long key lengths
 Appropriate choice of protocols
 A well-engineered implementation
 Absence of deliberately introduced hidden flaws

12
Classical Cryptographic
Techniques

13
 Substitution Technique

• Is one in which the letters of plaintext are replaced by other

letters or by numbers or symbols
• If the plaintext is viewed as a sequence of bits, then
substitution involves replacing plaintext bit patterns with
ciphertext bit patterns

14
 Caesar Cipher

• Simplest and earliest known use of a substitution cipher

• Used by Julius Caesar about 2000 years ago
• Involves replacing each letter of the alphabet with the letter standing
three places further down the alphabet
• Alphabet is wrapped around so that the letter following Z is A
General Algorithm
Encryption: A shift may be of any amount, so that the general
Caesar algorithm is:
𝑪 = 𝑬 𝒌, 𝒑 = 𝒑 + 𝒌 𝒎𝒐𝒅 𝟐𝟔
Decryption: Where k takes on a value in the range 1 to 25; the
decryption algorithm is simply:
P= 𝑫 𝒌, 𝑪 = 𝑪 − 𝒌 𝒎𝒐𝒅 𝟐𝟔
15
 Caesar Cipher
• Mathematically give each letter a number
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
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

• Can define transformation as (k=3):

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

• Algorithm can be expressed as:

c = E(3, p) = (p + 3) mod (26)

Example:
plain: meet me after the toga party
cipher: PHHW PH DIWHU WKH WRJD SDUWB

16
 Caesar Cipher
Activity #01:
plain: SSUET
cipher: ?????

Activity #02:
cipher: L FDPHL VDZL FRQTXHUHG
plain: ??????

17
 Brute-force Cryptanalysis of Caesar Cipher
PHHW PH DIWHU WKH WR JD SDUWB
KEY
1 oggv og chvgt vjg vqic rctva
2 nffu nf bgufs uif uphb qbsuz
3 meet me after the toga party
4 ldds ld zesdq sgd snfz ozqsx
5 kccr kc ydrcp rfc rmey nyprw
Three important characteristics of this 6 jbbq jb xcqbo qeb qldx mxoqv
7 iaap ia wbpan pda pkcw lwnp u
problem enabled us to use a brute-force
8 hzzo hz vaozm ocz ojbv kvmot
cryptanalysis: 9 gyyn gy uznyl nby niau julns
10 fxxm fx tymxk max mhzt itkmr
1. The encryption and decryption algorithms 11 ewwl ew sxlwj lzw lgys hsjlq
are known. 12 dvvk dv rwkvi kyv kfxr grikp
2. There are only 25 keys to try. 13 cuuj cu qvjuh jxu jewq fqhjo
14 btti bt puitg iwt idvp epgin
3. The language of the plaintext is known
15 assh as othsf hvs hcu o dofhm
and easily recognizable
16 zrrg zr nsgre gur gbtn cnegl
17 yqqf yq mrfqd ftq fasm bmdfk
18 xppe xp lqepc esp ezrl alcej
19 wood wo kpdob dro dyqk zkbdi
20 vnnc vn jocna cqn cxpj yjach
21 ummb um inbmz bpm bwoi xizbg
22 tlla tl hmaly aol avnh whyaf
23 skkz sk glzkx znk zumg vgxze
24 rjjy rj fkyjw ymj ytlf ufwyd

18
25 qiix qi ejxiv xli xske tevxc

Figure
(This 3.3can
chart Brute-Force Cryptanalysis
be found on of Caesar
page 71 in the Cipher
textbook)
TASK
• Break Cipher
GCUA VQ DTGCM

19
Sample Compressed Text

Figure: Sample of Compressed Text

20
 Monoalphabetic Cipher
• Permutation
 Of a finite set of elements S is an ordered sequence of all the elements of S ,
with each element appearing exactly once
 For example,
if S = {a, b, c}, there are six permutations of S : abc, acb, bac, bca, cab, cba

 In general, there are n ! permutations of a set of n elements, because the first

element can be chosen in one of n ways, the second in n - 1 ways, the third in n -
2 ways, and so on.

 If the “cipher” line can be any permutation of the 26 alphabetic characters, then
there are 26! or greater than 4 x 1026 possible keys

 Approach is referred to as a monoalphabetic substitution cipher because a

single cipher alphabet is used per message

21
 Monoalphabetic Cipher
• Example
 OPEN ALPHABET: A B C D E F G H I J K L M N O P Q R S
TUVWXYZ
 KEYWORD: K E Y W O R D

 Mapping of keyword with the alphabets.

ABCD EFGHIJKLMNOPQRSTUVWXYZ
KEYWORDABCFGHIJLMNPQSTUVXZ

PLAINTEXT: A L K I N D I

Plaintext: A L K I N D I
Ciphertext: K G F B I W B

22
Cryptanalysis of Monoalphabetic Cipher

Figure: Relative Frequency of Letters in English Text

23
 Cryptanalysis of Monoalphabetic Cipher
Example:
UZQSOVUOHXMOPVGPOZPEVSGZWSZOPFPESXUDBMETSXAIZ
VUEPHZHMDZSHZOWSFPAPPDTSVPQUZWYMXUZUHSX
EPYEPOPDZSZUFPOMBZWPFUPZHMDJUDTMOHMQ

Step #01: Determine relative frequency of the letters can be determined and compared to
a standard frequency distribution for English

• In any case, the relative frequencies of the letters in the ciphertext (in percentages) are
as follows:
P 13.33 H 5.83 F 3.33 B 1.67 C 0.00 Z 11.67 D 5.00 W 3.33
G 1.67 K 0.00 S 8.33 E 5.00 Q 2.50 Y 1.67 L 0.00 U 8.33
V 4.17 T 2.50 I 0.83 N 0.00 O 7.50 X 4.17 A 1.67 J 0.83
R 0.00 M 6.67

Step #02 After Comparing this breakdown, it seems likely P and Z = e and t, but it is not
certain which is which.

S, U, O, M, and H are all of relatively high frequency and probably correspond to plain
letters from the set {a, h, i, n, o, r, s}.

The letters with the lowest frequencies (namely, A, B, G, Y, I, J) are likely included in the
set {b, j, k, q, v, x, z}.
24
 Cryptanalysis of Monoalphabetic Cipher
• Easy to break because they reflect the frequency data of the original
alphabet

• Countermeasure is to provide multiple substitutes (homophones) for a

single letter

• Digram
 Two-letter combination
 Most common is th

• Trigram
 Three-letter combination
 Most frequent is the

25
 Cryptanalysis of Monoalphabetic Cipher
• Ciphertext: UZQSOVUOHXMOPVGPOZPEVSGZWSZOPFPESXUDBMETSXAIZ

• The most common digram is ZW, which appears three times. So we make the
correspondence of Z with t and W with h. Then, by our earlier hypothesis, we can
equate P with e.

• Now notice that the sequence ZWP appears in the ciphertext, and we can translate
that sequence as “the.” This is the most frequent trigram (three-letter combination)

• Next, notice the sequence ZWSZ in the first line. We do not know that these four
letters form a complete word, but if they do, it is of the form th_t. If so, S equates
with a.

UZQSOVUOHXMOPVGPOZPEVSGZWSZOPFPESXUDBMETSXAIZ’

t a e e te a that e e a a

VUEPHZHMDZSHZOWSFPAPPDTSVPQUZWYMXUZUHSX

e t ta t ha e ee a e th t a

EPYEPOPDZSZUFPOMBZWPFUPZHMDJUDTMOHMQ

e e e tat e the t
26
 Playfair Cipher

• Best-known multiple-letter encryption cipher

 Encrypts multiple letters instead of single letter at a time

• Treats digrams in the plaintext as single units and translates

these units into ciphertext digrams
• Based on the use of a 5 x 5 matrix of letters constructed using a
keyword
• Invented by British scientist Sir Charles Wheatstone in 1854
• Developed for telegraph (communication/cable/wire) secrecy
• Used as the standard field system by the British Army in World
War I and the U.S. Army and other Allied forces during World
War II.

27
 Playfair Cipher
Example:
Plaintext: BALLOON
Key: MONARCHY

1. Construct the matrix by filling in the letters of the keyword and remaining
letters in alphabetical order. The letters I and J count as one letter.

2. Break the plaintext into pairs.

3. Repeating plaintext letters that are in same pair are separated with filler
letter.

BA LX LO ON
28
 Playfair Cipher
4. Look into the matrix for the pair encryption,
5. Two PT letter fall in same column are replaced with the letter beneath
them
BA LX LO ON
I/J B

6. The PT letter lies in different row and column are replaced by letter lies
at the intersection of them (same row and column)
BA LX LO ON
I/J B SU PM

7. Two PT letter fall in same row are replaced with the letter on right side
BA LX LO ON
I/J B SU PM NA

29
Playfair Cipher
Activity #03

Plaintext = COME TO OFFICE

KEY = SECRET

30
Cryptanalysis of Playfair Cipher
• Security much improved over monoalphabetic since have 26 ×
26 = 676 digrams.

• Would need a 676 entry frequency table to analyze (verses 26

for a monoalphabetic) and corresponding more ciphertext

• Was widely used for a many years

• E.g. by US & British military in WWI

• Relatively easy to break, because it leaves much of the

structure of the plaintext language intact. A few hundred
letters of ciphertext are generally sufficient.

31
 Hill Cipher
• Developed by the mathematician Lester Hill in 1929

• Takes m successive PT letters (p1,p2,…pm) and

substitute with an CT (c1,c2,… cm).

• Each character is represented by a numerical value

0,….. 25, computes in matrix operation

Encryption: C = K P mod 26
Decryption: P = 𝐾 −1 C mod 26

Where, 𝐾 −1 = inverse of K
K(𝐾 −1 )=1 mod 26

32
 Hill Cipher

Example
Plaintext: ATTACK
Key: CDDG

33
Hill Cipher

34
Hill Cipher

35
Hill Cipher

36
 Hill Cipher
Finding 𝑲−𝟏

• Suppose

If |A|=0, inverse does not exist.

𝐴𝑑𝑗 𝑜𝑓 𝐴
Inverse of A = 𝐴−1 = Hence, can be used for encryption
|𝐴| But not decryption. Such keys are
Called weak keys
• For |A| = (5 × 3) – (8 × 17)
= 15 – 136
= -121 mod 26
=9

3 −8
−17 5
• For Adj of A =
9

37
 Hill Cipher
Finding Modular Inverse

5 is the modular inverse of 3 mod 7 since 5*3 mod 7 = 1

38
 Hill Cipher
Finding Inverse

Plaintext ?????

39
 Hill Cipher
Finding |A| of 3 × 3 Matrix
Suppose
0 11 15
A= 7 0 1
4 19 0

0 1 7 1 7 0
|A|=0 − 11 + 15
19 0 4 0 4 19

= 11 mod 26

Practice Question:
Plaintext = THEY ARE GOING TO ATTEND CONFERENCE
5 6
Key =
2 3
Perform encryption and decryption both

40
 Hill Cipher

• Strength is that it completely hides single-letter

frequencies
• The use of a larger matrix hides more frequency information
• A 3 x 3 Hill cipher hides not only single-letter but also two-letter
frequency information

Cryptanalysis of Hill Cipher

• Strong against a ciphertext-only attack but easily

broken with a known plaintext attack

41
Polyalphabetic Cipher

• Polyalphabetic substitution cipher

• Improves on the simple monoalphabetic technique by using
different monoalphabetic substitutions as one proceeds
through the plaintext message

All these techniques have the following features

in common:
• A set of related monoalphabetic substitution
rules is used

• A key determines which particular rule is

chosen for a given transformation

42
 Polyalphabetic Cipher

• For the next m letters of the plaintext, the key letters are
repeated.
• This process continues until all of the plaintext sequence
is encrypted.
• A general equation of the encryption process is

• Compare this with the Caesar cipher. In essence, each

plaintext character is encrypted with a different Caesar
cipher

• Similarly, A general equation of the decryption process is

43
 Polyalphabetic Cipher
• Repeat the key from start after end of the key is reached

Example: Suppose that a polyalphabetic cipher of period 3 is

being used with 3 monoalphabetic ciphers 𝑀1 , 𝑀2 , and 𝑀3 defined
as
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
𝑀1 K D N H P A W X C Z I M Q J B Y E T U G V R F O S L
𝑀2 P A G U K H J B Y D S O E M Q N W F Z I T C V L X R
𝑀3 J M F Z R N L D O W G I A K E S U C Q V H Y X T P B
Plaintext: now is the time for every good man
123 12 312 3123 123 12312 3123 123
Ciphertext: JQX ………….

• Note: for instance, two letters ‘oo’ in ‘good’ are encrypted as

different letters

• Makes cryptanalysis harder since have more alphabets to

guess and flatten frequency distribution 44
 Vigenère Cipher

• Best known and one of the simplest polyalphabetic

substitution ciphers

• In this scheme the set of related monoalphabetic

substitution rules consists of the 26 Caesar ciphers with
shifts of 0 through 25

45
 Example of Vigenère Cipher

• To encrypt a message, 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:
key: deceptivedeceptivedeceptive
plaintext: wearediscoveredsaveyourself

ciphertext: ZICVTWQNGRZGVTWAVZHCQYGLMGJ

Key 3 4 2 4 15 19 8 21 4 3 4 2 4 15
PT 22 4 0 17 4 3 8 18 2 14 21 4 17 4
CT 25 8 2 21 19 22 16 13 6 17 25 6 21 19

46
 Vigenère Cipher

• Strength of cipher is that there are multiple CT letters

for each PT letter. Thus, letter frequency distribution is
obscured.

• PT is encrypted and giving same cipher ‘red’ is encrypted

by VTW at a displacement of 9,one can find key is of
length 3 or 9. However, id message is long enough, there
will be a number of such repeated sequences.

47
 Vigenère Autokey System

• A keyword is concatenated with the plaintext itself to

provide a running key

• Example:
key: deceptivewearediscoveredsav
plaintext: wearediscoveredsaveyourself
ciphertext: ZICVTWQNGKZEIIGASXSTSLVVWLA

• Even this scheme is vulnerable to cryptanalysis

• Because the key and the plaintext share the same frequency
distribution of letters, a statistical technique can be applied

48
 Vernam Cipher
• Introduced by AT&T engineer named Gilbert Vernam.

• Ultimate defense against cryptanlaysis that is to choose a keyword

that is as long as PT and has no statistical relationship to it.

• It works on binary data rather than letters

Ci = Pi XOR K i
Pi = Ci XOR K i

• Although such a scheme with a long key presents formidable

cryptanalytic difficulties but can be broken sufficient CT, the use of
known portable PT
49
 One-Time Pad
• Improvement to Vernam cipher proposed by an Army Signal
Corp officer, Joseph Mauborgne

• Use a random key that is as long as the message so that the

key need not be repeated

• Key is used to encrypt and decrypt a single message and then

is discarded

• Each new message requires a new key of the same length as

the new message

• Scheme is unbreakable
• Produces random output that bears no statistical relationship to
the plaintext
• Because the ciphertext contains no information whatsoever about
the plaintext, there is simply no way to break the code

50
 Difficulties
• The one-time pad offers complete security but, in practice, has
two fundamental difficulties:
• There is the practical problem of making large quantities
of random keys
• Any heavily used system might require millions of random
characters on a regular basis
• Mammoth key distribution problem
• For every message to be sent, a key of equal length is needed
by both sender and receiver

• Because of these difficulties, the one-time pad is of limited

utility
• Useful primarily for low-bandwidth channels requiring very high
security

• The one-time pad is the only cryptosystem that exhibits perfect

secrecy (see Appendix F)

51
Transposition Ciphers

52
 Transposition Cipher

• Mapping is achieved by performing some sort of permutation

on the plaintext letters.

• Hid ethe message by rearranging the letter order without

altering the actual letters used.

• Scheme uses writing message in a rectangular row by row and

reading the message off column by column, but permute the
order of the columns

• Order of columns becomes the key to the algorithm

53
 Rail Fence Cipher
• Simplest transposition cipher

• Plaintext is written down as a sequence of diagonals and

then read off as a sequence of rows

• To encipher the message “meet me after the toga party”

with a rail fence of depth 2, we would write:
mematrhtgpry
etefeteoaat

Encrypted message is:

MEMATRHTGPRYETEFETEOAAT

54
 Rail Fence Cipher
Activity:
Plaintext = I CAME I SAW I CONQUERED
CT=???

• This sort of technique would be cryptanalyzed

55
 Row Transposition Cipher
• Is a more complex transposition
• Write the message in a rectangle, row by row, and read the
message off, column by column, but permute the order of the
columns
• The order of the columns then becomes the key to the algorithm

Key: 4312 5 67
Plaintext: atta c kp
ostpone
dunt i l t
w o a mx y z
Ciphertext: TTNAAPTMTSUOAODWCOIXKNLYPETZ

• Pure transposition cipher is easily recognized because it has the same

letter frequency as the original Plaintext. Digram and trigram frequency
tables can be useful
• Can be more secure by performing more than once stage of transposition.
The result will be more complex permutation that is not easily
reconstructed.
56
 Summary

• Present an overview of the main concepts of symmetric

cryptography
• Explain the difference between cryptanalysis and
brute-force attack
• Understand the operation of a monoalphabetic
substitution cipher
• Understand the operation of a polyalphabetic cipher
• Present an overview of the Hill cipher

57