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 * feeDigitalSignature.c 12 * 13 * Revision History 14 * ---------------- 15 * 10/06/98 ap 16 * Changed to compile with C++. 17 * 9 Sep 98 at NeXT 18 * Major changes to use projective elliptic algebra for 19 * Weierstrass curves. 20 * 15 Jan 97 at NeXT 21 * FEE_SIG_VERSION = 3 (removed code for compatibilty with all older 22 * versions). 23 * Was modg(), is curveOrderJustify() 24 * Use plus curve for ellipic algebra per IEEE standards 25 * 22 Aug 96 at NeXT 26 * Ported guts of Blaine Garst's NSFEEDigitalSignature.m to C. 27 */ 28 29#include "ckconfig.h" 30#include "feeTypes.h" 31#include "feePublicKey.h" 32#include "feePublicKeyPrivate.h" 33#include "feeDigitalSignature.h" 34#include "giantIntegers.h" 35#include "elliptic.h" 36#include "feeRandom.h" 37#include "curveParams.h" 38#include "falloc.h" 39#include "ckutilities.h" 40#include "feeDebug.h" 41#include "platform.h" 42#include "byteRep.h" 43#include "feeECDSA.h" 44#if CRYPTKIT_DER_ENABLE 45#include "CryptKitDER.h" 46#endif 47 48#include <stdlib.h> 49#include "ellipticProj.h" 50 51#define SIG_DEBUG 0 52#if SIG_DEBUG 53int sigDebug=1; // tweakable at runtime via debugger 54#endif // SIG_DEBUG 55 56#define SIG_CURVE DEFAULT_CURVE 57 58/* 59 * true : justify randGiant to [2, x1OrderPlus-2] 60 * false : no truncate or mod of randGiant 61 */ 62#define RAND_JUST_X1_ORDER_PLUS 1 63 64#define FEE_SIG_VERSION 4 65#define FEE_SIG_VERSION_MIN 4 66 67#ifndef max 68#define max(a,b) ((a)>(b)? (a) : (b)) 69#endif // max 70 71typedef struct { 72 giant PmX; // m 'o' P1; m = random 73 #if CRYPTKIT_ELL_PROJ_ENABLE 74 giant PmY; // y-coord of m 'o' P1 if we're 75 // using projective coords 76 #endif /* CRYPTKIT_ELL_PROJ_ENABLE */ 77 78 giant u; 79 giant randGiant; // random m as giant - only known 80 // when signing 81} sigInst; 82 83static sigInst *sinstAlloc() 84{ 85 sigInst *sinst = (sigInst*) fmalloc(sizeof(sigInst)); 86 87 bzero(sinst, sizeof(sigInst)); 88 return sinst; 89} 90 91/* 92 * Create new feeSig object, including a random large integer 'randGiant' for 93 * possible use in salting a feeHash object, and 'PmX', equal to 94 * randGiant 'o' P1. Note that this is not called when *verifying* a 95 * signature, only when signing. 96 */ 97feeSig feeSigNewWithKey( 98 feePubKey pubKey, 99 feeRandFcn randFcn, /* optional */ 100 void *randRef) 101{ 102 sigInst *sinst = sinstAlloc(); 103 feeRand frand; 104 unsigned char *randBytes; 105 unsigned randBytesLen; 106 curveParams *cp; 107 108 if(pubKey == NULL) { 109 return NULL; 110 } 111 cp = feePubKeyCurveParams(pubKey); 112 if(cp == NULL) { 113 return NULL; 114 } 115 116 /* 117 * Generate random m, a little larger than key size, save as randGiant 118 */ 119 randBytesLen = (feePubKeyBitsize(pubKey) / 8) + 1; 120 randBytes = (unsigned char*) fmalloc(randBytesLen); 121 if(randFcn) { 122 randFcn(randRef, randBytes, randBytesLen); 123 } 124 else { 125 frand = feeRandAlloc(); 126 feeRandBytes(frand, randBytes, randBytesLen); 127 feeRandFree(frand); 128 } 129 sinst->randGiant = giant_with_data(randBytes, randBytesLen); 130 memset(randBytes, 0, randBytesLen); 131 ffree(randBytes); 132 133 #if FEE_DEBUG 134 if(isZero(sinst->randGiant)) { 135 printf("feeSigNewWithKey: randGiant = 0!\n"); 136 } 137 #endif // FEE_DEBUG 138 139 /* 140 * Justify randGiant to be in [2, x1OrderPlus] 141 */ 142 x1OrderPlusJustify(sinst->randGiant, cp); 143 144 /* PmX := randGiant 'o' P1 */ 145 sinst->PmX = newGiant(cp->maxDigits); 146 147 #if CRYPTKIT_ELL_PROJ_ENABLE 148 149 if(cp->curveType == FCT_Weierstrass) { 150 151 pointProjStruct pt0; 152 153 sinst->PmY = newGiant(cp->maxDigits); 154 155 /* cook up pt0 as P1 */ 156 pt0.x = sinst->PmX; 157 pt0.y = sinst->PmY; 158 pt0.z = borrowGiant(cp->maxDigits); 159 gtog(cp->x1Plus, pt0.x); 160 gtog(cp->y1Plus, pt0.y); 161 int_to_giant(1, pt0.z); 162 163 /* pt0 := P1 'o' randGiant */ 164 ellMulProjSimple(&pt0, sinst->randGiant, cp); 165 166 returnGiant(pt0.z); 167 } 168 else { 169 if(SIG_CURVE == CURVE_PLUS) { 170 gtog(cp->x1Plus, sinst->PmX); 171 } 172 else { 173 gtog(cp->x1Minus, sinst->PmX); 174 } 175 elliptic_simple(sinst->PmX, sinst->randGiant, cp); 176 } 177 #else /* CRYPTKIT_ELL_PROJ_ENABLE */ 178 179 if(SIG_CURVE == CURVE_PLUS) { 180 gtog(cp->x1Plus, sinst->PmX); 181 } 182 else { 183 gtog(cp->x1Minus, sinst->PmX); 184 } 185 elliptic_simple(sinst->PmX, sinst->randGiant, cp); 186 187 #endif /* CRYPTKIT_ELL_PROJ_ENABLE */ 188 189 return sinst; 190} 191 192void feeSigFree(feeSig sig) 193{ 194 sigInst *sinst = (sigInst*) sig; 195 196 if(sinst->PmX) { 197 clearGiant(sinst->PmX); 198 freeGiant(sinst->PmX); 199 } 200 #if CRYPTKIT_ELL_PROJ_ENABLE 201 if(sinst->PmY) { 202 clearGiant(sinst->PmY); 203 freeGiant(sinst->PmY); 204 } 205 #endif /* CRYPTKIT_ELL_PROJ_ENABLE */ 206 if(sinst->u) { 207 clearGiant(sinst->u); 208 freeGiant(sinst->u); 209 } 210 if(sinst->randGiant) { 211 clearGiant(sinst->randGiant); 212 freeGiant(sinst->randGiant); 213 } 214 ffree(sinst); 215} 216 217/* 218 * Obtain Pm after feeSigNewWithKey() or feeSigParse() 219 */ 220unsigned char *feeSigPm(feeSig sig, 221 unsigned *PmLen) 222{ 223 sigInst *sinst = (sigInst*) sig; 224 unsigned char *Pm; 225 226 if(sinst->PmX == NULL) { 227 dbgLog(("feeSigPm: no PmX!\n")); 228 return NULL; 229 } 230 else { 231 Pm = mem_from_giant(sinst->PmX, PmLen); 232 #if SIG_DEBUG 233 if(sigDebug) 234 { 235 int i; 236 237 printf("Pm : "); printGiant(sinst->PmX); 238 printf("PmData: "); 239 for(i=0; i<*PmLen; i++) { 240 printf("%x:", Pm[i]); 241 } 242 printf("\n"); 243 } 244 #endif // SIG_DEBUG 245 } 246 return Pm; 247} 248 249/* 250 * Sign specified block of data (most likely a hash result) using 251 * specified feePubKey. 252 */ 253feeReturn feeSigSign(feeSig sig, 254 const unsigned char *data, // data to be signed 255 unsigned dataLen, // in bytes 256 feePubKey pubKey) 257{ 258 sigInst *sinst = (sigInst*) sig; 259 giant messageGiant = NULL; 260 unsigned maxlen; 261 giant privGiant; 262 unsigned privGiantBytes; 263 feeReturn frtn = FR_Success; 264 unsigned randBytesLen; 265 unsigned uDigits; // alloc'd digits in sinst->u 266 curveParams *cp; 267 268 if(pubKey == NULL) { 269 return FR_BadPubKey; 270 } 271 cp = feePubKeyCurveParams(pubKey); 272 if(cp == NULL) { 273 return FR_BadPubKey; 274 } 275 276 privGiant = feePubKeyPrivData(pubKey); 277 if(privGiant == NULL) { 278 dbgLog(("Attempt to Sign without private data\n")); 279 frtn = FR_IllegalArg; 280 goto abort; 281 } 282 privGiantBytes = abs(privGiant->sign) * GIANT_BYTES_PER_DIGIT; 283 284 /* 285 * Note PmX = m 'o' P1. 286 * Get message/digest as giant. May be significantly different 287 * in size from pubKey's basePrime. 288 */ 289 messageGiant = giant_with_data(data, dataLen); // M(text) 290 randBytesLen = feePubKeyBitsize(pubKey) / 8; 291 maxlen = max(randBytesLen, dataLen); 292 293 /* leave plenty of room.... */ 294 uDigits = (3 * (privGiantBytes + maxlen)) / GIANT_BYTES_PER_DIGIT; 295 sinst->u = newGiant(uDigits); 296 gtog(privGiant, sinst->u); // u := ourPri 297 mulg(messageGiant, sinst->u); // u *= M(text) 298 addg(sinst->randGiant, sinst->u); // u += m 299 300 /* 301 * Paranoia: we're using the curveParams from the caller's pubKey; 302 * this cp will have a valid x1OrderPlusRecip if pubKey is the same 303 * as the one passed to feeSigNewWithKey() (since feeSigNewWithKey 304 * called x1OrderPlusJustify()). But the caller could conceivably be 305 * using a different instance of their pubKey, in which case 306 * the key's cp->x1OrderPlusRecip may not be valid. 307 */ 308 calcX1OrderPlusRecip(cp); 309 310 /* u := u mod x1OrderPlus */ 311 #if SIG_DEBUG 312 if(sigDebug) { 313 printf("sigSign:\n"); 314 printf("u pre-modg : "); 315 printGiant(sinst->u); 316 } 317 #endif 318 modg_via_recip(cp->x1OrderPlus, cp->x1OrderPlusRecip, sinst->u); 319 320 #if SIG_DEBUG 321 if(sigDebug) { 322 printf("privGiant : "); 323 printGiant(privGiant); 324 printf("u : "); 325 printGiant(sinst->u); 326 printf("messageGiant: "); 327 printGiant(messageGiant); 328 printf("curveParams :\n"); 329 printCurveParams(cp); 330 } 331 #endif // SIG_DEBUG 332abort: 333 if(messageGiant) { 334 freeGiant(messageGiant); 335 } 336 return frtn; 337} 338 339/* 340 * Given a feeSig processed by feeSigSign, obtain a malloc'd byte 341 * array representing the signature. 342 * See ByteRep.doc for info on the format of the signature string; 343 * PLEASE UPDATE THIS DOCUMENT WHEN YOU MAKE CHANGES TO THE STRING FORMAT. 344 */ 345feeReturn feeSigData(feeSig sig, 346 unsigned char **sigData, // IGNORED....malloc'd and RETURNED 347 unsigned *sigDataLen) // RETURNED 348{ 349 sigInst *sinst = (sigInst*) sig; 350 351 #if CRYPTKIT_DER_ENABLE 352 return feeDEREncodeElGamalSignature(sinst->u, sinst->PmX, sigData, sigDataLen); 353 #else 354 *sigDataLen = lengthOfByteRepSig(sinst->u, sinst->PmX); 355 *sigData = (unsigned char*) fmalloc(*sigDataLen); 356 sigToByteRep(FEE_SIG_MAGIC, 357 FEE_SIG_VERSION, 358 FEE_SIG_VERSION_MIN, 359 sinst->u, 360 sinst->PmX, 361 *sigData); 362 return FR_Success; 363 #endif 364} 365 366/* 367 * Obtain a feeSig object by parsing an existing signature block. 368 * Note that if Pm is used to salt a hash of the signed data, this must 369 * function must be called prior to hashing. 370 */ 371feeReturn feeSigParse(const unsigned char *sigData, 372 size_t sigDataLen, 373 feeSig *sig) // RETURNED 374{ 375 sigInst *sinst = NULL; 376 feeReturn frtn; 377 #if !CRYPTKIT_DER_ENABLE 378 int version; 379 int magic; 380 int minVersion; 381 int rtn; 382 #endif 383 384 sinst = sinstAlloc(); 385 #if CRYPTKIT_DER_ENABLE 386 frtn = feeDERDecodeElGamalSignature(sigData, sigDataLen, &sinst->u, &sinst->PmX); 387 if(frtn) { 388 goto abort; 389 } 390 #else 391 rtn = byteRepToSig(sigData, 392 sigDataLen, 393 FEE_SIG_VERSION, 394 &magic, 395 &version, 396 &minVersion, 397 &sinst->u, 398 &sinst->PmX); 399 if(rtn == 0) { 400 frtn = FR_BadSignatureFormat; 401 goto abort; 402 } 403 switch(magic) { 404 case FEE_ECDSA_MAGIC: 405 frtn = FR_WrongSignatureType; // ECDSA! 406 goto abort; 407 case FEE_SIG_MAGIC: 408 break; // proceed 409 default: 410 frtn = FR_BadSignatureFormat; 411 goto abort; 412 } 413 #endif /* CRYPTKIT_DER_ENABLE */ 414 415 #if SIG_DEBUG 416 if(sigDebug) { 417 printf("sigParse: \n"); 418 printf("u: "); 419 printGiant(sinst->u); 420 } 421 #endif // SIG_DEBUG 422 423 *sig = sinst; 424 return FR_Success; 425 426abort: 427 if(sinst) { 428 feeSigFree(sinst); 429 } 430 return frtn; 431} 432 433/* 434 * Verify signature, obtained via feeSigParse, for specified 435 * data (most likely a hash result) and feePubKey. Returns non-zero if 436 * signature valid. 437 */ 438 439#define LOG_BAD_SIG 0 440 441#if CRYPTKIT_ELL_PROJ_ENABLE 442 443feeReturn feeSigVerifyNoProj(feeSig sig, 444 const unsigned char *data, 445 unsigned dataLen, 446 feePubKey pubKey); 447 448static void borrowPointProj(pointProj pt, unsigned maxDigits) 449{ 450 pt->x = borrowGiant(maxDigits); 451 pt->y = borrowGiant(maxDigits); 452 pt->z = borrowGiant(maxDigits); 453} 454 455static void returnPointProj(pointProj pt) 456{ 457 returnGiant(pt->x); 458 returnGiant(pt->y); 459 returnGiant(pt->z); 460} 461 462feeReturn feeSigVerify(feeSig sig, 463 const unsigned char *data, 464 unsigned dataLen, 465 feePubKey pubKey) 466{ 467 pointProjStruct Q; 468 giant messageGiant = NULL; 469 pointProjStruct scratch; 470 sigInst *sinst = (sigInst*) sig; 471 feeReturn frtn; 472 curveParams *cp; 473 key origKey; // may be plus or minus key 474 475 if(sinst->PmX == NULL) { 476 dbgLog(("sigVerify without parse!\n")); 477 return FR_IllegalArg; 478 } 479 480 cp = feePubKeyCurveParams(pubKey); 481 if(cp->curveType != FCT_Weierstrass) { 482 return feeSigVerifyNoProj(sig, data, dataLen, pubKey); 483 } 484 485 borrowPointProj(&Q, cp->maxDigits); 486 borrowPointProj(&scratch, cp->maxDigits); 487 488 /* 489 * Q := P1 490 */ 491 gtog(cp->x1Plus, Q.x); 492 gtog(cp->y1Plus, Q.y); 493 int_to_giant(1, Q.z); 494 495 messageGiant = giant_with_data(data, dataLen); // M(ciphertext) 496 497 /* Q := u 'o' P1 */ 498 ellMulProjSimple(&Q, sinst->u, cp); 499 500 /* scratch := theirPub */ 501 origKey = feePubKeyPlusCurve(pubKey); 502 gtog(origKey->x, scratch.x); 503 gtog(origKey->y, scratch.y); 504 int_to_giant(1, scratch.z); 505 506 #if SIG_DEBUG 507 if(sigDebug) { 508 printf("verify origKey:\n"); 509 printKey(origKey); 510 printf("messageGiant: "); 511 printGiant(messageGiant); 512 printf("curveParams:\n"); 513 printCurveParams(cp); 514 } 515 #endif // SIG_DEBUG 516 517 /* scratch := M 'o' theirPub */ 518 ellMulProjSimple(&scratch, messageGiant, cp); 519 520 #if SIG_DEBUG 521 if(sigDebug) { 522 printf("signature_compare, with\n"); 523 printf("p0 = Q:\n"); 524 printGiant(Q.x); 525 printf("p1 = Pm:\n"); 526 printGiant(sinst->PmX); 527 printf("p2 = scratch = R:\n"); 528 printGiant(scratch.x); 529 } 530 #endif // SIG_DEBUG 531 532 if(signature_compare(Q.x, sinst->PmX, scratch.x, cp)) { 533 534 frtn = FR_InvalidSignature; 535 #if LOG_BAD_SIG 536 printf("***yup, bad sig***\n"); 537 #endif // LOG_BAD_SIG 538 } 539 else { 540 frtn = FR_Success; 541 } 542 freeGiant(messageGiant); 543 544 returnPointProj(&Q); 545 returnPointProj(&scratch); 546 return frtn; 547} 548 549#else /* CRYPTKIT_ELL_PROJ_ENABLE */ 550 551#define feeSigVerifyNoProj(s, d, l, k) feeSigVerify(s, d, l, k) 552 553#endif /* CRYPTKIT_ELL_PROJ_ENABLE */ 554 555/* 556 * FEE_SIG_USING_PROJ true : this is the "no Weierstrass" case 557 * feeSigVerifyNoProj false : this is redefined to feeSigVerify 558 */ 559feeReturn feeSigVerifyNoProj(feeSig sig, 560 const unsigned char *data, 561 unsigned dataLen, 562 feePubKey pubKey) 563{ 564 giant Q = NULL; 565 giant messageGiant = NULL; 566 giant scratch = NULL; 567 sigInst *sinst = (sigInst*) sig; 568 feeReturn frtn; 569 curveParams *cp; 570 key origKey; // may be plus or minus key 571 572 if(sinst->PmX == NULL) { 573 dbgLog(("sigVerify without parse!\n")); 574 frtn = FR_IllegalArg; 575 goto out; 576 } 577 578 cp = feePubKeyCurveParams(pubKey); 579 Q = newGiant(cp->maxDigits); 580 581 /* 582 * pick a key (+/-) 583 * Q := P1 584 */ 585 if(SIG_CURVE == CURVE_PLUS) { 586 origKey = feePubKeyPlusCurve(pubKey); 587 gtog(cp->x1Plus, Q); 588 } 589 else { 590 origKey = feePubKeyMinusCurve(pubKey); 591 gtog(cp->x1Minus, Q); 592 } 593 594 messageGiant = giant_with_data(data, dataLen); // M(ciphertext) 595 596 /* Q := u 'o' P1 */ 597 elliptic_simple(Q, sinst->u, cp); 598 599 /* scratch := theirPub */ 600 scratch = newGiant(cp->maxDigits); 601 gtog(origKey->x, scratch); 602 603 #if SIG_DEBUG 604 if(sigDebug) { 605 printf("verify origKey:\n"); 606 printKey(origKey); 607 printf("messageGiant: "); 608 printGiant(messageGiant); 609 printf("curveParams:\n"); 610 printCurveParams(cp); 611 } 612 #endif // SIG_DEBUG 613 614 /* scratch := M 'o' theirPub */ 615 elliptic_simple(scratch, messageGiant, cp); 616 617 #if SIG_DEBUG 618 if(sigDebug) { 619 printf("signature_compare, with\n"); 620 printf("p0 = Q:\n"); 621 printGiant(Q); 622 printf("p1 = Pm:\n"); 623 printGiant(sinst->PmX); 624 printf("p2 = scratch = R:\n"); 625 printGiant(scratch); 626 } 627 #endif // SIG_DEBUG 628 629 if(signature_compare(Q, sinst->PmX, scratch, cp)) { 630 631 frtn = FR_InvalidSignature; 632 #if LOG_BAD_SIG 633 printf("***yup, bad sig***\n"); 634 #endif // LOG_BAD_SIG 635 } 636 else { 637 frtn = FR_Success; 638 } 639out: 640 if(messageGiant != NULL) { 641 freeGiant(messageGiant); 642 } 643 if(Q != NULL) { 644 freeGiant(Q); 645 } 646 if(scratch != NULL) { 647 freeGiant(scratch); 648 } 649 return frtn; 650} 651 652/* 653 * For given key, calculate maximum signature size. 654 */ 655feeReturn feeSigSize( 656 feePubKey pubKey, 657 unsigned *maxSigLen) 658{ 659 /* For now, assume that u and Pm.x in the signature are 660 * same size as the key's associated curveParams->basePrime. 661 * We might have to pad this a bit.... 662 */ 663 curveParams *cp = feePubKeyCurveParams(pubKey); 664 665 if(cp == NULL) { 666 return FR_BadPubKey; 667 } 668 #if CRYPTKIT_DER_ENABLE 669 *maxSigLen = feeSizeOfDERSig(cp->basePrime, cp->basePrime); 670 #else 671 *maxSigLen = (unsigned)lengthOfByteRepSig(cp->basePrime, cp->basePrime); 672 #endif 673 return FR_Success; 674} 675