13
$\begingroup$

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.

$\endgroup$
17
$\begingroup$

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

| improve this answer | |
$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Melvin Jan 17 '14 at 2:08
  • 1
    $\begingroup$ 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. $\endgroup$ – Ilmari Karonen Sep 21 '16 at 13:58
  • 2
    $\begingroup$ @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? $\endgroup$ – fgrieu Sep 22 '16 at 6:44
  • 3
    $\begingroup$ @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. $\endgroup$ – poncho Sep 22 '16 at 14:39
  • 1
    $\begingroup$ 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. $\endgroup$ – Ilmari Karonen Sep 24 '16 at 20:05
6
$\begingroup$

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.

| improve this answer | |
$\endgroup$
4
$\begingroup$

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

| improve this answer | |
$\endgroup$
  • $\begingroup$ can you give any of the inversion algorithm? $\endgroup$ – Melvin Jan 17 '14 at 2:10
  • $\begingroup$ 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? $\endgroup$ – Melvin Jan 17 '14 at 10:49
  • 1
    $\begingroup$ 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. $\endgroup$ – tylo Jan 17 '14 at 16:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.