In my previous post, I wrote about finite fields (Galois fields) of order 2n, abbreviated GF(2n). Their elements are congruence classes of polynomials over the field Z2 = { 0, 1 }. Each congruence class consists of all polynomials that leave the same remainder when divided by some fixed polynomial m.
To multiply two elements B and C from GF(2n), you choose a polynomial b from B and a polynomial c from C, and then calculate d = (b ⋅ c) mod m. The result d is a polynomial, which belongs to some congruence class D in GF(2n). D is the product of B and C.
In section 4.2 of the AES spec, you can find a different algorithm for multiplication in GF(28), which is conceptually simpler than the algorithm above, because it doesn't need polynomial multiplication and modulo division, but only addition and shifting of coefficients. However, I myself needed some time to understand how exactly the algorithm works and why exactly it is correct. So I decided to write about it and share my understanding of it. That's the first section of this post.
The AES spec states this algorithm only for GF(28) but it can easily be generalized to GF(2n) for arbitrary n. And in fact, it is just the algorithm presented in the GCM spec for multiplication in GF(2128), although the spec doesn't say this. So in the second section of this post, I will explain the connection between the algorithms in both specs in more detail. So read until the end if you are - like I was - struggling to understand section 6.3 of the GCM spec on multiplication of blocks. (Why is this pseudo-code correct? What's the magic bit string R?)
In case you're curious to see the algorithm I'm talking about in code, take a look at my Ruby implementation of it.
Multiplication in GF(28) following the AES spec
The goal of the algorithm in the AES spec is to calculate (b ⋅ c) mod m for polynomials b, c of degree < 8 and the fixed polynomial m = x8+x4+x3+x+1. I'll break down the algorithm into three steps:
- Calculate p ⋅ x for some polynomial p of degree < 8,
- calculate (p ⋅ x) mod m for some polynomial p of degree < 8 (this is called the xtimes function),
- reduce the calculation of (b ⋅ c) mod m to repeated applications of the function from step 2.
Calculation of p ⋅ x
Let's give the coefficients of p names: Let p = p7x7 + p6x6 + p5x5 + p4x4 + p3x3 + p2x2 + p1x + p0. Of course, p doesn't have to have degree 7; p7 can be zero, just as any other coefficient.
If you multiply p with x, you'll get p ⋅ x = p7x8 + p6x7 + p5x6 + p4x5 + p3x4 + p2x3 + p1x2 + p0x.
If you model polynomials as finite sequences of their coefficients, p is (p7, p6, p5, p4, p3, p2, p1, p0) and p ⋅ x is (p7, p6, p5, p4, p3, p2, p1, p0, 0). So multiplication of polynomials with x is extremely simple: you just have to add a zero to the sequence of coefficients.
Calculation of (p ⋅ x) mod m
Now we're going to define the so-called xtimes function. It should satisfy the condition xtimes(p) = (p ⋅ x) mod m. But we don't want to use this equation as definition, as we are searching for something simpler.
If p ⋅ x has degree < 8 (i.e. if p7 is zero), then (p ⋅ x) mod m is just p ⋅ x. So we can define:
xtimes(p) = (p6, p5, p4, p3, p2, p1, p0, 0) if p7 = 0.
(Note that we choose to omit the leading zero coefficient p7. If you actually define polynomials as finite sequences, this omission has to be justified. After all, the sequence (0, p6, p5, p4, p3, p2, p1, p0, 0) is different from the sequence (p6, p5, p4, p3, p2, p1, p0, 0). However, the omission is certainly justified here because in the end, we are interested in finding a representative of a congruence class. And leading zero coefficients surely don't change the congruence class of the polynomial.)
If, on the other hand, p7 is not zero, we have to calculate the reduction modulo m. In the case of AES, m is fixed, but let's do the reduction for an arbitrary polynomial of degree 8, m = m8x8 + m7x7 + m6x6 + m5x5 + m4x4 + m3x3 + m2x2 + m1x + m0. Remember that the coefficients are members of the field Z2 = { 0, 1 }. Addition and subtraction in Z2 are both the XOR operation.
Since p7 is not zero, it must be 1. And since m has degree 8, we have m8 = 1 as well. So the polynomial long division of p ⋅ x by m looks like this:
(x8 + p6x7 + ... + p0x) / (x8 + m7x7 + ... m1x + m0) = 1
- (x8 + m7x7 + ... m1x + m0)
-------------------------------
(1 - 1)x8 + (p6 - m7)x7 + ... + (p0 - m1)x + (0 - m0)
So written as a sequence, the remainder polynomial is (1 - 1, p6 - m7, ..., p0 - m1, 0 - m0) = (0, p6 - m7, ..., p0 - m1, m0).
With the same justification as above, we skip the leading zero. Since subtraction in Z2 is the XOR operation, we can calculate the remainder like this: (p6, p5, p4, p3, p2, p1, p0, 0) XOR (m7, m6, m5, m4, m3, m2, m1, m0).
Now, back to the spec. Here, m is the fixed polynomial x8+x4+x3+x+1, so the second part of the xtimes definition looks like this:
xtimes(p) = (p6, p5, p4, p3, p2, p1, p0, 0) XOR (0, 0, 0, 1, 1, 0, 1, 1) if p7 = 1.
Note that the the algorithm works just as well for other Galois fields GF(2n): For n=8, we only used the fact that m has degree 8. However, the modulus polynomial for GF(2n) has always degree n. Meaning: So far, the algorithm works for every n.
Reduction of multiplication to xtimes
We can use the xtimes function to calculate (b ⋅ c) mod m for arbitrary polynomials over Z2 of degree < 8. For example, let c be x2+x:
b ⋅ (x2+x) mod m
= (bx2 + bx) mod m
= (bx2 mod m) + (bx mod m)
Okay, (bx mod m) is just xtimes(b), that's good. The first summand can also be expressed in terms of xtimes:
bx2 mod m
= (bx ⋅ x) mod m
= ((bx mod m) ⋅ x) mod m
= (xtimes(b) ⋅ x) mod m
= xtimes(xtimes(b))
So we have:
b ⋅ (x2+x) mod m = xtimes(xtimes(b)) + xtimes(b)
In general, the algorithm for calculating (b ⋅ c) mod m works like this: Apply the xtimes function k times to b if ck is one. Then add all the results.
All of this works just the same for other Galois fields, even of different orders. So it's no surprise that we find the same algorithm in the GCM spec, where it is used to multiply 128-bit blocks instead of bytes.
Multiplication in GF(2128) following the GCM spec
To spare you the hassle to look it up, here is a screenshot of the multiplication algorithm in the GCM spec:
Just like above, one factor is fixed (Y) and the coefficients of the other (X) are inspected.
The blocks Vi are the results of repeated applications of xtimes to Y. The blocks Zi are the result of adding all Vis that correspond to a coefficient 1.
The Vi+1 is analogous to the xtimes definition, but there is a little gotcha: In GCM, the order of the coefficient is reversed, so the bit sequence x0x1...x127 represents the polynomial x0 + x1 ⋅ x + ... + x127 ⋅ x127.
When I explained above how to calculate p ⋅ x, I represented polynomials by bit sequences and assumed a different ordering, so that the x0x1...x127 would represent the polynomial x0 ⋅ x127 + ... + x126 ⋅ x + x127.
That's why multiplying a polynomial with x is not achieved by shifting the coefficients not to the left but to the right, and that's the explanation for the ">> 1" in the definition of Vi+1.
It also explains why the distinction between cases in the definition of Vi+1 works by looking at the least significant (right-most) bit, while the distinction in my xtimes definition worked by looking at the first/left-most/most significant bit.
And the unusual ordering of coefficients is the reason that the loop in step 3 ranges from 0 to 127, instead of the other way around.
Finally, the bit string R = 11100001 || 0120 is a shifted representation of the modulus polynomial. In the case of GCM, this polynomial is m = x128+x7+x2+x+1. To define xtimes, we discarded the highest order coefficient and wrote the other ones in a bit sequence. This gives us the bit sequence 0120 || 10000111. But again, GCM reverses the coefficients, so you end up with R.
Top comments (0)