libsecurity_cryptkit/lib/engineNSA127.c

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