CIPHERS

Classical Encryption
Techniques

1
 Basic Terminology

• plaintext - the original message

• ciphertext - the coded message
• cipher - algorithm for transforming plaintext/ciphertext
• key - info used in cipher known only to sender/receiver
• encipher (encrypt) - converting plaintext to ciphertext
• decipher (decrypt) - recovering plaintext from ciphertext
• cryptography - study of encryption principles/methods
• cryptanalysis (codebreaking) - the study of principles/ methods of
deciphering ciphertext without knowing key
• cryptology - the field of both cryptography and cryptanalysis

2
Components of Encryption system

Plaintext
Ciphertext
Encryption algorithm
Decryption algorithm
Key (optional)
 Types of encryption

Encryption

Symmetric Asymmetric/ Public key

Encryption Encryption
Knapsack, RSA, Diffie-
Hellman key exchange

Stream
Block cipher
cipher
A5/1, DES, AES,
RC4 Triple DES,
RC5, Blowfish
Substitution Transposition
cipher cipher

Caesar, Hill, Rail fence,

playfair etc. double
transposition
 Two kinds of Ciphers

State-of-the-art: two kinds of most popular encryption

algorithms
• Symmetric ciphers/Secret key ciphers
– Sender and receiver share a common key
• Public key ciphers/Asymmetric ciphers
– Sender and receiver have asymmetric information of
the key(s) (public key and private key)

5
Symmetric Encryption
• Conventional / private-key / single-key
• It was the only type prior to invention of public-key
in 1970’s
• It remains very widely used
• In this, sender and recipient share a common key
– Both parties have full information of the key
• All classical encryption algorithms are common key
(private-key) algorithms

6
 Symmetric Cipher Model
Sender side Receiver side

7
Symmetric key cipher

Figure: General idea of symmetric-key cipher

Asymmetric Key Cryptography
When someone wants to send an encrypted message, they can pull
the intended recipient's public key from a public directory and use it
to encrypt the message before sending it. The recipient of the
message can then decrypt the message using their related private key.

Sender Receiver
(A) (B)

Plain Cipher Netw Cipher Plain

text text ork text text

Encrypt Decrypt
with B’s with B’s
public key private key
Asymmetric Key Cryptography Example

Customer Bank’s
A public key

Customer Bank’s Bank’s Bank

B public key private key

Customer Bank’s
C public key
Difference between symmetric key encryption and
Asymmetric key encryption
Criteria Symmetric key Encryption Asymmetric key
Encryption
Key used for Same key is used for One key used for
encryption and decryption encryption and another,
encryption / different key is used for
decryption
decryption

Speed of encryption Very fast

Slower
/ decryption

Size of resulting Usually same as or less than More than the original
the original clear text size clear text size
encrypted text

Key agreement / A big problem as out-of-band No problem at all

method is used such as via
exchange face-to-face meeting.
Difference between symmetric key encryption and
Asymmetric key encryption
Criteria Symmetric key Asymmetric key
Encryption Encryption
Number of keys Equals about the square of Same as the number of
required as compared to the number of participants, participants, so scales up
the number of so scalability is an issue quite well
participants in the n(n-1)/2 keys for n n keys for n participants
message exchange participants

Usage Mainly for encryption and Can be used for encryption

decryption (confidentiality), a n d d e c r y p t i o n
cannot be used for digital (confidentiality) as well as
signatures (integrity and for digital signatures
(integrity and non-
non-repudiation checks)
repudiation checks)
Requirements
• Two requirements for secure use of symmetric encryption:
– a strong encryption algorithm (keeping key secret is sufficient
for security)
– a secret key known only to sender / receiver
Y = EK(X) or Y=E(K,X)
X = DK(Y) or X=D(K,Y)
EK is encryption using plaintext and key K
DK is decryption using ciphertext and same key K
• assume encryption algorithm is known
• implies a secure channel to distribute key

13
Cryptography
• Can be characterized by:
– type of encryption operations used
• substitution / transposition / product systems
– number of keys used
• single-key or private / two-key or public
– way in which plaintext is processed
• Block: process one block of elements a time
• Stream: continuous input, output one element a
time

14
Cryptanalysis and Brute-Force Attack

• The objective of attacking an encryption system

is to recover the key in use rather than simply
to recover the plaintext of a single ciphertext.
• Cryptanalysis
• Cryptanalytic attacks rely on nature of algorithm used
and some knowledge of plaintext-ciphertext pairs.
• Brute-force attack
• Attacker tries every possible key on ciphertext
• On average half of possible keys must be tried.
. 15
Types of Cryptanalytic Attacks

16
 Types of Cryptanalytic Attacks

• ciphertext only
– known to cryptoanalyst a) algorithm b) ciphertext
• known plaintext
– know some given plaintext/ciphertext pairs
• chosen plaintext
– select plaintext and obtain ciphertext
• chosen ciphertext
– select ciphertext and obtain plaintext
• chosen text
– select either plaintext or ciphertext to en/decrypt to attack
cipher 17
Ciphertext only Attack

18
Ciphertext only Attack

19
Known plaintext Attack

20
Known plaintext Attack

21
Chosen plaintext Attack

22
Chosen plaintext Attack

23
Chosen ciphertext Attack

24
Chosen ciphertext Attack

25
Brute Force attack
• always possible to simply try every key
• most basic attack, proportional to key size
• assume either know / recognise plaintext

26
 Statistical attack
A statistical attack attempts to exploit some statistical
weakness in the cryptosystem such as a lack of
randomness in key generation

Example: Letter ‘E’ is the most frequently used letter. The

cryptanalyst finds the mostly used character in the
ciphertext and assumes that the corresponding plaintext
character is ‘E’. After finding a few pairs, he can find the
key and use it to decrypt the message

27
 Pattern attack
Some ciphers may hide the characteristics of the language
but may create some patterns in the ciphertext

A cryptanalyst uses a pattern attack to break the cipher.

Therefore it is important to use ciphers that make the
ciphertext look as random as possible

28
More Definitions
• Unconditional security
– no matter how much computer power is
available, the cipher cannot be broken since
the ciphertext provides insufficient information
to uniquely determine the corresponding
plaintext
• Computational security
– given limited computing resources (e.g. time
needed for calculations is great), the cipher
cannot be broken

29
 Classical or Traditional Ciphers

• Traditional symmetric-key ciphers are divided into two

broad categories:
• Substitution ciphers (replace one symbol in the
ciphertext with another symbol)
• Transposition ciphers (re-order the position of
symbols in the plaintext)

30
Classical Substitution Ciphers

• In this, letters of plaintext are replaced by other

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

31
Substitution Ciphers
• It can be categorized as:
• Monoalphabetic Cipher
• Additive Cipher
• Shift Cipher
• Caesar Cipher
• Multiplicative Cipher
• Affine Cipher
• Polyalphabetic Cipher
• Autokey Cipher
• Playfair Cipher
• Hill Cipher
• Vigenere cipher
32
Monoalphabetic Cipher

• In monoalphabetic substitution, the relationship between

a symbol in the plaintext to a symbol in the ciphertext is
always one-to-one.

33
Examples of Monoalphabetic Cipher

34
Example of Monoalphabetic Cipher

PLAINTEXT

A long time ago, in a galaxy far, far away... It is a dark time for the
Rebellion.

KEY
AB C D E F G H I J K L MN OPQRSTUVWXYZ

P R M Z N G H C O A F E B W Q K S Y I UT D V X J L

Cipher text:

P EQWH UOBN PHQ, OW P HPEPXJ GPY, GPY PVPJ... OU OI P

ZPYF UOBN GQY UCN YNRNEEOQW.

35
Monoalphabetic Cipher Security
• Now we have a total of 26! (26 factorial) = 4.0329146
e+26 keys
• with so many keys, you might think it is secure
– The simplicity and strength of the monoalphabetic
substitution cipher dominated for the first millenium
AD.
• but it would be !!!WRONG!!!
– First broken by Arabic scientists in 9th century

36
Cryptanalysis
• given ciphertext:
UZQSOVUOHXMOPVGPOZPEVSGZWSZOPFPESXUDBMETSXAIZ
VUEPHZHMDZSHZOWSFPAPPDTSVPQUZWYMXUZUHSX
EPYEPOPDZSZUFPOMBZWPFUPZHMDJUDTMOHMQ

• count relative letter frequencies (see text)

• 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

37
Additive Cipher
• The plaintext consists of lowercase letters
• The ciphertext consists of uppercase
letters
• Numerical values are assigned to each
letter

38
Additive Cipher

39
Examples

• Use the additive cipher with key = 15 to encrypt

the message “hello”.

40
Examples

• Use the additive cipher with key = 15 to decrypt the

message “WTAAD”.

-a mod b = b - (a mod b)

41
 Shift Cipher
• Historically, additive ciphers are called
shift ciphers
• It is because the encryption algorithm can
be interpreted as “shift key characters
down” and decryption algorithm can be
interpreted as “shift key characters up”

42
Caesar Cipher
• Earliest known substitution cipher
• Used by Julius Caesar
• first attested use in military affairs
• replaces each letter by a letter three
places down the alphabet

43
 Caesar Cipher
• can define transformation as:
a b c d e f g h i j k l m n o p q r s t u v w x y z
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

• mathematically give each letter a number

a b c d e f g h i j k l m n o p q r s t u v w x y Z

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

• then have Caesar cipher as:

C = E(p) = (p + k) mod (26) , k=3

p = D(C) = (C – k) mod (26), k=3

44
Cryptanalysis of
Additive/Shift/Caesar Cipher
• only have 26 possible keys
– Could shift K = 0, 1, 2, …, 25 slots
• could simply try each in turn
• In that also, k=0 is useless so total 25 options
to try
• a brute force search
• given ciphertext, just try all shifts of letters

45
Example –Brute Force

• Eve has intercepted the ciphertext “UVACLYFZLJBYL”.

Show how she can use a brute-force attack to break the
cipher.

46
Example –Statistical

47
Multiplicative Ciphers

C = (P X k)mod 26
P = (C x k^-1) mod 26
Knowledge of multiplicative inverse is
necessary

48
Affine Ciphers

C = (P xk1 +k2) mod 26

P = ((C-k2) x k1^-1) mod 26

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

• The key stream k=(k1,k2,…) in which each ki is

used to encipher the ith character in the plaintext
to create the ith character in the ciphertext
50
 Autokey Ciphers
• The key is a stream of subkeys in which each
subkey is used to encrypt the corresponding
character in the plaintext

• The name of this cipher implies that the subkeys

are automatically created from the plaintext cipher
characters during the encryption process

51
 Autokey Ciphers
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.

52
 Playfair Ciphers
• The secret key in this cipher is made of 25 alphabets
arranged in a 5X5 matrix (letters I and J are considered
same while encrypting)

• Different arrangements of the letters in the matrix can

create many different secret keys

53
 Playfair Ciphers
If two letters in a pair are located:
• In the same row of the secret key, the corresponding
encrypted key character is the letter next to it on the right
in the same row

• In the same column of the secret key, the corresponding

encrypted key character is the letter beneath it on the
right in the same column

• Not in same row or column of the secret key, the

corresponding encrypted key character is the letter that is
in its own row but in the same column as the other letter
54
Playfair Ciphers

55
Playfair Ciphers

56
Playfair Ciphers

57
Hill Ciphers

• Example of polyalphabetic cipher

• The plaintext is divided into equal-size blocks.
• Type of block cipher.
• In a Hill cipher, the key is a square matrix of size
m × m in which ‘m’ is the size of the block.
• If we call the m characters in the plaintext block
P1, P2, …, Pm, the corresponding characters in
the ciphertext block are C1, C2, …, Cm.

58
 Hill Ciphers
The key matrix in the Hill cipher needs to have a
multiplicative inverse.

59
Hill Ciphers

• In general terms, the Hill system can be

expressed as
• C = E(K, P) = PK mod 26
• P = D(K, C) = CK-1 mod 26 = PKK-1 = P

60
Hill Cipher Example

• Use a Hill Cipher to encipher message

“ATTACK AT DAWN” using the following
3x3 key matrix
• K=245
921
3 7 17
• Cipher Text is PFOGOA NP GXFX

61
 Hill Ciphers
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”.

62
 Hill Ciphers
Assume that Eve knows that m = 3. She has intercepted three
plaintext/ciphertext pair blocks (not necessarily from the same
message)

63
 Hill Ciphers
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

Now she has the key and can break any ciphertext encrypted with
that key.
64
 Vigenere Ciphers

We can encrypt the message “She is listening” using the 6-character

keyword “PASCAL”.

65
 Vigenere Ciphers
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).

66