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

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?

-
I don't remember the term RCON from my read of the Rijndael book ... do you have a reference where it is used? Are these the round constants? (Also, have a look at my image of the AES key schedule in another answer, it might make things clearer.) – Paŭlo Ebermann Apr 21 '12 at 16:10
– goldroger Apr 21 '12 at 16:24
– goldroger Apr 21 '12 at 16:25
there is a three step in key expansion, rotation, after rotation, the every 8bit in my 32bit key will change using s-box and the RCON. – goldroger Apr 21 '12 at 16:28
Note that you have a slight mistake in your s-box step: Sbox(09) = 01, not 02. – Paŭlo Ebermann Apr 21 '12 at 18:11

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.

-
thanks for that @Paulo, but what is the used of Rcon[256], that will be found here en.wikipedia.org/wiki/Rijndael_key_schedule under Rcon. – goldroger Apr 21 '12 at 17:50
this is right, Rcon(0) = 01000000 Rcon(1) = 02000000 Rcon(2) = 04000000 Rcon(3) = 08000000 Rcon(4) = 10000000 Rcon(5) = 20000000 Rcon(6) = 40000000 Rcon(7) = 80000000 Rcon(8) = 1B000000 Rcon(9) = 36000000 Rcon(10) = 6C000000 Rcon(11) = D8000000 Rcon(12) = AB000000 Rcon(13) = 4D000000 Rcon(14) = 9A000000 but I don't know what is the meaning of Rcon[256] that was posted in wikipedia.. I don't know how to lookup in that table. – goldroger Apr 21 '12 at 17:52
The notation is slightly different between the individual sources ... you only need the first some entries in this table (10 for AES-128), and put the byte from the wikipedia table into the first byte of 32-bit constant. – Paŭlo Ebermann Apr 21 '12 at 18:16
The rcon byte does not even need a table: successive values are obtained by doubling in GF(256) as used in MixColumns. One can use rcon as the round counter, perhaps as in for( rcon=1; rcon!=0x6c; rcon=(rcon<<1)^(0x11b&-(rcon>>7)) ) – fgrieu Dec 27 '12 at 11:41
@fgrieu Thanks for the note, I added this to the answer. – Paŭlo Ebermann Dec 27 '12 at 22:40