AES

[mebob]

for my own satisfaction, im trying to make a program that does AES encryption, but ive run into a problem: i cant find an efficient way to us the s-box, and i would rather not have a switch statement with 256 cases. what could i do to do this effieciently.

[Dave Sinkula]

Hash table?

[mebob]

no, the aes s-box, used in the SubBytes step: http://edipermadi.files.wordpress.com/2008/03/sbox.png

[Salem]

It looks like an array with 256 entries to me.

[mebob]

ok, ive figured out more about this. now i need to know how to find the multiplicative inverse of a number in the field GF(2^8).

[robertl2]

If you trying to find Rcon you can do that with a lookup table, I think there's one posted on Wikipedia. To find those values yourself you need to handle really big numbers ( 2^200 and something ).

If your talking about the Mix-Columns step you need to preform matrix multiplication of some matrix, a, in GF(2^8) such that...

{ 2, 3, 1, 1; 1, 2, 3, 1; 1, 1, 2, 3; 3, 1, 1, 2 } * { a00, a01, a02, a03; a10, a11, a12, a13; a20, a21, a22, a23; a30, a31, a32, a33; } = { b00, b01 .... }

Ultimately you would have
b00 = 2*a00 + 3*a10 + 1*a20 + 1*a30
where the addition is just an xor and the multiplication is preformed in GF(2^8). This multiplication is polynomial multiplication (mod 2) modulo the polynomial x^8 + x^4 + x^3 + x + 1. You can implement this either logarithmically with a lookup table or you can do it the crazy-ass way I did it.

int mod ( int a, int b = 283 ) {
while ( a >= 256 ) {
int product = b;
while ( product < a/2 ) { product = product*2;}
a = a ^ product;
} return a;
}

int polyMod2 ( int a, int b, int N = 8 ) {
int sum = 0;
for ( int i = 0; i < N; ++i ) {
int place = pow ( 2, (N-1)-i );
if ( a >= place ) { sum = sum ^ b*place; a -= place; }
} return sum;
}

int ga ( int a, int b ) {
return mod ( polyMod2 ( a, b ) );
}

Doing it logarithmically would probably be smarter, but I like it this way because this is, more or less, how you would actually do it on paper.

To Un-Mix the Columns you do the same thing, but with the inverse matrix { 14, 11, 13, 9; ... }