Written By:	Adam Berent
Advanced Encryption Standard by Example
V.1.7

1.0 Preface

The following document provides a detailed and easy to understand explanation of the implementation of the AES (RIJNDAEL) encryption algorithm. The purpose of this paper is to give developers with little or no knowledge of cryptography the ability to implement AES.

2.0 Terminology

There are terms that are frequently used throughout this paper that need to be clarified.

Block: AES is a block cipher. This means that the number of bytes that it encrypts is fixed. AES can currently encrypt blocks of 16 bytes at a time; no other block sizes are presently a part of the AES standard. If the bytes being encrypted are larger than the specified block then AES is executed concurrently. This also means that AES has to encrypt a minimum of 16 bytes. If the plain text is smaller than 16 bytes then it must be padded.

Simply said the block is a reference to the bytes that are processed by the algorithm.

State: Defines the current condition (state) of the block. That is the block of bytes that are currently being worked on. The state starts off being equal to the block, however it changes as each round of the algorithms executes. Plainly said this is the block in progress.

XOR Refers to the bitwise operator Exclusive Or. XOR operates on the individual bits in a byte in the following way:

0 XOR 0 = 0

1 XOR 0 = 1

1 XOR 1 = 0

0 XOR 1 = 1

For example the Hex digits D4 XOR FF

11010100

XOR 11111111

= 00101011 (Hex 2B)

Another interesting property of the XOR operator is that it is reversible. So Hex 2B XOR FF = D4

Most programming languages have the XOR operator built in.

Programming Language	XOR Operator
C	^
C++	^
C#	^
Java	^
Visual Basic	XOR

HEX: Defines a notation of numbers in base 16. This simply means that; the highest number that can be represented in a single digit is 15, rather than the usual 9 in the decimal (base 10) system.

Hex to Decimal table:

0 1 2 3 4 5 6 7 8 9 A B C D E F

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

1 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31

2 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47

3 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63

4 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79

5 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95

6 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111

7 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127

8 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143

9 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159

A 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175

B 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191

C 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207

D 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223

E 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239

F 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255

For example using the above table HEX D4 = DEC 212

All of the tables and examples in this paper are written in HEX. The reason for this is that a single digit of Hex represents exactly 4 bits. This means that a single byte can always be represented by 2 HEX digits. This also makes it very useful in creating lookup tables where each HEX digit can represent a table index.

3.0 AES Brief History

Effective May 26, 2002 the National Institute of Science and Technology (NIST) has selected a block cipher called RIJNDAEL (named after its creators Vincent Rijmen and Joan Daemen) as the symmetric key encryption algorithm to be used to encrypt sensitive but unclassified American federal information.

RIJNDAEL was originally a variable block (16, 24, 32 bytes) and variable key size (16, 24, 32 bytes) encryption algorithm. NIST has however decided to define AES with a block size of 16 bytes while keeping their options open to future changes.

4.0 AES Algorithm

AES is an iterated symmetric block cipher, which means that:

· AES works by repeating the same defined steps multiple times.

· AES is a secret key encryption algorithm.

· AES operates on a fixed number of bytes

AES as well as most encryption algorithms is reversible. This means that almost the same steps are performed to complete both encryption and decryption in reverse order. The AES algorithm operates on bytes, which makes it simpler to implement and explain.

This key is expanded into individual sub keys, a sub keys for each operation round. This process is called KEY EXPANSION, which is described at the end of this document.

As mentioned before AES is an iterated block cipher. All that means is that the same operations are performed many times on a fixed number of bytes. These operations can easily be broken down to the following functions:

 
ADD ROUND KEY  
BYTE SUB   
SHIFT ROW
MIX COLUMN 

An iteration of the above steps is called a round. The amount of rounds of the algorithm depends on the key size.

Key Size (bytes)	Block Size (bytes)	Rounds
16	16	10
24	16	12
32	16	14

The only exception being that in the last round the Mix Column step is not performed, to make the algorithm reversible during decryption.
 
4.1 Encryption

AES encryption cipher using a 16 byte key.
 

Round	Function
-	Add Round Key(State)
0	Add Round Key(Mix Column(Shift Row(Byte Sub(State))))
1	Add Round Key(Mix Column(Shift Row(Byte Sub(State))))
2	Add Round Key(Mix Column(Shift Row(Byte Sub(State))))
3	Add Round Key(Mix Column(Shift Row(Byte Sub(State))))
4	Add Round Key(Mix Column(Shift Row(Byte Sub(State))))
5	Add Round Key(Mix Column(Shift Row(Byte Sub(State))))
6	Add Round Key(Mix Column(Shift Row(Byte Sub(State))))
7	Add Round Key(Mix Column(Shift Row(Byte Sub(State))))
8	Add Round Key(Mix Column(Shift Row(Byte Sub(State))))
9	Add Round Key(Shift Row(Byte Sub(State)))

 
AES encryption cipher using a 24 byte key.
 

Round	Function
-	Add Round Key(State)
0	Add Round Key(Mix Column(Shift Row(Byte Sub(State))))
1	Add Round Key(Mix Column(Shift Row(Byte Sub(State))))
2	Add Round Key(Mix Column(Shift Row(Byte Sub(State))))
3	Add Round Key(Mix Column(Shift Row(Byte Sub(State))))
4	Add Round Key(Mix Column(Shift Row(Byte Sub(State))))
5	Add Round Key(Mix Column(Shift Row(Byte Sub(State))))
6	Add Round Key(Mix Column(Shift Row(Byte Sub(State))))
7	Add Round Key(Mix Column(Shift Row(Byte Sub(State))))
8	Add Round Key(Mix Column(Shift Row(Byte Sub(State))))
9	Add Round Key(Mix Column(Shift Row(Byte Sub(State))))
10	Add Round Key(Mix Column(Shift Row(Byte Sub(State))))
11	Add Round Key(Shift Row(Byte Sub(State)))

 
AES encryption cipher using a 32 byte key.
 

Round	Function
-	Add Round Key(State)
0	Add Round Key(Mix Column(Shift Row(Byte Sub(State))))
1	Add Round Key(Mix Column(Shift Row(Byte Sub(State))))
2	Add Round Key(Mix Column(Shift Row(Byte Sub(State))))
3	Add Round Key(Mix Column(Shift Row(Byte Sub(State))))
4	Add Round Key(Mix Column(Shift Row(Byte Sub(State))))
5	Add Round Key(Mix Column(Shift Row(Byte Sub(State))))
6	Add Round Key(Mix Column(Shift Row(Byte Sub(State))))
7	Add Round Key(Mix Column(Shift Row(Byte Sub(State))))
8	Add Round Key(Mix Column(Shift Row(Byte Sub(State))))
9	Add Round Key(Mix Column(Shift Row(Byte Sub(State))))
10	Add Round Key(Mix Column(Shift Row(Byte Sub(State))))
11	Add Round Key(Mix Column(Shift Row(Byte Sub(State))))
12	Add Round Key(Mix Column(Shift Row(Byte Sub(State))))
13	Add Round Key(Shift Row(Byte Sub(State)))

 
 
4.2 Decryption
 
 AES decryption cipher using a 16 byte key.
 

Round	Function
-	Add Round Key(State)
0	Mix Column(Add Round Key(Byte Sub(Shift Row(State))))
1	Mix Column(Add Round Key(Byte Sub(Shift Row(State))))
2	Mix Column(Add Round Key(Byte Sub(Shift Row(State))))
3	Mix Column(Add Round Key(Byte Sub(Shift Row(State))))
4	Mix Column(Add Round Key(Byte Sub(Shift Row(State))))
5	Mix Column(Add Round Key(Byte Sub(Shift Row(State))))
6	Mix Column(Add Round Key(Byte Sub(Shift Row(State))))
7	Mix Column(Add Round Key(Byte Sub(Shift Row(State))))
8	Mix Column(Add Round Key(Byte Sub(Shift Row(State))))
9	Add Round Key(Byte Sub(Shift Row(State)))

 
 AES decryption cipher using a 24 byte key.
 

Round	Function
-	Add Round Key(State)
0	Mix Column(Add Round Key(Byte Sub(Shift Row(State))))
1	Mix Column(Add Round Key(Byte Sub(Shift Row(State))))
2	Mix Column(Add Round Key(Byte Sub(Shift Row(State))))
3	Mix Column(Add Round Key(Byte Sub(Shift Row(State))))
4	Mix Column(Add Round Key(Byte Sub(Shift Row(State))))
5	Mix Column(Add Round Key(Byte Sub(Shift Row(State))))
6	Mix Column(Add Round Key(Byte Sub(Shift Row(State))))
7	Mix Column(Add Round Key(Byte Sub(Shift Row(State))))
8	Mix Column(Add Round Key(Byte Sub(Shift Row(State))))
9	Mix Column(Add Round Key(Byte Sub(Shift Row(State))))
10	Mix Column(Add Round Key(Byte Sub(Shift Row(State))))
11	Add Round Key(Byte Sub(Shift Row(State)))

 
 AES decryption cipher using a 32 byte key.
 

Round	Function
-	Add Round Key(State)
0	Mix Column(Add Round Key(Byte Sub(Shift Row(State))))
1	Mix Column(Add Round Key(Byte Sub(Shift Row(State))))
2	Mix Column(Add Round Key(Byte Sub(Shift Row(State))))
3	Mix Column(Add Round Key(Byte Sub(Shift Row(State))))
4	Mix Column(Add Round Key(Byte Sub(Shift Row(State))))
5	Mix Column(Add Round Key(Byte Sub(Shift Row(State))))
6	Mix Column(Add Round Key(Byte Sub(Shift Row(State))))
7	Mix Column(Add Round Key(Byte Sub(Shift Row(State))))
8	Mix Column(Add Round Key(Byte Sub(Shift Row(State))))
9	Mix Column(Add Round Key(Byte Sub(Shift Row(State))))
10	Mix Column(Add Round Key(Byte Sub(Shift Row(State))))
11	Mix Column(Add Round Key(Byte Sub(Shift Row(State))))
12	Mix Column(Add Round Key(Byte Sub(Shift Row(State))))
13	Add Round Key(Byte Sub(Shift Row(State)))

5.0 AES Cipher Functions

5.1 Add Round Key

Each of the 16 bytes of the state is XORed against each of the 16 bytes of a portion of the expanded key for the current round. The Expanded Key bytes are never reused. So once the first 16 bytes are XORed against the first 16 bytes of the expanded key then the expanded key bytes 1-16 are never used again. The next time the Add Round Key function is called bytes 17-32 are XORed against the state.

The first time Add Round Key gets executed

State	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
	XOR	XOR	XOR	XOR	XOR	XOR	XOR