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