Entering a message

To be able to look at specific examples, we start by creating a standard message that we will work with.

>	message1 :="AZaz Good morning Mr. Phelps.  Your mission for today, should you choose to accept it, is to encode this message. AZaz"; message1;

(Notice that strings handle carriage returns as the special character "\n".  If we want to include the " symbol we use either a backslash quote \", or a double quote ''.)

The plain text starts and ends with the string AZaz to give easy clues for understanding the conversions.

>

Conversions 1 - Letters to numbers and back again

For most of the encryption systems we will study this semester, we have to look at a preliminary task of converting the messages into some kind of numerical equivalent that we can apply our equations to.  

With the classical ciphers we have looked at we considered a simple conversion that let a be represented by the number 0, b by the number 1, and so on down to z.  This is easy to do by hand once we make a conversion table.  Unfortunately, that system has the drawback of not dealing with capitol and small letters or spaces and other special characters.  Instead we will used a conversion to ASCII.  ASCII is the standard conversion used for most current computer systems.

With Maple, we convert between alphanumeric strings and strings of integers with the convert command.  The syntax is
     convert(xxx, bytes);

The same command works both ways.

>	temp[1] := convert(message1, bytes); temp[2] := convert(temp[1], bytes);

(Maple will convert from either a name (enclosed in back quotes `) or a string (enclosed in double quotes "), but it returns a string.  You must explicitly convert to type name if that is what we want.)

>

We can see that the ASCII conversion takes A to 65, Z to 90, a to 97, z to 122, and a blank space to 32.  The letters between a and z are converted in order so that B is 66 and b is 98.

The convert command can also be used on an array of integers.

>	convert([65,255, 66, 256, 67, 257, 68], bytes); convert([65,2,66, 1, 67, 0, 68, -2, 69],bytes);

A few things to notice:

1)  The convert function from integer to ASCII assumes the input is between 1 and 255, inclusive.  If fed an integer outside that range, the conversion routine stops.  In that case, it does not process the rest of the list.

2)  We only need 52 of the 255 places for English letters counting upper and lower case.  That leaves enough room for all the special characters and a lot of extra space as well.

>

Conversions 2 - Other number systems (hexadecimal in particular)

For most math classes we do arithmetic in base 10.  The base was chosen by an accident of history.  (Look at your hands and identify the accident.)  When we deal with digital computers we often do binary arithmetic do to an accident of mechanics. (The accident is that transistors have two states, on and off.)  One of the disadvantages of binary is that the numbers quickly become too long.  That has led to the use of base 16, or hexadecimal.

The syntax used to convert a decimal number xxx to binary is

     convert(xxx, binary);

The command to convert to hexadecimal is similar,

     convert(xxx, hex);

There is a catch with these two commands.  We want to use them on an array of decimal numbers.  To do this we use the map command.  The commands to convert an array, XXX, of decimal numbers to binary and hexadecimal are respectively:

     map(convert, XXX, binary);

     map(convert, XXX, hex);

The commands to reverse the processes are:

     map(convert, XXX, decimal,  binary);

     map(convert, XXX, decimal, hex);

>	temp[3] := map(convert, temp[1], binary); temp[4] := map(convert, temp[1], hex); temp[5] := map(convert, temp[3], decimal, binary); convert(temp[5], bytes); temp[6] := map(convert, temp[4], decimal, hex); convert(temp[6], bytes);

We want to make a small modification to hex.  Most ASCII characters convert to a two character hex string.  The usual convention of number writing drops leading zeroes.  For technical reasons we would like each character to be represented by a string of the same hex length.  Thus we introduce a procedure to include the leading zero if needed.

>	twodigithex := a -> substring(convert(256+a,hex),2..3): temp[a4] := map(twodigithex, temp[1]);

Note that the two lists temp[4] and temp[a4] are almost the same, with the D in temp[4][56] replaced by 0D in temp[a4][56].)

Arranging letters into "words"

Using strings of numbers does give an easy first encryption.  (It is not very secure however.)   One of the problems with strings of numbers is that they are cumbersome to write.  The conversion of every ASCII character to a two character hex string lets us concatenate hex characters into words of uniform length.  We now define procedures for turning a vector of hexadecimal numbers into an array of blocks, with bsize numbers put into each block, and the last block padded out with zeroes.  We also define a procedure for undoing the blocking.

>

blocker := proc(hexvec,bsize) local numCharacters, paddingNum, numWords, i, j, temp, hexblock; temp := hexvec; numCharacters :=linalg[vectdim](hexvec); numWords := ceil(numCharacters/bsize); paddingNum := numWords*bsize - numCharacters; temp := [op(temp),seq(`00`,j = 1..paddingNum)]; hexblock :=      [seq( cat(seq(temp[bsize*i + j], j = 1..bsize)), i=0..numWords-1)]: end:

>	numCharacters :=linalg[vectdim](temp[a4]); bl4 := blocker(temp[a4],4); bl7 := blocker(temp[a4],7); bl11 := blocker(temp[a4],11);

Notice that blocks of size 4 require 1 more character, while blocks of size 7 come out even, and blocks of size 11 need 2 extra characters to make the blocks come out even.

>	unblocker := (hexblock,bsize) ->    map(hexString -> seq(substring(hexString,2*j-1..2*j), j = 1..bsize),       hexblock):

>	s4 := unblocker(bl4, 4); s7 := unblocker(bl7, 7); s11 := unblocker(bl11, 11);

It is worthwhile to convert from blocks all the way back to the original message.

>	s7 := unblocker(bl7, 7); b7 := map(convert, s7, decimal, hex); convert(b7, bytes);

It should be noted that all four steps can be done in one line.

>	convert(map(convert, unblocker(bl7,7), decimal, hex), bytes);

Conversions 3 - Binary numbers and finite fields.

A number of commercial codes, including AES, include steps where binary numbers are viewed as numbers in finite fields and combined with the arithmetic in the finite field.  For this worksheet we simply are concerned with the conversion routines.  The conversion is done by considering the digits of the binary number as the coefficients on a polynomial in the variable alpha.  The coefficients can be either 0 or 1 and are listed highest power first.

>	binPoly := proc(binNum)    local binString, temp, stringLen, i:    binString := convert(binNum, string):    temp := 0:    stringLen := length(binString):    for i from 1 to stringLen do       temp := temp +         alpha^(stringLen-i)*parse(substring(binString,i)); od:    sort(temp); end:

>	polya := binPoly(1000110001111);

To convert back, we simply evaluate the polynomial with alpha equaling 2, then convert to a binary representation.

>	polyBin := poly -> convert(subs(alpha=2, poly), binary):

>	polyBin(polya);