Classical Encryption Techniques

Dr. Md. Mahbubur Rahman

 Outline

1. To define the terms and the concepts of symmetric key

ciphers
2. To emphasize the two categories of traditional ciphers:
substitution and transposition ciphers
3. To describe the categories of cryptanalysis used to break
the symmetric ciphers
4. To introduce the concepts of the stream ciphers and
block ciphers
5. To discuss some very dominant ciphers used in the past,
such as the Enigma machine
 Cryptographic Algorithms
 Symmetric encryption: Used to conceal the contents of blocks or
streams of data of any size, including messages, files, encryption
keys and passwords.

 Asymmetric encryption: Used to conceal small blocks of data, such

as encryption keys and hash function values, which are used in
digital signatures.

 Data integrity algorithms: Used to protect blocks of data, such as

messages, from alteration.

 Authentication protocols: These are schemes based on the use of

cryptographic algorithms designed to authenticate the identity of
entities.
 Encryption for Confidentiality

Aim: assure confidential information not made available to

unauthorized individuals (data confidentiality)

How: encrypt the original data; anyone can see the encrypted data,
but only authorized individuals can decrypt to see the original data

Used for both sending data across network and storing data on a
computer system
Model of Encryption for Confidentiality
Model of Encryption for Confidentiality
Model of Encryption for Confidentiality
 Terminology
Plaintext original message
Ciphertext encrypted or coded message
Encryption convert from plaintext to ciphertext (enciphering)
Decryption restore the plaintext from ciphertext (deciphering)
Key information used in cipher known only to
sender/receiver
Cipher a particular algorithm (cryptographic system)
Cryptography study of algorithms used for encryption
Cryptanalysis study of techniques for decryption without
knowledge of plaintext
Cryptology areas of cryptography and cryptanalysis
 Symmetric Encryption

 or conventional / private-key / single-key

 sender and recipient share a common key
 all classical encryption algorithms are private-key
 was only type prior to invention of public-key in 1970’s
 and by far most widely used
Symmetric Cipher Model
 Requirements and assumptions

two requirements for secure use of symmetric encryption:

 a strong encryption algorithm (cannot decrypt and know key)
 a secret key known only to sender / receiver

mathematically have:
C = E(K, P)
P = D(K, C)

Assumptions
• encryption algorithm is known
• a secure channel to distribute key
 Kerckhoff’s principle
Although it may appear that a cipher would be more secure if we
hide both the encryption/decryption algorithm and the secret key,
this is not recommended.

Based on Kerckhoff’s principle, one should always assume that

the adversary , Eve, knows the encryption/decryption algorithm.
The resistance of the cipher to attack must be based only on the
secrecy of key.

In other words, guessing the key should be so difficult that there

is no need to hide the encryption/decryption algorithm.
 Characterizing Cryptographic Systems
Operations used for encryption:
Substitution replace one element in plaintext with another
Transposition re-arrange elements
Product systems multiple stages of substitutions and transpositions

Number of keys used:

Symmetric sender/receiver use same key (single-key, secret-key,
shared-key, conventional)
Public-key sender/receiver use dierent keys (asymmetric)

Processing of plaintext:
Block cipher process one block of elements at a time
Stream cipher process input elements continuously
Cryptography Classification
 Symmetric Key Encryption for Confidentiality

Requirements
Strong encryption algorithm: given algorithm, ciphertext and known
pairs of (plaintext, ciphertext), attacker should be unable to find plaintext
or key
Shared secret keys: sender and receiver both have shared a secret key; no-
one else knows the key
 Attacks
Goal of the Attacker
• Discover the plaintext (good)
• Discover the key (better)
Assumed Attacker Knowledge
• Ciphertext (want to decrypt)
• Algorithm (nature of the algorithm) or general idea of the type of plaintext
• Other pairs of (plaintext, ciphertext) using same key (not the plaintext in
question)
Attack Methods
Brute-force attack Try every possible key on ciphertext
Cryptanalysis Exploit characteristics of algorithm to deduce
plaintext or key
Assumption: attacker can recognize correct plaintext
 Attacks on Block Ciphers
 Brute Force Attack
Approach: try all keys in key space
Metric: number of operations (time)
k bit key requires 2k operations
Depends on key length and computer speed
 Cryptanalysis
Approach: Find weaknesses in algorithms
Methods: Linear cryptanalysis, differential cryptanalysis,
meet-in-the-middle attack, side-channel attacks
Metrics: Number of operations
Amount of memory
Number of known plaintexts/ciphertexts

If either succeed all key usages are compromised

 Cryptanalysis and Brute-Force Attack

Cryptanalysis : Cryptanalytic attacks rely on the nature of the

algorithm plus perhaps some knowledge of the general
haracteristics of the plaintext or even some 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.
 Brute Force Attack
always possible to simply try every key
most basic attack, proportional to key size
assume either know / recognise plaintext
 Cryptanalysis

As cryptography is the science and art of creating secret codes,

cryptanalysis is the science and art of breaking those codes.

Cryptanalysis attacks
 Cryptanalysis (Cont.)

Ciphertext-only attack

We have: the ciphertext of several messages that have been

encrypted with the same key, K.
We recover: the plaintexts, or K.
 Cryptanalysis (Cont.)

Known-Plaintext Attack

We have: the ciphertexts and corresponding plaintexts of several

messages, all encrypted with the same key K.
We recover: the key K.
 Cryptanalysis (Cont.)

Chosen-Plaintext Attack

We have: the ciphertext of several messages that have been

encrypted with the same key K, such that we get to choose the
plaintexts.
We recover: the key K.
 Cryptanalysis (Cont.)

Chosen-Ciphertext Attack

We have: the plaintext of several messages that have been

encrypted with the same key K, such that we get to choose the
ciphertexts.
We recover: the key K.
Cryptanalysis: Summary
Exercise
 Cryptography

Cryptographic systems are characterized along three independent

dimensions:

1. The type of operations used for transforming plaintext to ciphertext.

—substitution and transposition (or product)

2. The number of keys used. (sym. and asym.)

3 The way in which the plaintext is processed. (block and stream)

 Measures of Security
Unconditionally Secure
Ciphertext does not contained enough information to
derive plaintext or key
One-time pad is only unconditionally secure cipher ( but not
very practical )

Computationally Secure
If either:
- Cost of breaking cipher exceeds value of encrypted information
-Time required to break cipher exceeds useful lifetime of
encrypted information
Hard to estimate value/lifetime of some information
Hard to estimate how much effort needed to break cipher
 Motivation for cryptanalysts

All forms of cryptanalysis for symmetric encryption schemes are

designed to exploit the fact that traces of structure or pattern in
the plaintext may survive encryption and be discernible in the
ciphertext.
 Substitution ciphers
A substitution cipher replaces one symbol with another.
Substitution ciphers can be categorized as either
monoalphabetic ciphers or polyalphabetic ciphers.

A substitution cipher replaces one symbol

with another.

Topics:
Monoalphabetic Ciphres
Polyalphabetic Ciphers
 Monoalphabetic Ciphers

In monoalphabetic substitution, the

relationship between a symbol in the
plaintext to a symbol in the ciphertext is
always one-to-one.
Encoding
 Continued

Example

The following shows a plaintext and its corresponding ciphertext. The

cipher is probably monoalphabetic because both l’s (els) are encrypted
as O’s.

Plaintext: hello Ciphertext: KHOOR

Example
The following shows a plaintext and its corresponding ciphertext. The
cipher is not monoalphabetic because each l (el) is encrypted by a
different character.

Plaintext: hello Ciphertext: KHOLR

 Additive Cipher

The simplest monoalphabetic cipher is the additive cipher.

This cipher is sometimes called a shift cipher and sometimes a

Caesar cipher, but the term additive cipher better reveals its
mathematical nature.

Plaintext and ciphertext in Z26

 Additive Cipher
 Replace each letter by the letter three positions along in
alphabet

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

Generalized Caesar Cipher

 Allow shift by k positions
 Assume each letter assigned number (a = 0, b = 1, . . . )
C = E(k,p) = (p + k) mod 26
p = D(k,C) = (C - k) mod 26
 Additive Cipher

When the cipher is additive, the plaintext,

ciphertext, and key are integers in Z26.
 Additive Cipher

Use the additive cipher with key = 15 to encrypt the

message “hello”.

Solution
We apply the encryption algorithm to the plaintext, character by
character:
 Continued
Shift Cipher and Caesar Cipher

Hitorically, additive ciphers are called shift ciphers. Julius

Caesar used an additive cipher to communicate with his
officers. For this reason, additive ciphers are sometimes
referred to as the Caesar cipher. Caesar used a key of 3 for his
communications.

Additive ciphers are sometimes referred to

as shift ciphers or Caesar cipher.
 Continued
Eve has intercepted the ciphertext “UVACLYFZLJBYL”. Show
how she can use a brute-force attack to break the cipher.

Solution
Eve tries keys from 1 to 7. With a key of 7, the plaintext is “not
very secure”, which makes sense.
 Breaking the Caesar Cipher

Brute force attack

-The encryption and decryption algorithms are known.
-Try all 25 keys, e.g. k = 1, k = 2, . . .
-Plaintext should be recognised
Recognising plaintext in brute force attacks
-Need to know “structure" of plaintext
-Language? Compression?
How to improve against brute force?
-Hide the encryption/decryption algorithm: Not practical
-Compress, use different language: Limited options
-Increase the number of keys
 Substitution in other forms: Monoalphabetic Ciphers
With only 25 possible keys, the Caesar cipher is far from secure. A dramatic
increase in the key space can be achieved by allowing an arbitrary
substitution (Random substitution).

Permutation: A 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
For n elementts, n! permutations.
 For Caesar 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

For mono-alphabetic substitution:

If, instead, the “cipher” line can be any permutation of the 26 alphabetic
characters,

then there are 26! or greater than 4 * 1026 possible keys

 Example

We can use the key in Figure in previous slide to encrypt the message

The ciphertext is
 Attacks on Mono-alphabetic Ciphers

Exploit the regularities of the language

-Frequency of letters, digrams, trigrams
-Expected words

Fundamental problem with mono-alphabetic ciphers

-Ciphertext reflects the frequency data of original
plaintext
-Solution 1: encrypt multiple letters of plaintext
-Solution 2: use multiple cipher alphabets
 Language Redundancy and Cryptanalysis

 Human languages are redundant

e.g., "th lrd s m shphrd shll nt wnt"
 Letters are not equally commonly used
 In English E is by far the most common letter
 followed by T,R,N,I,O,A,S

 Other letters like Z,J,K,Q,X are fairly rare

 Have tables of single, double & triple letter frequencies for various
languages
 Continued
Frequency of characters in English

Frequency of diagrams and trigrams

Relative Frequency of Letters in English Text
 Breaking Monoalphabetic Substitution Cipher

 Letter Frequency Analysis results:

 English Letter Frequencies

Sorted Relative Frequencies

14.000
12.000
10.000
8.000
6.000
4.000
2.000
0.000
E T A O I N S H R D L C U MW F G Y P B V K J X Q Z
 Example cryptanalysis

frequency

As a first step, the relative frequency of the letters can be determined

and compared to a standard frequency distribution for English
So far, then, we have
 Example Cryptanalysis
 given ciphertext

UZQSOVUOHXMOPVGPOZPEVSGZWSZOPFPESXUDBMETSXAIZ
VUEPHZHMDZSHZOWSFPAPPDTSVPQUZWYMXUZUHSX
EPYEPOPDZSZUFPOMBZWPFUPZHMDJUDTMOHMQ

 guess P & Z are e and t

 guess ZW is th and hence ZWP is “the”
 proceeding with trial and error finally get:

it was disclosed yesterday that several informal but

direct contacts have been made with political
representatives of the viet cong in moscow
 Multiplicative Ciphers

Multiplicative cipher

In a multiplicative cipher, the plaintext and ciphertext are

integers in Z26; the key is an integer in Z26*.
 Continued.
Example
What is the key domain for any multiplicative cipher?

Solution

The key needs to be in Z26*. This set has only 12 members: 1, 3, 5, 7, 9, 11, 15, 17,
19, 21, 23, 25.

Example

We use a multiplicative cipher to encrypt the message “hello” with a key of 7. The
ciphertext is “XCZZU”.
 Affine Ciphers
Combining additive and multiplicative cipher
 Affine Ciphers
Example

The affine cipher uses a pair of keys in which the first key is from Z 26* and the
second is from Z26. The size of the key domain is 26 × 12 = 312.

Example

Use an affine cipher to encrypt the message “hello” with the key pair (7, 2).
 Affine Ciphers
Example
Use the affine cipher to decrypt the message “ZEBBW” with the
key pair (7, 2) in modulus 26.
Solution

Example
The additive cipher is a special case of an affine cipher in which

k1 = 1. The multiplicative cipher is a special case of affine cipher

in which k2 = 0.
Polygraphic Substitution Ciphers
 Substitution: Other forms (Cont)

 Use two-letter combinations: Playfair Cipher

 Use multiple letter combinations: Hill Cipher

Use multiple ciphers. Use a key to select which alphabet (code) is used for
each letter of the message
 Poly-alphabetic Ciphers
 Monoalphabetic ciphers are easy to break because they reflect the
frequency data of the original alphabet. A countermeasure is to
provide multiple substitutes known as homophones, for a single letter.

 For example, the letter e could be assigned a number of different

cipher symbols, such as 16, 74, 35, and 21, with each homophone
assigned to a letter in rotation or randomly.

Use different mono-alphabetic substitutions as proceed

through plaintext
 Set of mono-alphabetic ciphers
 Key determines which mono-alphabetic cipher to use for each
plaintext letter
Examples: Vigenere cipher, Vernam cipher, One time pad
 Polyalphabetic Ciphers

In polyalphabetic substitution, each occurrence of a character may have

a different substitute. The relationship between a character in the
plaintext to a character in the ciphertext is one-to-many.

Autokey Cipher
 Autokey Cipher
Assume that Alice and Bob agreed to use an autokey cipher
with initial key value k1 = 12. Now Alice wants to send Bob
the message “Attack is today”. Enciphering is done character
by character.
 Autokey Cipher

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,

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.
 Playfair Cipher

 Not even the large number of keys in a monoalphabetic cipher provides

security
 One approach to improving security was to encrypt multiple letters
 The Playfair Cipher is an example
 Invented by Charles Wheatstone in 1854, but named after his friend Baron
Playfair
 Playfair Cipher
Initialization
1. Create 5x5 matrix and write keyword (row by row)
2. Fill out remainder with alphabet, not repeating any
letters
3. Special: Treat I and J as same letter
Encryption
1. Operate on pair of letters (digram) at a time
2. Special: if digram with same letters, separate by special
letter (e.g. x)
3. Plaintext in same row: replace with letters to right
4. Plaintext in same column: replace with letters below
5. Else, replace by letter in same row as it and same
column as other plaintext letter
Playfair Cipher
Playfair Cipher
 balloon balxloxon
ar RM
mu CM
hs BP
ea IM

In this case, the keyword is monarchy.

Plaintext is encrypted two letters at a time

 An example of a secret key in the Playfair cipher

Example
Let us encrypt the plaintext “hello” using the key in Figure
An example of a secret key in the Playfair cipher
An example of a secret key in the Playfair cipher
Exercise
 Measuring Effectiveness of the Playfair and other ciphers

The following plot is developed: (i) The number of occurrences of

each letter in the text is counted and divided by the number of
occurrences of the most frequently used letter. e is the most
frequently used letter.

To normalize the plot, the number of occurrences of each letter in

the ciphertext was again divided by the number of ccurrences of e
in the plaintext.

If the frequency distribution information were totally concealed in

the encryption process, the ciphertext plot
of frequencies would be flat, and cryptanalysis using ciphertext
only would be effectively impossible.
Relative Frequency of Occurrence of Letters
 Security of Playfair Cipher

Security much improved over monoalphabetic since have 26 x 26

= 676 digrams
Would need a 676 entry frequency table to analyse (versus 26 for a
monoalphabetic) and correspondingly more ciphertext was widely
used for many years
E.g. by US & British military in WW1
It can be broken, given a few hundred letters since still has much of
plaintext structure
 Playfair Cipher - Is it Breakable?

Better than mono-alphabetic: relative frequency of

digrams much less than of individual letters
But relatively easy (digrams, trigrams, expected words)
 Vigenere Cipher

Set of 26 general Caesar ciphers

26 Caesar ciphers with shifts of 0 through 25.
Letter in key determines the Caesar cipher to use
 Key must be as long as plaintext: repeat a keyword

Example:
Plain: internettechnologies
Key: sirindhornsirindhorn
Cipher: AVKMEQLHKRUPEWYRNWVF
Multiple ciphertext letters for each plaintext letter
For the next m letters of the plaintext, the key letters are
repeated.
Expressed numerically, we have the following result.
Vigenere Cipher
Example
Vigenere Cipher
We can encrypt the message “She is listening” using the 6-
character keyword “PASCAL”.

Let us see how we can encrypt the message “She is listening” using the
6-character keyword “PASCAL”. The initial key stream is (15, 0, 18, 2, 0,
11). The key stream is the repetition of this initial key stream (as many
times as needed).
 Vigenere Cipher

Vigenere cipher can be seen as combinations of m additive

ciphers.

Figure A Vigenere cipher as a combination of m additive ciphers

 Vigenere Cipher
Using Example , we can say that the additive cipher is a
special case of Vigenere cipher in which m = 1.

Table
A Vigenere Tableau
 Vigenere Cipher
(Cryptanalysis)

Example
Let us assume we have intercepted the following ciphertext:

The Kasiski test for repetition of three-character segments

yields the results shown in Table .
 Vigenere Cipher (Crypanalysis)

Example Cont.
Let us assume we have intercepted the following ciphertext:

The Kasiski test for repetition of three-character segments in

ciphertext yields the results shown in Table
 Example Cont.
The greatest common divisor of differences is 4, which means
that the key length is multiple of 4. First try m = 4.

In this case, the plaintext makes sense.

3.86
 Vigenere Cipher - Is it Breakable?

Yes
Monoalphabetic or Vigenere cipher? Letter frequency
analysis
Determine length of keyword
For keyword length m, Vigenere is m mono-alphabetic
substitutions
Break the mono-alphabetic ciphers separately
Weakness is repeating, structured keyword
 Hill Cipher
Another interesting multiletter cipher is the Hill cipher, developed by the
mathematician Lester Hill in 1929.

Plaintext are divided into equal size blocks. Each character in a block
contributes to the encryption of the other characters in the block. (Block
Cipher)

The key matrix in the Hill cipher needs to

have a multiplicative inverse.
 Examp Hilll1
For example, the plaintext “code is ready” can make a 3 × 4
matrix when adding extra bogus character “z” to the last block
and removing the spaces. The ciphertext is “OHKNIHGKLISS”.

Figure Example
 Example Hill2
Assume that Eve knows that m = 3. She has intercepted three
plaintext/ciphertext pair blocks (not necessarily from the same
message) as shown in Figure .

Figure
 Example Hill2 cont.

She makes matrices P and C from these pairs. Because P is

invertible, she inverts the P matrix and multiplies it by C to get
the K matrix as shown in Figure.
Figure Example

Now she has the key and can break any ciphertext encrypted
with that key.
 Hill Cipher
Concepts from Linear Algebra
We define the inverse M-1 of a square matrix M by the equation M(M-1)
= M-1M = I, where I is the identity matrix. I is a square matrix that is all
zeros except for ones along the main diagonal from upper left to lower
right.
(we are concerned with matrix arithmetic modulo 26).
 Matrix Operations
 Matrix addition/subtraction
 Matrices must be of same size.

 Matrix multiplication

mxn nx p mxp

n
Condition: n = q
Identity Matrix
Matrix Transpose
 Symmetric Matrices

Example:
 Determinants

2x2

3x3

nxn

Properties:
 Matrix Inverse
 The inverse A-1 of a matrix A has the property:
AA-1=A-1A=I

 A-1 exists only if

 Terminology
 Singular matrix: A-1 does not exist
 Ill-conditioned matrix: A is “close” to being singular
 Matrix Inverse (cont’d)

 Properties of the inverse:

 Inverse of a Matrix

Determinant
For any square matrix (m × m), the determinant equals the sum of
all the products that can be formed by taking exactly one element
from each row and exactly one element from each column, with
certain of the product terms preceded by a minus sign
 Det(A)=

Det(A)-1= 9-1 mod 26 =3 (not 1/9) As,

Note:
 Det(A)=

Det(A)-1= 9-1 mod 26=3 As,

We can show that 9-1 mod 26 = 3, because 9 ×3 = 27 mod 26
= 1 Therefore, we compute the inverse of A as
 The Hill Algorithm
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). For m = 3, the system can be described as
In general

“paymoremoney”
 One-Time Pad

 One of the goals of cryptography is perfect secrecy.

 A study by Shannon has shown that perfect secrecy can be achieved

if each plaintext symbol is encrypted with a key randomly chosen
from a key domain.

 This idea is used in a cipher called one-time pad, invented by

Vernam.
 One Time Pad

Similar to Vigenere, but use random key as long as plaintext

Only known scheme that is unbreakable (unconditional
security or perfect security)
 Ciphertext has no statistical relationship with plaintext
 Given two potential plaintext messages, attacker cannot identify
the correct message

A cipher system has perfect secrecy if the ciphertext gives the cryptanalyst
no information about the key. The one time pad achieves perfect secrecy.
 Continued
Mauborgne suggested using a random key that is as long as the message, so
that the key need not be repeated.
In addition, the 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, known as a one-time pad, is unbreakable.

Two practical limitations:

1. Difficult to provide large number of random keys
2. Distributing unique long random keys is difficult
Limited practical use
Ciphertext

We now show two different decryptions using two different keys:

So, for using random key, the cryptanalyst will be

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

His system works on binary data (bits) rather than letters. The
system can be expressed succinctly as follows
Vernam proposed the use of a running loop of tape that eventually
repeated the key, so that in fact the system worked with a very long
but repeating keyword.
 Rotor Cipher
Although one-tme pad is not practical, one step toward more secured
encipherment is rotor cipher.

It uses the idea behind monalphabetic substitution, but changes the

mapping between plaintext and cipphertext characters for each
Figure A rotor cipher
plaintext character.
 Rotor Cipher
It uuses only 6 letter, but actual rotor uses 26 letters.
Initial setting is the secret key.

‘bee’ encrypts as “BAA” if rotor is stationery,but become “BCA” as

rotates.
 Enigma Machine
Originally degined by Sherbius, modified by Geerman army and
extensively used in WWII.

‘.

Figure A schematic of the Enigma machine

 Rotor machines
The machine consists of a set of independently rotating cylinders through
which electrical pulses can flow.

Each cylinder has 26 input pins and 26 output pins, with internal wiring that
connects each input pin to a unique output pin.

After each input key is depressed, the cylinder rotates one position, so that the
internal connections are shifted accordingly.

After 26 letters of plaintext, the cylinder would be back to the initial position.
For every complete rotation of the inner cylinder, the middle cylinder
rotates one pin position. Finally, for every complete rotation of the middle
cylinder, the outer cylinder rotates one pin position.
Thus, a given setting of a 5-rotor machine is equivalent to a Vigenère cipher
with a key length of 11,881,376.
 Poly-alphabetic Ciphers Summary

 polyalphabetic substitution ciphers

 improve security using multiple cipher alphabets
 make cryptanalysis harder with more alphabets to guess and flatter
frequency distribution
 use a key to select which alphabet is used for each letter of the message
 use each alphabet in turn
 repeat from start after end of key is reached
 Frequencies After Polyalphabetic Encryption

Letter Relative Frequency

14.000
12.000
equiprobable
10.000
unencrypted
8.000
two keys
6.000
four keys
4.000
eight keys
2.000
0.000
A D G J M P S V Y
Frequencies After Polyalphabetic Encryption

Sorted relative frequencies

14
12
10 Equiprobible
Unencrypted/1 key
8
two keys
6
four keys
4
eight keys
2
0
1 4 7 10 13 16 19 22 25
 Transposition Ciphers
A transposition cipher does not substitute one symbol
for another, instead it changes the location of the
symbols.

A transposition cipher reorders symbols.

Topics:

Keyless Transposition Ciphers

Keyed Transposition Ciphers
Combining Two Approaches
 Keyless Transposition Ciphers

Simple transposition ciphers, which were used in the past, are

keyless.

Example
A good example of a keyless cipher using the first method is the
rail fence cipher. The ciphertext is created reading the pattern
row by row. For example, to send the message “Meet me at the
park” to Bob, Alice writes

She then creates the ciphertext “MEMATEAKETETHPR”.

 Example

Alice and Bob can agree on the number of columns and use the
second method. Alice writes the same plaintext, row by row, in a
table of four columns.

She then creates the ciphertext “MMTAEEHREAEKTTP”.

 Example

The cipher in Example is actually a transposition cipher. The

following shows the permutation of each character in the
plaintext into the ciphertext based on the positions.

The second character in the plaintext has moved to the fifth

position in the ciphertext; the third character has moved to the
ninth position; and so on. Although the characters are
permuted,
there is a pattern in the permutation: (01, 05, 09, 13), (02, 06,
10, 13), (03, 07, 11, 15), and (08, 12). In each section, the
difference between the two adjacent numbers is 4.
 Keyed Transposition Ciphers

The keyless ciphers permute the characters by using writing plaintext in

one way and reading it in another way The permutation is done on the
whole plaintext to create the whole ciphertext.

Another method is to divide the plaintext into groups of predetermined

size, called blocks, and then use a key to permute the characters in
each block separately.
 Example
Alice needs to send the message “Enemy attacks tonight” to
Bob..

The key used for encryption and decryption is a permutation

key, which shows how the character are permuted.

The permutation yields

 Combining Two Approaches
Example
Figure
 Keys
In Example , a single key was used in two directions for the
column exchange: downward for encryption, upward for
decryption. It is customary to create two keys.

Figure Encryption/decryption keys in transpositional ciphers

Continued
Figure Key inversion in a transposition cipher
 Continued
We can use matrices to show the encryption/decryption process
for a transposition cipher.

Example

Figure Representation of the key as a matrix in the transposition cipher

 Continued
Figure shows the encryption process. Multiplying the 4 × 5
plaintext matrix by the 5 × 5 encryption key gives the 4 × 5
ciphertext matrix.

Figure Representation of the key as a matrix in the transposition cipher

 Continued
Double Transposition Ciphers
Figure Double transposition cipher

3.132
 Stream and Block Ciphers
The literature divides the symmetric ciphers into two broad categories:
stream ciphers and block ciphers. Although the definitions are normally
applied to modern ciphers, this categorization also applies to traditional
ciphers.

Topics :
Stream Ciphers
Block Ciphers
Combination
 Stream Ciphers
Call the plaintext stream P, the ciphertext stream C, and the key stream K.

Figure Stream cipher

 Continued
Example
Additive ciphers can be categorized as stream ciphers in which
the key stream is the repeated value of the key. In other words,
the key stream is considered as a predetermined stream of
keys or
K = (k, k, …, k). In this cipher, however, each character in the
ciphertext depends only on the corresponding character in the
plaintext, because the key stream is generated independently.
Example
The monoalphabetic substitution ciphers discussed in this
chapter are also stream ciphers. However, each value of the
key stream in this case is the mapping of the current plaintext
character to the corresponding ciphertext character in the
mapping table.
 Continued
Example
Vigenere ciphers are also stream ciphers according to the
definition. In this case, the key stream is a repetition of m
values, where m is the size of the keyword. In other words,

Example
We can establish a criterion to divide stream ciphers based on
their key streams. We can say that a stream cipher is a
monoalphabetic cipher if the value of ki does not depend on the
position of the plaintext character in the plaintext stream;
otherwise, the cipher is polyalphabetic.
 Continued

 Additive ciphers are definitely monoalphabetic because ki in

the key stream is fixed; it does not depend on the position of
the character in the plaintext.

 Monoalphabetic substitution ciphers are monoalphabetic

because ki does not depend on the position of the
corresponding character in the plaintext stream; it depends
only on the value of the plaintext character.

 Vigenere ciphers are polyalphabetic ciphers because ki

definitely depends on the position of the plaintext character.
However, the dependency is cyclic. The key is the same for
two characters m positions apart.
 Stream Ciphers

In a block cipher, a group of plaintext symbols of size m (m > 1) are encrypted

together creating a group of ciphertext of the same size. A single key is used to
encrypt the whole block even if the key is made of multiple values. Figure 3.27 shows
the concept of a block cipher.

Figure 3.27 Block cipher

 Continued
Example
Playfair ciphers are block ciphers. The size of the block is m =
2. Two characters are encrypted together.
Example
Hill ciphers are block ciphers. A block of plaintext, of size 2 or
more is encrypted together using a single key (a matrix). In
these ciphers, the value of each character in the ciphertext
depends on
all the values of the characters in the plaintext. Although the key
is made of m × m values, it is considered as a single key.
Example
From the definition of the block cipher, it is clear that every
block cipher is a polyalphabetic cipher because each character
in a ciphertext block depends on all characters in the plaintext
block.
3.139
 Combination
In practice, blocks of plaintext are encrypted individually, but
they use a stream of keys to encrypt the whole message
block by block. In other words, the cipher is a block cipher
when looking at the individual blocks, but it is a stream
cipher when looking at the whole message considering each
block as a single unit.
 Product Ciphers
 ciphers using substitutions or transpositions are not secure because of
language characteristics
 hence consider using several ciphers in succession to make harder, but:
 two substitutions make a more complex substitution

 two transpositions make more complex transposition

 but a substitution followed by a transposition makes a new much

harder cipher
 this is bridge from classical to modern ciphers
The transposition cipher can be made significantly more secure by
performing more than one stage of transposition. If we apply previous
mapping again:

To visualize the result of this double transposition, designate the letters in the
original plaintext message by the numbers designating their position.
After the first transposition, we have

But after the second transposition, we have

The example just given suggests that multiple stages of encryption can
produce an algorithm that is significantly more difficult to cryptanalyze
This is as true of substitution ciphers as it is of transposition ciphers.
S-box
P-box
P-box
Exclusive-OR
Exclusive-OR
 Steganography & Cryptography

The methods of steganography conceal the existence of the message,

whereas the methods of cryptography render the message unintelligible to
outsiders by various transformations of the text
 Steganography
Hide a real message in a fake, but meaningful, message
Assumes recipient knows the method of hiding
Examples:
 Selected letters in a document are marked to form the hidden message
 Invisible ink (letters only become visible when exposed to a chemical or
heat)
 Using selected bits in images or videos to carry the message
Advantages
 Does not look like you are hiding anything
Disadvantages
Once attacker knows your method, everything is lost
Can be ineffcient (need to send lot of information to carry small message)
 Steganography Example
Dear George,
Greetings to all at Oxford. Many thanks for your
letter and for the Summer examination package.
All Entry Forms and Fee Forms should be ready
for final despatch to the Syndicate by Friday
20th or at the very latest, I'm told, by the 21st.
Admin has improved here, though there's room
for improvement still; just give us all two or three
more years and we'll really show you! Please
don't let these wretched 16+ proposals destroy
your basic O and A pattern. Certainly this
sort of change, if implemented immediately,
would bring chaos.
Sincerely yours.
Review
 a b

k1 1 2

k2 2 3

k3 3 4
 a b

k1 1 2

k2 2 3

k3 3 4
 Summary
 have considered:
 classical cipher techniques and terminology
 monoalphabetic substitution ciphers
 cryptanalysis using letter frequencies
 Playfair cipher
 polyalphabetic ciphers
 transposition ciphers
 product ciphers and rotor machines
 steganography