# Public Key Codes
# 
# Let's see how a computer algebra system (Maple) can help us with our
# calculations. First let's see how it handles large numbers.
> 71^7;
> 124^103;
# OK, it seems to do just fine! How about remainders?
> 71^7 mod 143;
> 124^103 mod 143;
# Hey, that looks familiar!
# 
# Now, let's try the theory behind the RSA code with some larger primes.
# 
# First, let's make sure that you can repeat this worksheet and get the
# same values. Replace the "13" that appears in the randomize command
# with any positive integer you like.
> randomize(13);
# First, pick two larger primes.
> p := nextprime(round(rand()));
> q := nextprime(round(rand()));
> n := p*q;
> m := (p-1)*(q-1);
# Next we choose an integer e (the encoder) which has no factors in
# common with m. We check this by having Maple compute the greatest
# common divisor of e and m. Change the value of e so that the greatest
# common divisor is 1.
> e := 37;
> igcd(e,m);
# Now we must find the decoder d. We use a built-in command in Maple to
# help with this.
> igcdex(e,m,'d','y');
# Let's have a look at the value of d
> d;
# If it came out negative, we need to find an equivalent positive power
# mod m
> d := d mod m;
# Now, let's test the encoding and decoding with these values. Pick a
# large integer at random (but less than n).
> W := rand() mod n;
# Now encode it using e.
> C := Power(W,e) mod n;
# Then let's decode it using d.
> Power(C,d) mod n;
# You got W back, right!!
# 
# Use the code segments below to decode and encode messages.
# 
# 
# Use the following block to encode a message using another person's
# public keys e and n.
# First enter the values of e and n.
> enc := 41;
> nval := 244999;
# Now enter your message into the list called inmessage below using the
# table of values below.
# A B C  D E  F G  H  I  J   K  L  M  N  O  P  Q   R  S  T  U  V   W  X 
# Y   Z  space
# 2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23  24
# 25 26  27  28
# 
# (Why did we start with 2 and not 1?)
> inmessage := [14,2,21,9,28,10,20,28,7,22,15];
# Now encode - adjust the upper bound for "i" (the 11) to match the
# length of your message.
> for i from 1 to 11 do 
>    decoded[i] := Power(inmessage[i],enc) mod nval
> od;
# Give the message to your friend to decode.
# 
# 
# Decode. Get a message (encoded using your public keys e and n) from
# your friend in the form of a sequence of numbers. Put the numbers into
# the message list (replace the numbers shown with the actual message).
# Set the number of entries in the list as the upper bound for "i" in
# the "for" statement.
# 
> message := [1234, 2345, 3456, 4567, 5678];
> for i from 1 to 5 do 
>    decoded[i] := Power(message[i],d) mod n
> od;
> 
# Now the message can be decoded. Write it down and use the table above
# to help.
>