Lecture 8: AES: The Advanced Encryption Standard Lecture ...

Lecture 8: AES: The Advanced Encryption Standard

Lecture Notes on ¡°Computer and Network Security¡±

by Avi Kak (kak@purdue.edu)

February 7, 2024

11:11pm

?2024 Avinash Kak, Purdue University

Goals:

? To review the overall structure of AES and to focus particularly on the

four steps used in each round of AES: (1) byte substitution, (2) shift

rows, (3) mix columns, and (4) add round key.

? Python and Perl implementations for creating the lookup tables for the

byte substitution steps in encryption and decryption.

? Python and Perl implementations of the Key Expansion Algorithms for

the 128 bit, 192 bit, and 256 bit AES.

? Perl implementations for creating histograms of the differentials and for

constructing linear approximation tables in attacks on block ciphers.

CONTENTS

Section Title

Page

8.1

Salient Features of AES

3

8.2

The Encryption Key and Its Expansion

10

8.3

The Overall Structure of AES

12

8.4

The Four Steps in Each Round of Processing

15

8.5

The Substitution Bytes Step: SubBytes and

InvSubBytes

19

8.5.1

Traditional Explanation of Byte Substitution:

Constructing the 16 ¡Á 16 Lookup Table

22

8.5.2

Python and Perl Implementations for the AES

Byte Substitution Step

27

8.6

The Shift Rows Step: ShiftRows and InvShiftRows

32

8.7

The Mix Columns Step: MixColumns and

InvMixColumns

34

8.8

The Key Expansion Algorithm

37

8.8.1

The Algorithmic Steps in Going from one 4-Word

Round Key to the Next 4-Word Round Key

41

8.8.2

Python and Perl Implementations of the Key

Expansion Algorithm

46

8.9

Differential, Linear, and Interpolation Attacks on

Block Ciphers

57

8.10

Homework Problems

91

2

Computer and Network Security by Avi Kak

Lecture 8

Back to TOC

8.1 SALIENT FEATURES OF AES

? AES is a block cipher with a block length of 128 bits.

? AES allows for three different key lengths: 128, 192, or 256 bits.

Most of our discussion will assume that the key length is 128

bits. [With regard to using a key length other than 128 bits,

the main thing that changes in AES is how you generate the

key schedule from the key ¡ª an issue I address at the end of

Section 8.8.1. The notion of key schedule in AES is explained

in Sections 8.2 and 8.8.]

? Encryption consists of 10 rounds of processing for 128-bit keys,

12 rounds for 192-bit keys, and 14 rounds for 256-bit keys.

? Except for the last round in each case, all other rounds are

identical.

? Each round of processing includes one single-byte based

substitution step, a row-wise permutation step, a column-wise

mixing step, and the addition of the round key. The order in

which these four steps are executed is different for encryption

and decryption.

3

Computer and Network Security by Avi Kak

Lecture 8

? To appreciate the use of ¡°row¡± and ¡°column¡± in the previous

bullet, you need to think of the input 128-bit block as consisting

of a 4 ¡Á 4 array of bytes, arranged as follows:

?

? byte0

?

?

? byte1

?

?

? byte

2

?

?

byte3

byte4

byte5

byte6

byte7

byte8

byte9

byte10

byte11

byte12

byte13

byte14

byte15

?

?

?

?

?

?

?

?

?

?

? Notice that the first four bytes of a 128-bit input block

occupy the first column in the 4 ¡Á 4 array of bytes. The next

four bytes occupy the second column, and so on.

? The 4 ¡Á 4 array of bytes shown above is referred to as the state

array in AES. If you are trying to create your own

implementation of AES in Python, you will find following

statement, which uses the notion of list comprehension in

Python, very useful for creating an initialized structure that

looks like the state array of AES:

statearray = [[0 for x in range(4)] for x in range(4)]

Next, try the following calls in relation to the structure thus

created:

import sys

statearray = [[0 for x in range(4)] for x in range(4)]

print(statearray)

4

Computer and Network Security by Avi Kak

Lecture 8

print(statearray[0])

print(statearray[2][3])

block = list(range(128))

print("\n\nblock: ", block)

for i in range(4):

for j in range(4):

statearray[j][i] = block[32*i + 8*j:32*i + 8*(j+1)]

for i in range(4):

sys.stdout.write("\n\n")

for j in range(4):

sys.stdout.write( str(statearray[i][j]) )

sys.stdout.write("\t")

sys.stdout.write("\n\n")

This is a nice warm-up exercise before you start implementing

AES in Python.

? AES also has the notion of a word. A word consists of four

bytes, that is 32 bits. Therefore, each column of the state array

is a word, as is each row.

? Each round of processing works on the input state array and

produces an output state array.

? The output state array produced by the last round is rearranged

into a 128-bit output block.

? Unlike DES, the decryption algorithm differs substantially from

the encryption algorithm. Although, overall, very similar steps

5

 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download