In my so-far implementation of Rijndael, I encountered a problem while making the finite field multiplication function.
That is, I encountered a problem in that what would normally work in the laws of mathematics is not applying.
The text at
http://csrc.nist.gov/publications/fi...7/fips-197.pdf clearly states the result of {57} * {83} (or in decimal, 87 * 131) in the gallois field 2^8
must return 193. This is given by the polynomial, where x = 10 (in binary)
(x^6 + x^4 + x^2 + x + 1)(x^7 + x + 1) = x^13 + x^11 + x^9 + x^8 + x^7 + x^5 + x^3 + x ^ 2 + x + x^6 + x^4 + x^2 + x + 1
Then, with the right side reduced:
x^13 + x^11 + x^9 + x^8 + x^6 + x^5 + x^4 + x^3 + 1
This can reduced, and put in binary, as:
(101 0111)(1000 0011) = (10 1011 0111 1001)
However, this is modulo the (and they put lots of emphasis on these words) irreducible polynomial: x^8 + x^4 + x^3 + x + 1 (which is in binary, 1 0001 1011, and in decimal, 283, and in hexadecimal, 0x011B)
Now, my function has debug tags like so:
Code:
public GF28(id,Byte1, Byte2) {
new Product
for ( new x = 0; x < 8; x++ ) {
client_print(id, print_chat, "Operation: %d * %d xor %d = %d^n", Byte1, Byte2 & (1 << x), Product, Product ^ (Byte1 * (Byte2 & (1 << x))) )
if ( (Byte2 >>> x) & 1 ) Product ^= Byte1 << x
}
client_print(id, print_chat, "Product: %d mod 283 = %d", Product, Product % 283)
return Product % 283
}
And it prints the correct data:
Operation: 87 * 1 xor 0 = 87
Operation: 87 * 2 xor 87 = 249
Operation: 87 * 0 xor 249 = 249
Operation: 87 * 0 xor 249 = 249
Operation: 87 * 0 xor 249 = 249
Operation: 87 * 0 xor 249 = 249
Operation: 87 * 0 xor 249 = 249
Operation: 87 * 128 xor 249 = 11129
Product: 11129 mod 283 = 92
Now, here's the clincher. 11129 mod 283 = 92 is a true statement. However...
11129 is in binary: 10 1011 0111 1001
And, it clearly states in the document that
(101 0111)(1000 0011) = (10 1011 0111 1001)
Just POSSIBLY assuming I'm wrong, I did this in calc:
10^13 + 10^11 + 10^9 + 10^8 + 10^6 + 10^5 + 10^4 + 10^3 + 1 =
10 1011 0111 1001
So, how is my 11129 mod 283 different from THEIR 11129 mod 283?
Mine: Mod returns 92. Document: 193 or {C1}