Raised This Month: $ Target: $400
 0% 

Modulo is wrong!?


  
 
 
Thread Tools Display Modes
Prev Previous Post   Next Post Next
Author Message
Anpheus
Senior Member
Join Date: Aug 2004
Old 09-12-2004 , 02:50   Modulo is wrong!?
Reply With Quote #1

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}
Anpheus is offline
 



Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off

Forum Jump


All times are GMT -4. The time now is 17:26.


Powered by vBulletin®
Copyright ©2000 - 2024, vBulletin Solutions, Inc.
Theme made by Freecode