(* Content-type: application/vnd.wolfram.mathematica *) (*** Wolfram Notebook File ***) (* http://www.wolfram.com/nb *) (* CreatedBy='Mathematica 10.0' *) (*CacheID: 234*) (* Internal cache information: NotebookFileLineBreakTest NotebookFileLineBreakTest NotebookDataPosition[ 158, 7] NotebookDataLength[ 49771, 1551] NotebookOptionsPosition[ 43120, 1323] NotebookOutlinePosition[ 43533, 1341] CellTagsIndexPosition[ 43490, 1338] WindowFrame->Normal*) (* Beginning of Notebook Content *) Notebook[{ Cell[CellGroupData[{ Cell["RSA (Rivest, Shamir, Adleman)", "Section", CellChangeTimes->{{3.625241887804907*^9, 3.6252419227930393`*^9}}], Cell[CellGroupData[{ Cell["asymmetric key cryptosystem/ public key cryptosystem", "Item", CellChangeTimes->{{3.625241937231802*^9, 3.625241971505184*^9}, { 3.62524200549032*^9, 3.625242006230294*^9}}], Cell["\<\ can be used for both encryption/decryption and authentication; in RSA we use \ the sender\[CloseCurlyQuote]s private key to sign the message and the \ recipient\[CloseCurlyQuote]s public key to encrypt the message.\ \>", "Item", CellChangeTimes->{{3.625241937231802*^9, 3.6252419776651897`*^9}, { 3.6252420093143587`*^9, 3.6252421141844254`*^9}, {3.625244180064468*^9, 3.625244180066016*^9}, {3.702697105963958*^9, 3.7026971104568996`*^9}}, TextJustification->1.], Cell["\<\ the security of the RSA cryptosystem resides in the hardness/time consuming \ problem of factoring a large number (the public modulus m) into its two prime \ factors (private primes p and q). Factoring integers is much harder than \ multiplying them!\ \>", "Item", CellChangeTimes->{{3.625241937231802*^9, 3.6252419776651897`*^9}, { 3.6252420093143587`*^9, 3.62524220685837*^9}, {3.625244217053761*^9, 3.62524421705651*^9}, {3.6252475184510117`*^9, 3.625247525273896*^9}}, TextJustification->1.] }, Open ]], Cell[BoxData[{ RowBox[{ RowBox[{"p", "=", "999999599"}], ";"}], "\[IndentingNewLine]", RowBox[{ RowBox[{"q", "=", "9999999967"}], ";"}], "\[IndentingNewLine]", RowBox[{ RowBox[{"m", "=", RowBox[{"p", "*", "q"}]}], ";"}]}], "Input", CellChangeTimes->{{3.625247835516335*^9, 3.625247861711792*^9}, { 3.6252479016059723`*^9, 3.625247906477366*^9}}, Background->RGBColor[0.87, 0.94, 1]], Cell[BoxData[{ RowBox[{"Timing", "[", RowBox[{"p", "*", "q"}], "]"}], "\[IndentingNewLine]", RowBox[{"Timing", "[", RowBox[{"FactorInteger", "[", "m", "]"}], "]"}]}], "Input", CellChangeTimes->{{3.6252478668468847`*^9, 3.625247898414075*^9}, 3.625247984712278*^9, {3.625248039608633*^9, 3.6252480446968603`*^9}}, Background->RGBColor[0.87, 0.94, 1]], Cell[BoxData[{ RowBox[{ RowBox[{"p", "=", "2425967623052370772757633156976982469681"}], ";"}], "\[IndentingNewLine]", RowBox[{ RowBox[{"q", "=", "5570373270183181665098052481109678989411"}], ";"}], "\[IndentingNewLine]", RowBox[{ RowBox[{"m", "=", RowBox[{"p", "*", "q"}]}], ";"}]}], "Input", CellChangeTimes->{{3.625247835516335*^9, 3.625247861711792*^9}, { 3.6252479016059723`*^9, 3.625247906477366*^9}, {3.625248104305825*^9, 3.6252481417593937`*^9}}, Background->RGBColor[0.87, 0.94, 1]], Cell[BoxData[{ RowBox[{"Timing", "[", RowBox[{"p", "*", "q"}], "]"}], "\[IndentingNewLine]", RowBox[{"Timing", "[", RowBox[{"FactorInteger", "[", "m", "]"}], "]"}]}], "Input", CellChangeTimes->{{3.6252478668468847`*^9, 3.625247898414075*^9}, 3.625247984712278*^9, {3.625248039608633*^9, 3.6252480446968603`*^9}, { 3.625248168745511*^9, 3.625248172576198*^9}}, Background->RGBColor[0.87, 0.94, 1]], Cell[TextData[{ StyleBox["The largest known prime number as of January 2017 is ", FontColor->RGBColor[1, 0, 1]], Cell[BoxData[ FormBox[ RowBox[{ SuperscriptBox["2", "74207281"], "-", "1"}], TraditionalForm]], FontColor->RGBColor[1, 0, 1]], ", a number with 22,338,618 decimal digits", StyleBox[". RSA protocols usually use a 2048-bit modulus m ", FontColor->RGBColor[1, 0, 1]], StyleBox["(which corresponds to 617 decimal digits)", FontColor->GrayLevel[0]], StyleBox[".", FontColor->RGBColor[1, 0, 1]] }], "Item", CellDingbat->"\[FivePointedStar]", CellChangeTimes->{{3.6252482697199497`*^9, 3.6252483284337606`*^9}, { 3.6252483673532267`*^9, 3.625248444993045*^9}, {3.6573154387673893`*^9, 3.657315485381854*^9}, {3.6573370371379147`*^9, 3.65733715324483*^9}, { 3.702697121223423*^9, 3.702697124049903*^9}, {3.702697911974164*^9, 3.702697928460547*^9}}] }, Open ]], Cell[CellGroupData[{ Cell["Mathematics behind RSA", "Section", CellChangeTimes->{{3.657336901492944*^9, 3.657336924400961*^9}}], Cell[CellGroupData[{ Cell[TextData[{ "RSA is based on ", StyleBox["Euler\[CloseCurlyQuote]s Theorem", FontWeight->"Bold"], ". Let p and q be two distinct prime numbers. Let m=pq." }], "Item", CellChangeTimes->{{3.625241937231802*^9, 3.6252419776651897`*^9}, { 3.6252420093143587`*^9, 3.62524220685837*^9}, {3.625244217053761*^9, 3.62524428543279*^9}, {3.625244338711761*^9, 3.625244342512076*^9}, 3.657337988592413*^9}], Cell[CellGroupData[{ Cell[TextData[{ " If a is relatively prime to m, then", StyleBox[" ", FontSize->14], Cell[BoxData[ FormBox[ RowBox[{ StyleBox[ SuperscriptBox["a", RowBox[{ RowBox[{"(", RowBox[{"p", "-", "1"}], ")"}], RowBox[{"(", RowBox[{"q", "-", "1"}], ")"}]}]], FontSize->16], "\[Congruent]", RowBox[{"1", RowBox[{"(", RowBox[{"mod", " ", "m"}], ")"}]}]}], TraditionalForm]], FontSize->14], "." }], "SubitemNumbered", CellChangeTimes->{{3.625241937231802*^9, 3.6252419776651897`*^9}, { 3.6252420093143587`*^9, 3.62524220685837*^9}, {3.625244217053761*^9, 3.625244394489273*^9}}], Cell["\<\ If a is any integer (not necessarily relatively prime to m), and k is any \ positive integer, then \ \>", "SubitemNumbered", CellChangeTimes->{{3.625241937231802*^9, 3.6252419776651897`*^9}, { 3.6252420093143587`*^9, 3.62524220685837*^9}, {3.625244217053761*^9, 3.625244446993721*^9}}], Cell[TextData[{ Cell[BoxData[ FormBox[ RowBox[{ StyleBox[ SuperscriptBox["a", RowBox[{ RowBox[{ RowBox[{"k", "(", RowBox[{"p", "-", "1"}], ")"}], RowBox[{"(", RowBox[{"q", "-", "1"}], ")"}]}], "+", "1"}]], FontSize->16], "\[Congruent]", RowBox[{"a", "(", RowBox[{"mod", " ", "m"}], ")"}]}], TraditionalForm]], FontSize->14], "." }], "SubitemParagraph", CellChangeTimes->{{3.625241937231802*^9, 3.6252419776651897`*^9}, { 3.6252420093143587`*^9, 3.62524220685837*^9}, {3.625244217053761*^9, 3.625244471590376*^9}}] }, Open ]], Cell[TextData[{ "This is a particular case of the ", StyleBox["general form of Euler\[CloseCurlyQuote]s Theorem", FontWeight->"Bold"], " which says that is m is any positive integer, and a is relatively prime to \ m, then ", Cell[BoxData[ FormBox[ RowBox[{ StyleBox[ SuperscriptBox["a", RowBox[{"\[Phi]", "(", "m", ")"}]], FontSize->16], "\[Congruent]", RowBox[{"1", RowBox[{"(", RowBox[{"mod", " ", "m"}], ")"}]}]}], TraditionalForm]], FontSize->14], ", where \[Phi] is Euler\[CloseCurlyQuote]s totient function." }], "Item", CellChangeTimes->{{3.702697960131833*^9, 3.702698107567314*^9}}] }, Open ]] }, Open ]], Cell[CellGroupData[{ Cell["RSA Setup", "Section", CellChangeTimes->{{3.625244572560223*^9, 3.625244584847946*^9}, { 3.657338059669033*^9, 3.6573380609066143`*^9}}], Cell[CellGroupData[{ Cell["\<\ Alice selects two distinct primes p and q and computes m=pq and n=(p-1)(q-1).\ \ \>", "Item", CellChangeTimes->{{3.625244606722229*^9, 3.625244671445468*^9}}], Cell["\<\ She chooses a number e, relatively prime to n=(p-1)(q-1), and finds the \ multiplicative inverse of e modulo n, that is, she finds an integer d such \ that ed\[Congruent]1(mod n).\ \>", "Item", CellChangeTimes->{{3.625244606722229*^9, 3.625244766470434*^9}}], Cell["\<\ Alice makes (m,e) public. m is called the public modulus, and e the public \ key or the encryption key.\ \>", "Item", CellChangeTimes->{{3.625244606722229*^9, 3.625244801735038*^9}, { 3.6573372647084417`*^9, 3.65733726575493*^9}}], Cell["\<\ Alice keeps p,q,n,d a secret. d is called the private key or the decryption \ key. \ \>", "Item", CellChangeTimes->{{3.625244606722229*^9, 3.625244852834271*^9}}] }, Open ]], Cell[TextData[{ "Encryption function: ", Cell[BoxData[ FormBox[ RowBox[{ RowBox[{"E", "(", "x", ")"}], "=", RowBox[{ SuperscriptBox["x", StyleBox["e", FontSize->16]], "(", RowBox[{"mod", " ", "m"}], ")"}]}], TraditionalForm]], FontColor->GrayLevel[0]], StyleBox[", where 1\[LessEqual]x\[LessEqual]m-1.", FontColor->GrayLevel[0]] }], "Subsection", CellChangeTimes->{{3.625244875687395*^9, 3.625244958389371*^9}, 3.625245007917489*^9, 3.625245068090877*^9}], Cell[TextData[{ "Decryption function: ", Cell[BoxData[ FormBox[ RowBox[{ RowBox[{"D", "(", "y", ")"}], "=", RowBox[{ SuperscriptBox["y", StyleBox["d", FontSize->16]], "(", RowBox[{"mod", " ", "m"}], ")"}]}], TraditionalForm]], FontColor->GrayLevel[0]], StyleBox[", where 1\[LessEqual]y\[LessEqual]m-1.", FontColor->GrayLevel[0]] }], "Subsection", CellChangeTimes->{{3.625244875687395*^9, 3.625244998861265*^9}, 3.625245070090597*^9}] }, Open ]], Cell[CellGroupData[{ Cell["Example", "Section", CellChangeTimes->{{3.6252422572710133`*^9, 3.62524225821455*^9}}], Cell[CellGroupData[{ Cell["Alice sets up an RSA scheme", "Subsection", CellChangeTimes->{{3.625242583978118*^9, 3.6252425995990343`*^9}}], Cell[CellGroupData[{ Cell["select primes p=11 and q=3.", "Item", CellChangeTimes->{{3.625242267734367*^9, 3.625242286112164*^9}}], Cell["compute m=pq=33 and n=(p-1)(q-1)=(11-1)(3-1)=20", "Item", CellChangeTimes->{{3.625242267734367*^9, 3.625242330850607*^9}}], Cell["\<\ choose a number e, relatively prime to n=20. Suppose we choose e=3.\ \>", "Item", CellChangeTimes->{{3.625242267734367*^9, 3.6252423658254957`*^9}}], Cell[TextData[{ "find an integer d such that ed\[Congruent]1(mod 20). The integer d is the \ multiplicative inverse of e, modulo 20. In this case, d=", Cell[BoxData[ FormBox[ RowBox[{ RowBox[{ SuperscriptBox["e", RowBox[{"-", "1"}]], "(", RowBox[{"mod", " ", "20"}], ")"}], "=", RowBox[{ RowBox[{ SuperscriptBox["3", RowBox[{"-", "1"}]], RowBox[{"(", RowBox[{"mod", " ", "20"}], ")"}]}], "=", RowBox[{"7", " ", RowBox[{ RowBox[{"(", RowBox[{"mod", " ", "20"}], ")"}], "."}]}]}]}], TraditionalForm]]], " " }], "Item", CellChangeTimes->{{3.625242267734367*^9, 3.6252425079335957`*^9}, { 3.657339484123369*^9, 3.657339485163246*^9}}], Cell["public key (m,e)=(33,3)", "Item", CellChangeTimes->{{3.625242267734367*^9, 3.625242528694952*^9}, { 3.625244110170093*^9, 3.625244110171534*^9}, {3.657338253790442*^9, 3.657338255279407*^9}}], Cell["e=3 is the public encryption key.", "ItemParagraph", CellChangeTimes->{{3.625242267734367*^9, 3.625242528694952*^9}, { 3.625244110170093*^9, 3.6252441402007504`*^9}, {3.65733825765312*^9, 3.657338257656754*^9}}], Cell["m=33 is the public modulus.", "ItemParagraph", CellChangeTimes->{{3.625242267734367*^9, 3.625242528694952*^9}, { 3.625244110170093*^9, 3.6252441402007504`*^9}, {3.65733825765312*^9, 3.657338268434039*^9}}], Cell["private key (p,q, n,d)=(11,3,20,7). ", "Item", CellChangeTimes->{{3.625242267734367*^9, 3.625242557807304*^9}, { 3.6252430269637547`*^9, 3.6252430566650763`*^9}, {3.6252430886950283`*^9, 3.6252432064506474`*^9}}], Cell["d=7 is the private decryption key.", "ItemParagraph", CellChangeTimes->{{3.625242267734367*^9, 3.625242557807304*^9}, { 3.6252430269637547`*^9, 3.6252430566650763`*^9}, {3.6252430886950283`*^9, 3.625243206447505*^9}, {3.625244145880591*^9, 3.625244156872418*^9}}] }, Open ]] }, Open ]], Cell[CellGroupData[{ Cell["Bob wants to send the message x=14 to Alice. ", "Subsection", CellChangeTimes->{{3.625242267734367*^9, 3.625242557802877*^9}, { 3.625242620433593*^9, 3.6252426380014963`*^9}}], Cell[CellGroupData[{ Cell["encrypt the message x=14 using Alice\[CloseCurlyQuote]s public key.", \ "Item", CellChangeTimes->{{3.625242663640246*^9, 3.625242680186634*^9}}], Cell[TextData[{ "compute y=", Cell[BoxData[ FormBox[ RowBox[{ RowBox[{ SuperscriptBox["x", "e"], "(", RowBox[{"mod", " ", "m"}], ")"}], "=", RowBox[{ RowBox[{ SuperscriptBox["14", "3"], RowBox[{"(", RowBox[{"mod", " ", "33"}], ")"}]}], "=", RowBox[{ RowBox[{"2744", " ", RowBox[{"(", RowBox[{"mod", " ", "33"}], ")"}]}], "=", RowBox[{"5", " ", RowBox[{ RowBox[{"(", RowBox[{"mod", " ", "33"}], ")"}], "."}]}]}]}]}], TraditionalForm]]] }], "Item", CellChangeTimes->{{3.625242663640246*^9, 3.625242806946746*^9}, { 3.657339529012929*^9, 3.65733953249858*^9}}], Cell[TextData[{ "the ciphertext is ", StyleBox["y=5", FontWeight->"Bold"], "." }], "Item", CellChangeTimes->{{3.625242663640246*^9, 3.625242823476877*^9}}], Cell["Bob sends the ciphertext y=5 to Alice.", "Item", CellChangeTimes->{{3.625242663640246*^9, 3.625242843115663*^9}}] }, Open ]] }, Open ]], Cell[CellGroupData[{ Cell["Alice receives the ciphertext y=5 (from Bob?)", "Subsection", CellChangeTimes->{{3.625242854507595*^9, 3.625242874755456*^9}}], Cell[CellGroupData[{ Cell["use the private key d=7 to decrypt it.", "Item", CellChangeTimes->{{3.625242998940206*^9, 3.6252430166551237`*^9}}], Cell[TextData[{ "compute x=", Cell[BoxData[ FormBox[ RowBox[{ RowBox[{ SuperscriptBox["y", "d"], "(", RowBox[{"mod", " ", "m"}], ")"}], "=", RowBox[{ SuperscriptBox["5", "7"], RowBox[{ RowBox[{"(", RowBox[{"mod", " ", "33"}], ")"}], "."}]}]}], TraditionalForm]]] }], "Item", CellChangeTimes->{{3.625242998940206*^9, 3.625243016651594*^9}, { 3.625243237149143*^9, 3.62524327279668*^9}, {3.625243319126224*^9, 3.625243326323463*^9}}], Cell[TextData[{ "x=", Cell[BoxData[ FormBox[ RowBox[{ RowBox[{ SuperscriptBox["5", "7"], RowBox[{"(", RowBox[{"mod", " ", "33"}], ")"}]}], "=", RowBox[{ RowBox[{ SuperscriptBox[ RowBox[{"(", SuperscriptBox["5", "3"], ")"}], "2"], "*", "5", " ", RowBox[{"(", RowBox[{"mod", " ", "33"}], ")"}]}], "=", RowBox[{ RowBox[{ SuperscriptBox["125", "2"], "*", "5"}], "=", RowBox[{ RowBox[{ SuperscriptBox[ RowBox[{"(", RowBox[{"-", "7"}], ")"}], "2"], "*", "5"}], "=", RowBox[{ RowBox[{"7", "*", "2"}], "=", RowBox[{"14", " ", RowBox[{"(", RowBox[{"mod", " ", "33"}], ")"}]}]}]}]}]}]}], TraditionalForm]]] }], "SubitemParagraph", CellChangeTimes->{{3.625242998940206*^9, 3.625243016651594*^9}, { 3.625243237149143*^9, 3.62524327279668*^9}, {3.625243319126224*^9, 3.62524351101333*^9}}], Cell["\<\ the decrypted message is x=14. (This is exactly Bob\[CloseCurlyQuote]s \ unencrypted message!)\ \>", "Item", CellChangeTimes->{{3.625243537937941*^9, 3.62524358762608*^9}}] }, Open ]] }, Open ]] }, Open ]], Cell[CellGroupData[{ Cell[TextData[{ "RSA with ", StyleBox["Mathematica", FontSlant->"Italic"] }], "Section", CellChangeTimes->{{3.657339643975224*^9, 3.657339654137108*^9}}], Cell[BoxData[{ RowBox[{ RowBox[{"EncryptionRSA", "[", RowBox[{ RowBox[{"x_", " ", "?", "IntegerQ"}], ",", " ", RowBox[{"e_", " ", "?", "IntegerQ"}], ",", " ", RowBox[{"m_", " ", "?", "IntegerQ"}]}], "]"}], ":=", " ", RowBox[{"PowerMod", "[", RowBox[{"x", ",", "e", ",", "m"}], "]"}]}], "\[IndentingNewLine]", RowBox[{"SetAttributes", "[", RowBox[{"EncryptionRSA", ",", " ", "Listable"}], "]"}]}], "Input", CellChangeTimes->{{3.6252458465831537`*^9, 3.625245954531653*^9}, 3.657339695466617*^9, {3.657339773714875*^9, 3.657339781398366*^9}, { 3.657339938657796*^9, 3.657339946126889*^9}, {3.657340581442622*^9, 3.65734059849508*^9}}, Background->RGBColor[0.87, 0.94, 1]], Cell[BoxData[{ RowBox[{ RowBox[{"DecryptionRSA", "[", RowBox[{ RowBox[{"x_", " ", "?", "IntegerQ"}], ",", " ", RowBox[{"d_", " ", "?", "IntegerQ"}], ",", " ", RowBox[{"m_", " ", "?", "IntegerQ"}]}], "]"}], ":=", " ", RowBox[{"PowerMod", "[", RowBox[{"x", ",", "d", ",", "m"}], "]"}]}], "\[IndentingNewLine]", RowBox[{"SetAttributes", "[", RowBox[{"DecryptionRSA", ",", " ", "Listable"}], "]"}]}], "Input", CellChangeTimes->{{3.6252467905928717`*^9, 3.625246845334633*^9}, 3.657339691926462*^9, {3.65733977120147*^9, 3.657339778231151*^9}, { 3.657339953560238*^9, 3.657339956894435*^9}, {3.657340589327003*^9, 3.657340606647954*^9}}, Background->RGBColor[0.87, 0.94, 1]], Cell["\<\ To decrypt the cipher message y = 5 received from Bob, Alice computes :\ \>", "Text", CellChangeTimes->{{3.657340001485924*^9, 3.657340051165872*^9}}], Cell[CellGroupData[{ Cell[BoxData[ RowBox[{"DecryptionRSA", "[", RowBox[{"5", ",", "7", ",", "33"}], "]"}]], "Input", CellChangeTimes->{{3.6573398149990053`*^9, 3.657339833573306*^9}}, Background->GrayLevel[0.85]], Cell[BoxData["14"], "Output", CellChangeTimes->{3.6573398349258213`*^9, 3.6573399751247168`*^9}] }, Open ]], Cell["\<\ To decrypt a list of cipher messages, say {5, 17, 10} received from Bob, \ Alice computes:\ \>", "Text", CellChangeTimes->{{3.657340613553617*^9, 3.6573406808031483`*^9}}], Cell[CellGroupData[{ Cell[BoxData[ RowBox[{"DecryptionRSA", "[", RowBox[{ RowBox[{"{", RowBox[{"5", ",", " ", "17", ",", " ", "10"}], "}"}], ",", "7", ",", "33"}], "]"}]], "Input", CellChangeTimes->{{3.6573398149990053`*^9, 3.657339833573306*^9}, { 3.657340688847287*^9, 3.6573406940323753`*^9}}, Background->GrayLevel[0.85]], Cell[BoxData[ RowBox[{"{", RowBox[{"14", ",", "8", ",", "10"}], "}"}]], "Output", CellChangeTimes->{{3.6573406951017027`*^9, 3.6573407050457373`*^9}}] }, Open ]], Cell["\<\ Short exercise: Produce a table with the encryptions of all integers between \ 0 and 32. How many unconcealed messages are there?\ \>", "Subsubsection", CellChangeTimes->{{3.657340867354693*^9, 3.6573408836104116`*^9}, { 3.657340942329458*^9, 3.65734094279469*^9}, {3.657347428476569*^9, 3.657347460083763*^9}, {3.6573474955814247`*^9, 3.6573475131980953`*^9}, 3.702735693021356*^9}], Cell[CellGroupData[{ Cell["Solution: ", "Subsubsection", CellChangeTimes->{{3.657340867354693*^9, 3.6573408836104116`*^9}, { 3.657340942329458*^9, 3.65734094279469*^9}, {3.657347428476569*^9, 3.657347460083763*^9}, {3.6573474955814247`*^9, 3.6573475131980953`*^9}, { 3.702735693021356*^9, 3.7027357062760963`*^9}}], Cell[CellGroupData[{ Cell[BoxData[ RowBox[{"T", "=", RowBox[{"Table", "[", RowBox[{ RowBox[{"i", "->", RowBox[{"EncryptionRSA", "[", RowBox[{"i", ",", " ", "3", ",", " ", "33"}], "]"}]}], ",", RowBox[{"{", RowBox[{"i", ",", "0", ",", "32"}], "}"}]}], "]"}]}]], "Input", CellChangeTimes->{{3.6252459615824757`*^9, 3.625246155689386*^9}, { 3.657340952638586*^9, 3.65734097435712*^9}}, Background->RGBColor[0.87, 0.94, 1]], Cell[BoxData[ RowBox[{"{", RowBox[{ RowBox[{"0", "\[Rule]", "0"}], ",", RowBox[{"1", "\[Rule]", "1"}], ",", RowBox[{"2", "\[Rule]", "8"}], ",", RowBox[{"3", "\[Rule]", "27"}], ",", RowBox[{"4", "\[Rule]", "31"}], ",", RowBox[{"5", "\[Rule]", "26"}], ",", RowBox[{"6", "\[Rule]", "18"}], ",", RowBox[{"7", "\[Rule]", "13"}], ",", RowBox[{"8", "\[Rule]", "17"}], ",", RowBox[{"9", "\[Rule]", "3"}], ",", RowBox[{"10", "\[Rule]", "10"}], ",", RowBox[{"11", "\[Rule]", "11"}], ",", RowBox[{"12", "\[Rule]", "12"}], ",", RowBox[{"13", "\[Rule]", "19"}], ",", RowBox[{"14", "\[Rule]", "5"}], ",", RowBox[{"15", "\[Rule]", "9"}], ",", RowBox[{"16", "\[Rule]", "4"}], ",", RowBox[{"17", "\[Rule]", "29"}], ",", RowBox[{"18", "\[Rule]", "24"}], ",", RowBox[{"19", "\[Rule]", "28"}], ",", RowBox[{"20", "\[Rule]", "14"}], ",", RowBox[{"21", "\[Rule]", "21"}], ",", RowBox[{"22", "\[Rule]", "22"}], ",", RowBox[{"23", "\[Rule]", "23"}], ",", RowBox[{"24", "\[Rule]", "30"}], ",", RowBox[{"25", "\[Rule]", "16"}], ",", RowBox[{"26", "\[Rule]", "20"}], ",", RowBox[{"27", "\[Rule]", "15"}], ",", RowBox[{"28", "\[Rule]", "7"}], ",", RowBox[{"29", "\[Rule]", "2"}], ",", RowBox[{"30", "\[Rule]", "6"}], ",", RowBox[{"31", "\[Rule]", "25"}], ",", RowBox[{"32", "\[Rule]", "32"}]}], "}"}]], "Output", CellChangeTimes->{3.657340975056321*^9}] }, Open ]] }, Open ]] }, Open ]], Cell[CellGroupData[{ Cell["Unconcealed Messages:", "Section", CellChangeTimes->{{3.625246213629616*^9, 3.625246216828774*^9}, { 3.6573410582922573`*^9, 3.6573410692883253`*^9}}], Cell[CellGroupData[{ Cell["\<\ All 33 values of x (from 0 to 32) map to unique ciphertext values y in the \ same range, in a sort of random manner.\ \>", "Item", CellChangeTimes->{{3.6252462336386127`*^9, 3.6252462782600117`*^9}}], Cell[TextData[{ "There are 9 values of x that map to themselves, 0,1,10,11,12, 21, 22, 23, \ 32! These are called unconcealed messages. The numbers 0,1,m-1 are no \ surprise, because they always map to themselves under the map ", Cell[BoxData[ FormBox[ SuperscriptBox["x", "e"], TraditionalForm]]], " (mod m). To see how many unconcealed messages there are for a chosen pair \ (m,e), we must solve a modular equation ", Cell[BoxData[ FormBox[ RowBox[{ SuperscriptBox["x", "e"], "\[Congruent]", " ", "x"}], TraditionalForm]]], " (mod m), or equivalently ", Cell[BoxData[ FormBox[ RowBox[{ SuperscriptBox["x", "d"], "\[Congruent]", " ", "x"}], TraditionalForm]]], " (mod m). In this case one solves ", Cell[BoxData[ FormBox[ RowBox[{ SuperscriptBox["x", "3"], "\[Congruent]", " ", RowBox[{"x", " ", RowBox[{"(", RowBox[{"mod", " ", "33"}], ")"}]}]}], TraditionalForm]]], ", which is equivalent to ", Cell[BoxData[ FormBox[ RowBox[{ RowBox[{ RowBox[{"x", "(", RowBox[{"x", "-", "1"}], ")"}], RowBox[{"(", RowBox[{"x", "+", "1"}], ")"}]}], "\[Congruent]", " ", RowBox[{"0", " ", RowBox[{"(", RowBox[{"mod", " ", "33"}], ")"}]}]}], TraditionalForm]]], "." }], "Item", CellChangeTimes->{{3.6252462336386127`*^9, 3.6252463243428593`*^9}, { 3.625246366702887*^9, 3.625246477444512*^9}, {3.625246538025545*^9, 3.625246570482761*^9}, {3.625246600820777*^9, 3.625246722498713*^9}, { 3.657908548239049*^9, 3.657908599071479*^9}}] }, Open ]], Cell[CellGroupData[{ Cell[BoxData[ RowBox[{"Solve", "[", RowBox[{ RowBox[{ RowBox[{"x", "^", "3"}], "\[Equal]", "x"}], ",", " ", "x", ",", " ", RowBox[{"Modulus", "\[Rule]", "33"}]}], "]"}]], "Input", CellChangeTimes->{{3.6252464898201103`*^9, 3.6252465058739157`*^9}}, FontSize->14, Background->RGBColor[0.87, 0.94, 1]], Cell[BoxData[ RowBox[{"{", RowBox[{ RowBox[{"{", RowBox[{"x", "\[Rule]", "0"}], "}"}], ",", RowBox[{"{", RowBox[{"x", "\[Rule]", "1"}], "}"}], ",", RowBox[{"{", RowBox[{"x", "\[Rule]", "10"}], "}"}], ",", RowBox[{"{", RowBox[{"x", "\[Rule]", "11"}], "}"}], ",", RowBox[{"{", RowBox[{"x", "\[Rule]", "12"}], "}"}], ",", RowBox[{"{", RowBox[{"x", "\[Rule]", "21"}], "}"}], ",", RowBox[{"{", RowBox[{"x", "\[Rule]", "22"}], "}"}], ",", RowBox[{"{", RowBox[{"x", "\[Rule]", "23"}], "}"}], ",", RowBox[{"{", RowBox[{"x", "\[Rule]", "32"}], "}"}]}], "}"}]], "Output", CellChangeTimes->{3.625246508907522*^9, 3.657343885806881*^9}] }, Open ]], Cell[TextData[{ StyleBox["Theorem:", FontWeight->"Bold"], " Let m = pq be the product of two distinct prime numbers, and suppose that \ e is relatively prime to (p-1)(q-1). Then the number of elements x in ", Cell[BoxData[ StyleBox[ SubscriptBox["\[DoubleStruckCapitalZ]", "m"], FontSize->16, FontWeight->"Bold"]], CellChangeTimes->{{3.657341362359997*^9, 3.6573414951571074`*^9}, { 3.657341538379751*^9, 3.6573415771763563`*^9}}], " that satisfy the relation ", Cell[BoxData[ FormBox[ StyleBox[ RowBox[{ SuperscriptBox["x", StyleBox["e", FontSize->12]], "=", "x"}], FontSize->16], TraditionalForm]]], " (mod m) is given by ", StyleBox["(GCD[e-1,p-1]+1)(GCD[e-1,q-1]+1)", FontWeight->"Bold", FontColor->RGBColor[0.5, 0, 0.5]], StyleBox[".", FontWeight->"Bold", FontColor->RGBColor[1, 0, 0]] }], "Text", CellChangeTimes->{{3.657341584334991*^9, 3.6573418441060133`*^9}, { 3.657342146548665*^9, 3.6573422225547333`*^9}, {3.657908246867893*^9, 3.657908250864717*^9}, 3.702735671071718*^9}], Cell[BoxData[{ RowBox[{ RowBox[{"p", "=", "3"}], ";", RowBox[{"q", "=", "11"}], ";", RowBox[{"e", "=", "3"}], ";"}], "\[IndentingNewLine]", RowBox[{ RowBox[{"(", RowBox[{ RowBox[{"GCD", "[", RowBox[{ RowBox[{"e", "-", "1"}], ",", RowBox[{"p", "-", "1"}]}], "]"}], "+", "1"}], ")"}], RowBox[{"(", RowBox[{ RowBox[{"GCD", "[", RowBox[{ RowBox[{"e", "-", "1"}], ",", RowBox[{"q", "-", "1"}]}], "]"}], "+", "1"}], ")"}]}]}], "Input", CellChangeTimes->{{3.6573418845858107`*^9, 3.6573419166590557`*^9}}, Background->RGBColor[0.87, 0.94, 1]], Cell[TextData[{ "Since p - 1, q - 1, e - 1 are all even, the number of unconcealed messages \ for any modulus m is ", StyleBox["at least 9", FontWeight->"Bold"], ". In practice, the encryption exponent e is small, whereas p and q are \ quite large, so the number of unconcealed messages will be very small \ compared to the total number of possible messages." }], "Text", CellChangeTimes->{{3.657341934132979*^9, 3.657341982311552*^9}, { 3.657342030238326*^9, 3.6573421250392857`*^9}, {3.702735737206365*^9, 3.7027357438616333`*^9}}, TextJustification->1.] }, Open ]], Cell[CellGroupData[{ Cell["Symmetric vs Asymmetric key Cryptography", "Section", CellChangeTimes->{{3.625241613975398*^9, 3.62524162859831*^9}, 3.702699051403493*^9}], Cell[CellGroupData[{ Cell["Symmetric Key Cryptography", "Subsection", CellChangeTimes->{{3.625241661172598*^9, 3.625241667724595*^9}}], Cell[CellGroupData[{ Cell["same key used for encryption/decryption", "Item", CellChangeTimes->{{3.6252416795564947`*^9, 3.625241694302442*^9}}], Cell["fast encryption/decryption", "Item", CellChangeTimes->{{3.6252416795564947`*^9, 3.6252417031186543`*^9}}], Cell["key exchange - a big problem!", "Item", CellChangeTimes->{{3.6252416795564947`*^9, 3.6252417192633953`*^9}}], Cell["\<\ used mainly for encryption/decryption, not so much for digital signatures\ \>", "Item", CellChangeTimes->{{3.6252416795564947`*^9, 3.625241742744972*^9}, 3.7026989866049967`*^9}] }, Open ]] }, Open ]], Cell[CellGroupData[{ Cell["Asymmetric Key Cryptography", "Subsection", CellChangeTimes->{{3.625241754528907*^9, 3.625241763481057*^9}}], Cell[CellGroupData[{ Cell["\<\ one key (public) used for encryption, another key (private) used for \ decryption\ \>", "Item", CellChangeTimes->{{3.625241785493659*^9, 3.6252418088658133`*^9}}], Cell["slower encryption/decryption", "Item", CellChangeTimes->{{3.625241785493659*^9, 3.625241819249476*^9}}], Cell["key exchange - no problem at all!", "Item", CellChangeTimes->{{3.625241785493659*^9, 3.6252418349515133`*^9}}], Cell["\<\ can be used for encryption/decryption, as well as for digital signatures\ \>", "Item", CellChangeTimes->{{3.625241785493659*^9, 3.625241862333808*^9}, 3.7026989898393917`*^9}] }, Open ]] }, Open ]] }, Open ]], Cell[CellGroupData[{ Cell["\<\ SSL (Secure Sockets Layer), TLS (Transport Layer Security) Handshake Protocol\ \>", "Section", CellChangeTimes->{{3.625239795885623*^9, 3.6252398166125727`*^9}, { 3.657343953328692*^9, 3.65734400075702*^9}, {3.657344073061174*^9, 3.657344076020822*^9}, {3.6573441116752243`*^9, 3.65734411472116*^9}, { 3.6573441738238173`*^9, 3.657344174189653*^9}}], Cell["\<\ Several versions of the protocols are in widespread use in applications such \ as web browsing, email, Internet faxing, Instant messaging, and voice - over \ - IP (VoIP). Major web sites (including Google, YouTube, Facebook and many \ others) use TLS to secure all communications between their servers and web \ browsers.\ \>", "Text", CellChangeTimes->{{3.657344118334159*^9, 3.6573441463836603`*^9}}], Cell[CellGroupData[{ Cell["\<\ provides security and privacy over the Internet by using encryption and \ server/client authentication based on RSA.\ \>", "Item", CellChangeTimes->{{3.625239833324499*^9, 3.6252398887443438`*^9}, { 3.62524033608421*^9, 3.6252403360858517`*^9}, 3.702699058969678*^9}], Cell["\<\ the SSL protocol negotiates encryption keys, as well as authenticates the \ server before data is exchanged by the higher level applications.\ \>", "Item", CellChangeTimes->{{3.625239833324499*^9, 3.6252398887443438`*^9}, { 3.62524033608421*^9, 3.6252403935767927`*^9}}], Cell["\<\ HTTP (Hypertext Transfer Protocol) and FTP (File Transfer Protocol) can be \ layered on top of SSL \ \>", "Item", CellChangeTimes->{{3.625239833324499*^9, 3.625239957671913*^9}, { 3.625240081266739*^9, 3.625240081269257*^9}}], Cell["\[DoubleLongRightArrow] HTTPS (Hypertext Transfer Protocol Secure).", \ "ItemParagraph", CellDingbat->None, CellChangeTimes->{{3.625239833324499*^9, 3.6252400000959578`*^9}, { 3.625240038011713*^9, 3.6252400739639874`*^9}, {3.625240105115883*^9, 3.625240105573299*^9}}], Cell["\<\ HTTPS is especially important over unencrypted wifi networks where anyone on \ the same local network can eavesdrop (packet sniffing) and discover sensitive \ information.\ \>", "ItemParagraph", CellDingbat->None, CellChangeTimes->{{3.625239833324499*^9, 3.6252400000959578`*^9}, { 3.625240038011713*^9, 3.6252400739639874`*^9}, {3.625240105115883*^9, 3.62524021115558*^9}, {3.702699077037767*^9, 3.702699081981812*^9}}], Cell["\<\ HTTPS provides a guarantee that one is communicating with precisely the web \ site/ web server that one intended to communicate with, as well as ensuring \ that the messages between the user and the site cannot be forged by any third \ party.\ \>", "ItemParagraph", CellDingbat->None, CellChangeTimes->{{3.625239833324499*^9, 3.6252400000959578`*^9}, { 3.625240038011713*^9, 3.6252400739639874`*^9}, {3.625240105115883*^9, 3.625240306647496*^9}, 3.702698994777807*^9}] }, Open ]], Cell[CellGroupData[{ Cell["SSL Handshake protocol has two parts", "Subsection", CellChangeTimes->{{3.6252404168559647`*^9, 3.625240430319562*^9}, 3.657347944833695*^9}], Cell[CellGroupData[{ Cell["server authentication (based on RSA).", "ItemNumbered", CellChangeTimes->{{3.625239833324499*^9, 3.625239957671913*^9}, 3.625240081266739*^9, {3.6252405027105618`*^9, 3.6252405319855957`*^9}, 3.7026989974915037`*^9}], Cell["(optional) client authentication (RSA).", "ItemNumbered", CellChangeTimes->{{3.625239833324499*^9, 3.625239957671913*^9}, 3.625240081266739*^9, {3.6252405027105618`*^9, 3.625240549493361*^9}, 3.702698999865756*^9}] }, Open ]] }, Open ]], Cell[CellGroupData[{ Cell["Part 1", "Subsection", CellChangeTimes->{{3.625240562933614*^9, 3.625240565645545*^9}, { 3.625240692510475*^9, 3.6252406944786043`*^9}}], Cell[CellGroupData[{ Cell["\<\ The handshake protocol begins when a client connects to a TLS or SSL-enabled \ server requesting a secure connection and presents a list of supported \ symmetric key ciphers (DES, Triple DES, AES, IDEA, MD5, RC2, RC4, etc.).\ \>", "Item", CellChangeTimes->{{3.625240578505947*^9, 3.6252406648384943`*^9}, { 3.625240708134561*^9, 3.6252407081401253`*^9}, {3.6573442736961327`*^9, 3.6573442886855717`*^9}, {3.657344534591373*^9, 3.657344607774754*^9}}], Cell["\<\ the server, in response to a client\[CloseCurlyQuote]s request, sends its \ digital certificate (server name, trusted certificate authority, public RSA \ key) and its symmetric key cipher method preference. \ \>", "Item", CellChangeTimes->{{3.625240578505947*^9, 3.6252406648384943`*^9}, { 3.625240708134561*^9, 3.6252407081401253`*^9}, {3.6573442736961327`*^9, 3.6573442886855717`*^9}, {3.657344534591373*^9, 3.6573445345934*^9}, { 3.657344613502378*^9, 3.657344615013974*^9}, {3.657344707388146*^9, 3.6573447850499687`*^9}}], Cell["\<\ the client generates a master key k, which he/she/it encrypts with the server\ \[CloseCurlyQuote]s public key using RSA, and transmits the encrypted master \ key to the server.\ \>", "Item", CellChangeTimes->{{3.625240578505947*^9, 3.6252406648384943`*^9}, { 3.625240708134561*^9, 3.62524079636901*^9}}], Cell["\<\ the server decrypts (recovers) the master key k, using his RSA private \ decryption key.\ \>", "Item", CellChangeTimes->{{3.625240578505947*^9, 3.6252406648384943`*^9}, { 3.625240708134561*^9, 3.6252408547509527`*^9}}], Cell["\<\ the server authenticates itself to the client by returning a message signed \ with his private RSA key and encrypted with the symmetric cipher with key k.\ \>", "Item", CellChangeTimes->{{3.625240578505947*^9, 3.6252406648384943`*^9}, { 3.625240708134561*^9, 3.625240919888164*^9}, {3.657344866825974*^9, 3.657344902467103*^9}}], Cell["\<\ subsequent data is encrypted with the symmetric key cipher and with keys \ derived from the master key k.\ \>", "Item", CellChangeTimes->{{3.625240578505947*^9, 3.6252406648384943`*^9}, { 3.625240708134561*^9, 3.6252409710133133`*^9}}] }, Open ]] }, Open ]], Cell[CellGroupData[{ Cell["Part 2 (optional)", "Subsection", CellChangeTimes->{{3.625240985380412*^9, 3.625240991588711*^9}}], Cell[CellGroupData[{ Cell["the server sends a challenge to the client", "Item", CellChangeTimes->{{3.625241003508387*^9, 3.625241021614657*^9}}], Cell["\<\ the client authenticates itself to the server by returning the client\ \[CloseCurlyQuote]s digital signature on the challenge, as well as its \ public-key certificate.\ \>", "Item", CellChangeTimes->{{3.625241003508387*^9, 3.6252410779315777`*^9}}] }, Open ]] }, Open ]] }, Open ]], Cell[CellGroupData[{ Cell["Electronic commerce", "Section", CellChangeTimes->{{3.625241136345224*^9, 3.625241141976615*^9}}], Cell[CellGroupData[{ Cell["IKP (Internet Keyed Payment Protocol) ", "Subsection", CellChangeTimes->{{3.6252411553686943`*^9, 3.625241181552308*^9}}], Cell["\<\ secure payments involving three or more parties; a buyer and a seller \ interact with a third party \[OpenCurlyDoubleQuote]acquirer\ \[CloseCurlyDoubleQuote] such as a credit card system or a bank, to authorize \ transactions.\ \>", "Item", CellChangeTimes->{{3.62524119538456*^9, 3.625241269590238*^9}}] }, Open ]], Cell[CellGroupData[{ Cell["SET (Secure Electronic Transaction Protocol) ", "Subsection", CellChangeTimes->{{3.62524119538456*^9, 3.625241320649701*^9}}], Cell[CellGroupData[{ Cell["\<\ secure, cost effective bankcard transactions over open networks, implemented \ by VISA, MasterCard, etc.\ \>", "Item", CellChangeTimes->{{3.625241342675803*^9, 3.625241386433896*^9}}], Cell["\<\ SET includes protocols for purchasing goods and services electronically, \ requesting authorization of payment and requesting \ \[OpenCurlyDoubleQuote]credentials\[CloseCurlyDoubleQuote] (digital \ certificates) binding public keys to identities.\ \>", "Item", CellChangeTimes->{{3.625241342675803*^9, 3.625241484772361*^9}}], Cell["\<\ SET supports DES for bulk data encryption and RSA for signatures and \ public-key encryption of the DES encryption keys and bankcard numbers.\ \>", "Item", CellChangeTimes->{{3.625241342675803*^9, 3.6252415488275003`*^9}}] }, Open ]] }, Open ]] }, Open ]], Cell[CellGroupData[{ Cell["Digital signatures with RSA", "Section", CellChangeTimes->{{3.6252485986078587`*^9, 3.625248604462529*^9}}], Cell[CellGroupData[{ Cell["Evil Third Party", "Subsection", CellChangeTimes->{{3.62525008489316*^9, 3.6252500891884937`*^9}}], Cell[TextData[{ "Eve wants to impersonate Bob. She writes a message x=\ \[CloseCurlyDoubleQuote]Alice, I don\[CloseCurlyQuote]t like you, Sincerely \ Bob\[CloseCurlyDoubleQuote], Encrypts x using Alice\[CloseCurlyQuote]s public \ key y= ", Cell[BoxData[ FormBox[ RowBox[{ SuperscriptBox["x", "e"], "(", RowBox[{"mod", " ", "m"}], ")"}], TraditionalForm]]], ", and send y to Alice. Alice decrypts the message y using her private key \ d, reads the message, but she has no way of verifying if the sender was \ really Bob." }], "Item", CellChangeTimes->{{3.62524862597162*^9, 3.625248848703128*^9}, { 3.625248905065248*^9, 3.625248912888876*^9}, {3.625248944287578*^9, 3.62524894820816*^9}}] }, Open ]], Cell[CellGroupData[{ Cell["Alice and Bob", "Subsection", CellChangeTimes->{{3.6252501163767767`*^9, 3.6252501597054873`*^9}}], Cell[CellGroupData[{ Cell["\<\ Bob would like to send Alice the following message \ x=\[CloseCurlyDoubleQuote]Alice, I like you, Sincerely Bob\ \[CloseCurlyDoubleQuote]. He would like to send Alice the message x, and also \ affix a digital signature to confirm his identity. This will be called a \ message-signature pair.\ \>", "Item", CellChangeTimes->{{3.62524862597162*^9, 3.625248884308907*^9}, { 3.625248923456868*^9, 3.625249044694343*^9}, {3.625249218115223*^9, 3.625249218118741*^9}, {3.625249397122004*^9, 3.625249402849959*^9}}], Cell[TextData[{ "Alice has her RSA scheme: public modulus ", Cell[BoxData[ FormBox[ RowBox[{ SubscriptBox["m", "A"], "=", RowBox[{ SubscriptBox["p", "A"], "*"}]}], TraditionalForm]]], Cell[BoxData[ FormBox[ SubscriptBox["q", "A"], TraditionalForm]]], ", public encryption key ", Cell[BoxData[ FormBox[ SubscriptBox["e", "A"], TraditionalForm]]], ", private decryption key ", Cell[BoxData[ FormBox[ RowBox[{ SubscriptBox["d", "A"], "."}], TraditionalForm]]] }], "Item", CellChangeTimes->{{3.62524862597162*^9, 3.625248884308907*^9}, { 3.625248923456868*^9, 3.625249044694343*^9}, {3.625249218115223*^9, 3.6252492517712517`*^9}}] }, Open ]] }, Open ]], Cell[CellGroupData[{ Cell["Bob", "Subsection", CellChangeTimes->{{3.625249687831465*^9, 3.625249688326453*^9}}], Cell[CellGroupData[{ Cell[TextData[{ "Bob sets up his own RSA scheme: public modulus ", Cell[BoxData[ FormBox[ RowBox[{ SubscriptBox["m", "B"], "=", RowBox[{ SubscriptBox["p", "B"], "*"}]}], TraditionalForm]]], Cell[BoxData[ FormBox[ SubscriptBox["q", "B"], TraditionalForm]]], ", public encryption key ", Cell[BoxData[ FormBox[ SubscriptBox["e", "B"], TraditionalForm]]], ", private decryption key ", Cell[BoxData[ FormBox[ RowBox[{ SubscriptBox["d", "B"], "."}], TraditionalForm]]] }], "Item", CellChangeTimes->{{3.62524862597162*^9, 3.625248884308907*^9}, { 3.625248923456868*^9, 3.625249196921515*^9}, {3.625249265830204*^9, 3.625249265834886*^9}}], Cell[TextData[{ "Bob signs the message x with his own private RSA key. The signature is \ \[Sigma]=", Cell[BoxData[ FormBox[ RowBox[{ SuperscriptBox["x", StyleBox[ SubscriptBox["d", "B"], FontSize->12]], "mod", " ", SubscriptBox["m", "B"]}], TraditionalForm]]], "." }], "Item", CellChangeTimes->{{3.62524862597162*^9, 3.625248884308907*^9}, { 3.625248923456868*^9, 3.625249196921515*^9}, {3.625249265830204*^9, 3.62524938434408*^9}}], Cell[TextData[{ "Bob encrypts the message-signature pair (x, \[Sigma]) to Alice using Alice\ \[CloseCurlyQuote]s public encryption key ", Cell[BoxData[ FormBox[ SubscriptBox["e", "A"], TraditionalForm]]], ". The result is the encrypted message-signature pair (y, \[Beta]) = (", Cell[BoxData[ FormBox[ RowBox[{ RowBox[{ SuperscriptBox["x", StyleBox[ SubscriptBox["e", "A"], FontSize->12]], "mod", " ", SubscriptBox["m", "A"]}], ",", " ", RowBox[{ SuperscriptBox["\[Sigma]", StyleBox[ SubscriptBox["e", "A"], FontSize->12]], "mod", " ", SubscriptBox["m", "A"]}]}], TraditionalForm]]], ")." }], "Item", CellChangeTimes->{{3.62524862597162*^9, 3.625248884308907*^9}, { 3.625248923456868*^9, 3.625249196921515*^9}, {3.625249265830204*^9, 3.6252494745207443`*^9}, {3.625249532482521*^9, 3.6252496495533333`*^9}}], Cell["\<\ Bob send the encrypted message signature pair (y,\[Beta]) to Alice.\ \>", "Item", CellChangeTimes->{{3.62524862597162*^9, 3.625248884308907*^9}, { 3.625248923456868*^9, 3.625249196921515*^9}, {3.625249265830204*^9, 3.6252494745207443`*^9}, {3.625249532482521*^9, 3.625249678236212*^9}}] }, Open ]] }, Open ]], Cell[CellGroupData[{ Cell["Alice", "Subsection", CellChangeTimes->{{3.62524862597162*^9, 3.625248884308907*^9}, { 3.625248923456868*^9, 3.625249196921515*^9}, {3.625249265830204*^9, 3.6252494745207443`*^9}, {3.625249532482521*^9, 3.625249706942501*^9}}], Cell[CellGroupData[{ Cell["\<\ Alice receives the encrypted message signature pair (y,\[Beta]) to Bob. At \ this stage, she doesn\[CloseCurlyQuote]t know if the sender of the message is \ really Bob.\ \>", "Item", CellChangeTimes->{{3.6252497224635468`*^9, 3.625249761147419*^9}}], Cell[TextData[{ "She decrypts the message using her private decryption exponent ", Cell[BoxData[ FormBox[ SubscriptBox["d", "A"], TraditionalForm]]], ". " }], "Item", CellChangeTimes->{{3.6252497224635468`*^9, 3.62524988582764*^9}}], Cell[TextData[{ "She computes (x, \[Sigma])=(", Cell[BoxData[ FormBox[ RowBox[{ RowBox[{ SuperscriptBox["y", SubscriptBox["d", "A"]], "mod", " ", SubscriptBox["m", "A"]}], ",", " ", RowBox[{ SuperscriptBox["\[Beta]", RowBox[{" ", SubscriptBox["d", "A"]}]], "mod", " ", SubscriptBox["m", "A"]}]}], TraditionalForm]]], ")." }], "ItemParagraph", CellChangeTimes->{{3.6252497224635468`*^9, 3.6252498858233557`*^9}}], Cell[TextData[{ "Alice looks up Bob\[CloseCurlyQuote]s public key ", Cell[BoxData[ FormBox[ SubscriptBox["e", "B"], TraditionalForm]]], " and public modulus ", Cell[BoxData[ FormBox[ RowBox[{ SubscriptBox["m", "B"], ".", " "}], TraditionalForm]]], "She checks Bob\[CloseCurlyQuote]s digital signature by computing z=", Cell[BoxData[ FormBox[ RowBox[{ SuperscriptBox["\[Sigma]", StyleBox[ SubscriptBox["e", "B"], FontSize->12]], "mod", " ", SubscriptBox["m", "B"]}], TraditionalForm]]], ". If z=x, then the message is authentic. If z\[NotEqual]x, then the sender \ of the message is not Bob." }], "Item", CellChangeTimes->{{3.6252497224635468`*^9, 3.6252498066094713`*^9}, { 3.625249897551312*^9, 3.625249960616703*^9}, {3.625249997134821*^9, 3.625250058299923*^9}}] }, Open ]] }, Open ]] }, Closed]] }, WindowSize->{808, 449}, WindowMargins->{{Automatic, 28}, {Automatic, 31}}, PrintingCopies->1, PrintingPageRange->{1, Automatic}, FrontEndVersion->"11.0 for Mac OS X x86 (32-bit, 64-bit Kernel) (September \ 21, 2016)", StyleDefinitions->"Default.nb" ] (* End of Notebook Content *) (* Internal cache information *) (*CellTagsOutline CellTagsIndex->{} *) (*CellTagsIndex CellTagsIndex->{} *) (*NotebookFileOutline Notebook[{ Cell[CellGroupData[{ Cell[580, 22, 116, 1, 64, "Section"], Cell[CellGroupData[{ Cell[721, 27, 182, 2, 30, "Item"], Cell[906, 31, 480, 8, 45, "Item"], Cell[1389, 41, 512, 9, 62, "Item"] }, Open ]], Cell[1916, 53, 401, 10, 91, "Input"], Cell[2320, 65, 364, 7, 70, "Input"], Cell[2687, 74, 519, 13, 91, "Input"], Cell[3209, 89, 414, 8, 70, "Input"], Cell[3626, 99, 891, 21, 46, "Item"] }, Open ]], Cell[CellGroupData[{ Cell[4554, 125, 107, 1, 64, "Section"], Cell[CellGroupData[{ Cell[4686, 130, 415, 9, 30, "Item"], Cell[CellGroupData[{ Cell[5126, 143, 656, 23, 28, "SubitemNumbered"], Cell[5785, 168, 301, 6, 24, "SubitemNumbered"], Cell[6089, 176, 604, 20, 25, "SubitemParagraph"] }, Open ]], Cell[6708, 199, 645, 19, 48, "Item"] }, Open ]] }, Open ]], Cell[CellGroupData[{ Cell[7402, 224, 145, 2, 64, "Section"], Cell[CellGroupData[{ Cell[7572, 230, 169, 4, 30, "Item"], Cell[7744, 236, 269, 5, 45, "Item"], Cell[8016, 243, 243, 5, 30, "Item"], Cell[8262, 250, 173, 4, 30, "Item"] }, Open ]], Cell[8450, 257, 507, 16, 45, "Subsection"], Cell[8960, 275, 484, 16, 38, "Subsection"] }, Open ]], Cell[CellGroupData[{ Cell[9481, 296, 93, 1, 64, "Section"], Cell[CellGroupData[{ Cell[9599, 301, 117, 1, 44, "Subsection"], Cell[CellGroupData[{ Cell[9741, 306, 109, 1, 30, "Item"], Cell[9853, 309, 129, 1, 30, "Item"], Cell[9985, 312, 159, 3, 30, "Item"], Cell[10147, 317, 731, 23, 46, "Item"], Cell[10881, 342, 203, 3, 30, "Item"], Cell[11087, 347, 223, 3, 21, "ItemParagraph"], Cell[11313, 352, 217, 3, 21, "ItemParagraph"], Cell[11533, 357, 224, 3, 30, "Item"], Cell[11760, 362, 275, 3, 21, "ItemParagraph"] }, Open ]] }, Open ]], Cell[CellGroupData[{ Cell[12084, 371, 184, 2, 44, "Subsection"], Cell[CellGroupData[{ Cell[12293, 377, 151, 2, 30, "Item"], Cell[12447, 381, 675, 23, 31, "Item"], Cell[13125, 406, 161, 6, 30, "Item"], Cell[13289, 414, 120, 1, 30, "Item"] }, Open ]] }, Open ]], Cell[CellGroupData[{ Cell[13458, 421, 133, 1, 44, "Subsection"], Cell[CellGroupData[{ Cell[13616, 426, 122, 1, 30, "Item"], Cell[13741, 429, 489, 16, 31, "Item"], Cell[14233, 447, 966, 32, 26, "SubitemParagraph"], Cell[15202, 481, 183, 4, 30, "Item"] }, Open ]] }, Open ]] }, Open ]], Cell[CellGroupData[{ Cell[15446, 492, 158, 5, 64, "Section"], Cell[15607, 499, 716, 15, 70, "Input"], Cell[16326, 516, 717, 15, 70, "Input"], Cell[17046, 533, 161, 3, 30, "Text"], Cell[CellGroupData[{ Cell[17232, 540, 198, 4, 48, "Input"], Cell[17433, 546, 97, 1, 32, "Output"] }, Open ]], Cell[17545, 550, 182, 4, 30, "Text"], Cell[CellGroupData[{ Cell[17752, 558, 324, 8, 48, "Input"], Cell[18079, 568, 155, 3, 32, "Output"] }, Open ]], Cell[18249, 574, 405, 7, 59, "Subsubsection"], Cell[CellGroupData[{ Cell[18679, 585, 301, 4, 29, "Subsubsection"], Cell[CellGroupData[{ Cell[19005, 593, 438, 11, 48, "Input"], Cell[19446, 606, 1461, 36, 75, "Output"] }, Open ]] }, Open ]] }, Open ]], Cell[CellGroupData[{ Cell[20968, 649, 159, 2, 64, "Section"], Cell[CellGroupData[{ Cell[21152, 655, 210, 4, 45, "Item"], Cell[21365, 661, 1538, 43, 101, "Item"] }, Open ]], Cell[CellGroupData[{ Cell[22940, 709, 317, 8, 50, "Input"], Cell[23260, 719, 709, 21, 32, "Output"] }, Open ]], Cell[23984, 743, 1061, 31, 75, "Text"], Cell[25048, 776, 607, 19, 70, "Input"], Cell[25658, 797, 569, 12, 68, "Text"] }, Open ]], Cell[CellGroupData[{ Cell[26264, 814, 150, 2, 64, "Section"], Cell[CellGroupData[{ Cell[26439, 820, 114, 1, 44, "Subsection"], Cell[CellGroupData[{ Cell[26578, 825, 123, 1, 30, "Item"], Cell[26704, 828, 112, 1, 30, "Item"], Cell[26819, 831, 115, 1, 30, "Item"], Cell[26937, 834, 193, 4, 30, "Item"] }, Open ]] }, Open ]], Cell[CellGroupData[{ Cell[27179, 844, 115, 1, 44, "Subsection"], Cell[CellGroupData[{ Cell[27319, 849, 173, 4, 30, "Item"], Cell[27495, 855, 110, 1, 30, "Item"], Cell[27608, 858, 117, 1, 30, "Item"], Cell[27728, 861, 190, 4, 30, "Item"] }, Open ]] }, Open ]] }, Open ]], Cell[CellGroupData[{ Cell[27979, 872, 368, 7, 99, "Section"], Cell[28350, 881, 413, 7, 68, "Text"], Cell[CellGroupData[{ Cell[28788, 892, 281, 5, 45, "Item"], Cell[29072, 899, 283, 5, 45, "Item"], Cell[29358, 906, 238, 5, 30, "Item"], Cell[29599, 913, 282, 5, 21, "ItemParagraph"], Cell[29884, 920, 437, 8, 38, "ItemParagraph"], Cell[30324, 930, 487, 9, 55, "ItemParagraph"] }, Open ]], Cell[CellGroupData[{ Cell[30848, 944, 152, 2, 44, "Subsection"], Cell[CellGroupData[{ Cell[31025, 950, 231, 3, 30, "ItemNumbered"], Cell[31259, 955, 229, 3, 30, "ItemNumbered"] }, Open ]] }, Open ]], Cell[CellGroupData[{ Cell[31537, 964, 145, 2, 44, "Subsection"], Cell[CellGroupData[{ Cell[31707, 970, 466, 7, 62, "Item"], Cell[32176, 979, 547, 9, 45, "Item"], Cell[32726, 990, 316, 6, 45, "Item"], Cell[33045, 998, 231, 5, 30, "Item"], Cell[33279, 1005, 344, 6, 45, "Item"], Cell[33626, 1013, 248, 5, 30, "Item"] }, Open ]] }, Open ]], Cell[CellGroupData[{ Cell[33923, 1024, 105, 1, 44, "Subsection"], Cell[CellGroupData[{ Cell[34053, 1029, 124, 1, 30, "Item"], Cell[34180, 1032, 259, 5, 45, "Item"] }, Open ]] }, Open ]] }, Open ]], Cell[CellGroupData[{ Cell[34500, 1044, 104, 1, 64, "Section"], Cell[CellGroupData[{ Cell[34629, 1049, 128, 1, 44, "Subsection"], Cell[34760, 1052, 315, 6, 45, "Item"] }, Open ]], Cell[CellGroupData[{ Cell[35112, 1063, 132, 1, 44, "Subsection"], Cell[CellGroupData[{ Cell[35269, 1068, 194, 4, 30, "Item"], Cell[35466, 1074, 336, 6, 45, "Item"], Cell[35805, 1082, 233, 4, 45, "Item"] }, Open ]] }, Open ]] }, Open ]], Cell[CellGroupData[{ Cell[36099, 1093, 114, 1, 64, "Section"], Cell[CellGroupData[{ Cell[36238, 1098, 105, 1, 44, "Subsection"], Cell[36346, 1101, 711, 16, 63, "Item"] }, Open ]], Cell[CellGroupData[{ Cell[37094, 1122, 105, 1, 44, "Subsection"], Cell[CellGroupData[{ Cell[37224, 1127, 524, 9, 62, "Item"], Cell[37751, 1138, 678, 23, 48, "Item"] }, Open ]] }, Open ]], Cell[CellGroupData[{ Cell[38478, 1167, 91, 1, 44, "Subsection"], Cell[CellGroupData[{ Cell[38594, 1172, 682, 23, 49, "Item"], Cell[39279, 1197, 474, 15, 33, "Item"], Cell[39756, 1214, 900, 26, 49, "Item"], Cell[40659, 1242, 302, 5, 30, "Item"] }, Open ]] }, Open ]], Cell[CellGroupData[{ Cell[41010, 1253, 238, 3, 44, "Subsection"], Cell[CellGroupData[{ Cell[41273, 1260, 260, 5, 45, "Item"], Cell[41536, 1267, 241, 7, 30, "Item"], Cell[41780, 1276, 473, 16, 23, "ItemParagraph"], Cell[42256, 1294, 824, 24, 66, "Item"] }, Open ]] }, Open ]] }, Closed]] } ] *)