CS代考计算机代写 algorithm Arithmetic in Galois Fields of the form 𝐺𝐹(2𝑛)
Arithmetic in Galois Fields of the form 𝐺𝐹(2𝑛)
Galois fields are finite fields, that is, they have a finite number of elements. (An example of an infinite field is the real numbers.) The number of elements must always be non- negative integer power of a prime number. In our examples, the prime will always be 2. It’s best to think of the elements in base 2, that is, as bit strings containing 𝑛 bits. In every field where the prime is 2, addition is defined as the bit-wise XOR of two 𝑛-bit values. Multiplication is not so briefly defined.
AES relies on arithmetic in the Galois field 𝐺𝐹(28), which contains 256 elements and which spans the values a single byte can have. We will start with the smaller field 𝐺𝐹(22), which contains four values {00,01,10,11}.
The addition table is easy to build:
+ (XOR)
00
01
10
11
00
00
01
10
11
01
01
00
11
10
10
10
11
00
01
11
11
10
01
00
But now I will introduce a different way to think about these two-bit values. Think of them as coefficients of a polynomial of the form 𝑏1𝑥 + 𝑏0 where 𝑏1𝑏0 is the value. Here is the addition table again but with the polynomial represented by each value inserted:
+ (XOR)
00 (𝟎 ⋅ 𝒙 + 𝟎)
01 (𝟎 ⋅ 𝒙 + 𝟏)
10 (𝟏 ⋅ 𝒙 + 𝟎)
11 (𝟏 ⋅ 𝒙 + 𝟏)
00 (𝟎 ⋅ 𝒙 + 𝟎)
00 (0 ⋅ 𝑥 + 0)
01 (0 ⋅ 𝑥 + 1)
10 (1 ⋅ 𝑥 + 0)
11 (1 ⋅ 𝑥 + 1)
01 (𝟎 ⋅ 𝒙 + 𝟏)
01 (0 ⋅ 𝑥 + 1)
00 (0 ⋅ 𝑥 + 0)
11 (1 ⋅ 𝑥 + 1)
10 (1 ⋅ 𝑥 + 0)
10 (𝟏 ⋅ 𝒙 + 𝟎)
10 (1 ⋅ 𝑥 + 0)
11 (1 ⋅ 𝑥 + 1)
00 (0 ⋅ 𝑥 + 0)
01 (0 ⋅ 𝑥 + 1)
11 (𝟏 ⋅ 𝒙 + 𝟏)
11 (1 ⋅ 𝑥 + 1)
10 (1 ⋅ 𝑥 + 0)
01 (0 ⋅ 𝑥 + 1)
00 (0 ⋅ 𝑥 + 0)
The reason for this is because multiplication between two elements is defined as the product of the polynomials represented by the elements. Of course, in many cases, this will result in a polynomial with three terms and so three coefficients. But we’ve seen a situation like this before, for example, when we multiplied two elements in Z26 and got a value not in the range 0 to 25. We took product modulo 26 to get it back in the correct range.
We’ll do the same here but this time we will need to take the product modulo a fixed polynomial. For this field, we’ll use the polynomial 𝑥2 + 𝑥 + 1. This is an irreducible polynomial. This means that it cannot be factored into simpler polynomials where the coefficients are either 0 or 1. Irreducible polynomials are like prime numbers. We saw that in Z𝑝, where 𝑝 is prime, all of the values from 1 to 𝑝 − 1 have multiplicative inverses. Something similar to that is being used here.
Note that a remainder resulting from division by this polynomial can only have an 𝑥 term. It cannot have an 𝑥2 term. In other words, the remainder must be one of these
polynomials: 𝑥 + 1, 𝑥, 1, 0. These correspond to the bit strings 11, 10, 01, 00.
Example multiplication
Let’s multiply 11 by 10. As polynomials that means multiplying 𝑥 + 1 by 𝑥, which yields 𝑥2 + 𝑥. Now we’ll divide this by the irreducible polynomial 𝑥2 + 𝑥 + 1:
1 𝑥2 +𝑥+1√𝑥2 +𝑥+0
𝑥2 + 𝑥 + 1 1
For a division to be possible, it is only necessary that the dividend’s lead term have a power greater than or equal to the divisor’s lead term.
The result here is that in 𝐺𝐹(22) 11 × 10 = 01. Here is the full multiplication table:
×
00 (𝟎 ⋅ 𝒙 + 𝟎)
01 (𝟎 ⋅ 𝒙 + 𝟏)
10 (𝟏 ⋅ 𝒙 + 𝟎)
11 (𝟏 ⋅ 𝒙 + 𝟏)
00 (𝟎 ⋅ 𝒙 + 𝟎)
00 (0 ⋅ 𝑥 + 0)
00 (0 ⋅ 𝑥 + 0)
00 (0 ⋅ 𝑥 + 0)
00 (0 ⋅ 𝑥 + 0)
01 (𝟎 ⋅ 𝒙 + 𝟏)
00 (0 ⋅ 𝑥 + 0)
01 (0 ⋅ 𝑥 + 1)
10 (1 ⋅ 𝑥 + 0)
11 (1 ⋅ 𝑥 + 1)
10 (𝟏 ⋅ 𝒙 + 𝟎)
00 (0 ⋅ 𝑥 + 0)
10 (1 ⋅ 𝑥 + 0)
11 (1 ⋅ 𝑥 + 1)
01 (0 ⋅ 𝑥 + 1)
11 (𝟏 ⋅ 𝒙 + 𝟏)
00 (0 ⋅ 𝑥 + 0)
11 (1 ⋅ 𝑥 + 1)
01 (0 ⋅ 𝑥 + 1)
10 (1 ⋅ 𝑥 + 0)
Now that we have defined multiplication, we can find multiplicative inverses. As always, the multiplicative identity is 1 so, for each element labeling a row above, its multiplicative inverse is the element labeling the column containing 1.
This idea can be extended to 𝐺𝐹(28). The irreducible polynomial used for AES is 𝑥8 + 𝑥4 + 𝑥3 + 𝑥 + 1.
Now we think of the elements as 8-bit strings where 𝑏𝑖 is the coefficient for 𝑥𝑖. We will also express these elements in hexadecimal. For example, we would like to multiply 0𝑥13 by 0𝑥65. Let’s look at these values in binary and as polynomials:
0𝑥13→00010011→𝑥4 +𝑥+1 0𝑥65→01100101→𝑥6 +𝑥5 +𝑥2 +1
Remember that addition and subtraction on values mod 2 are the same operation: XOR.
(𝑥4 +𝑥+1)×(𝑥6 +𝑥5 +𝑥2 +1)
=𝑥10 +𝑥9 +𝑥6 +𝑥4 +𝑥7 +𝑥6 +𝑥3 +𝑥+𝑥6 +𝑥5 +𝑥2 +1
=𝑥10 +𝑥9 +𝑥7 +𝑥6 +𝑥5 +𝑥4 +𝑥3 +𝑥2 +𝑥+1
This has degree larger than 7 so take it modulo the irreducible polynomial. Repeatedly divide the above polynomial by the irreducible polynomial. Multiply the irreducible by the power of 𝑥2 needed to knock out the leading term:
𝑥2 ×(𝑥8 +𝑥4 +𝑥3 +𝑥+1)=𝑥10 +𝑥6 +𝑥5 +𝑥3 +𝑥2 Subtract that right-hand product from the polynomial.
(𝑥10 +𝑥9 +𝑥7 +𝑥6 +𝑥5 +𝑥4 +𝑥3 +𝑥2 +𝑥+1)−(𝑥10 +𝑥6 +𝑥5 +𝑥3 +𝑥2)=𝑥9 +𝑥7 +𝑥4 +𝑥+1
Multiply the irreducible by 𝑥 to knock out the leading term: 𝑥×(𝑥8 +𝑥4 +𝑥3 +𝑥+1)=𝑥9 +𝑥5 +𝑥4 +𝑥3 +𝑥2 +𝑥
Subtract.
(𝑥9 +𝑥7 +𝑥4 +𝑥+1)−(𝑥9 +𝑥5 +𝑥4 +𝑥3 +𝑥2 +𝑥) =𝑥7 +𝑥5 +𝑥2 +1
This is a remainder with a leading term of power 7 or less. Reading off its coefficients, this is equivalent to the binary value 1010 0101, which in hex is 0𝑥𝑎5. So 0𝑥13 × 0𝑥65 = 0𝑥𝑎5 in 𝐺𝐹(28) (with the given irreducible).
To find multiplicative inverses requires the Extended Euclidean algorithm for finding the GCD, adapted to divisibility among these polynomials rather than divisibility among integers.
Two more examples
In generating the key schedule, AES uses a round coefficient defined to be 𝑥𝑖−1 for round 𝑖. Two of those, 𝑥8 and 𝑥9, are
polynomials with degree greater than 7. Here are those polynomials taken modulo the irreducible polynomial.
𝑥8 𝑚𝑜𝑑(𝑥8 +𝑥4 +𝑥3 +𝑥+1)=𝑥4 +𝑥3 +𝑥+1 ≡ 0001 1011 ≡ 0𝑥1𝑏
𝑥9 𝑚𝑜𝑑(𝑥8 +𝑥4 +𝑥3 +𝑥+1)=𝑥5 +𝑥4 +𝑥2 +𝑥 ≡ 0011 0110 ≡ 0𝑥36
