]> git.saurik.com Git - apple/security.git/blob - OSX/libsecurity_cryptkit/lib/curveParams.c
projects / apple / security.git / blob
? search:
summary | shortlog | log | commit | commitdiff | tree
blame | history | raw | HEAD
Security-59754.41.1.tar.gz
[apple/security.git] / 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
mirror of Security