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
<Text-field layout="_pstyle129" style="_cstyle106">Defining Variables, Functions and Procedures</Text-field>n := 5; # assignment statementf := x->x^2; # function definition mod # computation over the integers modulo mPower(x,e) mod n # binary exponentiation modulo n
<Text-field layout="_pstyle132" style="_cstyle109">Examples</Text-field>n := 5;f := x->x^2;12 mod 7;power(123456789123456781234567,987654321987654321987654321 )mod 122333444455555;
<Text-field layout="_pstyle129" style="_cstyle106">Expression Manipulation</Text-field>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
<Text-field layout="_pstyle132" style="_cstyle109">Examples</Text-field>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);
<Text-field layout="_pstyle129" style="_cstyle106">Constants</Text-field>phi(n) # Euler's Totient Functiondivisors(n) # the set of positive divisorstau(n) # number of divisors
<Text-field layout="_pstyle132" style="_cstyle109">Examples</Text-field>with(numtheory): phi(15);with(numtheory): divisors((2)^8*(3)^5*(5)^2);with(numtheory): tau((2)^8*(3)^5*(5)^2);
<Text-field layout="_pstyle129" style="_cstyle106"><Font foreground="[255,51,51]" size="18">An Example of RSA Cryptosystem</Font></Text-field>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.
<Text-field layout="Heading 2" style="Heading 2"><Font size="18">Generate two 100 digit random positive integers</Font></Text-field>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.
<Text-field layout="Heading 2" style="Heading 2"><Font size="18">Use command nextprime</Font></Text-field>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.
<Text-field layout="Heading 2" style="Heading 2"><Font size="18">Compute Phi(n)</Font></Text-field>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.
<Text-field layout="Heading 2" style="Heading 2"><Font size="18">Finding e</Font></Text-field>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:
<Text-field layout="Heading 2" style="Heading 2"><Font size="18">Finding d</Font></Text-field>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.)
<Text-field layout="Heading 2" style="Heading 2"><Font size="18">Encryption</Font></Text-field>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:
<Text-field layout="Heading 2" style="Heading 2"><Font size="18">Decryption</Font></Text-field>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);