2020 August 11

In the previous article I explained how the encryption algorithm of AES is structured. This time I focus on the decryption algorithm. I'll use a lot of terms and functions defined in the previous post so if you don't understand something check it out. As usual the examples assume we are using AES-128.

If you're interested in seeing an implementation close to the specification, checkout the one I coded for the cryptopals challenge. For a real world implementation I recommend Go's aes crypto package.

To decrypt a ciphertext $C$ and produce a plaintext $P$, the decryption algorithm uses the same round keys used in the encryption algorithm; however, the functions used in the encryption algorithm are reversed, we are now working with `InvShiftRows`

, `InvSubBytes`

and `InvMixColumns`

.

Here is the decryption algorithm:

As we can see we don't just replace the transformations by their inverse, the order of the transformations are modified as well and we go through the round keys in reverse.

InvShiftRows performs the inverse cyclical rotation of ShiftRows (you shift right instead of left).

- The first row is not shifted.
- The second row is shifted right by 1 byte.
- The third row is shifted right by 2 bytes.
- The fourth row is shifted right by 3 bytes.

InvSubBytes applies the inverse S-box to each byte of the state. Here is the inverse S-box (from Wikipedia):

The inverse of a XOR is a XOR. So the inverse of AddRoundKey is AddRoundKey itself.

As with all other functions described here, InvMixColumns is the inverse of its counterpart MixColumns.

$\begin{bmatrix} t_{0,0} \\ t_{1,0} \\ t_{2,0} \\ t_{3,0} \\ \end{bmatrix} = \begin{bmatrix} 0e & 0b & 0d & 09 \\ 09 & 0e & 0b & 0d \\ 0d & 09 & 0e & 0b \\ 0b & 0d & 09 & 0e \\ \end{bmatrix} \begin{bmatrix} s_{0,0} \\ s_{1,0} \\ s_{2,0} \\ s_{3,0} \\ \end{bmatrix}$The designers of AES also give another way of decrypting a block, using the same functions we just described. This alternative is based on several properties of the transformation but requires a small change in the key schedule.

The round keys $[K_1, ..., K_9]$ are transformed with `InvMixColumns`

, I note $D_i$ the new round keys:

The first and last round keys stay the same: $D_0 = K_0$ and $D_{10} = K_{10}$

You might be wondering how we are supposed to apply InvMixColumns on the key, since it usually applies on the state represented as a matrix. In the article describing the key schedule we wrote each round key $K_i$ as an array of 4-byte words $w_c$:

$K_1 = [w_4, w_5, w_6, w_7]$Each $w_c$ is made up of 4 bytes and we can note each byte $b_{k, c}$:

$w_c = \begin{bmatrix} b_{0, c} \\ b_{1, c} \\ b_{2, c} \\ b_{3, c} \\ \end{bmatrix}$Then we can represent the key $K_1$ as matrix as well:

$K_1 = \begin{bmatrix} b_{0,4} & b_{0,5} & b_{0,6} & b_{0,7} \\ b_{1,4} & b_{1,5} & b_{1,6} & b_{1,7} \\ b_{2,4} & b_{2,5} & b_{2,6} & b_{2,7} \\ b_{3,4} & b_{3,5} & b_{3,6} & b_{3,7} \\ \end{bmatrix}$Thanks to this transformation we can now have an inverse cipher that looks just like the encryption cipher:

Notice how this is the encryption algorithm with the inverse transformations and the new round keys.

You should now have a fair understanding of the AES decryption algorithm. There is something I haven't mentionned yet, real life implementations of the encryption or decryption algorithm won't use the functions chained together:

` invMixColumns(invShiftRows(invSubBytes(state)))`

Some implementations tricks will be used instead, check out Go's aes crypto package for an example. Here is their implementation of one decryption round:

```
for r := 0; r < nr; r++ {
t0 = xk[k+0] ^ td0[uint8(s0>>24)] ^ td1[uint8(s3>>16)] ^ td2[uint8(s2>>8)] ^ td3[uint8(s1)]
t1 = xk[k+1] ^ td0[uint8(s1>>24)] ^ td1[uint8(s0>>16)] ^ td2[uint8(s3>>8)] ^ td3[uint8(s2)]
t2 = xk[k+2] ^ td0[uint8(s2>>24)] ^ td1[uint8(s1>>16)] ^ td2[uint8(s0>>8)] ^ td3[uint8(s3)]
t3 = xk[k+3] ^ td0[uint8(s3>>24)] ^ td1[uint8(s2>>16)] ^ td2[uint8(s1>>8)] ^ td3[uint8(s0)]
k += 4
s0, s1, s2, s3 = t0, t1, t2, t3
}
```

I used and studied the following resources while writing this article: