CIS 628 Introduction to CryptographyBarbara Nostrand, Ph.D.Electrical Engineering and Computer Science |
An encryption round consists of the following steps: :
An encryption round inverts the order and the operations of an encryption round, and consists of the following steps: :
Please note that while the cyclic order for decryption is the opposite to the cyclic order for encryption, that the two loop bodies are not mirror images. This discrepency is handled by method calls outside of the respective loops. That is, our decryptor is simple an inverse composite function with respect to our encryptor. This is generally true for symmetric cryptographic systems.
// Nb = Number of 32-bit words (4 bytes per word) in the block // Nr = Number of rounds InvCipher(byte in[4*Nb], byte out[4*Nb], word w[Nb*(Nr+1)}) begin byte state[4,Nb] state = in AddRoundKey(state, w[Nr*Nb, (Nr+1)*Nb-1]) // Last Round Key for round = Nr-1 step -1 downto 1 InvShiftRows(state) InvSubBytes(state) AddRoundKey(state, w[round*Nb, (round+1)*Nb-1]) InvMixColumns(state) end for InvShiftRows(state) InvSubBytes(state) AddRoundKey(state, w[0, Nb-1]) // Extra Round-0 Key out = state end
Recall that state is a 2-dimensional matrix with 4 rows and Nb columns. We identify these columns as s_{0},...,s_{Nb-1}. w is an array of round keys one round key for each round. In our example, each of these round keys has 4 words. These round keys are listed as hexadecimal strings on pages 146-148 of our textbook. Each key is designated by its round number. Consequently, the 0-th round key is given in line R[00].k_sch at the top of page 147. Round keys are commonly representd as 2-dimensional matrices. In our example:
2b7e151628aed2a6abf7158809cf4f3cThis is converted into the w matrix by, by filling the rectangular matrix begining by filling the first column from top to bottom, and proceeding through subsequent columns until the matrix is filled. Consequently, in our example, we have:
2b 28 ab 09 7e ae f7 cf 15 d2 15 4f 16 a6 88 3cThe AddRoundKey method consists solely of GF(2) addition of the corresponding cells in the state matrix and the RoundKey matrix. This addition is accomplished by the exclusive or operation.
Recall that MixColumns is handled as a 4-th degree linear transformation over GF(2^{8}). This means that our matrix operations are performed in the usual manner, except that the underlying scalar addition and multiplcation operations are replaced by our bit-field operations. Consequently, addition is replaced by exclusive OR and multiplication is replaced by polynomial multiplaction modulo our generator polynomial. Polynomial multiplication is performed as scratchpad muiltiplication with sums not propogating carries. That is each column sum, is the composit exclusive or of each of its terms. The final result is the remainder resulting from dividing the polynomial resulting from our multiplication by the generator polynomial.
InvShiftRows like ShiftRows is performed by cyclicly shifting the cells of each row by a specified number of positions. For example, the following depicts the ShiftRows function used by the encryptor. This function applies a cylic LEFT shift to the rows:
s_{0,0} s_{0,1} s_{0,2} s_{0,3} s_{1,0} s_{1,1} s_{1,2} s_{1,3} s_{2,0} s_{2,2} s_{2,2} s_{2,3} s_{3,0} s_{3,3} s_{3,2} s_{3,3} | --> |
s_{0,0} s_{0,1} s_{0,2} s_{0,3} s_{1,1} s_{1,2} s_{1,3} s_{1,0} s_{2,2} s_{2,3} s_{2,0} s_{2,1} s_{3,3} s_{3,0} s_{3,1} s_{3,2} |
Consequently, the decryptor employs cyclic RIGHT shfit operations on the rows:
s_{0,0} s_{0,1} s_{0,2} s_{0,3} s_{1,0} s_{1,1} s_{1,2} s_{1,3} s_{2,0} s_{2,2} s_{2,2} s_{2,3} s_{3,0} s_{3,3} s_{3,2} s_{3,3} | --> |
s_{0,0} s_{0,1} s_{0,2} s_{0,3} s_{1,3} s_{1,0} s_{1,1} s_{1,2} s_{2,2} s_{2,3} s_{2,0} s_{2,1} s_{3,1} s_{3,2} s_{3,3} s_{3,0} |
This function can be precalculated as a discrete function which is performed via table lookup from an array of 256 possible values. Our author calculated this table for our current example. He provides a decryption table at the top of page 318. Details about how to find inverses of bit-fields which represent polynomials are in a previous note posted to the course schedule.