Substitution Techniques

The letters of plain texts are replaced by other letters

or by number or symbols

C=EK(P) denotes that C is the encryption of the

plaintext P using the key K

P=DK(C) denotes that P is the decryption of the

cipher text C using the key K

Shreenivas B, TE, BMSCE; Reference:

Cryptography and Network Security , 3rd
Edi, William Stallings
 Caesar Cipher
 Attributed to Julius Caesar
 It involves replacing each letter of the alphabet with the letter
standing three places further down the alphabet

 We can define the transformation by listing all possibilities as

follows

a bcde fghi j k lmno pqr s t uvwxyz

DEFGHIJKLMNOPQRSTUVWXYZABC

Example:
MEET ME AFTER THE TOGA PARTY
PHHW PH DIWHU WKH WRJD SDUWB

Shreenivas B, TE, BMSCE; Reference:

Cryptography and Network Security , 3rd
Edi, William Stallings
 Caesar Cipher
 Mathematically give each letter a number

abcdefghijklmnopqrstuvwxyz
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 key is a number from 0 to 25

 Caesar cipher can now be represented as
E(p) = (p + k) mod (26)
D(C) = (C –k) mod (26

Shreenivas B, TE, BMSCE; Reference:

Cryptography and Network Security , 3rd
Edi, William Stallings
Brute-force attack is easy: there
are only 25 keys possible

Try all 25 keys and check to see

which key gives an intelligible
message

Shreenivas B, TE, BMSCE; Reference:

Cryptography and Network Security , 3rd
Edi, William Stallings
 Caesar Cipher
Brute – force cryptanalysis, used on Caesar cipher, based on
following characteristics

1. Encryption and Decryption algorithm are known

2. There are only 25 keys to try
3. The language of the plaintext is known & recognizable

For 3rd case, we compress the data.

Shreenivas B, TE, BMSCE; Reference:

Cryptography and Network Security , 3rd
Edi, William Stallings
 Monoalphabetic Ciphers
 Cipher line can be any permutation of the 26 alphabetic
characters
 The increase in the number of keys is dramatic: 26!, i.e.,
more than 4x1026 possible
 Difficult to perform brute-force attacks
 If the cryptanalyst knows the nature of the text,then he can
exploit the patterns of the language
 In English E is by far the most common letter
Follows T,R,N,I,O,A,S
Other letters are fairly rare such as Z,J,K,Q,X
 Tables of single, double & triple letter frequencies exist
 Most common digram in English is TH
 Most common trigram in English in THE
Shreenivas B, TE, BMSCE; Reference:
Cryptography and Network Security , 3rd
Edi, William Stallings
Monoalphabetic ciphers

Shreenivas B, TE, BMSCE; Reference:

Cryptography and Network Security , 3rd
Edi, William Stallings
 Monoalphabetic Ciphers
 Monoalphabetic substitution ciphers do not change relative
letter frequencies

1. Calculate letter frequencies for ciphertext

2. Compare counts/plots against known values

 Most frequent letter in the ciphertext may well encrypt E

 The next one could encrypt T or A
 After relatively few tries the system is broken
 If the ciphertext is short (and so, the frequencies are not fully
relevant) then more guesses may be needed
 Look at the frequency of two-letter combinations (digrams)
Shreenivas B, TE, BMSCE; Reference:
Cryptography and Network Security , 3rd
Edi, William Stallings
 Monoalphabetic Ciphers
Ciphertext:
UZQSOVUOHXMOPVGPOZPEVSGZWSZOPFPESXUDBMETSXAIZVUEPHZHMDZSHZOWSF
PAPPDTSVPQUZWYMXUZUHSXEPYEPOPDZSZUFPOMBZWPFUPZHMDJUDTMOHMQ

 Count relative letter frequencies: P is the most frequent (13.33%), followed by Z

(11.67), S (8.33), U (8.33), O (7.5), M (6.67), H (5.83), etc.

 Guess P and Z stand for E and T but the order is not clear because of small difference
in the frequency

 The next set of letters {S,U, O, M, H} may stand for {A, H, I, N, O, R, S}but again it is
not completely clear which is which

 One may try to guess and see how the text translates

 Also, a good guess is that ZW, the most common digram in the ciphertext, is TH, the
most common digram in English: thus, ZWP is THE

 Proceed with trial and error and finally get after inserting the proper blanks:

it was disclosed yesterday that several informal but direct contacts have been made with
political representatives of the vietcong in moscow
Shreenivas B, TE, BMSCE; Reference:
Cryptography and Network Security , 3rd
Edi, William Stallings
 Monoalphabetic Ciphers

Monoalphabetic ciphers are easy to break because they reflect the

frequency of the original alphabet

Countermeasure: provide multiple substitutes for a given letter

Shreenivas B, TE, BMSCE; Reference:

Cryptography and Network Security , 3rd
Edi, William Stallings
 Playfair Ciphers
 Multiple letter encryption cipher

 It treats diagrams in the plaintext as a single unit

 These units are translated to ciphertexts diagrams

 This algorithm is based on the use of a 5x5 matrix in which the letters
of the alphabet are written (I is considered the same as J)

 This is called key matrix

 A 5X5 matrix of letters based on a keyword

 Fill in letters of keyword (no duplicates)

 Left to right, top to bottom

 Fill the rest of matrix with the other letters in alphabetic order
Shreenivas B, TE, BMSCE; Reference:
Cryptography and Network Security , 3rd
Edi, William Stallings
 Playfair Ciphers
E.g. using the keyword MONARCHY, we obtain the following matrix
M O N A R
C H Y B D
E F G J K
L P Q S T
U V W X Z

The plaintext is encrypted two letters at a time:

1.Break the plaintext into pairs of two consecutive letters
2.If a pair is a repeated letter, insert a filler like 'X‘ in the plaintext, eg. "balloon" is
treated as "balx lo on"
3.If both letters fall in the same row of the key matrix, replace each with the letter
to its right (wrapping back to start from end), eg. “AR" encrypts as "RM"
4.If both letters fall in the same column, replace each with the letter below it (again
wrapping to top from bottom), eg. “MU" encrypts to "CM"
5.Otherwise each letter is replaced by the one in its row in the column of the other
letter of the pair, eg. “HS" encrypts to "BP", and “EA" to "IM" or "JM" (as desired)
Shreenivas B, TE, BMSCE; Reference:
Cryptography and Network Security , 3rd
Edi, William Stallings
 Playfair Ciphers
E.g. using the keyword MONARCHY, we obtain the following matrix
M O N A R
C H Y B D
E F G J K
L P Q S T
U V W X Z

The plaintext is : statebankofindia

Cipher text is : TLRSICRAFRGKRYSB

Shreenivas B, TE, BMSCE; Reference:

Cryptography and Network Security , 3rd
Edi, William Stallings
 Playfair Ciphers
E.g. using the keyword MTECH, we obtain the following matrix
M T E C H
A B D F G
I/J K L N O
P Q R S U
V W X Y Z
The cipher text is: LCEDBENGKOFX

The Plain text is: need to find you

Shreenivas B, TE, BMSCE; Reference:

Cryptography and Network Security , 3rd
Edi, William Stallings
 Examples
1. Using play fair method, key=COMPUTER, decrypt : MTPAECNGHAQP

Shreenivas B, TE, BMSCE; Reference:

Cryptography and Network Security , 3rd
Edi, William Stallings
 Hill Ciphers
 Attributed to Lester Hill
 This algorithm takes ‘m’ successive plaintext letters & Substitutes for
them ‘m’ cipher letters

 Substitution is determined by ‘m’ linear equations in which each

character is assigned a numerical value (a=0, b=1, …… z=25)

 For m=3, system can be described as follows

C1= ( k11p1 + k12p2 + k13p3) mod 26

C2= ( k21p1 + k22p2 + k23p3) mod 26
C3= ( k31p1 + k32p2 + k33p3) mod 26
This can be expressed in terms of column vectors and matrices

Shreenivas B, TE, BMSCE; Reference:

Cryptography and Network Security , 3rd
Edi, William Stallings
 Hill Ciphers

Shreenivas B, TE, BMSCE; Reference:

Cryptography and Network Security , 3rd
Edi, William Stallings
 Hill Ciphers

Shreenivas B, TE, BMSCE; Reference:

Cryptography and Network Security , 3rd
Edi, William Stallings
 Hill Ciphers

Shreenivas B, TE, BMSCE; Reference:

Cryptography and Network Security , 3rd
Edi, William Stallings
 Polyalphabetic Ciphers

 By using different monoalphabetic substitution as on proceeds through

the plaintext message
1. A set of related monoalphabetic substitution rule is used

2. A key determine which particular rule is chosen for a given

transformation

 Each of the 26 ciphers is laid out horizontally with the key letters for
each cipher to its self

Shreenivas B, TE, BMSCE; Reference:

Cryptography and Network Security , 3rd
Edi, William Stallings
Plain text  KEY 

Shreenivas B, TE, BMSCE; Reference:

Cryptography and Network Security , 3rd
Edi, William Stallings
 Polyalphabetic Ciphers
 To encrypt message , a key is needed that is as long as the message
Eg: keyword: deceptive
Message: wearediscoveredsaveyourself
keyword: deceptivedeceptivedeceptive
Cipher: ZICVTWQNGRZGVTWAUZHCQYGLMHJ
Strength : There are multiple cipher text letters for each plain text letters
Cryptanalysis: if algorithm known , then progress depends on determining
the length of the keyword
If two identical sequence of plaintext letter occurs at a distance that is an
integer multiple of keyword length , they will generate identical cipher text
Eg: red – twice occurs
VTW – both the case
Shreenivas B, TE, BMSCE; Reference:
Cryptography and Network Security , 3rd
Edi, William Stallings
 Polyalphabetic Ciphers
Solution:

Periodic nature of the keyword can be eliminated by using a non-repeating

keyword that is as long as the message itself

Eg: autokey system: keyword is concatenated with the plain text itself to
provide running key

Message: wearediscoveredsaveyourself

keyword: deceptivewearediscoveredsav

Cipher: ZICVTWQNGKZEIIGASXSTSLVVWLA

Shreenivas B, TE, BMSCE; Reference:

Cryptography and Network Security , 3rd
Edi, William Stallings
 Transposition Techniques
 We have considered substitutions to encrypt the plaintext: each letter is
mapped into a letter according to some substitution
 New Method: perform some sort of permutation on the plaintext letters
 Hide the message by rearranging the letter order without altering the
actual letters used

Rail Fence Technique

 Plain text is written down as a sequence of diagonals
 Read off as a sequence of rows

Eg: message : “meet me after the toga party”

With a rail fence of depth 2

m e m a t r h t g p r y
e t e f e t e o a a t

Encrypt message is : MEMATRHTGPRYETEFETEOAAT

Shreenivas B, TE, BMSCE; Reference:
Cryptography and Network Security , 3rd
Edi, William Stallings
 Data Encryption Standard
 It take 64 bit length plain text and 56 bit length key (actual 64 but 8 bits
arbitrary or parity bits)

Initial permutation permuted Choice-1

56
K1
bit
Round 1 Permuted choice 2 Left circular shift
K2
Round 2 Permuted choice 2 Left circular shift

K16
Round 16 Permuted choice 2 Left circular shift

32 bit swap
General view of DES encryption Algorithm

Inverse IP

Shreenivas B, TE, BMSCE; Reference:

Cryptography and Network Security , 3rd
Edi, William Stallings
 Data Encryption Standard
Initial Permutation : IP

Shreenivas B, TE, BMSCE; Reference:

Cryptography and Network Security , 3rd
Edi, William Stallings
 Data Encryption Standard
Inverse Initial Permutation

Shreenivas B, TE, BMSCE; Reference:

Cryptography and Network Security , 3rd
Edi, William Stallings
 Data Encryption Standard
Details of Single Round

Li = Ri-1
Ri= Li-1 ⨁ F(Ri-1, Ki)

Shreenivas B, TE, BMSCE; Reference:

Cryptography and Network Security , 3rd
Edi, William Stallings
 Data Encryption Standard
 32 bit R input is expanded to 48 bits by using table E/P

The resulting 48 bit is XORed with Ki,

Result is passed through the substitution function that produces 32bit output
32 bit is permuted using following table
Shreenivas B, TE, BMSCE; Reference:
Cryptography and Network Security , 3rd
Edi, William Stallings
 Data Encryption Standard

S- box function:
 The substitution consists of a set of 8 boxes
 Each of which accepts 6 bits as input and produces 4 bit as output
 First and last bits – rows in the table Si
 Middle four bits – one of the sixteen columns
 The decimal value then converted to its 4 bit
 Eg: 011001
 Row: 01- row 1, 1100 – column 12

Shreenivas B, TE, BMSCE; Reference:

Cryptography and Network Security , 3rd
Edi, William Stallings
Data Encryption Standard

Shreenivas B, TE, BMSCE; Reference:

Cryptography and Network Security , 3rd
Edi, William Stallings
 Data
Encryption
Standard

Shreenivas B, TE, BMSCE; Reference:

Cryptography and Network Security , 3rd
Edi, William Stallings
 Data Encryption
Standard
Key Generation:
A 64-bit key is used –the bits of the key
are numbered from 1 to 64.
The algorithm ignores every 8th bit
 the key for DES is effectively 56-bit long
Before round 1 of DES, the key is
permuted according to a table labeled
Permuted Choice One
the resulting 56-bit key is split into its two
28-bit halves labeled C0and D0
In each round, Ci-1 and Di-1 are
separately subjected to a circular left shift of
one or two bits according to the table
The shifted values will be input to next
round
The shifted values serve as input to
Permuted Choice Two
which produces a 48-bit output - Ki
Shreenivas B, TE, BMSCE; Reference:
Cryptography and Network Security , 3rd
Edi, William Stallings
Data Encryption Standard

Shreenivas B, TE, BMSCE; Reference:

Cryptography and Network Security , 3rd
Edi, William Stallings
Data Encryption Standard

Shreenivas B, TE, BMSCE; Reference:

Cryptography and Network Security , 3rd
Edi, William Stallings
 Data Encryption Standard
Avalanche effect:
This is a desirable property of any encryption algorithm
A small change (even 1 bit) in the plaintext should produce significant
change in the ciphertext

Shreenivas B, TE, BMSCE; Reference:

Cryptography and Network Security , 3rd
Edi, William Stallings
 Block Cipher Mode Operation
 Electronic Codebook (ECB)
 Secure transmission of single values
 Cipher Block Chaining (CBC)
 General purpose block oriented transmission
 Cipher Feedback (CFB)
 General purpose stream oriented transmission
 Output Feedback (OFB)
 Stream oriented transmission over noisy channel
 Counter (CTR)
 High speed requirement

Shreenivas B, TE, BMSCE; Reference:

Cryptography and Network Security , 3rd
Edi, William Stallings
 Electronic Codebook Book (ECB)
Plain text is handled 64 bits at a time
Each block of plaintext is encrypted using
same key
Codebook: Given key, there is a unique
ciphertext for every 64 bit block of plaintext
Each block is encoded independently of the
other blocks
Ci = DESK1 (Pi)
Uses: secure transmission of single values
Shreenivas B, TE, BMSCE; Reference:
Cryptography and Network Security , 3rd
Edi, William Stallings
Electronic Codebook Book (ECB)

Shreenivas B, TE, BMSCE; Reference:

Cryptography and Network Security , 3rd
Edi, William Stallings
 Advantages and Limitations of ECB
Repetitions in message may show in
ciphertext
Weakness due to encrypted message blocks
being independent
Main use is sending a few blocks of data

Shreenivas B, TE, BMSCE; Reference:

Cryptography and Network Security , 3rd
Edi, William Stallings
 Cipher Block Chaining (CBC)
Message is broken into blocks
But these are linked together in the
encryption operation
Each previous cipher blocks is chained with
current plaintext block, hence name
use Initial Vector (IV) to start process
Ci = DESK1(Pi XOR Ci-1)
C-1 = IV
uses: bulk data encryption, authentication
Shreenivas B, TE, BMSCE; Reference:
Cryptography and Network Security , 3rd
Edi, William Stallings
Cipher Block Chaining (CBC)

Shreenivas B, TE, BMSCE; Reference:

Cryptography and Network Security , 3rd
Edi, William Stallings
 Advantages and Limitations of CBC
• Each ciphertext block depends on all message blocks
• Thus a change in the message affects all ciphertext blocks
after the change as well as the original block
• Need Initial Value (IV) known to sender & receiver
– however if IV is sent in the clear, an attacker can change bits of the
first block, and change IV to compensate
– hence either IV must be a fixed value or it must be sent encrypted
in ECB mode before rest of message
• At end of message, handle possible last short block
– by padding either with known non-data value (eg nulls)

Shreenivas B, TE, BMSCE; Reference:

Cryptography and Network Security , 3rd
Edi, William Stallings
 Cipher FeedBack (CFB)
 Message is treated as a stream of bits
 Added to the output of the block cipher
 Result is feed back for next stage (hence name)
 Standard allows any number of bit (1,8 or 64 or
whatever) to be feed back
 denoted CFB-1, CFB-8, CFB-64 etc
 Is most efficient to use all 64 bits (CFB-64)
Ci = Pi XOR DESK1(Ci-1)
C-1 = IV
 Uses: stream data encryption, authentication
Shreenivas B, TE, BMSCE; Reference:
Cryptography and Network Security , 3rd
Edi, William Stallings
Cipher FeedBack (CFB)

Shreenivas B, TE, BMSCE; Reference:

Cryptography and Network Security , 3rd
Edi, William Stallings
 Output FeedBack (OFB)
 Message is treated as a stream of bits
 Output of cipher is added to message
 Output is then feed back (hence name)
 Feedback is independent of message
 Can be computed in advance
Ci = Pi XOR Oi
Oi = DESK1(Oi-1)
O-1 = IV
 Uses: stream encryption over noisy channels
Shreenivas B, TE, BMSCE; Reference:
Cryptography and Network Security , 3rd
Edi, William Stallings
Output FeedBack (OFB)

Shreenivas B, TE, BMSCE; Reference:

Cryptography and Network Security , 3rd
Edi, William Stallings
 Counter (CTR)
a “new” mode, though proposed early on
similar to OFB but encrypts counter value
rather than any feedback value
must have a different key & counter value
for every plaintext block (never reused)
Ci = Pi XOR Oi
Oi = DESK1(i)
uses: high-speed network encryptions
Shreenivas B, TE, BMSCE; Reference:
Cryptography and Network Security , 3rd
Edi, William Stallings
Counter (CTR)

Shreenivas B, TE, BMSCE; Reference:

Cryptography and Network Security , 3rd
Edi, William Stallings
 Advantages of CTR
Hardware/ software efficiency : parallel
operation can be done
Pre-processing:
Simplicity
Random access

Shreenivas B, TE, BMSCE; Reference:

Cryptography and Network Security , 3rd
Edi, William Stallings