(************** Content-type: application/mathematica ************** CreatedBy='Mathematica 5.0' Mathematica-Compatible Notebook This notebook can be used with any Mathematica-compatible application, such as Mathematica, MathReader or Publicon. The data for the notebook starts with the line containing stars above. To get the notebook into a Mathematica-compatible application, do one of the following: * Save the data starting with the line of stars above into a file with a name ending in .nb, then open the file inside the application; * Copy the data starting with the line of stars above to the clipboard, then use the Paste menu command inside the application. Data for notebooks contains only printable 7-bit ASCII and can be sent directly in email or through ftp in text mode. Newlines can be CR, LF or CRLF (Unix, Macintosh or MS-DOS style). NOTE: If you modify the data for this notebook not in a Mathematica- compatible application, you must delete the line below containing the word CacheID, otherwise Mathematica-compatible applications may try to use invalid cache data. For more information on notebooks and Mathematica-compatible applications, contact Wolfram Research: web: http://www.wolfram.com email: info@wolfram.com phone: +1-217-398-0700 (U.S.) Notebook reader applications are available free of charge from Wolfram Research. *******************************************************************) (*CacheID: 232*) (*NotebookFileLineBreakTest NotebookFileLineBreakTest*) (*NotebookOptionsPosition[ 31259, 1012]*) (*NotebookOutlinePosition[ 31923, 1035]*) (* CellTagsIndexPosition[ 31879, 1031]*) (*WindowFrame->Normal*) Notebook[{ Cell[TextData[{ StyleBox["Using ", FontSize->18, FontWeight->"Bold", FontVariations->{"Underline"->True}], StyleBox["Mathematica", FontSize->18, FontWeight->"Bold", FontSlant->"Italic", FontVariations->{"Underline"->True}], StyleBox[" ", FontSize->18, FontWeight->"Bold", FontSlant->"Italic", FontVariations->{"Underline"->True}], StyleBox["to Implement RSA", FontSize->18, FontWeight->"Bold", FontVariations->{"Underline"->True}], StyleBox[" ", FontSize->18, FontWeight->"Bold", FontSlant->"Italic", FontVariations->{"Underline"->True}], "\nQuestions to: rogness@math.umn.edu" }], "Text", CellFrame->True, TextAlignment->Center, FontColor->GrayLevel[1], Background->RGBColor[0, 0, 1]], Cell[TextData[{ "Note: most of the \"introduction to ", StyleBox["Mathematica", FontSlant->"Italic"], "\" 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." }], "Text"], Cell[CellGroupData[{ Cell[TextData[{ "Introduction to ", StyleBox["Mathematica", FontSlant->"Italic"], " - Arithmetic, Functions, and Graphs" }], "Section"], Cell[TextData[{ StyleBox["Mathematica", FontSlant->"Italic"], " 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. ", StyleBox["Mathematica", FontSlant->"Italic"], " 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 ", StyleBox["Mathematica", FontSlant->"Italic"], ". 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." }], "Text"], Cell[CellGroupData[{ Cell["Arithmetic and Variables", "Subsection"], Cell[TextData[{ "The basic unit of a ", StyleBox["Mathematica", FontSlant->"Italic"], " notebook is a ", StyleBox["cell", FontSlant->"Italic"], ". 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 ", StyleBox["not", FontSlant->"Italic"], " have to press the shift key. \n\nPractice by evaluating these cells:" }], "Text"], Cell[BoxData[ \(2 + 2\)], "Input"], Cell[BoxData[ \(35/7\)], "Input"], Cell[TextData[{ "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.\n", "\n", StyleBox["Mathematica", FontSlant->"Italic"], " uses the normal operators +, -, /, and * for arithmetic operations, and ^ \ for exponents." }], "Text"], Cell[BoxData[{ \(3*3\), "\[IndentingNewLine]", \(3\ ^2\)}], "Input"], Cell[TextData[{ "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. ", StyleBox["Mathematica", FontSlant->"Italic"], " 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:)" }], "Text"], Cell[BoxData[{ \(\(9/3;\)\), "\[IndentingNewLine]", \(6^2\)}], "Input"], Cell[BoxData[ \(12*12; \ 5 + 1; \ 3/2\)], "Input"], Cell[TextData[{ StyleBox["Mathematica", FontSlant->"Italic"], " does most of its work symbolically, which is why the last output was a \ fraction instead of the decimal 1.5. Special constants like \[Pi] and \ \[ExponentialE] (the symbol for ", StyleBox["e", FontSlant->"Italic"], ") are treated as such; ", StyleBox["Mathematica", FontSlant->"Italic"], " does not replace \[Pi] with a number such as 3.14159. You can enter \ these constants like this:" }], "Text"], Cell[BoxData[{ \(Pi\), "\[IndentingNewLine]", \(E\)}], "Input"], Cell["\<\ 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.\ \>", "Text"], Cell[BoxData[{ \(a = 2; \ b = 3;\ \), "\[IndentingNewLine]", \(a\), "\[IndentingNewLine]", \(b\), "\[IndentingNewLine]", \(a + b\)}], "Input"], Cell["\<\ If you want to multiply variables be very careful to remember the * \ in between them.\ \>", "Text"], Cell[BoxData[ \(a*b\)], "Input"], Cell["\<\ Evaluate this next cell to see what happens if you forget the \ *.\ \>", "Text"], Cell[BoxData[ \(ab\)], "Input"], Cell[TextData[{ "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.\n\nIf you're done using variables you can \ erase them from memory using the ", StyleBox["Clear[ ]", FontWeight->"Bold"], " 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" }], "Text"], Cell[BoxData[ \(Clear[a, b]\)], "Input"] }, Open ]], Cell[CellGroupData[{ Cell["Functions", "Subsection"], Cell[TextData[{ "In order to do anything really interesting, we need to use functions. \ Functions which are part of ", StyleBox["Mathematica", FontSlant->"Italic"], " are always capitalized, and always use square brackets, [ and ], around \ their arguments. For example, here's the square root function:" }], "Text"], Cell[BoxData[ \(Sqrt[5]\)], "Input"], Cell[TextData[{ "Remember, ", StyleBox["Mathematica", FontSlant->"Italic"], " does things symbolically unless we tell it otherwise, so it returns ", Cell[BoxData[ \(TraditionalForm\`\@5\)]], " instead of 2.23607. If you want to see a decimal approximation of a \ number, use the function ", StyleBox["N", FontWeight->"Bold"], ":" }], "Text"], Cell[BoxData[ \(N[Sqrt[5]]\)], "Input"], Cell["\<\ 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:\ \>", "Text"], Cell[BoxData[ \(Sqrt[10]\)], "Input"], Cell[BoxData[ \(N[%]\)], "Input"], Cell[TextData[{ "The other way to force ", StyleBox["Mathematica", FontSlant->"Italic"], " to give you a decimal answer is to start out with a decimal number, i.e. \ \"5.0\" instead of \"5\" \[LongDash] in fact, you can simply type \"5.\" as \ shown here:" }], "Text"], Cell[BoxData[ \(Sqrt[5. ]\)], "Input"], Cell[TextData[{ "You could probably guess the names of some other common functions, such as \ ", StyleBox["Sin", FontWeight->"Bold"], ", ", StyleBox["Cos", FontWeight->"Bold"], ", ", StyleBox["Tan", FontWeight->"Bold"], ", ", StyleBox["Log", FontWeight->"Bold"], ", and ", StyleBox["Exp", FontWeight->"Bold"], ". (For people who haven't taken computer science classes, Exp[number] is \ a common notation for ", Cell[BoxData[ \(TraditionalForm\`e\^number\)]], ".) To see if you understand how to use functions, you should try to \ evaluate sine and cosine at 0, \[Pi]/2, and \[Pi] in another notebook \ window." }], "Text"], Cell[TextData[{ StyleBox["Warning!", FontSize->14, FontWeight->"Bold"], " You must remember that ", StyleBox["Mathematica", FontSlant->"Italic"], " functions are capitalized and use ", StyleBox["square", FontWeight->"Bold"], " brackets. Also remember that you ", StyleBox["must", FontWeight->"Bold"], " capitalize Pi if you want the number \[Pi]. For example, all of these \ commands are incorrect:\n\n", StyleBox["Sin(0)\ncos[0]\nTan[pi]\nsin(pi)", FontFamily->"Courier", FontWeight->"Bold"], StyleBox["\n", FontFamily->"Courier"], "\nThe last one is really bad; there are ", StyleBox["three", FontSlant->"Italic"], " mistakes! (See if you can find them.)\n\nForgetting to capitalize \ functions like ", StyleBox["Sin", FontWeight->"Bold"], " and ", StyleBox["Cos,", FontWeight->"Bold"], " and using ( ) instead of [ ], are ", StyleBox["by far", FontSlant->"Italic"], " 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 ", StyleBox["sin", FontWeight->"Bold"], " instead of ", StyleBox["Sin", FontWeight->"Bold"], ", or ", StyleBox["Sin(Pi)", FontWeight->"Bold"], " instead of ", StyleBox["Sin[Pi],", FontWeight->"Bold"], " etc. \n\nIf 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 ", StyleBox["Mathematica", FontSlant->"Italic"], " is, but never fear\[LongDash]in a few weeks you will get used to the \ syntax and everything will go much smoother." }], "Text", CellFrame->True, Background->GrayLevel[0.849989]], Cell[TextData[{ "Some ", StyleBox["Mathematica", FontSlant->"Italic"], " functions can actually grind out algebra problems for you. For example, \ suppose you're trying to find the intersection of the parabola y=", Cell[BoxData[ \(TraditionalForm\`\((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 ", StyleBox["Mathematica", FontSlant->"Italic"], " do it for you: (Note that we have replaced = with ==. You must do this \ or ", StyleBox["Solve", FontWeight->"Bold"], " won't work.)" }], "Text"], Cell[BoxData[ \(Solve[\((x - 1)\)^2\ + 2\ \[Equal] \ x + 5, \ x]\)], "Input"], Cell[TextData[{ "Another useful function is ", StyleBox["Simplify", FontWeight->"Bold"], ", which can take ugly expressions and make them much nicer." }], "Text"], Cell[BoxData[ \(6 x \((x + 2)\)/Sqrt[2]\ + \((6 + \ Pi)\)/Sqrt[2] - Sqrt[2]*\ Pi/2\)], "Input"], Cell[BoxData[ \(Simplify[%]\)], "Input"], Cell[BoxData[ \(Simplify[Cos[x]^2\ + \ Sin[x]^2]\)], "Input"] }, Open ]], Cell[CellGroupData[{ Cell["Help Browser", "Subsection"], Cell[TextData[{ "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 \ ", StyleBox["Mathematica", FontSlant->"Italic"], ", 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.\"\n\nAs a test, open the help \ browser and see if you can figure out how to get ", StyleBox["Mathematica ", FontSlant->"Italic"], "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.\n\n\ 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.\"" }], "Text"] }, Open ]], Cell[CellGroupData[{ Cell["Defining your Own Functions", "Subsection"], Cell[TextData[{ "Very often we'll want to work with our own functions, such as ", Cell[BoxData[ \(TraditionalForm\`f(x) = x\^2\)]], ". We can do this by using the following input:" }], "Text"], Cell[BoxData[ \(f[x_] = x^2\)], "Input"], Cell[TextData[{ "Note the underscore after the x on the left hand side. You ", StyleBox["must", FontSlant->"Italic"], " include the underscore after the x on the left hand side inside the \ bracket, but you should ", StyleBox["never", FontSlant->"Italic"], " include it on the right hand side! You don't really need to know the \ reason for this, but roughly speaking, the underscore tells ", StyleBox["Mathematica", FontSlant->"Italic"], " that the thing inside the brackets is a variable that can take on any \ value." }], "Text"], Cell[TextData[{ "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 ", StyleBox["Clear[x]", FontWeight->"Bold"], ") before redefining the function." }], "Text", CellFrame->True, Background->GrayLevel[0.849989]], Cell[TextData[{ "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 ", StyleBox["Mathematica", FontSlant->"Italic"], " functions are capitalized. If you only use lowercase functions, you \ don't have to worry about a conflict with something that is already defined.\n\ \nOnce 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:" }], "Text"], Cell[BoxData[{ \(f[4]\), "\[IndentingNewLine]", \(f[Pi]\), "\[IndentingNewLine]", \(f[\((1 + t)\)]\), "\[IndentingNewLine]", \(f[Sin[t*Pi]]\)}], "Input"], Cell[TextData[{ "Functions can have more than one argument. Also note that when you define \ a function, ", StyleBox["Mathematica", FontSlant->"Italic"], " returns the definition as output unless you use a semicolon after it:" }], "Text"], Cell[BoxData[{ \(\(g[u_, v_] = u/v;\)\), "\[IndentingNewLine]", \(g[2, 3]\), "\[IndentingNewLine]", \(g[5 Pi, \((x - 9)\)^6]\)}], "Input"], Cell[CellGroupData[{ Cell["Example", "Subsubsection"], Cell[TextData[{ "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 ", Cell[BoxData[ \(TraditionalForm\`ax\^2 + bx\ + \ c\ = \ 0\)]], ", you can use the quadratic formula, which says \n\n", StyleBox["x = ", FontSize->14], Cell[BoxData[ FormBox[ StyleBox[ FractionBox[ RowBox[{\(-b\), " ", "\[PlusMinus]", " ", FormBox[ SqrtBox[ FormBox[\(b\^2 - 4 ac\), "TraditionalForm"]], "TraditionalForm"]}], \(2 a\)], FontSize->18], TraditionalForm]]], ". \n\nDefine 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 \[PlusMinus] sign.) To see if you've done everything \ correctly, try to find the two roots of ", Cell[BoxData[ \(TraditionalForm\`2 x\^2 + 8 x - 1 = 0\)]], ". (The numeric approximations of the roots, found using the ", StyleBox["Mathematica", FontSlant->"Italic"], " function ", StyleBox["N[ ]", FontWeight->"Bold"], ", are -4.12132 and 0.12132.)" }], "Text"] }, Open ]] }, Open ]], Cell[CellGroupData[{ Cell["Drawing Graphs", "Subsection"], Cell[TextData[{ "There are ", StyleBox["many", FontSlant->"Italic"], " commands you can use to produce pictures in ", StyleBox["Mathematica", FontSlant->"Italic"], ". Today we're going to learn two of them.\n\nIf we have a function \ y=f(x), the easiest way to graph it is with the ", StyleBox["Plot", FontWeight->"Bold"], " command. The syntax is ", StyleBox["Plot[", FontWeight->"Bold"], " function, {x, xmin, xmax}", StyleBox["]", FontWeight->"Bold"], ". 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." }], "Text"], Cell[BoxData[{ \(\(f[x_] = x^2;\)\), "\[IndentingNewLine]", \(Plot[f[x], {x, \(-1\), 3}]\)}], "Input"], Cell[TextData[{ "You don't have to name a function before you can graph it. You can simply \ enter the function into the ", StyleBox["Plot", FontWeight->"Bold"], " command." }], "Text"], Cell[BoxData[ \(Plot[x\ *Sin[1/x], {x, \(-0.3\), 0.3}]\)], "Input"], Cell["You can name plots so you can refer to them later as well:", "Text"], Cell[BoxData[{ \(plot1 = Plot[Sin[x], {x, 0, 2 Pi}]\), "\[IndentingNewLine]", \(plot2 = Plot[Cos[x], {x, 0, 2 Pi}]\)}], "Input"], Cell[TextData[{ "If you've named a graph and you want to display it again later, you can \ use the ", StyleBox["Show", FontWeight->"Bold"], " command. You can give the command the names of multiple plots, and it \ will show them together:" }], "Text"], Cell[BoxData[ \(Show[plot1, plot2]\)], "Input"], Cell[CellGroupData[{ Cell[TextData[StyleBox["Options", FontWeight->"Bold"]], "Subsubsection"], Cell[TextData[{ "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\ \[RightArrow]Setting.\" [You can type the \[RightArrow] as (hyphen)(greater \ than), \[Dash]\[Succeeds]]. For example, the option Axes\[RightArrow]False \ will prevent ", StyleBox["Mathematica", FontSlant->"Italic"], " from showing the x- and y- axes in a graph. This option works with ", StyleBox["Plot", FontWeight->"Bold"], " and ", StyleBox["Show", FontWeight->"Bold"], ". Try adding it to the ", StyleBox["Show", FontWeight->"Bold"], " command above and re-evaluating it. (You need to add a comma after \ \"plot2\" before you can add the option.) Did the axes disappear?" }], "Text"] }, Open ]] }, Open ]], Cell[CellGroupData[{ Cell["Saving Notebooks", "Subsection"], Cell[TextData[{ "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.\" ", StyleBox["Please note", FontWeight->"Bold"], ": 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.\n\nSo, 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 ", StyleBox["Mathematica", FontSlant->"Italic"], ". 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." }], "Text"] }, Open ]] }, Open ]], Cell[CellGroupData[{ Cell["Implementing the RSA Algorithm", "Section"], Cell["\<\ In order to implement the RSA algorithm, we need to know about how \ to store messages as numbers, as well as modular arithmetic.\ \>", "Text"], Cell[CellGroupData[{ Cell["Basic Modular Arithmetic and Number Theory in Mathematica", "Subsection"], Cell[TextData[{ "To compute ", Cell[BoxData[ \(TraditionalForm\`x\ mod\ n\)]], " you use the ", Cell[BoxData[ FormBox[ StyleBox[\(Mod[x, n]\), FontWeight->"Bold"], TraditionalForm]]], " command, as in:" }], "Text"], Cell[BoxData[ \(Mod[30, 26]\)], "Input"], Cell[TextData[{ "We've learned to find greatest common divisors (and multiplicative \ inverses ", StyleBox["mod n", FontSlant->"Italic"], ") using the Euclidean Algorithm. In ", StyleBox["Mathematica", FontSlant->"Italic"], " we don't have to go through all those steps. For example, to find the \ greatest common divisor of 45 and 81, type:" }], "Text"], Cell[BoxData[ \(GCD[45, 81]\)], "Input"], Cell[TextData[{ "Here's a massively useful function: ", StyleBox["PowerMod[x,p,n]", FontWeight->"Bold", FontSlant->"Italic"], ". This computes ", Cell[BoxData[ \(TraditionalForm\`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 ", Cell[BoxData[ \(TraditionalForm\`p = \(-1\)\)]], " to compute multiplicative inverses." }], "Text"], Cell[BoxData[ \(PowerMod[3, \(-1\), 4060]\)], "Input"], Cell["We can check this answer:", "Text"], Cell[BoxData[ \(Mod[3*2707, 4060]\)], "Input"], Cell[TextData[{ "Also note that ", StyleBox["Mathematica", FontSlant->"Italic"], " will tell you if you inadvertantly ask for an inverse which doesn't \ exist:" }], "Text"], Cell[BoxData[ \(PowerMod[13, \(-1\), 26]\)], "Input"], Cell[TextData[{ "One other function we need to use is the Euler Phi Function, ", Cell[BoxData[ \(TraditionalForm\`\[Phi](n)\)]], ". It's computed as follows (here n=88):" }], "Text"], Cell[BoxData[ \(EulerPhi[88]\)], "Input"] }, Open ]], Cell[CellGroupData[{ Cell["Dealing with Text in Mathematica", "Subsection"], Cell[TextData[{ "In ", StyleBox["Mathematica", FontSlant->"Italic"], ", strings of characters are enclosed with ", StyleBox["double", FontSlant->"Italic"], " quotes:" }], "Text"], Cell[BoxData[ \(plaintext = "\"\)], "Input"], Cell[TextData[{ "To implement RSA we need to convert out characters to numbers. ", StyleBox["Mathematica", FontSlant->"Italic"], " has a method for doing this called ", StyleBox["ToCharacterCode[]", FontWeight->"Bold"], ":" }], "Text"], Cell[BoxData[ \(ToCharacterCode[plaintext]\)], "Input"], Cell[TextData[{ "Notice that ", StyleBox["Mathematica", FontSlant->"Italic"], " returns a ", StyleBox["list", FontSlant->"Italic"], " of numbers. Each character has been converted to a number according to \ ", StyleBox["Mathematica", FontSlant->"Italic"], "'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.)\n", "\n", "Given a list of numbers, we can can convert it back to text using ", StyleBox["FromCharacterCode[]", FontWeight->"Bold"], ":" }], "Text"], Cell[BoxData[ \(FromCharacterCode[{73, 116, 32, 119, 111, 114, 107, 101, 100, 33}]\)], "Input"] }, Open ]], Cell[CellGroupData[{ Cell["Implementing RSA", "Subsection"], Cell[TextData[{ "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. ", StyleBox["Mathematica", FontSlant->"Italic"], " includes a function ", StyleBox["Prime[k]", FontWeight->"Bold"], " which returns the ", Cell[BoxData[ \(TraditionalForm\`k\^th\)]], "prime number. Let's take the nineteenth and twenty-first and primes for \ our example." }], "Text"], Cell[BoxData[{ \(p = Prime[19]\), "\[IndentingNewLine]", \(q = Prime[20]\), "\[IndentingNewLine]", \(n = p*q\)}], "Input"], Cell[TextData[{ "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 ", Cell[BoxData[ \(TraditionalForm\`e\ mod\ \(\[Phi](n)\)\)]], "." }], "Text"], Cell[BoxData[{ \(e = 3\), "\[IndentingNewLine]", \(d = PowerMod[e, \(-1\), EulerPhi[n]]\)}], "Input"], Cell[BoxData[ \(EulerPhi[n]\)], "Input"], Cell[TextData[{ "Uh-oh! It turns out that ", Cell[BoxData[ \(TraditionalForm\`\[Phi](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 ", Cell[BoxData[ \(TraditionalForm\`e = 13\)]], "would work for our public key:" }], "Text"], Cell[BoxData[{ \(e = 13\), "\[IndentingNewLine]", \(d = PowerMod[e, \(-1\), EulerPhi[n]]\)}], "Input"], Cell["Now let's create the list of numbers we want to encrypt:", "Text"], Cell[BoxData[ \(plaintext = ToCharacterCode["\"]\)], "Input"], Cell[TextData[{ "A useful feature of lists in ", StyleBox["Mathematica", FontSlant->"Italic"], " is that an operation will be performed separately on each member of the \ list. For example:" }], "Text"], Cell[BoxData[{ \({1, 2, 3, 4, 5, 6} + 3\), "\[IndentingNewLine]", \({1, 2, 3, 4, 5, 6}^2\)}], "Input"], Cell[TextData[{ "Therefore, to raise each of our \"plaintext number\" to the ", Cell[BoxData[ \(TraditionalForm\`e\^th\)]], "power, we just raise the whole list the the ", Cell[BoxData[ \(TraditionalForm\`e\^th\)]], "power, and then reduce mod n. You can use either of the following \ commands:" }], "Text"], Cell[BoxData[{ \(ciphertext = Mod[plaintext^e, n]\), "\[IndentingNewLine]", \(ciphertext = PowerMod[plaintext, e, n]\)}], "Input"], Cell["\<\ Now let's double check that the decryption process works as \ advertised:\ \>", "Text"], Cell[BoxData[ \(decrypted = PowerMod[ciphertext, d, n]\)], "Input"], Cell[BoxData[ \(FromCharacterCode[decrypted]\)], "Input"], Cell["\<\ 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.)\ \>", "Text"], Cell[TextData[{ StyleBox["Exercise 1", FontWeight->"Bold"], "\n\nUse the ", StyleBox["Prime[k]", FontWeight->"Bold"], " function with k-values inbetween 500 and 1000 to generate an RSA key ", Cell[BoxData[ \(TraditionalForm\`\((n, e, d)\)\)]], ". Make sure your choices for ", StyleBox["e", FontSlant->"Italic"], " and ", StyleBox["d", FontSlant->"Italic"], " are valid! ", "Use your ", StyleBox["private", FontSlant->"Italic"], " key ", StyleBox["d", FontSlant->"Italic"], " to encrypt the word \"math\" and send me the resulting list of encrypted \ numbers along with the public part of the key, ", Cell[BoxData[ \(TraditionalForm\`\((n, e)\)\)]], ". This is a form of ", StyleBox["message authentication", FontSlant->"Italic"], "; I should be able to use ", StyleBox["e", FontSlant->"Italic"], " and ", StyleBox["n", FontSlant->"Italic"], " to decrypt your numbers and verify that the result is the word \ \"math.\"", "\n\n", StyleBox["Exercise 2", FontWeight->"Bold"], "\n\nYou are working for the government, trying to crack an ultra-secret \ sent by a foreign embassy. It was encoded using ", StyleBox["Mathematica", FontSlant->"Italic"], " 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\n\t\t", Cell[BoxData[ \(TraditionalForm\`\((n, e)\) = \((3574406403731, 65537)\)\)]], "\n\nThe message you've intercepted is\n\n\ {3145498042951,399536786549,2151517025468,2162527373498,1358752710204,\\\n\ 1692699813511,1574798950684,770507905045,399536786549,1358752710204,\\\n\ 2722160106600,1574798950684,2131168730337,299208071831,399536786549,\\\n\ 2722160106600,1358752710204,1814962457452,2899472317519,1814962457452,\\\n\ 399536786549,770507905045,3520273614506,1358752710204,2225716991430,\\\n\ 399536786549,2270936083495,770507905045,399536786549,1358752710204,\\\n\ 2899472317519,299208071831,299208071831,1358752710204,1574798950684,\\\n\ 744774205513,2722160106600,550046915935}\n\nFind the decryption key ", StyleBox["d", FontSlant->"Italic"], " and decrypt the message\n\n", StyleBox["Exercise 3", FontWeight->"Bold"], "\n\nTry to use ", StyleBox["Mathematica", FontSlant->"Italic"], " to generate an RSA key ", Cell[BoxData[ \(TraditionalForm\`\((n, e, d)\)\)]], "that I can't break. Give me the public part of the key, namely ", StyleBox["n", FontSlant->"Italic"], " and ", StyleBox["e", FontSlant->"Italic"], "." }], "Text", CellFrame->True, Background->GrayLevel[0.833326]] }, Open ]] }, Open ]] }, FrontEndVersion->"5.0 for X", ScreenRectangle->{{0, 1024}, {0, 768}}, ScreenStyleEnvironment->"Working", WindowSize->{607, 692}, WindowMargins->{{Automatic, 54}, {11, Automatic}} ] (******************************************************************* Cached data follows. If you edit this Notebook file directly, not using Mathematica, you must remove the line containing CacheID at the top of the file. The cache data will then be recreated when you save this file from within Mathematica. *******************************************************************) (*CellTagsOutline CellTagsIndex->{} *) (*CellTagsIndex CellTagsIndex->{} *) (*NotebookFileOutline Notebook[{ Cell[1754, 51, 777, 29, 71, "Text"], Cell[2534, 82, 383, 8, 86, "Text"], Cell[CellGroupData[{ Cell[2942, 94, 145, 5, 105, "Section"], Cell[3090, 101, 697, 14, 122, "Text"], Cell[CellGroupData[{ Cell[3812, 119, 46, 0, 38, "Subsection"], Cell[3861, 121, 722, 16, 158, "Text"], Cell[4586, 139, 38, 1, 27, "Input"], Cell[4627, 142, 37, 1, 27, "Input"], Cell[4667, 145, 375, 9, 104, "Text"], Cell[5045, 156, 77, 2, 43, "Input"], Cell[5125, 160, 490, 10, 104, "Text"], Cell[5618, 172, 80, 2, 43, "Input"], Cell[5701, 176, 54, 1, 27, "Input"], Cell[5758, 179, 490, 13, 86, "Text"], Cell[6251, 194, 72, 2, 43, "Input"], Cell[6326, 198, 178, 4, 50, "Text"], Cell[6507, 204, 161, 4, 75, "Input"], Cell[6671, 210, 110, 3, 32, "Text"], Cell[6784, 215, 36, 1, 27, "Input"], Cell[6823, 218, 90, 3, 32, "Text"], Cell[6916, 223, 35, 1, 27, "Input"], Cell[6954, 226, 654, 11, 158, "Text"], Cell[7611, 239, 44, 1, 27, "Input"] }, Open ]], Cell[CellGroupData[{ Cell[7692, 245, 31, 0, 38, "Subsection"], Cell[7726, 247, 329, 7, 68, "Text"], Cell[8058, 256, 40, 1, 27, "Input"], Cell[8101, 259, 370, 12, 51, "Text"], Cell[8474, 273, 43, 1, 27, "Input"], Cell[8520, 276, 208, 4, 50, "Text"], Cell[8731, 282, 41, 1, 27, "Input"], Cell[8775, 285, 37, 1, 27, "Input"], Cell[8815, 288, 278, 7, 50, "Text"], Cell[9096, 297, 42, 1, 27, "Input"], Cell[9141, 300, 676, 24, 86, "Text"], Cell[9820, 326, 2041, 59, 441, "Text"], Cell[11864, 387, 608, 17, 86, "Text"], Cell[12475, 406, 83, 1, 27, "Input"], Cell[12561, 409, 172, 5, 32, "Text"], Cell[12736, 416, 108, 2, 27, "Input"], Cell[12847, 420, 44, 1, 27, "Input"], Cell[12894, 423, 66, 1, 27, "Input"] }, Open ]], Cell[CellGroupData[{ Cell[12997, 429, 34, 0, 38, "Subsection"], Cell[13034, 431, 1085, 19, 266, "Text"] }, Open ]], Cell[CellGroupData[{ Cell[14156, 455, 49, 0, 38, "Subsection"], Cell[14208, 457, 205, 5, 50, "Text"], Cell[14416, 464, 44, 1, 27, "Input"], Cell[14463, 467, 560, 14, 86, "Text"], Cell[15026, 483, 493, 11, 102, "Text"], Cell[15522, 496, 634, 11, 158, "Text"], Cell[16159, 509, 172, 4, 75, "Input"], Cell[16334, 515, 249, 6, 50, "Text"], Cell[16586, 523, 153, 3, 59, "Input"], Cell[CellGroupData[{ Cell[16764, 530, 32, 0, 28, "Subsubsection"], Cell[16799, 532, 1261, 33, 224, "Text"] }, Open ]] }, Open ]], Cell[CellGroupData[{ Cell[18109, 571, 36, 0, 38, "Subsection"], Cell[18148, 573, 661, 19, 122, "Text"], Cell[18812, 594, 111, 2, 43, "Input"], Cell[18926, 598, 196, 6, 50, "Text"], Cell[19125, 606, 71, 1, 27, "Input"], Cell[19199, 609, 74, 0, 32, "Text"], Cell[19276, 611, 139, 2, 43, "Input"], Cell[19418, 615, 262, 7, 50, "Text"], Cell[19683, 624, 51, 1, 27, "Input"], Cell[CellGroupData[{ Cell[19759, 629, 74, 1, 28, "Subsubsection"], Cell[19836, 632, 800, 19, 122, "Text"] }, Open ]] }, Open ]], Cell[CellGroupData[{ Cell[20685, 657, 38, 0, 38, "Subsection"], Cell[20726, 659, 1152, 20, 248, "Text"] }, Open ]] }, Open ]], Cell[CellGroupData[{ Cell[21927, 685, 49, 0, 76, "Section"], Cell[21979, 687, 153, 3, 50, "Text"], Cell[CellGroupData[{ Cell[22157, 694, 79, 0, 38, "Subsection"], Cell[22239, 696, 254, 10, 32, "Text"], Cell[22496, 708, 44, 1, 27, "Input"], Cell[22543, 711, 374, 10, 68, "Text"], Cell[22920, 723, 44, 1, 27, "Input"], Cell[22967, 726, 484, 13, 68, "Text"], Cell[23454, 741, 58, 1, 27, "Input"], Cell[23515, 744, 41, 0, 32, "Text"], Cell[23559, 746, 50, 1, 27, "Input"], Cell[23612, 749, 182, 6, 50, "Text"], Cell[23797, 757, 57, 1, 27, "Input"], Cell[23857, 760, 195, 5, 50, "Text"], Cell[24055, 767, 45, 1, 27, "Input"] }, Open ]], Cell[CellGroupData[{ Cell[24137, 773, 54, 0, 38, "Subsection"], Cell[24194, 775, 196, 8, 32, "Text"], Cell[24393, 785, 62, 1, 27, "Input"], Cell[24458, 788, 254, 8, 50, "Text"], Cell[24715, 798, 59, 1, 27, "Input"], Cell[24777, 801, 586, 18, 104, "Text"], Cell[25366, 821, 108, 2, 27, "Input"] }, Open ]], Cell[CellGroupData[{ Cell[25511, 828, 38, 0, 38, "Subsection"], Cell[25552, 830, 474, 13, 86, "Text"], Cell[26029, 845, 136, 3, 59, "Input"], Cell[26168, 850, 270, 7, 50, "Text"], Cell[26441, 859, 110, 2, 43, "Input"], Cell[26554, 863, 44, 1, 27, "Input"], Cell[26601, 866, 356, 9, 68, "Text"], Cell[26960, 877, 111, 2, 43, "Input"], Cell[27074, 881, 72, 0, 32, "Text"], Cell[27149, 883, 87, 1, 27, "Input"], Cell[27239, 886, 213, 6, 50, "Text"], Cell[27455, 894, 111, 2, 43, "Input"], Cell[27569, 898, 330, 9, 50, "Text"], Cell[27902, 909, 139, 2, 43, "Input"], Cell[28044, 913, 97, 3, 32, "Text"], Cell[28144, 918, 71, 1, 27, "Input"], Cell[28218, 921, 61, 1, 27, "Input"], Cell[28282, 924, 234, 4, 68, "Text"], Cell[28519, 930, 2712, 78, 642, "Text"] }, Open ]] }, Open ]] } ] *) (******************************************************************* End of Mathematica Notebook file. *******************************************************************)