Maple worksheet for experimenting with the RSA cryptosystemHow to Perform Basic TasksMaple is a computer algebra system (CAS).A CAS is a computer system for the exact solution of problems in symbolic form. This is in contrast to the numerical analysis approach to solving problems as used in FORTRAN or BASIC, where you will get a numerical approximation .The following is a simple, short reference page covers the most basic system knowledge required to use Maple for experimenting with the RSA cryptosystem. To expand the examples sections, please click the + box. When Using Maple, Remember...Ending Maple CommandsCommands must end in semicolons (to display results) or colon (to suppress display of result)ENTER vs. SHIFT+ENTER Press ENTER to send the command to Maple; press SHIFT+ENTER to continue the command on the next lineCase SensitivityMaple is case sensitive: Diff and diff are different commandsConverting Symbolic to Numeric To convert a fraction to a decimal approximation, use evalf() (e.g. evalf(2/3)). Getting Help To access the help system, type ?topic or start the Help Navigator from the Help menu.Common Commands and Syntax

n := 5; # assignment statementf := x->x^2; # function definition mod # computation over the integers modulo mPower(x,e) mod n # binary exponentiation modulo n

n := 5;f := x->x^2;12 mod 7;power(123456789123456781234567,987654321987654321987654321 )mod 122333444455555;

random(r) # random number generator- [r-(optional) integer range or integer]ifactor(n); # Integer factorizationisprime(n); # primality testnextprime(n); # determine the next prime numberigcd(a,b,...) # greatest common divisor of integersilcm(a,b,...) # least common multiple of integersmod # computation over the integers modulo m1/a mod n # inverse of 'a' modulo nconvert/bytes # convert between strings and lists of integersconvert(n, base, beta) # convert/base converts the base 10 number n to base beta. convert(k, base, alpha, beta) # convert the list of digits k in base alpha to base beta

rand();ifactor(2^11-1);isprime(224737);n:=rand(10^9..10^10-1)(); nextprime(n)igcd(1234,56);ilcm( -10, 6, -8 );5^123 mod 7;1/3 mod 7;convert(`It is just for Test`,'bytes');convert([65,66,67],'bytes');convert(17,base,3);convert([2,2,1],base,3,10);

phi(n) # Euler's Totient Functiondivisors(n) # the set of positive divisorstau(n) # number of divisors

with(numtheory): phi(15);with(numtheory): divisors((2)^8*(3)^5*(5)^2);with(numtheory): tau((2)^8*(3)^5*(5)^2);

Suppose Bob wants to send a secret message to Alice using the RSA system. Here's what Alice does. [The communication can take place via email, for example.]We illustrate the RSA system using two randomly chosen primes with 100 decimal digits. Note that 10^(n-1) is the smallest n decimal digit integer and 10^n-1 is the largest. For example if n = 3, we obtain the smallest and largest 3 digit integers:smallest and largest 3 digit integersWe first generate two 100 digit random positive integers and then use the Maple command nextprime to obtain the smallest primes greater than each number. Notice that in rand we use the range 10^99..10^100-1.

N:=rand(10^99..10^100 -1)(); M:=rand(10^99..10^100 -1)();

Now we use the command nextprime. The command nextprime(n) finds the smallest prime greater than n.

p:=nextprime(N); q:=nextprime(M);Now we multiply these together to form our modulus n:n:=p*q;

Now we compute phi(n) which is possible since we know that n = p*q where p and q are primes. We simply use the formula phi(n) = (p-1)*(q-1). [Note that the comment phi(n) also works ,however this takes a while because Maple has to factor n first]. We denote it by the variable phi.

phi:=(p-1)*(q-1);

Now we wish to find a number e such that gcd(e, phi(n)) = 1. We keep trying random 100 digit integers till we find one that works.

for i from 1 do e:=rand(10^99..10^100-1)(); if gcd(e,phi) = 1 then break; fi; od: e;

The inverse of e modulo phi is an integer d such that e*d mod phi = 1. From number theory it is known that an integer 'e' has an inverse mod phi if and only if gcd(e,phi) = 1. The following command will compute the inverse of 'e' modulo phi:

d:=1/e mod phi;

We check that e*d mod phi(n) = 1.e*d mod phi;

In cryptography, plain text refers to any message that is not enciphered. After encryption it is called cipher text. We assign Bob's message to the variable named plain_text, as follows. (Of course, the name of the variable is not important.)

plain_text:="It is the act of learning";

We now convert this text to a list of numbers:List1:=convert(plain_text,bytes);

We consider List1 as the base 256 representation of a number. We convert this to a base 'n=p.q' number as follows:List2:=convert(List1,base,256,n);

Now we apply the mapping which sends M to Power(M,e) mod n to each number in List2. This can be done using map. We thus obtain the enciphered message that will be sent to Alice. cipher_text:=map(M->Power(M,e) mod n, List2);

Now Bob sends this to Alice . But since only Alice has the secret private key, only she will be able to decipher the message. We show now how she deciphers the message: She applies the mapping which sends C to Power(C,d) mod n where d is her private key to each received number:

decipher1:=map(C->Power(C,d) mod n,cipher_text);

Next she converts this to base 256:decipher2:=convert(decipher1,base,n,256);Finally she converts the numbers back to text and sees what message Bob sent her:decipher3:=convert(decipher2,bytes);

You are the sender. You will be sending the word \342\200\230DATELINE = 0401200512091405\342\200\231 to the receiver who has chosen a modulus n = 2905554057268138607 and e = 61223183. Find the message to send.restart; with(numtheory): M:=0401200512091405;n:=2905554057268138607;factor n or compute phi(n)ifactor(n);r:=phi(n);NiMqKkklRmluZEc2IiIiIkkkdGhlR0YlRiZJJ2NpcGhlckdGJUYmSSV0ZXh0R0YlRiY= e:=61223183; C:=Power(M,e) mod n;Invert e mod phi(n) to get the deciphering exponent dd:=1/e mod r;check that e*d mod phi(n) = 1.e*d mod r;Check to see if it worksOriginal_message:=Power(C,d) mod n;

You are the receiver, let n = 1813739439517193 = 29384712 \267 61723849 and e = 187247 and d = 251089477478663. A sender sent you the message, 298772360895187. Determine what message is being sent to you.restart; with(numtheory): n:=1813739439517193;

You are the opponent. You intercept the message 8832330981561936231837859 and you know that it was sent with the public modulus n = 34379516879486104880897911 and encrypting exponent e = 2343490992813. Determine the message.restart; with(numtheory):