Maple routines

Here are some simple Maple routines which I used to support my efforts in this course. These routines are not meant to be "production-grade" software. They should be used carefully. Other high-level languages such as Mathematica would support similar routines.

Letters to numbers

Numbers to letters

Preparing RSA keys

Some bitstream routines

Computing the GAG number

Letters to numbers

Several times in the course I wanted a simple way to turn alphabetic strings into numbers. For example, this was used in exercises on Diffie-Hellman and RSA protocols. Here is a routine to do this chore.

A2N:=proc(input)
local zorch,L,ss,j_,base,num;
zorch:=0;
L:=length(input);
base:=1;num:=0;
for j_ from 1 to L do
	ss:=substring(input,L-j_+1..L-j_+1);
	if ss='a' then num:=01 elif
	ss='b' then num:=02 elif
	ss='c' then num:=03 elif
	ss='d' then num:=04 elif
	ss='e' then num:=05 elif
	ss='f' then num:=06 elif
	ss='g' then num:=07 elif
	ss='h' then num:=08 elif
	ss='i' then num:=09 elif
	ss='j' then num:=10 elif
	ss='k' then num:=11 elif
	ss='l' then num:=12 elif
	ss='m' then num:=13 elif
	ss='n' then num:=14 elif
	ss='o' then num:=15 elif
	ss='p' then num:=16 elif
	ss='q' then num:=17 elif
	ss='r' then num:=18 elif
	ss='s' then num:=19 elif
	ss='t' then num:=20 elif
	ss='u' then num:=21 elif
	ss='v' then num:=22 elif
	ss='w' then num:=23 elif
	ss='x' then num:=24 elif
	ss='y' then num:=25 elif
	ss='z' then num:=26 fi;
	zorch:=num*base+zorch;
	base:=100*base
	od;
RETURN(zorch);
end;

And here is how it could be used:

Note that when the first letter is "a", the output number should begin "01" but leading 0's aren't printed: an amateur's routine.

TOP

Numbers to letters

Here is the routine which changes correctly prepared numbers into strings of letters.

N2A:=proc(input)
local cut_down, ss,zorch,alph;
alph:=`abcdefghijklmnopqrstuvwxyz`;
cut_down:=input;zorch:=``;
while(type(cut_down,positive)) do
	ss:=irem(cut_down,100);
	cut_down:=(cut_down-ss)/100;
	zorch:=cat(substring(alph,ss..ss),zorch)
	od;
RETURN(zorch);
end;

Below are some simple uses of this routine. Note the spurious answers for bad input -- I've definitely not written "bulletproof" computer code!

>N2A(260124);
                                 zax

>N2A(12624);

                                 azx

>N2A(37);



>N2A(237);

                                  b

>N2A(9);

                                  i

TOP

Preparing RSA keys

These routines were used to create the RSA exercises.

Here first is the divide-and-conquer method of exponentiation which I introduced in the RSA homework:

ES:=proc(base,power,modulus)
local A,B,C; 
A:=1; B:=power;C:=base; 
while type(B,positive) do 
	if type(B,odd) then A:=A*C mod modulus; B:=B-1; fi;
        B:=B/2; C:=C^2 mod modulus 
        od;
RETURN(A);
end;

Uses of ES are documented on the RSA web page.

The following routine has Maple compute primes P and Q, and a pair of encryption/decryption exponents e and d, given an integer n. P and Q will be n decimal places long.

RSA:=proc(n)
local P,Q,frog,T,R,S,toad,zebra;
P:=3;Q:=5;
while(type(2*n-length(P*Q),positive) and P<>Q) do
frog:=rand(10^(n-1)..10^n-1);
P:=nextprime(frog());
Q:=nextprime(frog())
od;
T:=(P-1)*(Q-1);
toad:=rand(10^iquo(2*n,4)..10^(3*iquo(2*n,4)));
R:=T;
while(igcd(T,R)>1) do
R:=toad();
zebra:=msolve(R*S=1,T)
od;assign(zebra);
RETURN(P,Q,P*Q,R,S);
end;

And here is a use of this routine:

>RSA(15);
  481321110693277, 397474256143567, 191312750439005747675813699059,

        305613921751630036805, 163151755562420097036265148189

The last two numbers are the encryption and decryption exponents.

This routine lets Maple prepare a sequence of public/private keys corresponding to one exponent. Please note that in reality the exponent must also change or else the cryptosystem itself can be broken easily. However, for the purposes of this course, I thought that varying the e and d pairs would be enough for students without also changing P and Q. It would not be difficult to amend what's given here to supply different P's and Q's as well if this is desired.
Please type readlib(unassign); before using the routine below.
```
keys:=proc(n,m,P,Q)
local R,S,T,count,toad,zebra;count:=m;
T:=(P-1)*(Q-1);
toad:=rand(10^iquo(2*n,4)..10^(3*iquo(2*n,4)));
while (type(count,positive)) do
	R:=T;
	while(igcd(T,R)>1) do
		R:=toad();
		zebra:=msolve(R*S=1,T)
		od;
	assign(zebra);
	print(R,S);unassign('S');
	count:=count-1
	od;
end;
```
Here's a use of keys. Maple verifies that two numbers are prime using the first two instructions.
```
>ifactor(311);
                                 (311)

>ifactor(503);

                                 (503)

>keys(4,3,311,503);

                             98333, 40177


                             693739, 9799


                             533593, 2297


                                 0
```
Three e/d pairs are found. The first parameter (4, above) asks that the first number be (uniformly) (pseudo-)randomly chosen between .5n and 1.5n digits long -- in this case, between 2 and 6 digits long. Of course, there isn't much chance that the number will be 2 or 3 digits long!

TOP

Some bitstream routines

Preparation of some assignments and work in class is made easier with a few simple routines manipulating bitstreams.

Here a bitstream is a string of 0's and 1's. The first routine "prettyprints" a bitstream in groups of 5:

fiver:=proc(tiger)
local m,empty,zorch,v,j;
zorch:=``;
m:=iquo(length(tiger),5,v); 
if type(v,positive) then m:=m+1 fi; 
empty:=` `; 
for j to m do 
	zorch:=cat(zorch,substring(tiger,(j-1)*5+1 .. j*5),empty)
	od; 
RETURN(zorch);
end;

Here is an example. Note that a string must be specified with ` at the beginning and the end.

>fiver(`010001111100`);
                           01000 11111 00

>fiver(000111111);
Error, (in fiver) string or symbol expected for substring

The following routine creates the xor of two bitstreams.

xor:=proc(frog,toad)
local m,zorch,j,zero,one,f,t;
m:=min(length(frog),length(toad));
zorch:=``;zero:=`0`;one:=`1`;
for j from 1 to m do
	f:=substring(frog,j .. j); t:=substring(toad,j .. j); 
	if f=t then zorch:=cat(zorch,zero) 
	else zorch:=cat(zorch,one) fi; 
	od; 
RETURN(zorch);
end;

Here is an example of how it can be used:

>xor(`01010101`,`111000`);
                                101101

Note that the output is a bitstream whose length is the minimum of the lengths of the two bitstreams to be xored.

Creation of a bitstream in an alien language means creation of a bitstream with correct relative frequencies of alien words. Here the connections between the words are ignored. For example, suppose we want to create a bitstream sentence in an alien language where 000000 appears 60% of the time and 11111 appears 40% of the time. We first write
```
>vocab:= [`000000`,3,`11111`,2];
                    vocab := [000000, 3, 11111, 2]
```
and then use the following:
```
lang:=proc(vocab,N)
local tt,k,v,total,rn,zorch,test,test_1,test_2;
v:=nops(vocab);
zorch:=``;
total:=sum('vocab[2*k]',k=1..iquo(v,2));
rn:=rand(1..total);
if v=2 then 
	while type(N-length(zorch),positive) do
	zorch:=cat(zorch,vocab[1]); 
	od
else
	test:=seq([vocab[2*test_1-1],sum('vocab[2*test_2]',test_2=1..test_1)],test_1=1..iquo(v,2)); 
	while type(N-length(zorch),positive) do
		tt:=rn();
		if  tt<=test[1][2] then zorch:=cat(zorch,test[1][1]) else v:=1;
			while type(tt-test[v][2],positive) do 
				v:=v+1 od;
			zorch:=cat(zorch,test[v][1]); fi;
		od;
	fi;
RETURN(zorch);
end;
```
We can demonstrate its use (twice!) as follows:
```
>lang(vocab,30);
                  000000111110000001111100000011111

>fiver(%);


               00000 01111 10000 00111 11000 00011 111

>lang(vocab,30);
                  0000001111100000000000000000011111

>fiver(%);


              00000 01111 10000 00000 00000 00001 1111
```
Since lang uses the Maple rand function, its output will likely be different each time it is invoked, even with the same parameters. Note that lang is requesting in each case a bitstream which is 30 bits long. The outputs (if A is 000000 and B is 11111) are the bitstreams corresponding to ABABAB and ABAAAB. There are 7 A's and 5 B's in total,so that A's are somewhat more common. But note that the length of the first output is 33 bits and the lenght of the second output is 34 bits. lang stops when the sequence of A's and B's it creates is at least 30 bits long. lang then prints the entire sequence of 0's and 1's implied by the letters.

TOP

Computing the GAG number

A handout in lecture 23 was designed to illustrate some of the pitfalls and benefits of authentication via hashing. A rather flawed algorithm produced the "GAG number" of a document. The routines below helped me compute the GAG number.

This routine counts vowels.

vowel:=proc(input)
local zorch, L, j_, ss;
zorch:=0;
L:=length(input);
for j_ from 1 to L do
	ss:=substring(input,L-j_+1..L-j_+1);
	if ss='a' then zorch:=zorch+1 elif
		ss='e' then zorch:=zorch+1 elif
		ss='i' then zorch:=zorch+1 elif
		ss='o' then zorch:=zorch+1 elif
		ss='u' then zorch:=zorch+1 fi;
	od;
RETURN(zorch);
end;

Its use is clear:

>vowel(frog);
                                  1

This routine counts spaces.

space:=proc(input)
local zorch, L, j_, ss;
zorch:=0;
L:=length(input);
for j_ from 1 to L do
	ss:=substring(input,L-j_+1..L-j_+1);
	if ss=` ` then zorch:=zorch+1 fi;
	od;
RETURN(zorch);
end;

Note that here a phrase must be delimited by `.

>space(`frog jumps`);
                                  1

>space(frog jumps);
missing operator or `;`

Here's the computation of the GAG number. I show these routines in the hope that others may use them and change them to suit their own purposes. It is interesting to contemplate ever more complex authentication algorithms and then to attempt to confound them, as in the homework assignment.

GAG:=proc(input)
local vo,sp,L,cons;
vo:=vowel(input);sp:=space(input);L:=length(input);
cons:=L-vo-sp;
RETURN(7*vo-3*cons+sp^2 mod 17);
end;

Here is a use of GAG taken from the hoemwork assignment:

>GAG(`We jointly and equally own the gravel pit at Loon Lake.`);
                                  16

>GAG(`Ted has one third interest in the Loon Lake gravel pit.`);

                                  16

TOP