Contents
Contents
1 Introduction 4
2 Finite Field Arithmetics 5
2.1 Byte Representation Forms . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.1.1 Binary Representation . . . . . . . . . . . . . . . . . . . . . . . . 5
2.1.2 Decimal Representation . . . . . . . . . . . . . . . . . . . . . . . 5
2.1.3 Hexadecimal Representation . . . . . . . . . . . . . . . . . . . . . 6
2.1.4 Polynomial Representation . . . . . . . . . . . . . . . . . . . . . . 7
2.2 Polynomial Addition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.3 Polynomial Multiplication . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.4 Polynomial Division . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.5 poly_mult Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . 11
3 aes_demo 14
4 aes_init 16
5 s_box_gen 17
5.1 find_inverse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
5.2 aff_trans . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
5.3 s_box_inversion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
6 rcon_gen 23
7 key_expansion 25
7.1 rot_word . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
7.2 sub_bytes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
8 poly_mat_gen 30
8.1 cycle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
2
Contents
9 cipher 35
9.1 add_round_key . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
9.2 shift_rows . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
9.3 mix_columns . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
10 inv_cipher 41
10.1 inv_shift_rows . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
3
1 Introduction
1 Introduction
This paper discusses a Matlab implementation of the Advanced Encryption Standard
(AES) [7]. AES is based on the block cipher Rijndael [4] [5] and b ecame the designated
successor of the Data Encryption Standard (DES) [8] which has been implemented in
a tremendous number of cryptographic modules worldwide since 1977. Matlab [1]
is a matrix-oriented programming language, perfectly suited for the matrix-based data
structure of AES.
Even though this implementation is fully operational, (i. e. it can be utilized to encrypt
arbitrarily chosen plaintext into ciphertext and vice versa), the main optimization pa-
rameter of this implementation has not been execution speed but understandability.
Assembler programmers might throw their hands up in horror, looking at shifting or
substitution functions that have been coded algorithmically step-by-step instead of us-
ing a simple predefined lookup table; the primary goal of this ”educational” paper is to
explain in greater detail what has to be done, rather than how it could be done for speed
optimization reasons.
Also the question why certain algorithms have been chosen, e. g. with respect to the resis-
tance against differential and linear cryptanalysis, is far beyond the scope of this paper.
Interested readers are referred to the annex of the AES proposal [6] or a good book on
cryptography [9]. Even Galois fields, the workhorse of modern cryptography, are intro-
duced in a very pragmatic, engineer-friendly way, touching only as much mathematical
background as necessary.
Furthermore, in order to minimize the number of if-then-else-conditions, a key length
of 128 bits (16 bytes) has been implemented only; the extension to 24 or 32 bytes key
lengths, as defined in [7], can easily be realized by altering the corresponding constants.
4
2 Finite Field Arithmetics
2 Finite Field Arithmetics
The following section introduces the different representation forms of a byte and discusses
the basic arithmetics of finite fields.
A finite field, also called a Galois Field [3], [2], is a field with only finitely many elements.
The finite field GF(2
8
) e. g. consists of the 2
8
= 256 different numbers (0 . . . 255)
represented by one byte (8 bits). Special xor- and modulo-operations, explained in
detail in the following sections, make sure that the sum and the product of two finite
field elements remain within the range of the original finite field.
2.1 Byte Representation Forms
The following four sections convert an example through the four usual representation
forms of a finite field element.
2.1.1 Binary Representation
A byte consists of 8 bits, leading to the binary representation (index b) of an arbitrarily
chosen example:
10100011
b
(1)
2.1.2 Decimal Representation
This example can be represented in decimal form (index d) by multiplying every bit by
its corresponding power of two:
1 · 2
7
+ 0 · 2
6
+ 1 · 2
5
+ 0 · 2
4
+ 0 · 2
3
+ 0 · 2
2
+ 1 · 2
1
+ 1 · 2
0
= 2
7
+ 2
5
+ 2
1
+ 2
0
= 128 + 32 + 2 + 1
= 163
d
(2)
Matlab uses the predefined function bin2dec (”binary to decimal”) to perform this
conversion. Note the use of single quotation marks to input the binary representation
as a string (character array):
>> bin2dec (’10100011’)
ans =
163
Example 1: Matlab example of bin2dec
5
