ου γαρ εστιν κρυπτον ο ου φανερον γενησεται ουδε αποκρυφον ο ου γνωσθησεται και εις φανερον ελθη
Wersja PL ENG Version

AES (Advanced Encryption Standard)

  • Description
  • Algorithm
  • Block diagrams
  • Mathematical functions
  • Implementation
AES is a modern block symmetric cipher, one of the most popular ciphers in the world. It was developed in 1997 by Vincent Rijmen and Joan Daemen, and later approved as a federal encryption standard in the United States in 2002.
Block cipher with symmetric secret key
Block length = 128 bits
Key length = 128 or 192 or 256 bits
AES is considered as a strong and secure cipher. Over last few years (mostly 2005-2010) several attacks against different AES implementations were described but generally speaking they concern just some special cases and are not considered to be a threat to the AES algorithm itself.

A secret key in AES, for both data encryption and decryption, may contain 128 or 192 or 256 bits. Based on the length of the key, a different number of encrypting cycles is performed.

AES Encryption

During encryption, the input data (plaintext) is divided into 128-bit blocks. The blocks of data are presented as column-major matrices of size 4 bytes × 4 bytes, called states. The following operations are performed for all blocks:

  1. Preparing Subkeys: one starting subkey is created first, and later one more subkey for every subsequent cycle of encryption (see below).
  2. Initial Round: all bytes of data block are added to corresponding bytes of the starting subkey using XOR operation.
  3. A number of encrypting cycles takes place. The number of repetition depends on the length of a secret key:
    -  9 cycles of repetition for a 128-bit key,
    - 11 cycles of repetition for a 192-bit key,
    - 13 cycles of repetition for a 256-bit key.

    The following operations are performed during each encryption round:
    1. Each byte of the state matrix is replaced with another byte, based on a lookup table, called Rijndael's S-Box. The operation is called the SB (Substitute Bytes) Operation. The construction of the lookup table guarantees that this substitution is non-linear.
    2. The bytes stored in the last three rows of the state matrix are shifted to the left. Note, that the bytes in the first row are not shifted at all. The bytes in the second row are shifted by one position, in the third row by two positions, and the bytes in the fourth row are shifted by three positions to the left. The leftmost bytes in each row moves to the right side of the same row. This state is called SR (Shift Rows) Operation.
    3. MC (Mix Columns) Operation (the multiplication of columns): all columns are multiplied with a constant matrix of size 4 bytes × 4 bytes.
    4. AR (Add Round Key) Operation: adding XOR all state bytes to the subkey bytes. A new subkey is created for every encryption round. Subkeys, like states, are 16-byte long.
  4. Final Round: the same operations are performed as in normal encryption rounds (described above), besides the multiplication of columns, which in the Final Round is omitted.

AES Key Expansion

AES uses a secret symmetric key, which contains 128, 192, or 256 bits (that is 16, 24, or 32 bytes respectively). In order to encrypt all data blocks, the key must be expanded. The new bytes are appended to the original bytes of the key:

The first bytes of the expanded key are all bytes of the original secret key. In order to create succeeding bytes of the expanded key, the following steps must be performed, with iterations numbered from 1. Steps below should be repeated until receiving a desirable number of bytes. To simplify the notation, the length (in bytes) of the original secret key (before expansion) will be denoted as n.

  1. Creating next 4 bytes of the key:
    1. Copying 4 last bytes of the current key to a temporary 4-byte vector.
    2. Shifting those four bytes to the left by one position. The leftmost byte should move to the rightmost position.
    3. Each byte in the vector should be replaced by another one, based on Rijndael's S-Boxes.
    4. Rcon Operation: adding XOR the leftmost byte in the vector to a number 2 raised to the power number equal to (number of current iteration - 1).
    5. Adding XOR the received 4-byte vector to a 4-byte block starting n bytes before the current end of the expanded key and appending the result to the end of the expanded key. At this point, four new key bytes have been created.
  2. Creating next 12 bytes of the key by performing the following steps three times:
    1. Copying 4 last bytes of the current key to a temporary 4-byte vector.
    2. Adding XOR the 4-byte vector to a 4-byte block starting n bytes before the current end of the expanded key and appending the result to the end of the expanded key.
  3. If the original key is 256 bits long, the following steps should be performed once in order to create 4 new key bytes:
    1. Copying 4 last bytes of the current key to a temporary 4-byte vector.
    2. Each byte in the vector should be replaced by another one, based on Rijndael's S-Boxes.
    3. Adding XOR the 4-byte vector to a 4-byte block starting n bytes before the current end of the expanded key and appending the result to the end of the expanded key.
  4. If the original key is 128 bits long, the following steps should be omitted. If the original key is 192 bits long, the following steps should be performed twice. If the original key is 256 bits long, the following steps should be repeated three times:
    1. Copying 4 last bytes of the current key to a temporary 4-byte vector.
    2. Adding XOR the 4-byte vector to a 4-byte block starting n bytes before the current end of the expanded key and appending the result to the end of the expanded key.
  5. Increasing the number of iterations by 1.

AES Decryption

During decryption, the encrypted text is used as input data to the algorithm. The corresponding, inverse operations should be performed, as during encryption:

  1. Inverse bytes substitution (ISB).
  2. Bytes shifting to the right (ISR).
  3. Adding XOR to a subkey (IAR).
  4. Inverse multiplication of columns (IMC).

Subkeys for each iteration should be taken in the reverse order than during encryption.

AES Performance

In order to accelerate the application, one can decide to pre-compute the functions in different rounds and replace them by simple byte substitution based on the calculated tables.

The disadvantage of this approach is that the size of the application will be much larger. It may increase from several to tens of kilobytes, depending on the size of the secret key that is used.

In all AES operations presented below, the bytes are written in a hexadecimal notation. Each character represents four bits.
Substitution in Rijndael S-Box
In Rijndael S-Boxes every input byte is replaced by another byte. Values in S-Boxes were chosen in a way, that provides a maximum non-linearity of this transformation. Thanks to that, the whole AES encryption is non-linear.

The byte substitutions are presented in a table below. In the rows, there are specified the more significant halves of input bytes. In the columns, there are the less significant halves of input bytes. The value of the output byte may be found inside the table, at the intersection of the specified row and the column.

Rijndael S-Box
x0
x1
x2
x3
x4
x5
x6
x7
x8
x9
xA
xB
xC
xD
xE
xF
0x
637c777bf26b6fc53001672bfed7ab76
1x
ca82c97dfa5947f0add4a2af9ca472c0
2x
b7fd9326363ff7cc34a5e5f171d83115
3x
04c723c31896059a071280e2eb27b275
4x
09832c1a1b6e5aa0523bd6b329e32f84
5x
53d100ed20fcb15b6acbbe394a4c58cf
6x
d0efaafb434d338545f9027f503c9fa8
7x
51a3408f929d38f5bcb6da2110fff3d2
8x
cd0c13ec5f974417c4a77e3d645d1973
9x
60814fdc222a908846eeb814de5e0bdb
Ax
e0323a0a4906245cc2d3ac629195e479
Bx
e7c8376d8dd54ea96c56f4ea657aae08
Cx
ba78252e1ca6b4c6e8dd741f4bbd8b8a
Dx
703eb5664803f60e6 13557b986c11d9e
Ex
e1f8981169d98e949b1e87e9ce5528df
Fx
8ca1890dbfe6426841992d0fb054bb16

For example, for an input byte 3F, the new output byte is i75.

For decryption, the Inverse Rijndael S-Boxes are used. They can be obtained from the original Rijndael S-Boxes.

Inverse Rijndael S-Box
x0
x1
x2
x3
x4
x5
x6
x7
x8
x9
xA
xB
xC
xD
xE
xF
0x
52096ad53036a538bf40a39e81f3d7fb
1x
7ce339829b2fff87348e4344c4dee9cb
2x
547b9432a6c2233dee4c950b42fac34e
3x
082ea16628d924b2765ba2496d8bd125
4x
72f8f66486689816d4a45ccc5d65b692
5x
6c704850fdedb9da5e154657a78d9d84
6x
90d8ab008cbcd30af7e45805b8b34506
7x
d02c1e8fca3f0f02c1afbd0301138a6b
8x
3a9111414f67dcea97f2cfcef0b4e673
9x
96ac7422e7ad3585e2f937e81c75df6e
Ax
47f11a711d29c5896fb7620eaa18be1b
Bx
fc563e4bc6d279209adbc0fe78cd5af4
Cx
1fdda8338807c731b11210592780ec5f
Dx
60517fa919b54a0d2de57a9f93c99cef
Ex
a0e03b4dae2af5b0c8ebbb3c83539961
Fx
172b047eba77d626e169146355210c7d
Multiplication of columns
Each column of a state matrix is multiplied by a predefined matrix of size of 4bytes x 4bytes. The result of each multiplication is a new column which contains different 4 bytes.

Multiplication of the square matrix with the column c results in creating a new column r, with new values.

Multiplication of columns
 x 
 c0 
 c1 
 c2 
 c3 
 = 
 r0 
 r1 
 r2 
 r3 

During decryption, an inverted matrix is used during this step:

Inverted matrix
Rcon Operation
In each iteration of the key generation process, the first byte of the current 4-byte long temporary vector is added XOR to 2 raised to the power of number one less than the current iteration number. The Rcon operation is performed in Rijndael's finite field.

These values can be calculated in runtime or stored in a table in the application memory.

Powers of x = 0x02
i01234567891011121314
xi01020408102040801b366cd8ab4d9a
Site under development.