1
$\begingroup$

I have been reading about finite fields because they are used in cryptography quite a bit. However I am having some trouble conceptualizing how they work exactly. Using AES as the example. When you multiply two numbers you then repeatedly xor with 283 until some point.

Ex, my book states using Hex to binary and GF(2^8) 87*02 is
10000111
00000010
-is 100001110. Then xored with 283?
xor100011011
==000010101

Now how do I know when to stop xoring? Why am I xoring? Just until there are 8 or less digits so I get the correct modulo?

  • 0
    http://www.cs.utsa.edu/~wagner/laws/FFM.html is what you're looking for.2011-02-07

1 Answers 1

4

The finite field $GF(2^8)$ is better thought of a collection of $7$th degree polynomials modulo $2$ and some (irreducible) $8$th degree polynomial $P$. Let's see what all of this means.

First, each member of $GF(2^8)$ is of the form $\sum_{i=0}^7 a_i x^i$, where the $a_i$ are coefficients "modulo $2$", i.e. bits. When you add two of the $a_i$s, you calculate the answer modulo $2$, so it's the same as XORing.

Adding two polynomials is easy: $\sum_{i=0}^7 a_i x^i + \sum_{i=0}^7 b_i x^i = \sum_{i=0}^7 (a_i+b_i) x^i.$ So addition corresponds to XOR.

Multiplication is more involved. For AES the polynomial in question is $P(x) = x^8 + x^4 + x^3 + x + 1.$ Written in bits, it is $(100011011)_2 = (283)_{10}$. The point is that $x^8 = x^4 + x^3 + x + 1$ (since everything's mod $2$), so in order to multiply a polynomial by $x$, you do the following:

  1. Remember the MSB (that's the power of $x^7$).
  2. Shift the number left once (replacing $x^i$ with $x^{i+1}$).
  3. If the old MSB was $1$, XOR $(11011)_2$ (since $x^8 = x^4 + x^3 + x + 1$).

Using this primitive, you can multiply two polynomials $A = \sum_{i=0}^7 a_i x^i$ and $B = \sum_{i=0}^7 b_i x^i$ as follows:

  1. Initialize the result $C = 0$.
  2. Add to $C$ the value of $a_0 B$, that is, if the LSB of $A$ is $1$, XOR $B$ to $C$.
  3. Add to $C$ the value of $a_1 x B$, that is, if the second least bit of $A$ is $1$, XOR $xB$ to $C$; to calculate $xB$, use the method above.
  4. And so on, until you get to $a_7$.
  5. Return $C$.

In practice, you implement it as a loop:

  1. Initialize $C = 0$.
  2. If $LSB(A)=1$, $C = C + B$.
  3. Set $B = xB$, $C=C/2$ (i.e. shift $C$ right once).
  4. Repeat the previous two steps $7$ more times.

In a real implementation, this multiplication table is stored in some condensed form. At the very least, you store the table of multiplication by $x$. The other extreme is storing all $2^{16}$ possible products. In between, you can store the product of any $A$ by any $2$-bit $B$ (size $2^{10}$ bytes), any $3$-bit $B$ (size $2^{11}$ bytes) or any $4$-bit $B$ (size $2^{12}$ bytes). It all depends on how much memory you can spare, and on the trade-off between memory access (i.e. cache sizes) and ALU performance.

  • 0
    I would suggest - for minimizing storage space with regards to GF(256) that you choose x to be a multiplicative generator of the non-zero elements and then construct a 'list' of 'logarithms'. Note that the list will start out 1,2,4,8,16,32,64,128,C and this C is related to the irreducible polynomial which x satisfies. Anyway you may need 2 such lists, one for x^k where k<=255 and you are storing one byte which is the 'additive form' of x^k = a 'polynomial over Z2' with degree < 8. The second list will be 'where do I find this 'polynomial over Z2' as x^what? This makes mult and additio simpler.2012-04-22