B N M Institute of Technology

Department of Artificial Intelligence & Machine

Learning

Cryptography
Academic Year 2024-25
(Even)
Semester/ Section : 8th A & B

By:
Mrs. Kavya M S
Assistant Professor
Dept. of AIML
BNMIT
1
 Background
• Information Security requirements have changed in recent times
• Computer use requires automated tools to protect files and other stored
information
• Use of networks and communications links requires measures to protect
data during transmission
• Computer Security - generic name for the collection of tools designed
to protect data and to thwart hackers
• Network Security - measures to protect data during their transmission
• Internet Security - measures to protect data during their transmission
over a collection of interconnected networks

2
 Security Attack
• Any action that compromises the security of information owned by an
organization
• Information security is about how to prevent attacks, or failing that, to
detect attacks on information-based systems
• Threat & attack used to mean same thing
• Generic types of attacks
• Passive
• Active

3
Passive Attack

4
Active Attack

5
 Recent Cyber Attack
Top Cybersecurity Breaches
Thousands of cyber attacks were recorded through 2021, including ransomware,
cryptocurrency theft, data loss, and supply chain attacks. Insight from the
Identity Theft Research Center (ITRC) shows that recorded data breaches increased
by 17% in 2021 compared to 2020.

Tether Attack
In March 2021, cyber criminals threatened to leak documents from the Tether cryptocurrency. The
attackers claimed the data would “harm the Bitcoin ecosystem” and demanded a settlement fee
of around 500 Bitcoin ($24 million), but Tether refused to pay.
CNA Financial Breach
A ransomware attack on insurance firm CNA Financial left employees locked out of their systems
and blocked from accessing corporate resources. The attack in March 2021 also involved
company data being stolen, which led CNA Financial to reportedly pay the $40 million settlement
fee.
Facebook Cyberattack
Data of more than 530 million Facebook users, including their names, Facebook IDs, dates of
birth, and relationship status, was published online in April 2021. Facebook, now Meta, said the
6
 Security Services & Mechanism
• Services :
• Enhance security of data processing systems and information
transfers of an organization
• Intended to counter security attacks
• Using one or more security mechanisms
• Mechanism:
• Feature designed to detect, prevent, or recover from a security attack
• No single mechanism that will support all services required
• One particular element underlies many of the security mechanisms in
use:
• cryptographic techniques
• Hence our focus on this topic

7
Why Cryptography?
The Importance of Cryptography:
Individuals and organizations use
cryptography on a daily basis to
protect and keep their
conversations and data
confidential.

General Security Goals:

• Confidentiality
• Privacy
• Integrity
• Authentication
• Availability
• Non- Reputability.
8
Why Cryptography?

9
 Why Cryptography?

Integrity: Information integrity includes the accuracy, relevance, precision, timeliness and
completeness of the information
Authentication: It is the process of determining whether someone or something is, in fact, who
or what it says it is.
Data availability: It means that information is accessible to authorized users. It provides an
assurance that your system and data can be accessed by authenticated users whenever they're
needed.
Non-repudiation: It means that someone cannot falsely deny that they created, altered,
observed, or transmitted data.
10
Why Cryptography?

11
Why Cryptography?

12
 Why Cryptography?
 National Institute of Standards & Technology (NIST)
 Internet Society (ISOC)
 International Telecommunication Union Telecommunication
Standardization Sector (ITU-T)
 International Organization for Standardization (ISO)
 RSA Labs (de facto)

13
 Overview of Syllabus
Module 1: Classical Encryption Techniques
Chapter 2: Symmetric Cipher Model, Cryptography, Cryptanalysis and
Brute-Force Attack, Substitution Techniques, Caesar Cipher,
Monoalphabetic Cipher, Playfair Cipher, Hill Cipher, Polyalphabetic
Cipher, One Time Pad.
Chapter 3: Block Ciphers and the data encryption standard: Traditional
block Cipher structure, stream Ciphers and block Ciphers, Motivation for
the feistel Cipher structure, the feistel Cipher, The data encryption
standard, DES encryption, DES decryption, A DES example, results, the
avalanche effect, the strength of DES, the use of 56-Bit Keys, the nature
of the DES algorithm, timing attacks, Block cipher design principles,
number of rounds, design of function F, key schedule algorithm
Textbook 1: Ch. 2.1,2.2, Ch. 3
14
 Chapter 2
2.1 Symmetric Cipher Model
• Cryptography
• Cryptanalysis and Brute-Force Attack
2.2 Substitution Techniques
• Caesar Cipher
• Monoalphabetic Ciphers
• Playfair Cipher
• Hill Cipher
• Polyalphabetic Ciphers
• One-Time Pad

15
2.1 Symmetric Cipher Model

16
 Basic Terminologies
• Plaintext - original message
• Ciphertext - coded message
• Cipher - algorithm for transforming plaintext to ciphertext
• Key - info used in cipher known only to sender/receiver
• Encipher (encrypt) - converting plaintext to ciphertext
• Decipher (decrypt) - recovering ciphertext from plaintext
• Cryptography - study of encryption principles/methods
• Cryptanalysis (code breaking) - study of principles/ methods of
deciphering ciphertext without knowing key
• Cryptology - field of both cryptography and cryptanalysis
17
 Requirement
• Two requirements for secure use of conventional
encryption:
• Need of a strong encryption algorithm.
• Secret key known only to sender and receiver.
• Kerckhoff’s principle: Kerckhoff's principle is the
concept that a Cryptographic system should be designed
to be secure, even if all its details, except for the key, are
publicly known.
• Do not need to keep the algorithm secret; need to keep
only the key secret.

18
Requirement
• Plaintext: X = [X1, X2,..., XM].
• The M elements of X are letters in
finite alphabet of the 26 capital
letters.
• Binary alphabet {0, 1} is typically
used.
• Key : K = [K1, K2,..., KJ] is
generated.
• If the key is generated at the
source,
• Provided to the destination by
means of some secure channel.
• A third party could generate the
key deliver it to both source and
destination. 19
 Cryptography
Cryptographic systems are characterized along three
independent dimensions:
[Link] type of operations used for transforming plaintext to
ciphertext.
• Substitution: Each element in the plaintext (bit, letter, group of bits
or letters) is mapped into another element

• Transposition: Elements in the plaintext are rearranged.

20
 Cryptography

2. The number of keys

used.
• If both sender and receiver
use the same key, the
system is referred to as
symmetric, single-key,
secret-key, or
conventional encryption.

• If the sender and receiver

use different keys, the 21
 Cryptography
3. The way in which the
plaintext is processed.
• A stream cipher
processes the input
elements continuously,
producing output one
element at a time, as it
goes along.

• A block cipher processes

the input one block of
elements at a time, 22
 2.1 Symmetric Cipher Model
• Conventional / private-key / single-key
• Sender and recipient share a common key
• All classical encryption algorithms are private-key
• Only type prior to invention of public-key in 1970’s
• Far most widely used

23
 Cryptanalysis and Brute-Force Attack
The are two general approaches to attacking a conventional
encryption scheme:
• Cryptanalysis: Cryptanalytic attacks rely
• Algorithm
• Some knowledge of the plaintext
• sample plaintext–ciphertext pairs.

• Brute-force attack: The 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.

24
 Cryptanalytic Techniques

ciphertext only
only know algorithm & ciphertext, is statistical,
know or can identify plaintext
known plaintext
know/suspect plaintext & ciphertext
chosen plaintext
select plaintext and obtain ciphertext
chosen ciphertext
select ciphertext and obtain plaintext
chosen text
select plaintext or ciphertext to en/decrypt
25
Cryptanalytic Techniques

26
 Cryptanalytic Techniques
• Ciphertext-only attack is the easiest to defend.
• Known Plaintext:
• The analyst may be able to capture one or more plaintext
messages as well as their encryptions.
• The analyst may know that certain plaintext patterns will appear
in a message.
• For example:
• A file that is encoded in the Postscript format always begins with
the same pattern
• A standardized header or banner to an electronic funds transfer
message.
• In an accounting file the opponent may know the placement of
certain key words.
• The source code for a program
• chosen-plaintext attack If the analyst is able somehow to get the
27
 Cryptanalytic Techniques
Two more definitions:
1. unconditional security
no matter how much computer power or time is available, the
cipher cannot be broken since the ciphertext provides
insufficient information to uniquely determine the
corresponding plaintext
2. computational security
An encryption algorithm can strive if it meets one or both of the
following criteria:
• 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 28
 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.
• That is, if there are X different keys, on average an attacker would
discover the actual key after X/2 tries.
• If the message is just plain text in English, then the result pops out
easily, although the task of recognizing English would have to be
automated.
• If the text message has been compressed before encryption, then
recognition is more difficult.

29
 2.2 Substitution Techniques
• A 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.
1. Caesar Cipher
• Substitution Techniques:2. Monoalphabetic Ciphers
3. Playfair Cipher
4. Hill Cipher
5. Polyalphabetic Ciphers
6. One-Time Pad
30
 [Link] Cipher
• Earliest known and easy to use substitution cipher
• By Julius Caesar
• First attested use in military affairs
• Replaces each letter by 3rd letter on example:
meet me after the toga party
PHHW PH DIWHU WKH WRJD SDUWB
• Alphabet is wrapped around, so that the letter following Z is A.

31
[Link] Cipher

32
 [Link] Cipher
Plain : 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
cipher: 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

then have Caesar cipher as:

c = E(p) = (p + k) mod (26)
p = D(c) = (c – k) mod (26)
33
 [Link] Cipher

Three important characteristics of this problem enabled

us to use a bruteforce cryptanalysis:
1. The encryption and decryption algorithms are known.
2. There are only 25 keys to try.
3. The language of the plaintext is known and easily
recognizable

34
 [Link] Cipher
Figure 2.3 shows the results of applying this strategy
to the example ciphertext. In this case, the plaintext
leaps out as occupying the third line.
What generally makes brute-force cryptanalysis
impractical is the use of an algorithm that employs a
large number of keys. For example, the triple DES
algorithm, makes use of a 168-bit key, giving a key
space of 2168 or greater than 3.7 * 1050 possible keys

35
 1. Caesar Cipher
• What generally makes brute-force cryptanalysis impractical
• An algorithm that employs a large number of keys.
• For example, the triple DES algorithm, makes use of a 168-bit
key
• If the language of the plaintext is unknown, then plaintext
output may not be recognizable.

36
 2. Monoalphabetic Cipher
• With only 25 possible keys, the Caesar cipher is far from secure.
• A increase in the key space can be achieved by allowing an arbitrary
substitution.
• In monoalphabetic substitution cipher, because a single cipher alphabet
(mapping from plain alphabet to cipher alphabet) is used per message.
• Shuffle the alphabet arbitrarily
• Each plain text letter maps to different random cipher text letter.
• Thus key is 26 letters long.

37
 2. Monoalphabetic Cipher
As a first step, the
relative frequency
of the letters can be
determined and
compared to a
standard frequency
distribution for
English, such as is
shown inFigure 2.5

38
 2. Monoalphabetic Cipher
The ciphertext to be solved is
UZQSOVUOHXMOPVGPOZPEVSGZWSZOPFPESXUDBMETSXAIZ
VUEPHZHMDZSHZOWSFPAPPDTSVPQUZWYMXUZUHSX
EPYEPOPDZSZUFPOMBZWPFUPZHMDJUDTMOHMQ
If the message were long enough, this technique alone might be sufficient, but because this is a
relatively short message, we cannot expect an exact [Link] relative frequencies of the letters
in the ciphertext (in percentages) are as follows:

Comparing this breakdown with Figure 2.5,

• it seems likely that cipher letters P and Z are the equivalents of plain letters e
and t, but it is not
• The letters 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 39
 2. Monoalphabetic Cipher
• Try to make some tentative assignments and start to fill in the plaintext to see if it
looks like a reasonable “skeleton” of a message.
• A powerful tool is to look at the frequency of two-letter combinations, known as
digrams.
• The most common such digram is th.
• In our ciphertext, 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) in
English.
• 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.
40
 2. Monoalphabetic Cipher

The complete plaintext, with spaces added between words, follows:

it was disclosed yesterday that several informal but
direct contacts have been made with political
representatives of the viet cong in moscow

41
 2. Monoalphabetic Cipher

Monoalphabetic ciphers are easy to break because they reflect the

frequency data of the original alphabet.
42
 3. Playfair Cipher
• The best-known multiple-letter encryption cipher is the Playfair, which
treats digrams in the plaintext as single units and translates these
units into ciphertext digrams.
• The Playfair algorithm is based on the use of a 5 * 5 matrix of letters
constructed using a keyword
• Keyword is monarchy.
• The matrix is constructed by filling in the letters of
the keyword (minus duplicates) from left to right and
from top to bottom, and then filling in the remainder
of the matrix with the remaining letters in alphabetic
43
order.
 3. Playfair Cipher
Plaintext is encrypted two letters at a time, according to the following rules:
1. Repeating plaintext letters that are in the same pair are separated with a filler letter, such as
x, so that balloon would be treated as ba lx lo on.
2. Two 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. Two plaintext letters that fall in the same column are each replaced by the letter beneath,
with the top element of the column circularly following the last. For example, mu is encrypted
as CM.
4. Otherwise, each plaintext letter in a pair 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).

44
3. Playfair Cipher

45
 3. Playfair Cipher
If both the letters are in the same column: Take the letter below each one
(going back to the top if at the bottom). For example:
Diagraph: "me"
Encrypted Text: cl
Encryption: m -> c e -> l

If both the letters are in the same row: Take the letter to the right of each one (going back to the leftmost
if at the rightmost position). For example:
Diagraph: "st"
Encrypted Text: tl
Encryption: s -> t t -> l

If neither of the above rules is true: Form a rectangle with the two letters and take the letters on the
horizontal opposite corner of the rectangle. For example:
Diagraph: "nt"
Encrypted Text: rq
Encryption: n -> r t -> q
46
 3. Playfair Cipher
Plain Text: "instrumentsz“
After Split: 'in' 'st' 'ru' 'me' 'nt' 'sz'
Encrypted Text:
Encryption:

47
 3. Playfair Cipher
Plain Text: "instrumentsz"
After Split: 'in' 'st' 'ru' 'me' 'nt' 'sz'
Encrypted Text:
Encryption:
i -> g
n -> a
s -> t
t -> l
r -> m
u -> z
m -> c
e -> l
n -> r
t -> q
s -> t
z -> x

48
 3. Playfair Cipher
Plain Text: "instrumentsz"
After Split: 'in' 'st' 'ru' 'me' 'nt' 'sz’
Encrypted Text: gatlmzclrqtx
Encryption:
i -> g
n -> a
s -> t
t -> l
r -> m
u -> z
m -> c
e -> l
n -> r
t -> q
s -> t
z -> x

49
 3. Playfair Cipher
• Analysis of Playfair:
• Security much improved over monoalphabetic
• Since have 26 x 26 = 676 digrams
• Need a 676 entry frequency table to analyse (verses 26 for a
monoalphabetic)
• Widely used for many years eg. by US & British military
• It can be broken, given a few hundred letters since still has much
of plaintext structure

50
 4. Hill Cipher
• Another interesting Multiletter cipher is the Hill cipher, developed by the
mathematician Lester Hill in 1929.

51
 4. Hill Cipher
This encryption algorithm takes m successive plaintext letters and
substitutes for them m ciphertext letters. The substitution is
determined by m linear equations in which each character is
assigned a numerical value (a = 0, b = 1, c, z = 25).

52
4. Hill Cipher Encryption

53
4. Hill Cipher Encryption Example

54
4. Hill Cipher Encryption Example

55
4. Hill Cipher Encryption Example

56
4. Hill Cipher Encryption Example

57
4. Hill Cipher Encryption Example

58
4. Hill Cipher Encryption Example

59
4. Hill Cipher Encryption Example

60
4. Hill Cipher Encryption Example

61
4. Hill Cipher Decryption

62
4. Hill Cipher Decryption

63
4. Hill Cipher Decryption Example

64
 4. Hill Cipher Decryption Example

Repeat 1st 2 columns

65
4. Hill Cipher Decryption Example

Repeat 1st 2 rows

Cancel 1st row and column

66
4. Hill Cipher Decryption Example

67
4. Hill Cipher Decryption Example

68
4. Hill Cipher Decryption Example

69
4. Hill Cipher Decryption Example

70
4. Hill Cipher Decryption Example

71
4. Hill Cipher Decryption Example

72
4. Hill Cipher Decryption Example

73
4. Hill Cipher Decryption Example

74
 4. Hill Cipher Practice Problem

Encrypt and Decrypt the following plaintext to

ciphertext using Hill Cipher Method
Plaintext: HELP
Key: 3 3 5 -3
2 5 -2 3
Det=9
Adj= d -b=
-c a
K-1=15 17
20 9

75
 5. Polyalphabetic Ciphers
• Use different monoalphabetic substitutions as one proceeds through
the plaintext message.
• The general name for this approach is polyalphabetic substitution
cipher. All these techniques have the following features in
common:
1. A set of related monoalphabetic substitution rules is used.
2. A key determines which particular rule is chosen for a given
transformation.

76
 5. Polyalphabetic-Vigenere Ciphers

1. Vigenère cipher
Assume a sequence of plaintext letters P = p0, p1, p2, c, pn-1
and a key consisting of the sequence of letters K = k0, k1, k2, c, km-1, where
typically m < n.
The sequence of ciphertext letters C = C0, C1, C2, c, Cn-1 is calculated as
follows:
C = C0, C1, C2, c, Cn-1 = E(K, P) = E[(k0, k1, k2, c, km-1), (p0, p1, p2, c, pn-1)]
= (p0 + k0) mod 26, (p1 + k1) mod 26, c, (pm-1 + km-1) mod 26,
(pm + k0) mod 26, (pm+1 + k1) mod 26, c, (p2m-1 + km-1) mod 26, c

77
5. Polyalphabetic-Vigenere Ciphers

Encryption: C = (p + k ) mod
i i i mod m

26
Decryption: p = (C - k ) mod 26
i i i mod m

78
 5. Polyalphabetic-Vigenere Ciphers

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
79
 5. Polyalphabetic-Vigenere Ciphers

key: deceptivedeceptivedeceptive
plaintext: wearediscoveredsaveyourself
ciphertext: ZICVTWQNGRZGVTWAVZHCQYGLMGJ

80
5. Polyalphabetic-Vigenere Ciphers

81
 5. Polyalphabetic-Vigenere Ciphers
• The strength of this cipher is that there are multiple
ciphertext letters for each plaintext letter, one for each
unique letter of the keyword.
• An improvement is achieved over the Playfair cipher, but
considerable frequency information remains.
• If Vigenère cipher is suspected, then progress depends on
determining the length of the keyword.
• How the keyword length can be determined.
• If two identical sequences of plaintext letters occur at a
distance that is an integer multiple of the keyword length,
key:
they will deceptivedeceptivedeceptive
generate identical ciphertext sequences.
plaintext: wearediscoveredsaveyourself
ciphertext: ZICVTWQNGRZGVTWAVZHCQYGLMGJ 82
 5. Polyalphabetic-Vigenere Ciphers
• The periodic nature of the keyword can be eliminated by
using a nonrepeating keyword that is as long as the
message itself.
• Vigenère proposed what is referred to as an autokey
system, in which a keyword is concatenated with the
plaintext itself to provide a running key.
For our example,
key: deceptivewearediscoveredsav
plaintext: wearediscoveredsaveyourself
ciphertext: ZICVTWQNGKZEIIGASXSTSLVVWLA

83
 5. Polyalphabetic-Vigenere Ciphers
Practice Problem
1. Encrypt and Decrypt the following plaintext to Ciphertext using Vigenere
Cipher method
Plain Text: ALL IS WELL
KEYWORD: CAKE
2. Encrypt and Decrypt the following plaintext to Ciphertext using Vigenere
Cipher method
Plain Text: MICHIGAN TECHNOLOGICAL UNIVERSITY
keyword : HOUGHTON

84
 5. Polyalphabetic -Vernam Cipher
• The ultimate defense against such a cryptanalysis is to
choose a keyword that is as long as the plaintext and has
no statistical relationship to it.
• Such a system was introduced by an AT&T engineer
named Gilbert Vernam in 1918.

85
 5. Polyalphabetic -Vernam Cipher

His system works on binary data (bits) rather than letters. The
system can be expressed
ci = pi XOR ki, Where
pi = ith binary digit of plaintext, ki = ith binary digit of key, ci
= ith binary digit of ciphertext
pi = ci XOR ki 86
 5. Polyalphabetic -Vernam Cipher
Plain-Text: O A K
Key: SON
O ==> 14 = 0 1 1 1 0
S ==> 18 = 1 0 0 1 0
Bitwise XOR Result: 1 1 1 0 0 = 28
Since the resulting number is greater than 26, subtract 26
from it.
Then convert the Cipher-Text character number to the Cipher-
Text character.

28 - 26 = 2 ==> C
CIPHER-TEXT: C
Similarly, do the same for the other corresponding 87
 5. Polyalphabetic -Vernam Cipher

PT: O A K
No: 14 00 10

KEY: S O N
No: 18 14 13
New Cipher-Text is after getting the corresponding character
from the resulting number.

CT-No: 02 14 07
CT: C O H

88
 5. Polyalphabetic -Vernam Cipher
Practice Problem
1. Encrypt and Decrypt the following plaintext to Ciphertext using Vernam
Cipher method
Plain-Text: RAMSWARUPK
Key: RANCHOBABA

89
 6. One-Time Pad
• An Army Signal Corp officer, Joseph Mauborgne, proposed an
improvement to the Vernam cipher that yields the ultimate in
security.
• Use random key that is as long as the message, so that the
key need not be repeated.
• Key is to be 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.
• Such a scheme is known as a one-time pad, is unbreakable.
• It produces random output that bears no statistical
relationship to the plaintext.
90
6. One-Time Pad

91
 6. One-Time Pad

We now show two different decryptions using two different

keys:
ciphertext:
ANKYODKYUREPFJBYOJDSPLREYIUNOFDOIUERFPLUYTS
key: pxlmvmsydofuyrvzwc tnlebnecvgdupahfzzlmnyih
plaintext: mr mustard with the candlestick in the hall
ciphertext:
ANKYODKYUREPFJBYOJDSPLREYIUNOFDOIUERFPLUYTS
key: pftgpmiydgaxgoufhklllmhsqdqogtewbqfgyovuhwt
plaintext: miss scarlet with the knife in the library
Suppose that a cryptanalyst had managed to find these two keys.
Two plausible plaintexts are produced.
There is no way to decide which key is correct and therefore which
plaintext is correct.
92
 6. One-Time Pad
The security of the one-time pad is entirely due to the randomness of the key.
If the stream of characters that constitute the key is truly random, then the
stream of characters that constitute the ciphertext will be truly random.
The one-time pad offers complete security but, in practice, has two
fundamental difficulties:
1. There is the practical problem of making large quantities of random keys.
2. Key distribution is very difficult.

93
 6. One-Time Pad

1 a. Encrypt the plaintext sendmoremoney with the key stream

9 0 1 7 23 15 21 14 11 11 2 8 9
b. Using the ciphertext produced in part (a), find a key so that the cipher
text decrypts to the plaintext cashnotneeded.

94
 Chapter 3
Block Ciphers and Data Encryption Standards

95
3.1 Traditional Block Cipher Structure

96
3.1 Traditional Block Cipher Structure

97
Motivation for the Feistel Cipher Structure

99
Motivation for the Feistel Cipher Structure

100
 Motivation for the Feistel Cipher Structure

Ideal block cipher, If a small block size, such as n = 4, is

used, then the system is equivalent to a classical substitution
Vulnerable to a statistical analysis of the plaintext.

101
 The Feistel Cipher

Feistel proposed method that can approximate the ideal block

cipher by utilizing the concept of a product cipher, which is the
execution of two or more simple ciphers in sequence in such a way
that the final result or product is cryptographically stronger than
any of the component ciphers.

102
 The Feistel Cipher
In particular, Feistel proposed the use of a cipher that alternates
substitutions
and permutations, where these terms are defined as follows:
• Substitution: Each plaintext element or group of elements is
uniquely replaced by a corresponding ciphertext element or
group of elements.
• Permutation: A sequence of plaintext elements is replaced
by a permutation
of that sequence. That is, no elements are added or deleted or
replaced in the
sequence, rather the order in which the elements appear in the
sequence is
changed. 103
 The Feistel Cipher

In fact, Feistel’s is a practical application of a

proposal by Claude Shannon to develop a product
cipher that alternates confusion and diffusion
•functions
In diffusion, the statistical structure of the plaintext is
dissipated into long-range statistics of the ciphertext.
• Each plaintext digit affect the value of many ciphertext
digits;
• An example of diffusion is to encrypt a message M = m1, m2,
m3, . . . of characters with an averaging operation:

adding k successive letters to get a ciphertext letter y . n

104
 The Feistel Cipher
• Confusion seeks to make the relationship
between the statistics of the ciphertext and the
value of the encryption key complex. This is
achieved by the use of a complex substitution
algorithm. In contrast, a simple linear
substitution function would add little confusion.

105
 Feistel Cipher Structure
• The left-hand side of Figure 3.3 depicts the structure proposed by
Feistel.
• The inputs to the encryption algorithm are a plaintext block of length
2w bits and a key K.
• The plaintext block is divided into two halves, L0 and R0.
• The two halves of the data pass through n rounds of processing and
then combine to produce the ciphertext block.
• Each round i has as inputs Li-1 and Ri-1 derived from the previous
round, as well as a subkey Ki derived from the overall K.
• In general, the subkeys Ki are different from K and from each other.
• For clarity, we use the notation LEi and REi for data traveling through
the encryption algorithm and LDi and RDi for data traveling through the
decryption algorithm. 106
 Feistel Cipher Structure
• A substitution is performed on the left half of the data. This is done by
applying a round function F to the right half of the data and then taking
the exclusive-OR of the output of that function and the left half of the
data.
• The round function has the same general structure for each round but
is parameterized by the round subkey Ki.
• Another way to express this is to say that F is a function of right-half
block of w bits and a subkey of y bits, which produces an output value
of length w bits: F(REi, Ki+1).
• Following this substitution, a permutation is performed that consists of
the interchange of the two halves of the data. This structure is a
particular form of the substitution-permutation network (SPN) proposed
by Shannon. 107
Feistel Cipher Structure- Encryption

108
Feistel Cipher Structure- Decryption

109
Feistel Cipher Structure

110
 Feistel Decryption Algorithm
• The process of decryption with a Feistel cipher is essentially the same
as the encryption process.
• The rule is as follows:
• Use the ciphertext as input to the algorithm, but use the subkeys Ki in
reverse order.
• That is, use Kn in the first round, Kn-1 in the second round, and so on,
until K1 is used in the last round.
• This is a nice feature, because it means we need not implement two
different algorithms; one for encryption and one for decryption.

111
 Feistel Cipher Structure
The exact realization of a Feistel network depends on the choice of the following
parameters and design features:
• Block size:
• Larger block sizes mean greater security. but reduce encryption/decryption
speed for a given algorithm
• Traditionally, a block size of 64 bits has been considered a reasonable
tradeoff and was nearly universal in block cipher design.
• However, the new AES uses a 128-bit block size.
• Key size:
• Larger key size means greater security but may decrease encryption/
decryption speed.
• Key sizes of 64 bits or less are now widely considered to be inadequate, and
128 bits has become a common size. 112
 Feistel Cipher Structure

• Number of rounds: The essence of the Feistel cipher is

that a single round offers inadequate security but that
multiple rounds offer increasing security. A typical size is
16 rounds.
• Subkey generation algorithm: Greater complexity in
this algorithm should lead to greater difficulty of
cryptanalysis.
• Round function F: Again, greater complexity generally
means greater resistance to cryptanalysis.

113
 Feistel Cipher Structure
There are two other considerations in the design of a
Feistel cipher:
• Fast software encryption/decryption:
In many cases, encryption is embedded in applications
or utility functions as the speed of execution of the
algorithm becomes a concern.
• Ease of analysis:
Goal is to make our algorithm as difficult as possible to
cryptanalyze.
If the algorithm can be concisely and clearly
explained, it is easier to analyze that algorithm for114
Feistel Cipher Structure

115
Feistel Example

116
 3.2 Data Encryption Standard
• Until the introduction of the Advanced Encryption Standard (AES)
in 2001, the Data Encryption Standard (DES) was the most widely
used encryption scheme.
• DES was issued in 1977 by the National Bureau of Standards, now
the National Institute of Standards and Technology (NIST),
• The algorithm itself is referred to as the Data Encryption Algorithm
(DEA).
• For DEA, data are encrypted in 64-bit blocks using a 56-bit key. The
algorithm transforms 64-bit input in a series of steps into a 64-bit
output.
• The same steps, with the same key, are used to reverse the
encryption.
117
 3.2 Data Encryption Standard

• Over the years, DES became the dominant symmetric

encryption algorithm, especially in financial applications.
• In 1994, NIST reaffirmed DES for federal use for another five
years.
• In 1999, NIST issued a new version of its standard that indicated
that DES should be used only for legacy systems and that triple
DES (which in essence involves repeating the DES algorithm
three times on the plaintext using two or three different keys to
produce the ciphertext) be used.

118
3.2 Data Encryption Standard

119
3.2 Data Encryption

120
3.2 Data Encryption

121
 3.2 Data Encryption
• The plaintext must be 64 bits in length and the key is
56 bits in length.
• Processing of the plaintext proceeds in three
phases.
1. 64-bit plaintext passes through an initial
permutation (IP) that rearranges the bits to
produce the permuted input.
2. A phase consisting of sixteen rounds of the same
function, which involves both permutation and
substitution functions. The output of the last
(sixteenth) round consists of 64 bits. The left and
122
right halves of the output are swapped to
 3.2 Data Encryption
3. Finally, the preoutput is passed through a permutation [IP -1]
that is the inverse of the initial permutation function, to produce the
64-bit ciphertext.
• With the exception of the initial and final permutations, DES has
the exact structure of a Feistel cipher.
• The 56-bit key is used.
• Initially, the key is passed through a permutation function.
• Then, for each of the sixteen rounds, a subkey (Ki) is produced
by the combination of a left circular shift and a permutation.
• The permutation function is the same for each round, but a
different subkey is produced because of the repeated shifts of
the key bits.
123
 3.2 Data Decryption

• As with any Feistel cipher, decryption uses the

same algorithm as encryption, except that the
application of the subkeys is reversed.
• Additionally, the initial and final permutations are
reversed.

124
 3.3 A DES Example

• Results
• Table 3.2 shows the progression of the algorithm.
• The first row shows the 32-bit values of the left and right halves of
data after the initial permutation generated for each round.
• Note that Li = Ri-1. The final row shows the left- and right-hand values
after the inverse initial permutation.
• These two values combined form the ciphertext. 125
3.3 A DES Example

126
 3.3 A DES Example

• The Avalanche Effect

• A desirable property of any encryption
algorithm is that a small change in either the
plaintext or the key should produce a
significant change in the ciphertext.
• In particular, a change in one bit of the
plaintext or one bit of the key should produce a
change in many bits of the ciphertext.
• This is referred to as the avalanche effect.
127
 3.3 A DES Example

• Using the example from Table 3.2, Table 3.3 shows the result when
the fourth bit of the plaintext is changed, so that the plaintext is
12468aceeca86420.
• The second column of the table shows the intermediate 64-bit
values at the end of each round for the two plaintexts.
• The third column shows the number of bits that differ between the
two intermediate values.
• The table shows that, after just three rounds, 18 bits differ between
the two blocks.
• On completion, the two ciphertexts differ in 32 bit positions.

128
 3.3 A DES Example

• Table 3.4 shows a similar test using the original plaintext of

with two keys that differ in only the fourth bit position: the
original key, 0f1571c947d9e859, and the altered key,
1f1571c947d9e859.
• Again, the results show that about half of the bits in the
ciphertext differ and that the avalanche effect is
pronounced after just a few rounds.

129
3.3 A DES Example

130
3.3 A DES Example

131
 3.4 The Strength of DES

• Since its adoption as a federal standard, there have been

concerns about the level of security provided by DES. These
concerns fall into two areas:
1. Key size
2. Nature of the algorithm.

132
 3.4 The Strength of DES
1. The Use of 56-Bit Key
• With a key length of 56 bits, there are 2 56 possible keys, which is
approximately 7.2 * 1016 keys.
• A brute-force attack appears impractical.
• On average, half the key space has to be searched, a single machine
performing one DES encryption per microsecond would take more than
a thousand years to break the cipher.
• One encryption per microsecond.
• In1977, Diffie and Hellman postulated that the technology existed to
build a parallel machine with 1 million encryption devices, each of
which could perform one encryption per microsecond.
• This would bring the average search time down to about 10 hours.
• The cost would be about $20 million in 1977 dollars.
133
 3.4 The Strength of DES
1. The Use of 56-Bit Key
• With current technology, it is not even necessary to use special,
purpose-built hardware.
• A rate of 1 billion (109) key combinations per second is reasonable
for today’s multicore computers.
• Both Intel and AMD now offer hardware-based instructions to
accelerate the use of AES.
• Single PC can break DES in about a year; if multiple PCs work in
parallel, the time is drastically shortened.
• And today’s supercomputers should be able to find a key in about an
hour.
• Fortunately, there are a number of alternatives to DES, the most
important of which are AES and triple DES
134
 3.4 The Strength of DES

Table 3.5 shows how much time is required for a brute-force attack for
various key sizes

135
 3.4 The Strength of DES
2. The Nature of the DES Algorithm
Another concern is the possibility that cryptanalysis is
possible by exploiting the characteristics of the DES
algorithm.
The focus of concern has been on the eight substitution
tables, or S-boxes, that are used in each iteration.
Because the design criteria for these boxes, and indeed for
the entire algorithm, were not made public, there is a
suspicion that the boxes were constructed in such a way
that cryptanalysis is possible for an opponent who knows
the weaknesses in the S-boxes. 136
 3.4 The Strength of DES

Timing Attacks

• A timing attack is one in which information about the key

or the plaintext is obtained by observing how long it takes
a given implementation to perform decryptions on various
ciphertexts.
• A timing attack exploits the fact that an encryption or
decryption algorithm often takes slightly different
amounts of time on different inputs.
• The authors conclude that DES appears to be fairly
resistant to a successful timing attack

137
 3.5 Block Cipher Design Principles

Three critical aspects of block cipher design:

1. The number of rounds
2. Design of the function F
3. Key scheduling.

138
 3.5 Block Cipher Design Principles

• Number of Rounds
• The greater the number of rounds, the more difficult it is to perform
cryptanalysis, even for a relatively weak F.
• In general, the criterion should be that the number of rounds is chosen so
that known cryptanalytic efforts require greater effort than a simple brute-
force key search attack.
• This criterion observes that for 16-round DES, a cryptanalysis attack is
slightly less efficient than brute force.
• If DES had 15 or fewer rounds, differential cryptanalysis would require less
effort than a brute-force key search.

139
 3.5 Block Cipher Design Principles

Design of Function F
The heart of a Feistel block cipher is the function F, which provides the
element of confusion in a Feistel cipher.
Thus, it must be difficult to “unscramble” the substitution performed by F.
The more nonlinear F, the more difficult any type of cryptanalysis will be.
More difficult it is to approximate F by a set of linear equations, the more
nonlinear F is.

140
 3.5 Block Cipher Design Principles

Several other criteria should be considered in designing F.

• A algorithm to have good avalanche properties.
• A change in one bit of the input should produce a change in many bits of the output.
• A more stringent version of this is the strict avalanche criterion (SAC) which states that
any output bit j of an S-box should change with probability 1/2 when any single input bit i is
inverted for all i, j.
• Another criterion proposed is the bit independence criterion (BIC), which states that
output bits j and k should change independently when any single input bit i is inverted for
all i, j, and k. The SAC and BIC criteria appear to strengthen the effectiveness of the
confusion function.

141
 3.5 Block Cipher Design Principles

Key Schedule Algorithm

• With any Feistel block cipher, the key is used to generate one
subkey for each round.
• In general, we would like to select subkeys to maximize the
difficulty of deducing individual subkeys and the difficulty of
working back to the main key.

142