OSX/libsecurity_cryptkit/lib/curveParams.c

   1 /* Copyright (c) 1998,2011,2014 Apple Inc.  All Rights Reserved.
   2  *
   3  * NOTICE: USE OF THE MATERIALS ACCOMPANYING THIS NOTICE IS SUBJECT
   4  * TO THE TERMS OF THE SIGNED "FAST ELLIPTIC ENCRYPTION (FEE) REFERENCE
   5  * SOURCE CODE EVALUATION AGREEMENT" BETWEEN APPLE, INC. AND THE
   6  * ORIGINAL LICENSEE THAT OBTAINED THESE MATERIALS FROM APPLE,
   7  * INC.  ANY USE OF THESE MATERIALS NOT PERMITTED BY SUCH AGREEMENT WILL
   8  * EXPOSE YOU TO LIABILITY.
   9  ***************************************************************************
  10  *
  11  * curveParams.c - FEE curve parameter static data and functions
  12  *
  13  * Revision History
  14  * ----------------
  15  * 10/06/98             ap
  16  *      Changed to compile with C++.
  17  *  9 Sep 98 at NeXT
  18  *      Added y1Plus for IEEE P1363 compliance.
  19  *      Added curveParamsInferFields().
  20  *  08 Apr 98 at Apple
  21  *      Mods for giantDigit.
  22  *  20 Jan 98 at Apple
  23  *      Added primeType, m, basePrimeRecip; added a few PT_GENERAL curves.
  24  *  19 Jan 1998 at Apple
  25  *      New curve: q=160, k=57
  26  *  09 Jan 1998 at Apple
  27  *      Removed obsolete (i.e., incomplete) curves parameters.
  28  *  11 Jun 1997 at Apple
  29  *      Added x1OrderPlusRecip and lesserX1OrderRecip fields
  30  *      Added curveParamsInitGiants()
  31  *  9 Jan 1997 at NeXT
  32  *      Major mods for IEEE-style parameters.
  33  *  7 Aug 1996 at NeXT
  34  *      Created.
  35  */
  36
  37 #include "curveParams.h"
  38 #include "giantIntegers.h"
  39 #include "elliptic.h"
  40 #include "ellipticProj.h"
  41 #include "platform.h"
  42 #include "falloc.h"
  43 #include "feeDebug.h"
  44 #include <stdlib.h>
  45
  46 typedef unsigned short arrayDigit;
  47
  48 static giant arrayToGiant(const arrayDigit *array);
  49
  50 /*
  51  * Can't declare giants statically; we declare them here via static arrayDigit
  52  * arrays which contain the 'digits' in base 65536 of a giant
  53  * used as a curve parameter. First element is sign; next element is
  54  * l.s. digit; size of each array is abs(sign) + 1. These arrays are
  55  * converted to a giant via arrayToGiant().
  56  *
  57  * Static q and k values, as well as pointers to the arrayDigit arrays
  58  * associated with the various giants for a given curve, are kept in an
  59  * array of curveParamsStatic structs; a feeDepth is an index into this
  60  * array. A curveParamsStatic struct is converted to a curveParams struct in
  61  * curveParamsForDepth().
  62  */
  63 typedef struct {
  64         feePrimeType            primeType;
  65         feeCurveType            curveType;
  66         unsigned                        q;
  67         int                     k;
  68         const arrayDigit        *basePrime;             // FPT_General only
  69         arrayDigit                      m;                              // must be 1 for current release
  70         const arrayDigit        *a;
  71         const arrayDigit        *b;
  72         const arrayDigit        *c;
  73         const arrayDigit        *x1Plus;
  74         const arrayDigit        *y1Plus;                // optional, currently only used for ECDSA curves
  75         const arrayDigit        *x1Minus;               // optional, not used for ECDSA curves
  76         const arrayDigit        *cOrderPlus;
  77         const arrayDigit        *cOrderMinus;   // optional, not used for ECDSA curves
  78         const arrayDigit        *x1OrderPlus;
  79         const arrayDigit        *x1OrderMinus;  // optional, not used for ECDSA curves
  80         const arrayDigit        *x1OrderPlusRecip;
  81
  82         /*
  83          * A null lesserX1OrderRecip when x1OrderPlusRecip is non-null
  84          * means that the two values are identical; in this case, only
  85          * one giant is alloc'd in the actual curveParams struct.
  86          */
  87         const arrayDigit        *lesserX1OrderRecip;
  88 } curveParamsStatic;
  89
  90 /*
  91  * First some common giant-arrays used in lots of curveGiants.
  92  */
  93 static const arrayDigit ga_666[]  = {1, 666 };  // a common value for 'c'
  94 static const arrayDigit ga_zero[] = {1, 0   };  // (giant)0
  95 static const arrayDigit ga_one[]  = {1, 1   };  // (giant)1
  96
  97 /*
  98  * Here are the actual static arrays, one for each giant we know about.
  99  * Since they're variable size, we have to allocate and name each one
 100  * individually....
 101  */
 102
 103 #include "curveParamData.h"
 104
 105
 106 /*
 107  * Now the curveParamsStatic structs, which provide templates for creating the
 108  * fields in a specific curveParams struct.
 109  *
 110  * All giants in a curveParamsStatic struct except for basePrime are
 111  * guaranteed valid.
 112  *
 113  * Note these are stored as an array, an index into which is a feeDepth
 114  * parameter.
 115  */
 116
 117
 118 static const curveParamsStatic curveParamsArray[] = {
 119 {
 120         /*
 121          * depth = 0
 122          * FEE CURVE: USE FOR FEE SIG. & FEED ONLY.
 123          * primeType->Mersenne
 124          * curveType->Montgomery
 125          * q = 31;   k = 1;  p = 2^q - k;
 126          * a = 1;   b = 0;   c = 666;
 127          * Both orders composite.
 128          */
 129         FPT_Mersenne,
 130         FCT_Montgomery,
 131         31, 1,                  // q=31, k=1
 132         NULL,                   // basePrime only used for FPT_General
 133         1,                              // m = 1
 134     ga_one,                     // a = 1
 135         ga_zero,                // b = 0
 136         ga_666,                 // c = 666
 137         ga_31m_x1Plus,
 138         NULL,                   // y1Plus
 139         ga_31m_x1Minus,
 140         ga_31m_plusOrder,
 141         ga_31m_minusOrder,
 142         ga_31m_x1OrderPlus,
 143         ga_31m_x1OrderMinus,
 144         ga_31m_x1OrderPlusRecip,
 145         ga_31m_lesserX1OrderRecip
 146 },
 147 {
 148         /*
 149          * depth = 1
 150          * IEEE P1363 COMPATIBLE.
 151          * primeType->Mersenne
 152          * curveType->Weierstrass
 153          * q = 31;   k = 1; p = 2^q-k;
 154          * a = 5824692    b = 2067311435   c = 0
 155          * Both orders prime.
 156          */
 157         FPT_Mersenne,
 158         FCT_Weierstrass,
 159         31, 1,                  // q=31, k=1
 160         NULL,                   // basePrime only used for FPT_General
 161         1,                              // m = 1
 162     ga_31w_a,
 163         ga_31w_b,
 164         ga_zero,                // c = 0
 165         ga_31w_x1Plus,
 166         NULL,                   // y1Plus
 167         ga_31w_x1Minus,
 168         ga_31w_plusOrder,
 169         ga_31w_minusOrder,
 170         ga_31w_x1OrderPlus,
 171         ga_31w_x1OrderMinus,
 172         ga_31w_x1OrderPlusRecip,
 173         NULL                    // x1PlusOrder is lesser
 174 },
 175 {
 176         /*
 177          * depth = 2
 178          * FEE CURVE: USE FOR FEE SIG. & FEED ONLY.
 179          * primeType->Mersenne
 180          * curveType->Montgomery
 181          * q = 127;   k = 1;  p = 2^q - k;
 182          * a = 1;   b = 0;   c = 666;
 183          * Both orders composite.
 184          */
 185         FPT_Mersenne,
 186         FCT_Montgomery,
 187         127, 1,                 // q = 127; k = 1
 188         NULL,                   // basePrime only used for FPT_General
 189         1,                              // m = 1
 190     ga_one,
 191         ga_zero,
 192         ga_666,
 193         ga_127m_x1Plus,
 194         NULL,                   // y1Plus
 195         ga_127m_x1Minus,
 196         ga_127m_plusOrder,
 197         ga_127m_minusOrder,
 198         ga_127m_x1OrderPlus,
 199         ga_127m_x1OrderMinus,
 200         ga_127m_x1OrderPlusRecip,
 201         ga_127m_lesserX1OrderRecip
 202 },
 203 {
 204         /*
 205          * depth = 3
 206          * IEEE P1363 COMPATIBLE.
 207          * primeType->feemod
 208          * curveType->Weierstrass
 209          * q = 127;  k = -57675; p = 2^q - k;
 210          * a = 170141183460469025572049133804586627403;
 211          * b = 170105154311605172483148226534443139403;    c = 0;
 212          * Both orders prime.
 213          */
 214         FPT_FEE,
 215         FCT_Weierstrass,
 216         127, -57675,    // q = 127;  k = -57675
 217         NULL,                   // basePrime only used for FPT_General
 218         1,                              // m = 1
 219     ga_128w_a,
 220         ga_128w_b,
 221         ga_zero,
 222         ga_128w_x1Plus,
 223         NULL,                   // y1Plus
 224         ga_128w_x1Minus,
 225         ga_128w_plusOrder,
 226         ga_128w_minusOrder,
 227         ga_128w_x1OrderPlus,
 228         ga_128w_x1OrderMinus,
 229         ga_128w_x1OrderPlusRecip,
 230         /* REC said NULL, dmitch says: */
 231         ga_128w_lesserX1OrderRecip                      // x1PlusOrder is lesser
 232 },
 233 {
 234         /*
 235          * depth = 4
 236          * IEEE P1363 COMPATIBLE.
 237          * primeType->feemod
 238          * curveType->Weierstrass
 239          * q = 160;  k = -5875; p = 2^q - k;
 240          * a = 1461501637330902918203684832716283019448563798259;
 241          * b = 36382017816364032;    c = 0;
 242          * Both orders prime.:
 243          */
 244         FPT_FEE,
 245         FCT_Weierstrass,
 246         160, -5875,             // q = 160;  k = -5875
 247         NULL,                   // basePrime only used for FPT_General
 248         1,                              // m = 1
 249     ga_161w_a,
 250         ga_161w_b,
 251         ga_zero,
 252         ga_161w_x1Plus,
 253         NULL,                   // y1Plus
 254         ga_161w_x1Minus,
 255         ga_161w_plusOrder,
 256         ga_161w_minusOrder,
 257         ga_161w_x1OrderPlus,
 258         ga_161w_x1OrderMinus,
 259         ga_161w_x1OrderPlusRecip,
 260         /* dmitch addenda - REC said NULL */
 261         ga_161w_lesserX1OrderRecip
 262 },
 263 {
 264         /*
 265          * depth = 5
 266          * IEEE P1363 COMPATIBLE.
 267          * primeType->General
 268          * curveType->Weierstrass
 269          * p is a 161-bit random prime (below, ga_161_gen_bp[]);
 270          * a = -152;   b = 722;    c = 0;
 271          * Both orders composite.
 272          */
 273         FPT_General,
 274         FCT_Weierstrass,
 275         161, 0,                 // not used
 276         ga_161_gen_bp,  // basePrime
 277         1,                              // m = 1
 278     ga_161_gen_a,
 279         ga_161_gen_b,
 280         ga_zero,
 281         ga_161_gen_x1Plus,
 282         NULL,                   // y1Plus
 283         ga_161_gen_x1Minus,
 284         ga_161_gen_plusOrder,
 285         ga_161_gen_minusOrder,
 286         ga_161_gen_x1OrderPlus,
 287         ga_161_gen_x1OrderMinus,
 288         ga_161_gen_x1OrderPlusRecip,
 289         NULL                    // x1PlusOrder is lesser
 290 },
 291 {
 292         /*
 293          * depth = 6
 294          * IEEE P1363 COMPATIBLE.
 295          * (NIST-P-192 RECOMMENDED PRIME)
 296          * primeType->General
 297          * curveType->Weierstrass
 298          * p is a 192-bit random prime (below, ga_161_gen_bp[]);
 299          * a = -3;
 300          * b = 2455155546008943817740293915197451784769108058161191238065;
 301          * c = 0;
 302          * Plus-order is prime, minus-order is composite.
 303          */
 304         FPT_General,
 305         FCT_Weierstrass,
 306         192, 0,                 // only used for initGiantStacks(giantMaxDigits())
 307         ga_192_gen_bp,  // basePrime
 308         1,                              // m = 1
 309     ga_192_gen_a,
 310         ga_192_gen_b,
 311         ga_zero,
 312         ga_192_gen_x1Plus,
 313         NULL,                   // y1Plus
 314         ga_192_gen_x1Minus,
 315         ga_192_gen_plusOrder,
 316         ga_192_gen_minusOrder,
 317         ga_192_gen_x1OrderPlus,
 318         ga_192_gen_x1OrderMinus,
 319         ga_192_gen_x1OrderPlusRecip,
 320         ga_192_gen_lesserX1OrderRecip
 321 },
 322
 323 /* ANSI X9.62/Certicom curves */
 324 {
 325         /*
 326          * depth = 7
 327          * ANSI X9.62/Certicom secp192r1
 328          */
 329         FPT_General,
 330         FCT_Weierstrass,
 331         192, 0,                 // only used for initGiantStacks(giantMaxDigits())
 332         ga_192_secp_bp, // basePrime
 333         1,                              // m = 1
 334     ga_192_secp_a,
 335         ga_192_secp_b,
 336         ga_zero,
 337         ga_192_secp_x1Plus,
 338         ga_192_secp_y1Plus,
 339         NULL,                   // x1Minus
 340         ga_192_secp_plusOrder,
 341         NULL,                   // minusOrder,
 342         ga_192_secp_x1OrderPlus,
 343         NULL,                   // x1OrderMinus,
 344         ga_192_secp_x1OrderPlusRecip,
 345 },
 346 {
 347         /*
 348          * depth = 8
 349          * ANSI X9.62/Certicom secp256r1
 350          */
 351         FPT_General,
 352         FCT_Weierstrass,
 353         256, 0,                 // only used for initGiantStacks(giantMaxDigits())
 354         ga_256_secp_bp, // basePrime
 355         1,                              // m = 1
 356     ga_256_secp_a,
 357         ga_256_secp_b,
 358         ga_zero,
 359         ga_256_secp_x1Plus,
 360         ga_256_secp_y1Plus,
 361         NULL,
 362         ga_256_secp_plusOrder,
 363         NULL,
 364         ga_256_secp_x1OrderPlus,
 365         NULL,
 366         ga_256_secp_x1OrderPlusRecip,
 367         NULL
 368 },
 369 {
 370         /*
 371          * depth = 9
 372          * ANSI X9.62/Certicom secp384r1
 373          */
 374         FPT_General,
 375         FCT_Weierstrass,
 376         384, 0,                 // only used for initGiantStacks(giantMaxDigits())
 377         ga_384_secp_bp, // basePrime
 378         1,                              // m = 1
 379     ga_384_secp_a,
 380         ga_384_secp_b,
 381         ga_zero,
 382         ga_384_secp_x1Plus,
 383         ga_384_secp_y1Plus,
 384         NULL,
 385         ga_384_secp_plusOrder,
 386         NULL,
 387         ga_384_secp_x1OrderPlus,
 388         NULL,
 389         ga_384_secp_x1OrderPlusRecip,
 390         NULL
 391 },
 392 {
 393         /*
 394          * depth = 10
 395          * ANSI X9.62/Certicom secp521r1
 396          */
 397         FPT_General,
 398         FCT_Weierstrass,
 399         521, 0,
 400         ga_521_secp_bp, // basePrime
 401         1,                              // m = 1
 402     ga_521_secp_a,
 403         ga_521_secp_b,
 404         ga_zero,
 405         ga_521_secp_x1Plus,
 406         ga_521_secp_y1Plus,
 407         NULL,
 408         ga_521_secp_plusOrder,
 409         NULL,
 410         ga_521_secp_x1OrderPlus,
 411         NULL,
 412         ga_521_secp_x1OrderPlusRecip,
 413         NULL
 414 }
 415 };
 416
 417 /*
 418  * Convert the static form of a giant - i.e., an array of arrayDigits,
 419  * the first of which is the sign, the remainder of which are base 65536
 420  * digits - into a giant. A null pointer on input results in a null return.
 421  */
 422 static giant arrayToGiant(const arrayDigit *array)
 423 {
 424         unsigned        numBytes;       // in result->n[]
 425         int                     numDigits;      // ditto
 426         giant           result;
 427         giantDigit      digit;
 428         unsigned char   byte;
 429         unsigned        i;
 430         unsigned        digitDex;       // index into result->n[]
 431         unsigned        digitByte;      // byte selector in digit
 432         const arrayDigit        *ap;            // running ptr into array
 433         short           sign;
 434
 435         if(array == NULL) {
 436                 CKRaise("arrayToGiant: NULL array");
 437         }
 438         sign = (short)array[0];
 439         numBytes = abs(sign) * sizeof(unsigned short);
 440         numDigits = BYTES_TO_GIANT_DIGITS(numBytes);
 441
 442         /* note giantstruct has one explicit giantDigit */
 443         result = (giant) fmalloc(sizeof(giantstruct) +
 444                 ((numDigits - 1) * GIANT_BYTES_PER_DIGIT));
 445         result->capacity = numDigits;
 446
 447         ap = array + 1;
 448         digit = 0;
 449         digitDex = 0;
 450
 451         for(i=0; i<numBytes;) {
 452             for(digitByte=0; digitByte<GIANT_BYTES_PER_DIGIT; digitByte++) {
 453                 /* grab a byte from the array */
 454                 if(i & 1) {
 455                     /* odd byte - snag it and advance to next array digit */
 456                     byte = (unsigned char)(*ap++ >> 8);
 457                 }
 458                 else {
 459                     /* even, i.e., l.s. byte */
 460                     byte = (unsigned char)(*ap);
 461                 }
 462
 463                 /* add byte to current digit */
 464                 digit |= (byte << (8 * digitByte));
 465                 if(++i == numBytes) {
 466                     /* end of array, perhaps in the midst of a digit */
 467                     break;
 468                 }
 469             }
 470             result->n[digitDex++] = digit;
 471             digit = 0;
 472         };
 473
 474         /* Careful:
 475          * -- array elements are unsigned. The first element is
 476          *    he number of SHORTS in the array; convert to native
 477          *    digits.
 478          * -- in the very odd (test only) case of giantDigit = unsigned char,
 479          *    we might have fewer valid digits than numDigits (might have
 480          *    leading zeros).
 481          */
 482         if(sign < 0) {
 483             result->sign = -numDigits;
 484         }
 485         else {
 486             result->sign = numDigits;
 487         }
 488         gtrimSign(result);
 489         return result;
 490 }
 491
 492 /*
 493  * Obtain a malloc'd and uninitialized curveParams, to be init'd by caller.
 494  */
 495 curveParams *newCurveParams(void)
 496 {
 497         curveParams *params = (curveParams*) fmalloc(sizeof(curveParams));
 498
 499         bzero(params, sizeof(curveParams));
 500         return params;
 501 }
 502
 503 /*
 504  * Alloc and zero reciprocal giants, when maxDigits is known.
 505  * Currently only called when creating a curveParams from a public key.
 506  * cp->primeType must be valid on input.
 507  */
 508 void allocRecipGiants(curveParams *cp)
 509 {
 510         cp->lesserX1OrderRecip = newGiant(cp->maxDigits);
 511         cp->x1OrderPlusRecip = newGiant(cp->maxDigits);
 512         int_to_giant(0, cp->lesserX1OrderRecip);
 513         int_to_giant(0, cp->x1OrderPlusRecip);
 514 }
 515
 516 /*
 517  * Obtain a malloc'd curveParams for a specified feeDepth.
 518  */
 519 curveParams *curveParamsForDepth(feeDepth depth)
 520 {
 521         curveParams *cp;
 522         const curveParamsStatic *cps = &curveParamsArray[depth];
 523
 524         if(depth > FEE_DEPTH_MAX) {
 525                 return NULL;
 526         }
 527
 528         cp = newCurveParams();
 529         cp->primeType = cps->primeType;
 530         cp->curveType = cps->curveType;
 531         cp->q = cps->q;
 532         cp->k = cps->k;
 533         cp->m = cps->m;
 534         if(cp->primeType == FPT_General) {
 535             cp->basePrime = arrayToGiant(cps->basePrime);
 536         }
 537         cp->a = arrayToGiant(cps->a);
 538         cp->b = arrayToGiant(cps->b);
 539         cp->c = arrayToGiant(cps->c);
 540         cp->x1Plus  = arrayToGiant(cps->x1Plus);
 541         if(cps->y1Plus) {
 542                 cp->y1Plus = arrayToGiant(cps->y1Plus);
 543         }
 544         if(cps->x1Minus) {
 545                 cp->x1Minus = arrayToGiant(cps->x1Minus);
 546         }
 547         cp->cOrderPlus   = arrayToGiant(cps->cOrderPlus);
 548         if(cps->cOrderMinus) {
 549                 cp->cOrderMinus  = arrayToGiant(cps->cOrderMinus);
 550         }
 551         cp->x1OrderPlus  = arrayToGiant(cps->x1OrderPlus);
 552         if(cps->x1OrderMinus) {
 553                 cp->x1OrderMinus = arrayToGiant(cps->x1OrderMinus);
 554         }
 555         cp->x1OrderPlusRecip = arrayToGiant(cps->x1OrderPlusRecip);
 556
 557         /*
 558          * Special case optimization for equal reciprocals.
 559          */
 560         if(cps->lesserX1OrderRecip == NULL) {
 561             cp->lesserX1OrderRecip = cp->x1OrderPlusRecip;
 562         }
 563         else {
 564             cp->lesserX1OrderRecip = arrayToGiant(cps->lesserX1OrderRecip);
 565         }
 566
 567         /* remainder calculated at runtime */
 568         curveParamsInferFields(cp);
 569         return cp;
 570 }
 571
 572 /*
 573  * Alloc a new curveParams struct as a copy of specified instance.
 574  * This is the only way we can create a curveParams struct which doesn't
 575  * match any existing known curve params.
 576  */
 577 curveParams *curveParamsCopy(curveParams *cp)
 578 {
 579         curveParams *newcp = newCurveParams();
 580
 581         newcp->primeType = cp->primeType;
 582         newcp->curveType = cp->curveType;
 583         newcp->q = cp->q;
 584         newcp->k = cp->k;
 585         newcp->m = cp->m;
 586         newcp->basePrime = copyGiant(cp->basePrime);
 587         newcp->minBytes = cp->minBytes;
 588         newcp->maxDigits = cp->maxDigits;
 589
 590         newcp->a            = copyGiant(cp->a);
 591         newcp->b            = copyGiant(cp->b);
 592         newcp->c            = copyGiant(cp->c);
 593         newcp->x1Plus       = copyGiant(cp->x1Plus);
 594         if(cp->x1Minus) {
 595                 newcp->x1Minus  = copyGiant(cp->x1Minus);
 596         }
 597         newcp->y1Plus       = copyGiant(cp->y1Plus);
 598         newcp->cOrderPlus   = copyGiant(cp->cOrderPlus);
 599         if(cp->cOrderMinus) {
 600                 newcp->cOrderMinus  = copyGiant(cp->cOrderMinus);
 601         }
 602         newcp->x1OrderPlus  = copyGiant(cp->x1OrderPlus);
 603         if(cp->x1OrderMinus) {
 604                 newcp->x1OrderMinus = copyGiant(cp->x1OrderMinus);
 605         }
 606
 607         newcp->x1OrderPlusRecip = copyGiant(cp->x1OrderPlusRecip);
 608         if(cp->x1OrderPlusRecip == cp->lesserX1OrderRecip) {
 609                 /*
 610                  * Equal reciprocals; avoid new malloc
 611                  */
 612                 newcp->lesserX1OrderRecip = newcp->x1OrderPlusRecip;
 613         }
 614         else {
 615                 newcp->lesserX1OrderRecip = copyGiant(cp->lesserX1OrderRecip);
 616         }
 617         if(cp->primeType == FPT_General) {
 618                 newcp->basePrimeRecip = copyGiant(cp->basePrimeRecip);
 619         }
 620         return newcp;
 621 }
 622
 623 /*
 624  * Free a curveParams struct.
 625  */
 626 void freeCurveParams(curveParams *cp)
 627 {
 628         if(cp->basePrime != NULL) {
 629                 freeGiant(cp->basePrime);
 630         }
 631         if(cp->a != NULL) {
 632                 freeGiant(cp->a);
 633         }
 634         if(cp->b != NULL) {
 635                 freeGiant(cp->b);
 636         }
 637         if(cp->c != NULL) {
 638                 freeGiant(cp->c);
 639         }
 640         if(cp->x1Plus != NULL) {
 641                 freeGiant(cp->x1Plus);
 642         }
 643         if(cp->x1Minus != NULL) {
 644                 freeGiant(cp->x1Minus);
 645         }
 646         if(cp->y1Plus != NULL) {
 647                 freeGiant(cp->y1Plus);
 648         }
 649         if(cp->cOrderPlus != NULL) {
 650                 freeGiant(cp->cOrderPlus);
 651         }
 652         if(cp->cOrderMinus != NULL) {
 653                 freeGiant(cp->cOrderMinus);
 654         }
 655         if(cp->x1OrderPlus != NULL) {
 656                 freeGiant(cp->x1OrderPlus);
 657         }
 658         if(cp->x1OrderMinus != NULL) {
 659                 freeGiant(cp->x1OrderMinus);
 660         }
 661         if(cp->x1OrderPlusRecip != NULL) {
 662                 freeGiant(cp->x1OrderPlusRecip);
 663         }
 664
 665         /*
 666          * Special case - if these are equal, we only alloc'd one giant
 667          */
 668         if(cp->lesserX1OrderRecip != cp->x1OrderPlusRecip) {
 669                 freeGiant(cp->lesserX1OrderRecip);
 670         }
 671         if(cp->basePrimeRecip != NULL) {
 672                 freeGiant(cp->basePrimeRecip);
 673         }
 674         ffree(cp);
 675 }
 676
 677 /*
 678  * Returns 1 if two sets of curve parameters are equivalent, else returns 0.
 679  */
 680 int curveParamsEquivalent(curveParams *cp1, curveParams *cp2)
 681 {
 682         if(cp1 == cp2) {
 683                 /*
 684                  * Trivial case, actually common for signature verify
 685                  */
 686                 return 1;
 687         }
 688         if(cp1->primeType != cp2->primeType) {
 689                 return 0;
 690         }
 691         if(cp1->curveType != cp2->curveType) {
 692                 return 0;
 693         }
 694         if(cp1->k != cp2->k) {
 695                 return 0;
 696         }
 697         if(cp1->q != cp2->q) {
 698                 return 0;
 699         }
 700         if(cp1->m != cp2->m) {
 701                 return 0;
 702         }
 703         if(gcompg(cp1->basePrime, cp2->basePrime)) {
 704                 return 0;
 705         }
 706         if(gcompg(cp1->a, cp2->a)) {
 707                 return 0;
 708         }
 709         if(gcompg(cp1->b, cp2->b)) {
 710                 return 0;
 711         }
 712         if(gcompg(cp1->c, cp2->c)) {
 713                 return 0;
 714         }
 715         if(gcompg(cp1->x1Plus, cp2->x1Plus)) {
 716                 return 0;
 717         }
 718         if((cp1->x1Minus != NULL) && (cp2->x1Minus != NULL)) {
 719                 if(gcompg(cp1->x1Minus, cp2->x1Minus)) {
 720                         return 0;
 721                 }
 722         }
 723         if(gcompg(cp1->cOrderPlus, cp2->cOrderPlus)) {
 724                 return 0;
 725         }
 726         if((cp1->cOrderMinus != NULL) && (cp2->cOrderMinus != NULL)) {
 727                 if(gcompg(cp1->cOrderMinus, cp2->cOrderMinus)) {
 728                         return 0;
 729                 }
 730         }
 731         if(gcompg(cp1->x1OrderPlus, cp2->x1OrderPlus)) {
 732                 return 0;
 733         }
 734         if((cp1->x1OrderMinus != NULL) && (cp2->x1OrderMinus != NULL)) {
 735                 if(gcompg(cp1->x1OrderMinus, cp2->x1OrderMinus)) {
 736                         return 0;
 737                 }
 738         }
 739         /*
 740          * If we got this far, reciprocals can't possibly be different
 741          */
 742         return 1;
 743 }
 744
 745 /*
 746  * Obtain the lesser of {x1OrderPlus, x1OrderMinus}. Returned value is not
 747  * malloc'd; it's a pointer to one of the orders in *cp.
 748  */
 749 giant lesserX1Order(curveParams *cp)
 750 {
 751         CKASSERT(!isZero(cp->x1OrderPlus));
 752
 753         if(cp->x1OrderMinus == NULL) {
 754             return(cp->x1OrderPlus);
 755         }
 756         else if(gcompg(cp->x1OrderPlus, cp->x1OrderMinus) >= 0) {
 757             return(cp->x1OrderMinus);
 758         }
 759         else {
 760             return(cp->x1OrderPlus);
 761         }
 762 }
 763
 764
 765 /*
 766  * Infer the following fields from a partially constructed curveParams:
 767  *
 768  *   basePrimeRecip if primeType == FPT_General
 769  *   basePrime if primeType != FPT_General
 770  *   y1Plus if curveType == FCT_Weierstrass and not pre-calculated
 771  *   minBytes
 772  *   maxDigits
 773  *
 774  * Assumes the following valid on entry:
 775  *   curveType
 776  *   primeType
 777  *   basePrime if primeType == FPT_General
 778  *   q, k if primeType != FPT_General
 779  */
 780 void curveParamsInferFields(curveParams *cp)
 781 {
 782         /* calc maxDigits, minBytes */
 783         calcGiantSizes(cp);
 784
 785         /* basePrime or its reciprocal */
 786         if(cp->primeType == FPT_General) {
 787                 /* FIXME this should be declared statically! */
 788             cp->basePrimeRecip = newGiant(cp->maxDigits);
 789             make_recip(cp->basePrime, cp->basePrimeRecip);
 790         }
 791         else {
 792             /*
 793              * FPT_FEE, FPT_Mersenne
 794              */
 795             cp->basePrime = newGiant(cp->maxDigits);
 796             make_base_prim(cp);
 797         }
 798
 799         /* y1Plus */
 800         if(cp->curveType == FCT_Weierstrass) {
 801                 if(cp->y1Plus == NULL) {
 802                         /* ECDSA Curves already have this */
 803                         pointProj pt = newPointProj(cp->maxDigits);
 804                         findPointProj(pt, cp->x1Plus, cp);
 805
 806                         /* initial point is supposed to be on curve! */
 807                         if(gcompg(pt->x, cp->x1Plus)) {
 808                                 CKRaise("curveParamsInferFields failure");
 809                         }
 810                         cp->y1Plus = copyGiant(pt->y);
 811                         freePointProj(pt);
 812                 }
 813         }
 814         else {
 815                 cp->y1Plus = newGiant(1);
 816         }
 817
 818
 819         if((cp->x1OrderPlusRecip == NULL) || isZero(cp->x1OrderPlusRecip)) {
 820                 /*
 821                  * an easy way of figuring this one out, this should not
 822                  * normally run.
 823                  */
 824                 cp->x1OrderPlusRecip = newGiant(cp->maxDigits);
 825                 make_recip(cp->x1OrderPlus, cp->x1OrderPlusRecip);
 826                 if(cp->lesserX1OrderRecip != NULL) {
 827                         freeGiant(cp->lesserX1OrderRecip);
 828                 }
 829                 cp->lesserX1OrderRecip = cp->x1OrderPlusRecip;
 830         }
 831 }
 832
 833 /*
 834  * Given key size in bits, obtain the asssociated depth.
 835  * Returns FR_IllegalDepth if specify key size not found
 836  * in current curve tables.
 837  */
 838 #define LOG_DEPTH       0
 839
 840 feeReturn feeKeyBitsToDepth(unsigned keySize,
 841         feePrimeType primeType,         /* FPT_Fefault means "best one" */
 842         feeCurveType curveType,         /* FCT_Default means "best one" */
 843         feeDepth *depth)
 844 {
 845         feeReturn frtn = FR_Success;
 846         switch(keySize) {
 847             case 31:
 848                         if(primeType == FPT_General) {
 849                                 return FR_IllegalDepth;
 850                         }
 851                         /* note we cut a request for FPT_FEE some slack...this is actually
 852                          * FPT_Mersenne, but that is technically a subset of FEE. */
 853                         switch(curveType) {
 854                                 case FCT_Montgomery:
 855                                         *depth = FEE_DEPTH_31M;
 856                                         break;
 857                                 case FCT_Weierstrass:
 858                                 case FCT_Default:
 859                                         *depth = FEE_DEPTH_31W;
 860                                         break;
 861                                 default:
 862                                         return FR_IllegalDepth;
 863                         }
 864                         break;
 865                 case 127:
 866                         /* Montgomery only */
 867                         if(primeType == FPT_General) {
 868                                 return FR_IllegalDepth;
 869                         }
 870                         /* note we cut a request for FPT_FEE some slack...this is actually
 871                          * FPT_Mersenne, but that is technically a subset of FEE. */
 872                         switch(curveType) {
 873                                 case FCT_Montgomery:
 874                                 case FCT_Default:
 875                                         *depth = FEE_DEPTH_127M;
 876                                         break;
 877                                 case FCT_Weierstrass:
 878                                 default:
 879                                         return FR_IllegalDepth;
 880                         }
 881                         break;
 882                 case 128:
 883                         /* Weierstrass/feemod only */
 884                         switch(primeType) {
 885                                 case FPT_General:
 886                                 case FPT_Mersenne:
 887                                         return FR_IllegalDepth;
 888                                 default:
 889                                         /* FPT_Default, FPT_FEE */
 890                                         break;
 891                         }
 892                         switch(curveType) {
 893                                 case FCT_Weierstrass:
 894                                 case FCT_Default:
 895                                         *depth = FEE_DEPTH_128W;
 896                                         break;
 897                                 default:
 898                                         return FR_IllegalDepth;
 899                         }
 900                         break;
 901                 case 161:
 902                         switch(curveType) {
 903                                 case FCT_Weierstrass:
 904                                 case FCT_Default:
 905                                         switch(primeType) {
 906                                                 case FPT_General:
 907                                                         *depth = FEE_DEPTH_161G;
 908                                                         break;
 909                                                 case FPT_FEE:
 910                                                 case FPT_Default:
 911                                                         *depth = FEE_DEPTH_161W;
 912                                                         break;
 913                                                 default:
 914                                                         /* i.e., FPT_Mersenne */
 915                                                         return FR_IllegalDepth;
 916                                         }
 917                                         break;
 918                                 default:
 919                                         return FR_IllegalDepth;
 920                         }
 921                         break;
 922                 case 192:
 923                         switch(curveType) {
 924                                 case FCT_Montgomery:
 925                                 default:
 926                                         return FR_IllegalDepth;
 927                                 case FCT_Weierstrass:
 928                                 case FCT_Default:
 929                                         switch(primeType) {
 930                                                 case FPT_General:
 931                                                 case FPT_Default:
 932                                                         *depth = FEE_DEPTH_192G;
 933                                                         break;
 934                                                 default:
 935                                                         /* i.e., FPT_Mersenne, FPT_FEE */
 936                                                         return FR_IllegalDepth;
 937                                         }
 938                                         break;
 939                                 case FCT_ANSI:
 940                                         switch(primeType) {
 941                                                 case FPT_General:
 942                                                 case FPT_Default:
 943                                                         break;
 944                                                 default:
 945                                                         return FR_IllegalDepth;
 946                                         }
 947                                         *depth = FEE_DEPTH_secp192r1;
 948                                         break;
 949                         }
 950                         break;
 951                 case 256:
 952                         switch(curveType) {
 953                                 case FCT_ANSI:
 954                                 case FCT_Default:
 955                                         break;
 956                                 default:
 957                                         return FR_IllegalDepth;
 958                         }
 959                         switch(primeType) {
 960                                 case FPT_General:
 961                                 case FPT_Default:
 962                                         break;
 963                                 default:
 964                                         return FR_IllegalDepth;
 965                         }
 966                         *depth = FEE_DEPTH_secp256r1;
 967                         break;
 968                 case 384:
 969                         switch(curveType) {
 970                                 case FCT_ANSI:
 971                                 case FCT_Default:
 972                                         break;
 973                                 default:
 974                                         return FR_IllegalDepth;
 975                         }
 976                         switch(primeType) {
 977                                 case FPT_General:
 978                                 case FPT_Default:
 979                                         break;
 980                                 default:
 981                                         return FR_IllegalDepth;
 982                         }
 983                         *depth = FEE_DEPTH_secp384r1;
 984                         break;
 985                 case 521:
 986                         switch(curveType) {
 987                                 case FCT_ANSI:
 988                                 case FCT_Default:
 989                                         break;
 990                                 default:
 991                                         return FR_IllegalDepth;
 992                         }
 993                         switch(primeType) {
 994                                 case FPT_General:
 995                                 case FPT_Default:
 996                                         break;
 997                                 default:
 998                                         return FR_IllegalDepth;
 999                         }
1000                         *depth = FEE_DEPTH_secp521r1;
1001                         break;
1002
1003                 default:
1004                         frtn = FR_IllegalDepth;
1005                         break;
1006         }
1007         #if LOG_DEPTH
1008         printf("feeKeyBitsToDepth: depth %d\n", *depth);
1009         #endif
1010         return frtn;
1011 }
1012
1013 /*
1014  * Obtain depth for specified curveParams
1015  */
1016 feeReturn curveParamsDepth(
1017         curveParams *cp,
1018         feeDepth *depth)
1019 {
1020         if(cp == NULL) {
1021                 return FR_IllegalArg;
1022         }
1023
1024         /* We do it this way to allow reconstructing depth from an encoded curveParams */
1025         feeCurveType curveType = cp->curveType;
1026         if((curveType == FCT_Weierstrass) && (cp->x1Minus == NULL)) {
1027                 /* actually an ANSI curve */
1028                 curveType = FCT_ANSI;
1029         }
1030         return feeKeyBitsToDepth(cp->q, cp->primeType, curveType, depth);
1031 }
1032
1033