image

Basic cipher operations


Examining the operation of individual operations of the round, and repeating the rounds the required number of times while illustrating all the intermediate actions, and not just their final results, with a concrete example of a message and a cipher key, we observe in detail all the steps of the encryption process and can analyze the conditions under which they are realized, the results that are obtained, etc. We remember at the same time that “the devil is in the details.”

With blind access to implementations, the user does not see anything of this, does not feel it, and most importantly, does not understand how encryption occurs. It sets only the message text and key. This is all that the user understands. The user completely trusts the developer, which has repeatedly come across figures from the state level to ordinary users. This is listening to negotiations of diplomatic missions and the failure of technical systems when someone else’s communication equipment is bought and installed without looking back.
How to analyze the encryption process, what and how changes are made is not clear.

Continuing the topic of block cipher - the winner of the contest held by the US National Institute of Standards and Technology (1997 - 2000), we will consider its functioning and work. The US National Security Agency was not a participant in the contest, so the developers had great chances to become a winner.

The competitive commission pre-selected 15 applications from different countries. Both organizations and private individuals could speak. In the end, RIJNDAEL (Belgium) won by authors Vincent Rumen and Vincent Rijmen and Joan Daemen. The cipher structure is considered a classic SP network.

The main technical specifications have already been given earlier and we will not repeat them.

Message encryption


The developers created a masterpiece, for the first time the ideology and implementation of a symmetric block cipher has become completely understandable, since the cipher is completely based on elements of a classical (transparent) algebraic structure (field), with quantitative characteristics that are modest enough for viewing. The final extended field (polynomial field) of characteristic 2 has a degree of expansion n=8 and the number of elements (field order 2 8 =256), hence the designation of the field GF (2 8 ).

Selection of the irreducible polynomial of the field $ φ (x)=x ^ 8 + x ^ 4 + x ^ 3 + x + 1 $ and the primitive field element α=00000011 2 =3 10 , is also not cryptic. In a word, this is not DES or domestic GOST 28147.89.
Sources are prepared on keyboard devices using
Table - ASCII Code Symbols

ITKarma picture


Rounds and AES encryption operations


The number of cipher rounds is indicated by Nr and depends on the key length (Nr=10 for a key of 128 bits, Nr=12 for a key of 192 bits and Nr=14 for a key of 256 bits).
The AES encryption cycle (one round) consists (in changing the state of the encrypted message) of four basic operations:
1. AddRoundKey S + Ki; summation of state (source text with key)
2. SubBytes a ∙ x -1 + b; replacing summation results with other bytes
3. ShiftRows; S ∙ p (x); cyclic line shifts by different number of positions
4. MixColumns A0 ∙ S. mixing columns of the "square".

We show how this happens with a numerical example for the current state in each operation, starting from the top (zero) line. The results of the 2nd and 3rd operations do not require numerical conversions, but MixColumns is associated with the multiplication of 2 matrices and the determination of the elements of the resulting matrix requires specific calculations in the GF field (2 8 ). The key generation algorithm (Keu Schedule) generates 32-bit words, the number of which is equal to the length of the Nb block.

The first round is preceded by a preliminary (zero), in which the "squares" of the source text and the key are summarized.Let's consider each operation in more detail.

There is a animation that explains the operation of the AES cipher algorithm, round operations are very clearly demonstrated. The author did not set out to show all the details of the encryption process, but even this simplified version (at the byte level), which almost coincides with the elements of the GF field (2 8 ), successfully demonstrates the operation of the AES cipher. Detailed exposition for understanding the mathematical foundations of working with field elements and specific implementation in various representations of field elements here .

Operation AddRoundKey for the i-th round


Summing State columns with a round key (Add Round Key).

The round key, pre-computed and selected, is represented in the form of (square) State (Key). Summation is performed for columns of the same name. A pair of State (Data) and State (Key) columns is added up bitwise by the XOR operation.

Thus, the AddRoundKey transformation consists of summing the matrix S of the block (“4x4 square”) of the message in M4 (GF (2 8 )) with the partial Ki key of the ith round (also with “square 4 × 4 "). The result of the summation is denoted by SiA, i.e., the state after the ith AddRoundKey M4 (GF (2 8 )) → M4 (GF (2 8 )), S → SiA=S + Ki.
In the initial round (r=0), only Add RoundKey is performed - summing by mod2 (XOR) bytes of the data block and key block. The result of this round is used as the initial (State) state for the first round (r=1) and is presented in the "square" format.
AES Message Encryption

Example 1 . Message (source=IT) in hexadecimal representation
has the form 32 43 f6 a8 88 5a 30 8d 31 31 98 a2 e0 37 07 34,
and the cipher key is 2b 7e 15 16 28 ae d2 a6 ab f7 15 88 09 0f 4f 3c.
AddRoundKey S + Ki operation for all 16 bytes of the State squared
A preliminary round of encryption prepares the IT amount with the key.

Their Sum , represented by bytes in the "square" format with Nb=Nk=4 and Nr=10, looks like:

ITKarma picture

Drawing Result of the preliminary round (before the first)

The key and the source text (this can be sound and picture, etc.) are presented in hexadecimal. This is not the most convenient representation, so we convert it to binary vectors and perform modulo 2 addition.

ITKarma picture

For the convenience of manual calculation, the hexadecimal representation of bytes is converted to binary, and after summing, the inverse transition from binary to hexadecimal representation.

SubByte Operation for Round i


Replacing Bytes (Sub Bytes ())

The first round . The AddRoundKey operation has already been completed. All bytes of the total “square” (the initial state is denoted by dots (x, y) on some plane) are converted by the S (x, y) function to the new values, the plate " Byte replacement ".
ITKarma picture
Replace the corner (upper left) byte State= Amount , (equal to 19), byte d4 from the S-block replacement table and the next (3D) by 27 (they are highlighted). This converts all 16 bytes of the square " Amount ".

So for the first byte {19}={x, y}, x=1, y=9, S (19)=d4. All such values ​​are also represented by a “square with substitutions.”

The function S (x, y) is tabulated, i.e. it is defined by a table with two inputs - row (x) and column (y). Since the entire variety of bytes is limited to 256, the table has a size of 16 × 16=256, and its rows and columns are numbered x, y=0 (1) 15 digits of the hexadecimal number system. The view of the table S (x, y) is given below.

ITKarma picture


We show how the values ​​of this table S (x, y) are obtained. First, each byte of the initial state {x, y} is converted to inverted {x, y} -1 , to the multiplicative inverse in the GF field (2 8 ). Then the byte is multiplied by matrix A.Zero byte goes into itself {0, 0} -1 ={0, 0}.

Each row of the affine transformation matrix A contains only five units.

Then an affine transformation is applied to the inverted (inverted) byte, which is written in the vector-matrix form as follows:

ITKarma picture


Affine Matrix

Writing vectors from the top (least significant bit) down. The shift vector c={63} 16 , which is reflected in the table S (x, y) for byte {00}. Each byte of the initial state undergoes such a conversion, and their values ​​are inscribed in the square table S (x, y).

The scalar representation of the affine transformation has the following form (general form of the ith element of the result):

ITKarma picture

where $ c_0=c_1=c_5=c_6=1; c_2=c_3=c_4=c_7=0 $ ; $ b_i $,  $ b_i $ ' - respectively, the source and the converted value of the i-th bit of bytes, i=0 (1) 7.

Expression for $ b_i $' contains 6 terms, since each row of the cyclic matrix of an affine transformation has only 5 nonzero elements; the sixth term is taken from the shift vector ci.

To speed up the calculations, a square table of fixed values ​​is used (S (x, y) - block). The value b=’63 ’is a hexadecimal number belongs to GF (2 8 ) and the matrix a has the form shown earlier. In essence, the operation implements the substitution (replacement) of bytes from the S “16 × 16 square”.

The SubByte transformation consists in applying to each element of the matrix S an elementary transformation s. The result of this operation is denoted by SiSu, i.e., this is the state of the block of text after the SubByte operation of the i-th round. Do not confuse the letters S and s (large and small).

In essence, an affine transformation is performed here with a constant shift vector denoted by b
M4 (GF (2 8 )) → M4 (GF (2 8 )).

Writing vectors from the top (least significant bit) down. The shift vector c={63} 16 , which is reflected in the table S (x, y) for byte {00}. Each byte of the source text (state) undergoes such a conversion, and their values ​​are inscribed in the table S (x, y).

Example 2 . The first byte of the initial state of the first round is {19}. The multiplicative inverse for it (see Table A1) is 3f={19} -1 =0011 1111 2 113 . This value is easily found on the table of elements of the GF field (2 8 ). If there is no table of field elements, you can perform direct calculations.

Let the byte {x, y}=09=α 199 and {09} -1 =4f, then
b0=(1 + 0 + 1) mod2=0, b4=(1 + 1 + 0) mod2=0,
b1=(1 + 0 + 1) mod2=0, b5=(0 + 1 + 1) mod2=0,
b2=(1 + 0 + 0) mod2=1, b6=(0 + 1 + 1) mod2=0,
b3=(1 + 1 + 0) mod2=0, b7=(0 + 1 + 0) mod2=1.
The resulting vector (0, 1, 2, 3, 4, 5, 6, 7)=1000 0100 2 =84.

Therefore, byte 4f by the S-block is converted to byte 84, which can be seen in the substitution table S (x, y)=S (4, f)=84. This result lies at the intersection of row number 4 and column number f. The geometric representation of Subbytes is shown in Figure 4, where s is a non-linear transformation defined by the relations:
GF (2 8 ) → GF (2 8 ),

ITKarma picture

ShiftRows operation for round i


In each round, after replacing all the State bytes, a square (average) of the initial state was obtained to convert the line shift. This shift contributes to even greater data mixing.

The choice of shift values ​​is subject to the following conditions:
Each line must have an individual element offset;
The implementation of the operation should be simple;

A set of shifts should in the best way prevent attacks:

A) attacks using reduced differential | C) attacks like Square.

ITKarma picture

Figure 5 Status after a line break

ShiftRows transformation is the movement of row bytes in the state matrix S, which cyclically shifts the rows of the state matrix by different offsets. The result of the operation is denoted by SiSh, that is, this state after the ShiftRows operation
i-round. Such movements can be described by P (x) by rearrangement of bytes from the "square" S, which has the form:

ITKarma picture

Of all the shift options that provide the best resistance to attacks, the simplest one was chosen - a cyclic shift and c0=0.

A geometric representation of the byte replacement transform is shown in Figure 4, which shows the squares of a numerical example for the first round.

The shift of lines in the State array is performed to the left. Line number zero remains fixed (does not shift). The remaining RIJNDAEL lines are shifted by the number of bytes c1, c2, c3 indicated in the square in Figure 5), depending on the number of Nb bytes in the data block. Line 1 is shifted by c1 bytes, line 2 by c2 bytes and line 3 by c3 bytes.

In the AES standard, Nb=128 is constant, therefore always c1=1, c2=2 and c3=3.

Shift Value Table

ITKarma picture


MixColumns operation for round i


This transformation is used to provide dispersion of the characters of the original message, to satisfy the second after mixing requirements for encryption transformations. The requirements for such a transformation presented by the theory of synthesis of ciphers are as follows.

  • The reversibility of the result.
  • Linearity in the GF field (2 8 ); compliance with this requirement creates the conditions for the use of direct decryption algorithm.
  • Strong enough data scatter.
  • High speed implementation on 8-bit processors; uniformity of processing of any data blocks, i.e. symmetry.
  • Simple view for description and implementation.

All of these requirements are satisfied in the AES standard. Of the possible linear transformations 4 bytes → 4 bytes, the operation of multiplying polynomials (field elements) modulo ψ (x)=x 4 + 1 was selected. The choice of the coefficients of the factors is determined by the requirements 1, 3, and 4. Coefficients {00 }, {01}, {02}, {03},... correspond: {00} - to the lack of conversion; {01} - no multiplication required; {02} - multiplication when using the x time () function and {03} - when using x time and the subsequent addition of intermediate results by mod2.

According to other, equally important reports, the choice of coefficients was stopped at the above values.

The essence of the Mix Columns () transformation is as follows. State Columns
S=& lt; S0c, S1c, S2c, S3c & gt ;, c=0 (1) 3, after the line shift are considered as elements of the field GF (2 8 ) and are multiplied by mod (x 4 + 1) on a fixed polynomial g (x):
g (x)={03} x 3 + {0,1} x 2 + {01} x + {02}.

ITKarma picture

where c is the State column number, c=0 (1) 3.

where A is a circulant matrix, i.e., a linear invertible (invertible) map onto GF (2 8 ), A belongs to M8 (GF (2 8 )),
× - denotes the multiplication of the matrix of GF (2 8 ) and the vector
x -1={b0 b1... b7} b, which is considered as an element over the field GF (2) - a vector space equivalent to transposed into the vector {b0 b1... b7} b.

Expand this expression in scalar form
S’0C=({02} · S0C) ⊕ ({03} · S1C) ⊕ S2C ⊕ S3C;
S’1C=S0C ⊕ ({02} · S1C) ⊕ ({03} · S2C) ⊕ S3C;
S’2C=S0C ⊕ S1C ⊕ ({02} · S2C) ⊕ ({03} · S3C);
S’3C=({03} · S0C) ⊕ S1C ⊕ S2C ⊕ ({02} · S3C).
As a result of these actions, the bytes of the vector
SC=& lt; S0c, S1c, S2c, S3c > will be replaced with bytes S’0C, S’1C, S’2C, S’3C.

MixColumns transformation consists of multiplication of two matrices. The matrices S of the intermediate state of the text and the fixed matrix A0 are both from the previously introduced set M4 (GF (2 8 )). The result of the operation is indicated by the symbol SiM, this is essentially the state S after the MixColumns operation of the i-th round.

M4 (GF (2 8 )) → M4 (GF (2 8 )),
S → Si, M=A · S,
where matrices A and A -1 (circulant matrices) are defined as:

ITKarma picture
.
Operation MixColumns - the product of a special cyclic A0 matrix by the State matrix, according to the “row by column” rule

ITKarma picture
.
Two empty columns in the resulting matrix are left for self-filling.
Start with the left corner element of the zero row of the square. Its value is determined by the sum of the products of pairs of elements: {02} D4⊕ {03} BF ⊕ {01} 5D ⊕ {01} 30. Elements of both matrices are elements of the GF field (2 8 ) on the one hand and information bytes in hexadecimal notation on the other. Multiplication of elements in a field is conveniently performed in a power-law representation of a primitive element.

Using the field table, we replace the hexadecimal representation with the power law for the left cyclic matrix, the elements {01}=a 0 , {02}=a 25 , {03}=a 1 . For the right matrix in the product we get

ITKarma picture

Now we can rewrite the sum for the corner element and the rest in the line through the degrees of the primitive element of the extended field, we place the terms in the columns of the table.
The summation results are placed in the last row of the table for each row of the matrix of mixed columns.

The 1st element of the zero line is defined as:

{02} D4⊕ {03} BF ⊕ {01} 5D ⊕ {01} 30=a 25 and 65 ⊕ a 1 a 157 ⊕ a 0 a 136 ⊕ a 0 a 101 =a 90 ⊕ a 158 ⊕a 136 ⊕a 101 ,

The 2nd element of the zero row is determined by a similar relation (the column has changed)

{02} E0⊕ {03} B4⊕ {01} 52⊕ {01} AE=a 25 and 68 ⊕ a 1 a 251 ⊕ a 0 a 253 ⊕ a 0 a 123 =a 93 ⊕ a 252 ⊕ a 253 ⊕a 123 ,

The 3rd element of the zero row is determined by a similar ratio the column has changed

{02} B8⊕ {03} 41⊕ {01} 11⊕ {01} F1=a 25 and 59 ⊕ a 1 a 143 ⊕ a 0 a 4 ⊕ a 0 a 74 =a 84 ⊕ a 144 ⊕ a 4 ⊕ a 74 ,

The 4th element of the zero row is determined by a similar ratio the column has changed

{02} 1E⊕ {03} 27⊕ {01} 98⊕ {01} E5=a 25 and 28 ⊕ a 1 a 106 ⊕ a 0 a 89 ⊕ a 0 a 32 =a 53 ⊕a 107 ⊕ and 89 ⊕a 32 .

The exponents are simply summed up as multiplications as logarithms. It is convenient to summarize the terms by returning to the hexadecimal, and from it to the binary representation. We will again use the table of elements of the GF field (2 8 ).

ITKarma picture

Let's move on to the calculation of the elements of the 1st row of the matrix (the row number of the cyclic matrix changes). The elements in pairs of products change relative to the 0th row.

The 1st element of the 1st row of the matrix of mixed columns is determined by the relation.

ITKarma picture

We proceed to the calculation of the elements of the 2nd row of the matrix (the row number of the cyclic matrix changes). Elements in pairs of works change relative to the 1st row.

The 1st element of the 2nd row of the matrix of mixed columns is determined by the relation

ITKarma picture

Let's move on to the calculation of the elements of the 3rd row of the matrix (the row number of the cyclic matrix changes). The elements in the pairs of products change relative to the 2nd row.

ITKarma picture
.

Source