image

This publication is caused by the need to enable students to study and model the encryption/decryption and decryption processes of the latest US standard. Familiarization with existing publications on the network does not correspond to the training program due to their superficial approach, incompleteness of presentation, and lack of proper rigor. For example, the choice and task of the primitive element that forms the field is not found anywhere, without which it is impossible to organize and simulate the work and training of a specialist, especially cryptanalytic phenomena and processes. This work uses a description slightly different from the original AES presented by FIPS PUB 197. The AES cipher is described here using matrices over GF (2 8 ), but the notes of the work are preserved, that is, the cipher is implemented over the final extended GF field (2 8 ). In Russian, a sufficiently complete and accessible version of the cipher is set out Zenzin O.S. and Ivanov M.A.

Mathematical Foundations of US AES Encryption Standard


AES is a block cipher with a block length of 128 bits, and the cipher supports keys of length $ N_к $ , equal to 128, 192 or 256 bits. AES is an iterative key cipher: consists of re-applying the round state transformation of the State block of encrypted text. The number of cipher rounds is indicated by $ N_r $depends on key lengths ( $ N_r=10 $for 128-bit key, $ N_r=12 $for the key is 192 bits and $ N_r=14 $for a 256-bit key).

The AES cipher transforms the initial state of the block, denoted by the symbol S (State) and belonging to the set of matrices {M4 (GF (2 8 ))} (that is, S є {M4 (GF (2 8 ))} is a 4 × 4 byte matrix, with its elements (coefficients) in GF (2 8 )), to another encrypted state in {M4 (GF (2 8 ))}.

Example 1 . A data block with a length of 128=4 · 32, 4 words of 32 bits is represented by a square table of bytes of 4 rows and 4 columns. Each row contains bytes from 4 different 32-bit words, and the column contains bytes of the same 32-bit word. The whole square is formed by 4 × 4=16 bytes, which can be processed as independent units.

It is this approach to data presentation that defines and provides a byte-oriented cipher structure and data processing. The cipher key K extends to $ N_r + 1 $subkeys denoted by the matrix Ki={M4 (GF (2 8 ))} belonging to the set {M4 (GF (2 8 ))}, (i=0, 1,., Nr). The permutation of the elements in the matrix S that arises during the row shift operation is indicated by the symbol p (x).

Data view selected for GF field elements (2 8 )


The AES cipher uses a byte data structure. The representation selected in [1] from the vector space GF (2 8 ) corresponding to the field GF (2 8 ) [X]/& lt; φ (x) & gt ;, where φ (x) is an irreducible polynomial,

$ φ (x)=x ^ 8 + x ^ 4 + x ^ 3 + x + 1 $

. For convenience and a better understanding of the material being studied, and to clarify the details of performing calculations with a pencil in hand, numerous numerical examples and the following table 1 are given below.

Table 1.Matching decimal, hexadecimal, binary numbers and polynomials
ITKarma picture
Four representations are used in this paper to denote each element of the extended field in GF (2 8 ), which are equivalent to one another.

Representation of data used in AES cipher


Choose a decimal integer whose equivalent we will represent
various forms in other number systems:

1. 212 10 , decimal - a number in the 10th number system.

2. {11010100} b, the representation of message elements by a binary vector - an element of the vector space GF (2 8 ) of binary vectors,

3. $ x ^ 7 + x ^ 6 + x ^ 4 + x ^ 2 $ , the polynomial representation is an element of the Galois field GF [2 8 ] corresponding to the binary vector,

4. {D4} 16 , - hexadecimal representation - by a number in the 16-number system,

⊕ - operation of bitwise summation of vectors from GF (2 8 ) to mod2 (without transferring 1 to the high order).
⊗ - operation of multiplication of elements (vectors, polynomials, numbers) from the field GF (2 8 )

The algorithm of the AES standard and the RIJNDAEL cipher operates with bytes of information that are identified with the elements of the final Galois field GF (2 8 ). The degree of expansion of a simple field GF (2) is 8. All elements of an extended field, when represented by polynomials, have an exponent of not more than seven (≤ 7).

This situation is achieved by bringing all the results of actions with field elements modulo an irreducible polynomial of degree 8, which is the forming polynomial for this field. In addition to the irreducible polynomial for constructing the field, you must specify a primitive element.

In the algorithm under consideration, the primitive element is specified (its order must be equal to the order of the multiplicative group of the field), and the polynomial is fixed and has the form φ (x). Without these characteristics, working with the standard will not work

$ φ (x)=x ^ 8 + x ^ 4 + x ^ 3 + x + 1 $

or 1 {1b} in hexadecimal.
The hexadecimal notation for the irreducible polynomial 1 {1b} uses 9 digits and the polynomial φ (x) does not belong to the field GF (2 8 ).
Table P1 of the presentation of the elements of the GF field (2 8 ) (at the end of the text in the Appendix).
Table A1 contains all the elements of the field in ascending order of the exponent of the primitive element (α=00000011 2 =3 10 ), the multiplicative order of which is 255.

Consider examples of performing arithmetic operations on field elements with various representations of these elements. Any byte of the source text (field element) can be formally represented by a character string $ a_i, i=0 (1) 7 $ , binary vector coefficients in the form:

$ {a_7, a_6, a_5, a_4, a_3, a_2, a_1, a_2, a_2, a_0}, a_i∊GF (2), i=0 (1) 7. $


Example 2 .The GF extended field element (2 8 ) is specified as a binary vector:

$ {a_7, a_6, a_5, a_4, a_3, a_2, a_2, a_2,, a_0}, a_i∊GF (2), i=0 (1) 7 $


The description by the polynomial of this element has the form:

$ (x)=a_7 x ^ 7 + a_6 x ^ 6 + a_5 x ^ 5 + a_4x ^ 4 + a_3 x ^ 3 + a_2 x ^ 2 + a_1 x ^ 1 + a_0 x ^ 0 $


If you override the values ​​of ai with binary values, i=0 (1) 7, for example, like so  $ {a_7, a_6, a_5, a_4, a_3, a_2, a_1, a_0} $ ={11000001} 2 , then we get the polynomial

$ α (x)=x ^ 7 + x ^ 6 +1, $

since  $ a_5=a_4=a_3=a_2=a_1=0. $

The hexadecimal representation of this element is α 16 ={c1}={11000001}, and the decimal

α 10 = $ 2 ^ 7 + 2 ^ 6 + 2 ^ 0 $ =128 + 64 + 1=193 10 .

With a primitive field element selected, a power law
α i ={c1}=α 178 .
We enter the table P1 of the elements of the GF field (2 8 ) with the value α 178 and in the corresponding columns for this row we find the described representations, as well as other characteristics of this field element. To understand the possible transformations with field elements, consider the operations with its elements in detail.

Summing GF Field Elements (2 8 )


Addition in the field under consideration represents the operation of bitwise summation of the values ​​of the bits of the terms without transferring the unit to the highest rank. This exclusive XOR operation (EXOR - EXLUSIV OR) is often denoted simply by XOR. In modular arithmetic, this addition is called summation modulo two (mod2).

Example 3 . We choose polynomials as operands
$ A (x)=x ^ 7 + x ^ 6 + 1; $
$ B (x)=x ^ 3 + x ^ 2 + x ^ 0. $
The binary representation of the sum of polynomials modulo two has the form
[A (x) ⊕B (x)] mod2={11000001} ⊕ {00001101}={11001100};

Hexadecimal representation {c1} ⊕ {0D}={cc} sub > 16=α 55 ;
power representation α 178 + α 238 55 · {α 123 + α 183 }=α 55 · 1=α 55 .

Representation by polynomials
$ (x ^ 7 + x ^ 6 + 1) ⊕ (x ^ 3 + x ^ 2 + 1) (mod2)=(x ^ 7 + x ^ 6 + x ^ 3 + x ^ 2 + 2) (mod2)=x ^ 7 + x ^ 6 + x ^ 3 + x ^ 2. $
Note that when adding operands, the degree of the polynomial of the result is not
increases, and the need to bring it modulo an irreducible polynomial of the field φ (x) does not arise. The coefficients of the result are given modulo two, i.e., all even coefficients vanish.

In the characteristic fields 2, the operations of addition and subtraction of operands are equivalent. For each element of the field in the additive group, he is the inverse to it (opposite). So, for element (a), the opposite is (-a), since a + (-a)=0. The zero element (unit of the field addition group, neutral element) in hexadecimal is {00} 16 .

Multiplication of GF field elements (2 8 )


The operation of the usual operand multiplication (in contrast to the modular ⊗) is indicated by a dot between the operands, or the multiplication sign is generally omitted when there is no danger of misreading. The operands in binary representation are multiplied according to the usual rules by a “column”. We will multiply the same operands as before.

Example 4. Multiplication of operands in binary representation
A (x) · B (x)={c1} · {0d}
ITKarma picture
The remainder of division gets the form of binary, polynomial and hexadecimal representations (as an element of a field)
R (x)=01011 1010 2 = $ x ^ 7 + x ^ 5 + x ^ 4 + x ^ 3 + x $ ={ba} 16 . The leading digit of the remainder is zero and is not taken into account.
We do not give a power representation here, but it can be found from Table A1.

The remainder of dividing by the irreducible polynomial φ (x) in its binary representation of the result of multiplying the operands is taken as the product of the operands as elements of the field GF (2 8 ).

Multiply the operands in the representation with polynomials.

Example 5 . Multiplication of operands of field elements in polynomial representation
A (x) ⊗ B (x)={c1} ⊗ {0d}
A (x) ⊗ B (x)= $ (x ^ 7 + x ^ 6+ 1) ⊗ (x ^ 3 + x ^ 2 + 1) $ (moddφ (x), 2)=
=(x 10 + $ x ^ 9 + x ^ 9 + x ^ 8 + x ^ 7 + x ^ 6 + x ^ 3 + x ^ 2 + 1) $ (moddφ (x), 2)=
=(x 10 + $ x ^ 8 + x ^ 7 + x ^ 6 + x ^ 3 + x ^ 2 + 1) $ (moddφ (x), 2).

Here, the symbol (moddφ (x), 2) denotes a cast modulo a double module: the polynomial modulo φ (x), and its coefficients modulo two, i.e. even odds are nullified. The resulting degree (deg (A (x) ⊗ B (x))=10) of the product result takes (this polynomial is the result) out of the field. In order for the result to belong to a field, it is brought (reduced, divided) modulo an irreducible polynomial. Perform this division in the usual way (corner)

Example 6 . The need for polynomial division arises when
multiplying them A (x) ⊗B (x)/φ (x). (There is no division operation in the field, when you need to divide something, it is something multiplied by the inverse element of the divider in the field)
ITKarma picture
- the remainder of the branch on φ (x) belongs to the field GF (2 8 ), and we accept it as the final result  $ R (x)=x ^ 7 + x ^ 5 + x ^ 4 + x ^ 3 + x $ modular multiplication.

Otherwise, the multiplication A (x) ⊗ B (x) is representable as
$ (x ^ 2 + 1) (x ^ 8 + x ^ 4 + x ^ 3 + x +1) ⊕ (x ^ 7 + x ^ 5 + x ^ 4 + x ^ 3 + x)== (x ^ 2 + 1) · φ (x) ⊕R (x) $ ={ba} 16 161 ,
where R (x) is a residue and degR (x) & lt; deg φ (x).
The power-law representation for obtaining the product of field elements is the most convenient.
A (x) · B (x)=α 178 · α 238 (178 + 238) 416 161 α 255 161 ={ba} 16 .

For any nonzero element of the β field, β · 1=β. The multiplicative unit in GF (2 8 ) is the element {01} 16 255 .
All calculated products for different representations of the operands are equivalent (converted to a single field element with the value {ba} 16 ).

Along with the usual (classical) consideration of the operation of multiplying elements in a binary field, there is a more convenient scheme. It is such a scheme that is implemented in the AES standard.

Consider the essence of this method of multiplication


Example 7 . Another way to multiply in a finite field. Let an arbitrary polynomial of the seventh degree be given
$ A (x)=a_7x ^ 7 + a_6x ^ 6 + a_5x ^ 5 + a_4x ^ 4 + a_3x ^ 3 + a_2x ^ 2 + a_1x + a_0 $
and its coefficients $ (a_7 a_6 a_5 a_4 a_3 a_2 a_101_0) ) _2 $ .

Multiply it by $ x $and get $ a_7x ^ 8 + a_1x ^ 2 + a_0x $. This result does not belong to the field GF (2 8 ); the degree of its polynomial is greater than 7 and it is necessary to bring it modulo φ (x)=1 {1b}, after which such a product becomes an element of the field GF (2 8 ).

For this purpose, the value $ a_7 $is determined. if $ a_7=0 $then the result is already belongs to the field, if $ a_7=1 $, instead of dividing it is enough to perform only the subtraction of A (x) x - φ (x) or the XOR operation for the product of A (x) x with φ (x).

In this case, when writing A (x) in the shift register, multiply by x the polynomial A (x), i.e. $ A (x) ⊗ {00000010}=A (x) ⊗ {02} $ corresponds to a shift of the polynomial A (x) by one bit towards the higher digits (to the left, that is, doubled) and, if necessary, the XOR operation with the irreducible polynomial of the field 1 {1b} 16 =φ (x).

In the algorithm of the encryption standard, the operation (function) xtime () is introduced, which essentially performs the multiplication of the polynomial by x, as described previously. Repeated use of xtime provides multiplication by x 8 . Further, by calculating the sum of the various degrees, we can obtain the result of the multiplication of arbitrary elements of the field GF (2 8 ).

Example 8 . Multiply the polynomials A (x)={c1} 16 and B (x)={11} 16 using their 16-decimal representations and representing the sum {11}={ 10⊕01}.
{c1} ⊗ {11}={11000001} ⊗ {00010001}={c1} ⊗ {10⊕01}={a4} ⊕ {c1}=01100101={65} 16 .

We detail all the actions. The x element in the GF field (2 8 ) has the representation
x={02} 16 =(00000010) 2 .
{c1} ⊗ {11}={c1} ⊗ {10} ⊕ {c1} ⊗ {01}=α 178 · α 100 ⊕α 178 · α 0 ={a4} ⊕ {c1}, since α 178 · α 100 (178 + 100-255) 23 ={a4}

Then multiplication by it simply leads to a shift of the first operand by 1 digit to the left.
{c1} ⊗ {02}=xtime {c1}=11000001⊗ 00000010=110000010 - 9-bit binary number. This result goes beyond our field. It is returned by subtracting the irreducible polynomial of the field φ (x), transforming it into an element of the field. Total Result 10011001={99}

$ \ begin {array} {r} - \ begin {array} {r} 110000010 \\ 100011011 \\ \ end {array} \\ \ hline \ begin {array} {r} 10011001 \ end {array} \ end {array} $


{c1} ⊗ {04}=xtime (99)=10011001⊗ 00000010=100110010 - 9-bit binary number. This result goes beyond our field. It is returned by subtracting the irreducible polynomial of the field φ (x), transforming it into an element of the field. Total Result 00101001={29}

$ \ begin {array} {r} - \ begin {array} {r} 100110010 \\ 100011011 \\ \ end {array} \\ \ hline \ begin {array} {r} 00101001 \ end {array} \ end {array} $


The next step in the procedure
{c1} ⊗ {08}=xtime (29)=00101001⊗ 00000010=0101 0010={52}.
Here we can’t summarize the result with φ (x), since the coefficient $ a_7=0 $ .

And one more step
{c1} ⊗ {10}=xtime (52)=01010010⊗00000010=10100100={a4} 16 .
Here, we also cannot summarize with φ (x), since the coefficient $ a_7=0 $ .
Thus, the value of the first term in the sum for the original
is found expressions where the second term is {c1} 16 .
Now finally find
{c1} ⊗ {11}={c1} ⊗ {10} ⊕ {c1} ⊗ {01}={a4} ⊕ {c1}=10100100⊕ 11000001={65} or

$ \ begin {array} {r} - \ begin {array} {r} 10100100 \\ 11000001 \\ \ end {array} \\ \ hline \ begin {array} {r} 01100101 \ end {array} \ end {array} $



verification by ordinary multiplication (power representation)
A (x) ∙ B (x)={c1} ∙ {11}=α 178 ∙ α 4 182
(from the tables we find in the row for α1 182 ) α 182 corresponds to {65} 16 .

An even greater effect in the production of calculations can be achieved by enlarging the elements with which manipulations are performed. So in the crypto algorithm RIJNDAEL 32-bit (4-byte) words are used. The byte constituent bits are not analyzed individually. This approach allows a 4-byte word to match a polynomial A (x) of degree at most three, and whose coefficients are in the field GF (2 8 ).

Multiplication operation for such words
$ A (x)=a_3x ^ 3 + a_2x ^ 2 + a_1x + a_0 $ and
$ B (x)=b_3x ^ 3 + b_2x ^ 2 + b_1x + b_0 $ ,
where $ a_i, b_i $єGF (2 8 ), i=0 (1) 3, is executed modulo a polynomial of degree at most four. Taking the result of a product modulo an irreducible polynomial of degree 4 always provides the result of the product as an element of the field.

The polynomial $ ψ (x)=x ^ 4 + 1 $ is chosen as such a polynomial . He has the simplest entry, and for him it is fair
$ x_i (mod (x ^ 4 + 1))=x_i (mod4) $ .
The last property is very useful in the calculations.
For the polynomials under consideration, the addition operation is performed similarly (XOR bitwise in mod2)
$ inline $ A (x) ⊕ B (x)=(a_3⊕ b_3) x ^ 3 ⊕ (a_2⊕ b_2) x ^ 2 ⊕ (a_1⊕ b_1) x ⊕ (a_0⊕ b_0) $ inline $.

Multiplication of polynomials.
$ inline $ A (x) ⊗ B (x)=C (x)=(c_6x ^ 6 ⊕ c_5x ^ 5 ⊕ c_4x ^ 4⊕ c_3x ^ 3 ⊕ c_2x ^ 2 ⊕ c_1x ^ 1 ⊕ c_0) mod (x ^ 4 +1) $ inline $.
Odds $ c_j, j=0 (1) 6 $determined from ratios
$ C_0=a_0⊕b_0 $,
$ C_1=a_1b_0⊕ a_0b_1 $,
$ C_2=a_2b_0 ⊕ a_1b_1⊕a_0b_2 $$ C_3=a_3b_0⊕ a_2b_1⊕ a_1b_2⊕a_1b_2⊕a_1b_2ba2_ab_2ba2_ab_2ba2_ab_2ba2_ab_2ba2_ab_2ba2_a_bb2xa ,
$ C_4=a_3b_1⊕ a_2b_2⊕ a_1b_3 $$ C_6=a_3b_3 $.

Окончательно результатом D(x) умножения ⊗ двух многочленов по модулю $x^4+1$будет
$inline$D(x)=A(x)⊗B(x)=d_3x^3 ⊕ d_2x^2 ⊕ d_1x ⊕ d_0$inline$, где
$d_0=a_0b_0⊕ a_3b_1⊕ a_2b_2⊕ a_1b_3$,
$d_1=a_1b_0⊕ a_0b_1⊕ a_3b_2⊕ a_2b_3$,
$d_2=a_2b_0⊕ a_1b_1⊕ a_0b_2⊕ a_3b_3$,
$d_3=a_3b_0⊕ a_2b_1⊕ a_1b_2⊕ a_0b_3$,
или более кратко в векторно – матричной записи,
ITKarma picture

выполним умножение В(х) на х по $mod(х^4+1)$, учитывая свойства многочлена. Такому умножению, как и ранее, соответствует циклический сдвиг байтов в пределах слова в направлении старшего байта. Так как
$x^4mod(x^4 + 1)=x_i mod4=x^0=1$, то
$x∙ B(x)=b_2x^3+ b_1x^2+ b_0x+ b_3 => x∙(b_3 b_2 b_1 b_0)$
реализуется циклический сдвиг байтов.

Приложение


Таблица П1 — расширенного поля, неприводимый многочлен φ(х)=Р (х), примитивный элемент α=3 16
ITKarma picture

ITKarma picture

ITKarma picture

ITKarma picture
.

Source