19.9 Decryption

Team-Fly

---

19.9 Decryption

For Rijndael decryption one runs the encryption process in reverse order with the inverse transformations. We have already considered the inverses of the transformations ByteSub, ShiftRow, and MixColumn, which in the following are represented in pseudocode by the functions InvByteSub, InvShiftRow, and InvMixColumn. The inverted S-box, the distances for inversion, the ShiftRow transformation, and the inverted matrix for the inversion of the MixColumn transformation are given on pages 369–370. The inverse round functions are the following:

   InvFinalRound (word State, word RoundKey)   {     AddRoundKey (State, RoundKey);     InvShiftRow (State);     InvByteSub (State);   }   InvRound (word State, word RoundKey)   {     AddRoundKey (State, RoundKey);     InvMixColumn (State);     InvShiftRow (State);     InvByteSub (State);   } 

The entire operation for decryption of a block is as follows:

   InvRijndael (byte State, byte CipherKey)   {     KeyExpansion (CipherKey, ExpandedKey);     InvFinalRound (State, ExpandedKey + Nb*Nr);     for (i = Nr − 1; i > 0; i−−)       InvRound (State, ExpandedKey + Nb*i);     AddRoundKey (State, ExpandedKey);   } 

The algebraic structure of Rijndael makes it possible to arrange the transformations for encryption in such a way that here, too, tables can be employed. Here one must note that the substitution S and the ShiftRow transformation commute, so that within a round their order can be switched. Because of the homomorphism property f(x + y) = f(x) + f (y) of linear transformations the MixColumn transformation and addition of the round key can be exchanged when MixColumn was used previously on the round key. Within a round the following course is taken:

   InvFinalRound (word State, word RoundKey)   {     AddRoundKey (State, RoundKey);     InvByteSub (State);     InvShiftRow (State);   }   InvRound (word State, word RoundKey)   {     InvMixColumn (State);     AddRoundKey (State, MixColumn (RoundKey));     InvByteSub (State);     InvShiftRow (State);   } 

Without changing the sequence of transformations over both functions ordered one after the other, they can be redefined as follows:

   AddRoundKey (State, RoundKey);   InvRound (word State, word RoundKey)   {     InvByteSub (State);     InvShiftRow (State);     InvMixColumn (State);     AddRoundKey (State, MixColumn (RoundKey));   }   InvFinalRound (word State, word RoundKey)   {     InvByteSub (State);     InvShiftRow (State);     AddRoundKey (State, RoundKey)   } 

With this is created the analogous structure to that for encryption. For reasons of efficiency the application of MixColumn to the round key in InvRound() is postponed until the key expansion, where the first and last round keys of MixColumn are left untouched. The "inverse" round keys are generated with

   InvKeyExpansion (byte CipherKey, word InvEpandedKey)   {     KeyExpansion (CipherKey, InvExpandedKey);     for (i = 1; i < Nr; I++)       InvMixColumn (InvExpandedKey + Nb*i);   } 

The entire decryption operation of a block is now as follows:

   InvRijndael (byte State, byte CipherKey)   {     InvKeyExpansion (CipherKey, InvExpandedKey);     AddRoundKey (State, InvExpandedKey + Nb*Nr);     for (i = Nr − 1; i > 0; i−−)       InvRound (State, InvExpandedKey + Nb*i);     InvFinalRound (State, InvExpandedKey);   } 

In analogy to encryption, tables can be precomputed for this form of decryption. With

(for w = 0,..., 255, S⁻¹(w) denotes the inverse S-box replacement) the result of an inverse round operation on a block b = (b_0,j, b_1,j, b_2,j, b_3,j), j = 0,..., L_b − 1, can be determined by

for j = 0,..., L_b − 1 with d⁻¹ (i, j) := j + mod L_b (cf. page 369) and the jth column the "inverse" round key.

Again in the last round the MixColumn transformation is omitted, and thus the result of the last round is given by

for j = 0,..., L_b − 1.

To save memory one can also make do in decryption with a table of only 256 4-byte words, in which

with a left rotation r(a, b, c, d) = (b, c, d, a) of one byte.

For further details, investigations into security and cryptanalysis, computational times, and current information on AES and Rijndael the reader is referred to the literature cited above as well as the Internet sites of NIST and Vincent Rijmen, which in turn contain many links to further sources of information:

• http://csrc.nist.gov/encryption/aes/aes_home.htm

• http://www.esat.kuleuven.ac.be/~rijmen/rijndael

On the accompanying CD-ROM are to be found three implementations of Rijndael, which are recommended for deepening the reader's understanding of the procedure and for further investigations. The programs also contain application segments with functions for Cipher Feedback Mode (CFB) and Output Feedback Mode (OFB). Once again, the author wishes to thank all the authors for permission to include their source code in this book. The source code is located in the following directories:

Directory	Implementation
rijndael\c_ref	C reference implementation with test suite by Vincent Rijmen and Paulo Barreto
rijndael\c_opt	optimized implementation in C by Vincent Rijmen, Antoon Bosselaers, and Paulo Barreto
rijndael\cpp_opt	optimized C++ implementation by Brian Gladman

---

Team-Fly