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 46typedef unsigned short arrayDigit; 47 48static 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 */ 63typedef 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 */ 93static const arrayDigit ga_666[] = {1, 666 }; // a common value for 'c' 94static const arrayDigit ga_zero[] = {1, 0 }; // (giant)0 95static 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#if FEE_PROTOTYPE_CURVES 104#include "curveParamDataOld.h" 105#else 106#include "curveParamData.h" 107#endif 108 109/* 110 * Now the curveParamsStatic structs, which provide templates for creating the 111 * fields in a specific curveParams struct. 112 * 113 * All giants in a curveParamsStatic struct except for basePrime are 114 * guaranteed valid. 115 * 116 * Note these are stored as an array, an index into which is a feeDepth 117 * parameter. 118 */ 119#if FEE_PROTOTYPE_CURVES 120static curveParamsStatic curveParamsArray[] = { 121 { // depth=0 122 FPT_Mersenne, 123 FCT_Weierstrass, 124 31, 1, // q=31, k=1 125 NULL, // basePrime only used for FPT_General 126 1, // m = 1 127 ga_w31_1_a, // a = 7 128 ga_one, // b = 1 129 ga_zero, // c = 0 130 ga_w31_1_x1Plus, 131 NULL, // y1Plus 132 ga_w31_1_x1Minus, 133 ga_w31_1_plusOrder, 134 ga_w31_1_minusOrder, 135 ga_w31_1_x1OrderPlus, 136 ga_w31_1_x1OrderMinus, 137 ga_w31_1_x1OrderPlusRecip, 138 ga_w31_1_lesserX1OrderRecip 139 }, 140 { // depth=1 141 FPT_Mersenne, 142 FCT_Montgomery, 143 31, 1, // q=31, k=1 144 NULL, 145 1, // m = 1 146 ga_one, // a = 1 147 ga_zero, // b = 0 148 ga_666, // c = 666 149 ga_m31_1_x1Plus, 150 NULL, // y1Plus 151 ga_m31_1_x1Minus, 152 ga_m31_1_plusOrder, 153 ga_m31_1_minusOrder, 154 ga_m31_1_x1OrderPlus, 155 ga_m31_1_x1OrderMinus, 156 ga_m31_1_x1OrderPlusRecip, 157 ga_m31_1_lesserX1OrderRecip 158 159 }, 160 { // depth=2 161 FPT_Mersenne, 162 FCT_Weierstrass, 163 31, 1, // q=31, k=1, prime curve orders 164 NULL, 165 1, // m = 1 166 ga_31_1P_a, // a = 5824692 167 ga_31_1P_b, // b = 2067311435 168 ga_zero, // c = 0 169 ga_31_1P_x1Plus, 170 NULL, // y1Plus 171 ga_31_1P_x1Minus, 172 ga_31_1P_plusOrder, 173 ga_31_1P_minusOrder, 174 ga_31_1P_x1OrderPlus, 175 ga_31_1P_x1OrderMinus, 176 ga_31_1P_x1OrderPlusRecip, 177 NULL // x1PlusOrder is lesser 178 179 }, 180 { // depth=3 181 FPT_FEE, 182 FCT_Weierstrass, 183 40, 213, // q=40, k=213, prime curve orders 184 NULL, 185 1, // m = 1 186 ga_40_213_a, // a = 1627500953 187 ga_40_213_b, // b = 523907505 188 ga_zero, // c = 0 189 ga_40_213_x1Plus, 190 NULL, // y1Plus 191 ga_40_213_x1Minus, 192 ga_40_213_plusOrder, 193 ga_40_213_minusOrder, 194 ga_40_213_x1OrderPlus, 195 ga_40_213_x1OrderMinus, 196 ga_40_213_x1OrderPlusRecip, 197 ga_40_213_lesserX1OrderRecip 198 199 }, 200 { // depth=4 201 FPT_Mersenne, 202 FCT_Montgomery, 203 127, 1, 204 NULL, 205 1, // m = 1 206 ga_one, // a = 1 207 ga_zero, // b = 0 208 ga_666, // c = 666 209 ga_127_1_x1Plus, 210 NULL, // y1Plus 211 ga_127_1_x1Minus, 212 ga_127_1_plusOrder, 213 ga_127_1_minusOrder, 214 ga_127_1_x1OrderPlus, 215 ga_127_1_x1OrderMinus, 216 ga_127_1_x1OrderPlusRecip, 217 ga_127_1_lesserX1OrderRecip 218 219 }, 220 { // depth=5 221 FPT_Mersenne, 222 FCT_Weierstrass, 223 127, 1, // q=127, k=1 Weierstrass 224 NULL, 225 1, // m = 1 226 ga_666, // a = 666 227 ga_one, // b = 1 228 ga_zero, // c = 0 229 ga_127_1W_x1Plus, 230 NULL, // y1Plus 231 ga_127_1W_x1Minus, 232 ga_127_1W_plusOrder, 233 ga_127_1W_minusOrder, 234 ga_127_1W_x1OrderPlus, 235 ga_127_1W_x1OrderMinus, 236 ga_127_1W_x1OrderPlusRecip, 237 NULL // x1PlusOrder is lesser 238 239 }, 240 { // depth=6 241 FPT_FEE, 242 FCT_Weierstrass, // also Atkin3 243 160, 57, 244 NULL, 245 1, // m = 1 246 ga_zero, // a = 0 247 ga_160_57_b, // b = 3 248 ga_zero, // c = 0 249 ga_160_57_x1Plus, 250 NULL, // y1Plus 251 ga_160_57_x1Minus, 252 ga_160_57_plusOrder, 253 ga_160_57_minusOrder, 254 ga_160_57_x1OrderPlus, 255 ga_160_57_x1OrderMinus, 256 ga_160_57_x1OrderPlusRecip, 257 NULL // x1PlusOrder is lesser 258 }, 259 { // depth=7 260 FPT_FEE, 261 FCT_Weierstrass, // also Atkin3 262 192, 1425, 263 NULL, 264 1, // m = 1 265 ga_zero, // a = 0 266 ga_192_1425_b, // b = -11 267 ga_zero, // c = 0 268 ga_192_1425_x1Plus, 269 NULL, // y1Plus 270 ga_192_1425_x1Minus, 271 ga_192_1425_plusOrder, 272 ga_192_1425_minusOrder, 273 ga_192_1425_x1OrderPlus, 274 ga_192_1425_x1OrderMinus, 275 ga_192_1425_x1OrderPlusRecip, 276 NULL // x1PlusOrder is lesser 277 278 }, 279 { // depth=8 280 FPT_FEE, 281 FCT_Weierstrass, 282 192, -529891, 283 NULL, 284 1, // m = 1 285 ga_192_M529891_a, // a = -152 286 ga_192_M529891_b, // b = 722 287 ga_zero, // c = 0 288 ga_192_M529891_x1Plus, 289 NULL, // y1Plus 290 ga_192_M529891_x1Minus, 291 ga_192_M529891_plusOrder, 292 ga_192_M529891_minusOrder, 293 ga_192_M529891_x1OrderPlus, 294 ga_192_M529891_x1OrderMinus, 295 ga_192_M529891_x1OrderPlusRecip, 296 ga_192_M529891_lesserX1OrderRecip 297 298 }, 299 /* 300 * FPT_General curves, currently just copies of known FPT_FEE or FPT_Mersenne 301 * curves with primeType set to FPT_General. These are just for 302 * verification the general curve are handled properly. 303 * We include the q parameter here for use by feeKeyBitsToDepth(). 304 */ 305 { // depth=9 306 FPT_General, 307 FCT_General, 308 127, 0, 309 ga_127_1_bp, // explicit basePrime 310 1, // m = 1 311 ga_one, // a = 1 312 ga_zero, // b = 0 313 ga_666, // c = 666 314 ga_127_1_x1Plus, 315 NULL, // y1Plus 316 ga_127_1_x1Minus, 317 ga_127_1_plusOrder, 318 ga_127_1_minusOrder, 319 ga_127_1_x1OrderPlus, 320 ga_127_1_x1OrderMinus, 321 ga_127_1_x1OrderPlusRecip, 322 ga_127_1_lesserX1OrderRecip 323 324 }, 325 326 { // depth=10, FPT_General version of q=160 327 FPT_General, 328 FCT_Weierstrass, 329 160, 0, // we don't use these... 330 ga_160_57_bp, // explicit basePrime 331 1, // m = 1 332 ga_zero, // a = 0 333 ga_160_57_b, // b = 3 334 ga_zero, 335 ga_160_57_x1Plus, 336 NULL, // y1Plus 337 ga_160_57_x1Minus, 338 ga_160_57_plusOrder, 339 ga_160_57_minusOrder, 340 ga_160_57_x1OrderPlus, 341 ga_160_57_x1OrderMinus, 342 ga_160_57_x1OrderPlusRecip, 343 NULL // x1PlusOrder is lesser 344 }, 345 346 { // depth=11, FPT_General, 161 bits 347 FPT_General, 348 FCT_Weierstrass, 349 //161, 0, 350 161, 0, // for verifying we don't use these... 351 ga_161_gen_bp, // explicit basePrime 352 1, // m = 1 353 ga_161_gen_a, // a = -152 354 ga_161_gen_b, // b = 722 355 ga_zero, // c = 0 356 ga_161_gen_x1Plus, 357 NULL, // y1Plus 358 ga_161_gen_x1Minus, 359 ga_161_gen_plusOrder, 360 ga_161_gen_minusOrder, 361 ga_161_gen_x1OrderPlus, 362 ga_161_gen_x1OrderMinus, 363 ga_161_gen_x1OrderPlusRecip, 364 NULL // x1PlusOrder is lesser 365 }, 366 367}; 368 369#else /* FEE_PROTOTYPE_CURVES */ 370 371static const curveParamsStatic curveParamsArray[] = { 372{ 373 /* 374 * depth = 0 375 * FEE CURVE: USE FOR FEE SIG. & FEED ONLY. 376 * primeType->Mersenne 377 * curveType->Montgomery 378 * q = 31; k = 1; p = 2^q - k; 379 * a = 1; b = 0; c = 666; 380 * Both orders composite. 381 */ 382 FPT_Mersenne, 383 FCT_Montgomery, 384 31, 1, // q=31, k=1 385 NULL, // basePrime only used for FPT_General 386 1, // m = 1 387 ga_one, // a = 1 388 ga_zero, // b = 0 389 ga_666, // c = 666 390 ga_31m_x1Plus, 391 NULL, // y1Plus 392 ga_31m_x1Minus, 393 ga_31m_plusOrder, 394 ga_31m_minusOrder, 395 ga_31m_x1OrderPlus, 396 ga_31m_x1OrderMinus, 397 ga_31m_x1OrderPlusRecip, 398 ga_31m_lesserX1OrderRecip 399}, 400{ 401 /* 402 * depth = 1 403 * IEEE P1363 COMPATIBLE. 404 * primeType->Mersenne 405 * curveType->Weierstrass 406 * q = 31; k = 1; p = 2^q-k; 407 * a = 5824692 b = 2067311435 c = 0 408 * Both orders prime. 409 */ 410 FPT_Mersenne, 411 FCT_Weierstrass, 412 31, 1, // q=31, k=1 413 NULL, // basePrime only used for FPT_General 414 1, // m = 1 415 ga_31w_a, 416 ga_31w_b, 417 ga_zero, // c = 0 418 ga_31w_x1Plus, 419 NULL, // y1Plus 420 ga_31w_x1Minus, 421 ga_31w_plusOrder, 422 ga_31w_minusOrder, 423 ga_31w_x1OrderPlus, 424 ga_31w_x1OrderMinus, 425 ga_31w_x1OrderPlusRecip, 426 NULL // x1PlusOrder is lesser 427}, 428{ 429 /* 430 * depth = 2 431 * FEE CURVE: USE FOR FEE SIG. & FEED ONLY. 432 * primeType->Mersenne 433 * curveType->Montgomery 434 * q = 127; k = 1; p = 2^q - k; 435 * a = 1; b = 0; c = 666; 436 * Both orders composite. 437 */ 438 FPT_Mersenne, 439 FCT_Montgomery, 440 127, 1, // q = 127; k = 1 441 NULL, // basePrime only used for FPT_General 442 1, // m = 1 443 ga_one, 444 ga_zero, 445 ga_666, 446 ga_127m_x1Plus, 447 NULL, // y1Plus 448 ga_127m_x1Minus, 449 ga_127m_plusOrder, 450 ga_127m_minusOrder, 451 ga_127m_x1OrderPlus, 452 ga_127m_x1OrderMinus, 453 ga_127m_x1OrderPlusRecip, 454 ga_127m_lesserX1OrderRecip 455}, 456{ 457 /* 458 * depth = 3 459 * IEEE P1363 COMPATIBLE. 460 * primeType->feemod 461 * curveType->Weierstrass 462 * q = 127; k = -57675; p = 2^q - k; 463 * a = 170141183460469025572049133804586627403; 464 * b = 170105154311605172483148226534443139403; c = 0; 465 * Both orders prime. 466 */ 467 FPT_FEE, 468 FCT_Weierstrass, 469 127, -57675, // q = 127; k = -57675 470 NULL, // basePrime only used for FPT_General 471 1, // m = 1 472 ga_128w_a, 473 ga_128w_b, 474 ga_zero, 475 ga_128w_x1Plus, 476 NULL, // y1Plus 477 ga_128w_x1Minus, 478 ga_128w_plusOrder, 479 ga_128w_minusOrder, 480 ga_128w_x1OrderPlus, 481 ga_128w_x1OrderMinus, 482 ga_128w_x1OrderPlusRecip, 483 /* REC said NULL, dmitch says: */ 484 ga_128w_lesserX1OrderRecip // x1PlusOrder is lesser 485}, 486{ 487 /* 488 * depth = 4 489 * IEEE P1363 COMPATIBLE. 490 * primeType->feemod 491 * curveType->Weierstrass 492 * q = 160; k = -5875; p = 2^q - k; 493 * a = 1461501637330902918203684832716283019448563798259; 494 * b = 36382017816364032; c = 0; 495 * Both orders prime.: 496 */ 497 FPT_FEE, 498 FCT_Weierstrass, 499 160, -5875, // q = 160; k = -5875 500 NULL, // basePrime only used for FPT_General 501 1, // m = 1 502 ga_161w_a, 503 ga_161w_b, 504 ga_zero, 505 ga_161w_x1Plus, 506 NULL, // y1Plus 507 ga_161w_x1Minus, 508 ga_161w_plusOrder, 509 ga_161w_minusOrder, 510 ga_161w_x1OrderPlus, 511 ga_161w_x1OrderMinus, 512 ga_161w_x1OrderPlusRecip, 513 /* dmitch addenda - REC said NULL */ 514 ga_161w_lesserX1OrderRecip 515}, 516{ 517 /* 518 * depth = 5 519 * IEEE P1363 COMPATIBLE. 520 * primeType->General 521 * curveType->Weierstrass 522 * p is a 161-bit random prime (below, ga_161_gen_bp[]); 523 * a = -152; b = 722; c = 0; 524 * Both orders composite. 525 */ 526 FPT_General, 527 FCT_Weierstrass, 528 161, 0, // not used 529 ga_161_gen_bp, // basePrime 530 1, // m = 1 531 ga_161_gen_a, 532 ga_161_gen_b, 533 ga_zero, 534 ga_161_gen_x1Plus, 535 NULL, // y1Plus 536 ga_161_gen_x1Minus, 537 ga_161_gen_plusOrder, 538 ga_161_gen_minusOrder, 539 ga_161_gen_x1OrderPlus, 540 ga_161_gen_x1OrderMinus, 541 ga_161_gen_x1OrderPlusRecip, 542 NULL // x1PlusOrder is lesser 543}, 544{ 545 /* 546 * depth = 6 547 * IEEE P1363 COMPATIBLE. 548 * (NIST-P-192 RECOMMENDED PRIME) 549 * primeType->General 550 * curveType->Weierstrass 551 * p is a 192-bit random prime (below, ga_161_gen_bp[]); 552 * a = -3; 553 * b = 2455155546008943817740293915197451784769108058161191238065; 554 * c = 0; 555 * Plus-order is prime, minus-order is composite. 556 */ 557 FPT_General, 558 FCT_Weierstrass, 559 192, 0, // only used for initGiantStacks(giantMaxDigits()) 560 ga_192_gen_bp, // basePrime 561 1, // m = 1 562 ga_192_gen_a, 563 ga_192_gen_b, 564 ga_zero, 565 ga_192_gen_x1Plus, 566 NULL, // y1Plus 567 ga_192_gen_x1Minus, 568 ga_192_gen_plusOrder, 569 ga_192_gen_minusOrder, 570 ga_192_gen_x1OrderPlus, 571 ga_192_gen_x1OrderMinus, 572 ga_192_gen_x1OrderPlusRecip, 573 ga_192_gen_lesserX1OrderRecip 574}, 575 576/* ANSI X9.62/Certicom curves */ 577{ 578 /* 579 * depth = 7 580 * ANSI X9.62/Certicom secp192r1 581 */ 582 FPT_General, 583 FCT_Weierstrass, 584 192, 0, // only used for initGiantStacks(giantMaxDigits()) 585 ga_192_secp_bp, // basePrime 586 1, // m = 1 587 ga_192_secp_a, 588 ga_192_secp_b, 589 ga_zero, 590 ga_192_secp_x1Plus, 591 ga_192_secp_y1Plus, 592 NULL, // x1Minus 593 ga_192_secp_plusOrder, 594 NULL, // minusOrder, 595 ga_192_secp_x1OrderPlus, 596 NULL, // x1OrderMinus, 597 ga_192_secp_x1OrderPlusRecip, 598}, 599{ 600 /* 601 * depth = 8 602 * ANSI X9.62/Certicom secp256r1 603 */ 604 FPT_General, 605 FCT_Weierstrass, 606 256, 0, // only used for initGiantStacks(giantMaxDigits()) 607 ga_256_secp_bp, // basePrime 608 1, // m = 1 609 ga_256_secp_a, 610 ga_256_secp_b, 611 ga_zero, 612 ga_256_secp_x1Plus, 613 ga_256_secp_y1Plus, 614 NULL, 615 ga_256_secp_plusOrder, 616 NULL, 617 ga_256_secp_x1OrderPlus, 618 NULL, 619 ga_256_secp_x1OrderPlusRecip, 620 NULL 621}, 622{ 623 /* 624 * depth = 9 625 * ANSI X9.62/Certicom secp384r1 626 */ 627 FPT_General, 628 FCT_Weierstrass, 629 384, 0, // only used for initGiantStacks(giantMaxDigits()) 630 ga_384_secp_bp, // basePrime 631 1, // m = 1 632 ga_384_secp_a, 633 ga_384_secp_b, 634 ga_zero, 635 ga_384_secp_x1Plus, 636 ga_384_secp_y1Plus, 637 NULL, 638 ga_384_secp_plusOrder, 639 NULL, 640 ga_384_secp_x1OrderPlus, 641 NULL, 642 ga_384_secp_x1OrderPlusRecip, 643 NULL 644}, 645{ 646 /* 647 * depth = 10 648 * ANSI X9.62/Certicom secp521r1 649 */ 650 FPT_General, 651 FCT_Weierstrass, 652 521, 0, 653 ga_521_secp_bp, // basePrime 654 1, // m = 1 655 ga_521_secp_a, 656 ga_521_secp_b, 657 ga_zero, 658 ga_521_secp_x1Plus, 659 ga_521_secp_y1Plus, 660 NULL, 661 ga_521_secp_plusOrder, 662 NULL, 663 ga_521_secp_x1OrderPlus, 664 NULL, 665 ga_521_secp_x1OrderPlusRecip, 666 NULL 667} 668}; 669#endif /* FEE_PROTOTYPE_CURVES */ 670 671/* 672 * Convert the static form of a giant - i.e., an array of arrayDigits, 673 * the first of which is the sign, the remainder of which are base 65536 674 * digits - into a giant. A null pointer on input results in a null return. 675 */ 676static giant arrayToGiant(const arrayDigit *array) 677{ 678 unsigned numBytes; // in result->n[] 679 int numDigits; // ditto 680 giant result; 681 giantDigit digit; 682 unsigned char byte; 683 unsigned i; 684 unsigned digitDex; // index into result->n[] 685 unsigned digitByte; // byte selector in digit 686 const arrayDigit *ap; // running ptr into array 687 short sign; 688 689 if(array == NULL) { 690 CKRaise("arrayToGiant: NULL array"); 691 } 692 sign = (short)array[0]; 693 numBytes = abs(sign) * sizeof(unsigned short); 694 numDigits = BYTES_TO_GIANT_DIGITS(numBytes); 695 696 /* note giantstruct has one explicit giantDigit */ 697 result = (giant) fmalloc(sizeof(giantstruct) + 698 ((numDigits - 1) * GIANT_BYTES_PER_DIGIT)); 699 result->capacity = numDigits; 700 701 ap = array + 1; 702 digit = 0; 703 digitDex = 0; 704 705 for(i=0; i<numBytes;) { 706 for(digitByte=0; digitByte<GIANT_BYTES_PER_DIGIT; digitByte++) { 707 /* grab a byte from the array */ 708 if(i & 1) { 709 /* odd byte - snag it and advance to next array digit */ 710 byte = (unsigned char)(*ap++ >> 8); 711 } 712 else { 713 /* even, i.e., l.s. byte */ 714 byte = (unsigned char)(*ap); 715 } 716 717 /* add byte to current digit */ 718 digit |= (byte << (8 * digitByte)); 719 if(++i == numBytes) { 720 /* end of array, perhaps in the midst of a digit */ 721 break; 722 } 723 } 724 result->n[digitDex++] = digit; 725 digit = 0; 726 }; 727 728 /* Careful: 729 * -- array elements are unsigned. The first element is 730 * he number of SHORTS in the array; convert to native 731 * digits. 732 * -- in the very odd (test only) case of giantDigit = unsigned char, 733 * we might have fewer valid digits than numDigits (might have 734 * leading zeros). 735 */ 736 if(sign < 0) { 737 result->sign = -numDigits; 738 } 739 else { 740 result->sign = numDigits; 741 } 742 gtrimSign(result); 743 return result; 744} 745 746/* 747 * Obtain a malloc'd and uninitialized curveParams, to be init'd by caller. 748 */ 749curveParams *newCurveParams(void) 750{ 751 curveParams *params = (curveParams*) fmalloc(sizeof(curveParams)); 752 753 bzero(params, sizeof(curveParams)); 754 return params; 755} 756 757/* 758 * Alloc and zero reciprocal giants, when maxDigits is known. 759 * Currently only called when creating a curveParams from a public key. 760 * cp->primeType must be valid on input. 761 */ 762void allocRecipGiants(curveParams *cp) 763{ 764 cp->lesserX1OrderRecip = newGiant(cp->maxDigits); 765 cp->x1OrderPlusRecip = newGiant(cp->maxDigits); 766 int_to_giant(0, cp->lesserX1OrderRecip); 767 int_to_giant(0, cp->x1OrderPlusRecip); 768} 769 770/* 771 * Obtain a malloc'd curveParams for a specified feeDepth. 772 */ 773curveParams *curveParamsForDepth(feeDepth depth) 774{ 775 curveParams *cp; 776 const curveParamsStatic *cps = &curveParamsArray[depth]; 777 778 if(depth > FEE_DEPTH_MAX) { 779 return NULL; 780 } 781 #if GIANTS_VIA_STACK 782 curveParamsInitGiants(); 783 #endif 784 cp = newCurveParams(); 785 cp->primeType = cps->primeType; 786 cp->curveType = cps->curveType; 787 cp->q = cps->q; 788 cp->k = cps->k; 789 cp->m = cps->m; 790 if(cp->primeType == FPT_General) { 791 cp->basePrime = arrayToGiant(cps->basePrime); 792 } 793 cp->a = arrayToGiant(cps->a); 794 cp->b = arrayToGiant(cps->b); 795 cp->c = arrayToGiant(cps->c); 796 cp->x1Plus = arrayToGiant(cps->x1Plus); 797 if(cps->y1Plus) { 798 cp->y1Plus = arrayToGiant(cps->y1Plus); 799 } 800 if(cps->x1Minus) { 801 cp->x1Minus = arrayToGiant(cps->x1Minus); 802 } 803 cp->cOrderPlus = arrayToGiant(cps->cOrderPlus); 804 if(cps->cOrderMinus) { 805 cp->cOrderMinus = arrayToGiant(cps->cOrderMinus); 806 } 807 cp->x1OrderPlus = arrayToGiant(cps->x1OrderPlus); 808 if(cps->x1OrderMinus) { 809 cp->x1OrderMinus = arrayToGiant(cps->x1OrderMinus); 810 } 811 cp->x1OrderPlusRecip = arrayToGiant(cps->x1OrderPlusRecip); 812 813 /* 814 * Special case optimization for equal reciprocals. 815 */ 816 if(cps->lesserX1OrderRecip == NULL) { 817 cp->lesserX1OrderRecip = cp->x1OrderPlusRecip; 818 } 819 else { 820 cp->lesserX1OrderRecip = arrayToGiant(cps->lesserX1OrderRecip); 821 } 822 823 /* remainder calculated at runtime */ 824 curveParamsInferFields(cp); 825 return cp; 826} 827 828/* 829 * Alloc a new curveParams struct as a copy of specified instance. 830 * This is the only way we can create a curveParams struct which doesn't 831 * match any existing known curve params. 832 */ 833curveParams *curveParamsCopy(curveParams *cp) 834{ 835 curveParams *newcp = newCurveParams(); 836 837 newcp->primeType = cp->primeType; 838 newcp->curveType = cp->curveType; 839 newcp->q = cp->q; 840 newcp->k = cp->k; 841 newcp->m = cp->m; 842 newcp->basePrime = copyGiant(cp->basePrime); 843 newcp->minBytes = cp->minBytes; 844 newcp->maxDigits = cp->maxDigits; 845 846 newcp->a = copyGiant(cp->a); 847 newcp->b = copyGiant(cp->b); 848 newcp->c = copyGiant(cp->c); 849 newcp->x1Plus = copyGiant(cp->x1Plus); 850 if(cp->x1Minus) { 851 newcp->x1Minus = copyGiant(cp->x1Minus); 852 } 853 newcp->y1Plus = copyGiant(cp->y1Plus); 854 newcp->cOrderPlus = copyGiant(cp->cOrderPlus); 855 if(cp->cOrderMinus) { 856 newcp->cOrderMinus = copyGiant(cp->cOrderMinus); 857 } 858 newcp->x1OrderPlus = copyGiant(cp->x1OrderPlus); 859 if(cp->x1OrderMinus) { 860 newcp->x1OrderMinus = copyGiant(cp->x1OrderMinus); 861 } 862 863 newcp->x1OrderPlusRecip = copyGiant(cp->x1OrderPlusRecip); 864 if(cp->x1OrderPlusRecip == cp->lesserX1OrderRecip) { 865 /* 866 * Equal reciprocals; avoid new malloc 867 */ 868 newcp->lesserX1OrderRecip = newcp->x1OrderPlusRecip; 869 } 870 else { 871 newcp->lesserX1OrderRecip = copyGiant(cp->lesserX1OrderRecip); 872 } 873 if(cp->primeType == FPT_General) { 874 newcp->basePrimeRecip = copyGiant(cp->basePrimeRecip); 875 } 876 return newcp; 877} 878 879/* 880 * Free a curveParams struct. 881 */ 882void freeCurveParams(curveParams *cp) 883{ 884 if(cp->basePrime != NULL) { 885 freeGiant(cp->basePrime); 886 } 887 if(cp->a != NULL) { 888 freeGiant(cp->a); 889 } 890 if(cp->b != NULL) { 891 freeGiant(cp->b); 892 } 893 if(cp->c != NULL) { 894 freeGiant(cp->c); 895 } 896 if(cp->x1Plus != NULL) { 897 freeGiant(cp->x1Plus); 898 } 899 if(cp->x1Minus != NULL) { 900 freeGiant(cp->x1Minus); 901 } 902 if(cp->y1Plus != NULL) { 903 freeGiant(cp->y1Plus); 904 } 905 if(cp->cOrderPlus != NULL) { 906 freeGiant(cp->cOrderPlus); 907 } 908 if(cp->cOrderMinus != NULL) { 909 freeGiant(cp->cOrderMinus); 910 } 911 if(cp->x1OrderPlus != NULL) { 912 freeGiant(cp->x1OrderPlus); 913 } 914 if(cp->x1OrderMinus != NULL) { 915 freeGiant(cp->x1OrderMinus); 916 } 917 if(cp->x1OrderPlusRecip != NULL) { 918 freeGiant(cp->x1OrderPlusRecip); 919 } 920 921 /* 922 * Special case - if these are equal, we only alloc'd one giant 923 */ 924 if(cp->lesserX1OrderRecip != cp->x1OrderPlusRecip) { 925 freeGiant(cp->lesserX1OrderRecip); 926 } 927 if(cp->basePrimeRecip != NULL) { 928 freeGiant(cp->basePrimeRecip); 929 } 930 ffree(cp); 931} 932 933/* 934 * Returns 1 if two sets of curve parameters are equivalent, else returns 0. 935 */ 936int curveParamsEquivalent(curveParams *cp1, curveParams *cp2) 937{ 938 if(cp1 == cp2) { 939 /* 940 * Trivial case, actually common for signature verify 941 */ 942 return 1; 943 } 944 if(cp1->primeType != cp2->primeType) { 945 return 0; 946 } 947 if(cp1->curveType != cp2->curveType) { 948 return 0; 949 } 950 if(cp1->k != cp2->k) { 951 return 0; 952 } 953 if(cp1->q != cp2->q) { 954 return 0; 955 } 956 if(cp1->m != cp2->m) { 957 return 0; 958 } 959 if(gcompg(cp1->basePrime, cp2->basePrime)) { 960 return 0; 961 } 962 if(gcompg(cp1->a, cp2->a)) { 963 return 0; 964 } 965 if(gcompg(cp1->b, cp2->b)) { 966 return 0; 967 } 968 if(gcompg(cp1->c, cp2->c)) { 969 return 0; 970 } 971 if(gcompg(cp1->x1Plus, cp2->x1Plus)) { 972 return 0; 973 } 974 if((cp1->x1Minus != NULL) && (cp2->x1Minus != NULL)) { 975 if(gcompg(cp1->x1Minus, cp2->x1Minus)) { 976 return 0; 977 } 978 } 979 if(gcompg(cp1->cOrderPlus, cp2->cOrderPlus)) { 980 return 0; 981 } 982 if((cp1->cOrderMinus != NULL) && (cp2->cOrderMinus != NULL)) { 983 if(gcompg(cp1->cOrderMinus, cp2->cOrderMinus)) { 984 return 0; 985 } 986 } 987 if(gcompg(cp1->x1OrderPlus, cp2->x1OrderPlus)) { 988 return 0; 989 } 990 if((cp1->x1OrderMinus != NULL) && (cp2->x1OrderMinus != NULL)) { 991 if(gcompg(cp1->x1OrderMinus, cp2->x1OrderMinus)) { 992 return 0; 993 } 994 } 995 /* 996 * If we got this far, reciprocals can't possibly be different 997 */ 998 return 1; 999} 1000 1001/* 1002 * Obtain the lesser of {x1OrderPlus, x1OrderMinus}. Returned value is not 1003 * malloc'd; it's a pointer to one of the orders in *cp. 1004 */ 1005giant lesserX1Order(curveParams *cp) 1006{ 1007 CKASSERT(!isZero(cp->x1OrderPlus)); 1008 1009 if(cp->x1OrderMinus == NULL) { 1010 return(cp->x1OrderPlus); 1011 } 1012 else if(gcompg(cp->x1OrderPlus, cp->x1OrderMinus) >= 0) { 1013 return(cp->x1OrderMinus); 1014 } 1015 else { 1016 return(cp->x1OrderPlus); 1017 } 1018} 1019 1020#if GIANTS_VIA_STACK 1021 1022/* 1023 * Prime the curveParams and giants modules for quick allocs of giants. 1024 */ 1025static int giantsInitd = 0; 1026 1027void curveParamsInitGiants(void) 1028{ 1029 const curveParamsStatic *cps = &curveParamsArray[FEE_DEPTH_MAX]; 1030 1031 if(giantsInitd) { 1032 return; 1033 } 1034 1035 /* 1036 * Figure the max giant size of the largest depth we know about... 1037 */ 1038 initGiantStacks(giantMaxDigits(giantMinBytes(cps->q, cps->k))); 1039 giantsInitd = 1; 1040} 1041 1042#endif // GIANTS_VIA_STACK 1043 1044/* 1045 * Infer the following fields from a partially constructed curveParams: 1046 * 1047 * basePrimeRecip if primeType == FPT_General 1048 * basePrime if primeType != FPT_General 1049 * y1Plus if curveType == FCT_Weierstrass and not pre-calculated 1050 * minBytes 1051 * maxDigits 1052 * 1053 * Assumes the following valid on entry: 1054 * curveType 1055 * primeType 1056 * basePrime if primeType == FPT_General 1057 * q, k if primeType != FPT_General 1058 */ 1059void curveParamsInferFields(curveParams *cp) 1060{ 1061 /* calc maxDigits, minBytes */ 1062 calcGiantSizes(cp); 1063 1064 /* basePrime or its reciprocal */ 1065 if(cp->primeType == FPT_General) { 1066 /* FIXME this should be declared statically! */ 1067 cp->basePrimeRecip = newGiant(cp->maxDigits); 1068 make_recip(cp->basePrime, cp->basePrimeRecip); 1069 } 1070 else { 1071 /* 1072 * FPT_FEE, FPT_Mersenne 1073 */ 1074 cp->basePrime = newGiant(cp->maxDigits); 1075 make_base_prim(cp); 1076 } 1077 1078 /* y1Plus */ 1079 #if CRYPTKIT_ELL_PROJ_ENABLE 1080 if(cp->curveType == FCT_Weierstrass) { 1081 if(cp->y1Plus == NULL) { 1082 /* ECDSA Curves already have this */ 1083 pointProj pt = newPointProj(cp->maxDigits); 1084 findPointProj(pt, cp->x1Plus, cp); 1085 1086 /* initial point is supposed to be on curve! */ 1087 if(gcompg(pt->x, cp->x1Plus)) { 1088 CKRaise("curveParamsInferFields failure"); 1089 } 1090 cp->y1Plus = copyGiant(pt->y); 1091 freePointProj(pt); 1092 } 1093 } 1094 else { 1095 cp->y1Plus = newGiant(1); 1096 } 1097 #else /* CRYPTKIT_ELL_PROJ_ENABLE */ 1098 cp->y1Plus = newGiant(1); 1099 #endif 1100 1101 if((cp->x1OrderPlusRecip == NULL) || isZero(cp->x1OrderPlusRecip)) { 1102 /* 1103 * an easy way of figuring this one out, this should not 1104 * normally run. 1105 */ 1106 cp->x1OrderPlusRecip = newGiant(cp->maxDigits); 1107 make_recip(cp->x1OrderPlus, cp->x1OrderPlusRecip); 1108 if(cp->lesserX1OrderRecip != NULL) { 1109 freeGiant(cp->lesserX1OrderRecip); 1110 } 1111 cp->lesserX1OrderRecip = cp->x1OrderPlusRecip; 1112 } 1113} 1114 1115/* 1116 * Given key size in bits, obtain the asssociated depth. 1117 * Returns FR_IllegalDepth if specify key size not found 1118 * in current curve tables. 1119 */ 1120#define LOG_DEPTH 0 1121 1122#if FEE_PROTOTYPE_CURVES 1123feeReturn feeKeyBitsToDepth(unsigned keySize, 1124 feePrimeType primeType, /* FPT_Fefault means "best one" */ 1125 feeCurveType curveType, /* FCT_Default means "best one" */ 1126 feeDepth *depth) 1127{ 1128 feeReturn frtn = FR_Success; 1129 switch(keySize) { 1130 case 31: 1131 switch(curveType) { 1132 case FCT_Montgomery: 1133 default: 1134 *depth = FEE_DEPTH_31_1_M; 1135 break; 1136 case FCT_Weierstrass: 1137 *depth = FEE_DEPTH_31_1_P; 1138 break; 1139 } 1140 break; 1141 case 40: 1142 switch(curveType) { 1143 case FCT_Weierstrass: 1144 default: 1145 *depth = FEE_DEPTH_40_213; 1146 break; 1147 case FCT_Montgomery: 1148 return FR_IllegalDepth; 1149 } 1150 break; 1151 case 127: 1152 switch(curveType) { 1153 case FCT_Montgomery: 1154 if(primeType == FPT_General) { 1155 *depth = FEE_DEPTH_127_GEN; 1156 } 1157 else{ 1158 *depth = FEE_DEPTH_127_1; 1159 } 1160 break; 1161 case FCT_Weierstrass: 1162 default: 1163 *depth = FEE_DEPTH_127_1W; 1164 break; 1165 } 1166 break; 1167 case 160: 1168 switch(curveType) { 1169 case FCT_Montgomery: 1170 return FR_IllegalDepth; 1171 case FCT_Weierstrass: 1172 default: 1173 if(primeType == FPT_General) { 1174 *depth = FEE_DEPTH_160_GEN; 1175 } 1176 else { 1177 *depth = FEE_DEPTH_160_57; 1178 } 1179 break; 1180 } 1181 break; 1182 case 192: 1183 switch(curveType) { 1184 case FCT_Montgomery: 1185 *depth = FEE_DEPTH_192_M529891; 1186 case FCT_Weierstrass: 1187 default: 1188 *depth = FEE_DEPTH_192_1425; 1189 break; 1190 } 1191 break; 1192 default: 1193 frtn = FR_IllegalDepth; 1194 break; 1195 } 1196 #if LOG_DEPTH 1197 printf("feeKeyBitsToDepth: depth %d\n", *depth); 1198 #endif 1199 return frtn; 1200} 1201 1202#else /* FEE_PROTOTYPE_CURVES */ 1203 1204feeReturn feeKeyBitsToDepth(unsigned keySize, 1205 feePrimeType primeType, /* FPT_Fefault means "best one" */ 1206 feeCurveType curveType, /* FCT_Default means "best one" */ 1207 feeDepth *depth) 1208{ 1209 feeReturn frtn = FR_Success; 1210 switch(keySize) { 1211 case 31: 1212 if(primeType == FPT_General) { 1213 return FR_IllegalDepth; 1214 } 1215 /* note we cut a request for FPT_FEE some slack...this is actually 1216 * FPT_Mersenne, but that is technically a subset of FEE. */ 1217 switch(curveType) { 1218 case FCT_Montgomery: 1219 *depth = FEE_DEPTH_31M; 1220 break; 1221 case FCT_Weierstrass: 1222 case FCT_Default: 1223 *depth = FEE_DEPTH_31W; 1224 break; 1225 default: 1226 return FR_IllegalDepth; 1227 } 1228 break; 1229 case 127: 1230 /* Montgomery only */ 1231 if(primeType == FPT_General) { 1232 return FR_IllegalDepth; 1233 } 1234 /* note we cut a request for FPT_FEE some slack...this is actually 1235 * FPT_Mersenne, but that is technically a subset of FEE. */ 1236 switch(curveType) { 1237 case FCT_Montgomery: 1238 case FCT_Default: 1239 *depth = FEE_DEPTH_127M; 1240 break; 1241 case FCT_Weierstrass: 1242 default: 1243 return FR_IllegalDepth; 1244 } 1245 break; 1246 case 128: 1247 /* Weierstrass/feemod only */ 1248 switch(primeType) { 1249 case FPT_General: 1250 case FPT_Mersenne: 1251 return FR_IllegalDepth; 1252 default: 1253 /* FPT_Default, FPT_FEE */ 1254 break; 1255 } 1256 switch(curveType) { 1257 case FCT_Weierstrass: 1258 case FCT_Default: 1259 *depth = FEE_DEPTH_128W; 1260 break; 1261 default: 1262 return FR_IllegalDepth; 1263 } 1264 break; 1265 case 161: 1266 switch(curveType) { 1267 case FCT_Weierstrass: 1268 case FCT_Default: 1269 switch(primeType) { 1270 case FPT_General: 1271 *depth = FEE_DEPTH_161G; 1272 break; 1273 case FPT_FEE: 1274 case FPT_Default: 1275 *depth = FEE_DEPTH_161W; 1276 break; 1277 default: 1278 /* i.e., FPT_Mersenne */ 1279 return FR_IllegalDepth; 1280 } 1281 break; 1282 default: 1283 return FR_IllegalDepth; 1284 } 1285 break; 1286 case 192: 1287 switch(curveType) { 1288 case FCT_Montgomery: 1289 default: 1290 return FR_IllegalDepth; 1291 case FCT_Weierstrass: 1292 case FCT_Default: 1293 switch(primeType) { 1294 case FPT_General: 1295 case FPT_Default: 1296 *depth = FEE_DEPTH_192G; 1297 break; 1298 default: 1299 /* i.e., FPT_Mersenne, FPT_FEE */ 1300 return FR_IllegalDepth; 1301 } 1302 break; 1303 case FCT_ANSI: 1304 switch(primeType) { 1305 case FPT_General: 1306 case FPT_Default: 1307 break; 1308 default: 1309 return FR_IllegalDepth; 1310 } 1311 *depth = FEE_DEPTH_secp192r1; 1312 break; 1313 } 1314 break; 1315 case 256: 1316 switch(curveType) { 1317 case FCT_ANSI: 1318 case FCT_Default: 1319 break; 1320 default: 1321 return FR_IllegalDepth; 1322 } 1323 switch(primeType) { 1324 case FPT_General: 1325 case FPT_Default: 1326 break; 1327 default: 1328 return FR_IllegalDepth; 1329 } 1330 *depth = FEE_DEPTH_secp256r1; 1331 break; 1332 case 384: 1333 switch(curveType) { 1334 case FCT_ANSI: 1335 case FCT_Default: 1336 break; 1337 default: 1338 return FR_IllegalDepth; 1339 } 1340 switch(primeType) { 1341 case FPT_General: 1342 case FPT_Default: 1343 break; 1344 default: 1345 return FR_IllegalDepth; 1346 } 1347 *depth = FEE_DEPTH_secp384r1; 1348 break; 1349 case 521: 1350 switch(curveType) { 1351 case FCT_ANSI: 1352 case FCT_Default: 1353 break; 1354 default: 1355 return FR_IllegalDepth; 1356 } 1357 switch(primeType) { 1358 case FPT_General: 1359 case FPT_Default: 1360 break; 1361 default: 1362 return FR_IllegalDepth; 1363 } 1364 *depth = FEE_DEPTH_secp521r1; 1365 break; 1366 1367 default: 1368 frtn = FR_IllegalDepth; 1369 break; 1370 } 1371 #if LOG_DEPTH 1372 printf("feeKeyBitsToDepth: depth %d\n", *depth); 1373 #endif 1374 return frtn; 1375} 1376 1377#endif /* FEE_PROTOTYPE_CURVES */ 1378 1379/* 1380 * Obtain depth for specified curveParams 1381 */ 1382feeReturn curveParamsDepth( 1383 curveParams *cp, 1384 feeDepth *depth) 1385{ 1386 if(cp == NULL) { 1387 return FR_IllegalArg; 1388 } 1389 1390 /* We do it this way to allow reconstructing depth from an encoded curveParams */ 1391 feeCurveType curveType = cp->curveType; 1392 if((curveType == FCT_Weierstrass) && (cp->x1Minus == NULL)) { 1393 /* actually an ANSI curve */ 1394 curveType = FCT_ANSI; 1395 } 1396 return feeKeyBitsToDepth(cp->q, cp->primeType, curveType, depth); 1397} 1398 1399 1400