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

Question

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.

Answer 1

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[256], antilog[255];
const uint8_t g = 3;

void init_log_table(void)
{
    log_table[0] = 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).

Answer 2

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[256];          /* 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] = 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.

Answer 3

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).