S-Box definition

The S-Box as a lookup table

>

SBoxTable :=table(["01000010" = "00101100", "10101000" = "11000010", "10110110" = "01001110", "00011010" = "10100010", "00111000" = "00000111", "11011000" = "01100001", "00000101" = "01101011", "00101111" = "00010101", "00110101" = "10010110", "00111111" = "01110101", "10000010" = "00010011", "00000110" = "01101111", "00100011" = "00100110", "10010010" = "01001111", "11000000" = "10111010", "11010000" = "01110000", "10111010" = "11110100", "10010111" = "10001000", "10101011" = "01100010", "11100110" = "10001110", "11101100" = "11001110", "00011101" = "10100100", "00000000" = "01100011", "10100010" = "00111010", "11000001" = "01111000", "00011001" = "11010100", "01101110" = "10011111", "11101011" = "11101001", "11101111" = "11011111", "00100111" = "11001100", "11110100" = "10111111", "00000001" = "01111100", "00011011" = "10101111", "01110111" = "11110101", "11010101" = "00000011", "00010111" = "11110000", "00111100" = "11101011", "10111011" = "11101010", "01000000" = "00001001", "11111011" = "00001111", "01111001" = "10110110", "10110000" = "11100111", "10100100" = "01001001", "11000010" = "00100101", "11110111" = "01101000", "00110100" = "00011000", "01011100" = "01001010", "00001101" = "11010111", "00111110" = "10110010", "01010010" = "00000000", "01001111" = "10000100", "11000101" = "10100110", "11110110" = "01000010", "01110110" = "00111000", "00100010" = "10010011", "00101011" = "11110001", "11001000" = "11101000", "01010110" = "10110001", "10101111" = "01111001", "11011010" = "01010111", "11111010" = "00101101", "00101110" = "00110001", "11011001" = "00110101", "11100000" = "11100001", "01101111" = "10101000", "11100100" = "01101001", "01000101" = "01101110", "00001000" = "00110000", "00000010" = "01110111", "00011000" = "10101101", "00010100" = "11111010", "01000001" = "10000011", "10101110" = "11100100", "10100110" = "00100100", "01110000" = "01010001", "01010100" = "00100000", "11100001" = "11111000", "10111000" = "01101100", "00100110" = "11110111", "10110011" = "01101101", "11000100" = "00011100", "11100111" = "10010100", "11101010" = "10000111", "00001100" = "11111110", "00110110" = "00000101", "01010000" = "01010011", "11101000" = "10011011", "10001110" = "00011001", "11001001" = "11011101", "11001011" = "00011111", "10111100" = "01100101", "00100100" = "00110110", "01011110" = "01011000", "01001000" = "01010010", "10000011" = "11101100", "11100101" = "11011001", "11011101" = "11000001", "00010000" = "11001010", "01001101" = "11100011", "01111010" = "11011010", "11010100" = "01001000", "00101100" = "01110001", "01011011" = "00111001", "01011101" = "01001100", "10011100" = "11011110", "01001110" = "00101111", "11001110" = "10001011", "00011111" = "11000000", "00101010" = "11100101", "11110000" = "10001100", "00110111" = "10011010", "11101101" = "01010101", "11100011" = "00010001", "10011011" = "00010100", "01010001" = "11010001", "10100101" = "00000110", "01011111" = "11001111", "01100001" = "11101111", "10001010" = "01111110", "00101001" = "10100101", "00110000" = "00000100", "01100111" = "10000101", "10101100" = "10010001", "11010010" = "10110101", "00100000" = "10110111", "10000101" = "10010111", "01101001" = "11111001", "00000100" = "11110010", "10110100" = "10001101", "01100010" = "10101010", "01101010" = "00000010", "01000111" = "10100000", "00111001" = "00010010", "11010001" = "00111110", "10010011" = "11011100", "10011101" = "01011110", "01110101" = "10011101", "11001111" = "10001010", "00001011" = "00101011", "01111111" = "11010010", "11010011" = "01100110", "00011100" = "10011100", "11111110" = "10111011", "00011110" = "01110010", "10000001" = "00001100", "10001011" = "00111101", "00010110" = "01000111", "10010100" = "00100010", "10110101" = "11010101", "01110011" = "10001111", "11011111" = "10011110", "11111001" = "10011001", "10101010" = "10101100", "10111101" = "01111010", "11000111" = "11000110", "11110010" = "10001001", "01101000" = "01000101", "10010000" = "01100000", "00110001" = "11000111", "01011000" = "01101010", "10000000" = "11001101", "10000100" = "01011111", "10001111" = "01110011", "10110111" = "10101001", "10011000" = "01000110", "01111101" = "11111111", "10000111" = "00010111", "11110101" = "11100110", "11000110" = "10110100", "10110010" = "00110111", "01101011" = "01111111", "01111100" = "00010000", "10110001" = "11001000", "00111011" = "11100010", "01000100" = "00011011", "11111111" = "00010110", "01100110" = "00110011", "01111110" = "11110011", "10100001" = "00110010", "00101101" = "11011000", "01011010" = "10111110", "00111101" = "00100111", "10101101" = "10010101", "10000110" = "01000100", "00010010" = "11001001", "11110001" = "10100001", "01101101" = "00111100", "10011010" = "10111000", "01000110" = "01011010", "01001001" = "00111011", "10100000" = "11100000", "11101110" = "00101000", "11111101" = "01010100", "00001111" = "01110110", "00111010" = "10000000", "11100010" = "10011000", "01110001" = "10100011", "11111000" = "01000001", "11000011" = "00101110", "00010101" = "01011001", "01010011" = "11101101", "01110010" = "01000000", "10111110" = "10101110", "00001110" = "10101011", "00010001" = "10000010", "10001100" = "01100100", "01001010" = "11010110", "10101001" = "11010011", "11001100" = "01001011", "10001101" = "01011101", "11001010" = "01110100", "10001001" = "10100111", "10010001" = "10000001", "11011011" = "10111001", "00010011" = "01111101", "00100101" = "00111111", "01100000" = "11010000", "01001100" = "00101001", "10011111" = "11011011", "11101001" = "00011110", "00001001" = "00000001", "00000111" = "11000101", "01011001" = "11001011", "01111011" = "00100001", "10001000" = "11000100", "10111111" = "00001000", "00101000" = "00110100", "10100111" = "01011100", "10111001" = "01010110", "00000011" = "01111011", "00110010" = "00100011", "01001011" = "10110011", "11110011" = "00001101", "01010111" = "01011011", "11011100" = "10000110", "10010101" = "00101010", "10010110" = "10010000", "01100011" = "11111011", "01100101" = "01001101", "11010111" = "00001110", "01110100" = "10010010", "11001101" = "10111101", "01010101" = "11111100", "01101100" = "01010000", "10100011" = "00001010", "11111100" = "10110000", "10011110" = "00001011", "11011110" = "00011101", "01111000" = "10111100", "10011001" = "11101110", "01000011" = "00011010", "11010110" = "11110110", "00001010" = "01100111", "00110011" = "11000011", "01100100" = "01000011", "00100001" = "11111101"]):

The inverse S-Box as a lookup table

>

InvSBoxTable :=  table(["00000010" = "01101010", "01101001" = "11100100", "01100000" = "10010000", "00001111" = "11111011", "00010100" = "10011011", "00100000" = "01010100", "11101100" = "10000011", "10111110" = "01011010", "01101100" = "10111000", "10001000" = "10010111", "01011110" = "10011101", "00100100" = "10100110", "11111000" = "11100001", "00111110" = "11010001", "11011010" = "01111010", "11110000" = "00010111", "10111000" = "10011010", "00101001" = "01001100", "11100101" = "00101010", "00000111" = "00111000", "10110101" = "11010010", "00111001" = "01011011", "11100000" = "10100000", "11110001" = "00101011", "01110011" = "10001111", "00100111" = "00111101", "00101000" = "11101110", "11110110" = "11010110", "01010011" = "01010000", "00001011" = "10011110", "11001001" = "00010010", "00001000" = "10111111", "00000100" = "00110000", "00101010" = "10010101", "10010000" = "10010110", "10101100" = "10101010", "01100110" = "11010011", "10111111" = "11110100", "01000011" = "01100100", "00001101" = "11110011", "10000001" = "10010001", "01001001" = "10100100", "01001110" = "10110110", "00110000" = "00001000", "10100101" = "00101001", "10001010" = "11001111", "11110101" = "01110111", "00000110" = "10100101", "10111010" = "11000000", "10110010" = "00111110", "11110111" = "00100110", "00111111" = "00100101", "00000000" = "01010010", "11001110" = "11101100", "10101111" = "00011011", "00110011" = "01100110", "01111011" = "00000011", "10000010" = "00010001", "11101010" = "10111011", "10110001" = "01010110", "11000101" = "00000111", "10000011" = "01000001", "11110011" = "01111110", "10111011" = "11111110", "01101101" = "10110011", "10001111" = "01110011", "01101010" = "01011000", "00100010" = "10010100", "01000101" = "01101000", "00000001" = "00001001", "00010010" = "00111001", "01010000" = "01101100", "10011101" = "01110101", "10101011" = "00001110", "10000110" = "11011100", "00001110" = "11010111", "11011000" = "00101101", "01011111" = "10000100", "10001011" = "11001110", "01100101" = "10111100", "10111101" = "11001101", "10010011" = "00100010", "10000100" = "01001111", "11101111" = "01100001", "11001000" = "10110001", "11110100" = "10111010", "00101110" = "11000011", "10010010" = "01110100", "00110010" = "10100001", "10011100" = "00011100", "00100011" = "00110010", "00101011" = "00001011", "01010100" = "11111101", "11011001" = "11100101", "10101001" = "10110111", "01110101" = "00111111", "11011100" = "10010011", "10011011" = "11101000", "01010101" = "11101101", "11000110" = "11000111", "01100010" = "10101011", "10101101" = "00011000", "11100100" = "10101110", "01000111" = "00010110", "00010101" = "00101111", "11010110" = "01001010", "10011110" = "11011111", "01001010" = "01011100", "10100110" = "11000101", "01111000" = "11000001", "01111101" = "00010011", "00010111" = "10000111", "10000101" = "01100111", "00100110" = "00100011", "01111100" = "00000001", "11011111" = "11101111", "00011111" = "11001011", "11001011" = "01011001", "01001100" = "01011101", "01110010" = "00011110", "01101011" = "00000101", "01000010" = "11110110", "10011010" = "00110111", "11111110" = "00001100", "00011010" = "01000011", "10110110" = "01111001", "10100001" = "11110001", "11100011" = "01001101", "01100011" = "00000000", "11001100" = "00100111", "11010000" = "01100000", "01110110" = "00001111", "00111010" = "10100010", "10100111" = "10001001", "01001111" = "10010010", "11000001" = "11011101", "11110010" = "00000100", "10100010" = "00011010", "01011000" = "01011110", "10110100" = "11000110", "01100001" = "11011000", "01010111" = "11011010", "11101001" = "11101011", "00011000" = "00110100", "01011010" = "01000110", "11101000" = "11001000", "10101010" = "01100010", "00110100" = "00101000", "00010000" = "01111100", "01111110" = "10001010", "00100101" = "11000010", "11111011" = "01100011", "11100001" = "11100000", "01101000" = "11110111", "11111010" = "00010100", "10010001" = "10101100", "11000100" = "10001000", "10001101" = "10110100", "00011001" = "10001110", "01011100" = "10100111", "01010010" = "01001000", "10011000" = "11100010", "10100000" = "01000111", "01000000" = "01110010", "00111011" = "01001001", "10001001" = "11110010", "01111010" = "10111101", "01101111" = "00000110", "11111001" = "01101001", "00101111" = "01001110", "11101110" = "10011001", "11010101" = "10110101", "11001010" = "00010000", "10100011" = "01110001", "10101110" = "10111110", "01001011" = "11001100", "00011011" = "01000100", "11101011" = "00111100", "10000111" = "11101010", "11000011" = "00110011", "00101100" = "01000010", "10010111" = "10000101", "01010110" = "10111001", "01110001" = "00101100", "11011110" = "10011100", "00000011" = "11010101", "10110000" = "11111100", "01110100" = "11001010", "11011011" = "10011111", "11000000" = "00011111", "10010110" = "00110101", "00001100" = "10000001", "00010011" = "10000010", "01011101" = "10001101", "10001100" = "11110000", "00110101" = "11011001", "00111000" = "01110110", "01000100" = "10000110", "10010100" = "11100111", "11010111" = "00001101", "10110111" = "00100000", "00111100" = "01101101", "01000001" = "11111000", "11111101" = "00100001", "00011101" = "11011110", "10101000" = "01101111", "01011001" = "00010101", "01111001" = "10101111", "11111111" = "01111101", "10110011" = "01001011", "01110000" = "11010000", "10111001" = "11011011", "00110001" = "00101110", "01010001" = "01110000", "00011100" = "11000100", "11000010" = "10101000", "11010100" = "00011001", "00010001" = "11100011", "01110111" = "00000010", "11101101" = "01010011", "11001101" = "10000000", "01100100" = "10001100", "11000111" = "00110001", "00010110" = "11111111", "10000000" = "00111010", "11100110" = "11110101", "10011001" = "11111001", "00001001" = "01000000", "01000110" = "10011000", "11010001" = "01010001", "10011111" = "01101110", "00101101" = "11111010", "00001010" = "10100011", "11111100" = "01010101", "10111100" = "01111000", "00100001" = "01111011", "10100100" = "00011101", "11100010" = "00111011", "11011101" = "11001001", "00110110" = "00100100", "00111101" = "10001011", "11001111" = "01011111", "10001110" = "11100110", "11010011" = "10101001", "11100111" = "10110000", "00000101" = "00110110", "11010010" = "01111111", "00011110" = "11101001", "01100111" = "00001010", "10010101" = "10101101", "01001101" = "01100101", "01111111" = "01101011", "00110111" = "10110010", "01001000" = "11010100", "01101110" = "01000101", "01011011" = "01010111"]):

Preparing some keys

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 two keys for test purposes.  The first one starts with a nice hex string.  The second one is randomly generated

>	testKeyHex := "0123456789ABCDEF0123456789ABCDEF"; testKeyList := [seq(substring(testKeyHex,i*2-1..i*2),i=1..16)]; hexTo8Bits := hexPair -> substring(convert(convert(     convert(hexPair,decimal,hex)+256,binary),string),2..9): testKey := map(hexTo8Bits,testKeyList);

>	intToBits := intValue ->   substring(convert(convert(intValue+256,binary), string), 2..9): randKeyInt := [seq(rand(0..255)(),i=1..16)]; randKey := map(intToBits, randKeyInt);

Step by step key expansion

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: 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)):

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;

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

We can convert the expanded key to integer values for easy viewing.

>	bitToInt := bitWord -> convert(parse(bitWord),decimal,binary): map(bitToInt,keyExpanded);

>

Code for one line commands

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:

Expanded Example

It may be useful to have an expanded example done.  Thus we include the following values.

>

testKeyList := ["01","23","45","67","89","AB","CD","EF",             "01","23","45","67","89","AB","CD","EF"]: testKey := ["00000001", "00100011", "01000101", "01100111",             "10001001", "10101011", "11001101", "11101111",             "00000001", "00100011", "01000101", "01100111",             "10001001", "10101011", "11001101", "11101111"]: key1 := matrix([["00000001", "10001001", "00000001", "10001001",    "01100010", "11101011", "11101010", "01100011", "00011010",    "11110001", "00011011", "01111000", "00010101", "11100100",    "11111111", "10000111", "00111000", "11011100", "00100011",    "10100100", "01001101", "10010001", "10110010", "00010110",    "11000011", "01010010", "11100000", "11110110", "10101001",    "11111011", "00011011", "11101101", "01111010", "10000001",    "10011010", "01110111", "01010111", "11010110", "01001100",    "00111011", "10001000", "01011110", "00010010", "00101001"],    ["00100011", "10101011", "00100011", "10101011", "10011110",    "00110101", "00010110", "10111101", "00000000", "00110101",    "00100011", "10011110", "01001010", "01111111", "01011100",    "11000010", "01011101", "00100010", "01111110", "10111100",    "01011110", "01111100", "00000010", "10111110", "01010101",    "00101001", "00101011", "10010101", "11000111", "11101110",    "11000101", "01010000", "01011111", "10110001", "01110100",    "00100100", "00001010", "10111011", "11001111", "11101011",    "00100001", "10011010", "01010101", "10111110"],    ["01000101", "11001101", "01000101", "11001101", "10011010",    "01010111", "00010010", "11011111", "11000110", "10010001",    "10000011", "01011100", "11001001", "01011000", "11011011",    "10000111", "11010001", "10001001", "01010010", "11010101",    "10010000", "00011001", "01001011", "10011110", "10111000",    "10100001", "11101010", "01110100", "11011101", "01111100",    "10010110", "11100010", "11100101", "10011001", "00001111",    "11101101", "01110000", "11101001", "11100110", "00001011",    "11011111", "00110110", "11010000", "11011011"],    ["01100111", "11101111", "01100111", "11101111", "11000000",    "00101111", "01001000", "10100111", "00111011", "00010100",    "01011100", "11111011", "10000111", "10010011", "11001111",    "00110100", "10010000", "00000011", "11001100", "11111000",    "11011001", "11011010", "00010110", "11101110", "10011110",    "01000100", "01010010", "10111100", "11011100", "10011000",    "11001010", "01110110", "10001001", "00010001", "11011011",    "10101101", "01111100", "01101101", "10110110", "00011011",    "10011110", "11110011", "01000101", "01011110"]]):