]>
git.saurik.com Git - apple/security.git/blob - libsecurity_cryptkit/lib/feeDigitalSignature.c
1 /* Copyright (c) 1998 Apple Computer, Inc. All rights reserved.
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 ***************************************************************************
11 * feeDigitalSignature.c
16 * Changed to compile with C++.
17 * 9 Sep 98 Doug Mitchell at NeXT
18 * Major changes to use projective elliptic algebra for
20 * 15 Jan 97 Doug Mitchell at NeXT
21 * FEE_SIG_VERSION = 3 (removed code for compatibilty with all older
23 * Was modg(), is curveOrderJustify()
24 * Use plus curve for ellipic algebra per IEEE standards
25 * 22 Aug 96 Doug Mitchell at NeXT
26 * Ported guts of Blaine Garst's NSFEEDigitalSignature.m to C.
31 #include "feePublicKey.h"
32 #include "feePublicKeyPrivate.h"
33 #include "feeDigitalSignature.h"
34 #include "giantIntegers.h"
36 #include "feeRandom.h"
37 #include "curveParams.h"
39 #include "ckutilities.h"
44 #if CRYPTKIT_DER_ENABLE
45 #include "CryptKitDER.h"
49 #include "ellipticProj.h"
53 int sigDebug
=1; // tweakable at runtime via debugger
56 #define SIG_CURVE DEFAULT_CURVE
59 * true : justify randGiant to [2, x1OrderPlus-2]
60 * false : no truncate or mod of randGiant
62 #define RAND_JUST_X1_ORDER_PLUS 1
64 #define FEE_SIG_VERSION 4
65 #define FEE_SIG_VERSION_MIN 4
68 #define max(a,b) ((a)>(b)? (a) : (b))
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 */
79 giant randGiant
; // random m as giant - only known
83 static sigInst
*sinstAlloc()
85 sigInst
*sinst
= (sigInst
*) fmalloc(sizeof(sigInst
));
87 bzero(sinst
, sizeof(sigInst
));
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.
97 feeSig
feeSigNewWithKey(
99 feeRandFcn randFcn
, /* optional */
102 sigInst
*sinst
= sinstAlloc();
104 unsigned char *randBytes
;
105 unsigned randBytesLen
;
111 cp
= feePubKeyCurveParams(pubKey
);
117 * Generate random m, a little larger than key size, save as randGiant
119 randBytesLen
= (feePubKeyBitsize(pubKey
) / 8) + 1;
120 randBytes
= (unsigned char*) fmalloc(randBytesLen
);
122 randFcn(randRef
, randBytes
, randBytesLen
);
125 frand
= feeRandAlloc();
126 feeRandBytes(frand
, randBytes
, randBytesLen
);
129 sinst
->randGiant
= giant_with_data(randBytes
, randBytesLen
);
130 memset(randBytes
, 0, randBytesLen
);
134 if(isZero(sinst
->randGiant
)) {
135 printf("feeSigNewWithKey: randGiant = 0!\n");
140 * Justify randGiant to be in [2, x1OrderPlus]
142 x1OrderPlusJustify(sinst
->randGiant
, cp
);
144 /* PmX := randGiant 'o' P1 */
145 sinst
->PmX
= newGiant(cp
->maxDigits
);
147 #if CRYPTKIT_ELL_PROJ_ENABLE
149 if(cp
->curveType
== FCT_Weierstrass
) {
153 sinst
->PmY
= newGiant(cp
->maxDigits
);
155 /* cook up pt0 as P1 */
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
);
163 /* pt0 := P1 'o' randGiant */
164 ellMulProjSimple(&pt0
, sinst
->randGiant
, cp
);
169 if(SIG_CURVE
== CURVE_PLUS
) {
170 gtog(cp
->x1Plus
, sinst
->PmX
);
173 gtog(cp
->x1Minus
, sinst
->PmX
);
175 elliptic_simple(sinst
->PmX
, sinst
->randGiant
, cp
);
177 #else /* CRYPTKIT_ELL_PROJ_ENABLE */
179 if(SIG_CURVE
== CURVE_PLUS
) {
180 gtog(cp
->x1Plus
, sinst
->PmX
);
183 gtog(cp
->x1Minus
, sinst
->PmX
);
185 elliptic_simple(sinst
->PmX
, sinst
->randGiant
, cp
);
187 #endif /* CRYPTKIT_ELL_PROJ_ENABLE */
192 void feeSigFree(feeSig sig
)
194 sigInst
*sinst
= (sigInst
*) sig
;
197 clearGiant(sinst
->PmX
);
198 freeGiant(sinst
->PmX
);
200 #if CRYPTKIT_ELL_PROJ_ENABLE
202 clearGiant(sinst
->PmY
);
203 freeGiant(sinst
->PmY
);
205 #endif /* CRYPTKIT_ELL_PROJ_ENABLE */
207 clearGiant(sinst
->u
);
210 if(sinst
->randGiant
) {
211 clearGiant(sinst
->randGiant
);
212 freeGiant(sinst
->randGiant
);
218 * Obtain Pm after feeSigNewWithKey() or feeSigParse()
220 unsigned char *feeSigPm(feeSig sig
,
223 sigInst
*sinst
= (sigInst
*) sig
;
226 if(sinst
->PmX
== NULL
) {
227 dbgLog(("feeSigPm: no PmX!\n"));
231 Pm
= mem_from_giant(sinst
->PmX
, PmLen
);
237 printf("Pm : "); printGiant(sinst
->PmX
);
239 for(i
=0; i
<*PmLen
; i
++) {
240 printf("%x:", Pm
[i
]);
250 * Sign specified block of data (most likely a hash result) using
251 * specified feePubKey.
253 feeReturn
feeSigSign(feeSig sig
,
254 const unsigned char *data
, // data to be signed
255 unsigned dataLen
, // in bytes
258 sigInst
*sinst
= (sigInst
*) sig
;
259 giant messageGiant
= NULL
;
262 unsigned privGiantBytes
;
263 feeReturn frtn
= FR_Success
;
264 unsigned randBytesLen
;
265 unsigned uDigits
; // alloc'd digits in sinst->u
271 cp
= feePubKeyCurveParams(pubKey
);
276 privGiant
= feePubKeyPrivData(pubKey
);
277 if(privGiant
== NULL
) {
278 dbgLog(("Attempt to Sign without private data\n"));
279 frtn
= FR_IllegalArg
;
282 privGiantBytes
= abs(privGiant
->sign
) * GIANT_BYTES_PER_DIGIT
;
285 * Note PmX = m 'o' P1.
286 * Get message/digest as giant. May be significantly different
287 * in size from pubKey's basePrime.
289 messageGiant
= giant_with_data(data
, dataLen
); // M(text)
290 randBytesLen
= feePubKeyBitsize(pubKey
) / 8;
291 maxlen
= max(randBytesLen
, dataLen
);
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
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.
308 calcX1OrderPlusRecip(cp
);
310 /* u := u mod x1OrderPlus */
313 printf("sigSign:\n");
314 printf("u pre-modg : ");
315 printGiant(sinst
->u
);
318 modg_via_recip(cp
->x1OrderPlus
, cp
->x1OrderPlusRecip
, sinst
->u
);
322 printf("privGiant : ");
323 printGiant(privGiant
);
325 printGiant(sinst
->u
);
326 printf("messageGiant: ");
327 printGiant(messageGiant
);
328 printf("curveParams :\n");
329 printCurveParams(cp
);
334 freeGiant(messageGiant
);
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.
345 feeReturn
feeSigData(feeSig sig
,
346 unsigned char **sigData
, // IGNORED....malloc'd and RETURNED
347 unsigned *sigDataLen
) // RETURNED
349 sigInst
*sinst
= (sigInst
*) sig
;
351 #if CRYPTKIT_DER_ENABLE
352 return feeDEREncodeElGamalSignature(sinst
->u
, sinst
->PmX
, sigData
, sigDataLen
);
354 *sigDataLen
= lengthOfByteRepSig(sinst
->u
, sinst
->PmX
);
355 *sigData
= (unsigned char*) fmalloc(*sigDataLen
);
356 sigToByteRep(FEE_SIG_MAGIC
,
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.
371 feeReturn
feeSigParse(const unsigned char *sigData
,
373 feeSig
*sig
) // RETURNED
375 sigInst
*sinst
= NULL
;
377 #if !CRYPTKIT_DER_ENABLE
384 sinst
= sinstAlloc();
385 #if CRYPTKIT_DER_ENABLE
386 frtn
= feeDERDecodeElGamalSignature(sigData
, sigDataLen
, &sinst
->u
, &sinst
->PmX
);
391 rtn
= byteRepToSig(sigData
,
400 frtn
= FR_BadSignatureFormat
;
404 case FEE_ECDSA_MAGIC
:
405 frtn
= FR_WrongSignatureType
; // ECDSA!
410 frtn
= FR_BadSignatureFormat
;
413 #endif /* CRYPTKIT_DER_ENABLE */
417 printf("sigParse: \n");
419 printGiant(sinst
->u
);
434 * Verify signature, obtained via feeSigParse, for specified
435 * data (most likely a hash result) and feePubKey. Returns non-zero if
439 #define LOG_BAD_SIG 0
441 #if CRYPTKIT_ELL_PROJ_ENABLE
443 feeReturn
feeSigVerifyNoProj(feeSig sig
,
444 const unsigned char *data
,
448 static void borrowPointProj(pointProj pt
, unsigned maxDigits
)
450 pt
->x
= borrowGiant(maxDigits
);
451 pt
->y
= borrowGiant(maxDigits
);
452 pt
->z
= borrowGiant(maxDigits
);
455 static void returnPointProj(pointProj pt
)
462 feeReturn
feeSigVerify(feeSig sig
,
463 const unsigned char *data
,
468 giant messageGiant
= NULL
;
469 pointProjStruct scratch
;
470 sigInst
*sinst
= (sigInst
*) sig
;
473 key origKey
; // may be plus or minus key
475 if(sinst
->PmX
== NULL
) {
476 dbgLog(("sigVerify without parse!\n"));
477 return FR_IllegalArg
;
480 cp
= feePubKeyCurveParams(pubKey
);
481 if(cp
->curveType
!= FCT_Weierstrass
) {
482 return feeSigVerifyNoProj(sig
, data
, dataLen
, pubKey
);
485 borrowPointProj(&Q
, cp
->maxDigits
);
486 borrowPointProj(&scratch
, cp
->maxDigits
);
491 gtog(cp
->x1Plus
, Q
.x
);
492 gtog(cp
->y1Plus
, Q
.y
);
493 int_to_giant(1, Q
.z
);
495 messageGiant
= giant_with_data(data
, dataLen
); // M(ciphertext)
498 ellMulProjSimple(&Q
, sinst
->u
, cp
);
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
);
508 printf("verify origKey:\n");
510 printf("messageGiant: ");
511 printGiant(messageGiant
);
512 printf("curveParams:\n");
513 printCurveParams(cp
);
517 /* scratch := M 'o' theirPub */
518 ellMulProjSimple(&scratch
, messageGiant
, cp
);
522 printf("signature_compare, with\n");
525 printf("p1 = Pm:\n");
526 printGiant(sinst
->PmX
);
527 printf("p2 = scratch = R:\n");
528 printGiant(scratch
.x
);
532 if(signature_compare(Q
.x
, sinst
->PmX
, scratch
.x
, cp
)) {
534 frtn
= FR_InvalidSignature
;
536 printf("***yup, bad sig***\n");
537 #endif // LOG_BAD_SIG
542 freeGiant(messageGiant
);
545 returnPointProj(&scratch
);
549 #else /* CRYPTKIT_ELL_PROJ_ENABLE */
551 #define feeSigVerifyNoProj(s, d, l, k) feeSigVerify(s, d, l, k)
553 #endif /* CRYPTKIT_ELL_PROJ_ENABLE */
556 * FEE_SIG_USING_PROJ true : this is the "no Weierstrass" case
557 * feeSigVerifyNoProj false : this is redefined to feeSigVerify
559 feeReturn
feeSigVerifyNoProj(feeSig sig
,
560 const unsigned char *data
,
565 giant messageGiant
= NULL
;
566 giant scratch
= NULL
;
567 sigInst
*sinst
= (sigInst
*) sig
;
570 key origKey
; // may be plus or minus key
572 if(sinst
->PmX
== NULL
) {
573 dbgLog(("sigVerify without parse!\n"));
574 frtn
= FR_IllegalArg
;
578 cp
= feePubKeyCurveParams(pubKey
);
579 Q
= newGiant(cp
->maxDigits
);
585 if(SIG_CURVE
== CURVE_PLUS
) {
586 origKey
= feePubKeyPlusCurve(pubKey
);
590 origKey
= feePubKeyMinusCurve(pubKey
);
591 gtog(cp
->x1Minus
, Q
);
594 messageGiant
= giant_with_data(data
, dataLen
); // M(ciphertext)
597 elliptic_simple(Q
, sinst
->u
, cp
);
599 /* scratch := theirPub */
600 scratch
= newGiant(cp
->maxDigits
);
601 gtog(origKey
->x
, scratch
);
605 printf("verify origKey:\n");
607 printf("messageGiant: ");
608 printGiant(messageGiant
);
609 printf("curveParams:\n");
610 printCurveParams(cp
);
614 /* scratch := M 'o' theirPub */
615 elliptic_simple(scratch
, messageGiant
, cp
);
619 printf("signature_compare, with\n");
622 printf("p1 = Pm:\n");
623 printGiant(sinst
->PmX
);
624 printf("p2 = scratch = R:\n");
629 if(signature_compare(Q
, sinst
->PmX
, scratch
, cp
)) {
631 frtn
= FR_InvalidSignature
;
633 printf("***yup, bad sig***\n");
634 #endif // LOG_BAD_SIG
640 if(messageGiant
!= NULL
) {
641 freeGiant(messageGiant
);
646 if(scratch
!= NULL
) {
653 * For given key, calculate maximum signature size.
655 feeReturn
feeSigSize(
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....
663 curveParams
*cp
= feePubKeyCurveParams(pubKey
);
668 #if CRYPTKIT_DER_ENABLE
669 *maxSigLen
= feeSizeOfDERSig(cp
->basePrime
, cp
->basePrime
);
671 *maxSigLen
= (unsigned)lengthOfByteRepSig(cp
->basePrime
, cp
->basePrime
);