CS436: Selected Topics I

Cryptography and Network Security

Lecture 03: Classical Encryption Techniques

Zagazig University
Faculty of Computers & Informatics

Department
Department
of Computer
of Information
Science
Topics
I. Introduction
1. Course Overview
2. Information and Network Security Concepts
II. Cryptography
3. Classical Encryption Techniques
4. Block Ciphers and the Data Encryption Standard
5. Advanced Emcryption Standard (AES)
6. Symmetric Ciphers Mode of Operations
7. Stream Ciphers
8. Public-Key Cryptography and RSA
9. Key Management
10. Hash and MAC Algorithms
11. Digital Signatures

Department of Computer Science 2

Topics
III.Network Security
12. Transport-Level Security
13.Wireless Network Security
14.SET Protocol
15.IP Security

Department of Computer Science 3

Course Syllabus
• Cryptography
- Classical Encryption Techniques
Symmetric Cipher Model
Substitution Techniques
Transposition Techniques

Department of Computer Science 4/50

Classical Encryption
• As opposed to modern cryptography
• Goals:

- to introduce basic concepts & terminology of encryption

- to prepare us for studying modern cryptography

Department of Computer Science 5/50

Symmetric Encryption
• 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
• Most widely used

Department of Computer Science 6/50

Some Basic Terminology
• 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: study of principles/ methods of
deciphering ciphertext without knowing key
• Cryptology: field of both cryptography and cryptanalysis

Department of Computer Science 7/50

Cryptography
• Characterize cryptographic system by:
- Type of encryption operations used
substitution / transposition / product
- Number of keys used
single-key or private / two-key or public
- Way in which plaintext is processed
block / stream

Department of Computer Science 8/50

Symmetric Cipher Model

Same Key

Department of Computer Science 9/50

Requirements
• Two requirements for secure use of symmetric encryption:
1. A strong encryption algorithm
2. A secret key known only to sender / receiver
• Mathematically have:
- Y = EK(X)
- X = DK(Y)
• Assume encryption algorithm is known
• Implies a secure channel to distribute key

Department of Computer Science 10/50

Requirements – Cont.

Department of Computer Science 11/50

Cryptanalysis
• Objective to recover key not just message
• General approaches:
- Cryptanalytic attack
- Brute-force attack

Department of Computer Science 12/50

Cryptanalytic Attacks
• 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

Department of Computer Science 13/50

Ciphertext-only attack
• Given: a ciphertext c
• Q: what is its plaintext m?
• An encryption scheme is completely insecure if it cannot resist ciphertext-only attacks.

Department of Computer Science 14/50

Known-plaintext attack
• Given: (m1,c1), (m2,c2), …, (mk,ck) and a new ciphertext c.

• Q: what is the plaintext of c?

• Q: what is the key in use?

Department of Computer Science 15/50

Chosen-plaintext attack

• Given: (m1,c1), (m2,c2), …, (mk,ck), where m1, m2, …, mk are chosen by the
adversary; and a new ciphertext c.

• Q: what is the plaintext of c, or what is the secret key?

Department of Computer Science 16/50

Chosen-ciphertext attack
• Given: (m1,c1), (m2,c2), …, (mk,ck), where c1, c2, …, ck are chosen by the adversary; and a new ciphertext c.

• Q: what is the plaintext of c, or what is the secret key?

Department of Computer Science 17/50

More Definitions
• 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
• Computational Security
- given limited computing resources (e.g. time needed for calculations is greater than age of universe), the
cipher cannot be broken

Department of Computer Science 18/50

Brute Force Attack
• Always possible to simply try every key
• Most basic attack, proportional to key size
• Assume either know / recognise plaintext

Department of Computer Science 19/50

Classical Substitution Ciphers
• Where 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

Department of Computer Science 20/50

Caesar Cipher
• Earliest known substitution cipher
• By Julius Caesar
• First attested use in military affairs
• Replaces each letter by n letter on
• example:

plain: meet me after the toga party

cipher: PHHW PH DIWHU WKH WRJD SDUWB

Department of Computer Science 21/50

Caesar Cipher – Cont.
• Can define transformation as:
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

• 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)
p = D(c) = (c – k) mod (26)

Department of Computer Science 22/50

Cryptanalysis of Caesar Cipher
• Only have 26 possible ciphers
- A maps to A,B,..Z
• Could simply try each in turn
• A brute force search
- Given ciphertext, just try all shifts of letters
- Need to recognize plaintext

Department of Computer Science 23/50

Cryptanalysis of Caesar Cipher – Cont.

Department of Computer Science 24/50

Monoalphabetic Cipher
• Rather than just shifting the alphabet
• could shuffle (jumble) the letters arbitrarily
• each plaintext letter maps to a different random ciphertext letter
• hence key is 26 letters long

Plain: abcdefghijklmnopqrstuvwxyz
Cipher: DKVQFIBJWPESCXHTMYAUOLRGZN

Plaintext: ifwewishtoreplaceletters
Ciphertext: WIRFRWAJUHYFTSDVFSFUUFYA

Department of Computer Science 25/50

Monoalphabetic Cipher – Cont.
• Now have a total of 26! = 4 x 1026 keys
• With so many keys, might think is secure
• But would be !!!WRONG!!!
• Problem is language characteristics

Department of Computer Science 26/50

Language Redundancy and Cryptanalysis
• Human languages are not random

• 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

• There are tables of single, double & triple letter frequencies for various languages

Department of Computer Science 27/50

English Letter Frequencies

Department of Computer Science 28/50

Department of Computer Science 29/50
Statistics for double & triple letters
• In decreasing order of frequency

• Double letters:
th he an in er re es on, …

• Triple letters:
the and ent ion tio for nde, …

Department of Computer Science 30/50

Use in Cryptanalysis

• Key concept: monoalphabetic substitution does not

change relative letter frequencies

• To attack, we
- calculate letter frequencies for ciphertext

- compare this distribution against the known one

Department of Computer Science 31/50

Example 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

Department of Computer Science 32/50

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

Department of Computer Science 33/50

 Playfair Cipher
• Improves security by encrypting multiple letters.
• A 5X5 matrix of letters based on a keyword
• Fill in letters of keyword (sans duplicates)
• Fill rest of matrix with other letters
• E.g. using the keyword MONARCHY

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

Department of Computer Science 34/50

Encrypting and Decrypting
• Suppose that the plantext is “meet at the schoolhouse”
• if a pair is a repeated letter, insert filler like ‘x’ so our plane text will be “me et at
th es ch ox ol ho us ex”
• plaintext is encrypted two letters at a time
1.if both letters fall in the same row, replace each with letter to right (wrapping
back to start from end)
2.if both letters fall in the same column, replace each with the letter below it (again
wrapping to top from bottom)
3.otherwise each letter is replaced by the letter in the same row and in the column of
the other letter of the pair

Department of Computer Science 35/50

Example
• Using "playfair example" as the key, the table becomes:
• P L A Y F
• I R E X M
• B C D G H
• J K N O S
• T U V W Z
• Encrypting the message "Hide the gold in the tree stump":
• HI DE TH EG OL DI NT HE TR EX ES TU MP
• ^

- The pair HI forms a rectangle, replace it with BM

- The pair DE is in a column, replace it with ND
- The pair TH forms a rectangle, replace it with ZB
- The pair EG forms a rectangle, replace it with XD
- The pair OL forms a rectangle, replace it with KY
- The pair DI forms a rectangle, replace it with BE
- The pair NT forms a rectangle, replace it with JV
- The pair HE forms a rectangle, replace it with DM
- The pair TR forms a rectangle, replace it with UI
- The pair EX (X inserted to split EE) is in a row, replace it with XM
- The pair ES forms a rectangle, replace it with MN
- The pair TU is in a row, replace it with UV
- The pair MP forms a rectangle, replace it with IF

Department of Computer Science 36/50

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 (verses 26 for a monoalphabetic) and
correspondingly more ciphertext
• it can be broken, given a few hundred letters; since still has much of plaintext structure

Department of Computer Science 37/50

Vigenère Cipher
• Write the plaintext out
• Write the keyword repeated above it
• Use each key letter as a caesar cipher key
• Encrypt the corresponding plaintext letter
• e.g. using keyword deceptive
key: deceptivedeceptivedeceptive
plaintext: wearediscoveredsaveyourself
ciphertext:ZICVTWQNGRZGVTWAVZHCQYGLMGJ

Department of Computer Science 38/50

Vigenère Cipher

Department of Computer Science 39/50

Security of Vigenère Ciphers
• There are multiple (how many?) ciphertext letters corresponding
to each plaintext letter.

• So, letter frequencies are obscured but not totally lost.

• To break Vigenere cipher:

1. Try to guess the key length. How?

2. If key length is N, the cipher consists of N Caesar ciphers.

Plaintext letters at positions k, N+k, 2N+k, 3N+k, etc., are
encoded by the same cipher.

3. Attack each individual cipher as before.

Department of Computer Science 40/50
Guessing the Key Length
• Main idea: Plaintext words separated by multiples of the key length are encoded in
the same way.
• In our example, if plaintext = “…thexxxxxxthe…” then “the” will be encrypted to the
same ciphertext words.

• So look at the ciphertext for repeated patterns.

• E.g. repeated “VTW” in the previous example suggests a key length of 3 or 9:

ciphertext: ZICVTWQNGRZGVTWAVZHCQYGLMGJ

• Of course, the repetition could be a random fluke.

Department of Computer Science 41/50

One-Time Pad
• If a truly random key as long as the message is used, the cipher
will be secure
• called a One-Time pad
• Is unbreakable since ciphertext bears no statistical relationship to
the plaintext
• Since for any plaintext & any ciphertext there exists a key
mapping one to other
• Can only use the key once though
• Problems in generation & safe distribution of key

Department of Computer Science 42/50

One-Time Pad
• The one-time pad offers complete security but, in practice, has two fundamental
difficulties:
- There is the practical problem of making large quantities of random keys
Any heavily used system might require millions of random characters on a regular basis
- Mammoth key distribution problem
For every message to be sent, a key of equal length is needed by both sender and receiver
• Because of these difficulties, the one-time pad is of limited utility
- Useful primarily for low-bandwidth channels requiring very high security
• The one-time pad is the only cryptosystem that exhibits perfect secrecy

Department of Computer Science 43/50

Hill Cipher
• Developed by the mathematician Lester Hill in 1929
• The 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 ... z = 25).

Department of Computer Science 44/50

Hill Cipher
• For m = 3, the system can be described as follows:

Department of Computer Science 45/50

Hill Cipher

Department of Computer Science 46/50

Hill Cipher
• Decryption requires using the inverse of the matrix K. The inverse K -1 of a matrix K is defined
by the equation KK-1 = K-1K = I
• If we change one letter in the plaintext, all the letters of the ciphertext will be affected.

Department of Computer Science 47/50

Transposition Ciphers
• Transposition or permutation ciphers
• Hide the message by rearranging the letter order without altering the actual letters used
• Can recognize these since have the same frequency distribution as the original text

Department of Computer Science 48/50

Row Transposition Ciphers
• Plaintext is written row by row in a rectangle.

• Ciphertext: write out the columns in an order specified by a key.

a t t a c k p
Key: 3 4 2 1 5 6 7 o s t p o n e
d u n t i l t
w o a mx y z
Plaintext:

Ciphertext: TTNAAPTMTSUOAODWCOIXKNLYPETZ

Department of Computer Science 49/50

Permutation Cipher

Department of Computer Science 50/50

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

Department of Computer Science 51/50

Rotor Machines
• Before modern ciphers, rotor machines were most common
complex ciphers in use
• Widely used in WW2
• Implemented a very complex, varying substitution cipher
• Used a series of cylinders, each giving one substitution, which
rotated and changed after each letter was encrypted
• With 3 cylinders have 263=17576 alphabets

Department of Computer Science 52/50

Rotor Machines

Department of Computer Science 53/50

Rotor Machines

Department of Computer Science 54/50

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
• Reading: Chapter 2

Department of Computer Science 55/50

 Questions

Zagazig University
Faculty of Computers & Informatics

Department
Department of Computer
of Computer Science
Science 56