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.