In ASE the finite field contains 256 element and is denoted as GF(2^8). this fie
ID: 3687536 • Letter: I
Question
In ASE the finite field contains 256 element and is denoted as GF(2^8). this field was chosen because each field element can be represented by one byte.proof: C(3) hex is an element in the finite field GF(2^8). All elements of F form an additive group with the group operation "+" and the neutral element 0. All elements of F except 0 form a multiplicative group with the group operation "x" and the neutral element l. When the two group operations are mixed, the distributivity law holds, i.e., for all a, b, c F: a(b + c) = (ab) + (ac).Explanation / Answer
The finite field GF(28 ) used by AES obviously contains 256 distinct polynomials over GF(2).
SOME OBSERVATIONS ON BIT-PATTERN ADDITIONS IN GF(2n )
• We know that the polynomial coefficients in GF(2n ) must obey the arithmetic rules that apply to GF(2) (which is the same as Z2, the set of remainders modulo 2).
• And we know that the operation of addition in GF(2) is like the logical XOR operation.
• Therefore, adding the bit patterns in GF(2n ) simply amounts to taking the bitwise XOR of the bit patterns. For example, the following must hold in GF(28 ): 5 + 13 = 0000 0101 + 0000 1101 = 0000 1000 = 8 76 + 22 = 0100 1100 + 0001 0110 = 0101 1010 = 90 7 3 = 0000 0111 0000 0011 = 0000 0100 = 4 7 + 3 = 0000 0111 + 0000 0011 = 0000 0100 = 4
• The last two examples above illustrate that subtracting is the same as adding in GF(28 ). That is because each “number” is its own additive inverse in GF(28 ). In other words, for every x GF(28 ), we have x = x. Yet another way of saying the same thing is that for every x GF(28 ), we have x + x = 0.
SOME OBSERVATIONS ON ARITHMETIC MULTIPLICATION IN GF(2n )
• As you just saw, it is obviously convenient to use simple binary arithmetic (in the form of XOR operations) for additions in GF(2n ). Could we do the same for multiplications?
• We can of course multiply the bit patterns of GF(2n ) by going back to the modulo polynomial arithmetic and using the multiplications operations defined in GF(2) for the coefficients.
• But it would be nice if we could directly multiply the bit patterns of GF(2n ) without having to think about the underlying polynomials. • It turns out that we can indeed do so, but the technique is specific to the order of the finite field being used. The order of a finite field refers to the number of elements in the field. So the order of GF(2n ) is 2n .
• On the next slide, we will focus specifically on the GF(28 ) finite field that is used in AES, which we will take up in the next lecture, and show that multiplications can be carried out directly in this field by using bitwise operations.
DIRECT BITWISE OPERATIONS FOR MULTIPLICATIONS IN GF(28 )
• Let’s consider the finite field GF(28 ) that is used in AES. As you will see in the next lecture, this field is derived using the following irreducible polynomial of degree 8: m(x) = x 8 + x 4 + x 3 + x + 1 • Now let’s see how we can carry out multiplications with direct bitwise operations in this GF(28 ).
• We first take note of the following equality in GF(28 ): x 8 mod m(x) = x 4 + x 3 + x + 1 The result follows immediately by a long division of x 8 by x 8 + x 4 + x 3 + x + 1. Obviously, the first term of the quotient will be 1. Multiplying the divisor by the quotient yields x 8 + x 4 + x 3 + x + 1. When this is subtracted from the dividend x 8 , we get x 4 x 3 x 1, which is the same as the result shown above.
• Now let’s consider the general problem of multiplying a general polynomial f(x) in GF(28 ) by just x. Let’s represent f(x) by f(x) = b7x 7 + b6x 6 + b5x 5 + x4x 4 + b3x 3 + b2x 2 + b1x + b0 Therefore, this f(x) stands for the bit pattern b7b6b5b4b3b2b1b0.
• Obviously, f(x)×x = b7x 8 + b6x 7 + b5x 6 + x4x 5 + b3x 4 + b2x 3 + b1x 2 + b0x But now recall that we must take the modulo of this polynomial with respect to m(x) = x 8 + x 4 + x 3 + x + 1. What that yields depends on whether or not the bit b7 is set.
• If the bit b7 of f(x) is equals 0, then the right hand above is already in the set of polynomials in GF(28 ) and nothing further needs to be done. In this case, the output bit pattern is b6b5b4b3b2b1b00.
• However, if b7 equals 1, we need to divide the polynomial we have for f(x) × x by the modulus polynomial m(x) and keep just the remainder. Therefore, when b7 = 1, we can write
(f(x) × x) mod m(x) = (b7x 8 + b6x 7 + b5x 6 + b4x 5 + b3x 4 + b2x 3 + b1x 2 + b0x) mod m(x) = (b6x 7 + b5x 6 + b4x 5 + b3x 4 + b2x 3 + b1x 2 + b0x) + (x 8 mod m(x)) = (b6x 7 + b5x 6 + b4x 5 + b3x 4 + b2x 3 + b1x 2 + b0x) + (x 4 + x 3 + x + 1) = (b6b5b4b3b2b1b00) (00011011) where, in the last expression shown, we have used the fact that the addition in GF(28 ) corresponds to the logical XOR operation for the bit patterns involved.