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