AES S-Box Creation \302\2512007 by Mike May, S.J., Saint Louis University - maymk@slu.edu restart; As with other symmetric block ciphers, AES has a rather complicated description. In trying to understand the structure of the algorithm, it is worth looking at the structure in several pieces. In this worksheet we look at the construction of the S-Box, or substitution box which is used for a byte substitution operation.

For the creation of the S-Box in AES we need to be able to think of an 8 bit byte in 4 different ways, as an integer from 0 through 255, as a string of 8 bits in binary, as a list of 8 bits with numeric values, and as a polynomial of degree at most 7 in alpha. We also need conversion routines to shift between the views. We start with the conversions to move cyclically between those four representations, and add others that will be useful. intToBits := intValue -> substring(convert(convert(intValue+256, binary), string), 2..9): bitToList := bitWord -> [seq(parse(substring(bitWord,i)), i=1..8)]: listToPoly := bitList -> sort(sum(bitList[j]*alpha^(8-j), j=1..8)): polyToInt := poly -> subs(alpha=2, poly): listToBits := bitList -> cat(seq(convert(bitList[i],string),i=1..8)): bitToInt := bitWord -> convert(parse(bitWord),decimal,binary): listToInt := bitList -> sort(sum(bitList[j]*2^(8-j), j=1..8)): polyToList := poly -> [seq(coeff(poly,alpha, 8-i),i=1..8)]: polyToBits := poly -> intToBits(polyToInt( poly)): bitToPoly := bitWord -> listToPoly(bitToList(bitWord)): We run through an example with the conversion functions intValue := rand(255)(); bitWord := intToBits(intValue); bitList := bitToList(bitWord); poly := listToPoly(bitList); intValue2 := polyToInt(poly);

The polynomial interpretation of a byte is bases on bytes as elements of a finite field GF(256). The construction of this field requires we fix an irreducible polynomial of degree 8 over Z_2. We include that polynomial for our computations. genPoly := alpha^8 + alpha^4 + alpha^3 + alpha + 1: For an individual entry of the S-Box, we create the value in 2 steps. In the first step we represent the number as a list of bits. If the list does not represent 0 we invert in the field GF(256). Recall that we invert in a finite field by using the extended Euclidean algorithm to represent 1 as a linear combination of the polynomial to be inverted and the generating polynomial. The coefficient of the polynomial to be inverted will be the inverse in the finite field. In the second step we multiply be a given matrix and shift by a specified vector. To keep consistent our usage where the first bit represents alpha^7 and the last bit represents 1, the top row of our matrix is [1, 1, 1, 1, 1, 0, 0, 0], and subsequent rows are obtained by rotating that row. The shift row becomes [0, 1, 1, 0, 0, 0, 1, 1]. (This uses the matrix and vector in the book but starts numbering at the lower right corner.) Given the special structure of the matrix, the matrix multiplication can be done with a shifted dot product. To get an entry of the S-Box we do these steps in order and convert the list to an 8 bit string. s1Make := proc(intValue) local bitList, invPoly, extraPoly, polyValue: bitList := bitToList(intToBits(intValue)): if (intValue <> 0) then #invert nonzero entries. polyValue := listToPoly(bitList): Gcdex(polyValue, genPoly, alpha, 'invPoly', 'extraPoly') mod 2; bitList := (polyToList(invPoly)): end if: bitList; end proc: s2Make := proc(bitList) local shift1List, shift2List: shift1List := [1,1,1,1,1,0,0,0]; shift2List := [0,1,1,0,0,0,1,1]: [seq(linalg[dotprod](bitList,ListTools[Rotate](shift1List,1-j)) +shift2List[j] mod 2, j=1..8)]; end proc: sMakeIBits := intVal -> listToBits(s2Make(s1Make(intVal))): Check by computing the first 8 values. for counter from 0 to 7 do print(sMakeIBits(counter),bitToInt(sMakeIBits(counter))); end do; We are ready to create the S-Box. [seq([seq(bitToInt(sMakeIBits(col-1+16*(r-1))),col=1..16)],r=1..16)]; For use in the algorithm, we would like the entries in the S-Box to be a binary string. We would like the S-Box to be a table indexed by the possible 8 bit strings used for look ups. This is the most efficient form for later use in the algorithm. SBoxTable := table([seq(intToBits(i)=sMakeIBits(i), i=0..255)]); For checking that we have the correct values we would like convert the table to a matrix, converting the bit strings to integers. SBoxMatrix1 := map(bitToInt, matrix(16,16,[seq(SBoxTable[intToBits(pos)],pos=0..255)])); We would also like to create a table for the inverse of the S-Box look up. Since we are working with tables, this is simply creating a table where the index and the entry are reversed. InvSBoxTable := table([seq(sMakeIBits(i)=intToBits(i), i=0..255)]);

We would like to record the result of the creation of the S-Box table and its inverse so that we can use them in another worksheet without going through all the steps. 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"]): 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"]):

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.