curveParams.c   [plain text]

/* 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.
 ***************************************************************************
 *
 * curveParams.c - FEE curve parameter static data and functions
 *
 * Revision History
 * ----------------
 * 10/06/98		ap
 *	Changed to compile with C++.
 *  9 Sep 98 at NeXT
 * 	Added y1Plus for IEEE P1363 compliance.
 *    	Added curveParamsInferFields().
 *  08 Apr 98 at Apple
 *	Mods for giantDigit.
 *  20 Jan 98 at Apple
 *	Added primeType, m, basePrimeRecip; added a few PT_GENERAL curves.
 *  19 Jan 1998 at Apple
 *	New curve: q=160, k=57
 *  09 Jan 1998 at Apple
 *	Removed obsolete (i.e., incomplete) curves parameters.
 *  11 Jun 1997 at Apple
 *	Added x1OrderPlusRecip and lesserX1OrderRecip fields
 *	Added curveParamsInitGiants()
 *  9 Jan 1997 at NeXT
 *	Major mods for IEEE-style parameters.
 *  7 Aug 1996 at NeXT
 *	Created.
 */

#include "curveParams.h"
#include "giantIntegers.h"
#include "elliptic.h"
#include "ellipticProj.h"
#include "platform.h"
#include "falloc.h"
#include "feeDebug.h"
#include <stdlib.h>

typedef unsigned short arrayDigit;

static giant arrayToGiant(const arrayDigit *array);

/*
 * Can't declare giants statically; we declare them here via static arrayDigit
 * arrays which contain the 'digits' in base 65536 of a giant
 * used as a curve parameter. First element is sign; next element is
 * l.s. digit; size of each array is abs(sign) + 1. These arrays are
 * converted to a giant via arrayToGiant().
 *
 * Static q and k values, as well as pointers to the arrayDigit arrays
 * associated with the various giants for a given curve, are kept in an
 * array of curveParamsStatic structs; a feeDepth is an index into this
 * array. A curveParamsStatic struct is converted to a curveParams struct in
 * curveParamsForDepth().
 */
typedef struct {
	feePrimeType		primeType;
	feeCurveType		curveType;
	unsigned			q;
	int         		k;
	const arrayDigit	*basePrime;		// FPT_General only
	arrayDigit			m;				// must be 1 for current release
	const arrayDigit	*a;
	const arrayDigit	*b;
	const arrayDigit	*c;
	const arrayDigit	*x1Plus;
	const arrayDigit	*y1Plus;		// optional, currently only used for ECDSA curves
	const arrayDigit	*x1Minus;		// optional, not used for ECDSA curves
	const arrayDigit	*cOrderPlus;
	const arrayDigit	*cOrderMinus;	// optional, not used for ECDSA curves
	const arrayDigit	*x1OrderPlus;
	const arrayDigit	*x1OrderMinus;	// optional, not used for ECDSA curves
	const arrayDigit	*x1OrderPlusRecip;

	/*
	 * A null lesserX1OrderRecip when x1OrderPlusRecip is non-null
	 * means that the two values are identical; in this case, only
	 * one giant is alloc'd in the actual curveParams struct.
	 */
	const arrayDigit 	*lesserX1OrderRecip;
} curveParamsStatic;

/*
 * First some common giant-arrays used in lots of curveGiants.
 */
static const arrayDigit ga_666[]  = {1, 666 };	// a common value for 'c'
static const arrayDigit ga_zero[] = {1, 0   };	// (giant)0
static const arrayDigit ga_one[]  = {1, 1   };	// (giant)1

/*
 * Here are the actual static arrays, one for each giant we know about.
 * Since they're variable size, we have to allocate and name each one
 * individually....
 */

#if		FEE_PROTOTYPE_CURVES
#include "curveParamDataOld.h"
#else
#include "curveParamData.h"
#endif

/*
 * Now the curveParamsStatic structs, which provide templates for creating the
 * fields in a specific curveParams struct.
 *
 * All giants in a curveParamsStatic struct except for basePrime are
 * guaranteed valid.
 *
 * Note these are stored as an array, an index into which is a feeDepth
 * parameter.
 */
#if		FEE_PROTOTYPE_CURVES
static curveParamsStatic curveParamsArray[] = {
    {	// depth=0
	FPT_Mersenne,
	FCT_Weierstrass,
	31, 1,			// q=31, k=1
	NULL,			// basePrime only used for FPT_General
	1,				// m = 1
    ga_w31_1_a,		// a = 7
	ga_one,			// b = 1
	ga_zero,		// c = 0
	ga_w31_1_x1Plus,
	NULL,			// y1Plus
	ga_w31_1_x1Minus,
	ga_w31_1_plusOrder,
	ga_w31_1_minusOrder,
	ga_w31_1_x1OrderPlus,
	ga_w31_1_x1OrderMinus,
	ga_w31_1_x1OrderPlusRecip,
	ga_w31_1_lesserX1OrderRecip
    },
    {	// depth=1
     	FPT_Mersenne,
	FCT_Montgomery,
   	31, 1,			// q=31, k=1
	NULL,
	1,				// m = 1
   	ga_one,			// a = 1
	ga_zero,		// b = 0
	ga_666,			// c = 666
	ga_m31_1_x1Plus,
	NULL,			// y1Plus
	ga_m31_1_x1Minus,
	ga_m31_1_plusOrder,
	ga_m31_1_minusOrder,
	ga_m31_1_x1OrderPlus,
	ga_m31_1_x1OrderMinus,
	ga_m31_1_x1OrderPlusRecip,
	ga_m31_1_lesserX1OrderRecip

   },
    {	// depth=2
    	FPT_Mersenne,
	FCT_Weierstrass,
   	31, 1,				// q=31, k=1, prime curve orders
	NULL,
	1,					// m = 1
    ga_31_1P_a,			// a = 5824692
	ga_31_1P_b,			// b = 2067311435
	ga_zero,			// c = 0
	ga_31_1P_x1Plus,
	NULL,			// y1Plus
	ga_31_1P_x1Minus,
	ga_31_1P_plusOrder,
	ga_31_1P_minusOrder,
	ga_31_1P_x1OrderPlus,
	ga_31_1P_x1OrderMinus,
	ga_31_1P_x1OrderPlusRecip,
	NULL			// x1PlusOrder is lesser

   },
    {	// depth=3
    	FPT_FEE,
	FCT_Weierstrass,
   	40, 213,			// q=40, k=213, prime curve orders
	NULL,
 	1,					// m = 1
   	ga_40_213_a,		// a = 1627500953
	ga_40_213_b,		// b = 523907505
	ga_zero,			// c = 0
	ga_40_213_x1Plus,
	NULL,			// y1Plus
	ga_40_213_x1Minus,
	ga_40_213_plusOrder,
	ga_40_213_minusOrder,
	ga_40_213_x1OrderPlus,
	ga_40_213_x1OrderMinus,
	ga_40_213_x1OrderPlusRecip,
	ga_40_213_lesserX1OrderRecip

   },
   {	// depth=4
     	FPT_Mersenne,
	FCT_Montgomery,
   	127, 1,
	NULL,
	1,				// m = 1
   	ga_one,			// a = 1
	ga_zero,		// b = 0
	ga_666,			// c = 666
	ga_127_1_x1Plus,
	NULL,			// y1Plus
	ga_127_1_x1Minus,
	ga_127_1_plusOrder,
	ga_127_1_minusOrder,
	ga_127_1_x1OrderPlus,
	ga_127_1_x1OrderMinus,
	ga_127_1_x1OrderPlusRecip,
	ga_127_1_lesserX1OrderRecip

    },
    {	// depth=5
     	FPT_Mersenne,
	FCT_Weierstrass,
   	127, 1, 		// q=127, k=1 Weierstrass
	NULL,
	1,				// m = 1
    ga_666,			// a = 666
	ga_one,			// b = 1
	ga_zero,		// c = 0
	ga_127_1W_x1Plus,
	NULL,			// y1Plus
	ga_127_1W_x1Minus,
	ga_127_1W_plusOrder,
	ga_127_1W_minusOrder,
	ga_127_1W_x1OrderPlus,
	ga_127_1W_x1OrderMinus,
	ga_127_1W_x1OrderPlusRecip,
	NULL			// x1PlusOrder is lesser

    },
    {	// depth=6
    FPT_FEE,
	FCT_Weierstrass,	// also Atkin3
    160, 57,
	NULL,
	1,					// m = 1
	ga_zero,			// a = 0
	ga_160_57_b,		// b = 3
	ga_zero,			// c = 0
	ga_160_57_x1Plus,
	NULL,			// y1Plus
	ga_160_57_x1Minus,
	ga_160_57_plusOrder,
	ga_160_57_minusOrder,
	ga_160_57_x1OrderPlus,
	ga_160_57_x1OrderMinus,
	ga_160_57_x1OrderPlusRecip,
	NULL			// x1PlusOrder is lesser
    },
    {	// depth=7
    FPT_FEE,
	FCT_Weierstrass,	// also Atkin3
     192, 1425,
	NULL,
	1,					// m = 1
    ga_zero,			// a = 0
	ga_192_1425_b,		// b = -11
	ga_zero,			// c = 0
	ga_192_1425_x1Plus,
	NULL,			// y1Plus
	ga_192_1425_x1Minus,
	ga_192_1425_plusOrder,
	ga_192_1425_minusOrder,
	ga_192_1425_x1OrderPlus,
	ga_192_1425_x1OrderMinus,
	ga_192_1425_x1OrderPlusRecip,
	NULL			// x1PlusOrder is lesser

    },
    {	// depth=8
    FPT_FEE,
	FCT_Weierstrass,
    192, -529891,
	NULL,
	1,						// m = 1
    ga_192_M529891_a,		// a = -152
	ga_192_M529891_b,		// b = 722
	ga_zero,				// c = 0
	ga_192_M529891_x1Plus,
	NULL,			// y1Plus
	ga_192_M529891_x1Minus,
	ga_192_M529891_plusOrder,
	ga_192_M529891_minusOrder,
	ga_192_M529891_x1OrderPlus,
	ga_192_M529891_x1OrderMinus,
	ga_192_M529891_x1OrderPlusRecip,
	ga_192_M529891_lesserX1OrderRecip

    },
    /*
     * FPT_General curves, currently just copies of known FPT_FEE or FPT_Mersenne
     * curves with primeType set to FPT_General. These are just for
     * verification the general curve are handled properly.
	 * We include the q parameter here for use by feeKeyBitsToDepth().
     */
    {	// depth=9
    FPT_General,
	FCT_General,
   	127, 0,
	ga_127_1_bp,	// explicit basePrime
	1,				// m = 1
   	ga_one,			// a = 1
	ga_zero,		// b = 0
	ga_666,			// c = 666
	ga_127_1_x1Plus,
	NULL,			// y1Plus
	ga_127_1_x1Minus,
	ga_127_1_plusOrder,
	ga_127_1_minusOrder,
	ga_127_1_x1OrderPlus,
	ga_127_1_x1OrderMinus,
	ga_127_1_x1OrderPlusRecip,
	ga_127_1_lesserX1OrderRecip

    },

    {	// depth=10, FPT_General version of q=160
	FPT_General,
	FCT_Weierstrass,
	160, 0,				// we don't use these...
	ga_160_57_bp,		// explicit basePrime
	1,					// m = 1
	ga_zero,			// a = 0
	ga_160_57_b,		// b = 3
	ga_zero,
	ga_160_57_x1Plus,
	NULL,			// y1Plus
	ga_160_57_x1Minus,
	ga_160_57_plusOrder,
	ga_160_57_minusOrder,
	ga_160_57_x1OrderPlus,
	ga_160_57_x1OrderMinus,
	ga_160_57_x1OrderPlusRecip,
	NULL			// x1PlusOrder is lesser
    },

    {	// depth=11, FPT_General, 161 bits
	FPT_General,
	FCT_Weierstrass,
	//161, 0,
    161, 0,				// for verifying we don't use these...
	ga_161_gen_bp,		// explicit basePrime
	1,					// m = 1
	ga_161_gen_a,		// a = -152
	ga_161_gen_b,		// b = 722
	ga_zero,			// c = 0
	ga_161_gen_x1Plus,
	NULL,			// y1Plus
	ga_161_gen_x1Minus,
	ga_161_gen_plusOrder,
	ga_161_gen_minusOrder,
	ga_161_gen_x1OrderPlus,
	ga_161_gen_x1OrderMinus,
	ga_161_gen_x1OrderPlusRecip,
	NULL			// x1PlusOrder is lesser
    },

};

#else	/* FEE_PROTOTYPE_CURVES */

static const curveParamsStatic curveParamsArray[] = {
{	
	/*
	 * depth = 0
	 * FEE CURVE: USE FOR FEE SIG. & FEED ONLY.
	 * primeType->Mersenne
	 * curveType->Montgomery
	 * q = 31;   k = 1;  p = 2^q - k;
	 * a = 1;   b = 0;   c = 666;
	 * Both orders composite.
	 */
	FPT_Mersenne,
	FCT_Montgomery,
	31, 1,			// q=31, k=1
	NULL,			// basePrime only used for FPT_General
	1,				// m = 1
    ga_one,			// a = 1
	ga_zero,		// b = 0
	ga_666,			// c = 666
	ga_31m_x1Plus,
	NULL,			// y1Plus
	ga_31m_x1Minus,
	ga_31m_plusOrder,
	ga_31m_minusOrder,
	ga_31m_x1OrderPlus,
	ga_31m_x1OrderMinus,
	ga_31m_x1OrderPlusRecip,
	ga_31m_lesserX1OrderRecip
},
{
	/* 
	 * depth = 1
	 * IEEE P1363 COMPATIBLE.
	 * primeType->Mersenne
	 * curveType->Weierstrass
	 * q = 31;   k = 1; p = 2^q-k;  
	 * a = 5824692    b = 2067311435   c = 0
	 * Both orders prime.
	 */
	FPT_Mersenne,
	FCT_Weierstrass,
	31, 1,			// q=31, k=1
	NULL,			// basePrime only used for FPT_General
	1,				// m = 1
    ga_31w_a,		
	ga_31w_b,		
	ga_zero,		// c = 0
	ga_31w_x1Plus,
	NULL,			// y1Plus
	ga_31w_x1Minus,
	ga_31w_plusOrder,
	ga_31w_minusOrder,
	ga_31w_x1OrderPlus,
	ga_31w_x1OrderMinus,
	ga_31w_x1OrderPlusRecip,
	NULL			// x1PlusOrder is lesser
},
{
	/* 
	 * depth = 2
	 * FEE CURVE: USE FOR FEE SIG. & FEED ONLY.
	 * primeType->Mersenne
	 * curveType->Montgomery
	 * q = 127;   k = 1;  p = 2^q - k;
	 * a = 1;   b = 0;   c = 666;
	 * Both orders composite.
	 */
	FPT_Mersenne,
	FCT_Montgomery,
	127, 1,			// q = 127; k = 1
	NULL,			// basePrime only used for FPT_General
	1,				// m = 1
    ga_one,		
	ga_zero,		
	ga_666,
	ga_127m_x1Plus,
	NULL,			// y1Plus
	ga_127m_x1Minus,
	ga_127m_plusOrder,
	ga_127m_minusOrder,
	ga_127m_x1OrderPlus,
	ga_127m_x1OrderMinus,
	ga_127m_x1OrderPlusRecip,
	ga_127m_lesserX1OrderRecip
},
{
	/*
	 * depth = 3
 	 * IEEE P1363 COMPATIBLE.
	 * primeType->feemod
	 * curveType->Weierstrass
	 * q = 127;  k = -57675; p = 2^q - k;
	 * a = 170141183460469025572049133804586627403;   
	 * b = 170105154311605172483148226534443139403;    c = 0;
	 * Both orders prime.
	 */
	FPT_FEE,
	FCT_Weierstrass,
	127, -57675,	// q = 127;  k = -57675
	NULL,			// basePrime only used for FPT_General
	1,				// m = 1
    ga_128w_a,		
	ga_128w_b,		
	ga_zero,
	ga_128w_x1Plus,
	NULL,			// y1Plus
	ga_128w_x1Minus,
	ga_128w_plusOrder,
	ga_128w_minusOrder,
	ga_128w_x1OrderPlus,
	ga_128w_x1OrderMinus,
	ga_128w_x1OrderPlusRecip,
	/* REC said NULL, dmitch says: */
	ga_128w_lesserX1OrderRecip			// x1PlusOrder is lesser
},
{
	/*
	 * depth = 4
 	 * IEEE P1363 COMPATIBLE.
	 * primeType->feemod
	 * curveType->Weierstrass
	 * q = 160;  k = -5875; p = 2^q - k;
	 * a = 1461501637330902918203684832716283019448563798259;   
	 * b = 36382017816364032;    c = 0;
	 * Both orders prime.:
	 */
	FPT_FEE,
	FCT_Weierstrass,
	160, -5875,		// q = 160;  k = -5875
	NULL,			// basePrime only used for FPT_General
	1,				// m = 1
    ga_161w_a,		
	ga_161w_b,		
	ga_zero,
	ga_161w_x1Plus,
	NULL,			// y1Plus
	ga_161w_x1Minus,
	ga_161w_plusOrder,
	ga_161w_minusOrder,
	ga_161w_x1OrderPlus,
	ga_161w_x1OrderMinus,
	ga_161w_x1OrderPlusRecip,
	/* dmitch addenda - REC said NULL */ 
	ga_161w_lesserX1OrderRecip
},
{
	/*
	 * depth = 5
 	 * IEEE P1363 COMPATIBLE.
	 * primeType->General
	 * curveType->Weierstrass
	 * p is a 161-bit random prime (below, ga_161_gen_bp[]);
	 * a = -152;   b = 722;    c = 0;
	 * Both orders composite.
	 */
	FPT_General,
	FCT_Weierstrass,
	161, 0,			// not used
	ga_161_gen_bp,	// basePrime 
	1,				// m = 1
    ga_161_gen_a,		
	ga_161_gen_b,		
	ga_zero,
	ga_161_gen_x1Plus,
	NULL,			// y1Plus
	ga_161_gen_x1Minus,
	ga_161_gen_plusOrder,
	ga_161_gen_minusOrder,
	ga_161_gen_x1OrderPlus,
	ga_161_gen_x1OrderMinus,
	ga_161_gen_x1OrderPlusRecip,
	NULL			// x1PlusOrder is lesser
},
{
	/*
	 * depth = 6
 	 * IEEE P1363 COMPATIBLE.
	 * (NIST-P-192 RECOMMENDED PRIME)
	 * primeType->General
	 * curveType->Weierstrass
	 * p is a 192-bit random prime (below, ga_161_gen_bp[]);
	 * a = -3;   
	 * b = 2455155546008943817740293915197451784769108058161191238065;    
	 * c = 0;
	 * Plus-order is prime, minus-order is composite.
	 */
	FPT_General,
	FCT_Weierstrass,
	192, 0,			// only used for initGiantStacks(giantMaxDigits())
	ga_192_gen_bp,	// basePrime 
	1,				// m = 1
    ga_192_gen_a,		
	ga_192_gen_b,		
	ga_zero,
	ga_192_gen_x1Plus,
	NULL,			// y1Plus
	ga_192_gen_x1Minus,
	ga_192_gen_plusOrder,
	ga_192_gen_minusOrder,
	ga_192_gen_x1OrderPlus,
	ga_192_gen_x1OrderMinus,
	ga_192_gen_x1OrderPlusRecip,
	ga_192_gen_lesserX1OrderRecip  
},

/* ANSI X9.62/Certicom curves */
{
	/*
	 * depth = 7
 	 * ANSI X9.62/Certicom secp192r1
	 */
	FPT_General,
	FCT_Weierstrass,
	192, 0,			// only used for initGiantStacks(giantMaxDigits())
	ga_192_secp_bp,	// basePrime 
	1,				// m = 1
    ga_192_secp_a,		
	ga_192_secp_b,		
	ga_zero,
	ga_192_secp_x1Plus,
	ga_192_secp_y1Plus,
	NULL,			// x1Minus
	ga_192_secp_plusOrder,
	NULL,			// minusOrder,
	ga_192_secp_x1OrderPlus,
	NULL,			// x1OrderMinus,
	ga_192_secp_x1OrderPlusRecip,
},
{
	/*
	 * depth = 8
 	 * ANSI X9.62/Certicom secp256r1
	 */
	FPT_General,
	FCT_Weierstrass,
	256, 0,			// only used for initGiantStacks(giantMaxDigits())
	ga_256_secp_bp,	// basePrime 
	1,				// m = 1
    ga_256_secp_a,		
	ga_256_secp_b,		
	ga_zero,
	ga_256_secp_x1Plus,
	ga_256_secp_y1Plus,
	NULL,
	ga_256_secp_plusOrder,
	NULL,
	ga_256_secp_x1OrderPlus,
	NULL,
	ga_256_secp_x1OrderPlusRecip,
	NULL  
},
{
	/*
	 * depth = 9
 	 * ANSI X9.62/Certicom secp384r1
	 */
	FPT_General,
	FCT_Weierstrass,
	384, 0,			// only used for initGiantStacks(giantMaxDigits())
	ga_384_secp_bp,	// basePrime 
	1,				// m = 1
    ga_384_secp_a,		
	ga_384_secp_b,		
	ga_zero,
	ga_384_secp_x1Plus,
	ga_384_secp_y1Plus,
	NULL,
	ga_384_secp_plusOrder,
	NULL,
	ga_384_secp_x1OrderPlus,
	NULL,
	ga_384_secp_x1OrderPlusRecip,
	NULL  
},
{
	/*
	 * depth = 10
 	 * ANSI X9.62/Certicom secp521r1
	 */
	FPT_General,
	FCT_Weierstrass,
	521, 0,		
	ga_521_secp_bp,	// basePrime 
	1,				// m = 1
    ga_521_secp_a,		
	ga_521_secp_b,		
	ga_zero,
	ga_521_secp_x1Plus,
	ga_521_secp_y1Plus,
	NULL,
	ga_521_secp_plusOrder,
	NULL,
	ga_521_secp_x1OrderPlus,
	NULL,
	ga_521_secp_x1OrderPlusRecip,
	NULL  
}
};
#endif	/* FEE_PROTOTYPE_CURVES */

/*
 * Convert the static form of a giant - i.e., an array of arrayDigits,
 * the first of which is the sign, the remainder of which are base 65536
 * digits - into a giant. A null pointer on input results in a null return.
 */
static giant arrayToGiant(const arrayDigit *array)
{
	unsigned 	numBytes;	// in result->n[]
	int			numDigits;	// ditto
	giant    	result;
	giantDigit 	digit;
	unsigned char 	byte;
	unsigned 	i;
	unsigned 	digitDex;	// index into result->n[]
	unsigned 	digitByte;	// byte selector in digit
	const arrayDigit 	*ap;		// running ptr into array
	short		sign;

	if(array == NULL) {
		CKRaise("arrayToGiant: NULL array");
	}
	sign = (short)array[0];
	numBytes = abs(sign) * sizeof(unsigned short);
	numDigits = BYTES_TO_GIANT_DIGITS(numBytes);

	/* note giantstruct has one explicit giantDigit */
	result = (giant) fmalloc(sizeof(giantstruct) +
		((numDigits - 1) * GIANT_BYTES_PER_DIGIT));
	result->capacity = numDigits;

	ap = array + 1;
	digit = 0;
	digitDex = 0;

	for(i=0; i<numBytes;) {
	    for(digitByte=0; digitByte<GIANT_BYTES_PER_DIGIT; digitByte++) {
	        /* grab a byte from the array */
	    	if(i & 1) {
		    /* odd byte - snag it and advance to next array digit */
		    byte = (unsigned char)(*ap++ >> 8);
		}
		else {
		    /* even, i.e., l.s. byte */
		    byte = (unsigned char)(*ap);
		}

		/* add byte to current digit */
		digit |= (byte << (8 * digitByte));
		if(++i == numBytes) {
		    /* end of array, perhaps in the midst of a digit */
		    break;
		}
	    }
	    result->n[digitDex++] = digit;
	    digit = 0;
	};

	/* Careful:
	 * -- array elements are unsigned. The first element is
	 *    he number of SHORTS in the array; convert to native
	 *    digits.
	 * -- in the very odd (test only) case of giantDigit = unsigned char,
	 *    we might have fewer valid digits than numDigits (might have
	 *    leading zeros).
	 */
	if(sign < 0) {
	    result->sign = -numDigits;
	}
	else {
	    result->sign = numDigits;
	}
	gtrimSign(result);
	return result;
}

/*
 * Obtain a malloc'd and uninitialized curveParams, to be init'd by caller.
 */
curveParams *newCurveParams(void)
{
	curveParams *params = (curveParams*) fmalloc(sizeof(curveParams));

	bzero(params, sizeof(curveParams));
	return params;
}

/*
 * Alloc and zero reciprocal giants, when maxDigits is known.
 * Currently only called when creating a curveParams from a public key.
 * cp->primeType must be valid on input.
 */
void allocRecipGiants(curveParams *cp)
{
	cp->lesserX1OrderRecip = newGiant(cp->maxDigits);
	cp->x1OrderPlusRecip = newGiant(cp->maxDigits);
	int_to_giant(0, cp->lesserX1OrderRecip);
	int_to_giant(0, cp->x1OrderPlusRecip);
}

/*
 * Obtain a malloc'd curveParams for a specified feeDepth.
 */
curveParams *curveParamsForDepth(feeDepth depth)
{
	curveParams *cp;
	const curveParamsStatic *cps = &curveParamsArray[depth];

	if(depth > FEE_DEPTH_MAX) {
		return NULL;
	}
	#if	GIANTS_VIA_STACK
	curveParamsInitGiants();
	#endif
	cp = newCurveParams();
	cp->primeType = cps->primeType;
	cp->curveType = cps->curveType;
	cp->q = cps->q;
	cp->k = cps->k;
	cp->m = cps->m;
	if(cp->primeType == FPT_General) {
	    cp->basePrime = arrayToGiant(cps->basePrime);
	}
	cp->a = arrayToGiant(cps->a);
	cp->b = arrayToGiant(cps->b);
	cp->c = arrayToGiant(cps->c);
	cp->x1Plus  = arrayToGiant(cps->x1Plus);
	if(cps->y1Plus) {
		cp->y1Plus = arrayToGiant(cps->y1Plus);
	}
	if(cps->x1Minus) {
		cp->x1Minus = arrayToGiant(cps->x1Minus);
	}
	cp->cOrderPlus   = arrayToGiant(cps->cOrderPlus);
	if(cps->cOrderMinus) {
		cp->cOrderMinus  = arrayToGiant(cps->cOrderMinus);
	}
	cp->x1OrderPlus  = arrayToGiant(cps->x1OrderPlus);
	if(cps->x1OrderMinus) {
		cp->x1OrderMinus = arrayToGiant(cps->x1OrderMinus);
	}
	cp->x1OrderPlusRecip = arrayToGiant(cps->x1OrderPlusRecip);

	/*
	 * Special case optimization for equal reciprocals.
	 */
	if(cps->lesserX1OrderRecip == NULL) {
	    cp->lesserX1OrderRecip = cp->x1OrderPlusRecip;
	}
	else {
	    cp->lesserX1OrderRecip = arrayToGiant(cps->lesserX1OrderRecip);
	}

	/* remainder calculated at runtime */
	curveParamsInferFields(cp);
	return cp;
}

/*
 * Alloc a new curveParams struct as a copy of specified instance.
 * This is the only way we can create a curveParams struct which doesn't
 * match any existing known curve params.
 */
curveParams *curveParamsCopy(curveParams *cp)
{
	curveParams *newcp = newCurveParams();

	newcp->primeType = cp->primeType;
	newcp->curveType = cp->curveType;
	newcp->q = cp->q;
	newcp->k = cp->k;
	newcp->m = cp->m;
	newcp->basePrime = copyGiant(cp->basePrime);
	newcp->minBytes = cp->minBytes;
	newcp->maxDigits = cp->maxDigits;

	newcp->a            = copyGiant(cp->a);
	newcp->b            = copyGiant(cp->b);
	newcp->c            = copyGiant(cp->c);
	newcp->x1Plus       = copyGiant(cp->x1Plus);
	if(cp->x1Minus) {
		newcp->x1Minus 	= copyGiant(cp->x1Minus);
	}
	newcp->y1Plus 	    = copyGiant(cp->y1Plus);
	newcp->cOrderPlus   = copyGiant(cp->cOrderPlus);
	if(cp->cOrderMinus) {
		newcp->cOrderMinus  = copyGiant(cp->cOrderMinus);
	}
	newcp->x1OrderPlus  = copyGiant(cp->x1OrderPlus);
	if(cp->x1OrderMinus) {
		newcp->x1OrderMinus = copyGiant(cp->x1OrderMinus);
	}
	
	newcp->x1OrderPlusRecip = copyGiant(cp->x1OrderPlusRecip);
	if(cp->x1OrderPlusRecip == cp->lesserX1OrderRecip) {
		/*
		 * Equal reciprocals; avoid new malloc
		 */
		newcp->lesserX1OrderRecip = newcp->x1OrderPlusRecip;
	}
	else {
		newcp->lesserX1OrderRecip = copyGiant(cp->lesserX1OrderRecip);
	}
	if(cp->primeType == FPT_General) {
		newcp->basePrimeRecip = copyGiant(cp->basePrimeRecip);
	}
	return newcp;
}

/*
 * Free a curveParams struct.
 */
void freeCurveParams(curveParams *cp)
{
	if(cp->basePrime != NULL) {
		freeGiant(cp->basePrime);
	}
	if(cp->a != NULL) {
		freeGiant(cp->a);
	}
	if(cp->b != NULL) {
		freeGiant(cp->b);
	}
	if(cp->c != NULL) {
		freeGiant(cp->c);
	}
	if(cp->x1Plus != NULL) {
		freeGiant(cp->x1Plus);
	}
	if(cp->x1Minus != NULL) {
		freeGiant(cp->x1Minus);
	}
	if(cp->y1Plus != NULL) {
		freeGiant(cp->y1Plus);
	}
	if(cp->cOrderPlus != NULL) {
		freeGiant(cp->cOrderPlus);
	}
	if(cp->cOrderMinus != NULL) {
		freeGiant(cp->cOrderMinus);
	}
	if(cp->x1OrderPlus != NULL) {
		freeGiant(cp->x1OrderPlus);
	}
	if(cp->x1OrderMinus != NULL) {
		freeGiant(cp->x1OrderMinus);
	}
	if(cp->x1OrderPlusRecip != NULL) {
		freeGiant(cp->x1OrderPlusRecip);
	}

	/*
	 * Special case - if these are equal, we only alloc'd one giant
	 */
	if(cp->lesserX1OrderRecip != cp->x1OrderPlusRecip) {
		freeGiant(cp->lesserX1OrderRecip);
	}
	if(cp->basePrimeRecip != NULL) {
		freeGiant(cp->basePrimeRecip);
	}
	ffree(cp);
}

/*
 * Returns 1 if two sets of curve parameters are equivalent, else returns 0.
 */
int curveParamsEquivalent(curveParams *cp1, curveParams *cp2)
{
	if(cp1 == cp2) {
		/*
		 * Trivial case, actually common for signature verify
		 */
		return 1;
	}
	if(cp1->primeType != cp2->primeType) {
		return 0;
	}
	if(cp1->curveType != cp2->curveType) {
		return 0;
	}
	if(cp1->k != cp2->k) {
		return 0;
	}
	if(cp1->q != cp2->q) {
		return 0;
	}
	if(cp1->m != cp2->m) {
		return 0;
	}
	if(gcompg(cp1->basePrime, cp2->basePrime)) {
		return 0;
	}
	if(gcompg(cp1->a, cp2->a)) {
		return 0;
	}
	if(gcompg(cp1->b, cp2->b)) {
		return 0;
	}
	if(gcompg(cp1->c, cp2->c)) {
		return 0;
	}
	if(gcompg(cp1->x1Plus, cp2->x1Plus)) {
		return 0;
	}
	if((cp1->x1Minus != NULL) && (cp2->x1Minus != NULL)) {
		if(gcompg(cp1->x1Minus, cp2->x1Minus)) {
			return 0;
		}
	}
	if(gcompg(cp1->cOrderPlus, cp2->cOrderPlus)) {
		return 0;
	}
	if((cp1->cOrderMinus != NULL) && (cp2->cOrderMinus != NULL)) {
		if(gcompg(cp1->cOrderMinus, cp2->cOrderMinus)) {
			return 0;
		}
	}
	if(gcompg(cp1->x1OrderPlus, cp2->x1OrderPlus)) {
		return 0;
	}
	if((cp1->x1OrderMinus != NULL) && (cp2->x1OrderMinus != NULL)) {
		if(gcompg(cp1->x1OrderMinus, cp2->x1OrderMinus)) {
			return 0;
		}
	}
	/*
	 * If we got this far, reciprocals can't possibly be different
	 */
	return 1;
}

/*
 * Obtain the lesser of {x1OrderPlus, x1OrderMinus}. Returned value is not
 * malloc'd; it's a pointer to one of the orders in *cp.
 */
giant lesserX1Order(curveParams *cp)
{
	CKASSERT(!isZero(cp->x1OrderPlus));

	if(cp->x1OrderMinus == NULL) {
	    return(cp->x1OrderPlus);
	}
	else if(gcompg(cp->x1OrderPlus, cp->x1OrderMinus) >= 0) {
	    return(cp->x1OrderMinus);
	}
	else {
	    return(cp->x1OrderPlus);
	}
}

#if		GIANTS_VIA_STACK

/*
 * Prime the curveParams and giants modules for quick allocs of giants.
 */
static int giantsInitd = 0;

void curveParamsInitGiants(void)
{
	const curveParamsStatic *cps = &curveParamsArray[FEE_DEPTH_MAX];

	if(giantsInitd) {
		return;
	}

	/*
	 * Figure the max giant size of the largest depth we know about...
	 */
	initGiantStacks(giantMaxDigits(giantMinBytes(cps->q, cps->k)));
	giantsInitd = 1;
}

#endif	// GIANTS_VIA_STACK

/*
 * Infer the following fields from a partially constructed curveParams:
 *
 *   basePrimeRecip if primeType == FPT_General
 *   basePrime if primeType != FPT_General
 *   y1Plus if curveType == FCT_Weierstrass and not pre-calculated
 *   minBytes
 *   maxDigits
 *
 * Assumes the following valid on entry:
 *   curveType
 *   primeType
 *   basePrime if primeType == FPT_General
 *   q, k if primeType != FPT_General
 */
void curveParamsInferFields(curveParams *cp)
{
	/* calc maxDigits, minBytes */
	calcGiantSizes(cp);

	/* basePrime or its reciprocal */
	if(cp->primeType == FPT_General) {
		/* FIXME this should be declared statically! */
	    cp->basePrimeRecip = newGiant(cp->maxDigits);
	    make_recip(cp->basePrime, cp->basePrimeRecip);
	}
	else {
	    /*
	     * FPT_FEE, FPT_Mersenne
	     */
	    cp->basePrime = newGiant(cp->maxDigits);
	    make_base_prim(cp);
	}

	/* y1Plus */
	#if CRYPTKIT_ELL_PROJ_ENABLE
	if(cp->curveType == FCT_Weierstrass) {
		if(cp->y1Plus == NULL) {
			/* ECDSA Curves already have this */
			pointProj pt = newPointProj(cp->maxDigits);
			findPointProj(pt, cp->x1Plus, cp);

			/* initial point is supposed to be on curve! */
			if(gcompg(pt->x, cp->x1Plus)) {
				CKRaise("curveParamsInferFields failure");
			}
			cp->y1Plus = copyGiant(pt->y);
			freePointProj(pt);
		}
	}
	else {
		cp->y1Plus = newGiant(1);
	}
	#else	/* CRYPTKIT_ELL_PROJ_ENABLE */
	cp->y1Plus = newGiant(1);
	#endif
	
	if((cp->x1OrderPlusRecip == NULL) || isZero(cp->x1OrderPlusRecip)) {
		/*
		 * an easy way of figuring this one out, this should not 
		 * normally run. 
		 */
		cp->x1OrderPlusRecip = newGiant(cp->maxDigits);
		make_recip(cp->x1OrderPlus, cp->x1OrderPlusRecip);
		if(cp->lesserX1OrderRecip != NULL) {
			freeGiant(cp->lesserX1OrderRecip);
		}
		cp->lesserX1OrderRecip = cp->x1OrderPlusRecip;
	}
}

/*
 * Given key size in bits, obtain the asssociated depth.
 * Returns FR_IllegalDepth if specify key size not found
 * in current curve tables. 
 */
#define LOG_DEPTH	0

#if	FEE_PROTOTYPE_CURVES
feeReturn feeKeyBitsToDepth(unsigned keySize,
	feePrimeType primeType,		/* FPT_Fefault means "best one" */
	feeCurveType curveType,		/* FCT_Default means "best one" */
	feeDepth *depth)
{
	feeReturn frtn = FR_Success;
	switch(keySize) {
	    case 31:
			switch(curveType) {
				case FCT_Montgomery:
				default:
					*depth = FEE_DEPTH_31_1_M;
					break;
				case FCT_Weierstrass:
					*depth = FEE_DEPTH_31_1_P;
					break;
			}
			break;
		case 40:
			switch(curveType) {
				case FCT_Weierstrass:
				default:
					*depth = FEE_DEPTH_40_213;
					break;
				case FCT_Montgomery:
					return FR_IllegalDepth;
			}
			break;
		case 127:
			switch(curveType) {
				case FCT_Montgomery:
					if(primeType == FPT_General) {
						*depth = FEE_DEPTH_127_GEN;
					}
					else{
						*depth = FEE_DEPTH_127_1;
					}
					break;
				case FCT_Weierstrass:
				default:
					*depth = FEE_DEPTH_127_1W;
					break;
			}
			break;
		case 160:
			switch(curveType) {
				case FCT_Montgomery:
					return FR_IllegalDepth;
				case FCT_Weierstrass:
				default:
					if(primeType == FPT_General) {
						*depth = FEE_DEPTH_160_GEN;
					}
					else {
						*depth = FEE_DEPTH_160_57;
					}
					break;
			}
			break;
		case 192:
			switch(curveType) {
				case FCT_Montgomery:
					*depth = FEE_DEPTH_192_M529891;
				case FCT_Weierstrass:
				default:
					*depth = FEE_DEPTH_192_1425;
					break;
			}
			break;
		default:
			frtn = FR_IllegalDepth;
			break;
	}
	#if LOG_DEPTH
	printf("feeKeyBitsToDepth: depth %d\n", *depth);
	#endif
	return frtn;
}

#else	/* FEE_PROTOTYPE_CURVES */

feeReturn feeKeyBitsToDepth(unsigned keySize,
	feePrimeType primeType,		/* FPT_Fefault means "best one" */
	feeCurveType curveType,		/* FCT_Default means "best one" */
	feeDepth *depth)
{
	feeReturn frtn = FR_Success;
	switch(keySize) {
	    case 31:
			if(primeType == FPT_General) {
				return FR_IllegalDepth; 
			}
			/* note we cut a request for FPT_FEE some slack...this is actually
			 * FPT_Mersenne, but that is technically a subset of FEE. */
			switch(curveType) {
				case FCT_Montgomery:
					*depth = FEE_DEPTH_31M;
					break;
				case FCT_Weierstrass:
				case FCT_Default:
					*depth = FEE_DEPTH_31W;
					break;
				default:
					return FR_IllegalDepth; 
			}
			break;
		case 127:
			/* Montgomery only */
			if(primeType == FPT_General) {
				return FR_IllegalDepth; 
			}
			/* note we cut a request for FPT_FEE some slack...this is actually
			 * FPT_Mersenne, but that is technically a subset of FEE. */
			switch(curveType) {
				case FCT_Montgomery:
				case FCT_Default:
					*depth = FEE_DEPTH_127M;
					break;
				case FCT_Weierstrass:
				default:
					return FR_IllegalDepth; 
			}
			break;
		case 128:
			/* Weierstrass/feemod only */
			switch(primeType) {
				case FPT_General:
				case FPT_Mersenne:
					return FR_IllegalDepth; 
				default:
					/* FPT_Default, FPT_FEE */
					break;
			}
			switch(curveType) {
				case FCT_Weierstrass:
				case FCT_Default:
					*depth = FEE_DEPTH_128W;
					break;
				default:
					return FR_IllegalDepth; 
			}
			break;
		case 161:
			switch(curveType) {
				case FCT_Weierstrass:
				case FCT_Default:
					switch(primeType) {
						case FPT_General:
							*depth = FEE_DEPTH_161G;
							break;
						case FPT_FEE:
						case FPT_Default:
							*depth = FEE_DEPTH_161W;
							break;
						default:
							/* i.e., FPT_Mersenne */
							return FR_IllegalDepth;
					}
					break;
				default:
					return FR_IllegalDepth;
			}
			break;
		case 192:
			switch(curveType) {
				case FCT_Montgomery:
				default:
					return FR_IllegalDepth;
				case FCT_Weierstrass:
				case FCT_Default:
					switch(primeType) {
						case FPT_General:
						case FPT_Default:
							*depth = FEE_DEPTH_192G;
							break;
						default:
							/* i.e., FPT_Mersenne, FPT_FEE */
							return FR_IllegalDepth;
					}
					break;
				case FCT_ANSI:
					switch(primeType) {
						case FPT_General:
						case FPT_Default:
							break;
						default:
							return FR_IllegalDepth;
					}
					*depth = FEE_DEPTH_secp192r1;
					break;
			}
			break;
		case 256:
			switch(curveType) {
				case FCT_ANSI:
				case FCT_Default:
					break;
				default:
					return FR_IllegalDepth;
			}
			switch(primeType) {
				case FPT_General:
				case FPT_Default:
					break;
				default:
					return FR_IllegalDepth;
			}
			*depth = FEE_DEPTH_secp256r1;
			break;
		case 384:
			switch(curveType) {
				case FCT_ANSI:
				case FCT_Default:
					break;
				default:
					return FR_IllegalDepth;
			}
			switch(primeType) {
				case FPT_General:
				case FPT_Default:
					break;
				default:
					return FR_IllegalDepth;
			}
			*depth = FEE_DEPTH_secp384r1;
			break;
		case 521:
			switch(curveType) {
				case FCT_ANSI:
				case FCT_Default:
					break;
				default:
					return FR_IllegalDepth;
			}
			switch(primeType) {
				case FPT_General:
				case FPT_Default:
					break;
				default:
					return FR_IllegalDepth;
			}
			*depth = FEE_DEPTH_secp521r1;
			break;
			
		default:
			frtn = FR_IllegalDepth;
			break;
	}
	#if LOG_DEPTH
	printf("feeKeyBitsToDepth: depth %d\n", *depth);
	#endif
	return frtn;
}

#endif	/* FEE_PROTOTYPE_CURVES  */

/* 
 * Obtain depth for specified curveParams
 */
feeReturn curveParamsDepth(
	curveParams *cp,
	feeDepth *depth)
{
	if(cp == NULL) {
		return FR_IllegalArg;
	}
	
	/* We do it this way to allow reconstructing depth from an encoded curveParams */
	feeCurveType curveType = cp->curveType;
	if((curveType == FCT_Weierstrass) && (cp->x1Minus == NULL)) {
		/* actually an ANSI curve */
		curveType = FCT_ANSI;
	}
	return feeKeyBitsToDepth(cp->q, cp->primeType, curveType, depth);
}