CIS 428 Introduction to Cryptography

Barbara Nostrand, Ph.D.

Electrical Engineering and Computer Science


About Implementing AES

Different versions of AES

Encryption

An encryption round consists of the following steps: :

  1. ByteSub - nonlinear layer
  2. ShiftRow - linear mixing layer
  3. MixColumns - polynomial transformation layer
  4. AddRoundKey - addition layer

Decryption

An encryption round inverts the order and the operations of an encryption round,  and consists of the following steps: :

  1. InvShiftRow - linear mixing layer
  2. InvByteSub - nonlinear layer
  3. SubRoundKey - addition layer
  4. InverseMixColumns - polynomial transformation layer

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. 

Example

AES Inverse Cipher Function


	// 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

AddRoundKey

Recall that state is a 2-dimensional matrix with 4 rows and Nb columns.  We identify these columns as s0,...,sNb-1w 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: 

2b7e151628aed2a6abf7158809cf4f3c
This 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	3c
The 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. 

InvMixColumns

Recall that MixColumns is handled as a 4-th degree linear transformation over GF(28).  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

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: 


s0,0 s0,1 s0,2 s0,3  
s1,0 s1,1 s1,2 s1,3  
s2,0 s2,2 s2,2 s2,3  
s3,0 s3,3 s3,2 s3,3  
-->
   

s0,0 s0,1 s0,2 s0,3  
s1,1 s1,2 s1,3 s1,0  
s2,2 s2,3 s2,0 s2,1  
s3,3 s3,0 s3,1 s3,2  

Consequently,  the decryptor employs cyclic RIGHT shfit operations on the rows: 


s0,0 s0,1 s0,2 s0,3  
s1,0 s1,1 s1,2 s1,3  
s2,0 s2,2 s2,2 s2,3  
s3,0 s3,3 s3,2 s3,3  
-->
   

s0,0 s0,1 s0,2 s0,3  
s1,3 s1,0 s1,1 s1,2  
s2,2 s2,3 s2,0 s2,1  
s3,1 s3,2 s3,3 s3,0  

InvSubBytes

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. 


Last modified: 2008 MAR 05
bnostran@syr.edu