]> 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-57336.10.29.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 #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
120 static 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
371 static 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 */
676 static 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 */
749 curveParams *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 */
762 void 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 */
773 curveParams *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 */
833 curveParams *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 */
882 void 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 */
936 int 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 */
1005 giant 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 */
1025 static int giantsInitd = 0;
1026
1027 void 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 */
1059 void 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
1123 feeReturn 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
1204 feeReturn 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 */
1382 feeReturn 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
mirror of Security