Modulo is wrong!?
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:
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} |
why are you doing this in small
make a module, that's what the nice new SDK is for |
I've never done C++ before.
Edit, I just looked at my JASS implementation. I should have read further ahead in the doc: function MultGF takes integer A, integer B returns integer local integer i = 7 local integer C = 0 local integer z loop exitwhen i < 0 if ( B >= udg_Pow[i] ) then set B = B - udg_Pow[i] set C = XORBIN(C,udg_Pow[i]*A) endif set i = i - 1 endloop loop exitwhen C < 256 set z = 16 loop exitwhen C - udg_Pow[z] >= 0 set z = z - 1 endloop set C = XORBIN(C,283*udg_Pow[z-8]) endloop return C endfunction They use funky mod :-) to make sure its in the field gf(2^8) |
| All times are GMT -4. The time now is 17:26. |
Powered by vBulletin®
Copyright ©2000 - 2024, vBulletin Solutions, Inc.