1

Cryptography
Basic Definitions
Encryption & Decryption
Transmission Technique
Symmetric Cryptography
Asymmetric Cryptography
Types of Ciphers

2
 Cryptography is the study of transforming a secret message in such a
way that it can be understood only by an authorized recipient who has
been provided with a secret key for deciphering it.

Cryptography enables you to store sensitive information or transmit

it across insecure networks so that it cannot be read by anyone except
the intended recipient.

3
 Plaintext: Data that can be read and understood without any special
measures.
Encryption: The method of hiding plaintext in such a way as to hide its
substance is called encryption.
Cipher text: Encrypting plaintext results in unreadable data called
cipher text. i.e transformed message.
Decryption: The process of returning cipher text to its original plaintext
is called decryption.
Key: some secret piece of information that customizes how the cipher
text is produced.

4
 Cryptanalysis: The art of breaking ciphers, i.e. retrieving the
plaintext without knowing the proper key.
Cryptanalysts: Experts of cryptanalysis.
Cryptology: The branch of mathematics that studies the
mathematical foundations of cryptographic methods.
Cipher: The Encrypted message is called cipher.

5
6
 For “secret writing”
To establish a shared secret when other people (eavesdroppers)
are listening.

TYPES
1. Symmetric key cryptography
2. Asymmetric key cryptography

7
8
 bla-bla

ciphertext
msg
decoder (ciphertext in
encoder - plaintext out)
(plaintext in - bla-bla
cmb-cmb
ciphertext out)

eavesdropper
(should understand
nothing about the msg)
9
 Cryptology
Cryptography Cryptanalysis

Symmetric key Asymmetric key

cryptography cryptography
(Public key cryptography)

Classical Modern
cryptography cryptography

Transposition Substitution Stream Block

cipher cipher cipher cipher

10
 In classical cryptography, a transposition cipher changes
one character from the plaintext to another i.e. the order of
the characters is changed.

11
 Substitution cipher is a method of encryption by which units of
plaintext are substituted with cipher text according to a regular
system or A system of enciphering that uses the method of
substitution is called substitution cipher.

12
 A Stream Cipher is a symmetric or secret-key encryption algorithm
that encrypts a single bit at a time. With a Stream Cipher, the same
plaintext bit or byte will encrypt to a different bit or byte every time it is
encrypted.
In stream cipher we use different keys for enciphering successive
letters.
e.g. Binary of plain text: 010111101 (hypothetical)
Key: 100101011 Perform XOR
Cipher text: 110010110
To decrypt make the XOR operation of the cipher text with the key.

13
 Block cipher technique involves encryption of one block of text at a
time .Decryption also takes one block of encrypted text at a time.
Length of the block is usually 64 or 128 bits.
e.g. :
Plain text: four and five
Four and five
Key Key Key
Cipher text: wvfa ast wvfa

14
 Public key cryptography is an asymmetric scheme that uses a
Pair of keys for encryption: a Public key, which encrypts data,
and a corresponding Private key (secret key) for decryption.

15
Cryptanalysis refers to the study of ciphers, cipher text, or
cryptosystems (that is, to secret code systems) with a view to
finding weaknesses in them that will license recovery of the plain
text from the cipher text, without necessarily knowing the key or
the algorithm. This is known as breaking the cipher, cipher text, or
cryptosystem.
Unlike cryptography which is a clearly defined science,
Cryptanalysis is as much an art as it is a science.

16
Known - plain text analysis

Chosen – plain text analysis (Differential cryptanalysis)

Cipher text - only analysis

Man – in – the - middle attack

17
 It is a side channel attack which exploits sounds emitted by computers or
machines.
Modern acoustic cryptanalysis mostly focuses on sounds emitted by
computer keyboards and internal computer components
Historically it has also been applied to impact printers and
electromechanical cipher machines.

18
 It is a side channel attack which exploits sounds emitted by computers or
machines.
Modern acoustic cryptanalysis mostly focuses on sounds emitted by
computer keyboards and internal computer components
Historically it has also been applied to impact printers and
electromechanical cipher machines.

19
 Use rubber keyboard or virtual keyboards to prevent keystroke
sounds.
Use acoustic printers.
Use Acoustic case for CPU.

20
 Cryptography, being an art of encrypting and decrypting confidential
information and private messages, should be implemented in the network
security to prevent any leakage and threat.
It can be done by using any of these techniques discussed above for
fortifying the personal data transmission as well as for secure transaction.
Acoustic cryptanalysis, being an art of decrypting or leaking
confidential information from the sound generated from the CPU,
Keyboard, printers, etc may be used in both constructive as well as
destructive ways.
21
 Books

Understanding Cryptography by Cristopher Paar

Introduction to Modern Cryptography by J. Katz and Y. Lindell
Introduction to Cryptography by Johannes Buchmann

22
 Presented By : Shibani Sarangi
IT Branch, Regd no. 1001289324

Guided By : Prof. X
1
If we shift each letter forwarded by k places around
the circle, the resulting permutation of the alphabet
is called cyclic shift of length k. Enciphering done by
using cyclic shift is called shift cipher or Caesar
cipher. The actual cipher used by Caesar was a cyclic
shift with k=3. In this case the letter A shifts to D and
B shifts to E and so on. For example,
ABCDEFGHIJKLMNOPQRSTUVWXYZ
DEFGHIJKLMNOPQRSTUVWXYZABC
2
For example if k=3 we get key of shift cipher
ABCDEFGHIJKLMNOPQRSTUVWXYZ
DEFGHIJKLMNOPQRSTUVWXYZABC
Plain Text : ATTACK IS IMMINENT
Using above key we get cipher text is
Cipher Text: DWWDFNLVLPPLQHQW
Using above decipher the following
Cipher Text: SURFHHGWRURPH
Plain Text: PROCEED TO ROME
3
The Vigenère cipher is a method of encrypting
alphabetic text by using a series of linked
Caesar ciphers based on the letters of a keyword.
It is periodic substitution cipher composed of shift
cipher. In this cipher we use key as a key word for
example key word : PARIS
ABCDEFGHIJKLMNOPQRSTUVWXYZ
PQRSTUVWXYZABCDEFGHIJKLMNO
ABCDEFGHIJKLMNOPQRSTUVWXYZ
RSTUVWXYZABCDEFGHIJKLMNOPQ
I JKLMNOPQRSTUVWXYZABCDEFGH
STUVWXYZABCDEFGHIJKLMNOPQR 4
Example: Using the Vigenere cipher with the key word
PARIS
(a) Encipher the plain text: SEND MORE MONEY
(b) Decipher the cipher text: XADKCBPCMLTLPJJDKV
Solution: Here key word is PARIS so k=5 we make block
of 5 words and apply the keyword PARIS.
(a) Plain Text : SENDM OREMO NEY
Cipher Text: HEELE DRVUG CEP
so HEELEDRVUGCEP is required cipher text
(b) Cipher Text : XADKC BPCML TLPJJ DKV

Plain Text: IAMCO MPLET ELYBR OKE

By inserting blank spaces at appropriate places we get

5
the message I AM COMPLETELY BROKE
➢ ℤ𝑛 is ring
➢ ℤ𝑛 is an integral domain if and only if n is prime.
➢ A finite integral domain is field .
➢ For example: ℤ4 , ℤ6 , ℤ8 are not integral domain
hence not fields.
➢ 𝑈(ℤ𝑛 )= 𝑎 ∈ ℤ𝑛 ∶ gcd 𝑎, 𝑛 = 1
➢ U(ℤ26 )={1,3,5,7,9,11,15,17,19,21,23,25}
Euler’s phi-function
∅ 𝑛 = 𝑎 ∈ ℤ+ ; 𝑎 < 𝑛, ∶ 𝑛, 𝑎 = 1
Example: ∅(26)=12= 𝑈(ℤ26 )
∅(p)=p-1 if and only if p is prime integer.
➢ If R is ring then U(R) is multiplicative abelian
group.
6
Example: Obtain the multiplicative group U(ℤ12 ) and find the
product of every two elements in it.
Solution: U(ℤ12 ) ={ 1, 5, 7, 11}
𝟓𝟐 = 𝟏, 𝟕𝟐 = 𝟏, 𝟏𝟏𝟐 = 𝟏
5.7=11, 5.11=7, 7.11=5
• U(ℤ12 ) is an example of Klien’s four group.
• Finding Inverses in U(ℤ𝑛 )
𝑎 ∈ 𝑈(ℤ𝑛 ), find 𝑎−1 ???
Since gcd(a,n)=1 there exist s,t∈ ℤ such that sa+tn=1
𝑎−1 =s(mod n)
Example: Find the inverse of a=21 in U(ℤ100 ).
By division Algorithm
100=4(21)+16 ,
21=1(16)+5 ,
16=3(5)+1
Now we start from last equation and move upward
1=16-3(5), 16-3(21-1(16))=4(16)-3(21)=4(100-4(21))-3(21)
=4(100)-19(21)=4(100)+(-19)(21)
𝑎−1 =(-19)(mod 100) 21−1 =81 7
Ex 1: Show that U(ℤ8 ) is Klein’s four group;
Ex2: Find the inverse of 11 in U(ℤ81 ) .

An enciphering that makes use of the algebraic operations in

ℤn is called a modular enciphering.

Affine Cipher is the simplest example of modular enciphering.

Let a, b∈ ℤ𝑛 and (a,n)=1 this implies that a is invertible.

Define 𝜎: ℤ𝑛 → ℤ𝑛 by
𝜎(x)=(ax+b)mod n and this mapping is bijective.
• 𝜎 is called an Affine cipher
• If a=1 then 𝜎 is known as Shift Cipher.
Now define 𝜎 −1 : ℤ𝑛 → ℤ𝑛 by
𝜎 −1 (y)= 𝑎−1 (y-b)= 𝑎−1 𝑦 − 𝑎−1 b for all y∈ ℤ𝑛 .
8
Let Ω = {A, 𝐵, 𝐶, 𝐷, … , 𝑍}, Ω =26=n So we can take the mapping
𝜌: Ω → ℤ26 as
A→1
B→2
C→3
.
.
.
Z →26
Example: Use the mapping 𝜌 and the affine cipher
𝜎(x)=(7x+4)mod 26
(a) To encipher ALGEBRA (b) To decipher AMEQMNZW

9
SOLUTION:
(a) Since (7,26)=1
Plain Text : A L G E B R A
x : 1 12 7 5 2 18 1
7x+4 : 11 88 53 39 18 130 11
(7x+4 )mod 26 : 11 10 1 13 18 0 11
Cipher Text : K J A M R Z K

(b) To decipher we use inverse mapping of 7x+4=y

x=7−1 (y-4)
By Euclidian Algorithm we get 7−1 =15
d(y)=15y-60 mod 26=15y+18
Cipher Text : A M E Q M N Z W
y : 1 13 5 17 13 14 0 23
15y+18 : 33 213 93 273 213 228 18 363
15y+18mod26: 7 5 15 13 5 20 18 25
Plain Text : G E O M E T R Y
10
Use a Vigenere Cipher or Shift cipher with the Key word ATHENS to
a) Encipher SOCRATES b) decipher PEHXB
By applying the mapping 𝜎(x)=(x+k)mod 26
Solution: a) Since key word is ATHENS so we use value of k corresponding to each letter.
A→ 0, T → 19, H → 7, E → 4 , N → 13, S → 18
K takes these values in cyclic repetition.
Plain Text : S O C R A T E S
x : 19 15 3 18 1 20 5 19
K : 0 19 7 4 13 18 0 19
x+k mod26 : 19 8 10 22 14 12 5 12
Cipher Text: S H J V N L E L

b) To decipher we use inverse mapping x=(y-k) mod 26

Cipher Text : P E H X B
y : 16 5 8 24 2
K : 0 19 7 4 13
(Y-k) mod 26 : 16 12 1 20 15
Plain Text : P L A T O
11
If p is prime then ℤ𝑝 is field
Every non zero element in ℤ𝑝 is invertible.
Let n=29
▪ Ω ={A, B, C, D, …., Z, comma , . , blank space}
▪ Then the mapping 𝝆: Ω → ℤ29 is given as
A →1
B →2
C →3
D →4
.
.
.
Z →26
Comma → 27
Point(.) →28
Blank space → 0
EXERCISE
Use the mapping 𝝆: Ω → ℤ29 and affine cipher
𝜎(x)=(4x+10)mod 29
a) To Encipher: WAR AND PEACE
b) To Decipher: CL#.CLW. 12
Affine Cipher 𝜎(x)=ax+b contains two parameters a and b where
a and b are elements of integer residue ring ℤ𝑛 and gcd(a,n)=1

Question 1 : How many a’s and b’s are possible??

Answer : For total number of a’s answer is ∅(𝑛) which is Euler
phi-function and for b’s it will be the elements in ℤ𝑛 .
Question 2: How many possible keys (a,b) used in affine cipher??
Answer: There are( 𝑛 ∅(𝑛) ) total number of keys are used in
affine cipher over ℤ𝑛 .

Example: For n=26

The total number of keys = 26 ×12= 312
If n=p then
The total number of keys =p(p-1)
➢ Number of Keys is not large enough to make it a secure cipher . The
Code can be broken easily by an exhaustive key search.

13
Choose a, b , 𝑥0 be any elements of ℤ𝑛 with gcd(a,n)=1
Let 𝑥𝑖 ∈ ℤ𝑛 represent ith letter in the plain text message.
We Encipher 𝑥𝑖 by using the affine mapping
𝜎𝑖 : ℤ𝑛 → ℤ𝑛 given by
𝜎𝑖 (x)=ax +b𝑥𝑖−1 , i=1,2,3,….
𝜎𝑖 (𝑥𝑖 )=a 𝑥𝑖 +b𝑥𝑖−1 i=1,2,3,…..
This type of stream cipher is known as Text-induced .

Example : Use the Text-induced stream affine cipher

𝜎𝑖 (x)=(5x +9𝑥𝑖−1 ) mod 26 , i=1,2,3,…
With 𝑥0 =1 to
a) Encipher HAPINESS
b) Decipher ZLQRCP

14
Example : Use the Text-induced stream affine cipher
𝜎𝑖 (x)=(5x +9𝑥𝑖−1 ) mod 26 , i=1,2,3,… With 𝑥0 =1 to Encipher HAPINESS Decipher ZLQRCP

SOLUTION: a)
Plain Text : H A P P I N E S S
𝑖 : 1 2 3 4 5 6 7 8 9
𝑥𝑖 : 8 1 16 16 9 14 5 19 19
(5 𝑥𝑖 +9 𝑥𝑖−1 )mod26: 23 25 11 16 7 21 21 10 6
Cipher Text : W Y K P G U U J F

b) Let 𝑦𝑖 represents the ith letter in cipher text

𝑦𝑖 =(5 𝑥𝑖 +9 𝑥𝑖−1 ) mod 26
𝑥𝑖 =5−1 ( 𝑦𝑖 - 9𝑥𝑖−1 ) mod 26 = (21 𝑦𝑖 +19 𝑥𝑖−1 ) mod 26
Cipher Text: Z L Q R C P
𝑖 : 1 2 3 4 5 6
𝑥𝑖= 5 𝑦𝑖 +19 𝑥𝑖−1 mod26: 19 15 18 18 15 23
Plain text : S O R R O W
15
In this Cipher we extend the bijective mapping ρ: Ω → ℤ𝑛 where Ω = n
ρ ∶ Ω𝑟 → (ℤ𝑛 )𝑟
ρ(a1, a2, a3, …., ar)=(ρ(a1), ρ(a2), ρ(a3), ….., ρ(ar))
However a natural bijection is
𝜏: (ℤ𝑛 )𝑟 → ℤ𝑛𝑟 defined as
𝜏(𝑥1 , 𝑥2 , 𝑥3 , ….., 𝑥𝑟 )= 𝑥1 𝑛𝑟−1 + 𝑥2 𝑛𝑟−1 +….. 𝑥𝑟

𝜏 𝜊 ρ: Ω𝑟 → ℤ𝑛𝑟 is a bijection mapping.

𝜎 ∶ ℤ𝑛𝑟 → ℤ𝑛𝑟 be an affine mapping defined by

𝜎(x)=(ax+b)mod 𝑛𝑟 where a,b are elements of ℤ𝑛𝑟
and gcd(a,n)=1

16
Ω𝑟 → (ℤ𝑛 )𝑟 → ℤ𝑛𝑟 → ℤ𝑛𝑟 → (ℤ𝑛 )𝑟 → Ω𝑟

If the mapping for Affine cipher is 𝜎 ∶ ℤ𝑛𝑟 → ℤ𝑛𝑟 then the total
number of keys for this cipher is 𝑛𝑟 𝜙(𝑛𝑟 ).

If n=26 and r=2 then the possible total number of keys are
262 ϕ(262 )
= 262 ϕ(132 , 22 )
=676(156× 2)
=210910
So There are 210910 possible keys for affine cipher for r=2 and
n=26.
17
Example: Use the blocks of two letters and the affine
cipher 𝜎(𝑥) = (35𝑥 + 120)mod676
a) Encipher HELLO b) Decipher IUOZDG
Solution: a) We break the message into blocks of two
letters and adding an extra letter Z at the end to
complete block.
Plain Text : HE LL OZ
𝑥1 , 𝑥2 : 8,5 12,12 15,0
𝑥 = 26𝑥1 + 𝑥2 : 213 324 130
𝑦 = (35𝑥 + 120)mod676: 139 644 614
𝑦1 , 𝑦2 : 5,9 24,20 23,16
Cipher Text: EI XT WP
Hence we get cipher text is EIXTWP Corresponding
to HELLO
18
b) If 𝑦 = 35𝑥 + 120 𝑚𝑜𝑑676
𝑡ℎ𝑒𝑛 𝑥 = 35−1 𝑦 − 120 𝑚𝑜𝑑676
This implies that 𝑦 = 367𝑦 + 576 𝑚𝑜𝑑676
Cipher Text: IU OZ DG
𝒚𝟏 , 𝒚𝟐 : 9,21 15,0 4,7
y=26𝒚𝟏 +𝒚𝟐 : 255 390 111
x= 𝟑𝟔𝟕𝒚 + 𝟓𝟕𝟔 𝒎𝒐𝒅𝟔𝟕𝟔 197 394 77
𝒙𝟏 , 𝒙𝟐 : 7,15 15,4 2,25

Plain Text : GO OD BY
Hence we get plain text is GOODBY corresponding to
Cipher text IUOZDG
19
 Presented By : Shibani Sarangi
IT Branch, Regd no. 1001289324

Guided By : Prof. X
1
Choose a, b , 𝑥0 be any elements of ℤ𝑛 with gcd(a,n)=1
Let 𝑥𝑖 ∈ ℤ𝑛 represent ith letter in the plain text message.
We Encipher 𝑥𝑖 by using the affine mapping
𝜎𝑖 : ℤ𝑛 → ℤ𝑛 given by
𝜎𝑖 (x)=ax +b𝑥𝑖−1 , i=1,2,3,….
𝜎𝑖 (𝑥𝑖 )=a 𝑥𝑖 +b𝑥𝑖−1 i=1,2,3,…..
This type of stream cipher is known as Text-induced .

Example : Use the Text-induced stream affine cipher

𝜎𝑖 (x)=(5x +9𝑥𝑖−1 ) mod 26 , i=1,2,3,…
With 𝑥0 =1 to
a) Encipher HAPINESS
b) Decipher ZLQRCP

2
Example : Use the Text-induced stream affine cipher
𝜎𝑖 (x)=(5x +9𝑥𝑖−1 ) mod 26 , i=1,2,3,… With 𝑥0 =1 to Encipher HAPINESS Decipher ZLQRCP

SOLUTION: a)
Plain Text : H A P P I N E S S
𝑖 : 1 2 3 4 5 6 7 8 9
𝑥𝑖 : 8 1 16 16 9 14 5 19 19
(5 𝑥𝑖 +9 𝑥𝑖−1 )mod26: 23 25 11 16 7 21 21 10 6
Cipher Text : W Y K P G U U J F

b) Let 𝑦𝑖 represents the ith letter in cipher text

𝑦𝑖 =(5 𝑥𝑖 +9 𝑥𝑖−1 ) mod 26
𝑥𝑖 =5−1 ( 𝑦𝑖 - 9𝑥𝑖−1 ) mod 26 = (21 𝑦𝑖 +19 𝑥𝑖−1 ) mod 26
Cipher Text: Z L Q R C P
𝑖 : 1 2 3 4 5 6
𝑥𝑖= 5 𝑦𝑖 +19 𝑥𝑖−1 mod26: 19 15 18 18 15 23
Plain text : S O R R O W
3
In this Cipher we extend the bijective mapping ρ: Ω → ℤ𝑛 where Ω = n
ρ ∶ Ω𝑟 → (ℤ𝑛 )𝑟
ρ(a1, a2, a3, …., ar)=(ρ(a1), ρ(a2), ρ(a3), ….., ρ(ar))
However a natural bijection is
𝜏: (ℤ𝑛 )𝑟 → ℤ𝑛𝑟 defined as
𝜏(𝑥1 , 𝑥2 , 𝑥3 , ….., 𝑥𝑟 )= 𝑥1 𝑛𝑟−1 + 𝑥2 𝑛𝑟−1 +….. 𝑥𝑟

𝜏 𝜊 ρ: Ω𝑟 → ℤ𝑛𝑟 is a bijection mapping.

𝜎 ∶ ℤ𝑛𝑟 → ℤ𝑛𝑟 be an affine mapping defined by

𝜎(x)=(ax+b)mod 𝑛𝑟 where a,b are elements of ℤ𝑛𝑟
and gcd(a,n)=1

4
Ω𝑟 → (ℤ𝑛 )𝑟 → ℤ𝑛𝑟 → ℤ𝑛𝑟 → (ℤ𝑛 )𝑟 → Ω𝑟

If the mapping for Affine cipher is 𝜎 ∶ ℤ𝑛𝑟 → ℤ𝑛𝑟 then the total
number of keys for this cipher is 𝑛𝑟 𝜙(𝑛𝑟 ).

If n=26 and r=2 then the possible total number of keys are
262 ϕ(262 )
= 262 ϕ(132 , 22 )
=676(156× 2)
=210910
So There are 210910 possible keys for affine cipher for r=2 and
n=26.
5
Example: Use the blocks of two letters and the affine
cipher 𝜎(𝑥) = (35𝑥 + 120)mod676
a) Encipher HELLO b) Decipher IUOZDG
Solution: a) We break the message into blocks of two
letters and adding an extra letter Z at the end to
complete block.
Plain Text : HE LL OZ
𝑥1 , 𝑥2 : 8,5 12,12 15,0
𝑥 = 26𝑥1 + 𝑥2 : 213 324 130
𝑦 = (35𝑥 + 120)mod676: 139 644 614
𝑦1 , 𝑦2 : 5,9 24,20 23,16
Cipher Text: EI XT WP
Hence we get cipher text is EIXTWP Corresponding
to HELLO
6
b) If 𝑦 = 35𝑥 + 120 𝑚𝑜𝑑676
𝑡ℎ𝑒𝑛 𝑥 = 35−1 𝑦 − 120 𝑚𝑜𝑑676
This implies that 𝑦 = 367𝑦 + 576 𝑚𝑜𝑑676
Cipher Text: IU OZ DG
𝒚𝟏 , 𝒚𝟐 : 9,21 15,0 4,7
y=26𝒚𝟏 +𝒚𝟐 : 255 390 111
x= 𝟑𝟔𝟕𝒚 + 𝟓𝟕𝟔 𝒎𝒐𝒅𝟔𝟕𝟔 197 394 77
𝒙𝟏 , 𝒙𝟐 : 7,15 15,4 2,25

Plain Text : GO OD BY
Hence we get plain text is GOODBY corresponding to
Cipher text IUOZDG
7
ℤ𝑝 [𝑥]
≈ 𝐺𝐹 𝑝, 𝑟 = 𝐺𝐹(𝑝𝑟 )=ℱ𝑝𝑟
<𝑓 𝑥 >
Where f(x) is monic irreducible polynomial of degree r
over ℤ𝑝
ℱ𝑝𝑟 =൛𝑎1 𝑡 𝑟−1 + 𝑎2 𝑡 𝑟−2 + 𝑎3 𝑡 𝑟−3 + ⋯ + 𝑎𝑟−1 𝑡 + 𝑎𝑟 ∶
𝑎1 , 𝑎2 , 𝑎3 , … 𝑎𝑟 ∈ ℤ𝑝 ൟ
Where f(t)= 𝑡 𝑟 + 𝑐1 𝑡 𝑟−1 + 𝑐2 𝑡 𝑟−2 + ⋯ + 𝑐𝑟 =0
t is known as primitive element and ℱ𝑝𝑟 is Galois field
extension of the prime field ℤ𝑝 . Moreover ℱ𝑝𝑟 is vector
space over ℤ𝑝 with dimension r. However
(ℱ𝑝𝑟 )∗ = ℱ𝑝𝑟 − 0 Is multiplicative cyclic group of
order 𝑝𝑟 − 1 and t is its generator with order 𝑝𝑟 − 1 .
8
9
 Galois Field
power form n-tuple form polynomial form
0 0000 0
 0100 
2 0010 2
3 0001 3
Table of Galois Field which is 4 1100 1
generated by primitive 5 0110   2
element ξ . 6 0011 2  3

ℤ𝑝 [𝑥] 7 1101 1    3
≈ 𝐺𝐹 𝑝, 𝑟 = 𝐺𝐹(𝑝𝑟 )=ℱ𝑝𝑟 8 1010 1  2
<𝑓 𝑥 >
Where f(x) is monic irreducible 9 0101   3
polynomial of degree r over ℤ𝑝  10 1110 1    2
 11 0111   2  3
 12 1111 1    2  3
 13 1011 1  2  3
 14 1001 10 1  3
 15 1 1

Department of Mathematics
Ω → ℤ𝑝𝑟 → ℱ𝑝𝑟 → ℱ𝑝𝑟 → ℤ𝑝𝑟 → Ω
Here Ω is set of Alphabet of n order.

If we take n=27
𝑓 𝑥 = 𝑥 3 +2x+1 is monic irreducible over ℤ3
ℱ33 = ℱ27 ={𝑎𝑡 2 +bt+c : a, b, c∈ ℤ3 }
Where t satisfies the relation 𝑡 3 + 2𝑡 + 1 = 0,
𝑡 3 = −2𝑡 − 1
𝑡3 = 𝑡 + 2
By taking successive powers of t we can find the order of t is 26.
Thus t is primitive element and therefore every non zero element
in Field ℱ27 Is the power of t.
Now we make the table which shows that for each character in Ω
its numerical value in ℤ27 , the corresponding element in ℱ27 and
its expression as a power of t
11
Ω ℤ𝑝𝑟 ℱ𝑝 𝑟 ℱ𝑝 𝑟 Ω ℤ𝑝𝑟 ℱ𝑝𝑟 ℱ𝑝 𝑟
A 1 1 t0 N 14 t 2 +t+2 t11
B 2 2 t13 O 15 t 2 +2t t4
C 3 t t1 P 16 t 2 +2t+1 t18
D 4 t+1 t9 Q 17 t 2 +2t+2 t7
E 5 t+2 t3 R 18 2t 2 t15
F 6 2t t14 S 19 2t 2 +1 t 25
G 7 2t+1 t16 T 20 2t 2 +2 t8
H 8 2t+2 t 22 U 21 2t 2 +t t17
I 9 t2 t2 V 22 2t 2 +t+1 t 20
J 10 t 2 +1 t 21 W 23 2t 2 +𝑡 + 2 t5
K 11 t 2 +2 t12 X 24 2t 2 +2t t 23
L 12 t 2 +t t10 Y 25 2t 2 +2t+1 t 24
M 13 t 2 +t+1 t6 Z 26 2t 2 +2𝑡 + 2 t19
SPACE 0 0 0

12
Use the representation table of the alphabet by ℱ27 describe in
previous slide and the affine cipher 𝜎: ℱ27 → ℱ27 given by
𝜎 𝑢 = 𝑡 + 1 𝑢 + 𝑡2 + 2
(a) Encipher FIELD (b) Decipher FVC A

SOLUTION: (a)
We write for each letter in the plain text its representation 𝑢 ∈ ℱ27
and find
𝜎 𝑢 = 𝑡 + 1 𝑢 + 𝑡 2 + 2. The table shows the work
Plain Text: F I E L D
𝑢 ∈ ℱ27 : 2t 𝑡2 t+2 𝑡 2 +t t+1
𝜎 𝑢 : 2t+2 2𝑡 2 +t+1 2𝑡 2 +1 2t+1 2𝑡 2 +2t
Cipher text: H V S G X

13
(b) Decipher FVC A
SOLUTION: (b)
From the table we find that 𝑡 + 1 = 𝑡 9 , Hence the inverse of
𝑡 + 1 is 2𝑡 2 +t . Because (𝑡 + 1)−1 = (𝑡 9 )−1 = 𝑡 17 = 2𝑡 2 +t
Thus the inverse mapping 𝜎 −1 is given by
𝜎 −1 𝑣 = 2𝑡 2 + t v − 𝑡 2 + 2 = 2𝑡 2 + t v + 2t + 1
The table shows the work
Cipher Text: F V C SPACE D
V∈ ℱ27 : 2t 2𝑡 2 +𝑡 + 1 t 0 1
𝜎 −1 𝑣 : 2𝑡 2 𝑡2 𝑡 2 + 𝑡 + 2 2t+1 2𝑡 2 +1
Plain Text: R I N G S

14
Q1: Use the Text induced stream affine cipher with 𝑥0 =5
and 𝜎𝑖 (x)=(7𝑥 + 4𝑥𝑖−1 )mod26
(a)Encipher ABSTRACT (b) Decipher AJSKHDA

Q2: Use blocks of two letters and the affine cipher

(23x+314)mod262
(a)Encipher HEAVEN (b) Decipher RMLR

Q3: Use the representation of the alphabetic by the

field ℱ27 and the affine cipher
𝜎 𝑢 = 𝑡2 + 1 u + t + 1
(a) Encipher NEW (b) Decipher ITJ
15
 Presented By : Shibani Sarangi
IT Branch, Regd no. 1001289324

Guided By : Prof. X
1
•Invented by Lester. S. Hill in 1929.
•Inputs : String of English letters, A,B,…,Z.
An rr matrix B, with entries drawn from
0,1,…,25.
(The matrix B serves as the secret key. )
•Divide the input string into blocks of size r.
•Identify A=0, B=1, C=2, …, Z=25.
•Encryption: Multiply each block by B and then
reduce mod 26.
•Decryption: multiply each block by the inverse of
B, and reduce mod 26.
2
Let n be the number of characters in plain text alphabet
Ω, and let 𝑟 ∈ ℤ+ and 𝑟 > 1
𝜌: Ω𝑟 → (ℤ𝑛 )𝑟 is defined by
𝜌(𝒂𝟏 , 𝒂𝟐 , 𝒂𝟑 , … , 𝒂𝒓 ) = (𝜌 𝒂𝟏 , 𝜌 𝒂𝟐 , 𝜌 𝒂𝟑 , … , 𝜌 𝒂𝒓 )
is the extension of 𝜌: Ω → ℤ𝑛 .

𝑥1
𝑥2
(ℤ𝑛 )𝑟 = , 𝑥1 , 𝑥2 , … , 𝑥𝑟 ∈ ℤ𝑛
⋮
𝑥𝑟

𝒙𝟏𝟏 … 𝒙𝟏𝒓
⋮ ⋱ ⋮
(ℤ𝑛 )𝑟∗𝑟 = { 𝒙𝒓𝟏 ⋯ 𝒙𝒓𝒓 : 𝑥ij ∈ ℤ𝑛 1 ≤ 𝑖, 𝑗 ≤ 𝑟}

3
➢ An square matrix B over ℤ𝑛 is invertible if and only if det 𝐵 is
relatively prime to n.

Let B be an invertible 𝑟 × 𝑟 matrix over ℤ𝑛 and D ∈ (ℤ𝑛 )𝑟 . Then

the mapping 𝜎: (ℤ𝑛 )𝑟 → (ℤ𝑛 )𝑟 given by
𝜎 X = BX + D ∀ 𝑋 ∈ (ℤ𝑛 )𝑟
Is called a Hill Cipher.

In this cipher we use scheme of enciphering and deciphering as

follows;
Ω𝑟 → (ℤ𝑛 )𝑟 → (ℤ𝑛 )𝑟 → Ω𝑟
To decipher the Cipher text , we use the inverse mapping

𝝈−𝟏 𝒀 = 𝑩−𝟏 (𝒀 − 𝑫)
4
Use the Hill Cipher with n=26, r=2 given by
𝑥1 8 5 𝑥1 7
𝜎 𝑥 = + (mod 26)
2 5 6 𝑥2 9
a) Encipher MOUNTAIN
b) Decipher AJGLLRKE
SOLUTION:
8 5
a) First we Calculate the det B =det =23 and gcd(23,26)=1
5 6
This implies that B is invertible.
For Encipher , we divide the plain text message into blocks of two letters ,
represent each block by column of numbers given by the mapping and
apply the mapping 𝝈.

Plain Text : MO UN TA IN
𝑥1 13 21 20 9
𝑥2 :
15 14 01 14
𝑥1 4 11 16 19
𝜎 𝑥 :
2 8 16 11 8
Cipher Text: DH KP PK SH
5
Decipher AJGLLRKE
SOLUTION:
8 5
First we Calculate the det B =det =23 and gcd(23,26)=1
5 6
This implies that B is invertible.
For Decipher , we calculate inverse of B for this first calculate the (det
24 19
B)−1 =23−1 = 17 𝑜𝑣𝑒𝑟 𝑚𝑜𝑑 26 . Hence 𝐵−1 = 17 6 −5 𝑚𝑜𝑑26 = .
−5 8 19 6
𝑦1 24 19 𝑦1 7
To Decipher we use the mapping 𝝈−𝟏 𝑦 = 𝑦2 − mod 26 =
2 19 6 9
−𝟏
𝑦1 24 19 𝑦1 25
𝝈 𝑦2 = +
19 6 𝑦2 21

Cipher Text : AJ GL LR KE
𝑦1 1 7 12 11
𝑦2 :
10 12 18 5
−𝟏
𝑦1 5 5 5 20
𝝈 𝑦2 : 22 18 19 0
Plain Text: EV ER ES TZ
6
Select 𝑟 × 𝑟 matrices B, C over ℤ𝑛 when B is invertible
and fix 𝑋0 ∈ (ℤ𝑛 )𝑟 .
Let 𝑋𝑖 ∈ (ℤ𝑛 )𝑟 represent the ith block of r letters in the
plain text . We define the mapping 𝝈𝑖 : (ℤ𝑛 )𝑟 → (ℤ𝑛 )𝑟
by
𝝈𝑖 𝑋 = 𝐵𝑋 + 𝐶𝑿𝑖−1 ∀ 𝑋 ∈ (ℤ𝑛 )𝑟
The ith block 𝑋𝑖 is enciphered by using the Hill Cipher
𝝈𝑖 .

7
An Other Example
Message to encrypt
HELLOWORLD
HELLO WORLD has been encrypted to
SLHZY ATGZT
 Change message into 2 x 1 letter vectors
 Change each vector into 2 x 1 numeric
vectors
 Multiply each numeric vector by decryption
matrix
 Convert new vectors to letters
Message to Decrypt
SLHZYATGZT
SLHZYATGZT has been decrypted to
HELLO WORLD
 Creating valid encryption/decryption
matrices is the most difficult part of Hill
Ciphers.
 Otherwise, Hill Ciphers use simple linear
algebra and modular arithmetic
 7 3
Q1: Use the Hill Cipher 𝜎 X = BX + D with B=
8 7
4
D= , Over ℤ26 .
5
a) Encipher HAPPY
b) Decipher JHFK
Q2: Use the Hill Cipher 𝜎 X = BX + D with
17 23 4 4
B= 17 12 7 , D= 5 Over ℤ26 . TO
11 15 25 9
a) Encipher LINEAR
b) Decipher RYLWMYGOA
18
Q3:
𝑎 𝑏
a) Show that a square matrix B= over Over ℤ𝑛 ,
𝑐 𝑑
with det B=-1, is involutory if and only a+d=0.

b) Show that If a square matrix B Over ℤ𝑝 is involutory,

then det B= ±1

An 𝑛 × 𝑛 𝑚𝑎𝑡𝑟𝑖𝑥 𝐵 𝑖𝑠 𝑐𝑎𝑙𝑙𝑒𝑑 𝑖𝑛𝑣𝑜𝑙𝑢𝑡𝑜𝑟𝑦 𝑖𝑓 𝐵−1 = 𝐵

19
DATA ENCRYPTION STANDARD
(DES)

[Link] Asif
Department of Mathematics
University of Management and Technology Sialkot
History

In 1971, IBM developed an algorithm,

named LUCIFER which operates on a
block of 64 bits, using a 128-bit key

Walter Tuchman, an IBM researcher,

refined LUCIFER and reduced the key
size to 56-bit, to fit on a chip.
History

In 1977, the results of Tuchman’s

project of IBM was adopted as the Data
Encryption Standard by NSA (NIST).
DES Algorithm
Initial Permutation
IP Table
58 50 42 34 26 18 10 2
60 52 44 36 28 20 12 4
62 54 46 38 30 22 14 6
64 56 48 40 32 24 16 8
57 49 41 33 25 17 9 1
59 51 43 35 27 19 11 3
61 53 45 37 29 21 13 5
63 55 47 39 31 23 15 7
Round wise Encryption
𝐻𝑜𝑤 𝑡𝑜 𝐶𝑎𝑙𝑐𝑢𝑙𝑎𝑡𝑒 𝐶𝑖𝑝ℎ𝑒𝑟 𝐹𝑢𝑛𝑐𝑡𝑖𝑜𝑛 𝐹(𝑥, 𝑘)
 Expansion Table (E Table)
◼ E
32 1 2 3 4 5
4 5 6 7 8 9
8 9 10 11 12 13
12 13 14 45 16 17
16 17 18 19 20 21
20 21 22 23 24 25
24 25 26 27 28 29
28 29 30 31 32 1
How do S-boxes Work?

Bit 0 Bit 1 Bit 2 Bit 3 Bit 4 Bit 5

Row Column

Use the Row and Column number to find the corresponding output
number from the S-box.
Besides, the n-th block must use the n-th S-box.
S-Box 1: Substitution Box 1

Row / Column 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
0 14 4 13 1 2 15 11 8 3 10 6 12 5 9 0 7
1 0 15 7 4 14 2 13 1 10 6 12 11 9 5 3 8
2 4 1 14 8 13 6 2 11 15 12 9 7 3 10 5 0
3 15 12 8 2 4 9 1 7 5 11 3 14 10 0 6 13

S-Box 2: Substitution Box 2

Row / Column 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
0 15 1 8 14 6 11 3 4 9 7 2 13 12 0 5 10
1 3 13 4 7 15 2 8 14 12 0 1 10 6 9 11 5
2 0 14 7 11 10 4 13 1 5 8 12 6 9 3 2 15
3 13 8 10 1 3 15 4 2 11 6 7 12 0 5 14 9
S-Box 3: Substitution Box 3
Row / Column 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
0 10 0 9 14 6 3 15 5 1 13 12 7 11 4 2 8
1 13 7 0 9 3 4 6 10 2 8 5 14 12 11 15 1
2 13 6 4 9 8 15 3 0 11 1 2 12 5 10 14 7
3 1 10 13 0 6 9 8 7 4 15 14 3 11 5 2 12

S-Box 4: Substitution Box 4

Row / Column 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
0 7 13 14 3 0 6 9 10 1 2 8 5 11 12 4 15
1 13 8 11 5 6 15 0 3 4 7 2 12 1 10 14 9
2 10 6 9 0 12 11 7 13 15 1 3 14 5 2 8 4
3 3 15 0 6 10 1 13 8 9 4 5 11 12 7 2 14
S-Box 5: Substitution Box 5
Row / Column 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
0 2 12 4 1 7 10 11 6 8 5 3 15 13 0 14 9
1 14 11 2 12 4 7 13 1 5 0 15 10 3 9 8 6
2 4 2 1 11 10 13 7 8 15 9 12 5 6 3 0 14
3 11 8 12 7 1 14 2 13 6 15 0 9 10 4 5 3

S-Box 6: Substitution Box 6

Row / Column 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
0 12 1 10 15 9 2 6 8 0 13 3 4 14 7 5 11
1 10 15 4 2 7 12 9 5 6 1 13 14 0 11 3 8
2 9 14 15 5 2 8 12 3 7 0 4 10 1 13 11 6
3 4 3 2 12 9 5 15 10 11 14 1 7 6 0 8 13
S-Box 7: Substitution Box 7
Row / Column 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
0 4 11 2 14 15 0 8 13 3 12 9 7 5 10 6 1
1 13 0 11 7 4 9 1 10 14 3 5 12 2 15 8 6
2 1 4 11 13 12 3 7 14 10 15 6 8 0 5 9 2
3 6 11 13 8 1 4 10 7 9 5 0 15 14 2 3 12

S-Box 8: Substitution Box 8

Row / Column 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
0 13 2 8 4 6 15 11 1 10 9 3 14 5 0 12 7
1 1 15 13 8 10 3 7 4 12 5 6 11 0 14 9 2
2 7 11 4 1 9 12 14 2 0 6 10 13 15 3 5 8
3 2 1 14 7 4 10 8 13 15 12 9 0 3 5 6 11
Permutation Table (P Table)
◼ P
16 7 20 21 29 12 28 17

1 15 23 26 5 18 31 10

2 8 24 14 32 27 3 9

9 13 30 6 22 11 4 25
Final Permutation
◼ IP-1
40 8 48 16 56 24 64 32
39 7 47 15 55 23 63 31
38 6 46 14 54 22 62 30
37 5 45 13 53 21 61 29
36 4 44 12 52 20 60 28
35 3 43 11 51 19 59 27
34 2 42 10 50 18 58 26
33 1 41 9 49 17 57 25
 Key Schedule Algorithm
Input Key

Permuted Choice One (PC-1)

C0 D0
▪ ▪
▪ ▪
▪ ▪
Ci-1 Di-1
Permuted Choice Two (PC-2)

Schedule of Left Shifts

Keyi
Ci Di
 PERMUTED CHOICE 1 (PC-1)
57 49 41 33 25 17 9
1 58 50 42 34 26 18
10 2 59 51 43 35 27
19 11 3 60 52 44 36
63 55 47 39 31 23 15
7 62 54 46 38 30 22
14 6 61 53 45 37 29
21 13 5 28 20 12 4
 ITERATION PROCESS

Round 1 2 3 4 5 6 7 8
Iterations 1 1 2 2 2 2 2 2

Round 9 10 11 12 13 14 15 16
Iterations 1 2 2 2 2 2 2 1
 PERMUTED CHOICE 2 (PC-2)
14 17 11 24 1 5
3 28 15 6 21 10
23 19 12 4 26 8
16 7 27 20 13 2
41 52 31 37 47 55
30 40 51 45 33 48
44 49 39 56 34 53
46 42 50 36 29 32
Decryption
◼ The same algorithm as
encryption.
◼ Reversed the order of key
(Key16, Key15, … Key1).
◼ For example:
 IP undoes IP-1 step of
encryption.
 1st round with SK16
undoes 16th encrypt round.

[1]
Strength of DES
◼ Criticism
 Reduction in key size of 72 bits
◼ Too short to withstand with brute-force attack

 S-boxes were classified.

◼ Weak points enable NSA to decipher without key.

◼ 56-bit keys have 256 = 7.2 x 1016 values

 Brute force search looks hard.
 A machine performing one DES encryption per
microsecond would take more than a thousand year
to break the cipher.
Strength of DES
◼ Avalanche effect in
DES
 Ifa small change in
either the plaintext or
the key, the ciphertext
should change
markedly.
◼ DES exhibits a strong
avalanche effect.
Ultimate
◼ DES was proved insecure
 In 1997 on Internet in a few months
 in 1998 on dedicated h/w (EFF) in a few days
 In 1999 above combined in 22hrs!
AES
Chapter 5 –Advanced Encryption
Standard

"It seems very simple."

"It is very simple. But if you don't know what
the key is it's virtually indecipherable."
—Talking to Strange Men, Ruth Rendell
 AES Origins
 clear a replacement for DES was needed
 have theoretical attacks that can break it
 have demonstrated exhaustive key search attacks
 can use Triple-DES – but slow, has small blocks
 US NIST issued call for ciphers in 1997
 15 candidates accepted in Jun 98
 5 were shortlisted in Aug-99
 Rijndael was selected as the AES in Oct-2000
 issued as FIPS PUB 197 standard in Nov-2001
 The AES Cipher - Rijndael
 designed by Rijmen-Daemen in Belgium
 has 128/192/256 bit keys, 128 bit data
 an iterative rather than Feistel cipher
 processes data as block of 4 columns of 4 bytes
 operates on entire data block in every round
 designed to have:
 resistance against known attacks
 speed and code compactness on many CPUs
 design simplicity
 AES
Encryption
Process
 AES Structure
 data block of 4 columns of 4 bytes is state
 key is expanded to array of words
 has 9/11/13 rounds in which state undergoes:
 byte substitution (1 S-box used on every byte)
 shift rows (permute bytes between groups/columns)
 mix columns (subs using matrix multiply of groups)
 add round key (XOR state with key material)
 view as alternating XOR key & scramble data bytes
 initial XOR key material & incomplete last round
 with fast XOR & table lookup implementation
AES Structure
 Some Comments on AES
1. an iterative rather than Feistel cipher
2. key expanded into array of 32-bit words
1. four words form round key in each round
3. 4 different stages are used as shown
4. has a simple structure
5. only AddRoundKey uses key
6. AddRoundKey a form of Vernam cipher
7. each stage is easily reversible
8. decryption uses keys in reverse order
9. decryption does recover plaintext
10. final round has only 3 stages
 Substitute Bytes
 a simple substitution of each byte
 uses one table of 16x16 bytes containing a
permutation of all 256 8-bit values
 each byte of state is replaced by byte indexed by
row (left 4-bits) & column (right 4-bits)
 eg. byte {95} is replaced by byte in row 9 column 5
 which has value {2A}
 S-box constructed using defined transformation
of values in GF(28)
 designed to be resistant to all known attacks
Substitute Bytes
Substitute Bytes Example
 Shift Rows
 a circular byte shift in each each
 1st row is unchanged
 2nd row does 1 byte circular shift to left
 3rd row does 2 byte circular shift to left
 4th row does 3 byte circular shift to left
 decrypt inverts using shifts to right
 since state is processed by columns, this step
permutes bytes between the columns
Shift Rows
 Mix Columns
 each column is processed separately
 each byte is replaced by a value
dependent on all 4 bytes in the column
 effectively a matrix multiplication in GF(28)
using prime poly m(x) =x8+x4+x3+x+1
Mix Columns
Mix Columns Example
 AES Arithmetic
 uses arithmetic in the finite field GF(28)
 with irreducible polynomial
m(x) = x8 + x4 + x3 + x + 1
which is (100011011) or {11b}
 e.g.
{02} • {87} mod {11b} = (1 0000 1110) mod {11b}
= (1 0000 1110) xor (1 0001 1011) = (0001 0101)
 Mix Columns
 can express each col as 4 equations
 to derive each new byte in col
 decryption requires use of inverse matrix
 with larger coefficients, hence a little harder
 have an alternate characterisation
 each column a 4-term polynomial
 with coefficients in GF(28)
 and polynomials multiplied modulo (x4+1)
 coefficients based on linear code with
maximal distance between codewords
 Add Round Key
 XOR state with 128-bits of the round key
 again processed by column (though
effectively a series of byte operations)
 inverse for decryption identical
 since XOR own inverse, with reversed keys
 designed to be as simple as possible
 a form of Vernam cipher on expanded key
 requires other stages for complexity / security
Add Round Key
AES Round
 AES Key Expansion
 takes 128-bit (16-byte) key and expands
into array of 44/52/60 32-bit words
 start by copying key into first 4 words
 then loop creating words that depend on
values in previous & 4 places back
 in 3 of 4 cases just XOR these together
 1st word in 4 has rotate + S-box + XOR round
constant on previous, before XOR 4 th back
AES Key Expansion
 Key Expansion Rationale
 designed to resist known attacks
 design criteria included
 knowing part key insufficient to find many more
 invertible transformation
 fast on wide range of CPU’s
 use round constants to break symmetry
 diffuse key bits into round keys
 enough non-linearity to hinder analysis
 simplicity of description
 AES
Example
Key
Expansion
 AES
Example
Encryption
 AES
Example
Avalanche
 AES Decryption
 AES decryption is not identical to
encryption since steps done in reverse
 but can define an equivalent inverse
cipher with steps as for encryption
 but using inverses of each step
 with a different key schedule
 works since result is unchanged when
 swap byte substitution & shift rows
 swap mix columns & add (tweaked) round key
AES Decryption
 Implementation Aspects
 can efficiently implement on 8-bit CPU
 byte substitution works on bytes using a table
of 256 entries
 shift rows is simple byte shift
 add round key works on byte XOR’s
 mix columns requires matrix multiply in GF(28)
which works on byte values, can be simplified
to use table lookups & byte XOR’s
 Implementation Aspects
 can efficiently implement on 32-bit CPU
 redefine steps to use 32-bit words
 can precompute 4 tables of 256-words
 then each column in each round can be
computed using 4 table lookups + 4 XORs
 at a cost of 4Kb to store tables
 designers believe this
very efficient
implementation was a key factor in its
selection as the AES cipher
 Summary
 have considered:
 the AES selection process
 the details of Rijndael – the AES cipher
 looked at the steps in each round
 the key expansion
 implementation aspects
 AES Example - Input (128 bit key and message)
Key in English: Thats my Kung Fu (16 ASCII characters, 1 byte each)
Translation into Hex:

T h a t s m y K u n g F u
54 68 61 74 73 20 6D 79 20 4B 75 6E 67 20 46 75

Key in Hex (128 bits): 54 68 61 74 73 20 6D 79 20 4B 75 6E 67 20 46 75

Plaintext in English: Two One Nine Two (16 ASCII characters, 1 byte each)
Translation into Hex:

Tw o O n e N i n e Tw o
54 77 6F 20 4F 6E 65 20 4E 69 6E 65 20 54 77 6F

Plaintext in Hex (128 bits): 54 77 6F 20 4F 6E 65 20 4E 69 6E 65 20 54 77 6F

1
 AES Example - The first Roundkey
• Key in Hex (128 bits): 54 68 61 74 73 20 6D 79 20 4B 75 6E 67 20 46 75
• w[0] = (54, 68, 61, 74), w[1] = (73, 20, 6D, 79), w[2] = (20, 4B, 75, 6E), w[3] = (67, 20, 46, 75)
• g(w[3]):
• circular byte left shift of w[3]: (20, 46, 75, 67)
• Byte Substitution (S-Box): (B7, 5A, 9D, 85)
• Adding round constant (01, 00, 00, 00) gives: g(w[3]) = (B6, 5A, 9D, 85)

• w[4] = w[0] ⊕ g(w[3]) = (E2, 32, F C, F 1):

0101 0100 0110 1000 0110 0001 0111 0100
1011 0110 0101 1010 1001 1101 1000 0101
1110 0010 0011 0010 1111 1100 1111 0001
E2 32 FC F1
• w[5] = w[4] ⊕ w[1] = (91, 12, 91, 88), w[6] = w[5] ⊕ w[2] = (B1, 59, E4, E6),
w[7] = w[6] ⊕ w[3] = (D6, 79, A2, 93)
• first roundkey: E2 32 FC F1 91 12 91 88 B1 59 E4 E6 D6 79 A2 93

2
 AES Example - All RoundKeys

• Round 0: 54 68 61 74 73 20 6D 79 20 4B 75 6E 67 20 46 75
• Round 1: E2 32 FC F1 91 12 91 88 B1 59 E4 E6 D6 79 A2 93
• Round 2: 56 08 20 07 C7 1A B1 8F 76 43 55 69 A0 3A F7 FA
• Round 3: D2 60 0D E7 15 7A BC 68 63 39 E9 01 C3 03 1E FB
• Round 4: A1 12 02 C9 B4 68 BE A1 D7 51 57 A0 14 52 49 5B
• Round 5: B1 29 3B 33 05 41 85 92 D2 10 D2 32 C6 42 9B 69
• Round 6: BD 3D C2 B7 B8 7C 47 15 6A 6C 95 27 AC 2E 0E 4E
• Round 7: CC 96 ED 16 74 EA AA 03 1E 86 3F 24 B2 A8 31 6A
• Round 8: 8E 51 EF 21 FA BB 45 22 E4 3D 7A 06 56 95 4B 6C
• Round 9: BF E2 BF 90 45 59 FA B2 A1 64 80 B4 F7 F1 CB D8
• Round 10: 28 FD DE F8 6D A4 24 4A CC C0 A4 FE 3B 31 6F 26

3
 AES Example - Add Roundkey, Round 0
• State Matrix and Roundkey No.0 Matrix:
   
54 4F 4E 20 54 73 20 67
 77 6E 69 54  68 20 4B 20
   
6F 65 6E 77  61 6D 75 46
20 20 65 6F 74 79 6E 75
• XOR the corresponding entries, e.g., 69 ⊕ 4B = 22
0110 1001
0100 1011
0010 0010
• the new State Matrix is
 
00 3C 6E 47
1F 4E 22 74 
 
0E 08 1B 31 
54 59 0B 1A

4
 AES Example - Round 1, Substitution Bytes
• current State Matrix is
 
00 3C 6E 47
1F 4E 22 74 
 
0E 08 1B 31 
54 59 0B 1A
• substitute each entry (byte) of current state matrix by corresponding entry in AES
S-Box
• for instance: byte 6E is substituted by entry of S-Box in row 6 and column E, i.e.,
by 9F
• this leads to new State Matrix
 
63 EB 9F A0
 C0 2F 93 92 
 
AB 30 AF C7
20 CB 2B A2
• this non-linear layer is for resistance to differential and linear cryptanalysis attacks
5
 AES Example - Round 1, Shift Row

• the current State Matrix is

 
63 EB 9F A0
 C0 2F 93 92 
 
AB 30 AF C7
20 CB 2B A2
• four rows are shifted cyclically to the left by offsets of 0,1,2, and 3
• the new State Matrix is
 
63 EB 9F A0
 2F 93 92 C0
 
AF C7 AB 30 
A2 20 CB 2B
• this linear mixing step causes diffusion of the bits over multiple rounds

6
 AES Example - Round 1, Mix Column

• Mix Column multiplies fixed matrix against current State Matrix:

    
02 03 01 01 63 EB 9F A0 BA 84 E8 1B
01 02 03 01  2F 93 92 C0  75 A4 8D 40 
01 01 02 03 AF C7 AB 30  =  F 4 8D 06 7D 
    

03 01 01 02 A2 20 CB 2B 7A 32 0E 5D
• entry BA is result of (02 • 63) ⊕ (03 • 2F ) ⊕ (01 • AF ) ⊕ (01 • A2):
• 02 • 63 = 00000010 • 01100011 = 11000110
• 03 • 2F = (02 • 2F ) ⊕ 2F = (00000010 • 00101111) ⊕ 00101111 = 01110001
• 01 • AF = AF = 10101111 and 01 • A2 = A2 = 10100010
• hence
11000110
01110001
10101111
10100010
10111010

7
 AES Example - Add Roundkey, Round 1

• State Matrix and Roundkey No.1 Matrix:

   
BA 84 E8 1B E2 91 B1 D6
 75 A4 8D 40   32 12 59 79 
   
 F 4 8D 06 7D F C 91 E4 A2 
7A 32 0E 5D F 1 88 E6 93
• XOR yields new State Matrix
 
58 15 59 CD
 47 B6 D4 39 
 
 08 1C E2 DF 
8B BA E8 CE
• AES output after Round 1: 58 47 08 8B 15 B6 1C BA 59 D4 E2 E8 CD 39 DF CE

8
 AES Example - Round 2

• after Substitute Byte and after Shift Rows:

   
6A 59 CB BD 6A 59 CB BD
 A0 4E 48 12  4E 48 12 A0 
   
 30 9C 98 9E   98 9E 30 9B 
3D F 4 9B 8B 8B 3D F 4 9B

• after Mixcolumns and after Roundkey:

   
15 C9 7F 9D 43 0E 09 3D
CE 4D 4B C2  C6 57 08 F 8 
   
 89 71 BE 88  A9 C0 EB 7F 
65 47 97 CD 62 C8 F E 37

9
 AES Example - Round 3

• after Substitute Byte and after Shift Rows:

   
1A AB 01 27 1A AB 01 27
 B4 5B 30 41  5B 30 41 B4 
   
 D3 BA E9 D2 E9 D2 D3 BA 
AA E8 BB 9A A9 AA E8 BB

• after Mixcolumns and after Roundkey:

   
AA 65 F A 88 78 70 99 4B
 16 0C 05 3A 76 76 3C 39 
   
 3D C1 DE 2A 30 7D 37 34 
B3 4B 5A 0A 54 23 5B F 1

10
 AES Example - Round 4

• after Substitute Byte and after Shift Rows:

   
BC 51 EE B3 BC 51 EE B3
 38 38 EB 12   38 EB 12 38 
   
 04 F F 9A 18   9A 18 04 F F 
20 26 39 A1 A1 20 26 39

• after Mixcolumns and after Roundkey:

   
10 BC D3 F 3 B1 08 04 E7
D8 94 E0 E0  CA F C B1 B2
   
 53 EA 9E 25   51 54 C9 6C 
24 40 73 7B ED E1 D3 20

11
 AES Example - Round 5

• after Substitute Byte and after Shift Rows:

   
C8 30 F 2 94 C8 30 F 2 94
 74 B0 C8 37   B0 C8 37 74
   
D1 20 DD 50  DD 50 D1 20
55 F 8 66 B7 B7 55 F 8 66

• after Mixcolumns and after Roundkey:

   
2A 26 8F E9 9B 23 5D 2F
 78 1E 0C 7A  51 5F 1C 38 
   
1B A7 6F 0A  20 22 BD 91 
5B 62 00 3F 68 F 0 32 56

12
 AES Example - Round 6

• after Substitute Byte and after Shift Rows:

   
14 26 4C 15 14 26 4C 15
D1 CF 9C 07  CF 9C 07 D1
   
B7 93 7A 81   7A 81 B7 93 
45 8C 23 B1 B1 45 8C 23

• after Mixcolumns and after Roundkey:

   
A9 37 AA F 2 14 8F C0 5E
AE D8 0C 21  93 A4 60 0F 
   
 E7 6C B1 9C  25 2B 24 92 
F 0 F D 67 3B 77 E8 40 75

13
 AES Example - Round 7

• after Substitute Byte and after Shift Rows:

   
F A 73 BA 58 F A 73 BA 58
DC 49 D0 76   49 D0 76 DC 
   
 3F F 1 36 4F   36 4F 3F F 1 
F 5 9B 09 9D 9D F 5 9B 09

• after Mixcolumns and after Roundkey:

   
9F 37 51 37 53 43 4F 85
AF EC 8C F A  39 06 0A 52 
   
 63 39 04 66  8E 93 3B 57 
4B F B B1 D7 5D F 8 95 BD

14
 AES Example - Round 8

• after Substitute Byte and after Shift Rows:

   
ED 1A 84 97 ED 1A 84 97
 12 6F 67 00   6F 67 00 12 
   
 19 DC E2 5B   E2 5B 19 DC 
4C 41 2A 7A 7A 4C 41 2A

• after Mixcolumns and after Roundkey:

   
E8 8A 4B F 5 66 70 AF A3
 74 75 EE E6  25 CE D3 73 
   
D3 1F 75 58  3C 5A 0F 13 
55 8A 0C 38 74 A8 0A 54

15
 AES Example - Round 9

• after Substitute Byte and after Shift Rows:

   
33 51 79 0A 33 51 79 0A
 3F 8B 66 8F  8B 66 8F 3F 
   
EB BE 76 7D   76 7D EB BE 
92 C2 67 20 20 92 C2 67

• after Mixcolumns and after Roundkey:

   
B6 E7 51 8C 09 A2 F 0 7B
 84 88 98 CA   66 D1 F C 3B 
   
 34 60 66 F B  8B 9A E6 30 
E8 D7 70 51 78 65 C4 89

16
 AES Example - Round 10

• after Substitute Byte and after Shift Rows:

   
01 3A 8C 21 01 3A 8C 21
 33 3E B0 E2 3E B0 E2 33 
   
 3D B8 8E 04  8E 04 3D B8
BC 4D 1C A7 A7 BC 4D 1C

• after Roundkey (Attention: no Mix columns in last round):

 
29 57 40 1A
C3 14 22 02 
 
 50 20 99 D7
5F F 6 B3 3A
• ciphertext: 29 C3 50 5F 57 14 20 F6 40 22 99 B3 1A 02 D7 3A

17