Using Mathematica to Implement RSA 
Questions to: rogness@math.umn.edu

Note: most of the "introduction to Mathematica" stuff here is taken from the introduction I wrote for Math 2374 at the University; see http://www.math.umn.edu/math2374.  In particular, I left in some things that we won't use (like the graphing commands) because I thought you might be interested.

Introduction to Mathematica - Arithmetic, Functions, and Graphs

Mathematica is a very powerful program.  If you own a graphing calculator, you may as well put it away.  Even a TI-89 or TI-92 is out of its league here.  Mathematica can do everything they can do, and then some.  And some more.  And then a lot more.  The purpose of this introduction is to get you comfortable with Mathematica.  We'll start with the easy stuff -- such as how to add two numbers -- and move on to more complicated things.  Then we'll move on to the commands which will let you implement the RSA algorithm.

Arithmetic and Variables

The basic unit of a Mathematica notebook is a cell.  You're currently reading a text cell, which we can use to document what we're doing, but the real work is done in "input" cells.  To run a command (or "evaluate a cell") you have to use the keyboard or the mouse to position the cursor anywhere in the input line and hit either (1) Shift+Enter, where "Enter" is the normal Enter key, or (2) the Enter key on the numeric keypad.  If you use option (2), you do not have to press the shift key. 

Practice by evaluating these cells:

2 + 2

35/7

From now on, whenever you run across a command as you read, you can assume it's meant as an example for you.  You should evaluate it, even if you're not specifically told to do so.

Mathematica uses the normal operators +, -, /, and * for arithmetic operations, and ^ for exponents.

3*3
3 ^2

As you can see, you can put multiple commands in a single input cell by hitting Enter (without the shift key!) and putting a new command on the next line.  Mathematica will return the output in the same order.  If you want to suppress the output of a command, put a semicolon after it.  (If you use a semicolon, you can put the next command on the same line, so the third line of input here is valid:)

9/3;
6^2

12*12;  5 + 1;  3/2

Mathematica does most of its work symbolically, which is why the last output was a fraction instead of the decimal 1.5.  Special constants like π and e (the symbol for e) are treated as such; Mathematica does not replace π with a number such as 3.14159.  You can enter these constants like this:

Pi
E

You can use variables and assign values to them.  For reasons that will be clear later, you should only use lower case letters in your variable names.

a = 2;  b = 3; 
a
b
a + b

If you want to multiply variables be very careful to remember the * in between them.

a*b

Evaluate this next cell to see what happens if you forget the *.

ab

Mathematica returns "ab" because there is nothing between the letters in the input cell, so it doesn't know you're trying to multiply to different variables together.  Instead, it assumes you're asking for the value of a new variable named "ab."  You haven't given "ab" a value yet, so Mathematica just returns the variable itself.

If you're done using variables you can erase them from memory using the Clear[ ] command.  This is sometimes useful before you use variables, as well; you can clear them just in case they were used for something else before

Clear[a, b]

Functions

In order to do anything really interesting, we need to use functions.  Functions which are part of Mathematica are always capitalized, and always use square brackets, [ and ], around their arguments.  For example, here's the square root function:

Sqrt[5]

Remember, Mathematica does things symbolically unless we tell it otherwise, so it returns (Sqrt[5]) instead of 2.23607.  If you want to see a decimal approximation of a number, use the function N:

N[Sqrt[5]]

If you get an answer to a problem and want a numeric value for it, you don't have to type the answer again.  You can use the symbol  %, which refers back to the most recent output:

Sqrt[10]

N[%]

The other way to force Mathematica to give you a decimal answer is to start out with a decimal number, i.e. "5.0" instead of "5" — in fact, you can simply type "5." as shown here:

Sqrt[5. ]

You could probably guess the names of some other common functions, such as Sin, Cos, Tan, Log, and Exp.  (For people who haven't taken computer science classes, Exp[number] is a common notation for (e^number).)  To see if you understand how to use functions, you should try to evaluate sine and cosine at 0, π/2, and π in another notebook window.

Warning!  You must remember that Mathematica functions are capitalized and use square brackets.  Also remember that you must capitalize Pi if you want the number π.  For example, all of these commands are incorrect:

Sin(0)
cos[0]
Tan[pi]
sin(pi)

The last one is really bad; there are three mistakes!  (See if you can find them.)

Forgetting to capitalize functions like Sin and Cos, and using ( ) instead of [ ], are by far the most common mistakes students make well into the semester.  During the first few weeks of the course, it's very common for people to call us to their computer and say, "This isn't working," and the problem is that they typed sin instead of Sin, or Sin(Pi) instead of Sin[Pi], etc.  

If you have a problem with the computer, you should always feel free to ask us for help.  Especially during these first few weeks, however, you will usually save yourself (and us) some time by carefully double-checking your brackets and capitalization; that's very likely the problem.  We realize it takes a while to get use to how syntax-sensitive Mathematica is, but never fear—in a few weeks you will get used to the syntax and everything will go much smoother.

Some Mathematica functions can actually grind out algebra problems for you.  For example, suppose you're trying to find the intersection of the parabola y=(((x - 1))^2)+2 with the line y = x + 5.  You could set these two equations equal and solve for x, or you can have Mathematica do it for you:  (Note that we have replaced = with ==.  You must do this or Solve won't work.)

Solve[(x - 1)^2  + 2  ==  x + 5,  x]

Another useful function is Simplify, which can take ugly expressions and make them much nicer.

6  x (x + 2)/Sqrt[2]  + (6 +  Pi)/Sqrt[2] - 
      Sqrt[2]* Pi/2

Simplify[%]

Simplify[Cos[x]^2  +  Sin[x]^2]

Help Browser

There is one very important resource for you, called the Help Browser.  You can find it under the Help menu above.  If you want to know how to do something you should check there first.  Sometimes the help files are a little hard to understand, especially if you don't have much experience with Mathematica, so you can always ask your TA for help.  However, if you haven't looked it up, you should be prepared for us to answer with, "Check the help browser and let me know if it doesn't make sense."

As a test, open the help browser and see if you can figure out how to get Mathematica to find |x|, the absolute value of x.  (Suggestion: search for "absolute value.")  Check your work by computing the absolute values of 3 and -3.

Here's a tip: many pages in the help browser include examples, which can be very instructive.  To see these example you have to click on the little triangle next to the words "Further Examples."

Defining your Own Functions

Very often we'll want to work with our own functions, such as f(x) = (x^2).  We can do this by using the following input:

f[x_] = x^2

Note the underscore after the x on the left hand side.  You must include the underscore after the x on the left hand side inside the bracket, but you should never include it on the right hand side!  You don't really need to know the reason for this, but roughly speaking, the underscore tells Mathematica that the thing inside the brackets is a variable that can take on any value.

Forgetting the underscore is another very common problem during the first month of the class.  If you're having a problem with a function that you defined on your own, double check that you've used the underscore correctly.  If you left out the underscore, you'll probably have to clear the variable name (as in Clear[x]) before redefining the function.

You can choose your own favorite name for a function when you define it, but you should only use lowercase letters.  The reason for this, and for why we recommend you only use lowercase variables, is that all of the internal Mathematica functions are capitalized.  If you only use lowercase functions, you don't have to worry about a conflict with something that is already defined.

Once we've defined a function, we can do all sorts of cool things with it.  You can input numbers or symbols -- or even whole expressions -- into a function:

f[4]
f[Pi]
f[(1 + t)]
f[Sin[t*Pi]]

Functions can have more than one argument.  Also note that when you define a function, Mathematica returns the definition as output unless you use a semicolon after it:

g[u_, v_] = u/v;
g[2, 3]
g[5  Pi, (x - 9)^6]

Example

It's not imperative that you do this problem, but if you have the time it would probably be very helpful.  Recall that if you want to solve the equation (ax^2) + bx  +  c  =  0, you can use the quadratic formula, which says 

x = ((-b ± (Sqrt[(b^2) - 4  ac]))/(2  a)).  

Define a function f[a_,b_,c_] which returns one root, and another function g[a_,b_,c_] which returns the other root.  (There are two roots because of the ± sign.)  To see if you've done everything correctly, try to find the two roots of 2  (x^2) + 8  x - 1 = 0.  (The numeric approximations of the roots, found using the Mathematica function N[ ], are -4.12132 and 0.12132.)

Drawing Graphs

There are many commands you can use to produce pictures in Mathematica.  Today we're going to learn two of them.

If we have a function y=f(x), the easiest way to graph it is with the Plot command.  The syntax is Plot[ function, {x, xmin, xmax}].  Note that expressions such as {x, xmin, xmax} will be very common this semester.  Basically it means you want to let x range from xmin to xmax.

f[x_] = x^2;
Plot[f[x], {x, -1, 3}]

You don't have to name a function before you can graph it.  You can simply enter the function into the Plot command.

Plot[x *Sin[1/x], {x, -0.3, 0.3}]

You can name plots so you can refer to them later as well:

plot1 = Plot[Sin[x], {x, 0, 2  Pi}]
plot2 = Plot[Cos[x], {x, 0, 2  Pi}]

If you've named a graph and you want to display it again later, you can use the Show command.  You can give the command the names of multiple plots, and it will show them together:

Show[plot1, plot2]

Options

Occasionally you will want to use optional arguments when drawing graphs. Options generally come at the end of a command and have the form "OptionName→Setting."  [You can type the → as (hyphen)(greater than), –≻].  For example, the option Axes→False will prevent Mathematica from showing the x- and y- axes in a graph.  This option works with Plot and Show.  Try adding it to the Show command above and re-evaluating it.  (You need to add a comma after "plot2" before you can add the option.)  Did the axes disappear?

Saving Notebooks

Once you're finished working, you'll usually want to save your notebook so you don't lose your work.  You can do this through the File menu with either "Save" or "Save As."  Please note:  output, and particularly graphics output, takes up a tremendous amount of disk space and, if you save notebooks with graphics, they will quickly get to be so large that you will use up your disk quota and be barred from using the computer.  This is especially true in later labs, where we will create animations.  If you save a notebook with an animation, it will take up several megabytes of disk space.

So, before you save a notebook, you should always go to the Kernel menu and choose "Delete All output."  This will leave all of your commands intact, but delete all of the answers and graphics from Mathematica.  If you load a notebook that was saved after deleting all output, you can run all of the commands automatically by going to the Kernel menu again and choosing Evaluation : Evaluate Notebook.

Implementing the RSA Algorithm

In order to implement the RSA algorithm, we need to know about how to store messages as numbers, as well as modular arithmetic.

Basic Modular Arithmetic and Number Theory in Mathematica

To compute x mod n you use the Mod[x, n] command, as in:

Mod[30, 26]

We've learned to find greatest common divisors (and multiplicative inverses mod n) using the Euclidean Algorithm.  In Mathematica we don't have to go through all those steps.  For example, to find the greatest common divisor of 45 and 81, type:

GCD[45, 81]

Here's a massively useful function: PowerMod[x,p,n].  This computes (x^p) mod n.  Both the encryption and decryption steps in RSA involve this kind of calculation.  Another useful thing about this function is that you can use p = -1 to compute multiplicative inverses.

PowerMod[3, -1, 4060]

We can check this answer:

Mod[3*2707, 4060]

Also note that Mathematica will tell you if you inadvertantly ask for an inverse which doesn't exist:

PowerMod[13, -1, 26]

One other function we need to use is the Euler Phi Function, ϕ(n).  It's computed as follows (here n=88):

EulerPhi[88]

Dealing with Text in Mathematica

In Mathematica, strings of characters are enclosed with double quotes:

plaintext = "Hello World"

To implement RSA we need to convert out characters to numbers.  Mathematica has a method for doing this called ToCharacterCode[]:

ToCharacterCode[plaintext]

Notice that Mathematica returns a list of numbers.  Each character has been converted to a number according to Mathematica's own internal method, which will work just fine for our purposes.  (So, for example, "H" is 72, "e" is 101, "l" is 108, and so on.)

Given a list of numbers, we can can convert it back to text using FromCharacterCode[]:

FromCharacterCode[{73, 116, 32, 119, 111, 114, 107, 101, 100, 
        33}]

Implementing RSA

To implement RSA we need to find two prime numbers.  Normally they'd be very large, but we'll use small ones to keep things manageable here.  Mathematica includes a function Prime[k] which returns the (k^th)prime number.   Let's take the nineteenth and twenty-first and primes for our example.

p = Prime[19]
q = Prime[20]
n = p*q

We can trying to use the exponent 3 as our public encryption key.  Then we need to find our private decryption key, which is the multiplicative inverse of e mod ϕ(n).

e = 3
d = PowerMod[e, -1, EulerPhi[n]]

EulerPhi[n]

Uh-oh!  It turns out that ϕ(n) = 4620, which is divisible by 3, so 3 doesn't have a multiplicative inverse in this case.  We experiment with other small numbers and find that e = 13would work for our public key:

e = 13
d = PowerMod[e, -1, EulerPhi[n]]

Now let's create the list of numbers we want to encrypt:

plaintext = ToCharacterCode["This is my message."]

A useful feature of lists in Mathematica is that an operation will be performed separately on each member of the list.  For example:

{1, 2, 3, 4, 5, 6} + 3
{1, 2, 3, 4, 5, 6}^2

Therefore, to raise each of our "plaintext number" to the (e^th)power, we just raise the whole list the the (e^th)power, and then reduce mod n.  You can use either of the following commands:

ciphertext = Mod[plaintext^e, n]
ciphertext = PowerMod[plaintext, e, n]

Now let's double check that the decryption process works as advertised:

decrypted = PowerMod[ciphertext, d, n]

FromCharacterCode[decrypted]

Woohoo!  Now work on the following problems, and hand in a page or two with your answers and explanations of your work.  (I can help you find applications to write your answers, and with printing them off.)

Exercise 1

Use the Prime[k] function with k-values inbetween 500 and 1000 to generate an RSA key (n, e, d).   Make sure your choices for e and d are valid!  Use your private key d to encrypt the word "math" and send me the resulting list of encrypted numbers along with the public part of the key, (n, e).  This is a form of message authentication; I should be able to use e and n to decrypt your numbers and verify that the result is the word "math."

Exercise 2

You are working for the government, trying to crack an ultra-secret sent by a foreign embassy.  It was encoded using Mathematica and RSA in the same method we've used here.  Unfortunately for the foreign government, they've used numbers which are far too small to ensure security.  The public part of their key is

		(n, e) = (3574406403731, 65537)

The message you've intercepted is

{3145498042951,399536786549,2151517025468,2162527373498,1358752710204,\
1692699813511,1574798950684,770507905045,399536786549,1358752710204,\
2722160106600,1574798950684,2131168730337,299208071831,399536786549,\
2722160106600,1358752710204,1814962457452,2899472317519,1814962457452,\
399536786549,770507905045,3520273614506,1358752710204,2225716991430,\
399536786549,2270936083495,770507905045,399536786549,1358752710204,\
2899472317519,299208071831,299208071831,1358752710204,1574798950684,\
744774205513,2722160106600,550046915935}

Find the decryption key d and decrypt the message

Exercise 3

Try to use Mathematica to generate an RSA key (n, e, d)that I can't break.  Give me the public part of the key, namely n and e.