AlliedModders

AlliedModders (https://forums.alliedmods.net/index.php)
-   Scripting Help (https://forums.alliedmods.net/forumdisplay.php?f=11)
-   -   Modulo is wrong!? (https://forums.alliedmods.net/showthread.php?t=5766)

Anpheus 09-12-2004 02:50

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

BAILOPAN 09-12-2004 04:23

why are you doing this in small

make a module, that's what the nice new SDK is for

Anpheus 09-12-2004 10:47

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.