2

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!

Community
  • 1
  • 1
Jacob Wang
  • 4,411
  • 5
  • 29
  • 43
  • My apologies. yes I have implemented it and should've mentioned it. It's basically just uses the `/=` on the LHS and RHS terms and return the result so nothing fancy there. edited my answer. – Jacob Wang Aug 25 '13 at 12:49

3 Answers3

4

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.

Community
  • 1
  • 1
Nemo
  • 70,042
  • 10
  • 116
  • 153
  • I know (and intentionally) put it in the range of 0~254, as explained in my comment. Thanks for explaining the concept of multiplication in finite field. I have indeed put down bad test cases due to my lack of understanding of finite fields. – Jacob Wang Aug 26 '13 at 05:15
  • @jtcwang but the comment in your _code_ says `//this wraps the value to between 0~255` – gx_ Aug 26 '13 at 16:18
  • will fix. Thanks for spotting – Jacob Wang Sep 06 '13 at 04:03
0

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.

ntoskrnl
  • 5,714
  • 2
  • 27
  • 31
  • 1
    By the way, this is true not only for C++ `%` but for integer division remainder (modulo) in general. Precision: when `x` is signed (e.g. `int x`), `x % 255` can evaluate to an integer between -254 and 254 (inclusive) (that's why OP's code is `((t % 255) + 255) % 255` and not simply `t % 255`). – gx_ Aug 25 '13 at 11:45
  • 2
    I have tried that before but it doesn't work. With my finite understanding of GF(2^8), the pattern of exp/log table repeats on the 255th element. i.e. element [1] is the same as [255], thus doing 255 modulus. – Jacob Wang Aug 25 '13 at 11:49
0

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

Community
  • 1
  • 1
Jacob Wang
  • 4,411
  • 5
  • 29
  • 43