Calculating AES Round Constants

Question

I am attempting to calculate the round constants used in AES. Using the formula found on Wikipedia's Rijndael Key Schedule page results in answers that the same page says are correct, but the primary source for my current project gives a different formula, so I feel like I might be missing something.

The formula given is: $r(i) = x^{(i-4)/4} mod (x^8+x^4+x^3+x+1)$ where $i$ is the current round. It seems to me that this formula and the one listed on the Wikipedia page for Rcon, which I'm assuming is short for "round constant," have the same purpose, but one uses values four times as high. For reference, the Wikipedia function is $Rcon(i) = b^{i-1}$ in $GF(2^8)$.

The project requires that I calculate the value of r for all i divisible by 4 from 4 to 40. My solutions for 4 to 32 match the values given for Rcon(1) to Rcon(8) (01 to 80) in the linked article.

My understanding is that the modulus operator is here applied in a manner equivalent to an XOR operator, which seems to hold if the above is correct, as it results in r(36) = 0x1B, which is given as the value of Rcon(9) in the linked article.

What is the use of the two functions given in paragraph 2, and why would two separate functions be necessary in this application?

Answer 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.

Answer 2

Here's a way with Rust to calculate the round constant depending on the round index:

fn rcon(index: u8) -> u8 {
    // We start with 0xCB because left shifting and reducing it
    // produces 0x8D, the result of rcon(0), which when left-shifted and
    // reduced again, is 0x01.
    // And 0x01 is the correct result of rcon(1).
    let mut rcon: u16 = 0xCB;

    // If index is 0, we do this once
    for _ in 0..=index {
        rcon <<= 1;

        // If rcon is greater than a byte, we reduce with 0x11B to stay inside
        // Rijndael's Galois field
        if rcon > 0xFF {
            rcon ^= 0x11B;
        }
    }
    rcon as u8
}

#[test]
fn rcon_works() {
    // The NIST standard says that the index starts
    // at 1, but other implementations also produce a value
    // for rcon(0)
    assert_eq!(0x8d, rcon(0));
    assert_eq!(0x01, rcon(1));
    assert_eq!(0x02, rcon(2));
    assert_eq!(0x04, rcon(3));
    assert_eq!(0x08, rcon(4));
    assert_eq!(0x10, rcon(5));
    assert_eq!(0x20, rcon(6));
    assert_eq!(0x40, rcon(7));
    assert_eq!(0x80, rcon(8));
    assert_eq!(0x1B, rcon(9));
    assert_eq!(0x36, rcon(10));
}