-/* 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.
- ***************************************************************************
-
- elliptic.c - Library for Apple-proprietary Fast Elliptic
- Encryption. The algebra in this module ignores elliptic point's
- y-coordinates.
-
- Patent information:
-
- FEE is patented, U.S. Patents #5159632 (1992), #5271061 (1993),
- #5463690 (1994). These patents are implemented
- in various elliptic algebra functions such as
- numer/denom_plus/times(), and in the fact of special
- forms for primes: p = 2^q-k.
-
- Digital signature using fast elliptic addition, in
- U. S. Patent #5581616 (1996), is implemented in the
- signature_compare() function.
-
- FEED (Fast Elliptic Encryption) is patent pending (as of Jan 1998).
- Various functions such as elliptic_add() implement the patent ideas.
-
-
- Modification history since the U.S. Patent:
- -------------------------------------------
- 10/06/98 ap
- Changed to compile with C++.
- 9 Sep 98 at Apple
- cp->curveType optimizations.
- Removed code which handled "unknown" curve orders.
- elliptic() now exported for timing measurements.
- 21 Apr 98 at Apple
- Used inline platform-dependent giant arithmetic.
- 20 Jan 98 at Apple
- feemod now handles PT_MERSENNE, PT_FEE, PT_GENERAL.
- Added calcGiantSizes(), rewrote giantMinBytes(), giantMaxShorts().
- Updated heading comments on FEE curve algebra.
- 11 Jan 98 at Apple
- Microscopic feemod optimization.
- 10 Jan 98 at Apple
- ell_odd, ell_even() Montgomery optimization.
- 09 Jan 98 at Apple
- ell_odd, ell_even() Atkin3 optimization.
- 08 Jan 97 at Apple
- Cleaned up some debugging code; added gsquareTime
- 11 Jun 97 at Apple
- Mods for modg_via_recip(), divg_via_recip() math
- Deleted a lot of obsolete code (previously ifdef'd out)
- Added lesserX1OrderJustify(), x1OrderPlusJustify()
- Added binvg_cp(), avoiding general modg in favor of feemod
- 05 Feb 97 at Apple
- New optimized numer_plus(), denom_double(), and numer_times()
- All calls to borrowGiant() and newGiant have explicit giant size
- 08 Jan 97 at NeXT
- Major mods to accomodate IEEE-style curve parameters.
- New functions feepowermodg() and curveOrderJustify();
- elliptic_add(), elliptic(), signature_compare(), and
- which_curve() completely rewritten.
- 19 Dec 96 at NeXT
- Added mersennePrimes[24..26]
- 08 Aug 96 at NeXT
- Fixed giant leak in elliptic_add()
- 05 Aug 96 at NeXT
- Removed dead code
- 24 Jul 96 at NeXT
- Added ENGINE_127_BITS dependency for use of security engine
- 24 Oct 92 at NeXT
- Modified new_public_from_private()
- Created.
-
-
- FEE curve algebra, Jan 1997.
-
- Curves are:
-
- y^2 = x^3 + c x^2 + a x + b
-
- where useful parameterizations for practical purposes are:
-
- Montgomery: a = 1, b = 0. (The original 1991 FEE system.)
- Weierstrass: c = 0. (The basic IEEE form.)
- Atkin3: c = a = 0.
- Atkin4: c = b = 0.
-
- However, the code is set up to work with any a, b, c.
- The underlying fields F_{p^m} are of odd characteristic,
- with all operations are (mod p). The special FEE-class
- primes p are of the form:
-
- p = 2^q - k = 3 (mod 4)
-
- where k is single-precision. For such p, the mod operations
- are especially fast (asymptotically vanishing time with respect
- to a multiply). Note that the whole system
- works equally well (except for slower execution) for arbitrary
- primes p = 3 (mod 4) of the same bit length (q or q+1).
-
- The elliptic arithmetic now proceeds on the basis of
- five fundamental operations that calculate various
- numerator/denominator parts of the elliptic terms:
-
- numer_double(giant x, giant z, giant res, curveParams *par)
- res := (x^2 - a z^2)^2 - 4 b (2 x + c z) z^3.
-
- numer_plus(giant x1, giant x2, giant res, curveParams *par)
- res = (x1 x2 + a)(x1 + x2) + 2(c x1 x2 + b).
-
- denom_double(giant x, giant z, giant res, curveParams *par)
- res = 4 z (x^3 + c x^2 z + a x z^2 + b z^3).
-
- denom_times(giant x1, giant z1, giant x2, giant z2, giant res,
- curveParams *par)
- res := (x1 z2 - x2 z1)^2
-
- numer_times(giant x1, giant z1, giant x2, giant z2, giant res,
- curveParams *par)
- res := (x1 x2 - a z1 z2)^2 - 4 b(x1 z2 + x2 z1 + c z1 z2) z1 z2
-
- If x(+-) represent the sum and difference x-coordinates
- respectively, then, in pseudocode,
-
- For unequal starting coords:
- x(+) + x(-) = U = 2 numer_plus/denom_times
- x(+) x(-) = V = numer_times/denom_times
-
- and for equal starting coords:
- x(+) = numer_double/denom_double
-
- The elliptic_add() function uses the fact that
-
- x(+) = U/2 + s*Sqrt[U^2/4 - V]
-
- where the sign s = +-1.
-
-*/
-
-#include "ckconfig.h"
-#include <stdio.h>
-#include <stdlib.h>
-#include <string.h>
-#include "platform.h"
-
-#include "giantIntegers.h"
-#include "elliptic.h"
-#include "ellipticProj.h"
-#include "ckutilities.h"
-#include "curveParams.h"
-#include "feeDebug.h"
-#include "ellipticMeasure.h"
-#include "falloc.h"
-#include "giantPortCommon.h"
-
-#if FEE_PROFILE
-
-unsigned numerDoubleTime;
-unsigned numerPlusTime;
-unsigned numerTimesTime;
-unsigned denomDoubleTime;
-unsigned denomTimesTime;
-unsigned ellipticTime;
-unsigned sigCompTime;
-unsigned powerModTime;
-unsigned ellAddTime;
-unsigned whichCurveTime;
-unsigned modgTime;
-unsigned mulgTime;
-unsigned binvauxTime;
-unsigned gsquareTime;
-
-unsigned numMulg;
-unsigned numFeemod;
-unsigned numGsquare;
-unsigned numBorrows;
-
-void clearProfile()
-{
- numerDoubleTime = 0;
- numerPlusTime = 0;
- numerTimesTime = 0;
- denomDoubleTime = 0;
- denomTimesTime = 0;
- ellipticTime = 0;
- sigCompTime = 0;
- powerModTime = 0;
- ellAddTime = 0;
- whichCurveTime = 0;
- modgTime = 0;
- mulgTime = 0;
- binvauxTime = 0;
- gsquareTime = 0;
- numMulg = 0;
- numFeemod = 0;
- numGsquare = 0;
- numBorrows = 0;
-}
-
-#endif // FEE_PROFILE
-
-#if ELL_PROFILE
-unsigned ellOddTime;
-unsigned ellEvenTime;
-unsigned numEllOdds;
-unsigned numEllEvens;
-
-void clearEllProfile()
-{
- ellOddTime = 0;
- ellEvenTime = 0;
- numEllOdds = 0;
- numEllEvens = 0;
-}
-
-#endif /* ELL_PROFILE */
-#if ELLIPTIC_MEASURE
-
-int doEllMeasure; // gather stats on/off */
-int bitsInN;
-int numFeeMods;
-int numMulgs;
-
-void dumpEll()
-{
- printf("\nbitlen(n) : %d\n", bitsInN);
- printf("feemods : %d\n", numFeeMods);
- printf("mulgs : %d\n", numMulgs);
-}
-
-#endif // ELLIPTIC_MEASURE
-
-/********** Globals ********************************/
-
-static void make_base(curveParams *par, giant result); // result = with 2^q-k
-static int keys_inconsistent(key pub1, key pub2);
-/* Return non-zero if pub1, pub2 have inconsistent parameters.
- */
-
-
-static void ell_even(giant x1, giant z1, giant x2, giant z2, curveParams *par);
-static void ell_odd(giant x1, giant z1, giant x2, giant z2, giant xxor,
- giant zor, curveParams *par);
-static void numer_double(giant x, giant z, giant res, curveParams *par);
-static void numer_plus(giant x1, giant x2, giant res, curveParams *par);
-static void denom_double(giant x, giant z, giant res, curveParams *par);
-static void denom_times(giant x1, giant z1, giant x2, giant z2, giant res,
- curveParams *par);
-static void numer_times(giant x1, giant z1, giant x2, giant z2, giant res,
- curveParams *par);
-static void feepowermodg(curveParams *par, giant x, giant n);
-static void curveOrderJustifyWithRecip(giant g, giant curveOrder, giant recip);
-
-/*
- * Completely rewritten in CryptKit-18, 13 Jan 1997, for new IEEE-style
- * curveParameters.
- */
-int which_curve(giant x, curveParams *par)
- /* Returns (+-1) depending on whether x is on curve
- (+-)y^2 = x^3 + c x^2 + a x + b.
- */
-{
- giant t1;
- giant t2;
- giant t3;
- int result;
- PROF_START;
-
- t1 = borrowGiant(par->maxDigits);
- t2 = borrowGiant(par->maxDigits);
- t3 = borrowGiant(par->maxDigits);
-
- /* First, set t2:= x^3 + c x^2 + a x + b. */
- gtog(x, t2); addg(par->c, t2);
- mulg(x, t2); addg(par->a, t2); /* t2 := x^2 + c x + a. */
- feemod(par, t2);
- mulg(x, t2); addg(par->b, t2);
- feemod(par, t2);
- /* Next, test whether t2 is a square. */
- gtog(t2, t1);
- make_base(par, t3); iaddg(1, t3); gshiftright(1, t3); /* t3 = (p+1)/2. */
- feepowermodg(par, t1, t3); /* t1 := t2^((p+1)/2) (mod p). */
- if(gcompg(t1, t2) == 0)
- result = CURVE_PLUS;
- else
- result = CURVE_MINUS;
- returnGiant(t1);
- returnGiant(t2);
- returnGiant(t3);
- PROF_END(whichCurveTime);
- return result;
-}
-
-key new_public(curveParams *cp, int twist) {
- key k;
-
- k = (key) fmalloc(sizeof(keystruct));
- k->cp = cp;
- k->twist = twist;
-
- k->x = newGiant(cp->maxDigits);
- if((twist == CURVE_PLUS) && (cp->curveType == FCT_Weierstrass)) {
- k->y = newGiant(cp->maxDigits);
- }
- else {
- /*
- * no projective algebra. We could optimize and save a few bytes
- * here by setting y to NULL, but that really complicates things
- * in may other places. Best to have a real giant.
- */
- k->y = newGiant(1);
- }
- return(k);
-}
-
-key new_public_with_key(key old_key, curveParams *cp)
-{
- key result;
-
- result = new_public(cp, old_key->twist);
- CKASSERT((old_key->x != NULL) && (old_key->y != NULL));
- CKASSERT((result->x != NULL) && (result->y != NULL));
- gtog(old_key->x, result->x);
- gtog(old_key->y, result->y);
- return result;
-}
-
-void free_key(key pub) {
- if(!pub) {
- return;
- }
- if (pub->x) {
- freeGiant(pub->x);
- }
- if (pub->y) {
- freeGiant(pub->y);
- }
- ffree(pub);
-}
-
-/*
- * Specify private data for key created by new_public().
- * Generates k->x.
- */
-void set_priv_key_giant(key k, giant privGiant)
-{
- curveParams *cp = k->cp;
-
- /* elliptiy multiply of initial public point times private key */
- #if CRYPTKIT_ELL_PROJ_ENABLE
- if((k->twist == CURVE_PLUS) && (cp->curveType == FCT_Weierstrass)) {
- /* projective */
-
- pointProj pt1 = newPointProj(cp->maxDigits);
-
- CKASSERT((cp->y1Plus != NULL) && (!isZero(cp->y1Plus)));
- CKASSERT(k->y != NULL);
-
- /* pt1 := {x1Plus, y1Plus, 1} */
- gtog(cp->x1Plus, pt1->x);
- gtog(cp->y1Plus, pt1->y);
- int_to_giant(1, pt1->z);
-
- /* pt1 := pt1 * privateKey */
- ellMulProjSimple(pt1, privGiant, cp);
-
- /* result back to {k->x, k->y} */
- gtog(pt1->x, k->x);
- gtog(pt1->y, k->y);
- freePointProj(pt1); // FIXME - clear the giants
- }
- else {
- #else
- {
- #endif /* CRYPTKIT_ELL_PROJ_ENABLE */
- /* FEE */
- if(k->twist == CURVE_PLUS) {
- gtog(cp->x1Plus, k->x);
- }
- else {
- gtog(cp->x1Minus, k->x);
- }
- elliptic_simple(k->x, privGiant, k->cp);
- }
-}
-
-int key_equal(key one, key two) {
- if (keys_inconsistent(one, two)) return 0;
- return !gcompg(one->x, two->x);
-}
-
-static void make_base(curveParams *par, giant result)
-/* Jams result with 2^q-k. */
-{
- gtog(par->basePrime, result);
-}
-
-void make_base_prim(curveParams *cp)
-/* Jams cp->basePrime with 2^q-k. Assumes valid maxDigits, q, k. */
-{
- giant tmp = borrowGiant(cp->maxDigits);
-
- CKASSERT(cp->primeType != FPT_General);
- int_to_giant(1, cp->basePrime);
- gshiftleft((int)cp->q, cp->basePrime);
- int_to_giant(cp->k, tmp);
- subg(tmp, cp->basePrime);
- returnGiant(tmp);
-}
-
-static int sequalg(int n, giant g) {
- if((g->sign == 1) && (g->n[0] == n)) return(1);
- return(0);
-}
-
-
-/*
- * Elliptic multiply: x := n * {x, 1}
- */
-void elliptic_simple(giant x, giant n, curveParams *par) {
- giant ztmp = borrowGiant(par->maxDigits);
- giant cur_n = borrowGiant(par->maxDigits);
-
- START_ELL_MEASURE(n);
- int_to_giant(1, ztmp);
- elliptic(x, ztmp, n, par);
- binvg_cp(par, ztmp);
- mulg(ztmp, x);
- feemod(par, x);
- END_ELL_MEASURE;
-
- returnGiant(cur_n);
- returnGiant(ztmp);
-}
-
-/*
- * General elliptic multiply.
- *
- * {xx, zz} := k * {xx, zz}
- */
-void elliptic(giant xx, giant zz, giant k, curveParams *par) {
- int len = bitlen(k);
- int pos = len - 2;
- giant xs;
- giant zs;
- giant xorg;
- giant zorg;
-
- PROF_START;
- if(sequalg(1,k)) return;
- if(sequalg(2,k)) {
- ell_even(xx, zz, xx, zz, par);
- goto out;
- }
- zs = borrowGiant(par->maxDigits);
- xs = borrowGiant(par->maxDigits);
- zorg = borrowGiant(par->maxDigits);
- xorg = borrowGiant(par->maxDigits);
- gtog(xx, xorg); gtog(zz, zorg);
- ell_even(xx, zz, xs, zs, par);
- do {
- if(bitval(k, pos--)) {
- ell_odd(xs, zs, xx, zz, xorg, zorg, par);
- ell_even(xs, zs, xs, zs, par);
- } else {
- ell_odd(xx, zz, xs, zs, xorg, zorg, par);
- ell_even(xx, zz, xx, zz, par);
- }
- } while (pos >= 0); // REC fix 9/23/94
- returnGiant(xs);
- returnGiant(zs);
- returnGiant(xorg);
- returnGiant(zorg);
-out:
- PROF_END(ellipticTime);
-}
-
-/*
- * Completely rewritten in CryptKit-18, 13 Jan 1997, for new IEEE-style
- * curveParameters.
- */
-void elliptic_add(giant x1, giant x2, giant x3, curveParams *par, int s) {
-
- /* Addition algorithm for x3 = x1 + x2 on the curve, with sign ambiguity s.
- From theory, we know that if {x1,1} and {x2,1} are on a curve, then
- their elliptic sum (x1,1} + {x2,1} = {x3,1} must have x3 as one of two
- values:
-
- x3 = U/2 + s*Sqrt[U^2/4 - V]
-
- where sign s = +-1, and U,V are functions of x1,x2. Tho present function
- is called a maximum of twice, to settle which of +- is s. When a call
- is made, it is guaranteed already that x1, x2 both lie on the same curve
- (+- curve); i.e., which curve (+-) is not connected at all with sign s of
- the x3 relation.
- */
-
- giant cur_n;
- giant t1;
- giant t2;
- giant t3;
- giant t4;
- giant t5;
-
- PROF_START;
- cur_n = borrowGiant(par->maxDigits);
- t1 = borrowGiant(par->maxDigits);
- t2 = borrowGiant(par->maxDigits);
- t3 = borrowGiant(par->maxDigits);
- t4 = borrowGiant(par->maxDigits);
- t5 = borrowGiant(par->maxDigits);
-
- if(gcompg(x1, x2)==0) {
- int_to_giant(1, t1);
- numer_double(x1, t1, x3, par);
- denom_double(x1, t1, t2, par);
- binvg_cp(par, t2);
- mulg(t2, x3); feemod(par, x3);
- goto out;
- }
- numer_plus(x1, x2, t1, par);
- int_to_giant(1, t3);
- numer_times(x1, t3, x2, t3, t2, par);
- int_to_giant(1, t4); int_to_giant(1, t5);
- denom_times(x1, t4, x2, t5, t3, par);
- binvg_cp(par, t3);
- mulg(t3, t1); feemod(par, t1); /* t1 := U/2. */
- mulg(t3, t2); feemod(par, t2); /* t2 := V. */
- /* Now x3 will be t1 +- Sqrt[t1^2 - t2]. */
- gtog(t1, t4); gsquare(t4); feemod(par, t4);
- subg(t2, t4);
- make_base(par, cur_n); iaddg(1, cur_n); gshiftright(2, cur_n);
- /* cur_n := (p+1)/4. */
- feepowermodg(par, t4, cur_n); /* t4 := t2^((p+1)/4) (mod p). */
- gtog(t1, x3);
- if(s != SIGN_PLUS) negg(t4);
- addg(t4, x3);
- feemod(par, x3);
-
-out:
- returnGiant(cur_n);
- returnGiant(t1);
- returnGiant(t2);
- returnGiant(t3);
- returnGiant(t4);
- returnGiant(t5);
-
- PROF_END(ellAddTime);
-}
-
-/*
- * Key exchange atom.
- */
-giant make_pad(giant privGiant, key publicKey) {
- curveParams *par = publicKey->cp;
- giant result = newGiant(par->maxDigits);
-
- gtog(publicKey->x, result);
- elliptic_simple(result, privGiant, par);
- return result;
-}
-
-static void ell_even(giant x1, giant z1, giant x2, giant z2, curveParams *par) {
- giant t1;
- giant t2;
- giant t3;
-
- EPROF_START;
-
- t1 = borrowGiant(par->maxDigits);
- t2 = borrowGiant(par->maxDigits);
- t3 = borrowGiant(par->maxDigits);
-
- if(par->curveType == FCT_Montgomery) {
- /* Begin Montgomery OPT: 10 Jan 98 REC. */
- gtog(x1, t1); gsquare(t1); feemod(par, t1); /* t1 := x1^2. */
- gtog(z1, t2); gsquare(t2); feemod(par, t2); /* t2 := z1^2. */
-
- gtog(x1, t3); mulg(z1, t3); feemod(par, t3);
- gtog(t3, z2); mulg(par->c, z2); feemod(par, z2);
- addg(t1, z2); addg(t2, z2); mulg(t3, z2); gshiftleft(2, z2);
- feemod(par, z2); /* z2 := 4 x1 z1 (x1^2 + c x1 z1 + z1^2). */
- gtog(t1, x2); subg(t2, x2); gsquare(x2); feemod(par, x2);
- /* x2 := (x1^2 - z1^2)^2. */
- /* End OPT: 10 Jan 98 REC. */
- }
- else if((par->curveType == FCT_Weierstrass) && isZero(par->a)) {
- /* Begin Atkin3 OPT: 9 Jan 98 REC. */
- gtog(x1, t1);
- gsquare(t1); feemod(par, t1);
- mulg(x1, t1); feemod(par, t1); /* t1 := x^3. */
- gtog(z1, t2);
- gsquare(t2); feemod(par, t2);
- mulg(z1, t2); feemod(par, t2); /* t2 := z1^3 */
- mulg(par->b, t2); feemod(par, t2); /* t2 := b z1^3. */
- gtog(t1, t3); addg(t2, t3); /* t3 := x^3 + b z1^3 */
- mulg(z1, t3); feemod(par, t3); /* t3 *= z1
- * = z1 ( x^3 + b z1^3 ) */
- gshiftleft(2, t3); feemod(par, t3); /* t3 = 4 z1 (x1^3 + b z1^3) */
-
- gshiftleft(3, t2); /* t2 = 8 b z1^3 */
- subg(t2, t1); /* t1 = x^3 - 8 b z1^3 */
- mulg(x1, t1); feemod(par, t1); /* t1 = x1 (x1^3 - 8 b z1^3) */
-
- gtog(t3, z2);
- gtog(t1, x2);
- /* End OPT: 9 Jan 98 REC. */
- }
- else {
- numer_double(x1, z1, t1, par);
- denom_double(x1, z1, t2, par);
- gtog(t1, x2); gtog(t2, z2);
- }
- returnGiant(t1);
- returnGiant(t2);
- returnGiant(t3);
-
- EPROF_END(ellEvenTime);
- EPROF_INCR(numEllEvens);
-
- /*
- printf("ell_even end\n");
- printf(" x1 : "); printGiant(x1);
- printf(" z1 : "); printGiant(z1);
- printf(" x2 : "); printGiant(x2);
- printf(" z2 : "); printGiant(z2);
- */
-}
-
-static void ell_odd(giant x1, giant z1, giant x2, giant z2, giant xxor,
- giant zor, curveParams *par)
-{
-
- giant t1;
- giant t2;
-
- EPROF_START;
- t1 = borrowGiant(par->maxDigits);
- t2 = borrowGiant(par->maxDigits);
-
- if(par->curveType == FCT_Montgomery) {
- /* Begin Montgomery OPT: 10 Jan 98 REC. */
- giant t3 = borrowGiant(par->maxDigits);
- giant t4 = borrowGiant(par->maxDigits);
-
- gtog(x1, t1); addg(z1, t1); /* t1 := x1 + z1. */
- gtog(x2, t2); subg(z2, t2); /* t2 := x2 - z2. */
- gtog(x1, t3); subg(z1, t3); /* t3 := x1 - z1. */
- gtog(x2, t4); addg(z2, t4); /* t4 := x2 + z2. */
- mulg(t2, t1); feemod(par, t1); /* t1 := (x1 + z1)(x2 - z2) */
- mulg(t4, t3); feemod(par, t3); /* t4 := (x2 + z2)(x1 - z1) */
- gtog(t1, z2); subg(t3, z2); /*???gshiftright(1, z2);*/
- /* z2 := ((x1 + z1)(x2 - z2) - x2)/2 */
- gsquare(z2); feemod(par, z2);
- mulg(xxor, z2); feemod(par, z2);
- gtog(t1, x2); addg(t3, x2); /*????gshiftright(1, x2);*/
- gsquare(x2); feemod(par, x2);
- mulg(zor, x2); feemod(par, x2);
-
- returnGiant(t3);
- returnGiant(t4);
- }
- else if((par->curveType == FCT_Weierstrass) && isZero(par->a)) {
- /* Begin Atkin3 OPT: 9 Jan 98 REC. */
-
- giant t3 = borrowGiant(par->maxDigits);
- giant t4 = borrowGiant(par->maxDigits);
-
- gtog(x1, t1); mulg(x2, t1); feemod(par, t1); /* t1 := x1 x2. */
- gtog(z1, t2); mulg(z2, t2); feemod(par, t2); /* t2 := z1 z2. */
- gtog(x1, t3); mulg(z2, t3); feemod(par, t3); /* t3 := x1 z2. */
- gtog(z1, t4); mulg(x2, t4); feemod(par, t4); /* t4 := x2 z1. */
- gtog(t3, z2); subg(t4, z2); gsquare(z2); feemod(par, z2);
- mulg(xxor, z2); feemod(par, z2);
- gtog(t1, x2); gsquare(x2); feemod(par, x2);
- addg(t4, t3); mulg(t2, t3); feemod(par, t3);
- mulg(par->b, t3); feemod(par, t3);
- addg(t3, t3); addg(t3, t3);
- subg(t3, x2); mulg(zor, x2); feemod(par, x2);
-
- returnGiant(t3);
- returnGiant(t4);
- /* End OPT: 9 Jan 98 REC. */
- }
- else {
- numer_times(x1, z1, x2, z2, t1, par);
- mulg(zor, t1); feemod(par, t1);
- denom_times(x1, z1, x2, z2, t2, par);
- mulg(xxor, t2); feemod(par, t2);
-
- gtog(t1, x2); gtog(t2, z2);
- }
-
- returnGiant(t1);
- returnGiant(t2);
-
- EPROF_END(ellOddTime);
- EPROF_INCR(numEllOdds);
-
- /*
- printf("ell_odd end\n");
- printf(" x2 : "); printGiant(x2);
- printf(" z2 : "); printGiant(z2);
- */
-}
-
-/*
- * return codes from keys_inconsistent() and signature_compare(). The actual
- * values are not public; they are defined here for debugging.
- */
-#define CURVE_PARAM_MISMATCH 1
-#define TWIST_PARAM_MISMATCH 2
-#define SIGNATURE_INVALID 3
-
-
-/*
- * Determine whether two keystructs have compatible parameters (i.e., same
- * twist and curveParams). Return 0 if compatible, else non-zero.
- */
-static int keys_inconsistent(key pub1, key pub2){
- if(!curveParamsEquivalent(pub1->cp, pub2->cp)) {
- return CURVE_PARAM_MISMATCH;
- }
- if(pub1->twist != pub2->twist) {
- return TWIST_PARAM_MISMATCH;
- }
- return 0;
-}
-
-int signature_compare(giant p0x, giant p1x, giant p2x, curveParams *par)
-/* Returns non-zero iff p0x cannot be the x-coordinate of the sum of two points whose respective x-coordinates are p1x, p2x. */
-{
- int ret = 0;
- giant t1;
- giant t2;
- giant t3;
- giant t4;
- giant t5;
-
- PROF_START;
-
- t1 = borrowGiant(par->maxDigits);
- t2 = borrowGiant(par->maxDigits);
- t3 = borrowGiant(par->maxDigits);
- t4 = borrowGiant(par->maxDigits);
- t5 = borrowGiant(par->maxDigits);
-
- if(gcompg(p1x, p2x) == 0) {
- int_to_giant(1, t1);
- numer_double(p1x, t1, t2, par);
- denom_double(p1x, t1, t3, par);
- mulg(p0x, t3); subg(t3, t2);
- feemod(par, t2);
- } else {
- numer_plus(p1x, p2x, t1, par);
- gshiftleft(1, t1); feemod(par, t1);
- int_to_giant(1, t3);
- numer_times(p1x, t3, p2x, t3, t2, par);
- int_to_giant(1, t4); int_to_giant(1, t5);
- denom_times(p1x, t4 , p2x, t5, t3, par);
- /* Now we require t3 x0^2 - t1 x0 + t2 == 0. */
- mulg(p0x, t3); feemod(par, t3);
- subg(t1, t3); mulg(p0x, t3);
- feemod(par, t3);
- addg(t3, t2);
- feemod(par, t2);
- }
-
- if(!isZero(t2)) ret = SIGNATURE_INVALID;
- returnGiant(t1);
- returnGiant(t2);
- returnGiant(t3);
- returnGiant(t4);
- returnGiant(t5);
- PROF_END(sigCompTime);
- return(ret);
-}
-
-
-static void numer_double(giant x, giant z, giant res, curveParams *par)
-/* Numerator algebra.
- res := (x^2 - a z^2)^2 - 4 b (2 x + c z) z^3.
- */
-{
- giant t1;
- giant t2;
-
- PROF_START;
- t1 = borrowGiant(par->maxDigits);
- t2 = borrowGiant(par->maxDigits);
-
- gtog(x, t1); gsquare(t1); feemod(par, t1);
- gtog(z, res); gsquare(res); feemod(par, res);
- gtog(res, t2);
- if(!isZero(par->a) ) {
- if(!isone(par->a)) { /* Speedup - REC 17 Jan 1997. */
- mulg(par->a, res); feemod(par, res);
- }
- subg(res, t1); feemod(par, t1);
- }
- gsquare(t1); feemod(par, t1);
- /* t1 := (x^2 - a z^2)^2. */
- if(isZero(par->b)) { /* Speedup - REC 17 Jan 1997. */
- gtog(t1, res);
- goto done;
- }
- if(par->curveType != FCT_Weierstrass) { // i.e., !isZero(par->c)
- // Speedup - REC 17 Jan 1997.
- gtog(z, res); mulg(par->c, res); feemod(par, res);
- } else {
- int_to_giant(0, res);
- }
- addg(x, res); addg(x, res); mulg(par->b, res);
- feemod(par, res);
- gshiftleft(2, res); mulg(z, res); feemod(par, res);
- mulg(t2, res); feemod(par, res);
- negg(res); addg(t1, res);
- feemod(par, res);
-
-done:
- returnGiant(t1);
- returnGiant(t2);
- PROF_END(numerDoubleTime);
-}
-
-static void numer_plus(giant x1, giant x2, giant res, curveParams *par)
-/* Numerator algebra.
- res = (x1 x2 + a)(x1 + x2) + 2(c x1 x2 + b).
- */
-{
- giant t1;
- giant t2;
-
- PROF_START;
- t1 = borrowGiant(par->maxDigits);
- t2 = borrowGiant(par->maxDigits);
-
- gtog(x1, t1); mulg(x2, t1); feemod(par, t1);
- gtog(x2, t2); addg(x1, t2); feemod(par, t2);
- gtog(t1, res);
- if(!isZero(par->a))
- addg(par->a, res);
- mulg(t2, res); feemod(par, res);
- if(par->curveType == FCT_Weierstrass) { // i.e., isZero(par->c)
- int_to_giant(0, t1);
- }
- else {
- mulg(par->c, t1); feemod(par, t1);
- }
- if(!isZero(par->b))
- addg(par->b, t1);
- gshiftleft(1, t1);
- addg(t1, res); feemod(par, res);
-
- returnGiant(t1);
- returnGiant(t2);
- PROF_END(numerPlusTime);
-}
-
-static void denom_double(giant x, giant z, giant res, curveParams *par)
-/* Denominator algebra.
- res = 4 z (x^3 + c x^2 z + a x z^2 + b z^3). */
-{
- giant t1;
- giant t2;
-
- PROF_START;
- t1 = borrowGiant(par->maxDigits);
- t2 = borrowGiant(par->maxDigits);
-
- gtog(x, res); gtog(z, t1);
- if(par->curveType != FCT_Weierstrass) { // i.e., !isZero(par->c)
- gtog(par->c, t2); mulg(t1, t2); feemod(par, t2);
- addg(t2, res);
- }
- mulg(x, res); feemod(par, res);
- gsquare(t1); feemod(par, t1);
- if(!isZero(par->a)) {
- gtog(t1, t2);
- mulg(par->a, t2); feemod(par, t2);
- addg(t2, res);
- }
- mulg(x, res); feemod(par, res);
- if(!isZero(par->b)) {
- mulg(z, t1); feemod(par, t1);
- mulg(par->b, t1); feemod(par, t1);
- addg(t1, res);
- }
- mulg(z, res); gshiftleft(2, res);
- feemod(par, res);
-
- returnGiant(t1);
- returnGiant(t2);
- PROF_END(denomDoubleTime);
-}
-
-
-
-static void denom_times(giant x1, giant z1, giant x2, giant z2, giant res,
- curveParams *par)
-/* Denominator algebra.
- res := (x1 z2 - x2 z1)^2
- */
-{
- giant t1;
-
- PROF_START;
- t1 = borrowGiant(par->maxDigits);
-
- gtog(x1, res); mulg(z2, res); feemod(par, res);
- gtog(z1, t1); mulg(x2, t1); feemod(par, t1);
- subg(t1, res); gsquare(res); feemod(par, res);
-
- returnGiant(t1);
- PROF_END(denomTimesTime);
-}
-
-static void numer_times(giant x1, giant z1, giant x2, giant z2, giant res,
- curveParams *par)
-/* Numerator algebra.
- res := (x1 x2 - a z1 z2)^2 -
- 4 b(x1 z2 + x2 z1 + c z1 z2) z1 z2
- */
-{
- giant t1;
- giant t2;
- giant t3;
- giant t4;
-
- PROF_START;
- t1 = borrowGiant(par->maxDigits);
- t2 = borrowGiant(par->maxDigits);
- t3 = borrowGiant(par->maxDigits);
- t4 = borrowGiant(par->maxDigits);
-
- gtog(x1, t1); mulg(x2, t1); feemod(par, t1);
- gtog(z1, t2); mulg(z2, t2); feemod(par, t2);
- gtog(t1, res);
- if(!isZero(par->a)) {
- gtog(par->a, t3);
- mulg(t2, t3); feemod(par, t3);
- subg(t3, res);
- }
- gsquare(res); feemod(par, res);
- if(isZero(par->b))
- goto done;
- if(par->curveType != FCT_Weierstrass) { // i.e., !isZero(par->c)
- gtog(par->c, t3);
- mulg(t2, t3); feemod(par, t3);
- } else int_to_giant(0, t3);
- gtog(z1, t4); mulg(x2, t4); feemod(par, t4);
- addg(t4, t3);
- gtog(x1, t4); mulg(z2, t4); feemod(par, t4);
- addg(t4, t3); mulg(par->b, t3); feemod(par, t3);
- mulg(t2, t3); gshiftleft(2, t3); feemod(par, t3);
- subg(t3, res);
- feemod(par, res);
-
-done:
- returnGiant(t1);
- returnGiant(t2);
- returnGiant(t3);
- returnGiant(t4);
- PROF_END(numerTimesTime);
-}
-
-/*
- * New, 13 Jan 1997.
- */
-static void feepowermodg(curveParams *par, giant x, giant n)
-/* Power ladder.
- x := x^n (mod 2^q-k)
- */
-{
- int len, pos;
- giant t1;
-
- PROF_START;
- t1 = borrowGiant(par->maxDigits);
- gtog(x, t1);
- int_to_giant(1, x);
- len = bitlen(n);
- pos = 0;
- while(1) {
- if(bitval(n, pos++)) {
- mulg(t1, x);
- feemod(par, x);
- }
- if(pos>=len) break;
- gsquare(t1);
- feemod(par, t1);
- }
- returnGiant(t1);
- PROF_END(powerModTime);
-}
-
-/*
- * Set g := g mod curveOrder;
- * force g to be between 2 and (curveOrder-2), inclusive.
- *
- * Tolerates zero curve orders (indicating "not known").
- */
-
-/*
- * This version is not normally used; it's for when the reciprocal of
- * curveOrder is not known and won't be used again.
- */
-void curveOrderJustify(giant g, giant curveOrder)
-{
- giant recip;
-
- CKASSERT(!isZero(curveOrder));
-
- recip = borrowGiant(2 * abs(g->sign));
- make_recip(curveOrder, recip);
- curveOrderJustifyWithRecip(g, curveOrder, recip);
- returnGiant(recip);
-}
-
-/*
- * New optimzation of curveOrderJustify using known reciprocal, 11 June 1997.
- * g is set to be within [2, curveOrder-2].
- */
-static void curveOrderJustifyWithRecip(giant g, giant curveOrder, giant recip)
-{
- giant tmp;
-
- CKASSERT(!isZero(curveOrder));
-
- modg_via_recip(curveOrder, recip, g); // g now in [0, curveOrder-1]
-
- if(isZero(g)) {
- /*
- * First degenerate case - (g == 0) : set g := 2
- */
- dbgLog(("curveOrderJustify: case 1\n"));
- int_to_giant(2, g);
- return;
- }
- if(isone(g)) {
- /*
- * Second case - (g == 1) : set g := 2
- */
- dbgLog(("curveOrderJustify: case 2\n"));
- int_to_giant(2, g);
- return;
- }
- tmp = borrowGiant(g->capacity);
- gtog(g, tmp);
- iaddg(1, tmp);
- if(gcompg(tmp, curveOrder) == 0) {
- /*
- * Third degenerate case - (g == (curveOrder-1)) : set g -= 1
- */
- dbgLog(("curveOrderJustify: case 3\n"));
- int_to_giant(1, tmp);
- subg(tmp, g);
- }
- returnGiant(tmp);
- return;
-}
-
-#define RECIP_DEBUG 0
-#if RECIP_DEBUG
-#define recipLog(x) printf x
-#else // RECIP_DEBUG
-#define recipLog(x)
-#endif // RECIP_DEBUG
-
-/*
- * curveOrderJustify routines with specific orders, using (and possibly
- * generating) associated reciprocals.
- */
-void lesserX1OrderJustify(giant g, curveParams *cp)
-{
- /*
- * Note this is a pointer to a giant in *cp, not a newly
- * malloc'd giant!
- */
- giant lesserX1Ord = lesserX1Order(cp);
-
- if(isZero(lesserX1Ord)) {
- return;
- }
-
- /*
- * Calculate reciprocal if we don't have it
- */
- if(isZero(cp->lesserX1OrderRecip)) {
- if((lesserX1Ord == cp->x1OrderPlus) &&
- (!isZero(cp->x1OrderPlusRecip))) {
- /*
- * lesserX1Ord happens to be x1OrderPlus, and we
- * have a reciprocal for x1OrderPlus. Copy it over.
- */
- recipLog((
- "x1OrderPlusRecip --> lesserX1OrderRecip\n"));
- gtog(cp->x1OrderPlusRecip, cp->lesserX1OrderRecip);
- }
- else {
- /* Calculate the reciprocal. */
- recipLog(("calc lesserX1OrderRecip\n"));
- make_recip(lesserX1Ord, cp->lesserX1OrderRecip);
- }
- }
- else {
- recipLog(("using existing lesserX1OrderRecip\n"));
- }
- curveOrderJustifyWithRecip(g, lesserX1Ord, cp->lesserX1OrderRecip);
-}
-
-/*
- * Common code used by x1OrderPlusJustify() and x1OrderPlusMod() to generate
- * reciprocal of x1OrderPlus.
- * 8 Sep 1998 - also used by feeSigSign().
- */
-void calcX1OrderPlusRecip(curveParams *cp)
-{
- if(isZero(cp->x1OrderPlusRecip)) {
- if((cp->x1OrderPlus == lesserX1Order(cp)) &&
- (!isZero(cp->lesserX1OrderRecip))) {
- /*
- * lesserX1Order happens to be x1OrderPlus, and we
- * have a reciprocal for lesserX1Order. Copy it over.
- */
- recipLog((
- "lesserX1OrderRecip --> x1OrderPlusRecip\n"));
- gtog(cp->lesserX1OrderRecip, cp->x1OrderPlusRecip);
- }
- else {
- /* Calculate the reciprocal. */
- recipLog(("calc x1OrderPlusRecip\n"));
- make_recip(cp->x1OrderPlus, cp->x1OrderPlusRecip);
- }
- }
- else {
- recipLog(("using existing x1OrderPlusRecip\n"));
- }
-}
-
-void x1OrderPlusJustify(giant g, curveParams *cp)
-{
- CKASSERT(!isZero(cp->x1OrderPlus));
-
- /*
- * Calculate reciprocal if we don't have it
- */
- calcX1OrderPlusRecip(cp);
- curveOrderJustifyWithRecip(g, cp->x1OrderPlus, cp->x1OrderPlusRecip);
-}
-
-/*
- * g := g mod x1OrderPlus. Result may be zero.
- */
-void x1OrderPlusMod(giant g, curveParams *cp)
-{
- CKASSERT(!isZero(cp->x1OrderPlus));
-
- /*
- * Calculate reciprocal if we don't have it
- */
- calcX1OrderPlusRecip(cp);
- modg_via_recip(cp->x1OrderPlus, cp->x1OrderPlusRecip, g);
-}
-
-/*
- * New general-purpose giant mod routine, 8 Jan 97.
- * x := x mod basePrime.
- */
-
-/*
- * This stuff is used to analyze the critical loop behavior inside feemod().
- */
-#define FEEMOD_LOOP_TEST 0
-#if FEEMOD_LOOP_TEST
-/*
- * these two are only examined via debugger
- */
-unsigned feemodCalls = 0; // calls to feemod()
-unsigned feemodMultLoops = 0; // times while() loop runs > once
-#define FEEMOD_LOOP_INCR feemodLoops++
-#define FEEMOD_CALL_INCR feemodCalls++
-#else // FEEMOD_LOOP_TEST
-#define FEEMOD_LOOP_INCR
-#define FEEMOD_CALL_INCR
-#endif // FEEMOD_LOOP_TEST
-
-
-void
-feemod(curveParams *par, giant x)
-{
- int sign, sign2;
- giant t1;
- giant t3;
- giant t4;
- giant t5;
- #if FEEMOD_LOOP_TEST
- unsigned feemodLoops = 0;
- #endif // FEEMOD_LOOP_TEST
-
- FEEMOD_CALL_INCR; // for FEEMOD_LOOP_TEST
- INCR_FEEMODS; // for ellipticMeasure
- PROF_INCR(numFeemod); // for general profiling
-
- switch(par->primeType) {
- case FPT_Mersenne:
- /*
- * Super-optimized Mersenne prime modulus case
- */
- gmersennemod(par->q, x);
- break;
-
- case FPT_FEE:
- /*
- * General 2**q-k case
- */
- sign = (x->sign < 0) ? -1 : 1;
- sign2 = 1;
- x->sign = abs(x->sign);
- if(gcompg(par->basePrime, x) >= 0) {
- goto outFee;
- }
- t1 = borrowGiant(par->maxDigits);
- t3 = borrowGiant(par->maxDigits);
- t4 = borrowGiant(par->maxDigits);
- t5 = borrowGiant(par->maxDigits);
-
- /* Begin OPT: 11 Jan 98 REC. */
- if( ((par->q & (GIANT_BITS_PER_DIGIT - 1)) == 0) &&
- (par->k >= 0) &&
- (par->k < GIANT_DIGIT_MASK)) {
-
- /*
- * Microscopic mod for certain regions of {q,k}
- * parameter space.
- */
- int j, digits, excess, max;
- giantDigit carry;
- giantDigit termHi; // double precision
- giantDigit termLo;
- giantDigit *p1, *p2;
-
- digits = par->q >> GIANT_LOG2_BITS_PER_DIGIT;
- while(bitlen(x) > par->q) {
- excess = (x->sign) - digits;
- max = (excess > digits) ? excess : digits;
- carry = 0;
-
- p1 = &x->n[0];
- p2 = &x->n[digits];
-
- if(excess <= digits) {
- carry = VectorMultiply(par->k,
- p2,
- excess,
- p1);
-
- /* propagate final carry */
- p1 += excess;
- for(j = excess; j < digits; j++) {
-
- /*
- * term = *p1 + carry;
- * *p1++ = term & 65535;
- * carry = term >> 16;
- */
- termLo = giantAddDigits(*p1, carry, &carry);
- *p1++ = termLo;
- }
- } else {
- carry = VectorMultiply(par->k,
- p2,
- digits,
- p1);
- p1 += digits;
- p2 += digits;
- for(j = digits; j < excess; j++) {
- /*
- * term = (par->k)*(*p2++) + carry;
- */
- giantMulDigits(par->k,
- *p2++,
- &termLo,
- &termHi);
- giantAddDouble(&termLo, &termHi, carry);
-
- /*
- * *p1++ = term & 65535;
- * carry = term >> 16;
- */
- *p1++ = termLo;
- carry = termHi;
- }
- }
-
- if(carry > 0) {
- x->n[max] = carry;
- } else {
- while(--max){
- if(x->n[max] != 0) break;
- }
- }
- x->sign = max + 1;
- FEEMOD_LOOP_INCR;
- }
- } else { /* Macroscopic mod for general PT_FEE case. */
- int_to_giant(par->k, t4);
- while(bitlen(x) > par->q) {
- /* Enter fast loop, as in FEE patent. */
- int_to_giant(1, t5);
- gtog(x, t3);
- extractbits(par->q, t3, x);
- while(bitlen(t3) > par->q) {
- gshiftright(par->q, t3);
- extractbits(par->q, t3, t1);
- PAUSE_ELL_MEASURE;
- mulg(t4, t5);
- mulg(t5, t1);
- RESUME_ELL_MEASURE;
- addg(t1, x);
- }
- FEEMOD_LOOP_INCR;
- }
- }
- /* End OPT: 11 Jan 98 REC. */
-
- sign2 = (x->sign < 0)? -1: 1;
- x->sign = abs(x->sign);
- returnGiant(t1);
- returnGiant(t3);
- returnGiant(t4);
- returnGiant(t5);
- outFee:
- if(gcompg(x, par->basePrime) >=0) subg(par->basePrime, x);
- if(sign != sign2) {
- giant t2 = borrowGiant(par->maxDigits);
- gtog(par->basePrime, t2);
- subg(x, t2);
- gtog(t2, x);
- returnGiant(t2);
- }
- break;
- /* end case PT_FEE */
-
- case FPT_General:
- /*
- * Use brute-force modg.
- */
- #if FEE_DEBUG
- if(par->basePrimeRecip == NULL) {
- CKRaise("feemod(PT_GENERAL): No basePrimeRecip!\n");
- }
- #endif /* FEE_DEBUG */
- modg_via_recip(par->basePrime, par->basePrimeRecip, x);
- break;
-
- case FPT_Default:
- /* never appears here */
- CKASSERT(0);
- break;
- } /* switch primeType */
-
- #if FEEMOD_LOOP_TEST
- if(feemodLoops > 1) {
- feemodMultLoops++;
- if(feemodLoops > 2) {
- printf("feemod while loop executed %d times\n", feemodLoops);
- }
- }
- #endif // FEEMOD_LOOP_TEST
-
- return;
-}
-
-/*
- * For a given curveParams, calculate minBytes and maxDigits.
- * Assumes valid primeType, and also a valid basePrime for PT_GENERAL.
- */
-void calcGiantSizes(curveParams *cp)
-{
-
- if(cp->primeType == FPT_General) {
- cp->minBytes = (bitlen(cp->basePrime) + 7) / 8;
- }
- else {
- cp->minBytes = giantMinBytes(cp->q, cp->k);
- }
- cp->maxDigits = giantMaxDigits(cp->minBytes);
-}
-
-unsigned giantMinBytes(unsigned q, int k)
-{
- unsigned kIsNeg = (k < 0) ? 1 : 0;
-
- return (q + 7 + kIsNeg) / 8;
-}
-
-/*
- * min value for "extra" bytes. Derived from the fact that during sig verify,
- * we have to multiply a giant representing a digest - which may be
- * 20 bytes for SHA1 - by a giant of minBytes.
- */
-#define MIN_EXTRA_BYTES 20
-
-unsigned giantMaxDigits(unsigned minBytes)
-{
- unsigned maxBytes = 4 * minBytes;
-
- if((maxBytes - minBytes) < MIN_EXTRA_BYTES) {
- maxBytes = minBytes + MIN_EXTRA_BYTES;
- }
- return BYTES_TO_GIANT_DIGITS(maxBytes);
-}
-
-
-/*
- * Optimized binvg(basePrime, x). Avoids the general modg() in favor of
- * feemod.
- */
-int binvg_cp(curveParams *cp, giant x)
-{
- feemod(cp, x);
- return(binvaux(cp->basePrime, x));
-}
-
-/*
- * Optimized binvg(x1OrderPlus, x). Uses x1OrderPlusMod().
- */
-int binvg_x1OrderPlus(curveParams *cp, giant x)
-{
- x1OrderPlusMod(x, cp);
- return(binvaux(cp->x1OrderPlus, x));
-}
projects / apple / security.git / blobdiff