# Multiplicative inverse in $\operatorname{GF}(2^8)$?

I know how to do multiplication over ${\rm GF}(2^8)$:

uint8_t  gmul(uint8_t  a, uint8_t  b)
{
uint8_t p=0;
uint8_t carry;
int i;
for(i=0;i<8;i++)
{
if(b & 1)
p ^=a;
carry = a & 0x80;
a = a<<1;
if(carry)
a^=0x1b;
b = b>>1;
}
return p;
}


So, I tried to create a ${\rm GF}(2^8)$ multiplication table using this code. I've given below the values in the 3rd row of the table, but I don't think they're correct:

    0  1  2  3  4  5  6  7   8  9  A  B  C  D  E  F
0
1
2   0  2  4  6  8  A  C  E  10 12 14 16 18 1A 1C 1E
3
.
.
E
F


I don't know what went wrong. I built the table by multiplying the values in the first row with those in the first column. E.g. in the third row, I multiplied 2 × 0, 2 × 1, …, 2 × E, 2 × F.

How can I create a multiplication table for arithmetic in ${\rm GF}(2^8)$?

Also, how can I find the multiplicative inverse of a number in ${\rm GF}(2^8)$?

For example, how can I determine that the inverse of 95 is 8A? I tried to do this using the multiplication table above, but when I took 9th row and the 5th column in the multiplication table I got 2D, not 8A.

The standard method for doing multiplication (and multiplicative inverses) in $\operatorname{GF}(2^8)$ is using a log and antilog table. Each table takes up only 255 bytes; hence it is much smaller than a full $256 \times 256$ multiplication table, and it is much faster than the multiplication procedure you give above.

To create such tables, we need to pick a generator $g$; that is a field element such that $g^i$ is all 255 nonzero elements for $0 \le i < 255$ (where $g^i$ is what you would expect; $g$ multiplied by itself $i$ time). Such an element always exists, and (IIRC) $g=3$ happens to be a generator in the field representation you are using.

Now, the antilog table is defined as:

$${\rm antilog}(i) = g^i$$

This table has 255 elements, and can be easily built using your multiplication procedure. You may want to extend it farther (as discussed below); it just continues in the obvious way (and it just repeats itself).

The log table is defined as its inverse, that is:

$$\log(\operatorname{antilog}(i)) = i$$

This table also has 255 elements (but is indexed from 1 to 255), and can be built using the antilog table we already have, or just initialized at the same time:

uint8_t log_table, antilog;
const uint8_t g = 3;

void init_log_table(void)
{
log_table = 0;  /* dummy value */
for (int i = 0, x = 1; i < 255; x = gmul(x, g), i++) {
log_table[x] = i;
antilog[i] = x;
}
}


Once we have those two, we can do multiplication by:

uint8_t gmul_table(uint8_t a, uint8_t b)
{
if (a == 0 || b == 0) return 0;

uint8_t x = log_table[a];
uint8_t y = log_table[b];
uint8_t log_mult = (x + y) % 255;

return antilog[log_mult];
}


This works because, if $a = g^x$ and $b = g^y$, then $a \times b = g^x \times g^y = g^{x+y} = g^{(x+y) \bmod 255}$

As you can see, that should be considerably more efficient than your original algorithm; you can omit the % 255 operation by extending the antilog table for 255 more elements.

We can also use those tables to compute multiplicative inverses:

uint8_t ginv_table(uint8_t a)
{
if (a == 0) return 0;       /* as needed in the context of AES */

uint8_t x = log_table[a];   /* x       is in range [0..255] */
uint8_t log_inv = 255 - x;  /* log_inv is in range [0..255] */

return antilog[log_inv];
}


You can also compute inverses using the Extended Euclidean Algorithm (which can be adapted to work in $\operatorname{GF}(2^8)$; however it's considerably more work than two table lookups.

Here is how that algorithm would look like:

uint8_t ginv(uint8_t x)
{
uint16_t u1 = 0, u3 = 0x11b, v1 = 1, v3 = x;

while (v3 != 0) {
uint16_t t1 = u1, t3 = u3;
int8_t q = bitlength(u3) - bitlength(v3);

if (q >= 0) {
t1 ^= v1 << q;
t3 ^= v3 << q;
}
u1 = v1; u3 = v3;
v1 = t1; v3 = t3;
}

if (u1 >= 0x100) u1 ^= 0x11b;

return u1;
}


where bitlength(x) returns the position of the most significant 1 bit of x (i.e. the smallest number y such that (1 << y) - 1 >= x).

• i included "#include<math.h>" then too i get the following error- undefined reference to antilog'. can you explain(with code)how to compute using euclidean algorithm. i know the extended euclidean alogorithm, but don't know how to implement in binaries? – Melvin Jan 17 '14 at 2:08
• I just edited your generally excellent answer to add some explicit code for building the log and antilog tables; please do revert or edit it if you don't like my changes. Also, just for completeness, here's a quick little test program showing that this code indeed works, and that the table-based implementations give the same results as the non-table-based ones. – Ilmari Karonen Sep 21 '16 at 13:58
• @poncho: I'm puzzled by the use of q = numbits(z) , defined as the number of bits set in z(for example, q=1 for z=8); can you explain? – fgrieu Sep 22 '16 at 6:44
• @fgrieu: well, we're trying to figure out how many bits to shift v3 left so that v3<<q cancels out the msbit of u3. x is u3 will all the bits to the right of the msbit set (so if u3 = 0x12, then x = 0x1f); similarly y is v3 with all the bits to the right of the msbit set. Because of this, z will consist of those bits where there's a bit set to the left in u3, but not in v3. Hence, the number of such bits is the number of bits we need to shift v3 left. – poncho Sep 22 '16 at 14:39
• Thanks for the reply to @fgrieu's comment above. To be honest, the bit fiddling and counting confused me too, but your explanation made it clear. Based on it, I took the liberty of rewriting your ginv() code to use a bitlength() function/macro instead, hopefully making the actual algorithm clearer (and probably faster too, at least on platforms that have a built-in bit length / leading zero count instruction). And yes, I checked that it still works. – Ilmari Karonen Sep 24 '16 at 20:05

The question's gmul code correctly computes $$A*B$$ with each of $$A$$ and $$B$$ any of the $$256$$ elements of $$\operatorname{GF}(2^8)$$. But notice that the multiplication table shown has $$16\times16$$ entries, a very small subset of the full table with $$256\times256$$ entries.

One way to compute the multiplicative inverse $$A^{-1}$$ is as $$B=A^{254}$$, which works because $$A*B=A*A^{254}=A^{255}=1$$ since the order of the multiplicative subgroup is $$2^8-1=255$$.

/* modular inverse, computing a^^254 using exponentiation by squaring */
uint8_t ginv(uint8_t a) {
uint8_t j, b = a;
for (j = 14; --j;)              /* for j from 13 downto 1 */
b = gmul(b, j&1 ? b : a);   /* alternatively square and multiply */
return b;
}


This can be reduced from 13 to 11 field multiplications with an addition chain, code in this Try It Online!, also illustrating a typically constant-time and faster gmul.

As explained in poncho's answer, there are more efficient ways to perform multiplication, and inverse, using two tables for log and antilog; and the inverse can also be built using the extended Euclidean algorithm. Beware that both lead to typically non-constant-time code, which can make an implementation vulnerable to timing attack.

As explained in Dmitry Khovratovich's answer, one could find the inverse of any non-zero $$A$$ by systematically looking for which $$B$$ it holds that $$A*B=1$$, which will require attempting at worse $$255$$ non-zero values of $$B$$. This is OK for building the table of inverses once for all, but that can be optimized to:

/* build table of inverses, using generator 0x03 of inverse 0xf6 */
uint8_t ginvt;          /* table of inverses */
void gbuildt(void) {
uint8_t i = 1, j = 1;   /* i and j are inverses */
for(;;) {               /* loop */
ginvt[i] = j;
i = gmul(i, 0x03);
if (i==j) break;    /* ends met */
j = gmul(j, 0xf6);
ginvt[j] = i;
}
ginvt = 0;           /* table's entry for 0 is 0 */
}


This uses a known generator 0x03 and its inverse 0xf6. It builds their respective powers until they meet. The loop is performed 127 times, for a total of 255 field multiplications. Try It Online!

Notice that the reduction binary polynomial $$x^8+x^4+x^3+x+1$$ is irreducible (as it must be) but not primitive, thus 0x02 is not a generator (which inverse is just the reduction polynomial 0x11b` right-shifted by one).

In the general case of $$\operatorname{GF(2^n)}$$, the cost of building the table by the above technique is asymptotically a single field multiplication and assignment per entry in the table, including the cost of finding a generator and it's inverse, as follows:

• We can test if an element $$g$$ is a generator by checking $$g^{(2^n-1)/p}\ne1$$ (computable using exponentiation by squaring with less than $$2n$$ field multiplications) for each prime $$p$$ dividing $$2^n-1$$ (starting with the lowest $$p$$ for efficiency). The cost of factoring $$2^n-1$$ is negligible since we have sub-exponential factoring algorithms, and especially good ones for Mersenne numbers. We know these factorizations for all $$n<929$$.
• Each $$g$$ tested has probability $$>1/2$$ to be a generator, so we test less than two $$g$$ on average, and conjecturally less than $$2+\log_2 n$$ when we try $$g$$ per the sequence of binary irreducible polynomials (OEIS A014580), which first terms are $$\mathtt{02_h}$$, $$\mathtt{03_h}$$, $$\mathtt{07_h}$$, $$\mathtt{0b_h}$$, $$\mathtt{0d_h}$$, $$\mathtt{13_h}$$, $$\mathtt{19_h}$$, $$\mathtt{1f_h}$$
• When we get $$g$$, it's inverse can be found as $$g^{2^n-2}$$, with less than $$2n$$ field multiplications.

The technique could be useful e.g. to build a 16 GiB table of inverses in $$\operatorname{GF}(2^{32})$$ (or S-table based on that), without additionally requiring the log and antilog tables of poncho's answer, which eat an additional 32 GiB.

The multiplication table has $2^8 = 256$ rows and columns. You are doing the multiplication right, but you have not filled the entire third row yet (there must be 256 elements).

To find the inverse of $A$, you find $B$ such that $A*B = 1$ in your multiplication table (there are other algorithms for inversion, but you might not need them for such a small field).

• can you give any of the inversion algorithm? – Melvin Jan 17 '14 at 2:10
• inverse of 95 is 8A. but when i took 9th row and 5th column in multiplication table i got 2D. So A*B !=1. then how to fidn out inverse of 95? – Melvin Jan 17 '14 at 10:49
• You have a multiplication table. And you look for entries $9$ and $5$. That means you compute a value $9\cdot 5= 2D$ (or 45 in decimal). This has nothing to do with the inverse of $95$. If you have a full multiplication table, then you look at row $95$, and find in this row the entry "1". The column of this entry is the inverse element. Btw as others said before, $GF(2^8)$ has 256 elements, not 16. – tylo Jan 17 '14 at 16:39