X-Git-Url: https://git.saurik.com/apple/security.git/blobdiff_plain/80e2389990082500d76eb566d4946be3e786c3ef..d8f41ccd20de16f8ebe2ccc84d47bf1cb2b26bbb:/Security/libsecurity_cryptkit/lib/engineNSA127.c diff --git a/Security/libsecurity_cryptkit/lib/engineNSA127.c b/Security/libsecurity_cryptkit/lib/engineNSA127.c new file mode 100644 index 00000000..0e8ea4af --- /dev/null +++ b/Security/libsecurity_cryptkit/lib/engineNSA127.c @@ -0,0 +1,542 @@ +/* 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 */