How to use RCON In Key Expansion of 128 Bit Advanced Encryption Standard

Question

I have a question about RCON

here is my illustration...

this is the 128 bit key..

[2b] [28] [ab] [09]
[7e] [ae] [f7] [cf]
[15] [d2] [15] [4f]
[16] [a6] [88] [3c]

and then I will get this..

[09]
[cf]
[4f]
[3c]

and then I will put down the first 8bit(1byte) where it is the 09:

[cf]
[4f]
[3c]
[09]

after that I will change their value according to s-box..

[8a]
[84]
[eb]
[01]

and then I will xor that substituted 32 bit value to

[2b]        [8a]        [01]
[7e]  XOR   [84]  XOR   [00] <--- that is a RCON(4)
[15]        [eb]        [00]
[16]        [01]        [00]

My question is: How will I determine the RCON that I will use? Or will I only used this one?

[01]
[00] <--- that is a RCON(4)
[00]
[00]

But why?

Answer 1

The Rijndael/AES key schedule uses (for every some steps, depending on the key size) a non-linear function (I called it $f_i$ in my schematic image in a related answer) on a 32-bit column:

This function $f_i$ (note that $i$ starts with $1$ here) does the following steps:

• substitute each byte, using the AES S-box.
• rotate the whole column by one byte "down" (these two steps can be swapped around without effect)

• XOR in the round constant $RCON[i] = [x^{i-1}, \mathtt{00}, \mathtt{00}, \mathtt{00} ]$. The values $x^{i-1}$ are to be computed in the same representation of $GF(2^8)$ as used in all other operations in AES (see at the end on how to do this), but you can also take them from a table in the Wikipedia article, or from the examples in Appendix A of the AES standard.

  As you see, $RCON[i]$ consists mainly of zeros, the only effective part is in the first byte. This means, this step only modifies the first byte of the column, the others are unaffected.

So, in your example, you have this column 3 of the original key:

[09]
[cf]
[4f]
[3c]

Now we rotate this by one:

[cf]
[4f]
[3c]
[09]

Now we put this through the AES S-box (component wise):

[8a]
[84]
[eb]
[01]

And now the round step: This is round 1, thus we need $RCON[1] = [\mathtt{01}, \mathtt{00}, \mathtt{00}, \mathtt{00}]$:

[8a ⊕ 01]   [8b]
[84 ⊕ 00] = [84]
[eb ⊕ 00]   [eb]
[01 ⊕ 00]   [01]

This was $f_1$, and we'll now XOR this result with column 0 of the original key to obtain column 4 of the expanded key:

[8b ⊕ 2b]   [a0]
[84 ⊕ 7e] = [fa]
[eb ⊕ 15]   [fe]
[01 ⊕ 16]   [17]

After three more simple XOR steps to get column 5-7 we would then apply $f_2$ (which uses $RCON[ 2] = [\mathtt{02},\mathtt{00}, \mathtt{00}, \mathtt{00}]$) on column 7 and XOR the result with column 4 to get column 8, and so on.

The Rcon-array on Wikipedia contains the precomputed constants $x^{i-1}$ for $i$ from $0$ to $255$, so you would put $RCON[i] = [\mathtt{Rcon[i]}, \mathtt{00}, \mathtt{00}, \mathtt{00}]$. For AES-128, you only need the RCONs from $1$ to $10$ (as you need 44 columns of round key material), and here are these as a table (in hexadecimal form, as all constants in code font here):

   i        1     2     3     4     5     6     7     8     9    10
--------------------------------------------------------------------
          [01]  [02]  [04]  [08]  [10]  [20]  [40]  [80]  [1b]  [36]
RCON[i]   [00]  [00]  [00]  [00]  [00]  [00]  [00]  [00]  [00]  [00]
          [00]  [00]  [00]  [00]  [00]  [00]  [00]  [00]  [00]  [00]
          [00]  [00]  [00]  [00]  [00]  [00]  [00]  [00]  [00]  [00]

For AES-192 and AES-256 you need even less of these round constants, so putting all 255 of them in Wikipedia is a bit superfluous. Even for Rijndael-256-128 (i.e. 256-bit blocks and 128-bit keys) we would need only $(14+1)·8/4-1 = 29$ of these.

As mentioned by fgrieu in a comment, you can also calculate the $\mathtt{Rcon[i]}$ on the fly, as each of them is obtained from the previous by an doubling in $GF(2^8)$, which in the representation used in Rijndael is just a left-shift followed with a conditional XOR with a constant. In C-like syntax (using a twos-complement representation like every usual computer nowadays) this looks like this:

rcon = (rcon<<1) ^ (0x11b & -(rcon>>7));

_{An explanation: (rcon<<1) is the pure doubling (multiplication by $x$ in $\mathbb{Z}_2[x]$). rcon >> 7 is the first bit of rcon, i.e. either $\mathtt{0}$ or $\mathtt{1}$. -(rcon>>7) then is $\mathtt{0}$ or -1 (= $\mathtt{f...ff}$, i.e. all bits set). Thus (0x11b & -(rcon>>7)) is either $\mathtt{0}$ or $\mathtt{11b}$, and XORing with this just is reduction modulo the Rijndael polynomial $x^8 + x^4 + x^3 + x + 1$.}

The same doubling operation is used in the MixColumns-step of the actual encryption operation, so you need to implement it anyways.