OSX/libsecurity_cryptkit/lib/engineNSA127.c

   1 /* Copyright (c) 1998,2011,2014 Apple Inc.  All Rights Reserved.
   2  *
   3  * NOTICE: USE OF THE MATERIALS ACCOMPANYING THIS NOTICE IS SUBJECT
   4  * TO THE TERMS OF THE SIGNED "FAST ELLIPTIC ENCRYPTION (FEE) REFERENCE
   5  * SOURCE CODE EVALUATION AGREEMENT" BETWEEN APPLE, INC. AND THE
   6  * ORIGINAL LICENSEE THAT OBTAINED THESE MATERIALS FROM APPLE,
   7  * INC.  ANY USE OF THESE MATERIALS NOT PERMITTED BY SUCH AGREEMENT WILL
   8  * EXPOSE YOU TO LIABILITY.
   9  ***************************************************************************
  10
  11    CONFIDENTIAL   CONFIDENTIAL    CONFIDENTIAL
  12    engineNSA.c
  13
  14    Security Engine code, to be compiled prior to software
  15    distribution.  The code performs the
  16    elliptic curve algebra fundamental to the patented FEE
  17    system.
  18
  19    This Engine is designed to be virtually nonmalleable
  20    with respect to key size.  This is achieved herein
  21    via hard-coding of numerical algorithms with respect to
  22    the DEPTH = 4 security level (127 bit Mersenne prime).
  23
  24    In meetings between the NSA and NeXT Software, Inc. in
  25    1995-1996, the notion of Security Engine emerged as a
  26    means by which one could discourage disassembly of
  27    FEE compilations, especially when such disassembly
  28    has the sinister goal of modifying encryption depth.
  29
  30    DO NOT EVEN THINK ABOUT READING THE SOURCE CODE
  31    BELOW UNLESS YOU ARE EXPLICITLY AUTHORIZED TO DO SO
  32    BY NeXT OR ITS DESIGNEE.
  33
  34    c. 1996, NeXT Software, Inc.
  35    All Rights Reserved.
  36 */
  37
  38 /* This engine requires no initialization.  There is one
  39    function to becalled externally, namely elliptic().
  40  */
  41
  42
  43
  44
  45
  46
  47
  48
  49
  50
  51
  52
  53
  54
  55
  56
  57
  58
  59
  60 /*
  61  * Revision History
  62  * ----------------
  63  * 10/06/98             ap
  64  *      Changed to compile with C++.
  65  *  6 Aug 06 at NeXT
  66  *      'a' argument to elliptic() and ell_even() is now a giant.
  67  * 25 Jul 96 at NeXT
  68  *      Wrapped ENGINEmul() with gmersennemod(127,.) to guarantee no
  69  *              overflow in the hard-coded mul.
  70  *      Fixed sign calculation bug in ENGINEmul().
  71  * 24 Jul 96 at NeXT
  72  *      Made conditional on ENGINE_127_BITS.
  73  *      Made all functions except for elliptic() static.
  74  *      Renamed some giants function calls via #define.
  75  *      Deleted use of array of static pseudo-giants.
  76  *      Cosmetic changes for debuggability.
  77  * 19 Jun 96 at NeXT
  78  *      Created.
  79  */
  80
  81 #include "ckconfig.h"
  82
  83 #if     ENGINE_127_BITS
  84 /*
  85  * This file is obsolete as of 8 January 1997.
  86  */
  87 #error  Hey! New curveParam-dependent 127-bit elliptic() needed!
  88 #warning Using NSA-approved 127-bit security engine...
  89
  90 #include        "NSGiantIntegers.h"
  91
  92 #define D 65536
  93 #define DM 65535
  94
  95 /*
  96  * Size of 127-bit giantstruct n[] array, in shorts.
  97  */
  98 #define SHORTCOUNT              (8 * 2)
  99 #define BORROW_SIZE             0
 100
 101
 102 static void
 103 ENGINEmul(giant a, giant b) {
 104         int a0,a1,a2,a3,a4,a5,a6,a7,
 105        b0,b1,b2,b3,b4,b5,b6,b7;
 106    int asign, bsign;
 107    int   i, j, car;
 108    unsigned int prod;
 109    unsigned short mult;
 110
 111    gmersennemod(127, a);
 112    gmersennemod(127, b);
 113    asign = a->sign;
 114    bsign = b->sign;
 115
 116    for(j = abs(asign); j < SHORTCOUNT; j++) a->n[j] = 0;
 117    for(j = abs(bsign); j < SHORTCOUNT; j++) b->n[j] = 0;
 118         a0 = a->n[0];
 119         a1 = a->n[1];
 120         a2 = a->n[2];
 121         a3 = a->n[3];
 122         a4 = a->n[4];
 123         a5 = a->n[5];
 124         a6 = a->n[6];
 125         a7 = a->n[7];
 126         b0 = b->n[0];
 127         b1 = b->n[1];
 128         b2 = b->n[2];
 129         b3 = b->n[3];
 130         b4 = b->n[4];
 131         b5 = b->n[5];
 132         b6 = b->n[6];
 133         b7 = b->n[7];
 134    for(j = 0; j < SHORTCOUNT; j++) b->n[j] = 0;
 135
 136    i = 0;
 137    mult = b0;
 138    car = 0;
 139
 140       prod = a0 * mult + b->n[i] + car;
 141       b->n[i++] = prod & DM;
 142       car = prod/D;
 143
 144       prod = a1 * mult + b->n[i] + car;
 145       b->n[i++] = prod & DM;
 146       car = prod/D;
 147
 148       prod = a2 * mult + b->n[i] + car;
 149       b->n[i++] = prod & DM;
 150       car = prod/D;
 151
 152       prod = a3 * mult + b->n[i] + car;
 153       b->n[i++] = prod & DM;
 154       car = prod/D;
 155
 156       prod = a4 * mult + b->n[i] + car;
 157       b->n[i++] = prod & DM;
 158       car = prod/D;
 159
 160       prod = a5 * mult + b->n[i] + car;
 161       b->n[i++] = prod & DM;
 162       car = prod/D;
 163
 164       prod = a6 * mult + b->n[i] + car;
 165       b->n[i++] = prod & DM;
 166       car = prod/D;
 167
 168       prod = a7 * mult + b->n[i] + car;
 169       b->n[i++] = prod & DM;
 170       car = prod/D;
 171
 172       b->n[i] = car;
 173
 174    i = 1;
 175    mult = b1;
 176    car = 0;
 177
 178       prod = a0 * mult + b->n[i] + car;
 179       b->n[i++] = prod & DM;
 180       car = prod/D;
 181
 182       prod = a1 * mult + b->n[i] + car;
 183       b->n[i++] = prod & DM;
 184       car = prod/D;
 185
 186       prod = a2 * mult + b->n[i] + car;
 187       b->n[i++] = prod & DM;
 188       car = prod/D;
 189
 190       prod = a3 * mult + b->n[i] + car;
 191       b->n[i++] = prod & DM;
 192       car = prod/D;
 193
 194       prod = a4 * mult + b->n[i] + car;
 195       b->n[i++] = prod & DM;
 196       car = prod/D;
 197
 198       prod = a5 * mult + b->n[i] + car;
 199       b->n[i++] = prod & DM;
 200       car = prod/D;
 201
 202       prod = a6 * mult + b->n[i] + car;
 203       b->n[i++] = prod & DM;
 204       car = prod/D;
 205
 206       prod = a7 * mult + b->n[i] + car;
 207       b->n[i++] = prod & DM;
 208       car = prod/D;
 209
 210       b->n[i] = car;
 211
 212    i = 2;
 213    mult = b2;
 214    car = 0;
 215
 216       prod = a0 * mult + b->n[i] + car;
 217       b->n[i++] = prod & DM;
 218       car = prod/D;
 219
 220       prod = a1 * mult + b->n[i] + car;
 221       b->n[i++] = prod & DM;
 222       car = prod/D;
 223
 224       prod = a2 * mult + b->n[i] + car;
 225       b->n[i++] = prod & DM;
 226       car = prod/D;
 227
 228       prod = a3 * mult + b->n[i] + car;
 229       b->n[i++] = prod & DM;
 230       car = prod/D;
 231
 232       prod = a4 * mult + b->n[i] + car;
 233       b->n[i++] = prod & DM;
 234       car = prod/D;
 235
 236       prod = a5 * mult + b->n[i] + car;
 237       b->n[i++] = prod & DM;
 238       car = prod/D;
 239
 240       prod = a6 * mult + b->n[i] + car;
 241       b->n[i++] = prod & DM;
 242       car = prod/D;
 243
 244       prod = a7 * mult + b->n[i] + car;
 245       b->n[i++] = prod & DM;
 246       car = prod/D;
 247
 248       b->n[i] = car;
 249
 250    i = 3;
 251    mult = b3;
 252    car = 0;
 253
 254       prod = a0 * mult + b->n[i] + car;
 255       b->n[i++] = prod & DM;
 256       car = prod/D;
 257
 258       prod = a1 * mult + b->n[i] + car;
 259       b->n[i++] = prod & DM;
 260       car = prod/D;
 261
 262       prod = a2 * mult + b->n[i] + car;
 263       b->n[i++] = prod & DM;
 264       car = prod/D;
 265
 266       prod = a3 * mult + b->n[i] + car;
 267       b->n[i++] = prod & DM;
 268       car = prod/D;
 269
 270       prod = a4 * mult + b->n[i] + car;
 271       b->n[i++] = prod & DM;
 272       car = prod/D;
 273
 274       prod = a5 * mult + b->n[i] + car;
 275       b->n[i++] = prod & DM;
 276       car = prod/D;
 277
 278       prod = a6 * mult + b->n[i] + car;
 279       b->n[i++] = prod & DM;
 280       car = prod/D;
 281
 282       prod = a7 * mult + b->n[i] + car;
 283       b->n[i++] = prod & DM;
 284       car = prod/D;
 285
 286       b->n[i] = car;
 287
 288    i = 4;
 289    mult = b4;
 290    car = 0;
 291
 292       prod = a0 * mult + b->n[i] + car;
 293       b->n[i++] = prod & DM;
 294       car = prod/D;
 295
 296       prod = a1 * mult + b->n[i] + car;
 297       b->n[i++] = prod & DM;
 298       car = prod/D;
 299
 300       prod = a2 * mult + b->n[i] + car;
 301       b->n[i++] = prod & DM;
 302       car = prod/D;
 303
 304       prod = a3 * mult + b->n[i] + car;
 305       b->n[i++] = prod & DM;
 306       car = prod/D;
 307
 308       prod = a4 * mult + b->n[i] + car;
 309       b->n[i++] = prod & DM;
 310       car = prod/D;
 311
 312       prod = a5 * mult + b->n[i] + car;
 313       b->n[i++] = prod & DM;
 314       car = prod/D;
 315
 316       prod = a6 * mult + b->n[i] + car;
 317       b->n[i++] = prod & DM;
 318       car = prod/D;
 319
 320       prod = a7 * mult + b->n[i] + car;
 321       b->n[i++] = prod & DM;
 322       car = prod/D;
 323
 324       b->n[i] = car;
 325
 326    i = 5;
 327    mult = b5;
 328    car = 0;
 329
 330       prod = a0 * mult + b->n[i] + car;
 331       b->n[i++] = prod & DM;
 332       car = prod/D;
 333
 334       prod = a1 * mult + b->n[i] + car;
 335       b->n[i++] = prod & DM;
 336       car = prod/D;
 337
 338       prod = a2 * mult + b->n[i] + car;
 339       b->n[i++] = prod & DM;
 340       car = prod/D;
 341
 342       prod = a3 * mult + b->n[i] + car;
 343       b->n[i++] = prod & DM;
 344       car = prod/D;
 345
 346       prod = a4 * mult + b->n[i] + car;
 347       b->n[i++] = prod & DM;
 348       car = prod/D;
 349
 350       prod = a5 * mult + b->n[i] + car;
 351       b->n[i++] = prod & DM;
 352       car = prod/D;
 353
 354       prod = a6 * mult + b->n[i] + car;
 355       b->n[i++] = prod & DM;
 356       car = prod/D;
 357
 358       prod = a7 * mult + b->n[i] + car;
 359       b->n[i++] = prod & DM;
 360       car = prod/D;
 361
 362       b->n[i] = car;
 363
 364    i = 6;
 365    mult = b6;
 366    car = 0;
 367
 368       prod = a0 * mult + b->n[i] + car;
 369       b->n[i++] = prod & DM;
 370       car = prod/D;
 371
 372       prod = a1 * mult + b->n[i] + car;
 373       b->n[i++] = prod & DM;
 374       car = prod/D;
 375
 376       prod = a2 * mult + b->n[i] + car;
 377       b->n[i++] = prod & DM;
 378       car = prod/D;
 379
 380       prod = a3 * mult + b->n[i] + car;
 381       b->n[i++] = prod & DM;
 382       car = prod/D;
 383
 384       prod = a4 * mult + b->n[i] + car;
 385       b->n[i++] = prod & DM;
 386       car = prod/D;
 387
 388       prod = a5 * mult + b->n[i] + car;
 389       b->n[i++] = prod & DM;
 390       car = prod/D;
 391
 392       prod = a6 * mult + b->n[i] + car;
 393       b->n[i++] = prod & DM;
 394       car = prod/D;
 395
 396       prod = a7 * mult + b->n[i] + car;
 397       b->n[i++] = prod & DM;
 398       car = prod/D;
 399
 400       b->n[i] = car;
 401
 402    i = 7;
 403    mult = b7;
 404    car = 0;
 405
 406       prod = a0 * mult + b->n[i] + car;
 407       b->n[i++] = prod & DM;
 408       car = prod/D;
 409
 410       prod = a1 * mult + b->n[i] + car;
 411       b->n[i++] = prod & DM;
 412       car = prod/D;
 413
 414       prod = a2 * mult + b->n[i] + car;
 415       b->n[i++] = prod & DM;
 416       car = prod/D;
 417
 418       prod = a3 * mult + b->n[i] + car;
 419       b->n[i++] = prod & DM;
 420       car = prod/D;
 421
 422       prod = a4 * mult + b->n[i] + car;
 423       b->n[i++] = prod & DM;
 424       car = prod/D;
 425
 426       prod = a5 * mult + b->n[i] + car;
 427       b->n[i++] = prod & DM;
 428       car = prod/D;
 429
 430       prod = a6 * mult + b->n[i] + car;
 431       b->n[i++] = prod & DM;
 432       car = prod/D;
 433
 434       prod = a7 * mult + b->n[i] + car;
 435       b->n[i++] = prod & DM;
 436       car = prod/D;
 437
 438       b->n[i] = car;
 439       b->sign = abs(b->sign) + abs(a->sign);
 440       for(j = (b->sign)-1; j >= 0; j--) {
 441                                 if(b->n[j] != 0) {
 442                 break;
 443             }
 444       }
 445       b->sign = j+1;
 446       gmersennemod(127,b);
 447 }
 448
 449 static void
 450 ell_even(giant x1, giant z1, giant x2, giant z2, giant a, int q)
 451 {
 452         giant t1, t2, t3;
 453
 454         t1 = borrowGiant(BORROW_SIZE);
 455         t2 = borrowGiant(BORROW_SIZE);
 456         t3 = borrowGiant(BORROW_SIZE);
 457
 458         gtog(x1, t1); gsquare(t1); gmersennemod(q, t1);
 459         gtog(z1, t2); gsquare(t2); gmersennemod(q, t2);
 460         gtog(x1, t3); ENGINEmul(z1, t3);
 461         gtog(t1, x2); subg(t2, x2); gsquare(x2); gmersennemod(q, x2);
 462         gtog(a, z2);
 463         ENGINEmul(t3, z2);
 464         addg(t1, z2); addg(t2, z2); ENGINEmul(t3, z2);
 465         gshiftleft(2, z2);
 466         gmersennemod(q, z2);
 467
 468         returnGiant(t1);
 469         returnGiant(t2);
 470         returnGiant(t3);
 471 }
 472
 473 static void
 474 ell_odd(giant x1, giant z1, giant x2, giant z2, giant xor, giant zor, int q)
 475 {
 476         giant t1, t2, t3;
 477
 478         t1 = borrowGiant(BORROW_SIZE);
 479         t2 = borrowGiant(BORROW_SIZE);
 480         t3 = borrowGiant(BORROW_SIZE);
 481
 482         gtog(x1, t1); subg(z1, t1);
 483         gtog(x2, t2); addg(z2, t2);
 484         ENGINEmul(t1, t2);
 485         gtog(x1, t1); addg(z1, t1);
 486         gtog(x2, t3); subg(z2, t3);
 487         ENGINEmul(t3, t1);
 488         gtog(t2, x2); addg(t1, x2);
 489         gsquare(x2);  gmersennemod(q, x2); //?
 490         gtog(t2, z2); subg(t1, z2);
 491         gsquare(z2);  gmersennemod(q, z2); //?
 492         ENGINEmul(zor, x2);
 493         ENGINEmul(xor, z2);
 494
 495         returnGiant(t1);
 496         returnGiant(t2);
 497         returnGiant(t3);
 498 }
 499
 500 /* Elliptic multiply.
 501    For given curve parameter a and given prime p = 2^q-1,
 502    the point (xx,zz) becomes k * (xx,zz), in place.
 503  */
 504 void
 505 elliptic(giant xx, giant zz, giant k, giant a, int q)
 506 {
 507         int len = bitlen(k), pos = len-2;
 508         giant xs;
 509         giant zs;
 510         giant xorg;
 511         giant zorg;
 512
 513         if(scompg(1,k)) return;
 514         if(scompg(2,k)) {
 515                 ell_even(xx, zz, xx, zz, a, q);
 516                 return;
 517         }
 518
 519         zs = borrowGiant(BORROW_SIZE);
 520         xs = borrowGiant(BORROW_SIZE);
 521         zorg = borrowGiant(BORROW_SIZE);
 522         xorg = borrowGiant(BORROW_SIZE);
 523
 524         gtog(xx, xorg); gtog(zz, zorg);
 525         ell_even(xx, zz, xs, zs, a, q);
 526         do{
 527            if(bitval(k, pos--)) {
 528                 ell_odd(xs, zs, xx, zz, xorg, zorg, q);
 529                 ell_even(xs, zs, xs, zs, a, q);
 530            } else {
 531                 ell_odd(xx, zz, xs, zs, xorg, zorg, q);
 532                 ell_even(xx, zz, xx, zz, a, q);
 533            }
 534         } while(pos >=0);
 535
 536         returnGiant(xs);
 537         returnGiant(zs);
 538         returnGiant(xorg);
 539         returnGiant(zorg);
 540 }
 541
 542 #endif  /* ENGINE_127_BITS */