3. The Key Expansion Part 3: Rcon

The last helper function Rcon takes an integer as input, and gives back an array of 4 bytes with the 3 least significant bytes set to 0.

Here comes the tricky part.

AES operates some of its transformations in the Finite Field GF(2^8) defined with the polynomial X^8 + X^4 + X^3 + X + 1. Rcon is one of these weird transformation, and is defined as rcon(i) = [X^i, 0, 0, 0] in that field we just talked about.

I will not ask you to understand what I just wrote, and I will even advise you to just implement this function using a lookup table (basically the result of the operations already done for you). At the end of this set, if you want to know more about AES you should come back here and re-implement it using math.

Below is the golang code for the lookup table.

var rcon = [256]byte{
0x8d, 0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80, 0x1b, 0x36, 0x6c, 0xd8, 0xab, 0x4d, 0x9a,
0x2f, 0x5e, 0xbc, 0x63, 0xc6, 0x97, 0x35, 0x6a, 0xd4, 0xb3, 0x7d, 0xfa, 0xef, 0xc5, 0x91, 0x39,
0x72, 0xe4, 0xd3, 0xbd, 0x61, 0xc2, 0x9f, 0x25, 0x4a, 0x94, 0x33, 0x66, 0xcc, 0x83, 0x1d, 0x3a,
0x74, 0xe8, 0xcb, 0x8d, 0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80, 0x1b, 0x36, 0x6c, 0xd8,
0xab, 0x4d, 0x9a, 0x2f, 0x5e, 0xbc, 0x63, 0xc6, 0x97, 0x35, 0x6a, 0xd4, 0xb3, 0x7d, 0xfa, 0xef,
0xc5, 0x91, 0x39, 0x72, 0xe4, 0xd3, 0xbd, 0x61, 0xc2, 0x9f, 0x25, 0x4a, 0x94, 0x33, 0x66, 0xcc,
0x83, 0x1d, 0x3a, 0x74, 0xe8, 0xcb, 0x8d, 0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80, 0x1b,
0x36, 0x6c, 0xd8, 0xab, 0x4d, 0x9a, 0x2f, 0x5e, 0xbc, 0x63, 0xc6, 0x97, 0x35, 0x6a, 0xd4, 0xb3,
0x7d, 0xfa, 0xef, 0xc5, 0x91, 0x39, 0x72, 0xe4, 0xd3, 0xbd, 0x61, 0xc2, 0x9f, 0x25, 0x4a, 0x94,
0x33, 0x66, 0xcc, 0x83, 0x1d, 0x3a, 0x74, 0xe8, 0xcb, 0x8d, 0x01, 0x02, 0x04, 0x08, 0x10, 0x20,
0x40, 0x80, 0x1b, 0x36, 0x6c, 0xd8, 0xab, 0x4d, 0x9a, 0x2f, 0x5e, 0xbc, 0x63, 0xc6, 0x97, 0x35,
0x6a, 0xd4, 0xb3, 0x7d, 0xfa, 0xef, 0xc5, 0x91, 0x39, 0x72, 0xe4, 0xd3, 0xbd, 0x61, 0xc2, 0x9f,
0x25, 0x4a, 0x94, 0x33, 0x66, 0xcc, 0x83, 0x1d, 0x3a, 0x74, 0xe8, 0xcb, 0x8d, 0x01, 0x02, 0x04,
0x08, 0x10, 0x20, 0x40, 0x80, 0x1b, 0x36, 0x6c, 0xd8, 0xab, 0x4d, 0x9a, 0x2f, 0x5e, 0xbc, 0x63,
0xc6, 0x97, 0x35, 0x6a, 0xd4, 0xb3, 0x7d, 0xfa, 0xef, 0xc5, 0x91, 0x39, 0x72, 0xe4, 0xd3, 0xbd,
0x61, 0xc2, 0x9f, 0x25, 0x4a, 0x94, 0x33, 0x66, 0xcc, 0x83, 0x1d, 0x3a, 0x74, 0xe8, 0xcb, 0x8d
}

Examples:

Once you are done, you can go to the next step. Ignore the rest of this page unless you are ready to do some math.

Next

Are you ready for some math?

You need to understand four things, minus the definition of a field which is not too useful for us here:

  1. How can a byte be represented as a polynomial in this field?
  2. How to do addition in this field?
  3. How to do multiplication in this field?
  4. What to do when the resulting polynomial is larger or equal to X^8?

How can a byte be represented as a polynomial in this field?

A byte is 8 bits right? Imagine this byte 10011010. To translate this into a polynomial we just see each digit as an index, telling us if this position in our polynomial is enabled (1) or not (0).

1 would be 1, 10 would be X, 100 would be X^2

So our previous example 10011010 would be \(X^7 + X^4 + X^3 + X\)

How to do addition in this field?

The addition behaves like a XOR. This means that for example \(X + X = 0\) or \(1 + 1 = 0\).

How to do multiplication in this field?

Like you've always been doing multiplications of polynomials. For example:

\[ (X^2 + X) ( X^4 + 1) = X^2 \times X^4 + X^2 \times 1 + X \times X^4 + X \times 1 = X^6 + X^2 + X^5 + X \]

What to do when the resulting polynomial is larger or equal to X^8?

So here is the tricky part. You must have wondered "but if I get a polynomial larger or equal to \(X^8\) how would I convert that back to a byte? And you were right to ask yourself this question.

Basically, additions are done modulo a polynomial, in the case of AES this polynomial is:

\[ X^8 + X^4 + X^3 + X + 1 \]

How this helps, is that, this AES polynomial is equal to 0 thus we have

\[ X^8 = X^4 + X^3 + X + 1 \]

which solves the case where you would have exactly \( X^8 \). (Remember, coefficients are only 0 or 1, no negative signs. So if you move things around, you don't change the sign.)

Now, let's imagine that we have made a multiplication that gives us something larger, \( X^9 \) for example. What we would realize is that \(X^9 = X \times X^8\) which can be written as

\[ X \times (X^4 + X^3 + X + 1) = X^5 + X^4 + X^2 + X \]

And there you have it. That's all there is to it. If the result is still bigger than \( X^8 \) just repeat this until the larger power of \(X\) is no more than \(7\).

Now you know enough to implement this function in math!

Next