Conversion Functions

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

>	intValue := 17; bitWord := intToBits(intValue); bitList := bitToList(bitWord); poly := listToPoly(bitList); intValue2 := polyToInt(poly);

Sbox Creation

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 Eulcidean 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.  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: s2Make := proc(bitList)    local shift1List, shift2List:    shift1List := [1,1,1,1,1,0,0,0,1,1,1,1,1,0,0,0]:    shift2List := [0,1,1,0,0,0,1,1]:    [seq(linalg[dotprod](bitList,[seq(shift1List[9+i-j],i=1..8)])           +shift2List[j] mod 2, j=1..8)]; end: sMakeIBits := intVal -> listToBits(s2Make(s1Make(intVal))):

Check by computing the first 8 values.

>	for i from 0 to 7 do sMakeIBits(i) end do;

We are ready to create the S-Box.  We would like it to be a table indexes by the possible byte values 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.

>	SBoxMatrix1 := matrix(16,16,[seq(SBoxTable[intToBits(i)],i=0..255)]);

We would then like to convert the entries to integer values so we can check them against the book.

>	SBoxMatrix2 := map( bitToInt,SBoxMatrix1);

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)]);

Results only

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

>