Calculating AES Round Constants

Solution 1:

GF(2) polynomials represent rings of numbers. As an example, the mapping of coefficients to numbers for $\mathtt{x^2+x+1}$ is given by the following table:

\begin{array} {|r|r|r|} dec & bin & polynomial\\ \hline 0 & 000 & 0 \\ 1 & 001 & 1 \\ 2 & 010 & x \\ 3 & 011 & x+1 \\ 4 & 100 & x^2 \\ 5 & 101 & x^2+1\\ 6 & 110 & x^2+x\\ 7 & 111 & x^2+x+1 \\ \end{array}

AES uses the same irreducible polynomial for everything, which is $\mathtt{x^8+x^4+x^3+x+1}$. This polynomial results in 9 bits, and is 0x11B in hexadecimal, or 100011011 in binary. You will notice that the 9 bits are one bit more than you have in an 8-bit byte, and this allows the modulus to be the XOR of 0x1B, instead of 0x11B. The prefix of the RCON value is actually just 0x01 starting at round 1, which is just shifted left.

To create the AES round constants in C, see the following program that I hastily made:

#include <stdint.h>    /* to be sure the bit widths are correct*/
#include <stdio.h>     /* for printf */

typedef uint8_t u8;
typedef uint32_t u32;

int main () {
u32 i;
u8 x=0xcb;
u8 val=0;
  for(i = 0; i < 11; i++)
  {
     if(x & 0x80)
     {
        x=(x<<1);
        x=x^0x1B;
        val=0x1B;
     }else
     {
        x=(x<<1);
        x=x^0x00;
        val=0x00;
     }
   fprintf(stdout,"%02i: 0x%02x 0x%02x\n",i,val,x);
  }
return(0);
}

You will notice in the program that you check the value of the high bit of the byte x before the shift via (x & 0x80), and then calculate the XOR if true. This program results in the following output:

00: 0x1b 0x8d
01: 0x1b 0x01
02: 0x00 0x02
03: 0x00 0x04
04: 0x00 0x08
05: 0x00 0x10
06: 0x00 0x20
07: 0x00 0x40
08: 0x00 0x80
09: 0x1b 0x1b
10: 0x00 0x36

Where the first column is the round count, the second column is the XOR mask (ie: the modular division via subtraction because you can never get larger than the AES polynomial) and the final column is the AES round constant.