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