-/* 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 */
projects / apple / security.git / blobdiff