--- /dev/null
+(***********************************************************************
+
+ Mathematica-Compatible Notebook
+
+This notebook can be used on any computer system with Mathematica 3.0,
+MathReader 3.0, or any compatible application. The data for the notebook
+starts with the line of 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[ 10630, 213]*)
+(*NotebookOutlinePosition[ 11308, 238]*)
+(* CellTagsIndexPosition[ 11264, 234]*)
+(*WindowFrame->Normal*)
+
+
+
+Notebook[{
+Cell[BoxData[
+ \(\( (*\n\
+ Algorithm\ 8.1 .10\
+ \((Direct - embedding\ ECC\ encryption)\) . \t\t\t\n\ Support\ code\
+ for\n\ R . \ Crandall\ and\ C . \ Pomerance, \n\
+ "\<Prime Numbers: a Computational Perspective,\>"\n\ Springer -
+ Verlag\ 2001. \n\ c . \ 2000\ Perfectly\ Scientific, \
+ Inc . \n\ All\ Rights\ Reserved . \n\t\n\t20\ Apr\ 2001\ RC\
+ \((revamped\ for\ simplicity)\)\n\ 10\ Dec\ 2000\ AH\
+ \((Formatting)\)\n\t14\ Sep\ 2000\ RT\ \((Creation)\)\n*) \n\)\)],
+ "Input"],
+
+Cell[BoxData[{
+ \( (*\ CODE\ *) \n
+ \[IndentingNewLine] (*\
+ We\ include\ functions\ from\ algorithm\ 7.2 .2\ for\ performing\
+ elliptic\ \n\(arithmetic . \)\ *) \n
+ \n (*\ Next, \
+ a\ function\ that\ negates\ a\ point\ pt\ on\ an\ elliptic\
+ \(curve . \)\ *) \n
+ ellneg[pt_]\ := \ Mod[pt\ *\ {1, \(-1\), \ 1}, \ p]; \n
+ \n (*\ Next, \ elliptic\ subtraction\ pt1 - \(pt2 . \)\ *) \n
+ \(ellsub[pt1_, \ pt2_]\ := \ elladd[pt1, \ ellneg[pt2]]; \)\n
+ \n (*\ Next, \ the\ double\ of\ a\ \(point . \)\ *) \),
+ \(elldouble[pt_]\ := \ elladd[pt, pt]; \n
+ \n (*\ Next, \ elliptic\ addition\ pt1 + \(pt2 . \)\ *) \n\n\n
+ \(elladd[pt1_, \ pt2_]\ := \ \n\t
+ Block[{x1, y1, x2, y2, x3, y3, m}, \n\t\t
+ If[pt1[\([3]\)]\ == \ 0, \ Return[pt2]]; \n\t\t
+ If[pt2[\([3]\)]\ == \ 0, \ Return[pt1]]; \n\t\t
+ x1\ = \ pt1[\([1]\)]; \ y1\ = \ pt1[\([2]\)]; \n\t\t
+ x2\ = \ pt2[\([1]\)]; \ y2\ = \ pt2[\([2]\)]; \n\t\t
+ If[x1\ == \ x2, \ \n\t\t\t
+ If[Mod[y1 + y2, p] == 0, \ Return[{1, 1, 0}]]; \n\t\t\t
+ m\ = \ Mod[\((3\ x1^2\ + \ a)\)\ *\ PowerMod[2 y1, \(-1\), p], \
+ p], \n\t\t\t
+ m\ = \ Mod[\((y2 - y1)\)\ PowerMod[x2 - x1, \(-1\), p], p]\n\t\t];
+ \n\t\tx3\ = \ Mod[m^2\ - \ x1\ - \ x2, p]; \n\t\t
+ y3\ = \ Mod[m \((x1 - x3)\)\ - \ y1, \ p]; \n\t\t
+ Return[{x3, y3, 1}]\n\t]; \)\n\ \
+ \n (*\ Next, \ elliptic - multiply\ a\ point\ pt\ by\ \(k . \)\ *) \),
+ \(\n\nelliptic[pt_, \ k_]\ := \ \n\t
+ Block[{hh, \ kk, pt2, lenh, \ lenk, \ hb, \ kb}, \n\t\t
+ If[k == 0, \ Return[{1, 1, 0}]]; \n\t\t
+ hh\ = \ Reverse[IntegerDigits[3 k, 2]]; \n\t\t
+ kk\ = \ Reverse[IntegerDigits[k, 2]]; \n\t\tpt2\ = \ pt; \n\t\t
+ lenh\ = \ Length[hh]; \n\t\tlenk\ = \ Length[kk]; \n\t\t
+ Do[\n\t\t\tpt2\ = \ elldouble[pt2]; \n\t\t\thb\ = \ hh[\([b]\)]; \n
+ \t\t\tIf[b\ <= \ lenk, \ kb\ = \ kk[\([b]\)], \ kb\ = \ 0]; \n
+ \t\t\tIf[{hb, kb}\ == \ {1, 0}, \n\t\t\t\t
+ pt2\ = \ elladd[pt2, \ pt], \n\t\t\t\t
+ If[{hb, \ kb}\ == \ {0, 1}, \n\t\t\t\t
+ pt2\ = \ ellsub[pt2, \ pt]]\n\t\t\t]\n\t\t\t, \n
+ \t\t\t{b, \ lenh - 1, \ 2, \(-1\)}\n\t\t\ ]; \n\tReturn[pt2]\n]\n
+ \n (*\ Next, \
+ we\ include\ algorithm\ 2.3 .8\ for\ finding\ square\ roots\ \nmodulo\
+ a\ prime\ p, \
+ to\ be\ used\ to\ seek\ out\ valid\ y -
+ coordinates\ on\ \(curves . \)\ *) \n\),
+ \(sqrtmod[b_, p_] := \ \n\t
+ Module[{a, x, c, d, cd, m, t, tst}, \n\ \ \ \t\ta\ = \ Mod[b, p]; \n
+ \ \ \ \t\tIf[p\ == \ 2, \ Return[a]]; \n\ \ \ \ \t
+ If[MemberQ[{3, 7}, Mod[p, 8]], \n\ \ \ \ \ \ \t\t
+ Return[PowerMod[a, \((p + 1)\)/4, p]]\n\ \ \ \ \ \ \t]; \n\ \ \ \ \t
+ If[Mod[p, 8]\ == \ 5, \n\ \ \ \ \ \ \t\t
+ x\ = \ PowerMod[a, \((p + 3)\)/8, p]; \n\ \ \ \ \ \ \t\t
+ c\ = \ Mod[x^2, p]; \n\ \ \ \ \ \ \t\t
+ If[Not[c\ == \ a], \n\ \ \ \ \ \ \ \ \t\t
+ Return[Mod[x\ PowerMod[2, \((p - 1)\)/4, p], \ p]]\n
+ \ \ \ \ \ \ \ \ \t]; \n\ \ \ \ \ \ \t]; \n\ \ \ \ \t\n
+ \ \ \ \ \t (*\ Here, \ p\ = \ 1\ \(\((mod\ 8)\) . \)\ *) \n
+ \ \ \ \ \ \ \ttst\ = \ 1; \n\ \ \ \ \ \ \t
+ While[Not[tst\ == \ \(-1\)], \n\ \ \ \ \ \ \ \ \t
+ d\ = \ Random[Integer, {1, p}]; \n\ \ \ \ \ \ \ \ \t
+ tst\ = \ JacobiSymbol[d, p]\n\ \ \ \ \ \ \ \ ]; \n\ \ \ \ \ \ \t
+ t\ = \ \((p - 1)\)/2; \ s\ = \ 1; \n\ \ \ \ \ \ \t
+ While[EvenQ[t], \ t\ = \ t/2; \ \(++s\)]; \n\ \ \ \ \ \ \t
+ ca\ = \ PowerMod[a, t, p]; \n\ \ \ \ \ \ \t
+ cd\ = \ PowerMod[d, t, p]; \n\ \ \ \ \ \ \tm\ = \ 0; \n
+ \ \ \ \ \ \ \t
+ Do[\n\ \ \ \ \ \ \t\ \ \
+ If[PowerMod[Mod[ca\ PowerMod[cd, \ m, \ p], p], \
+ 2^\((s - 1 - i)\), \ p]\n\ \ \ \ \ \ \t\ \ \ \t\t == \ p - 1,
+ \ m\ += \ 2^i]\n\ \ \ \ \ \ \t\ \ \ , {i, 0, s - 1}\n
+ \ \ \ \ \ \ \t]; \ \ \ \ \ \ \t\ \ \ \ \n\ \ \ \ \ \ \t
+ Return[Mod[PowerMod[a, \ \((t + 1)\)/2, p]\ PowerMod[cd, \ m/2, p],
+ p]]; \ \n\t]; \n\n
+ \n (*\ Now, \
+ the\ main\ routine . \ Parameters\ are\ given\ for\ 161 -
+ bit\ prime\ field\n\t\t\tand\ specific\ curve; \n\t\ \
+ direct\ embedding\ proceeds\ on\ "\<plaintext\>"\ integers\ x\
+ \((mod\ p)\) . \ \n\ \ \ We\ start\ with\ relevant\ global\
+ \((and\ public, \ except\ for\ kb)\)\n\ \ \ parameters\n\ *) \n
+ \[IndentingNewLine]p\ = \
+ 1654338658923174831024422729553880293604080853451; \nA\ = \ \(-152\);
+ \nB\ = \ 722; \ng\ = \ \(-1\);
+ \ \ (*\ Quadratic\ nonresidue\ \((mod\ p)\)\ for\ this\ case, \
+ as\ p\ = \ 3\ \(\((mod\ 4)\) . \)\ *) \n
+ Atwist\ = \ Mod[A\ \ Mod[h\ = \ g^2, p], \ p]; \n
+ Btwist\ = \ Mod[B\ \ Mod[h\ g, p], p]; \n
+ \n (*\ Next, \
+ create\ public\ point\ P\ of\ prime\ order\ on\ main\ \(curve . \)\ *)
+ \nx1 = \ 124590448755381588517063157600522073397838354227; \ \ \n
+ pubpoint\ =
+ \ {x1, \ sqrtmod[Mod[x1\ Mod[x1^2\ + \ A, p]\ + \ B, p], \ p], 1}; \n
+ \n (*\ Next, \
+ create\ public\ point\ P'\ of\ prime\ order\ on\ twist\
+ \(curve . \)\ *) \n
+ x1twist\ = \ 480775151193986876474195670157924389403361833567; \n
+ pubpointtwist\ =
+ \ {x1twist, \
+ sqrtmod[Mod[x1twist\ Mod[x1twist^2\ + \ Atwist, p]\ + \ Btwist, p],
+ \ p], 1}; \n\nkb\ = \ 968525826201321079923232842886222248;
+ \ \ (*\ Private\ key\ \(K_B . \)\ *) \n\n{a, b}\ = \ {A, B};
+ \ \ (*\ Prepare\ elliptic\ algebra\ for\ main\ \(curve . \)\ *) \n
+ pubkey\ = \ \ \ elliptic[pubpoint, \ kb];
+ \ \ \ \ \ \ \ \ (*\ Public\ key\ \(P_B . \)\ *) \n\
+ \n{a, b}\ = \ {Atwist, \ Btwist};
+ \ \ \ (*\ Prepare\ elliptic\ algebra\ for\ twist\ \(curve . \)\ *) \n
+ pubkeytwist\ = \ \telliptic[pubpointtwist, \ kb];
+ \ \ \ \ \ (*\ Public\ key\ \(P_B' . \)\ *) \n\ \n\t\t\n
+ encryptEmbed[x_] := \
+ Module[{cubic, \ curve, \ X\ = \ x, \ Y, \ pbk, \ X1},
+ \[IndentingNewLine] (*\ First, \
+ let\ us\ determine\ which\ curve . \ \n\t\t\ \ \ EITHER\ X\ lies\ in
+ \ the\ curve\ y^2\ = \ X^3\ + \ A\ X\ + \ B, \n\t\t\ \ \
+ or\ Xt\ := \
+ \(g\ X\ lies\ on\ y^2\ = \
+ Xt^3\ + \ Atwist\ Xt\ + \ Btwist\)\ *) \n\t\t\
+ cubic\ = \ Mod[X\ Mod[X^2\ + \ A, p]\ + \ B, p]; \n\t\t\
+ If[JacobiSymbol[cubic, \ p]\ > \ \(-1\), \ \n\t\t\t\ \ \ \ \ \
+ curve\ = \ 1; \ {a, b}\ = \ {A, B}; \ pbk\ = \ pubkey; \
+ pbp\ = \ pubpoint, \t\t\t\ \ \ \ \ \ \n\t\t\t\t\ \ \ \ \
+ curve\ = \ \(-1\); \ {a, b}\ = \ {Atwist, \ Btwist}; \
+ pbk\ = \ pubkeytwist; \ pbp\ = \ pubpointtwist; \ \n
+ \t\t\t\t\t\t\t\t\tX\ = \ g\ X; \ \n\t\t\ \ \ \ \ \ \
+ cubic\ = \ Mod[X\ Mod[X^2\ + \ Atwist, p]\ + \ Btwist, p]\n
+ \t\t\ \ ]; \n\t\t\ \ Y\ = \ sqrtmod[cubic, \ p]; \ \ \n
+ \t\t\t (*\
+ Now\ we\ \(have : \ \n\t\t\t\t\t\t\ \
+ \((X\ = \ x, Y)\)\ or\ \((X\ = \ g\ x, \ Y)\) lies\ on\ the\
+ respective\ curve\); \n\t\t\t\t\ \ \ \
+ \((a, b)\)\ parameters\ are\ set\ up\ for\ respective\
+ \(curve . \)\ *) \n\t\t\t\ \n\t\t\t
+ r\ = \ Random[Integer, \ {2, p - 2}]; \n\t\t\t
+ u\ = \ elladd[elliptic[pbk, \ r], \ {X, \ Y, 1}]; \n\t\t\t
+ c\ = \ elliptic[pbp, \ r]; \n
+ \t\t\ \ {u, \ c, \ curve}\[IndentingNewLine]]; \[IndentingNewLine]\n
+ decryptEmbed[cipherList_] := \
+ Module[{u\ = \ cipherList[\([1]\)], \ c\ = \ cipherList[\([2]\)], \
+ curve\ = \ cipherList[\([3]\)]},
+ \[IndentingNewLine]If[curve\ == \ 1, \n
+ \t\t\t\t{a, b}\ = \ {A, \ B}, \n
+ \t\t\t\ \ {a, b}\ = \ {Atwist, \ Btwist}\n\t\t\ \ \ ]; \n\t\t
+ X\ = \ \(ellsub[u, \ elliptic[c, \ kb]]\)[\([1]\)]; \n\t\t
+ If[curve\ != \ 1, \ X\ = \ Mod[X\ PowerMod[g, \(-1\), \ p], p]]; \n
+ \t\t\tX\[IndentingNewLine]]; \[IndentingNewLine]\n\)}], "Input"],
+
+Cell[BoxData[{
+ \( (*\ EXAMPLE\ *) \ \n\n
+ \[IndentingNewLine]ciph\ = \
+ encryptEmbed[plain\ = \ 1324578918324567]\),
+ \(decryptEmbed[ciph]\)}], "Input"]
+},
+FrontEndVersion->"NeXT 3.0",
+ScreenRectangle->{{0, 957}, {0, 768}},
+WindowToolbars->{},
+WindowSize->{762, 676},
+WindowMargins->{{Automatic, 45}, {Automatic, 0}},
+ShowCellLabel->False
+]
+
+
+(***********************************************************************
+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[1709, 49, 546, 10, 202, "Input"],
+Cell[2258, 61, 8194, 144, 2206, "Input"],
+Cell[10455, 207, 171, 4, 78, "Input"]
+}
+]
+*)
+
+
+
+
+(***********************************************************************
+End of Mathematica Notebook file.
+***********************************************************************)
+
projects / apple / security.git / blobdiff