AES Standard Decryption Algorithm

Cryptography Tutorials - Herong's Tutorial Examples

∟Introduction to AES (Advanced Encryption Standard)

∟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)" at http://csrc.nist.gov/publications/fips/fips197/fips-197.pdf 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
   AddRoundKey(): Add round key procedure
   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|   |     |
}