11
$\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$
13
$\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).

$\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
  • $\begingroup$ Actually, log and antilog are tables that you build (or initialize); they're uint8_t log[255], antilog[255]; (and, come to think about it, in C, log isn't the best name; it conflicts with the log() function within math.h). You initialize those tables as above (possibly using your multiplication routine to generate the initial antilog entries) $\endgroup$ – poncho Jan 17 '14 at 2:29
  • 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
  • 1
    $\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
  • 1
    $\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
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).

$\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
4
$\begingroup$

The question's code for multiplication 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 group is $255$. We can compute $A^{254}$ using $13$ multiplications with exponentiation by squaring (we successively compute $A$ raised to the powers $2$, $3$, $6$, $7$, $14$, $15$, $30$, $31$, $62$, $63$, $126$, $127$, $254$). This can be reduced to $11$ multiplications with an addition chain (we successively compute $A$ raised to the powers $2$, $3$, $6$, $12$, $24$, $48$, $51$, $63$, $126$, $127$, $254$).

The code can be as simple as

/* 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;
}

As explained in Dmitry Khovratovich's answer, you 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 fine for building the table of inverses once for all.

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.

$\endgroup$
-3
$\begingroup$

int mul(int t1,int t2)

{

int i,j,a[9]={0},v1,v2;

for(i=t2;i>0;i=i-pow(2,lg(i)))

for(j=t1;j>0;j=j-pow(2,lg(j)))

a[lg(i)+lg(j)]+=1;

for(i=0;i<9;i++)

a[i]=a[i]%2;

return b2d(a);//Binary to decimal

}

int lg(int n)//log base 2

{

int a;

a=log10(n)/log10(2);

return a;

}

int b2d(int *p)

{

int i=-1,s=0;

while(i<8)

{

i++;

if(p[i]==1)

s=s+pow(2,i);

}

$\endgroup$
  • $\begingroup$ say t2 is 9 and t1 is 7.x^3+x^0 (x^0 is obviously 1) or 3 0 in similar context 7 is 2 1 0 .now for every bit 9,7 is multiplied[i'm using an array.so in my case,it added].then 5 4 3 and 2 1 0 together it is 5 4 3 2 1 0 or 63. extracted from 7*9(1001)=7*2^3 XOR 7*2^0 $\endgroup$ – Jai Mar 9 '17 at 16:04
  • $\begingroup$ Hi, Jai, and welcome to Cryptography Stack Exchange. Unfortunately, answers that consist of nothing but an unexplained code dump are not generally considered useful here. You may want to take a look at our guidance on writing good answers, or just browse our highest voted answers to see some examples of what a really good answer should look like. (In any case, this question has already been answered pretty well. If you think your code improves upon the existing answers in some way, you should note that explicitly in your answer.) $\endgroup$ – Ilmari Karonen Mar 9 '17 at 17:51

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.