Conversions

Mike May, S.J. 1998

(Worksheet 1 for Cryptography and Coding Theory)

This worksheet is focused on the preliminary work of conversion of data formats. As we work with encryption, we will want to put messages in a number of different formats. We first want to convert back and forth between normal text and strings of numbers. For reasons that will become apparent later we will also want to be able to convert the numbers between decimal, binary, and hexidecimal formats. Finally we want to be able to concatonate the hex numbers into blocks.

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 we enclosed the message in single open quotes. That told maple to use the string rather than try to interpret it as a collection of variables.)

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

Conversion 1 - Letters to numbers and back again

For most of the encription 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. The first naive conversion is to let a be represented by the number 1, b by the number 2, 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 charachters. Instead we will use 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[1];
temp[2] := convert(temp[1], bytes);
temp[2];

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, it 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.

Exercises

1) Produce a conversion chart for converting the lower case letters in the set {a, c, e, g, h, i, m, r, s, t} to the ASCII equivalent.

>

2) Produce a conversion chart for converting the special characters in the string

`,.;' :"[]{}()!$%?` used for punctuation to ASCII.

>

3) Use your table to convert the string `this is a secret message` to ASCII. Use Maple to check your work.

>

4) Type the first full paragraph on page 7 of your book (by Beutelspacher) and save it as message2. Use Maple to convert message2 to the string of numbers corresponding to the ascii equivalents.

>

Warning - A bug in the Maple conversion routine

There is are two bugs in the Maple conversion routine that you should be aware of. Neither affects the characters we normally use in typing, but they are worth noting anyway. The first bug is that Maple converts both 10 and 13 to carriage return, which is converted back to 13. The second bug is that while the number to character conversion accepts integers from 1 to 255, the character to number conversion returns an output that is a signed integer between -128 and 127.

> numstring := [seq(i,i=5..15),seq(i,i=120..140)];
charstring := convert(numstring,bytes);
numstring2 := convert(charstring, bytes);

Conversions 2 - Other number systems

For most math classes we do arithmetic in base 10. The base was chosen by an accident of history. (Lookat 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 hexidecimal.

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

convert(xxx, binary);

The command to convert to hexidecimal 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 hexidecimal 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);

Exercises:

5) Covert message2 to an array of binary numbers.

>

6) Convert message2 to an array of hexidecimal numbers.

>

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 combersome to write. You should notice that every ASCII character we have tried to convert is two characters long. That makes hex a good system for concatinating characters into words of uniform size. We now define procedures for turning a vector of hexidecimal numbers into an array of blocks of with bsize numbers put into a block and the last block padded out with zeroes. We also define a procedure for undoing the blocking.

> blocker := proc(hexvec,bsize)
local l1, l2, l3, i, j, temp, hexblock;
temp := hexvec;
l1 :=linalg[vectdim](hexvec);
l2 := l1 + bsize -1 - (l1 + bsize - 1 mod bsize);
l3 := l2/bsize;
for j from l1 + 1 to l2 do
temp := [op(temp),`00`];
od;
hexblock := [];
for i from 1 to l3 do
hexblock := [op(hexblock) ,cat(seq(temp[bsize*i + j], j = 1-bsize..0))];
od;
hexblock;
end:

> bl4 := blocker(temp[4],4);
bl5 := blocker(temp[4],5);
bl7 := blocker(temp[4],7);

Notice that blocks of size 7 required 1 more character, while blocks of size 4 and 5 needed 2 extra characters to make the blocks come out even.

> unblocker := proc(hexblock,bsize)
local l1, i, j, hexvec;
l1 :=linalg[vectdim](hexblock);
hexvec := [];
for i from 1 to l1 do
hexvec := [op(hexvec) ,
seq(substring(hexblock[i],2*j-1..2*j), j = 1..bsize)];
od;
hexvec;
end:

> s4 := unblocker(bl4, 4);
s5 := unblocker(bl5, 5);
s7 := unblocker(bl7, 7);

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 three steps can be done in one line.

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

Exercises:

7) Convert message2 into hex blocks with 5 characters going into each word. (The words in your answer should appear to be 10 letters long.)

>

8) Convert the message

[`415A617A20`, `5468652072`, `61696E2069`, `6E20537061`, `696E206661`, `6C6C73206D`, `61696E6C79`, `20696E2074`, `686520706C`, `61696E2E20`, `415A617A00`]

back to plaintext from hex blocks.

>

When you finish the worksheet, print it up and turn it in.