The Laws of Cryptography:
AES Decryption

by Neal R. Wagner

NOTE: This site is obsolete. See book draft (in PDF):

Modifications to the AES Algorithm for Decryption.

The following functions need minor (or more major) revision for decryption:

• Cipher(), changed to InvCipher(), which is the main decryption outline. It is of course very similar to the Cipher() function, except that many of the subfunctions are themselves inverses, and the order of functions within a round is different.
• ShiftRows(), changed to InvShiftRows() -- just minor changes.
• MixColumns(), changed to InvMixColumns() -- the inverse function, similar but with different constants in it.
• AddRoundKey(), changed to InvAddRoundKey() -- just works backwards along the expanded key.
As before, one also needs to organize a number of minor details to get a complete working Java program.

Implementation of InvCipher().

Here is Java pseudo-code for the inverse cipher. The various steps must be carried out in reverse order. These are arranged into rounds as with encryption, but the functions in each round are in a slightly different order than the order used in encryption. The AES specification has also supplied an equivalent inverse cipher in which the individual parts of each round are in the same order as with encryption. This might make a hardware implementation easier, but I have not used it here.

 ``` Constants: int Nb = 4; // but it might change someday int Nr = 10, 12, or 14; // rounds, for Nk = 4, 6, or 8 Inputs: array in of 4*Nb bytes // input ciphertext array out of 4*Nb bytes // output plaintext array w of 4*Nb*(Nr+1) bytes // expanded key Internal work array: state, 2-dim array of 4*Nb bytes, 4 rows and Nb cols Algorithm: void InvCipher(byte[] in, byte[] out, byte[] w) { byte[][] state = new byte[4][Nb]; state = in; // actual component-wise copy AddRoundKey(state, w, Nr*Nb, (Nr+1)*Nb - 1); for (int round = Nr-1; round >= 1; round--) { InvShiftRows(state); InvSubBytes(state); AddRoundKey(state, w, round*Nb, (round+1)*Nb-1); MixColumns(state); } InvShiftRows(state); InvSubBytes(state); AddRoundKey(state, w, 0, Nb - 1); out = state; // component-wise copy }```

Implementation of InvShiftRows().

This just does the inverse of ShiftRows: doing a left circular shift of rows 1, 2, and 3, by amounts of 1, 2, and 3 bytes. The actual Java code below does this.

```
void InvShiftRows(byte[][] state) {
byte[] t = new byte[4];
for (int r = 1; r < 4; r++) {
for (int c = 0; c < Nb; c++)
t[(c + r)%Nb] = state[r][c];
for (int c = 0; c < Nb; c++)
state[r][c] = t[c];
}
}
```

Implementation of InvMixColumns().

The MixColumns() function was carefully constructed so that it has an inverse. I will add in the theory of this here (or elsewhere) later. For now, it suffices to say that the function multiplied each column by the inverse polynomial of a(x):

```
a-1(x) = (0b)x3 + (0d)x2 +(09)x + (0e),
```

The resulting function, when simplified, takes the following form in Java pseudo-code, where as before # indicates multiplication in the field:

```
void InvMixColumns(byte[][] s) {
byte[] sp = new byte[4];
for (int c = 0; c < 4; c++) {
sp[0] = (0x0e # s[0][c]) ^ (0x0b # s[1][c]) ^
(0x0d # s[2][c]) ^ (0x09 # s[3][c]);
sp[1] = (0x09 # s[0][c]) ^ (0x0e # s[1][c]) ^
(0x0b # s[2][c]) ^ (0x0d # s[3][c]);
sp[2] = (0x0d # s[0][c]) ^ (0x09 # s[1][c]) ^
(0x0e # s[2][c]) ^ (0x0b # s[3][c]);
sp[3] = (0x0b # s[0][c]) ^ (0x0d # s[1][c]) ^
(0x09 # s[2][c]) ^ (0x0e # s[3][c]);
for (int i = 0; i < 4; i++) s[i][c] = sp[i];
}
}
```

Since the AES specification uses a parameterized AddRoundKey() function, it is its own inverse, using the parameters in the opposite order. My implementation just lets AddRoundKey() exclusive-or in another 16 bytes every time it is called, so I need a slightly different function, where wCount is initialized to 4*Nb*(Nr+1):

```
for (int c = Nb - 1; c >= 0; c--)
for (int r = 3; r >= 0 ; r--)
state[r][c] = state[r][c] ^ w[--wCount];
}
```

Actual Java Implementation of Decryption Using the AES Algorithm.

As before, it's a matter of putting it all together, with a number of details to make the Java work correctly. My Java implementation uses the old Tables, GetBytes, Copy, and Print classes along with the new classes:

Here is a combined listing of all the ecryption classes: Java Implementation of AES Decryption.

Here are results of test runs of the program, where encryption is followed by decryption:

Revision date: 2002-01-23. (Please use ISO 8601, the International Standard.)