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 102static void 103ENGINEmul(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 449static void 450ell_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 473static void 474ell_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 */ 504void 505elliptic(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 */ 543