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.
The Inverse Cipher
To decrypt a ciphertext CC and produce a plaintext PP, 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.
Inverse transformations
InvShiftRows
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.
[s0,0s0,1s0,2s0,3s1,0 s1,1s1,2s1,3s2,0s2,1s2,2s 2,3s3,0s3,1s3, 2s3,3]→[s0,0s0,1s0,2s0,3 s1,3s1,0s1,1s1, 2s2,2s2,3s2,0 s2,1s3,1s3,2 s3,3s3,0]\begin{bmatrix} s_{0,0} & s_{0,1} & s_{0,2} & s_{0,3} \\ s_{1,0} & s_{1,1} & s_{1,2} & s_{1,3} \\ s_{2,0} & s_{2,1} & s_{2,2} & s_{2,3} \\ s_{3,0} & s_{3,1} & s_{3,2} & s_{3,3} \\ \end{bmatrix} \to \begin{bmatrix} s_{0,0} & s_{0,1} & s_{0,2} & s_{0,3} \\ s_{1,3} & s_{1,0} & s_{1,1} & s_{1,2} \\ s_{2,2} & s_{2,3} & s_{2,0} & s_{2,1} \\ s_{3,1} & s_{3,2} & s_{3,3} & s_{3,0} \\ \end{bmatrix}
InvSubBytes
InvSubBytes applies the inverse S-box to each byte of the state. Here is the inverse S-box [from Wikipedia]:
AddRoundKey
The inverse of a XOR is a XOR. So the inverse of AddRoundKey is AddRoundKey itself.
InvMixColumns
As with all other functions described here, InvMixColumns is the inverse of its counterpart MixColumns.
[t 0,0t1,0t2,0t3,0]=[0e0b0d 09090e0b0d0d090e0b0b0d090e][s0,0 s1,0s2,0s3,0 ] \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 Equivalent Inverse Cipher
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.
New Round Keys
The round keys [K1,...,K9][K_1, ..., K_9] are transformed with InvMixColumns, I note DiD_i the new round keys:
Di=InvMixColumns[ Ki]for1≤i