# How does the key schedule of Rijndael looks for keysizes other than 128 bit?

It said in Wikipedia that:

[....] Rijndael can be specified with block and key sizes in any multiple of 32 bits, with a minimum of 128 bits. The blocksize has a maximum of 256 bits, but the keysize has no theoretical maximum.

How would the key schedule look for these other key sizes, like a 136-bit key?

-
Why do you want to use such an unusual key size? I hope you don't plug in a password directly as key. Passwords should be sent through a KDF, such as PBKDF2 before being used as key. –  CodesInChaos Apr 30 '12 at 8:58
what is KDF? and PBKDF2? –  goldroger Apr 30 '12 at 9:05
I think you should return to the very beginning, and describe what you want to do, and what your requirements are. In particular answer all of David's questions. Once you answered all of that, we can recommend a mode, and how to use it. –  CodesInChaos Apr 30 '12 at 9:32
Actually, Wikipedia is wrong about "the key has no theoretical maximum". This refers to theoretical variants of Rijndael, not to one of the ones specified by the designers. Rijndael (as specified) has a maximum key size of 256 bits. –  Paŭlo Ebermann Apr 30 '12 at 12:12
show 1 more comment

Rijndael (the algorithm behind AES) is specified with block sizes and key sizes of 128, 160, 192, 224 and 256, in any combination of block and key size. (Thus, Wikipedia was wrong with the keysize has no theoretical maximum here, though one could invent extensions of the key schedule algorithm which allow longer keys. See below for details. I now fixed this wrong statement on Wikipedia, too.)

Of these 25 combinations, only the ones with a block size of 128 bit (16 bytes) and key sizes of 128, 192 and 256 bits (16, 24 and 32 bytes) are standardized as Advanced Encryption Standard. If you are using any of the other variants of Rijndael, you are not implementing AES.

For normal file encryption there is no reason to use any of the other variants, 128-bit key and block sizes are enough (when used with a reasonable mode of operation).

So, how does the key schedule look like?

(For the following, a column is a bundle of 32 bits (= 4 bytes).)

First, from the block size $N_B$ and number of rounds $n_r$ we calculate how much keying material we need for the round keys (it is $N_B · (n_r + 1)$.) The block size is then not needed any more for the key schedule. Calculate this in columns. For example, in the case of 128-bit blocks and 160-bit keys, you are using 11 rounds, and thus need $4 · (11+1) = 48$ columns of round keys.

We write as many columns as there are in the key size - for example, for our 160-bit key, we would write these as

   k_0    k_1    k_2    k_3    k_4


These are the first five columns of the round keys (i.e. the first round key and one column of the second one). As the next step, we apply the non-linear function $f_1$ of the key schedule on $k_4$, and XOR ($\oplus$) the result with $k_0$ to get $k_5$:

                                     ┏━━━┓
k_0    k_1    k_2    k_3    k_4 ─→┃f_1┃─╮
│                                ┗━━━┛ │
╭──│──────────────────────────────────────╯
│  ↓
╰─→⊕
│
↓
k_5


I described $f_i$ in an answer to another of your questions.

To generate the following round key columns, we simply calculate $k_n = k_{n-1} \oplus k_{n-5}$ (as the key size is five columns here), until we come to $k_{10}$, where we have to use $k_{10} = f_2(k_9) \oplus k_5$. We repeat this until we get to $k_{47}$ (as we need only 48 columns of round key material), then we can stop.

                                     ┏━━━┓
k_0    k_1    k_2    k_3    k_4 ─→┃f_1┃─╮
│      │      │      │      |    ┗━━━┛ │
╭──│──────│──────│──────│──────│──────────╯
│  ↓      ↓      ↓      ↓      ↓
╰─→⊕   ╭─→⊕   ╭─→⊕   ╭─→⊕   ╭─→⊕
│   │  │   │  │   │  │   │  │
↓   │  ↓   │  ↓   │  ↓   │  ↓    ┏━━━┓
k_5 ─╯ k_6 ─╯ k_7 ─╯ k_8 ─╯ k_9 ─→┃f_2┃─╮
│      │      │      │      |    ┗━━━┛ │
╭──│──────│──────│──────│──────│──────────╯
│  ↓      ↓      ↓      ↓      ↓
╰─→⊕   ╭─→⊕   ╭─→⊕   ╭─→⊕   ╭─→⊕
│   │  │   │  │   │  │   │  │
↓   │  ↓   │  ↓   │  ↓   │  ↓     ┏━━━┓
k_10 ╯ k_11 ╯ k_12 ╯ k_13 ╯ k_14 ─→┃f_3┃─╮
│      │      │      │      |     ┗━━━┛ │
╭──│──────│──────│──────│──────│───────────╯
│  ↓      ↓      ↓      ↓      ↓
...........................................
│  ↓      ↓      ↓
╰─→⊕   ╭─→⊕   ╭─→⊕
│   │  │   │  │
↓   │  ↓   │  ↓
k_45 ╯ k_46 ╯ k_47


So, it is just like the key schedule for an 128-bit key, but with one column more.

When we actually have to use the round keys for the encryption (remember, in this example the block size is 128 bits, i.e. 4 columns), we use $k_0 \dots k_3$ as the zeroth round key (i.e. before the first round), $k_4 \dots k_7$ as the first one, … and $k_{44} \dots k_{47}$ as the last one (after the 11th round).

The key schedule works similarly for other key sizes, but for key sizes larger than six columns (i.e. seven or eight - more is not specified), there is a second nonlinear function $g$ (a simplified version of $f_i$) after the first four columns in each row (see my previous answer for an example with 8 columns, i.e. AES-256).

To extend this idea to larger key sizes than 8 columns (256 bits), one would have to define what would happen with more columns - use a third nonlinear function $h$, use $g$ again, do nothing? This definition was not done by the designers, as 265 bits of key size seem to be enough for the rest of human history.

This whole key schedule can be done on the fly (i.e. while encrypting a block), and this is usually done on memory-limited implementations, who don't want to hold the whole 167 bytes (for AES-128) to 240 bytes (for AES-256) in memory. On "normal" implementations, you'll calculate the key schedule once and reuse it for each block (as you normally encrypt multiple blocks with the same key).

One can even calculate the key schedule backwards (starting with the last some columns, i.e. $k_{43}$ to $k_{47}$ in our example), which would be done for decryption on low-memory devices.

-

AES always has a blocksize of 128, and a keysize of 128, 192 or 256 bits, because NIST only standardized those modes.

Rijndael on the other hand is more flexible regarding parameters. Wikipedia says:

AES has a fixed block size of 128 bits and a key size of 128, 192, or 256 bits, whereas Rijndael can be specified with block and key sizes in any multiple of 32 bits, with a minimum of 128 bits. The blocksize has a maximum of 256 bits, but the keysize has no theoretical maximum.

136 bits it not a multiple of 32, and thus doesn't work.

-
What If I will used a 160 bits key? If I will encrypt a blocksize of 128 bits of plaintext? –  goldroger Apr 30 '12 at 9:15
key size and block size are independent, you could use a 160 bit key and 128 bit blocksize in rijndael. But why do you want to use a 160 bits key? Why don't you use one of the standard sizes? –  CodesInChaos Apr 30 '12 at 9:16
so therefore If I will encrypt a plaintext blocksize of 128 bits, I will use only a 32-128 bits of secret key? 192 bits, I will use a 32-192 bits of secret key? 256 bits, I will use a 32-256 bits of secret key? –  goldroger Apr 30 '12 at 9:18
@JohnPaulParreño That makes no sense at all. AES always uses the full secret key. I don't see how plaintext size and keysize are related. –  CodesInChaos Apr 30 '12 at 9:21
what? I'm confused, but you said before why don't I use one of the standard sizes, i thought If I will encrypt a 128 bits of plaintext, I can used a 128 bits of key... –  goldroger Apr 30 '12 at 9:26