Rijndael key schedule


Rijndael key schedule

AES (Rijndael) uses a key schedule to expand a short key into a number of separate round keys. This is known as the Rijndael key schedule.

Common operations

Rijndael's key schedule utilizes a number of operations, which will be described before describing the key schedule.

Rotate

The rotate operation takes a 32-bit word like this (in hexadecimal):

:1d2c3a4f

And rotates it eight bits to the left:

:2c3a4f1d

Rcon

Rcon is what the Rijndael documentation calls the exponentiation of 2 to a user-specified value. Note that this operation is not performed with regular integers, but in Rijndael's finite field. In polynomial form, 2 is 2 = 00000010 = 0 x^7 + 0 x^6 + 0 x^5 + 0 x^4 + 0 x^3 + 0 x^2 + 1 x + 0 = x, and we compute

: extrm{rcon}(i) = x^{(254+i)}in mathbb{F}_{2^8} or equivalently, : extrm{rcon}(i) = x^{(254+i)} mod x^8 + x^4 + x^3 + x + 1in mathbb{F}_{2}.

For example, the rcon(1) = 1, the rcon(2) = 2, the rcon(3) = 4, and the rcon(9) is the hexadecimal number 0x1b (27 in decimal).

Rcon [255] = {

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}

S-box

The key schedule uses Rijndael's S-box.

Key schedule core

This operation is used as an inner loop in the key schedule, and is done thus:

* The input is a 32-bit word and an iteration number i. The output is a 32-bit word.
* Copy the input over to the output.
* Use the above described rotate operation to rotate the output eight bits to the left
* Apply Rijndael's S-box on all four individual bytes in the output word
* On just the first (leftmost) byte of the output word, exclusive or the byte with 2 to the power of (i-1). In other words, perform the rcon operation with i as the input, and exclusive or the rcon output with the first byte of the output word

The key schedule

Constants

Since the key schedule for 128-bit, 192-bit, and 256-bit encryption are very similar, with only some constants changed, the following keysize constants are defined here:

* n has a value of 16 for 128-bit keys, 24 for 192-bit keys, and 32 for 256-bit keys
* b has a value of 176 for 128-bit keys, 208 for 192-bit keys, and 240 for 256-bit keys

Key schedule description

Rijndael's key schedule is done as follows:

# The first n bytes of the expanded key are simply the encryption key.
# The rcon iteration value i is set to 1
# Until we have b bytes of expanded key, we do the following to generate n more bytes of expanded key:
#* We do the following to create 4 bytes of expanded key:
#*# We create a 4-byte temporary variable, t
#*# We assign the value of the previous four bytes in the expanded key to t
#*# We perform the key schedule core (see above) on t, with i as the rcon iteration value
#*# We increment i by 1
#*# We exclusive-or t with the four-byte block n bytes before the new expanded key. This becomes the next 4 bytes in the expanded key
#* We then do the following three times to create the next twelve bytes of expanded key:
#*# We assign the value of the previous 4 bytes in the expanded key to t
#*# We exclusive-or t with the four-byte block n bytes before the new expanded key. This becomes the next 4 bytes in the expanded key
#* If we are generating a 256-bit key, we do the following to generate the next 4 bytes of expanded key:
#*# We assign the value of the previous 4 bytes in the expanded key to t
#*# We run each of the 4 bytes in t through Rijndael's S-box
#*# We exclusive-or t with the 4-byte block 32 bytes before the new expanded key. This becomes the next 4 bytes in the expanded key.
#* If we are generating a 128-bit key, we do not perform the following steps. If we are generating a 192-bit key, we run the following steps twice. If we are generating a 256-bit key, we run the following steps three times:
#*# We assign the value of the previous 4 bytes in the expanded key to t
#*# We exclusive-or t with the four-byte block n bytes before the new expanded key. This becomes the next 4 bytes in the expanded key
# Step three is repeated until at least b bytes of expanded key are generated

References

* [http://fp.gladman.plus.com/cryptography_technology/rijndael/aes.spec.311.pdf Rijndael specification] (PDF file)
* [http://www.csrc.nist.gov/publications/fips/fips197/fips-197.pdf FIPS PUB 197: the official AES standard] (PDF file)
* [http://www.samiam.org/key-schedule.html Description of Rijndael's key schedule]

See also

* Advanced Encryption Standard


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Key-schedule — En cryptographie, le key schedule (préparation des clés) consiste à créer des sous clés à partir de la clé principale pour un algorithme de chiffrement par bloc. Le terme est également employé dans le cadre des fonctions de hachage… …   Wikipédia en Français

  • Key Schedule — En cryptographie, le key schedule (préparation des clés) consiste à créer des sous clés à partir de la clé principale pour un algorithme de chiffrement par bloc. Le terme est également employé dans le cadre des fonctions de hachage… …   Wikipédia en Français

  • Key schedule — In cryptography, the so called product ciphers are a certain kind of ciphers, where the (de )ciphering of data is done in rounds . The general setup of each round is the same, except for some hard coded parameters and a part of the cipher key,… …   Wikipedia

  • Key schedule — En cryptographie, le key schedule (préparation des clés) consiste à créer des sous clés à partir de la clé principale pour un algorithme de chiffrement par bloc. Le terme est également employé dans le cadre des fonctions de hachage… …   Wikipédia en Français

  • Rijndael — est le nom de l algorithme de chiffrement symétrique employé par le standard AES. Sommaire 1 Rijndael et AES 2 Objectifs 3 Origines 4 Voir auss …   Wikipédia en Français

  • Advanced Encryption Standard — Infobox block cipher name = AES caption = The SubBytes step, one of four stages in a round of AES designers = Vincent Rijmen, Joan Daemen publish date = 1998 derived from = Square derived to = Anubis, Grand Cru related to = certification = AES… …   Wikipedia

  • Advanced Encryption Standard — AES, Rijndael AES, Rijndael Создатель: Винсент Рэймен Йоан Даймен Созда …   Википедия

  • Advanced Encryption Standard — AES Der Substitutionschritt, einer von 4 Teilschritten pro Runde Entwickler Joan Daemen, Vincent Rijmen Veröffentlicht 1998, Zertifizierung Oktober 2000 Abgeleitet …   Deutsch Wikipedia

  • Мёрфи, Шон (криптограф) — В Википедии есть статьи о других людях с такой фамилией, см. Мёрфи. Шон Мерфи (англ. Sean Murphy)  английский криптограф, в настоящее время профессор Лондонского университета (колледж Royal Holloway). Содержание 1 Научная деятельность …   Википедия

  • Кнудсен, Ларс — Ларс Рамкильд Кнудсен англ. Lars Ramkilde Knudsen …   Википедия