Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.
  1. I know how to do multiplication over $GF(2^8)$.
    Logic is...

    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 created arithmetic in a $GF(2^8)$-Multiplication table. Given below the values in the 3rd raw, but I don't think it is true. I don't know what went wrong.

    I multiplied first raw value with first column values.
    Eg: in the third row, I multiplied 2*0, 2*1,.....2*e, 2*f.

        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
    

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

  2. How can I find the multiplicative inverse in $GF(2^8)$.
    Eg: the inverse of (95) = 8A?

share|improve this question

2 Answers 2

The standard method for doing multiplication (and multiplicative inverses) in $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:

$$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:

$$antilog(log(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.

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(a);
        uint8_t y = log(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;   /* Error */

        uint8_t x = log(a);
        uint8_t log_inv = (255 - x) % 255;

        return antilog(log_inv);
    }

You can also compute inverses using the Extended Euclidean Algorithm (which can be adapted to work in $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, u3, v1, v3;

        u1 = 0; u3 = 0x11b;
        v1 = 1; v3 = x;

        for (;;) {
            uint16_t t1, t3, x, y;

            if (v3 == 0) break;

            x = u3; x |= x>>1; x |= x>>2; x |= x>>4;
            y = v3; y |= y>>1; y |= y>>2; y |= y>>4;
            if (x >= y) {
                uint16_t z = x & ~y;
                uint8_t q = numbits(z);
                t1 = u1 ^ (v1<<q);
                t3 = u3 ^ (v3<<q);
            } else {
                t1 = u1;
                t3 = u3;
            }
            u1 = v1; u3 = v3;
            v1 = t1; v3 = t3;
        }

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

        return u1;
    }

(where numbits(x) returns the number of bits set in x)

share|improve this answer
    
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 at 2:08
    
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) –  poncho Jan 17 at 2:29
    
k will do, but can you show me code using extended euclidean algorithm to show multiplicative inverse? –  Melvin Jan 17 at 3:12
    
hot to create antilog(log_inv) function? you said to create uint8_t log[255] which is an array,then how will antilog(log_inv)call will work? how to implement it? if any other ways are there please show me –  Melvin Jan 17 at 10:57

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

share|improve this answer
    
can you give any of the inversion algorithm? –  Melvin Jan 17 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 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 at 16:39

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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