Technical details I - Alphabets

One of our objectives is to mask the beginning and ending of words to keep an attacker from using that information for an attack on our code.  This could be done by removing spaces and punctuation before we encode, but that also confuses the message after it has been decoded by the person we are sending it to.  The other strategy is to consider special characters as part of a larger alphabet.  Since Maple has a command to convert characters in a string to ASCII equivalents, it is easiest to simply use the normal ASCII character set for our alphabet.  That means that our alphabet has 127 letters in it.  In keeping with the numbering conventions of ASCII, we will also be using clock arithmetic rather than modular arithmetic.  (Our numbers will go from 1 to 127 rather than from 0 to 126.)  We notice as a bonus that 127 is prime.  We start by defining a command that adjust numbers from modular notation to clock arithmetic.

>	clock127 := x -> ((x-1) mod 127) + 1:

Initial Variables and Message Length

We next need a message and an encrypting key.  Our initial key will be a 3 by 3 invertible matrix over .  For the next several worksheets, our messages will begin and end with know strings.  Our beginning string is "az AZ - Good morning, Mr. Phelps.

The secret message for today is:"

The ending string is "az AZ".  Notice that the beginning string has a newline character in the middle of it.

Our secret message for today is a poem by Ogden Nash.

>

mess1 := `az AZ - Good morning, Mr. Phelps. The secret message for today is: I objurgate the centipede, A bug we realy do not need. At sleepy time he beats a path Straight to bedroom or the bath. You always wollop where he's not, Or if he is, he leaves a spot. az AZ`: nums1 := convert(mess1, bytes); mykey := matrix([[1,2,3],[0,5,7],[0,0,11]]);

We want to check the determinant of mykey and that mykey is invertible over .

>	Det(mykey) mod 127; unkey := Inverse(mykey) mod 127;

Since we are encrypting the message in blocks of three characters, the next detail is to make sure that the message  has a length divisible by three (the size of the encrypting matrix).  Evensize is a procedure that takes a list of decimal numbers and pads it out with 32's to make the message a length divisible by the size of the key.  (the ASCII equivalent of 32 is a blank space.)

>	linalg[vectdim](nums1);

>	evensize := proc(decvec,bsize) local charLength, paddingLength, j, temp; temp := decvec; charLength :=linalg[vectdim](decvec); paddingLength := (bsize - irem(charLength, bsize)) mod bsize; temp := [op(temp),seq(32, j=1..paddingLength)]: #temp; end:

>	nums2 := evensize(nums1,3);

Encoding by Matrix Multiplication

Next we want to define the procedure that multiplies the matrix by appropriate vectors from the decimal list.

>

matmult := proc(decvec, key, keysize) local l1, l3, i, j, k, temp, temp2, temp3; temp2 := linalg[vector](keysize); temp := convert(decvec,array); l1 :=linalg[vectdim](temp); l3 := l1/keysize; for j from 0 to (l3 -1) do    for i from 1 to keysize do      temp2[i] := temp[j*keysize+i]:    od;    temp2 := map(clock127,linalg[multiply](key,temp2)):    for i from 1 to keysize do      temp[j*keysize + i] := temp2[i]:          od: od; convert(temp,list); end:

Now we apply the transformation, then convert back to ASCII and print the message.

>	nums3 := matmult(nums2,mykey,3); mess2 := convert(nums3,bytes);

The printed ciphertext is not very manageable.  By using the larger alphabet, we now have special characters sprinkled throughout the ciphertext.  It makes retyping the ciphertext impossible, and we also could not include the ciphertext in a mail message.  Before we look at that problem, let us make sure that we can decipher the message.  Decryption should be done by the same process of matrix multiplication with a key that is the inverse of the original key.

>	unkey := Inverse(mykey) mod 127;

>	nums4 := matmult(nums3, unkey, 3); mess3 := convert(nums4, bytes); convert(mess3,name);

Cleaning up the Ciphertext

Now we get to worry about presenting the encoded message.  The easiest solution seems to be to go back to hex representation, then store the code in blocks corresponding to 3 (the size of the key) characters.  We need to recall the procedures defined in the Type Conversions worksheet for blocking and unblocking hex vectors.

>

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: unblocker := (hexblock,bsize) ->   map(hexString -> seq(substring(hexString,2*j-1..2*j), j = 1..bsize),hexblock):

We have one more problem to be aware of.  Our use of the procedure blocker assumes that every ASCII character has a two digit hex representation.  However Maple's conversion to hex follows the usual math convention and leaves off leading zeroes.  With normal ASCII text, this only give us problems if a newline (ASCII equivalent of 13) is included, since that would be represented by a single hex character.  After we have used the Hill cipher, the characters are distributed, so it should give us a problem for 1 character out of 8.  We solve this problem by recalling a procedure converts to 2 character hex strings.

>	intTo2dHex := intValue -> substring(convert(intValue+256,hex), 2..3):

Now we can convert our output to hex blocked words.

>	nums5 := map(intTo2dHex, nums3); nums6 := blocker(nums5,3);

As always, we want to test that this final encoded message can be decoded.

>	nums7 := unblocker(nums6,3); nums8 := map(convert,nums7,decimal,hex); nums9 := matmult(nums8,unkey,3); mess4 := convert(nums9,bytes); convert(mess4, name);

Cleaning up our procedures

Since we will be storing our cyphertext in hex blocks we can rewrite our procedures to make them a bit more compact and portable.  This will also make them easier to copy and paste if we want to use them on another worksheet.

Our first two procedures are for housekeeping.  The next two are procedures to convert a string into a list of blocked hex words and back again.   We give these procedures the names stringtoblocks and blockstostring.

>

>

clock127 := x -> ((x-1) mod 127) + 1: intTo2dHex := intValue -> substring(convert(intValue+256,hex), 2..3): stringtoblocks := proc(charstring,bsize)    local declist, hexlist, hexblock, i, j, numChars, numBlocks, paddingLength:   #First we convert string to decimals and padd out with spaces    declist := convert(charstring,bytes):    numChars :=linalg[vectdim](declist);    numBlocks := ceil(numChars/bsize):    paddingLength := numBlocks*bsize - numChars:    declist := [op(declist),seq(32, j=1..paddingLength)];   #Now we convert to hex and block into words    hexlist := map(intTo2dHex,declist):    hexblock := [seq(cat(seq(hexlist[bsize*i + j], j = 1-bsize..0)),i=1..numBlocks)]; end: blockstostring := proc(hexblock,bsize)    local declist, hexlist, charstring, i, j, l1:   #First we back to a list of hex characters    hexlist := map(hexString ->       seq(substring(hexString,2*j-1..2*j), j = 1..bsize), hexblock);   #Then we convert back to a decimal list, then to a string.    declist := map(convert,hexlist,decimal,hex):    charstring := convert(declist,bytes): end:

We also need a procedure for multiplying a matrix times a hex word.

>

matmultbloc := proc(word,key,bsize)    local i, j, decvect, hexvect, hexword:    decvect := linalg[vector]([seq(      convert(substring(word,(2*i-1)..(2*i)),decimal,hex),i=1..bsize)]):    decvect := map(clock127, linalg[multiply](key,decvect)):    hexvect := map(intTo2dHex,decvect):    hexword := cat(seq(hexvect[j],j=1..bsize)): end:

We want to define a key and use these procedures to uncrypt a message, then decrypt it to check our work.

>	key5 := matrix(5,5,[[1,2,3,4,5],[7,0,0,0,0],[0,0,0,12,0],[0,0,13,0,0], [0,11,0,0,0]]); a:= stringtoblocks(mess1,5); secret1 := map(matmultbloc,a,key5,5); unkey5 := Inverse(key5) mod 127; b := map(matmultbloc,secret1,unkey5,5); test1 := blockstostring(b,5); convert(test1,name);