AES, or Rijndael, Encryption Algorithm

Cryptography Tutorials - Herong's Tutorial Examples

∟Introduction to AES (Advanced Encryption Standard)

∟AES, or Rijndael, Encryption Algorithm

A quick description of the AES (Advanced Encryption Standard) encryption algorithm is provided. This description only covers AES encryption for a single block of 128-bit plaintext with a 128-bit cipher key.

In the same FIPS publication, "Announcing the ADVANCED ENCRYPTION STANDARD (AES)" at http://csrc.nist.gov/publications/fips/fips197/fips-197.pdf in 2001, AES decryption algorithms were included for AES-128, AES-196 and AES256.

The AES-128 encryption algorithm is for a single block of 128-bit plaintext with a 128-bit cipher key:

Input: 
   T: 128 bits of plaintext
   K: 128 bits cipher key
   S[]: Substitution box (s-box) of 16x16 well-selected byte values
   KeyExpansion(): Procedure to expand cipher key to round keys
   AddRoundKey(): Add round key procedure
   SubBytes(): Substitution of bytes procedure
   ShiftRows(): Shift rows procedure
   MixColumns(): Mix columns procedure

Output:
   C: 128 bits of ciphertext

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

   state = T                     # copying plaintext to state
   AddRoundKey(State, k[0])      # adding first round key

   for i = 1 to 9                # loop to repeat 9 rounds
      SubBytes(state)            # performing substitution
      ShiftRows(state)           # performing byte shifting
      MixColumns(state)          # mixing columns in state
      AddRoundKey(state, k[i])   # adding next round key
   end for                       # end of loop

   SubBytes(state)               # performing substitution
   ShiftRows(state)              # performing byte shifting
   AddRoundKey(state, k[10])     # adding last round key

   C = state                     # copying state to ciphertext

As you can see, most operations of the AES encryption algorithm are carried out on the "state" object, which stores the intermediate ciphertext as a 4x4 byte array.

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

KeyExpansion() - The KeyExpansion() procedure takes the cipher key, K, as input and generates a key schedule, which is a series of 11 round keys, k[0], k[1], k[2], ..., k[10]. Round constants, S-Box (substitution box), XOR operations, and cyclic shift operations are used in the KeyExpansion() procedure. Details of the KeyExpansion() algorithm are given in next tutorials.

AddRoundKey() - The AddRoundKey() procedure performs the XOR operation of the state and the given round key. The result is stored back to the state as shown below:

AddRoundKey(state,k) {
   state = state XOR k
}

SubBytes() - The SubBytes() procedure performs a lookup operation on the S-Box for each byte in the state. The result is stored back to the state as shown below:

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

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

ShiftRows() - The SubBytes() procedure performs a cyclic left shift operation on each row of bytes in the state. The result is stored back to the state as shown below. The S-Box is presented at the end of the section.

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

MixColumns() - The MixColumns() procedure performs a matrix multiplication of the state with a static matrix. Details of the MixColumns() algorithm are given in next tutorials.