GCM cipher M0 tables : semantic questions on how to implement GCM

Question

I`m reading the PDF "The Galois/Counter Mode of Operation (GCM)". In section 4.1 on the optimization of multiplications with tab, in algorithm 3 I have the following questions:

1. A vector called M with 128 bits is created, then the value of H is copied into that vector, now M [128] is the same as H, is not it? Or is it after those 128 bits? In programming would be that way.

If I believe that the 128-bit vector is created, and these remain null. because if not the while cycle does not make sense. in this the value of i is multiplied by 2 this results in 128, and the principle of H would be multiplied with the plain text?

2. P in the plain text, but no matter how long this is, only the first 128 bits of the plain text will be multiplied with H?

Later, it is stored in the vector, but it is being overwritten by what I see in the division of i / 2?

Answer 1

$M$ is a table with 256 elements, where each element has 16 bytes (128 bits), such that $M[x]$ is equal to $x \cdot H$

In the first step, the 128-th element is set to $H$, i.e. $M[128] = H$. The reason for that is the confusing bit order convention of GCM (see What does GHASH really do?). GCM works with binary polynomials, and the polynomial $1$ is represented, as a byte, as the integer value $128$ (e.g. $1000000$ in binary) instead of of $1$ (e.g. $00000001$ in binary). Therefore, what the first step is doing is setting $M[1] = H$, if GCM were defined with a more conventional bit order.

The rest of your confusion probably arises from the same issue. So anywhere you see $M[i]$ in the algorithm, pretend it's $M[rev(i)]$ where $rev$ reverses the bits of the input, and things may start to make more sense.

Also, $P$ is not the plaintext, it's the polynomial $\alpha$ (i.e. $010000...0$)