MODULE 1�

Classical Encryption Techniques: Symmetric cipher model, Substitution techniques, Transposition techniques (Text 1: Chapter 1)

​

Basic Concepts of Number Theory and Finite Fields: Euclidean algorithm, Modular arithmetic (Text 1: Chapter 3)

​

​

Text Books:

1. William Stallings , “Cryptography and Network Security Principles and Practice”, Pearson Education Inc., 6th Edition, 2014, ISBN: 978-93-325-1877-3
2. Bruce Schneier, “Applied Cryptography Protocols, Algorithms, and Source

code in C”, Wiley Publications, 2nd Edition, ISBN: 9971-51-348-X.

Reference Books:

1. Cryptography and Network Security, Behrouz A. Forouzan, TMH, 2007.

2. Cryptography and Network Security, Atul Kahate, TMH, 2003.

​

​

​

Symmetric Cipher Model

Basic Terminology

• plaintext - the original message
• ciphertext - the 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 (codebreaking) - the study of principles/ methods of deciphering ciphertext without knowing key
• cryptology - the field of both cryptography and cryptanalysis

Symmetric Cipher Model

5

Wednesday, September 22, 2021

Model of Conventional Cryptosystem

Requirements

• two requirements for secure use of symmetric encryption:
• a strong encryption algorithm
• a secret key known only to sender / receiver

Y = E_K(X)

X = D_K(Y)

• assume encryption algorithm is known
• implies a secure channel to distribute key

Cryptography

• can characterize 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

Types of Cryptanalytic Attacks

• ciphertext only
• only know algorithm / ciphertext, statistical, can identify plaintext
• known plaintext
• know/suspect plaintext & ciphertext to attack cipher
• chosen plaintext
• select plaintext and obtain ciphertext to attack cipher
• chosen ciphertext
• select ciphertext and obtain plaintext to attack cipher
• chosen text
• select either plaintext or ciphertext to en/decrypt to attack cipher

Brute Force Search

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

​

​

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

​

​

Caesar Cipher

• earliest known 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

​

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

0 1 2 3 4 5 6 7 8 9 10 11 12

n o p q r s t u v w x y Z

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)

​

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
• do need to recognize when have plaintext

​

14

Wednesday, September 22, 2021

Three important characteristics of this problem enabled us to use a brute-force cryptanalysis:

• The encryption and decryption algorithms are known.
• There are only 25 keys to try.
• The language of the plaintext is known and easily recognizable.

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

​

Monoalphabetic Cipher Security

• 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

Language Redundancy and Cryptanalysis

• human languages are redundant
• letters are not equally commonly used
• in English e is by far the most common letter
• then T,R,N,I,O,A,S
• other letters are fairly rare
• cf. Z,J,K,Q,X
• have tables of single, double & triple letter frequencies

English Letter Frequencies

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 Key Matrix

• a 5X5 matrix of letters based on a keyword
• fill in letters of keyword (sans duplicates)
• fill rest of matrix with other letters
• eg. using the keyword MONARCHY

MONAR

CHYBD

EFGIK

LPQST

UVWXZ

21

Wednesday, September 22, 2021

Playfair Cipher

Security of the 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
• was widely used for many years (eg. US & British military in WW1)
• it can be broken, given a few hundred letters
• since still has much of plaintext structure

23

Wednesday, September 22, 2021

Hill Cipher

c₁ = (k_11P1 + k_12P2 + k_13P3) mod 26

c₂ = (k_21P1 + k_22P2 + k_23P3) mod 26

c₃ = (k_31P1 + k_32P2 + k3_3P3) mod 26

This can be expressed in term of column vectors and matrices:

HILL CIPHER

Encryption

C = K.P (mod 26)

Decryption

P = K^-1.C (mod 26)

K^-1 = adjoint of K

determinant of K

Polyalphabetic Ciphers (Vigenère cipher)

26

Wednesday, September 22, 2021

key: deceptivedeceptivedeceptive

plaintext: wearediscoveredsaveyourself

ciphertext: ZICVTWQNGRZGVTWAVZHCQYGLMGJ

key: deceptivewearediscoveredsav

plaintext: wearediscoveredsaveyourself ciphertext: ZICVTWQNGKZEIIGASXSTSLVVWLA

AT&T engineer named Gilbert Vernam in 1918

27

Wednesday, September 22, 2021

One-Time Pad Army Signal Corp officer, Joseph Mauborgne

In theory, we need look no further for a cipher. 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. Any heavily used system might require millions of random characters on a regular basis. Supplying truly random characters in this volume is a significant task.

​

2) Even more daunting is the problem of key distribution and protection. For every message to be sent, a key of equal length is needed by both sender and receiver. Thus, a mammoth key distribution problem exists.

​

Because of these difficulties, the one-time pad is of limited utility, and is useful primarily for low-bandwidth channels requiring very high security.

Transposition Ciphers

• now consider classical transposition or permutation ciphers
• these hide the message by rearranging the letter order
• without altering the actual letters used
• can recognise these since have the same frequency distribution as the original text

Rail Fence cipher

• write message letters out diagonally over a number of rows
• then read off cipher row by row
• eg. write message out as:

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

e t e f e t e o a a t

• giving ciphertext

MEMATRHTGPRYETEFETEOAAT

​

​

Row Transposition Ciphers

• a more complex scheme
• write letters of message out in rows over a specified number of columns
• then reorder the columns according to some key before reading off the rows

Key: 3 4 2 1 5 6 7

Plaintext: a t t a c k p

o s t p o n e

d u n t i l t

w o a m x y z

Ciphertext: TTNAAPTMTSUOAODWCOIXKNLYPETZ

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

​

Rotor Machines

• before modern ciphers, rotor machines were most common product cipher
• were widely used in WW2
• German Enigma, Allied Hagelin, Japanese Purple
• 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 26³=17576 alphabets

Steganography

• an alternative to encryption
• hides existence of message
• using only a subset of letters/words in a longer message marked in some way
• using invisible ink
• hiding in LSB in graphic image or sound file
• has drawbacks
• high overhead to hide relatively few info bits

​

Basic Concepts in Number Theory and Finite Fields

Introduction

• concern operations on “numbers”
• where what constitutes a “number” and the type of operations varies considerably
• start with basic number theory concepts

Divisors

• say a non-zero number b divides a if for some m have a=mb (a,b,m all integers)
• that is b divides into a with no remainder
• denote this b|a
• and say that b is a divisor of a
• eg. all of 1,2,3,4,6,8,12,24 divide 24
• eg. 13 | 182; –5 | 30; 17 | 289; –3 | 33; 17 | 0

Properties of Divisibility

• If a|1, then a = ±1.
• If a|b and b|a, then a = ±b.
• Any b /= 0 divides 0.
• If a | b and b | c, then a | c
• e.g. 11 | 66 and 66 | 198 so 11 | 198
• If b|g and b|h, then b|(mg + nh)

for arbitrary integers m and n

e.g. b = 7; g = 14; h = 63; m = 3; n = 2

7|14 and 7|63 hence 7 | 42+126 = 168

​

Division Algorithm

• if divide a by n get integer quotient q and integer remainder r such that:
• a = qn + r where 0 <= r < n; q = floor(a/n)
• remainder r often referred to as a residue

​

​

​

​

Greatest Common Divisor (GCD)

• a common problem in number theory
• GCD (a,b) of a and b is the largest integer that divides evenly into both a and b
• eg GCD(60,24) = 12
• define gcd(0, 0) = 0
• often want no common factors (except 1) define such numbers as relatively prime
• eg GCD(8,15) = 1
• hence 8 & 15 are relatively prime

Example GCD(1970,1066)

1970 = 1 x 1066 + 904 gcd(1066, 904)

1066 = 1 x 904 + 162 gcd(904, 162)

904 = 5 x 162 + 94 gcd(162, 94)

162 = 1 x 94 + 68 gcd(94, 68)

94 = 1 x 68 + 26 gcd(68, 26)

68 = 2 x 26 + 16 gcd(26, 16)

26 = 1 x 16 + 10 gcd(16, 10)

16 = 1 x 10 + 6 gcd(10, 6)

10 = 1 x 6 + 4 gcd(6, 4)

6 = 1 x 4 + 2 gcd(4, 2)

4 = 2 x 2 + 0 gcd(2, 0)

​

GCD(1160718174, 316258250)

Dividend Divisor Quotient Remainder

a = 1160718174 b = 316258250 q1 = 3 r1 = 211943424

b = 316258250 r1 = 211943424 q2 = 1 r2 = 104314826

r1 = 211943424 r2 = 104314826 q3 = 2 r3 = 3313772

r2 = 104314826 r3 = 3313772 q4 = 31 r4 = 1587894

r3 = 3313772 r4 = 1587894 q5 = 2 r5 = 137984

r4 = 1587894 r5 = 137984 q6 = 11 r6 = 70070

r5 = 137984 r6 = 70070 q7 = 1 r7 = 67914

r6 = 70070 r7 = 67914 q8 = 1 r8 = 2156

r7 = 67914 r8 = 2156 q9 = 31 r9 = 1078

r8 = 2156 r9 = 1078 q10 = 2 r10 = 0

Modular Arithmetic

• define modulo operator “a mod n” to be remainder when a is divided by n
• where integer n is called the modulus
• b is called a residue of a mod n
• since with integers can always write: a = qn + b
• usually chose smallest positive remainder as residue
• ie. 0 <= b <= n-1
• process is known as modulo reduction
• eg. -12 mod 7 = -5 mod 7 = 2 mod 7 = 9 mod 7
• a & b are congruent if: a mod n = b mod n
• when divided by n, a & b have same remainder
• eg. 100 mod 11 = 34 mod 11

so 100 is congruent to 34 mod 11

Modular Arithmetic Operations

• can perform arithmetic with residues
• uses a finite number of values, and loops back from either end

Z_n = {0, 1, . . . , (n – 1)}

• modular arithmetic is when do addition & multiplication and modulo reduce answer
• can do reduction at any point, ie
• a+b mod n = [a mod n + b mod n] mod n

​

Modular Arithmetic Operations

1. [(a mod n) + (b mod n)] mod n = (a + b) mod n
2. [(a mod n) – (b mod n)] mod n = (a – b) mod n
3. [(a mod n) x (b mod n)] mod n = (a x b) mod n

e.g.

[(11 mod 8) + (15 mod 8)] mod 8 = 10 mod 8 = 2 (11 + 15) mod 8 = 26 mod 8 = 2

[(11 mod 8) – (15 mod 8)] mod 8 = –4 mod 8 = 4 (11 – 15) mod 8 = –4 mod 8 = 4

[(11 mod 8) x (15 mod 8)] mod 8 = 21 mod 8 = 5 (11 x 15) mod 8 = 165 mod 8 = 5

​

Modulo 8 Addition Example

Modulo 8 Multiplication

Modular Arithmetic Properties

Euclidean Algorithm

• an efficient way to find the GCD(a,b)
• uses theorem that:
• GCD(a,b) = GCD(b, a mod b)
• Euclidean Algorithm to compute GCD(a,b) is:

Euclid(a,b)

if (b=0) then return a;

else return Euclid(b, a mod b);

Extended Euclidean Algorithm

• calculates not only GCD but x & y:

ax + by = d = gcd(a, b)

• useful for later crypto computations
• follow sequence of divisions for GCD but assume at each step i, can find x &y:

r = ax + by

• at end find GCD value and also x & y
• if GCD(a,b)=1 these values are inverses

​

Finding Inverses

EXTENDED EUCLID(m, b)

1. (A1, A2, A3)=(1, 0, m);

(B1, B2, B3)=(0, 1, b)

2. if B3 = 0

return A3 = gcd(m, b); no inverse

3. if B3 = 1

return B3 = gcd(m, b); B2 = b^–1 mod m

4. Q = A3 div B3

5. (T1, T2, T3)=(A1 – Q B1, A2 – Q B2, A3 – Q B3)

6. (A1, A2, A3)=(B1, B2, B3)

7. (B1, B2, B3)=(T1, T2, T3)

8. goto 2

​

Inverse of 550 in GF(1759)

355 is inverse of 550