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 * feeECDSA.c - Elliptic Curve Digital Signature Algorithm (per IEEE 1363)
12 *
13 * Revision History
14 * ----------------
15 * 11/27/98	dmitch
16 *	Added ECDSA_VERIFY_ONLY dependencies.
17 * 10/06/98	ap
18 *	Changed to compile with C++.
19 *  3 Sep 98 at Apple
20 *  	Rewrote using projective elliptic algebra, per IEEE P1363.
21 * 17 Dec 97 at Apple
22 *	Fixed c==0 bug in feeECDSAVerify()
23 *	Created.
24 */
25
26/****
27 Nomenclature, per IEEE P1363 D1, Dec. 1997
28
29    G = initial public point = (x1Plus, y1Plus) as usual
30    x1OrderPlus = IEEE r = (always prime) order of x1Plus
31    f = message to be signed, generally a SHA1 message digest
32    s = signer's private key
33    W = signer's public key
34    * : integer multiplication, as in (x * y)
35    'o' : elliptic multiply, as in (u 'o' G)
36
37    Signing algorithm:
38
39    1) Obtain random u in [2, x1OrderPlus-2];
40    2) Compute x coordinate, call it c, of u 'o' G  (elliptic mul);
41    3) Reduce: c := c mod x1OrderPlus;
42    4) If c = 0, goto (1);
43    5) Compute u^(-1) (mod x1OrderPlus);
44    6) Compute signature s as:
45
46	    d = [u^(-1) (f + (s*c))] (mod x1OrderPlus)
47
48    7) If d = 0, goto (1);
49    8) Signature is the integer pair (c, d).  Each integer
50	in the pair must be in [1, x1OrderPlus-1].
51
52    Note: therefore a component of the signature could be slightly
53    larger than base prime.
54
55    Verification algorithm, given signature (c, d):
56
57    1) Compute h = d^(-1) (mod x1OrderPlus);
58    2) Compute h1 = digest as giant integer (skips assigning to 'f' as in
59       IEEE spec)
60    3) Compute h1 = h1 * h (mod x1OrderPlus)   (i.e., = f * h)
61    4) Compute h2 = c * h (mod x1OrderPlus);
62    5) Compute h2W = h2 'o' W
63    6) Compute h1G = h1 'o' G
64    7) Compute elliptic sum of h1G + h2W
65    8) If elliptic sum is point at infinity, signature is bad; stop.
66    9) cPrime = x coordinate of elliptic sum, mod x1OrderPlus
67   10) Signature is good iff cPrime == c.
68
69***********/
70
71#include "ckconfig.h"
72
73#if	CRYPTKIT_ECDSA_ENABLE
74
75#include "feeTypes.h"
76#include "feePublicKey.h"
77#include "feePublicKeyPrivate.h"
78#include "giantIntegers.h"
79#include "elliptic.h"
80#include "feeRandom.h"
81#include "curveParams.h"
82#include "falloc.h"
83#include "ckutilities.h"
84#include "feeDebug.h"
85#include "platform.h"
86#include "byteRep.h"
87#include <stdlib.h>
88#include "feeECDSA.h"
89#include "byteRep.h"
90#include "feeDigitalSignature.h"
91#include "ECDSA_Profile.h"
92#include "ellipticProj.h"
93#if	CRYPTKIT_DER_ENABLE
94#include "CryptKitDER.h"
95#endif
96
97#ifndef	ECDSA_VERIFY_ONLY
98static void ECDSA_encode(giant c,
99	giant d,
100	unsigned char **sigData,		// malloc'd and RETURNED
101	unsigned *sigDataLen);			// RETURNED
102#endif	/* ECDSA_VERIFY_ONLY */
103
104static feeReturn ECDSA_decode(const unsigned char *sigData,
105	size_t sigDataLen,
106	giant *gs,						// alloc'd & RETURNED
107	giant *x0,						// alloc'd & RETURNED
108	unsigned *sigVersion);			// RETURNED
109
110
111#define ECDSA_DEBUG		0
112#if	ECDSA_DEBUG
113int	ecdsaDebug=1;			/* tweakable at runtime via debugger */
114#define sigDbg(x)		\
115	if(ecdsaDebug) {	\
116		printf x;	\
117	}
118#define sigLogGiant(s, g)	\
119	if(ecdsaDebug) {	\
120		printf(s);	\
121		printGiant(g) /*printGiantExp(g)*/;	\
122	}
123#else	// ECDSA_DEBUG
124#define sigDbg(x)
125#define sigLogGiant(s, g)
126#endif	// ECDSA_DEBUG
127
128#if	ECDSA_PROFILE
129/*
130 * Profiling accumulators.
131 */
132unsigned signStep1;
133unsigned signStep2;
134unsigned signStep34;
135unsigned signStep5;
136unsigned signStep67;
137unsigned signStep8;
138unsigned vfyStep1;
139unsigned vfyStep3;
140unsigned vfyStep4;
141unsigned vfyStep5;
142unsigned vfyStep6;
143unsigned vfyStep7;
144unsigned vfyStep8;
145#endif	// ECDSA_PROFILE
146
147/*
148 * Totally incompatible with feeDigitalSignature.c. Caller must be aware of
149 * signature format. We will detect an ElGamal signature, however, and
150 * return FR_WrongSignatureType from feeECDSAVerify().
151 */
152#define FEE_ECDSA_VERSION		2
153#define FEE_ECDSA_VERSION_MIN	2
154
155/*
156 * When true, use ellMulProjSimple rather than elliptic_simple in
157 * sign operation. Using ellMulProjSimple is a *big* win.
158 */
159#define ECDSA_SIGN_USE_PROJ	1
160
161/*
162 * Sign specified block of data (most likely a hash result) using
163 * specified private key. Result, an enc64-encoded signature block,
164 * is returned in *sigData.
165 */
166
167#ifndef	ECDSA_VERIFY_ONLY
168
169feeReturn feeECDSASign(feePubKey pubKey,
170	const unsigned char *data,   		// data to be signed
171	unsigned dataLen,					// in bytes
172	feeRandFcn randFcn,					// optional
173	void *randRef,						// optional
174	unsigned char **sigData,			// malloc'd and RETURNED
175	unsigned *sigDataLen)				// RETURNED
176{
177	curveParams 		*cp;
178
179	/* giant integers per IEEE P1363 notation */
180
181	giant 			c;		// both 1363 'c' and 'i'
182						// i.e., x-coord of u's pub key
183	giant 			d;
184	giant 			u;		// random private key
185	giant			s;		// private key as giant
186	giant			f;		// data (message) as giant
187
188	feeReturn 		frtn = FR_Success;
189	feeRand 		frand;
190	unsigned char 	*randBytes;
191	unsigned		randBytesLen;
192	giant			privGiant;
193	#if	ECDSA_SIGN_USE_PROJ
194	pointProjStruct	pt;		// pt->x = c
195	giant			pty;		// pt->y
196	giant			ptz;		// pt->z
197	#endif	// ECDSA_SIGN_USE_PROJ
198
199	if(pubKey == NULL) {
200		return FR_BadPubKey;
201	}
202	cp = feePubKeyCurveParams(pubKey);
203	if(cp == NULL) {
204		return FR_BadPubKey;
205	}
206	if(cp->curveType != FCT_Weierstrass) {
207		return FR_IllegalCurve;
208	}
209
210	CKASSERT(!isZero(cp->x1OrderPlus));
211
212	/*
213	 * Private key and message to be signed as giants
214	 */
215	privGiant = feePubKeyPrivData(pubKey);
216	if(privGiant == NULL) {
217		dbgLog(("Attempt to Sign without private data\n"));
218		return FR_IllegalArg;
219	}
220	s = borrowGiant(cp->maxDigits);
221	gtog(privGiant, s);
222	if(dataLen > (cp->maxDigits * GIANT_BYTES_PER_DIGIT)) {
223	    f = borrowGiant(BYTES_TO_GIANT_DIGITS(dataLen));
224	}
225	else {
226	    f = borrowGiant(cp->maxDigits);
227	}
228	deserializeGiant(data, f, dataLen);
229
230	/*
231	 * Certicom SEC1 states that if the digest is larger than the modulus,
232	 * use the left q bits of the digest.
233	 */
234	unsigned hashBits = dataLen * 8;
235	if(hashBits > cp->q) {
236		gshiftright(hashBits - cp->q, f);
237	}
238
239	sigDbg(("ECDSA sign:\n"));
240	sigLogGiant("  s        : ", s);
241	sigLogGiant("  f        : ", f);
242
243	c = borrowGiant(cp->maxDigits);
244	d = borrowGiant(cp->maxDigits);
245	u = borrowGiant(cp->maxDigits);
246	if(randFcn == NULL) {
247		frand = feeRandAlloc();
248	}
249	else {
250		frand = NULL;
251	}
252
253	/*
254	 * Random size is just larger than base prime
255	 */
256	randBytesLen = (feePubKeyBitsize(pubKey) / 8) + 1;
257	randBytes = (unsigned char*) fmalloc(randBytesLen);
258
259	#if	ECDSA_SIGN_USE_PROJ
260	/* quick temp pointProj */
261	pty = borrowGiant(cp->maxDigits);
262	ptz = borrowGiant(cp->maxDigits);
263	pt.x = c;
264	pt.y = pty;
265	pt.z = ptz;
266	#endif	// ECDSA_SIGN_USE_PROJ
267
268	while(1) {
269		/* Repeat this loop until we have a non-zero c and d */
270
271		/*
272		 * 1) Obtain random u in [2, x1OrderPlus-2]
273		 */
274		SIGPROF_START;
275		if(randFcn) {
276			randFcn(randRef, randBytes, randBytesLen);
277		}
278		else {
279			feeRandBytes(frand, randBytes, randBytesLen);
280		}
281		deserializeGiant(randBytes, u, randBytesLen);
282		x1OrderPlusJustify(u, cp);
283		SIGPROF_END(signStep1);
284		sigLogGiant("  u        : ", u);
285
286    		/*
287		 * note 'o' indicates elliptic multiply, * is integer mult.
288		 *
289    		 * 2) Compute x coordinate, call it c, of u 'o' G
290		 * 3) Reduce: c := c mod x1OrderPlus;
291   		 * 4) If c == 0, goto (1);
292		 */
293		SIGPROF_START;
294		gtog(cp->x1Plus, c);
295
296		#if	ECDSA_SIGN_USE_PROJ
297
298		/* projective coordinates */
299		gtog(cp->y1Plus, pty);
300		int_to_giant(1, ptz);
301		ellMulProjSimple(&pt, u, cp);
302
303		#else	/* ECDSA_SIGN_USE_PROJ */
304
305		/* the FEE way */
306		elliptic_simple(c, u, cp);
307
308		#endif	/* ECDSA_SIGN_USE_PROJ */
309
310		SIGPROF_END(signStep2);
311		SIGPROF_START;
312		x1OrderPlusMod(c, cp);
313		SIGPROF_END(signStep34);
314		if(isZero(c)) {
315			dbgLog(("feeECDSASign: zero modulo (1)\n"));
316			continue;
317		}
318
319		/*
320		 * 5) Compute u^(-1) mod x1OrderPlus;
321		 */
322		SIGPROF_START;
323		gtog(u, d);
324		binvg_x1OrderPlus(cp, d);
325		SIGPROF_END(signStep5);
326		sigLogGiant("  u^(-1)   : ", d);
327
328		/*
329		 * 6) Compute signature d as:
330	 	 *    d = [u^(-1) (f + s*c)] (mod x1OrderPlus)
331		 */
332		SIGPROF_START;
333		mulg(c, s);	     	// s *= c
334		x1OrderPlusMod(s, cp);
335		addg(f, s);   		// s := f + (s * c)
336		x1OrderPlusMod(s, cp);
337		mulg(s, d);	     	// d := u^(-1) (f + (s * c))
338		x1OrderPlusMod(d, cp);
339		SIGPROF_END(signStep67);
340
341		/*
342		 * 7) If d = 0, goto (1);
343		 */
344		if(isZero(d)) {
345			dbgLog(("feeECDSASign: zero modulo (2)\n"));
346			continue;
347		}
348		sigLogGiant("  c        : ", c);
349		sigLogGiant("  d        : ", d);
350		break;			// normal successful exit
351	}
352
353	/*
354	 * 8) signature is now the integer pair (c, d).
355	 */
356
357	/*
358	 * Cook up raw data representing the signature.
359	 */
360	SIGPROF_START;
361	ECDSA_encode(c, d, sigData, sigDataLen);
362	SIGPROF_END(signStep8);
363
364	if(frand != NULL) {
365		feeRandFree(frand);
366	}
367	ffree(randBytes);
368	returnGiant(u);
369	returnGiant(d);
370	returnGiant(c);
371	returnGiant(f);
372	returnGiant(s);
373	#if	ECDSA_SIGN_USE_PROJ
374	returnGiant(pty);
375	returnGiant(ptz);
376	#endif	/* ECDSA_SIGN_USE_PROJ */
377	return frtn;
378}
379
380#endif	/* ECDSA_VERIFY_ONLY */
381
382/*
383 * Verify signature for specified data (most likely a hash result) and
384 * feePubKey. Returns FR_Success or FR_InvalidSignature.
385 */
386
387#define LOG_BAD_SIG	0
388
389feeReturn feeECDSAVerify(const unsigned char *sigData,
390	size_t sigDataLen,
391	const unsigned char *data,
392	unsigned dataLen,
393	feePubKey pubKey)
394{
395	/* giant integers per IEEE P1363 notation */
396	giant 		h;			// s^(-1)
397	giant		h1;			// f h
398	giant		h2;			// c times h
399	giant		littleC;		// newGiant from ECDSA_decode
400	giant 		littleD;		// ditto
401	giant		c;			// borrowed, full size
402	giant		d;			// ditto
403	giant		cPrime = NULL;		// i mod r
404	pointProj	h1G = NULL;		// h1 'o' G
405	pointProj	h2W = NULL;		// h2 'o' W
406	key		W;			// i.e., their public key
407
408	unsigned	version;
409	feeReturn	frtn;
410	curveParams	*cp = feePubKeyCurveParams(pubKey);
411	int		result;
412
413	if(cp == NULL) {
414		return FR_BadPubKey;
415	}
416
417	/*
418	 * First decode the byteRep string.
419	 */
420	frtn = ECDSA_decode(sigData,
421		sigDataLen,
422		&littleC,
423		&littleD,
424		&version);
425	if(frtn) {
426		return frtn;
427	}
428
429	/*
430	 * littleC and littleD have capacity = abs(sign), probably
431	 * not big enough....
432	 */
433	c = borrowGiant(cp->maxDigits);
434	d = borrowGiant(cp->maxDigits);
435	gtog(littleC, c);
436	gtog(littleD, d);
437	freeGiant(littleC);
438	freeGiant(littleD);
439
440	sigDbg(("ECDSA verify:\n"));
441
442	/*
443	 * W = signer's public key
444	 */
445	W = feePubKeyPlusCurve(pubKey);
446
447	/*
448	 * 1) Compute h = d^(-1) (mod x1OrderPlus);
449	 */
450	SIGPROF_START;
451	h = borrowGiant(cp->maxDigits);
452	gtog(d, h);
453	binvg_x1OrderPlus(cp, h);
454	SIGPROF_END(vfyStep1);
455
456	/*
457	 * 2) h1 = digest as giant (skips assigning to 'f' in P1363)
458	 */
459	if(dataLen > (cp->maxDigits * GIANT_BYTES_PER_DIGIT)) {
460	    h1 = borrowGiant(BYTES_TO_GIANT_DIGITS(dataLen));
461	}
462	else {
463	    h1 = borrowGiant(cp->maxDigits);
464	}
465	deserializeGiant(data, h1, dataLen);
466
467	/*
468	 * Certicom SEC1 states that if the digest is larger than the modulus,
469	 * use the left q bits of the digest.
470	 */
471	unsigned hashBits = dataLen * 8;
472	if(hashBits > cp->q) {
473		gshiftright(hashBits - cp->q, h1);
474	}
475
476	sigLogGiant("  Wx       : ", W->x);
477	sigLogGiant("  f        : ", h1);
478	sigLogGiant("  c        : ", c);
479	sigLogGiant("  d        : ", d);
480	sigLogGiant("  s^(-1)   : ", h);
481
482	/*
483	 * 3) Compute h1 = f * h mod x1OrderPlus;
484	 */
485	SIGPROF_START;
486	mulg(h, h1);					// h1 := f * h
487	x1OrderPlusMod(h1, cp);
488	SIGPROF_END(vfyStep3);
489
490	/*
491	 * 4) Compute h2 = c * h (mod x1OrderPlus);
492	 */
493	SIGPROF_START;
494	h2 = borrowGiant(cp->maxDigits);
495	gtog(c, h2);
496	mulg(h, h2);					// h2 := c * h
497	x1OrderPlusMod(h2, cp);
498	SIGPROF_END(vfyStep4);
499
500     	/*
501	 * 5) Compute h2W = h2 'o' W  (W = theirPub)
502	 */
503	CKASSERT((W->y != NULL) && !isZero(W->y));
504	h2W = newPointProj(cp->maxDigits);
505	gtog(W->x, h2W->x);
506	gtog(W->y, h2W->y);
507	int_to_giant(1, h2W->z);
508	ellMulProjSimple(h2W, h2, cp);
509
510	/*
511	 * 6) Compute h1G = h1 'o' G   (G = {x1Plus, y1Plus, 1} )
512	 */
513	CKASSERT((cp->y1Plus != NULL) && !isZero(cp->y1Plus));
514	h1G = newPointProj(cp->maxDigits);
515	gtog(cp->x1Plus, h1G->x);
516	gtog(cp->y1Plus, h1G->y);
517	int_to_giant(1,  h1G->z);
518	ellMulProjSimple(h1G, h1, cp);
519
520	/*
521	 * 7) h1G := (h1 'o' G) + (h2  'o' W)
522	 */
523	ellAddProj(h1G, h2W, cp);
524
525	/*
526	 * 8) If elliptic sum is point at infinity, signature is bad; stop.
527	 */
528	if(isZero(h1G->z)) {
529		dbgLog(("feeECDSAVerify: h1 * G = point at infinity\n"));
530		result = 1;
531		goto vfyDone;
532	}
533	normalizeProj(h1G, cp);
534
535	/*
536	 * 9) cPrime = x coordinate of elliptic sum, mod x1OrderPlus
537	 */
538	cPrime = borrowGiant(cp->maxDigits);
539	gtog(h1G->x, cPrime);
540	x1OrderPlusMod(cPrime, cp);
541
542	/*
543	 * 10) Good sig iff cPrime == c
544	 */
545	result = gcompg(c, cPrime);
546
547vfyDone:
548	if(result) {
549		frtn = FR_InvalidSignature;
550		#if	LOG_BAD_SIG
551		printf("***yup, bad sig***\n");
552		#endif	// LOG_BAD_SIG
553	}
554	else {
555		frtn = FR_Success;
556	}
557
558	returnGiant(c);
559	returnGiant(d);
560	returnGiant(h);
561	returnGiant(h1);
562	returnGiant(h2);
563	if(h1G != NULL) {
564		freePointProj(h1G);
565	}
566	if(h2W != NULL) {
567		freePointProj(h2W);
568	}
569	if(cPrime != NULL) {
570		returnGiant(cPrime);
571	}
572	return frtn;
573}
574
575#ifndef	ECDSA_VERIFY_ONLY
576
577/*
578 * Encode to/from byteRep.
579 */
580static void ECDSA_encode(giant c,
581	giant d,
582	unsigned char **sigData,		// malloc'd and RETURNED
583	unsigned *sigDataLen)			// RETURNED
584{
585	#if	CRYPTKIT_DER_ENABLE
586	feeDEREncodeECDSASignature(c, d, sigData, sigDataLen);
587	#else
588	*sigDataLen = lengthOfByteRepSig(c, d);
589	*sigData = (unsigned char*) fmalloc(*sigDataLen);
590	sigToByteRep(FEE_ECDSA_MAGIC,
591		FEE_ECDSA_VERSION,
592		FEE_ECDSA_VERSION_MIN,
593		c,
594		d,
595		*sigData);
596	#endif
597}
598
599#endif	/* ECDSA_VERIFY_ONLY */
600
601static feeReturn ECDSA_decode(const unsigned char *sigData,
602	size_t sigDataLen,
603	giant *c,						// alloc'd  & RETURNED
604	giant *d,						// alloc'd  & RETURNED
605	unsigned *sigVersion)			// RETURNED
606{
607	#if	CRYPTKIT_DER_ENABLE
608	feeReturn frtn = feeDERDecodeECDSASignature(sigData, sigDataLen, c, d);
609	if(frtn == FR_Success) {
610		*sigVersion = FEE_ECDSA_VERSION;
611	}
612	return frtn;
613	#else
614	int		magic;
615	int		minVersion;
616	int		rtn;
617
618	rtn = byteRepToSig(sigData,
619		sigDataLen,
620		FEE_ECDSA_VERSION,
621		&magic,
622		(int *)sigVersion,
623		&minVersion,
624		c,
625		d);
626	if(rtn == 0) {
627		return FR_BadSignatureFormat;
628	}
629	switch(magic) {
630	    case FEE_ECDSA_MAGIC:
631		return FR_Success;
632	    case FEE_SIG_MAGIC:		// ElGamal sig!
633	    	return FR_WrongSignatureType;
634	    default:
635	    	return FR_BadSignatureFormat;
636	}
637	#endif
638}
639
640/*
641 * For given key, calculate maximum signature size.
642 */
643feeReturn feeECDSASigSize(
644	feePubKey pubKey,
645	unsigned *maxSigLen)
646{
647	/* For now, assume that c and d in the signature are
648	 * same size as the key's associated curveParams->basePrime.
649	 * We might have to pad this a bit....
650	 */
651	curveParams	*cp = feePubKeyCurveParams(pubKey);
652
653	if(cp == NULL) {
654		return FR_BadPubKey;
655	}
656	#if	CRYPTKIT_DER_ENABLE
657	*maxSigLen = feeSizeOfDERSig(cp->basePrime, cp->basePrime);
658	#else
659	*maxSigLen = (unsigned)lengthOfByteRepSig(cp->basePrime, cp->basePrime);
660	#endif
661	return FR_Success;
662}
663
664#endif	/* CRYPTKIT_ECDSA_ENABLE */
665
666