image

The motive for the publication of such detailed texts about the AES standard is the provision of the opportunity to familiarize yourself with it in details sufficient not only to develop an independent software implementation of the encryption algorithm, but also to create algorithms for possible cryptanalytic attacks on the cipher, i.e., to decrypt ciphers without knowing the key.

Those publications that are available on the network do not meet these goals and cannot be used by me in the process of training specialists.

One of the main old (or even old) requirements for ciphers is to create an open (accessible for study) encryption and encryption algorithm around it (modes, protocols, etc.) everything except the cipher key. The key is that which must be kept in the strictest confidence from everyone. However, the key does not necessarily have the "Secret" signature stamp. The limit of such a condition is only the recipient of the ciphergram owns the key, he himself, in principle, must establish it.

For symmetric encryption systems, this condition is not feasible. And this is the fundamental difference between asymmetric (two-key) systems from symmetric ones, in which the source of key information leakage may not be the only one. It was previously noted that AES is a simplified version of the RIJNDAEL cipher, but here we will use the full version in some places.

Algorithm for generating AES cipher keys (Key Schedule). General Provisions and Principle


Choosing a key when encrypting a message is a responsible task. The general approach is that a random binary vector is selected and used for the key in a multidimensional vector space. Often, a number of encryption algorithms and ciphers are characterized by the presence of weak or invalid keys, which are identified either during the development of ciphers or during their operation during additional research algorithms by authors or cryptographers, analysts and, accordingly, publications about it.

In turn, this imposes restrictions on the key generation procedure, which is undesirable as it complicates it. The mathematical foundations regarding encryption are very similar to the mathematical foundations for generating keys, and you can read more about them here .

The selected binary vector is called the cipher key and it is converted into a “square” of 4 × 4=16 bytes. Next, round keys are formed from it using two special procedures, which are used in the encryption/decryption processes, which are described in detail here .

One procedure is called Key Expansion, and the other is called Round Key Selection. The selected random random vector with a fixed length is expanded. It is also important to carefully consider the choice of a random number sensor, conduct its testing and testing.

Key extension


The meaning of expanding the original (selected) key is to split it into non blocks (32 bits each) and then generate from them many new blocks of the same length for each round.
So, let the cipher key be selected (128 bits) AES=2b 7e 15 16 28 ae d2 a6 ab f7 15 88 09 cf 4f 3c, for Nk=4, which is represented by blocks of 4 bytes and its initial round extension has the form w [0 ]=2b7e1516; w [1]=28aed2a6; w [2]=abf71588; w [3]=09cf4f3c. The w [i] symbol in the QC table, i=0 (1) 43, denotes a column of 4 bytes of the round key.

An encryption session is the preparation and algorithmic transformation of a message, such as a letter. The text of the letter in the bit representation is divided into blocks of fixed length Nb=128, 192 or 256 bits. In AES, the block length is only 128 bits.

Then each block is represented by a square or (rectangle with 4 lines) and is encrypted separately for a fixed number of rounds Nr=Nr (Nb, Nk), which is a function of two variables: the length of the block Nb and the length of the key Nk, which can independently take values 128, 192, 256 bits.

Choosing an encryption key does not impose any restrictions on the bit sequence itself.Each of the Nr rounds uses its own pre-formed, or directly calculated, round key {w [i]}.

Round keys are generated from the encryption key using a special algorithm, which includes the Key Expansion procedure and the Round Key Selection procedure. Setting round keys directly bypassing these procedures is unacceptable.

The essence and purpose of the first procedure is to convert the specified source encryption key into a longer, extended key (Expanded Key). The total number of bits of the extended key from which round keys are selected is determined by the product K=Nk (Nr + 1) - the number of bits of the key block is multiplied by the number of rounds increased by one.

Example 1 . Let Nb=Nk=4, given blocks with a length of 4 × 32=128 bits, then Nr=10.
The length K in bits for the extended key is K=128 ∙ 11=1408 bits.

The second procedure (RoundKey Selection) is a sequential selection of 32Nk, i.e., 4 32-bit words from the extended key, i.e. the first round key is represented by the initial newly formed Nk words, the second round key by the following Nk words and so on until the last round.

Example 2 . With the same initial data (see the previous example), the total length of the extended key in bytes contains Nk (Nr + 1)=4 ∙ 11=44 four-byte words W (i),
i=0 (1) Nk (Nr + 1) - 1. The rows of the KK table are numbered by natural numbers. The first row has number 4, since 4 rows (with numbers 0,1,2,3) with a cipher key are not included in the QC table.

Table AES cipher key for all 10 rounds (see QC table below).

ITKarma picture

ITKarma picture

Rows of the table are divided into groups (4 rows each). In each group, only one top line is filled in all the fields. In the next three lines, only the extreme (left and right) fields are filled. The left field ( temp ) of the next and two subsequent lines contains the values ​​taken from the right field of the line above it.

We give an example of filling the first row with the number i=4 of the QC table. Left column - the current line numbers begin with the value (4) since the first 0,1,2,3 values ​​are not included in the table. In general, the index (line number) i runs through the values ​​i=0 (1) Nk (Nr + 1) -1 or i=0 (1) 43 in total 44 words out of 32 digits.

In the temp column, the value w [i-1]=09cf4f3c is placed and by rotation (cyclic shift of one byte) RotWord () we get the value CF4F3C09, which is placed in the 3rd column. The 4th column contains the result of 8A84EB01 replacing bytes of SubBytes of values ​​from the 3rd column, i.e. CF → 8A; 4F → 84; 3C → EB; 09 → 01=> 8A84EV01.

Each 4th row of the table in the 5th column is filled with the value Rcon [i/Nk], a constant calculated by the formula Rcon (J)=01000000, j=[i/Nk]=2 j-1 =2 0 =1) the value 01 00 00 00 is written out of 4 byte words, the first byte of which is 2 0 =1, i.e. 0000 0001 2 , the remaining bytes of this 32-bit word are zero.

Column 6 field contains the sum (XOR) of fields 4 and 5 of 8А84EB01 + 01000000=8B84EB01;
Column 7 field contains W [i - Nk]=W [4 - 4]=W [0]=2B7E1516;
Column 8 field contains the sum of the fields of columns 6 and 7 W [i=4]=8А84EB01 + 2B7E1516=A0FAFE17;
Now, we’ll take a closer look at the named procedures in detail and details.

Key Expansion Procedure


Let us consider in detail the procedure for generating an Expanded Key from the original cipher key. The formally expanded key W will be described by the sequence of blocks W [i], i=0 (1) Nk (Nr + 1) -1, 4-byte words (round keys) contained in the last column of the KK table, in which the first Nk are 32-bit words represent the original key, i.e.
W={W [0], W [1], W [2], W [3], W [4],..., W [K-1]}

Subsequent i-th words are formed recursively from previous words in accordance with the expression in which the summation is XOR.

ITKarma picture.

For the key words W [i] whose index is a multiple of Nk, the values ​​of W [i-1] are subjected to additional conversion before performing the XOR operation. This conversion is described as follows.

Description of conversion contains functions:

RotWord () - byte cyclic shift of the 32-bit word a (0) a (1) a (2) a (3) by the rule
{a (0) a (1) a (2) a (3)} → {a (3) a (0) a (1) a (2)};

SubWord () - byte replacement of a (j) with elements of the S-block of the SubBytes () function, for example, byte (a f) is replaced with byte s (a, f) from the S-block; action similar to message processing,
Rcon [j] - the XOR term is 2 j-1 .

ITKarma picture

Multiples of Nb are selected, the values ​​of which are formed using the functions SubWord (), RotWord (), Rcon (). Positions W [0] –W [3] are filled in according to the given initial data, all subsequent ones are calculated by the ratio for W [i].

Round Key Selection


Selection of a round key (RoundKeySelection). For the current round with the number r. The round key is selected as {W [Nb (r) -1],..., W [Nb (r + 1) - 1]},
r=1 (1) Nr.

Here we note that the general encryption algorithm provides for different options for sets of variables Nb, Nk, Nr. For a specific implementation of the fixed option, it can be greatly simplified. The round key can be calculated on the fly, which does not require large memory to store the entire sequence W. You can limit yourself to a buffer of Nk words.

Example 3 . Let us explain the above theoretical propositions by a numerical example. Let, as before, Nb=Nk=4, Nr=10. The cipher key is given in the form of a hexadecimal sequence K=2b7e1516 282ed2a6 abf71588 09cf4f3c

ITKarma picture


The “square” architecture and byte-oriented computing determine the form of their presentation in the following table.

ITKarma picture

Left column is added to the table - number (r) of the round
In the first line r=1, i=4, the previous byte W [i-1]=W [3] is written in the third column; the last byte of the K cipher key. Since the index i=4 is a multiple of Nk=4, then in column 6 we write (Rcon (J)=01000000, j=[i/Nk]=2 j-1 =2 0 =1) the value 01 00 00 00 of a 4-byte word is written, the first byte of which is 2 0 =1, i.e. 0000 0001, the remaining bytes of this 32-bit word are zero.

In the fourth column of the table, we enter the values ​​from the previous column, but cyclically shifted by 1 byte to the left (word rotation - RotWord). The fifth column contains the result of a byte replacement of the values ​​of the previous column with the byte values ​​from the S - block (SubWord function - byte replacement). After that, mod2 (XOR) addition is performed on the contents of columns 5 and 6, 8a84eb01 + 0100 0000=8b84eb01, and the summation is entered in column 7.

In the binary representation of the byte 0000 0001 2 =01 16 the least significant bits are located on the right.

Column 8 contains the value of the word W [i-Nk]=W [0] (for the first line, this is the value of the first (left byte) 4-byte word of the encryption key W [0]), which is added by the XOR operation 8b 84 eb 01+ 2b 7e 15 16=a0 fa fe 17 with contents of 7 columns. The result of the summation (column 9) is precisely the first of the four, 4-byte words of the round key of the first round.

The other three words of the round key of the first round are formed without using the cyclic shift, replace, and Rcon [j] functions, since their numbers are not multiples of Nk. The contents of column 9 are transferred to the third column of the next row of the table.

Definition of Rcon [j]. This procedure is performed according to a special algorithm, the actions of which we will illustrate with examples. The argument j of the function Rcon [j] is integer and is determined by the current value of the variable i, the key word number. Obviously
j=1, 2, 3,... for i=Nk, 2Nk, 3Nk,....

Since Nk in our example is 4, we have integer values ​​j for i=4, 8, 12. Further, for each integer j Rcon [j]=2 j-1 =1, 2, 4, 8, 16,....
Doubling values ​​is valid as long as Rcon [j] is an element of the GF field (2 8 ).

For i > 32 we get j > 8. Values ​​outside the field must be returned to the field. This is achieved by reducing the polynomial representation of the elements of the field Rcon [j] (modφ (x)).

Example 4 . Let i=32, 36, 40. Then j=8, 9, 10. These values ​​are outside the field. We return them to the field by reduction modulo φ (x) and calculate the required values.
We define the corresponding values ​​of Rcon [j]. The results of the calculations are tabulated.

ITKarma picture

This can complete the consideration of the steps for generating round AES cipher keys.

Source