OSX/libsecurity_cryptkit/lib/CurveParamDocs/FEEDaffine.nb

   1 (***********************************************************************
   2
   3                     Mathematica-Compatible Notebook
   4
   5 This notebook can be used on any computer system with Mathematica 3.0,
   6 MathReader 3.0, or any compatible application. The data for the notebook
   7 starts with the line of stars above.
   8
   9 To get the notebook into a Mathematica-compatible application, do one of
  10 the following:
  11
  12 * Save the data starting with the line of stars above into a file
  13   with a name ending in .nb, then open the file inside the application;
  14
  15 * Copy the data starting with the line of stars above to the
  16   clipboard, then use the Paste menu command inside the application.
  17
  18 Data for notebooks contains only printable 7-bit ASCII and can be
  19 sent directly in email or through ftp in text mode.  Newlines can be
  20 CR, LF or CRLF (Unix, Macintosh or MS-DOS style).
  21
  22 NOTE: If you modify the data for this notebook not in a Mathematica-
  23 compatible application, you must delete the line below containing the
  24 word CacheID, otherwise Mathematica-compatible applications may try to
  25 use invalid cache data.
  26
  27 For more information on notebooks and Mathematica-compatible
  28 applications, contact Wolfram Research:
  29   web: http://www.wolfram.com
  30   email: info@wolfram.com
  31   phone: +1-217-398-0700 (U.S.)
  32
  33 Notebook reader applications are available free of charge from
  34 Wolfram Research.
  35 ***********************************************************************)
  36
  37 (*CacheID: 232*)
  38
  39
  40 (*NotebookFileLineBreakTest
  41 NotebookFileLineBreakTest*)
  42 (*NotebookOptionsPosition[     10630,        213]*)
  43 (*NotebookOutlinePosition[     11308,        238]*)
  44 (*  CellTagsIndexPosition[     11264,        234]*)
  45 (*WindowFrame->Normal*)
  46
  47
  48
  49 Notebook[{
  50 Cell[BoxData[
  51     \(\( (*\n\
  52       Algorithm\ 8.1  .10\
  53         \((Direct - embedding\ ECC\ encryption)\) . \t\t\t\n\ Support\ code\
  54         for\n\ R . \ Crandall\ and\ C . \ Pomerance, \n\
  55       "\<Prime Numbers: a Computational Perspective,\>"\n\ Springer -
  56         Verlag\ 2001. \n\ c . \ 2000\ Perfectly\ Scientific, \
  57       Inc . \n\ All\ Rights\ Reserved . \n\t\n\t20\ Apr\ 2001\ RC\
  58         \((revamped\ for\ simplicity)\)\n\ 10\ Dec\ 2000\ AH\
  59         \((Formatting)\)\n\t14\ Sep\ 2000\ RT\ \((Creation)\)\n*) \n\)\)],
  60   "Input"],
  61
  62 Cell[BoxData[{
  63     \( (*\ CODE\ *) \n
  64     \[IndentingNewLine] (*\
  65       We\ include\ functions\ from\ algorithm\ 7.2  .2\ for\ performing\
  66         elliptic\ \n\(arithmetic . \)\ *) \n
  67     \n (*\ Next, \
  68       a\ function\ that\ negates\ a\ point\ pt\ on\ an\ elliptic\
  69         \(curve . \)\ *) \n
  70     ellneg[pt_]\  := \ Mod[pt\ *\ {1, \(-1\), \ 1}, \ p]; \n
  71     \n (*\ Next, \ elliptic\ subtraction\ pt1 - \(pt2 . \)\ *) \n
  72     \(ellsub[pt1_, \ pt2_]\  := \ elladd[pt1, \ ellneg[pt2]]; \)\n
  73     \n (*\ Next, \ the\ double\ of\ a\ \(point . \)\ *) \),
  74     \(elldouble[pt_]\  := \ elladd[pt, pt]; \n
  75     \n (*\ Next, \ elliptic\ addition\ pt1 + \(pt2 . \)\ *) \n\n\n
  76     \(elladd[pt1_, \ pt2_]\  := \ \n\t
  77       Block[{x1, y1, x2, y2, x3, y3, m}, \n\t\t
  78         If[pt1[\([3]\)]\  == \ 0, \ Return[pt2]]; \n\t\t
  79         If[pt2[\([3]\)]\  == \ 0, \ Return[pt1]]; \n\t\t
  80         x1\  = \ pt1[\([1]\)]; \ y1\  = \ pt1[\([2]\)]; \n\t\t
  81         x2\  = \ pt2[\([1]\)]; \ y2\  = \ pt2[\([2]\)]; \n\t\t
  82         If[x1\  == \ x2, \ \n\t\t\t
  83           If[Mod[y1 + y2, p] == 0, \ Return[{1, 1, 0}]]; \n\t\t\t
  84           m\  = \ Mod[\((3\ x1^2\  + \ a)\)\ *\ PowerMod[2  y1, \(-1\), p], \
  85               p], \n\t\t\t
  86           m\  = \ Mod[\((y2 - y1)\)\ PowerMod[x2 - x1, \(-1\), p], p]\n\t\t];
  87         \n\t\tx3\  = \ Mod[m^2\  - \ x1\  - \ x2, p]; \n\t\t
  88         y3\  = \ Mod[m \((x1 - x3)\)\  - \ y1, \ p]; \n\t\t
  89         Return[{x3, y3, 1}]\n\t]; \)\n\ \
  90     \n (*\ Next, \ elliptic - multiply\ a\ point\ pt\ by\ \(k . \)\ *) \),
  91     \(\n\nelliptic[pt_, \ k_]\  := \ \n\t
  92       Block[{hh, \ kk, pt2, lenh, \ lenk, \ hb, \ kb}, \n\t\t
  93         If[k == 0, \ Return[{1, 1, 0}]]; \n\t\t
  94         hh\  = \ Reverse[IntegerDigits[3  k, 2]]; \n\t\t
  95         kk\  = \ Reverse[IntegerDigits[k, 2]]; \n\t\tpt2\  = \ pt; \n\t\t
  96         lenh\  = \ Length[hh]; \n\t\tlenk\  = \ Length[kk]; \n\t\t
  97         Do[\n\t\t\tpt2\  = \ elldouble[pt2]; \n\t\t\thb\  = \ hh[\([b]\)]; \n
  98           \t\t\tIf[b\  <= \ lenk, \ kb\  = \ kk[\([b]\)], \ kb\  = \ 0]; \n
  99           \t\t\tIf[{hb, kb}\  == \ {1, 0}, \n\t\t\t\t
 100             pt2\  = \ elladd[pt2, \ pt], \n\t\t\t\t
 101             If[{hb, \ kb}\  == \ {0, 1}, \n\t\t\t\t
 102               pt2\  = \ ellsub[pt2, \ pt]]\n\t\t\t]\n\t\t\t, \n
 103           \t\t\t{b, \ lenh - 1, \ 2, \(-1\)}\n\t\t\ ]; \n\tReturn[pt2]\n]\n
 104     \n (*\ Next, \
 105       we\ include\ algorithm\ 2.3  .8\ for\ finding\ square\ roots\ \nmodulo\
 106         a\ prime\ p, \
 107       to\ be\ used\ to\ seek\ out\ valid\ y -
 108         coordinates\ on\ \(curves . \)\ *) \n\),
 109     \(sqrtmod[b_, p_] := \ \n\t
 110       Module[{a, x, c, d, cd, m, t, tst}, \n\ \ \ \t\ta\  = \ Mod[b, p]; \n
 111         \ \ \ \t\tIf[p\  == \ 2, \ Return[a]]; \n\ \ \ \ \t
 112         If[MemberQ[{3, 7}, Mod[p, 8]], \n\ \ \ \ \ \ \t\t
 113           Return[PowerMod[a, \((p + 1)\)/4, p]]\n\ \ \ \ \ \ \t]; \n\ \ \ \ \t
 114         If[Mod[p, 8]\  == \ 5, \n\ \ \ \ \ \ \t\t
 115           x\  = \ PowerMod[a, \((p + 3)\)/8, p]; \n\ \ \ \ \ \ \t\t
 116           c\  = \ Mod[x^2, p]; \n\ \ \ \ \ \ \t\t
 117           If[Not[c\  == \ a], \n\ \ \ \ \ \ \ \ \t\t
 118             Return[Mod[x\ PowerMod[2, \((p - 1)\)/4, p], \ p]]\n
 119             \ \ \ \ \ \ \ \ \t]; \n\ \ \ \ \ \ \t]; \n\ \ \ \ \t\n
 120         \ \ \ \ \t (*\ Here, \ p\  = \ 1\ \(\((mod\ 8)\) . \)\ *) \n
 121         \ \ \ \ \ \ \ttst\  = \ 1; \n\ \ \ \ \ \ \t
 122         While[Not[tst\  == \ \(-1\)], \n\ \ \ \ \ \ \ \ \t
 123           d\  = \ Random[Integer, {1, p}]; \n\ \ \ \ \ \ \ \ \t
 124           tst\  = \ JacobiSymbol[d, p]\n\ \ \ \ \ \ \ \ ]; \n\ \ \ \ \ \ \t
 125         t\  = \ \((p - 1)\)/2; \ s\  = \ 1; \n\ \ \ \ \ \ \t
 126         While[EvenQ[t], \ t\  = \ t/2; \ \(++s\)]; \n\ \ \ \ \ \ \t
 127         ca\  = \ PowerMod[a, t, p]; \n\ \ \ \ \ \ \t
 128         cd\  = \ PowerMod[d, t, p]; \n\ \ \ \ \ \ \tm\  = \ 0; \n
 129         \ \ \ \ \ \ \t
 130         Do[\n\ \ \ \ \ \ \t\ \ \
 131           If[PowerMod[Mod[ca\ PowerMod[cd, \ m, \ p], p], \
 132                 2^\((s - 1 - i)\), \ p]\n\ \ \ \ \ \ \t\ \ \ \t\t == \ p - 1,
 133             \ m\  += \ 2^i]\n\ \ \ \ \ \ \t\ \ \ , {i, 0, s - 1}\n
 134           \ \ \ \ \ \ \t]; \ \ \ \ \ \ \t\ \ \ \ \n\ \ \ \ \ \ \t
 135         Return[Mod[PowerMod[a, \ \((t + 1)\)/2, p]\ PowerMod[cd, \ m/2, p],
 136             p]]; \ \n\t]; \n\n
 137     \n (*\ Now, \
 138       the\ main\ routine . \ Parameters\ are\ given\ for\ 161 -
 139         bit\ prime\ field\n\t\t\tand\ specific\ curve; \n\t\ \
 140       direct\ embedding\ proceeds\ on\ "\<plaintext\>"\ integers\ x\
 141         \((mod\ p)\) . \ \n\ \ \ We\ start\ with\ relevant\ global\
 142         \((and\ public, \ except\ for\ kb)\)\n\ \ \ parameters\n\ *) \n
 143     \[IndentingNewLine]p\  = \
 144       1654338658923174831024422729553880293604080853451; \nA\  = \ \(-152\);
 145     \nB\  = \ 722; \ng\  = \ \(-1\);
 146     \ \  (*\ Quadratic\ nonresidue\ \((mod\ p)\)\ for\ this\ case, \
 147       as\ p\  = \ 3\ \(\((mod\ 4)\) . \)\ *) \n
 148     Atwist\  = \ Mod[A\ \ Mod[h\  = \ g^2, p], \ p]; \n
 149     Btwist\  = \ Mod[B\ \ Mod[h\ g, p], p]; \n
 150     \n (*\ Next, \
 151       create\ public\ point\ P\ of\ prime\ order\ on\ main\ \(curve . \)\ *)
 152       \nx1 = \ 124590448755381588517063157600522073397838354227; \ \ \n
 153     pubpoint\  =
 154       \ {x1, \ sqrtmod[Mod[x1\ Mod[x1^2\  + \ A, p]\  + \ B, p], \ p], 1}; \n
 155     \n (*\ Next, \
 156       create\ public\ point\ P'\ of\ prime\ order\ on\ twist\
 157         \(curve . \)\ *) \n
 158     x1twist\  = \ 480775151193986876474195670157924389403361833567; \n
 159     pubpointtwist\  =
 160       \ {x1twist, \
 161         sqrtmod[Mod[x1twist\ Mod[x1twist^2\  + \ Atwist, p]\  + \ Btwist, p],
 162           \ p], 1}; \n\nkb\  = \ 968525826201321079923232842886222248;
 163     \ \  (*\ Private\ key\ \(K_B . \)\ *) \n\n{a, b}\  = \ {A, B};
 164     \ \  (*\ Prepare\ elliptic\ algebra\ for\ main\ \(curve . \)\ *) \n
 165     pubkey\  = \ \ \ elliptic[pubpoint, \ kb];
 166     \ \ \ \ \ \ \ \  (*\ Public\ key\ \(P_B . \)\ *) \n\
 167     \n{a, b}\  = \ {Atwist, \ Btwist};
 168     \ \ \  (*\ Prepare\ elliptic\ algebra\ for\ twist\ \(curve . \)\ *) \n
 169     pubkeytwist\  = \ \telliptic[pubpointtwist, \ kb];
 170     \ \ \ \ \  (*\ Public\ key\ \(P_B' . \)\ *) \n\ \n\t\t\n
 171     encryptEmbed[x_] := \
 172       Module[{cubic, \ curve, \ X\  = \ x, \ Y, \ pbk, \ X1},
 173         \[IndentingNewLine] (*\ First, \
 174           let\ us\ determine\ which\ curve . \ \n\t\t\ \ \ EITHER\ X\ lies\ in
 175               \ the\ curve\ y^2\  = \ X^3\  + \ A\ X\  + \ B, \n\t\t\ \ \
 176           or\ Xt\  := \
 177             \(g\ X\ lies\ on\ y^2\  = \
 178               Xt^3\  + \ Atwist\ Xt\  + \ Btwist\)\ *) \n\t\t\
 179         cubic\  = \ Mod[X\ Mod[X^2\  + \ A, p]\  + \ B, p]; \n\t\t\
 180         If[JacobiSymbol[cubic, \ p]\  > \ \(-1\), \ \n\t\t\t\ \ \ \ \ \
 181           curve\  = \ 1; \ {a, b}\  = \ {A, B}; \ pbk\  = \ pubkey; \
 182           pbp\  = \ pubpoint, \t\t\t\ \ \ \ \ \ \n\t\t\t\t\ \ \ \ \
 183           curve\  = \ \(-1\); \ {a, b}\  = \ {Atwist, \ Btwist}; \
 184           pbk\  = \ pubkeytwist; \ pbp\  = \ pubpointtwist; \ \n
 185           \t\t\t\t\t\t\t\t\tX\  = \ g\ X; \ \n\t\t\ \ \ \ \ \ \
 186           cubic\  = \ Mod[X\ Mod[X^2\  + \ Atwist, p]\  + \ Btwist, p]\n
 187           \t\t\ \ ]; \n\t\t\ \ Y\  = \ sqrtmod[cubic, \ p]; \ \ \n
 188         \t\t\t (*\
 189           Now\ we\ \(have : \ \n\t\t\t\t\t\t\ \
 190               \((X\  = \ x, Y)\)\ or\ \((X\  = \ g\ x, \ Y)\) lies\ on\ the\
 191                 respective\ curve\); \n\t\t\t\t\ \ \ \
 192           \((a, b)\)\ parameters\ are\ set\ up\ for\ respective\
 193             \(curve . \)\ *) \n\t\t\t\ \n\t\t\t
 194         r\  = \ Random[Integer, \ {2, p - 2}]; \n\t\t\t
 195         u\  = \ elladd[elliptic[pbk, \ r], \ {X, \ Y, 1}]; \n\t\t\t
 196         c\  = \ elliptic[pbp, \ r]; \n
 197         \t\t\ \ {u, \ c, \ curve}\[IndentingNewLine]]; \[IndentingNewLine]\n
 198     decryptEmbed[cipherList_] := \
 199       Module[{u\  = \ cipherList[\([1]\)], \ c\  = \ cipherList[\([2]\)], \
 200           curve\  = \ cipherList[\([3]\)]},
 201         \[IndentingNewLine]If[curve\  == \ 1, \n
 202           \t\t\t\t{a, b}\  = \ {A, \ B}, \n
 203           \t\t\t\ \ {a, b}\  = \ {Atwist, \ Btwist}\n\t\t\ \ \ ]; \n\t\t
 204         X\  = \ \(ellsub[u, \ elliptic[c, \ kb]]\)[\([1]\)]; \n\t\t
 205         If[curve\  != \ 1, \ X\  = \ Mod[X\ PowerMod[g, \(-1\), \ p], p]]; \n
 206         \t\t\tX\[IndentingNewLine]]; \[IndentingNewLine]\n\)}], "Input"],
 207
 208 Cell[BoxData[{
 209     \( (*\ EXAMPLE\ *) \ \n\n
 210     \[IndentingNewLine]ciph\  = \
 211       encryptEmbed[plain\  = \ 1324578918324567]\),
 212     \(decryptEmbed[ciph]\)}], "Input"]
 213 },
 214 FrontEndVersion->"NeXT 3.0",
 215 ScreenRectangle->{{0, 957}, {0, 768}},
 216 WindowToolbars->{},
 217 WindowSize->{762, 676},
 218 WindowMargins->{{Automatic, 45}, {Automatic, 0}},
 219 ShowCellLabel->False
 220 ]
 221
 222
 223 (***********************************************************************
 224 Cached data follows.  If you edit this Notebook file directly, not using
 225 Mathematica, you must remove the line containing CacheID at the top of
 226 the file.  The cache data will then be recreated when you save this file
 227 from within Mathematica.
 228 ***********************************************************************)
 229
 230 (*CellTagsOutline
 231 CellTagsIndex->{}
 232 *)
 233
 234 (*CellTagsIndex
 235 CellTagsIndex->{}
 236 *)
 237
 238 (*NotebookFileOutline
 239 Notebook[{
 240 Cell[1709, 49, 546, 10, 202, "Input"],
 241 Cell[2258, 61, 8194, 144, 2206, "Input"],
 242 Cell[10455, 207, 171, 4, 78, "Input"]
 243 }
 244 ]
 245 *)
 246
 247
 248
 249
 250 (***********************************************************************
 251 End of Mathematica Notebook file.
 252 ***********************************************************************)
 253