# Help with finite fields

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?

-
What definition is your book using? Which finite field are you working in? –  Qiaochu Yuan Feb 7 '11 at 19:47
GF(2^8) I think –  DasWood Feb 7 '11 at 19:49
"repeatedly xoring with 283" is not a very useful thing to do... –  Mariano Suárez-Alvarez Feb 7 '11 at 19:53
Could you post the entire passage to give some context? I suspect your book does not say "repeatedly xor with $283$", since doing xor with $283$ twice is the same as doing nothing (I think you mean, the first few bits only). It's hard to guess what is being described, but a direct quote would help. –  Arturo Magidin Feb 7 '11 at 19:55
Also, $283 > 255$... –  Yuval Filmus Feb 7 '11 at 20:11

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.

-
That is much easier to understand than my book. However now I need to ask if my book is wrong then. I already checked the errata. 01010111*00000100=01011100xor(00011011) Why is i xoring if the msb isn't 1? –  DasWood Feb 7 '11 at 21:18
Your book is probably correct. You might have misunderstood something. What seems wrong in the book? –  Yuval Filmus Feb 7 '11 at 21:20
You're multiplying by $4$ so you shift $01010111$ left twice, so the leftmost $1$ "jumps off the cliff" and needs to be accounted for. In other words, $x^{6+2} = x^8$. –  Yuval Filmus Feb 7 '11 at 21:22
It demonstrates 01010111*10000011 and then gives examples of multiplying by each order of x. 01010111*00000010=10101110 and 01010111*00000100=01011100xor00011011 and 01010111*00001000=10001110 Now for each of these the msb before shifting is 0 so why are they xoring? –  DasWood Feb 7 '11 at 21:23
When you're shifting left $k$ times, it's the $k$ most significant bits that count. –  Yuval Filmus Feb 7 '11 at 23:02