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