Security-57740.51.3.tar.gz

[apple/security.git] / OSX / libsecurity_cryptkit / lib / elliptic.c

/* 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));
}