AES SubBytes step

[zxcv]

Hello

I'm having some problems implementing AES's SubBytes routine. Instead of using tables id like to do it myself.

I can do the affine transformation fine, I'm just not sure how to go about getting the inverse that I need for it. The AES spec explains multiplication but I didn't notice anything about division, so I guess that means doing it with the Extended Euclidean Algorithm is out.

Is there a easy and efficient way to go about this, without tables?

Thanks

[brewbuck]

Hello

I'm having some problems implementing AES's SubBytes routine. Instead of using tables id like to do it myself.

Good luck. If you can crack the tables (by finding a non-table based implementation of SubBytes), then you've cracked AES.

Unless you are a prodigy working for NSA, I doubt you'll be able to.

The entire strength of AES comes from these S-boxes.

[zxcv]

*sigh* no, not at all...

Its described in the spec, I just don't know quite enough about the fields to do it myself. Theres no magic anywhere in the spec...

No genius needed at all.

[brewbuck]

*sigh* no, not at all...

Its described in the spec, I just don't know quite enough about the fields to do it myself. Theres no magic anywhere in the spec...

No genius needed at all.

Maybe I misunderstood then. What exactly are you attempting to do? Generate the S-box values themselves or something else?

[zxcv]

Yeah, thats it.

I want to generate the Sbox values myself, without using a table. The transform is easy enough but I'm not sure how I can get the inverse without first learning division.

For the multiplication theres a handful of nice and optimized algorithms just for the 2^8 case needed by AES, I cant seem to track one down for inverses or division(although I could fake it if i had too).

Thanks

[zxcv]

Heres multiplication if anyone is curious:

unsigned char mult(unsigned char a, unsigned char b) {
	int i;
	int retval = 0;
	
	for(i = 0; i < 8; i++) {
		if((b & 1) == 1) 
			retval ^= a;
		
		if((a & 0x80) == 0x80) {
			a <<= 1;
			a  ^= 0x1b;
		} else {
			a <<= 1;
		}
		
		b >>= 1;
	}
	
	return (unsigned char)retval;
}

[Jim Tremblay]

static unsigned char sbox[256];
static unsigned char inv_sbox[256];

static unsigned char mul_inv(unsigned char in)
{
	unsigned char result;

	if(in == 0)
		return(0);

	result = 1;
	while(mult(in,result) > 1) {
		result++;
	}
	return(result);
}

static void calc_sbox(void)
{
	unsigned short i,j;
	unsigned char x,y;

	for(i=0; i<256; i++) {
		x = mul_inv((unsigned char)i);

		y = x;
		for(j=0; j<4; j++) {
			y = (y >> 7) | (y << 1);
			x ^= y;
		}
		x ^= 0x63;

		sbox[i] = x;
	}
}

static void calc_inv_sbox(void)
{
	unsigned short i;

	for(i = 0; i < 256; i++) {
		inv_sbox[sbox[i]] = i;
	}
}

With this code, you will generate sbox and inv_sbox at the run time. It's possible to substitute the byte you want at run time without ram tables, but you will loose performance. For reference, you can check this link: http://www.mediatronix.com/examples/Rijndael-3.htm.

I hope this will help you.

Jim

[akeel88]

Hi there,
Could u explain how u get to this part?

while(mult(in,result) > 1) {
		result++;
	}

Surely it must be less (<) than 1 instead of >;

thanks.