AES Standard Decryption Algorithm

The standard decryption algorithm of the AES-128 encryption is provided. It is a straightforward reverse of the encryption algorithm.

In the same FIPS publication, "Announcing the ADVANCED ENCRYPTION STANDARD (AES)" in 2001, 2 types of AES decryption algorithms were included.

The first type of AES decryption algorithms is the standard reverse process of the encryption algorithm. Here is the version for a single block of 128-bit ciphertext with a 128-bit cipher key:

```Input:
C: 128 bits of ciphertext
K: 128 bits cipher key

InvS[]: Inverse substitution box of 16x16 byte values
KeyExpansion(): Procedure to expand cipher key to round keys
InvShiftRows(): Inverse shift rows procedure
InvSubBytes(): Inverse substitution of bytes procedure
InvMixColumns(): Inverse mix columns procedure

Output:
T: 128 bits of plaintext

Algorithm:
KeyExpansion(K,k[])           # expanding K to 11 round keys:
# k[0], k[1], k[2], ..., k[10]

state = C                     # copying ciphertext to state
AddRoundKey(State, k[10])     # adding last round key

for i = 9 to 1                # loop to repeat 9 rounds backward
InvShiftRows(state)        # performing reverse byte shifting
InvSubBytes(state)         # performing reverse substitution
AddRoundKey(state, k[i])   # adding next round key
InvMixColumns(state)       # reversely mixing columns in state
end for                       # end of loop

InvShiftRows(state)           # performing reverse byte shifting
InvSubBytes(state)            # performing reverse substitution
AddRoundKey(state, k[0])      # adding first round key

T = state                     # copying state to plaintext
```

Brief descriptions of procedures and the S-Box used in the AES decryption algorithm are described below.

KeyExpansion() - The KeyExpansion() procedure is the same procedure used in the encryption algorithm.

AddRoundKey() - The AddRoundKey() procedure is the same procedure used in the encryption algorithm.

InvShiftRows() - The InvShiftRows() procedure is the inverse of the ShiftRows() procedure. It performs a cyclic right shift operation on each row of bytes in the state. The result is stored back to the state as shown below:

```InvShiftRows(state) {
Row[0..3] = state               # copying state to rows
Row[1] = RightRotate(Row[1],1)  # left rotating by 1 byte
Row[2] = RightRotate(Row[2],2)  # left rotating by 2 bytes
Row[3] = RightRotate(Row[3],3)  # left rotating by 3 bytes
state = Row[0..3]               # copying rows to state
}
```

InvSubBytes() - The InvSubBytes() procedure is the inverse of the SubBytes() procedure. It performs a lookup operation on the Inverse S-Box for each byte in the state. The result is stored back to the state as shown below. The Inverse S-Box is presented at the end of the section.

```InvSubBytes(state) {
for each byte b in state
h = (b>>4) && 0x0f   # high order 4 bits
l = b && 0x0f        # low order 4 bits
b = InvS[h,l]        # look up in the Inverse S-Box
end for
}
where InvS[16,16] is (in hexadecimal digits):

| 0  1  2  3  4  5  6  7  8  9  a  b  c  d  e  f
---|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|
00 |52 09 6a d5 30 36 a5 38 bf 40 a3 9e 81 f3 d7 fb
10 |7c e3 39 82 9b 2f ff 87 34 8e 43 44 c4 de e9 cb
20 |54 7b 94 32 a6 c2 23 3d ee 4c 95 0b 42 fa c3 4e
30 |08 2e a1 66 28 d9 24 b2 76 5b a2 49 6d 8b d1 25
40 |72 f8 f6 64 86 68 98 16 d4 a4 5c cc 5d 65 b6 92
50 |6c 70 48 50 fd ed b9 da 5e 15 46 57 a7 8d 9d 84
60 |90 d8 ab 00 8c bc d3 0a f7 e4 58 05 b8 b3 45 06
70 |d0 2c 1e 8f ca 3f 0f 02 c1 af bd 03 01 13 8a 6b
80 |3a 91 11 41 4f 67 dc ea 97 f2 cf ce f0 b4 e6 73
90 |96 ac 74 22 e7 ad 35 85 e2 f9 37 e8 1c 75 df 6e
a0 |47 f1 1a 71 1d 29 c5 89 6f b7 62 0e aa 18 be 1b
b0 |fc 56 3e 4b c6 d2 79 20 9a db c0 fe 78 cd 5a f4
c0 |1f dd a8 33 88 07 c7 31 b1 12 10 59 27 80 ec 5f
d0 |60 51 7f a9 19 b5 4a 0d 2d e5 7a 9f 93 c9 9c ef
e0 |a0 e0 3b 4d ae 2a f5 b0 c8 eb bb 3c 83 53 99 61
f0 |17 2b 04 7e ba 77 d6 26 e1 69 14 63 55 21 0c 7d
```

InvMixColumns() - The InvMixColumns() procedure is the inverse of the MixColumns() procedure. It performs a matrix multiplication of the state with a static matrix. The matrix multiplication is the same operation used in the encryption algorithm, see the previous tutorial for more details.

```InvMixColumns(state) {
|     |   |0x0e 0x0b 0x0d 0x09|   |     |
|     |   |0x09 0x0e 0x0b 0x0d|   |     |
|state| = |0x0d 0x09 0x0e 0x0b| ● |state|
|     |   |0x0b 0x0d 0x09 0x0e|   |     |
}
```

Last update: 2015.