AES Key Expansion \302\2512007 by Mike May, S.J., Saint Louis University - maymk@slu.edu restart; A second block of material in understanding the AES algorithm is the routine for expansion of a 128 bit key into a collection of 11 round keys, each of which is a 4 b 4 section of a matrix, with entries each being a byte, or 8 bits string. The procedure for expanding a key requires the use of the S-Box used for AES. The S-Box was derived in an earlier worksheet and is read from a file which should be in the current directory. read `AES.m`; In particular we have loaded: Look up tables: SBoxTable and InvSBoxTable. Each is indexed by an 8 character binary string and returns the appropriate 8 bit binary string. Standard byte format conversion functions: hexTo8Bits, intToBits, polyToInt, polyToBits; Similar conversion functions for 128 bit strings: intTo32Hex;

To look at key expansion, it is most convenient to think of an AES key as a list of 16 strings, each of which is an 8 bit byte. We produce three keys for test purposes. The first one starts with a nice hex string, the second is all zeros, and the third one is randomly generated. testKeyHex := "0123456789ABCDEF0123456789ABCDEF"; testKeyList := [seq(substring(testKeyHex,i*2-1..i*2),i=1..16)]; testKey := map(hexTo8Bits,testKeyList); zeroKeyHex := intTo32Hex(0); zeroKeyList := [seq("00",i=1..16)]; zeroKey := map(hexTo8Bits,zeroKeyList); randKeyHex := intTo32Hex(rand(2^128)()); randKeyList := [seq(substring(randKeyHex,i*2-1..i*2),i=1..16)]; randKey := map(hexTo8Bits, randKeyList);

In each round of the key expansion we need the byte representation of (alpha)^(i-1) in the finite field GF(258) with the specified generating polynomial. This is added in as a fudge factor each round of the expanded key. genPoly := alpha^8 + alpha^4 + alpha^3 + alpha + 1: roundFudge := int -> Rem(alpha^(int-1),genPoly,alpha) mod 2: roundFudgeWord := int -> polyToBits(roundFudge(int)): For the version of AES we are using there are 10 rounds. (The number of rounds depends on both the size used for the key and the size used for the message block.) for i from 1 to 10 do print(i,roundFudge(i),roundFudgeWord(i)) end do;

We also need to be able to XOR 8 bit string representations of bytes. XOR := (a,b) -> if (a=b) then "0" else "1" fi: xorNbits := proc(a,b,N) local aString, bString: aString := convert(a,string): bString := convert(b,string): cat(seq(XOR(substring(aString,i), substring(bString,i)),i=1..N)): end: xor8 := (a,b) -> xorNbits(a,b,8):

We are ready to start making the round keys. Since we have 10 rounds we need 11 keys with a key being 16 bytes. We arrange the expanded key as a 4 by 44 matrix with the original key in the first 4 columns. keyExpanded := matrix(4,44): for j from 1 to 4 do for i from 1 to 4 do keyExpanded[i,j] := testKey[(j-1)*4+i]; end do; end do; keyExpanded[1,2];

Now we recursively define the round keys. The ith round defines columns 4*i+1 through 4*i+4. Each column is defined by a process that looks at the previous column and the one 4 columns back. Three of the four columns in a round are created by simply XORing the two columns that it depends on. The first column in a round twists one of the columns first, does an S-Box lookup, and adds in a fudge factor based on the number of the round. [Recall that the book's description of AES numbers the columns from 0 and we are numbering them from 1. We want the special rule used for the first column in a round.] for i from 1 to 10 do # Create the fudge factor added in on the block fudgeWord := roundFudgeWord(i); # Use special process for first column in a block keyExpanded[1,4*i+1] := xor8(keyExpanded[1,4*i-3], SBoxTable[keyExpanded[2,4*i]]); keyExpanded[1,4*i+1] := xor8(keyExpanded[1,4*i+1],fudgeWord); keyExpanded[2,4*i+1] := xor8(keyExpanded[2,4*i-3], SBoxTable[keyExpanded[3,4*i]]); keyExpanded[3,4*i+1] := xor8(keyExpanded[3,4*i-3], SBoxTable[keyExpanded[4,4*i]]); keyExpanded[4,4*i+1] := xor8(keyExpanded[4,4*i-3], SBoxTable[keyExpanded[1,4*i]]); # Unse normal procedure for 3 remaining columns in block for j from 2 to 4 do for k from 1 to 4 do keyExpanded[k,4*i+j] := xor8(keyExpanded[k,4*i+j-4], keyExpanded[k,4*i+j-1]): end do: end do: end do:

We can convert the expanded key to integer values for easy viewing. We then break the extended key into 4 by 4 round keys. print(convert([k1],Matrix)); bitToInt := bitWord -> convert(parse(bitWord),decimal,binary): keyMatrixToRoundKeys := keyMatrix ->seq(matrix(4,4, [seq(seq(keyMatrix[i,j+(k-1)*4],j=1..4),i=1..4)]),k=1..11): keyViewer := keyExpanded -> keyMatrixToRoundKeys(map(bitToInt,keyExpanded)): k1 := keyViewer(keyExpanded): for i from 1 to 11 do print("Round key ",i," = ", k1[i]): end do:

We would like to condense the discussion above for easier use. The first block of code below has all the preparatory code. The second block then does key expansion in a single procedure. genPoly := alpha^8 + alpha^4 + alpha^3 + alpha + 1: roundFudge := int -> Rem(alpha^(int-1),genPoly,alpha) mod 2: polyToInt := poly -> subs(alpha=2, poly): intToBits := intValue -> substring(convert(convert(intValue+256, binary), string), 2..9): polyToBits := poly -> intToBits(polyToInt( poly)): roundFudgeWord := int -> polyToBits(roundFudge(int)): XOR := (a,b) -> if (a=b) then "0" else "1" fi: xorNbits := proc(a,b,N) local aString, bString: aString := convert(a,string): bString := convert(b,string): cat(seq(XOR(substring(aString,i), substring(bString,i)),i=1..N)): end: xor8 := (a,b) -> xorNbits(a,b,8): bitToInt := bitWord -> convert(parse(bitWord),decimal,binary): intToBits := intValue -> substring(convert(convert(intValue+256,binary), string), 2..9): randKeyGenerator := () -> map(intToBits, [seq(rand(0..255)(),i=1..16)]): hexTo8Bits := hexPair -> substring(convert(convert( convert(hexPair,decimal,hex)+256,binary),string),2..9): hex32ToKey:= hexWord ->map(hexTo8Bits, [seq(substring(hexWord,2*i-1..2*i),i=1..16)]): keyExpander := proc(keyList) local keyExpanded, i, j, k, fudgeWord: keyExpanded := matrix(4,44): for j from 1 to 4 do for i from 1 to 4 do keyExpanded[i,j] := keyList[(j-1)*4+i]; end do: end do: for i from 1 to 10 do fudgeWord := roundFudgeWord(i); keyExpanded[1,4*i+1] := xor8(keyExpanded[1,4*i-3],SBoxTable[keyExpanded[2,4*i]]); keyExpanded[2,4*i+1] := xor8(keyExpanded[2,4*i-3],SBoxTable[keyExpanded[3,4*i]]); keyExpanded[3,4*i+1] := xor8(keyExpanded[3,4*i-3],SBoxTable[keyExpanded[4,4*i]]); keyExpanded[4,4*i+1] := xor8(keyExpanded[4,4*i-3],SBoxTable[keyExpanded[1,4*i]]); keyExpanded[1,4*i+1] := xor8(keyExpanded[1,4*i+1],fudgeWord); for j from 2 to 4 do for k from 1 to 4 do keyExpanded[k,4*i+j] :=xor8(keyExpanded[k,4*i+j-4],keyExpanded[k,4*i+j-1]): end do: end do: end do: keyExpanded; end:

key1 := (keyExpander(testKey)): key2 := (keyExpander(zeroKey)): key3 := (keyExpander(randKey)): k1 := keyViewer(key1): k2 := keyViewer(key2): k3 := keyViewer(key3): print("Round", " Key 1", " Key 2 ", " Key 3"); for i from 1 to 11 do print(i, k1[i], k2[i], k3[i]); end do: key4a := randKeyGenerator(); key4 := keyExpander(key4a): k4 := keyViewer(key4): hexKey := "0123456789ABCDEFFEDCBA9876543210": key5a := hex32ToKey(hexKey); key5 := keyExpander(key5a): k5 := keyViewer(key5): print("Round", " Key 4", " Key 5 "); for i from 1 to 11 do print(i, k4[i], k5[i]); end do:

Legal Notice: The copyright for this application is owned by the author(s). Neither Maplesoft nor the author are responsible for any errors contained within and are not liable for any damages resulting from the use of this material. This application is intended for non-commercial, non-profit use only. Contact the author for permission if you wish to use this application in for-profit activities.