Crypto-IT

• Block length = 128 bits
• Key length = 128 or 192 or 256 bits

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.

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.

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 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:

• A 128-bit key (16 bytes) is expanded to 176 bytes.
• A 192-bit key (24 bytes) is expanded to 208 bytes.
• A 256-bit key (32 bytes) is expanded to 240 bytes.

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.

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.

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.

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.

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

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

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.

During decryption, an inverted matrix is used for multiplication:

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: