AES SubBytes step

This is a discussion on AES SubBytes step within the Tech Board forums, part of the Community Boards category; Hello I'm having some problems implementing AES's SubBytes routine. Instead of using tables id like to do it myself. I ...

  1. #1
    Registered User
    Join Date
    May 2006
    Posts
    57

    AES SubBytes step

    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

  2. #2
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,274
    Quote Originally Posted by zxcv View Post
    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.

  3. #3
    Registered User
    Join Date
    May 2006
    Posts
    57
    *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.

  4. #4
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,274
    Quote Originally Posted by zxcv View Post
    *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?

  5. #5
    Registered User
    Join Date
    May 2006
    Posts
    57
    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

  6. #6
    Registered User
    Join Date
    May 2006
    Posts
    57
    Heres multiplication if anyone is curious:
    Code:
    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;
    }

  7. #7
    Registered User
    Join Date
    Jul 2008
    Posts
    1
    Code:
    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

  8. #8
    Registered User
    Join Date
    Oct 2010
    Posts
    3
    Hi there,
    Could u explain how u get to this part?
    Code:
    while(mult(in,result) > 1) {
    		result++;
    	}
    Surely it must be less (<) than 1 instead of >;

    thanks.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 16
    Last Post: 11-23-2007, 01:48 PM
  2. recursion
    By paulmedic555 in forum C Programming
    Replies: 26
    Last Post: 01-28-2005, 12:43 AM
  3. robot step sizes
    By n00by in forum C Programming
    Replies: 2
    Last Post: 04-29-2004, 04:29 PM
  4. step by step debug != run debug
    By bonkey in forum Windows Programming
    Replies: 8
    Last Post: 09-09-2002, 01:55 PM
  5. this sites Compiler Resources Specs.
    By Powerfull Army in forum C++ Programming
    Replies: 9
    Last Post: 07-08-2002, 07:12 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21