Incorrect Multiplication/Division in Galois Field (2^8)

Question

I'm attempting to implement multiplication and division in GF(2^8) using log and exponential tables. I'm using the exponent of 3 as my generator, using instructions from here.

However I'm failing some trivial test cases.

example:

//passes  
assert((GF256elm(4) / GF256elm(1)) == GF256elm(4));  
assert((GF256elm(32) / GF256elm(16)) == GF256elm(2));  
assert((GF256elm(15) / GF256elm(5)) == GF256elm(3));  
assert((GF256elm(88) / GF256elm(8)) == GF256elm(11));  
//fails, but should pass
assert((GF256elm(77) / GF256elm(11)) == GF256elm(7));
assert((GF256elm(77) / GF256elm(7)) == GF256elm(11));  

The first four line passes, however it fails on both 5th and 6th line.
Upon further investigation I found out that these error occur when there is a 'wrap over', i.e. log3(a) + log3(b) > 255 (multiplication case) or log3(a) - log3(b) < 0. However the value is "modded" such that they remain in 0~255 using true modulus.

GF256elm& GF256elm::operator/=(const GF256elm& other) { //C++ operator override for division
    int t = _logTable[val] - _logTable[other.val]; //log3(a) - log3(b)
    int temp =  ((t % 255) + 255) % 255; //this wraps the value to between 0~254 inclusive.
    val = _expTable[temp];
    return *this;
}

the / operator is implemented using the /= override above so nothing special happens there.

I have checked that the generated log/exp tables are correct.

What am I missing here? Thanks!

Answer 1

There is nothing wrong with the code. Finite field multiplication/division is different from normal arithmetic. Please refer to this question in cryptostackxchange.

Answer 2

First, read this question and all its answers and comments carefully:

Addition and multiplication in a Galois Field

I think your code is OK, but you have two problems.

First, the comments are wrong; you are keeping the exponent in the range 0-254, not 0-255.

Second, your "trivial" test cases are wrong.

In this field, think of numbers as polynomials whose coefficients you get from the binary representation of the number. For example, since 5 = 2^2 + 1, in this field "5" means x^2 + 1.

So "5" * "3" = (x^2 + 1) * (x + 1) = x^3 + x^2 + x + 1, or "15". This is why your test case assert((GF256elm(15) / GF256elm(5)) == GF256elm(3)); works. It has nothing to do with your usual notion that five times three equals fifteen. Similarly for your other working test cases, which you will notice mostly involve powers of two.

However, "7" * "11" = (x^2 + x + 1) * (x^3 + x + 1) = x^5 + x^4 + 2x^3 + 2x^2 +2x + 1

But the coefficients are all modulo 2, so this is actually x^5 + x^4 + 1 = "49". This is why your last two test cases fail.

If you try assert(GF256elm(49) / GF256elm(7) == GF256elm(11)); you should find it checks out.

Answer 3

x % n evaluates to an integer between 0 and (n - 1), inclusive.

This means that x % 255 evaluates to an integer between 0 and 254, not 0 and 255.

You should replace 255 with 256, or alternatively, perform a bitwise AND with 0xff for the same result. The latter is faster, though it is quite likely that compilers are smart enough to optimize them to the same bytecode.