/* Copyright (c) 1998,2011,2014 Apple Inc. All Rights Reserved. * * NOTICE: USE OF THE MATERIALS ACCOMPANYING THIS NOTICE IS SUBJECT * TO THE TERMS OF THE SIGNED "FAST ELLIPTIC ENCRYPTION (FEE) REFERENCE * SOURCE CODE EVALUATION AGREEMENT" BETWEEN APPLE, INC. AND THE * ORIGINAL LICENSEE THAT OBTAINED THESE MATERIALS FROM APPLE, * INC. ANY USE OF THESE MATERIALS NOT PERMITTED BY SUCH AGREEMENT WILL * EXPOSE YOU TO LIABILITY. *************************************************************************** CONFIDENTIAL CONFIDENTIAL CONFIDENTIAL engineNSA.c Security Engine code, to be compiled prior to software distribution. The code performs the elliptic curve algebra fundamental to the patented FEE system. This Engine is designed to be virtually nonmalleable with respect to key size. This is achieved herein via hard-coding of numerical algorithms with respect to the DEPTH = 4 security level (127 bit Mersenne prime). In meetings between the NSA and NeXT Software, Inc. in 1995-1996, the notion of Security Engine emerged as a means by which one could discourage disassembly of FEE compilations, especially when such disassembly has the sinister goal of modifying encryption depth. DO NOT EVEN THINK ABOUT READING THE SOURCE CODE BELOW UNLESS YOU ARE EXPLICITLY AUTHORIZED TO DO SO BY NeXT OR ITS DESIGNEE. c. 1996, NeXT Software, Inc. All Rights Reserved. */ /* This engine requires no initialization. There is one function to becalled externally, namely elliptic(). */ /* * Revision History * ---------------- * 10/06/98 ap * Changed to compile with C++. * 6 Aug 06 at NeXT * 'a' argument to elliptic() and ell_even() is now a giant. * 25 Jul 96 at NeXT * Wrapped ENGINEmul() with gmersennemod(127,.) to guarantee no * overflow in the hard-coded mul. * Fixed sign calculation bug in ENGINEmul(). * 24 Jul 96 at NeXT * Made conditional on ENGINE_127_BITS. * Made all functions except for elliptic() static. * Renamed some giants function calls via #define. * Deleted use of array of static pseudo-giants. * Cosmetic changes for debuggability. * 19 Jun 96 at NeXT * Created. */ #include "ckconfig.h" #if ENGINE_127_BITS /* * This file is obsolete as of 8 January 1997. */ #error Hey! New curveParam-dependent 127-bit elliptic() needed! #warning Using NSA-approved 127-bit security engine... #include "NSGiantIntegers.h" #define D 65536 #define DM 65535 /* * Size of 127-bit giantstruct n[] array, in shorts. */ #define SHORTCOUNT (8 * 2) #define BORROW_SIZE 0 static void ENGINEmul(giant a, giant b) { int a0,a1,a2,a3,a4,a5,a6,a7, b0,b1,b2,b3,b4,b5,b6,b7; int asign, bsign; int i, j, car; unsigned int prod; unsigned short mult; gmersennemod(127, a); gmersennemod(127, b); asign = a->sign; bsign = b->sign; for(j = abs(asign); j < SHORTCOUNT; j++) a->n[j] = 0; for(j = abs(bsign); j < SHORTCOUNT; j++) b->n[j] = 0; a0 = a->n[0]; a1 = a->n[1]; a2 = a->n[2]; a3 = a->n[3]; a4 = a->n[4]; a5 = a->n[5]; a6 = a->n[6]; a7 = a->n[7]; b0 = b->n[0]; b1 = b->n[1]; b2 = b->n[2]; b3 = b->n[3]; b4 = b->n[4]; b5 = b->n[5]; b6 = b->n[6]; b7 = b->n[7]; for(j = 0; j < SHORTCOUNT; j++) b->n[j] = 0; i = 0; mult = b0; car = 0; prod = a0 * mult + b->n[i] + car; b->n[i++] = prod & DM; car = prod/D; prod = a1 * mult + b->n[i] + car; b->n[i++] = prod & DM; car = prod/D; prod = a2 * mult + b->n[i] + car; b->n[i++] = prod & DM; car = prod/D; prod = a3 * mult + b->n[i] + car; b->n[i++] = prod & DM; car = prod/D; prod = a4 * mult + b->n[i] + car; b->n[i++] = prod & DM; car = prod/D; prod = a5 * mult + b->n[i] + car; b->n[i++] = prod & DM; car = prod/D; prod = a6 * mult + b->n[i] + car; b->n[i++] = prod & DM; car = prod/D; prod = a7 * mult + b->n[i] + car; b->n[i++] = prod & DM; car = prod/D; b->n[i] = car; i = 1; mult = b1; car = 0; prod = a0 * mult + b->n[i] + car; b->n[i++] = prod & DM; car = prod/D; prod = a1 * mult + b->n[i] + car; b->n[i++] = prod & DM; car = prod/D; prod = a2 * mult + b->n[i] + car; b->n[i++] = prod & DM; car = prod/D; prod = a3 * mult + b->n[i] + car; b->n[i++] = prod & DM; car = prod/D; prod = a4 * mult + b->n[i] + car; b->n[i++] = prod & DM; car = prod/D; prod = a5 * mult + b->n[i] + car; b->n[i++] = prod & DM; car = prod/D; prod = a6 * mult + b->n[i] + car; b->n[i++] = prod & DM; car = prod/D; prod = a7 * mult + b->n[i] + car; b->n[i++] = prod & DM; car = prod/D; b->n[i] = car; i = 2; mult = b2; car = 0; prod = a0 * mult + b->n[i] + car; b->n[i++] = prod & DM; car = prod/D; prod = a1 * mult + b->n[i] + car; b->n[i++] = prod & DM; car = prod/D; prod = a2 * mult + b->n[i] + car; b->n[i++] = prod & DM; car = prod/D; prod = a3 * mult + b->n[i] + car; b->n[i++] = prod & DM; car = prod/D; prod = a4 * mult + b->n[i] + car; b->n[i++] = prod & DM; car = prod/D; prod = a5 * mult + b->n[i] + car; b->n[i++] = prod & DM; car = prod/D; prod = a6 * mult + b->n[i] + car; b->n[i++] = prod & DM; car = prod/D; prod = a7 * mult + b->n[i] + car; b->n[i++] = prod & DM; car = prod/D; b->n[i] = car; i = 3; mult = b3; car = 0; prod = a0 * mult + b->n[i] + car; b->n[i++] = prod & DM; car = prod/D; prod = a1 * mult + b->n[i] + car; b->n[i++] = prod & DM; car = prod/D; prod = a2 * mult + b->n[i] + car; b->n[i++] = prod & DM; car = prod/D; prod = a3 * mult + b->n[i] + car; b->n[i++] = prod & DM; car = prod/D; prod = a4 * mult + b->n[i] + car; b->n[i++] = prod & DM; car = prod/D; prod = a5 * mult + b->n[i] + car; b->n[i++] = prod & DM; car = prod/D; prod = a6 * mult + b->n[i] + car; b->n[i++] = prod & DM; car = prod/D; prod = a7 * mult + b->n[i] + car; b->n[i++] = prod & DM; car = prod/D; b->n[i] = car; i = 4; mult = b4; car = 0; prod = a0 * mult + b->n[i] + car; b->n[i++] = prod & DM; car = prod/D; prod = a1 * mult + b->n[i] + car; b->n[i++] = prod & DM; car = prod/D; prod = a2 * mult + b->n[i] + car; b->n[i++] = prod & DM; car = prod/D; prod = a3 * mult + b->n[i] + car; b->n[i++] = prod & DM; car = prod/D; prod = a4 * mult + b->n[i] + car; b->n[i++] = prod & DM; car = prod/D; prod = a5 * mult + b->n[i] + car; b->n[i++] = prod & DM; car = prod/D; prod = a6 * mult + b->n[i] + car; b->n[i++] = prod & DM; car = prod/D; prod = a7 * mult + b->n[i] + car; b->n[i++] = prod & DM; car = prod/D; b->n[i] = car; i = 5; mult = b5; car = 0; prod = a0 * mult + b->n[i] + car; b->n[i++] = prod & DM; car = prod/D; prod = a1 * mult + b->n[i] + car; b->n[i++] = prod & DM; car = prod/D; prod = a2 * mult + b->n[i] + car; b->n[i++] = prod & DM; car = prod/D; prod = a3 * mult + b->n[i] + car; b->n[i++] = prod & DM; car = prod/D; prod = a4 * mult + b->n[i] + car; b->n[i++] = prod & DM; car = prod/D; prod = a5 * mult + b->n[i] + car; b->n[i++] = prod & DM; car = prod/D; prod = a6 * mult + b->n[i] + car; b->n[i++] = prod & DM; car = prod/D; prod = a7 * mult + b->n[i] + car; b->n[i++] = prod & DM; car = prod/D; b->n[i] = car; i = 6; mult = b6; car = 0; prod = a0 * mult + b->n[i] + car; b->n[i++] = prod & DM; car = prod/D; prod = a1 * mult + b->n[i] + car; b->n[i++] = prod & DM; car = prod/D; prod = a2 * mult + b->n[i] + car; b->n[i++] = prod & DM; car = prod/D; prod = a3 * mult + b->n[i] + car; b->n[i++] = prod & DM; car = prod/D; prod = a4 * mult + b->n[i] + car; b->n[i++] = prod & DM; car = prod/D; prod = a5 * mult + b->n[i] + car; b->n[i++] = prod & DM; car = prod/D; prod = a6 * mult + b->n[i] + car; b->n[i++] = prod & DM; car = prod/D; prod = a7 * mult + b->n[i] + car; b->n[i++] = prod & DM; car = prod/D; b->n[i] = car; i = 7; mult = b7; car = 0; prod = a0 * mult + b->n[i] + car; b->n[i++] = prod & DM; car = prod/D; prod = a1 * mult + b->n[i] + car; b->n[i++] = prod & DM; car = prod/D; prod = a2 * mult + b->n[i] + car; b->n[i++] = prod & DM; car = prod/D; prod = a3 * mult + b->n[i] + car; b->n[i++] = prod & DM; car = prod/D; prod = a4 * mult + b->n[i] + car; b->n[i++] = prod & DM; car = prod/D; prod = a5 * mult + b->n[i] + car; b->n[i++] = prod & DM; car = prod/D; prod = a6 * mult + b->n[i] + car; b->n[i++] = prod & DM; car = prod/D; prod = a7 * mult + b->n[i] + car; b->n[i++] = prod & DM; car = prod/D; b->n[i] = car; b->sign = abs(b->sign) + abs(a->sign); for(j = (b->sign)-1; j >= 0; j--) { if(b->n[j] != 0) { break; } } b->sign = j+1; gmersennemod(127,b); } static void ell_even(giant x1, giant z1, giant x2, giant z2, giant a, int q) { giant t1, t2, t3; t1 = borrowGiant(BORROW_SIZE); t2 = borrowGiant(BORROW_SIZE); t3 = borrowGiant(BORROW_SIZE); gtog(x1, t1); gsquare(t1); gmersennemod(q, t1); gtog(z1, t2); gsquare(t2); gmersennemod(q, t2); gtog(x1, t3); ENGINEmul(z1, t3); gtog(t1, x2); subg(t2, x2); gsquare(x2); gmersennemod(q, x2); gtog(a, z2); ENGINEmul(t3, z2); addg(t1, z2); addg(t2, z2); ENGINEmul(t3, z2); gshiftleft(2, z2); gmersennemod(q, z2); returnGiant(t1); returnGiant(t2); returnGiant(t3); } static void ell_odd(giant x1, giant z1, giant x2, giant z2, giant xor, giant zor, int q) { giant t1, t2, t3; t1 = borrowGiant(BORROW_SIZE); t2 = borrowGiant(BORROW_SIZE); t3 = borrowGiant(BORROW_SIZE); gtog(x1, t1); subg(z1, t1); gtog(x2, t2); addg(z2, t2); ENGINEmul(t1, t2); gtog(x1, t1); addg(z1, t1); gtog(x2, t3); subg(z2, t3); ENGINEmul(t3, t1); gtog(t2, x2); addg(t1, x2); gsquare(x2); gmersennemod(q, x2); //? gtog(t2, z2); subg(t1, z2); gsquare(z2); gmersennemod(q, z2); //? ENGINEmul(zor, x2); ENGINEmul(xor, z2); returnGiant(t1); returnGiant(t2); returnGiant(t3); } /* Elliptic multiply. For given curve parameter a and given prime p = 2^q-1, the point (xx,zz) becomes k * (xx,zz), in place. */ void elliptic(giant xx, giant zz, giant k, giant a, int q) { int len = bitlen(k), pos = len-2; giant xs; giant zs; giant xorg; giant zorg; if(scompg(1,k)) return; if(scompg(2,k)) { ell_even(xx, zz, xx, zz, a, q); return; } zs = borrowGiant(BORROW_SIZE); xs = borrowGiant(BORROW_SIZE); zorg = borrowGiant(BORROW_SIZE); xorg = borrowGiant(BORROW_SIZE); gtog(xx, xorg); gtog(zz, zorg); ell_even(xx, zz, xs, zs, a, q); do{ if(bitval(k, pos--)) { ell_odd(xs, zs, xx, zz, xorg, zorg, q); ell_even(xs, zs, xs, zs, a, q); } else { ell_odd(xx, zz, xs, zs, xorg, zorg, q); ell_even(xx, zz, xx, zz, a, q); } } while(pos >=0); returnGiant(xs); returnGiant(zs); returnGiant(xorg); returnGiant(zorg); } #endif /* ENGINE_127_BITS */