# GCM Construction of table M0

I am reading the paper on GCM The Galois/Counter Mode of Operation (GCM) . I have some doubts about the implementation of table M0 and R.

When I have to multiply by the variable P it is nothing more than a shift to the indexes. At the top of page 10 I have the example of multiplication by X · P and I suppose the one below is to multiply two elements.

Z ← 0, V ← X for i =0 to 127 do if Yi =1 then Z ← Z ⊕ V end if V ← V · P end for return Z

From what I understand:

V ← V · P

Is equal to:

if V127 =0 then V ← rightshift(V ) else V ← rightshift(V ) ⊕ R

According to the examples on page 9 in formulas (3) (5), would they be the same, right?

Well already on page 11 in the example of the deconposition of X (7), xi refers to 1 byte of X, but my doubt is in P ^ 8i, in the first for 8 · i would give zero and at the end when i is 15 would be 120. That part I don't really understand.

Going to algorithm 3 and its explanation above:

while i> 0 do M ← M[2i] · P i ←li/2J

Assuming that the value of i is 64, that cycle would multiply by P eight times if I am not mistaken.

Well and in the part of the multiplication by P:

M ← M[2i] · P

Is equal to:

if M[2i]127 =0 then M ← rightshift(M[2i]) else M ← rightshift(M[2i]) ⊕ R end if

And the 247 additions would be:

M[i + j]= M ⊕M[j]

Everything explained above is fine, it would be enough to build table M0 and R? But I don't understand the following elevation P^8(i+1) and P^128.

Thanks.

## 1 Answer

This is one of the most poorly written "mainstream" crypto papers I've read. Sorry, McGrew and Viega.

# Field representation and bit order

GCM works in the binary field $$GF(2^{128})$$. Elements of this field can be represented as polynomials with binary coefficients (i.e. 0 or 1).

Using the notation of the paper, here are some examples of field elements:

• $$1$$ (note that this is $$0\alpha^{127} + 0\alpha^{126} + \ldots + 0\alpha^1 + 1$$; we simply don't writte the coefficients with 0).
• $$\alpha^1 + 1$$
• $$\alpha^2 + \alpha$$
• $$\alpha^{127} + \alpha^{64} + 1$$
• $$\alpha^{127}$$

Cool. So how do we represent this in memory, since we only have bits and bytes, and not actually polynomials? The straightforward way is to simply group the coefficients in groups of eight, inside bytes. Which raises the question: how to order the bits inside the byte? And how to order the bytes inside the 16-byte buffer (totaling 128 bits)?

One straightforward answer is to use little endian for both bits and bytes; i.e the least significant bit of the byte (i.e. what you get with x & 0x01, note that calling this "little endian" it not that usual but I need to call it something) is the least significant bit of the 8-bit group; and the least significant byte of the buffer (i.e. what you get with b[0]) is the least significant 8-bit group of the 16 groups. So these examples would be encoded as:

• $$1$$: 0x01 0x00 ... 0x00
• $$\alpha^1 + 1$$: 0x03 0x00 ... 0x00
• $$\alpha^2 + \alpha$$: 0x06 0x00 ... 0x00
• $$\alpha^{127} + \alpha^{64} + 1$$: 0x01 0x00 ... 0x01 ... 0x00 0x80
• $$\alpha^{127}$$: 0x00 ... 0x00 0x80

This seems natural (at least it does for me); but you could make a convicing argument for a "little-endian" bit order and big-endian byte order since it looks more like the way we write the polynomials. That's OK. Is that what GCM does? No, it isn't.

GCM uses "big-endian" for bits, and little-endian for bytes. Our examples become:

• $$1$$: 0x80 0x00 ... 0x00
• $$\alpha^1 + 1$$: 0xC0 0x00 ... 0x00
• $$\alpha^2 + \alpha$$: 0x06 0x00 ... 0x00
• $$\alpha^{127} + \alpha^{64} + 1$$: 0x80 0x00 ... 0x80 ... 0x00 0x01
• $$\alpha^{127}$$: 0x00 ... 0x00 0x01

So there's that.

# Now actually answering the question

According to the examples on page 9 in formulas (3) (5), would they be the same, right?

Yes.

Well already on page 11 in the example of the deconposition of X (7), xi refers to 1 byte of X, but my doubt is in P ^ 8i, in the first for 8 · i would give zero and at the end when i is 15 would be 120. That part I don't really understand.

As I described, the coefficients of the polynomials are grouped into 16 bytes with 8 bits each. Formula (7) is just the mathematical way of saying that. Note that $$P = \alpha$$. Why not call the same thing by two different names?

For example, take the field element $$X = \alpha^{15} + 1$$. This is represented by the byte buffer 0x80 0x01. So in the decomposition, we have:

• $$x_0$$ = $$1$$ = 0x80
• $$x_1$$ = $$\alpha^7$$ = 0x01 (we're looking at it as a 8-bit polynomial)

and then, $$X = \bigoplus\limits_{i=0}^{15} x_iP^{8i} = \bigoplus\limits_{i=0}^{15} x_i\alpha^{8i} = x_0\alpha^0 + x_1\alpha^8 + ...$$ = $$1\alpha^0 + (\alpha^7)\alpha^8 = 1 + \alpha^{15}$$.

Assuming that the value of i is 64, that cycle would multiply by P eight times if I am not mistaken.

Table $$M$$ contains $$M[x] = xH$$ for all 8-bit polynomials and the 128-bit polynomial $$H$$ (which is computed from the key).

That cycle multiplies by $$P$$ seven times. That loop is computing $$M[128], M[64], M[32], ... M[1]$$. Recall that the index is actually a polynomial, so that's the same as $$M[1], M[\alpha], M[\alpha^2], ..., M[\alpha^7]$$. Yes, $$128 = 0x80$$ (the number) is equal to $$1$$ (the polynomial). Welcome to GCM.

Everything explained above is fine, it would be enough to build table M0 and R? But I don't understand the following elevation P^8(i+1) and P^128.

I think what I've explained covers the rest of your question, but I'm not sure. Feel free to ask for clarifications and I'll edit the answer.

• I would personally disagree - this is far from the most poorly written crypto paper I've seen. I would agree that the bit ordering within GCM is counterintuitive, and they could call it out more. – poncho May 19 at 13:24
• @poncho I certainly have read way less papers than you, and I was thinking in relation to similar papers (i.e. describing ciphers). The bit order is not only confusing but makes software implementations difficult since shifting a word won't shift the polynomial in the right way. – Conrado May 19 at 14:13
• Hi, well if you tell me that I am correct about the multiplication of P, it is practically what I need to know. But I have a question about creating the R table, the 1024 bytes M0[192] = H ⊕ H · P I can understand this without any problem, but how do I continue to decompose R and build the rest of the table? I have some more questions and I would like to show the codes that I have, but it does not allow me to write many characters in the answer. – verzz May 20 at 21:56