]> git.saurik.com Git - apple/security.git/blob - Security/libsecurity_cryptkit/lib/feeECDSA.c
Security-57031.40.6.tar.gz
[apple/security.git] / Security / libsecurity_cryptkit / lib / feeECDSA.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 * 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
98 static 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
104 static 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
113 int 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 */
132 unsigned signStep1;
133 unsigned signStep2;
134 unsigned signStep34;
135 unsigned signStep5;
136 unsigned signStep67;
137 unsigned signStep8;
138 unsigned vfyStep1;
139 unsigned vfyStep3;
140 unsigned vfyStep4;
141 unsigned vfyStep5;
142 unsigned vfyStep6;
143 unsigned vfyStep7;
144 unsigned 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
169 feeReturn 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
389 feeReturn 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
547 vfyDone:
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 */
580 static 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
601 static 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 */
643 feeReturn 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