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