Note 4/20/17: Due to circumstances I have had to move my web pages here.
The Rijndael algorithm was announced as the winner of the Advanced Encryption Standard
(AES) in 2001. This algorithm is intended to replace the
DES algorithm. AES was designed to be efficient in both hardware
and software, and supports a block length of 128 bits
and key lengths of 128, 192, and 256 bits.
AES is defined in Fips 197.
Click here for a description of how AES works.
How AES Works
This page only describes the 128-bit version, but the 192-bit and 256-bit key versions
are similar.
AES is designed to work on bytes. However, each byte is interperted as a representation
of the polynomial:
b7x7 + b6x6 +
b5x5 + b4x4 +
b3x3 + b2x2 +
b1x + b0
Where each bi is either 0 or 1.
Addition and Multiplication
Addition then becomes exclusive-or, but multiplication is defined as polynomial
multiplication modulo x8 + x4 + x3 + x + 1.
For example 2d * a3 would be calculated as follows
(remembering xy + xy = 0):
| 2d = 00101101 = |
x5 + x3 + x2 + 1 |
| a3 = 10100011 = |
x7 + x5 + x + 1 |
| 2d * a3 = |
(x12 + x10 + x9 + x7) +
(x10 + x8 + x7 + x5) +
(x6 + x4 + x3 + x) +
(x5 + x3 + x2 + 1)
|
| = |
x12 + x9 + x8 + x6 + x4 +
x2 + x + 1 |
| - modulus * x4 = |
x9 + x7 + x6 + x5 +
x2 + x + 1 |
| - modulus * x = |
x7 + x6 + x4 + 1 |
| 2d * a3 = |
11010001 = d1 |
Although this seems not efficient, all multiplications are by a constant, so they
can be calculated in advance and turned into a simple table lookup.
Algorithm State
The 128-bit state can be represented as a 4 by 4 table of bytes. The cipher will perform
various operations on this array.
Encryption Algorithm (128-bit version)
Cipher(byte in[16], byte out[16], word w[44])
begin
byte state[4,4]
state = in
AddRoundKey(state, w[0, 3])
for round = 1 step 1 to 10
SubBytes(state)
ShiftRows(state)
MixColumns(state)
AddRoundKey(state, w[round*4, (round+1)*4-1])
end for
SubBytes(state)
ShiftRows(state)
AddRoundKey(state, w[40, 43])
out = state
end
SubBytes Routine
In this routine, each byte of the state is replaced according to the following
formula:
For each bit i, set bi to
bi xor b(i+4) mod 8 xor b(i+5) mod 8
xor b(i+6) mod 8 xor b(i+7) mod 8 + ci
where c = 63 hex.
As with multiplication, this is usually implemented as a table lookup.
ShiftRows Routine
This routine modifies each row of the state matrix. The top row is not changed,
the next row is rotated left one position, the following row two positions, and
the bottom row three positions.
MixColumns Routine
This function mixes up the data in each column according to the following formulas:
- Set s0,c to
2*s0,c xor 3*s1,c xor s2,c xor s3,c
- Set s1,c to
0,c xor 2*s1,c xor 3*s2,c xor s3,c
- Set s2,c to
s0,c xor s1,c xor 2*s2,c xor 3*s3,c
- Set s3,c to
3*s0,c xor s1,c xor s2,c xor 2*s3,c
AddRoundKey Routine
This function does an XOR between each column of the state and a 32-bit word from
the key schedule.
Key Expansion
The key schedule w is generated in the following form:
- The first four words (w[0] through w[3]) of the key are
the incoming cipher key.
- To calculate w[i] for i from 4 to 43:
- Set temp = w[i-1]
- If i = 4, 8, 12, 16, ..., 40 (multiples of 4)
- Rotate this word left one byte
- Replace each byte (using the same substitution
function as SubBytes)
- Do an exclusive-or with the round constant Rcon[i]
- Set w[i] = w[i-4] xor temp
AES Decryption
Decryption basically consists of performing each of the encryption steps in reverse,
using the following algorithm:
InvCipher(byte in[16], byte out[16], word w[44])])
begin
byte state[4,4]
state = in
AddRoundKey(state, w[40, 43])
for round = 9 step -1 downto 1
InvShiftRows(state)
InvSubBytes(state)
AddRoundKey(state, w[round*3, (round+1)*3-1])
InvMixColumns(state)
end for
InvShiftRows(state)
InvSubBytes(state)
AddRoundKey(state, w[0, 3])
out = state
end
Each of the Inv... functions is the inverse of the corresponding encryption
function. InvSubBytesbecomes another table lookup, and the equations for
InvMixColumns are:
- Set s0,c to
0x0e*s0,c xor 0x0b*s1,c
xor 0x0d*s2,c xor 0x09*s3,c
- Set s1,c to
0x09*s0,c xor 0x0e*s1,c
xor 0x0b*s2,c xor 0x0d*s3,c
- Set s2,c to
0x0d*s0,c xor 0x09*s1,c
xor 0x0e*s2,c xor 0x0b*s3,c
- Set s3,c to
0x0b*s0,c xor 0x0d*s1,c
xor 0x09*s2,c xor 0x0e*s3,c
The algorithm can be rewritten so it looks similar to the encryption algorithm, with a
few simple modifications.
Return to my home page
Send Mail