]>
git.saurik.com Git - apple/security.git/blob - OSX/libsecurity_cryptkit/lib/feeDigitalSignature.c
1 /* Copyright (c) 1998,2011,2014 Apple 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, 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 ***************************************************************************
11 * feeDigitalSignature.c
16 * Changed to compile with C++.
18 * Major changes to use projective elliptic algebra for
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
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 + 8 ; // +8bytes (64bits) to reduce the biais when with reduction mod prime. Per FIPS186-4 - "Using Extra Random Bits"
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 #pragma clang diagnostic push
170 #pragma clang diagnostic ignored "-Wunreachable-code"
171 if ( SIG_CURVE
== CURVE_PLUS
) {
172 gtog ( cp
-> x1Plus
, sinst
-> PmX
);
175 gtog ( cp
-> x1Minus
, sinst
-> PmX
);
177 #pragma clang diagnostic pop
178 elliptic_simple ( sinst
-> PmX
, sinst
-> randGiant
, cp
);
180 #else /* CRYPTKIT_ELL_PROJ_ENABLE */
182 if ( SIG_CURVE
== CURVE_PLUS
) {
183 gtog ( cp
-> x1Plus
, sinst
-> PmX
);
186 gtog ( cp
-> x1Minus
, sinst
-> PmX
);
188 elliptic_simple ( sinst
-> PmX
, sinst
-> randGiant
, cp
);
190 #endif /* CRYPTKIT_ELL_PROJ_ENABLE */
195 void feeSigFree ( feeSig sig
)
197 sigInst
* sinst
= ( sigInst
*) sig
;
200 clearGiant ( sinst
-> PmX
);
201 freeGiant ( sinst
-> PmX
);
203 #if CRYPTKIT_ELL_PROJ_ENABLE
205 clearGiant ( sinst
-> PmY
);
206 freeGiant ( sinst
-> PmY
);
208 #endif /* CRYPTKIT_ELL_PROJ_ENABLE */
210 clearGiant ( sinst
-> u
);
213 if ( sinst
-> randGiant
) {
214 clearGiant ( sinst
-> randGiant
);
215 freeGiant ( sinst
-> randGiant
);
221 * Obtain Pm after feeSigNewWithKey() or feeSigParse()
223 unsigned char * feeSigPm ( feeSig sig
,
226 sigInst
* sinst
= ( sigInst
*) sig
;
229 if ( sinst
-> PmX
== NULL
) {
230 dbgLog (( "feeSigPm: no PmX! \n " ));
234 Pm
= mem_from_giant ( sinst
-> PmX
, PmLen
);
240 printf ( "Pm : " ); printGiant ( sinst
-> PmX
);
242 for ( i
= 0 ; i
<* PmLen
; i
++) {
243 printf ( " %x :" , Pm
[ i
]);
253 * Sign specified block of data (most likely a hash result) using
254 * specified feePubKey.
256 feeReturn
feeSigSign ( feeSig sig
,
257 const unsigned char * data
, // data to be signed
258 unsigned dataLen
, // in bytes
261 sigInst
* sinst
= ( sigInst
*) sig
;
262 giant messageGiant
= NULL
;
265 unsigned privGiantBytes
;
266 feeReturn frtn
= FR_Success
;
267 unsigned randBytesLen
;
268 unsigned uDigits
; // alloc'd digits in sinst->u
274 cp
= feePubKeyCurveParams ( pubKey
);
279 privGiant
= feePubKeyPrivData ( pubKey
);
280 if ( privGiant
== NULL
) {
281 dbgLog (( "Attempt to Sign without private data \n " ));
282 frtn
= FR_IllegalArg
;
285 privGiantBytes
= abs ( privGiant
-> sign
) * GIANT_BYTES_PER_DIGIT
;
288 * Note PmX = m 'o' P1.
289 * Get message/digest as giant. May be significantly different
290 * in size from pubKey's basePrime.
292 messageGiant
= giant_with_data ( data
, dataLen
); // M(text)
293 randBytesLen
= feePubKeyBitsize ( pubKey
) / 8 ;
294 maxlen
= max ( randBytesLen
, dataLen
);
296 /* leave plenty of room.... */
297 uDigits
= ( 3 * ( privGiantBytes
+ maxlen
)) / GIANT_BYTES_PER_DIGIT
;
298 sinst
-> u
= newGiant ( uDigits
);
299 gtog ( privGiant
, sinst
-> u
); // u := ourPri
300 mulg ( messageGiant
, sinst
-> u
); // u *= M(text)
301 addg ( sinst
-> randGiant
, sinst
-> u
); // u += m
304 * Paranoia: we're using the curveParams from the caller's pubKey;
305 * this cp will have a valid x1OrderPlusRecip if pubKey is the same
306 * as the one passed to feeSigNewWithKey() (since feeSigNewWithKey
307 * called x1OrderPlusJustify()). But the caller could conceivably be
308 * using a different instance of their pubKey, in which case
309 * the key's cp->x1OrderPlusRecip may not be valid.
311 calcX1OrderPlusRecip ( cp
);
313 /* u := u mod x1OrderPlus */
316 printf ( "sigSign: \n " );
317 printf ( "u pre-modg : " );
318 printGiant ( sinst
-> u
);
321 modg_via_recip ( cp
-> x1OrderPlus
, cp
-> x1OrderPlusRecip
, sinst
-> u
);
325 printf ( "privGiant : " );
326 printGiant ( privGiant
);
328 printGiant ( sinst
-> u
);
329 printf ( "messageGiant: " );
330 printGiant ( messageGiant
);
331 printf ( "curveParams : \n " );
332 printCurveParams ( cp
);
337 freeGiant ( messageGiant
);
343 * Given a feeSig processed by feeSigSign, obtain a malloc'd byte
344 * array representing the signature.
345 * See ByteRep.doc for info on the format of the signature string;
346 * PLEASE UPDATE THIS DOCUMENT WHEN YOU MAKE CHANGES TO THE STRING FORMAT.
348 feeReturn
feeSigData ( feeSig sig
,
349 unsigned char ** sigData
, // IGNORED....malloc'd and RETURNED
350 unsigned * sigDataLen
) // RETURNED
352 sigInst
* sinst
= ( sigInst
*) sig
;
354 #if CRYPTKIT_DER_ENABLE
355 return feeDEREncodeElGamalSignature ( sinst
-> u
, sinst
-> PmX
, sigData
, sigDataLen
);
357 * sigDataLen
= lengthOfByteRepSig ( sinst
-> u
, sinst
-> PmX
);
358 * sigData
= ( unsigned char *) fmalloc (* sigDataLen
);
359 sigToByteRep ( FEE_SIG_MAGIC
,
370 * Obtain a feeSig object by parsing an existing signature block.
371 * Note that if Pm is used to salt a hash of the signed data, this must
372 * function must be called prior to hashing.
374 feeReturn
feeSigParse ( const unsigned char * sigData
,
376 feeSig
* sig
) // RETURNED
378 sigInst
* sinst
= NULL
;
380 #if !CRYPTKIT_DER_ENABLE
387 sinst
= sinstAlloc ();
388 #if CRYPTKIT_DER_ENABLE
389 frtn
= feeDERDecodeElGamalSignature ( sigData
, sigDataLen
, & sinst
-> u
, & sinst
-> PmX
);
394 rtn
= byteRepToSig ( sigData
,
403 frtn
= FR_BadSignatureFormat
;
407 case FEE_ECDSA_MAGIC
:
408 frtn
= FR_WrongSignatureType
; // ECDSA!
413 frtn
= FR_BadSignatureFormat
;
416 #endif /* CRYPTKIT_DER_ENABLE */
420 printf ( "sigParse: \n " );
422 printGiant ( sinst
-> u
);
437 * Verify signature, obtained via feeSigParse, for specified
438 * data (most likely a hash result) and feePubKey. Returns non-zero if
442 #define LOG_BAD_SIG 0
444 #if CRYPTKIT_ELL_PROJ_ENABLE
446 feeReturn
feeSigVerifyNoProj ( feeSig sig
,
447 const unsigned char * data
,
451 static void borrowPointProj ( pointProj pt
, unsigned maxDigits
)
453 pt
-> x
= borrowGiant ( maxDigits
);
454 pt
-> y
= borrowGiant ( maxDigits
);
455 pt
-> z
= borrowGiant ( maxDigits
);
458 static void returnPointProj ( pointProj pt
)
465 feeReturn
feeSigVerify ( feeSig sig
,
466 const unsigned char * data
,
471 giant messageGiant
= NULL
;
472 pointProjStruct scratch
;
473 sigInst
* sinst
= ( sigInst
*) sig
;
476 key origKey
; // may be plus or minus key
478 if ( sinst
-> PmX
== NULL
) {
479 dbgLog (( "sigVerify without parse! \n " ));
480 return FR_IllegalArg
;
483 cp
= feePubKeyCurveParams ( pubKey
);
484 if ( cp
-> curveType
!= FCT_Weierstrass
) {
485 return feeSigVerifyNoProj ( sig
, data
, dataLen
, pubKey
);
488 borrowPointProj (& Q
, cp
-> maxDigits
);
489 borrowPointProj (& scratch
, cp
-> maxDigits
);
494 gtog ( cp
-> x1Plus
, Q
. x
);
495 gtog ( cp
-> y1Plus
, Q
. y
);
496 int_to_giant ( 1 , Q
. z
);
498 messageGiant
= giant_with_data ( data
, dataLen
); // M(ciphertext)
501 ellMulProjSimple (& Q
, sinst
-> u
, cp
);
503 /* scratch := theirPub */
504 origKey
= feePubKeyPlusCurve ( pubKey
);
505 gtog ( origKey
-> x
, scratch
. x
);
506 gtog ( origKey
-> y
, scratch
. y
);
507 int_to_giant ( 1 , scratch
. z
);
511 printf ( "verify origKey: \n " );
513 printf ( "messageGiant: " );
514 printGiant ( messageGiant
);
515 printf ( "curveParams: \n " );
516 printCurveParams ( cp
);
520 /* scratch := M 'o' theirPub */
521 ellMulProjSimple (& scratch
, messageGiant
, cp
);
525 printf ( "signature_compare, with \n " );
528 printf ( "p1 = Pm: \n " );
529 printGiant ( sinst
-> PmX
);
530 printf ( "p2 = scratch = R: \n " );
531 printGiant ( scratch
. x
);
535 if ( signature_compare ( Q
. x
, sinst
-> PmX
, scratch
. x
, cp
)) {
537 frtn
= FR_InvalidSignature
;
539 printf ( "***yup, bad sig*** \n " );
540 #endif // LOG_BAD_SIG
545 freeGiant ( messageGiant
);
548 returnPointProj (& scratch
);
552 #else /* CRYPTKIT_ELL_PROJ_ENABLE */
554 #define feeSigVerifyNoProj(s, d, l, k) feeSigVerify(s, d, l, k)
556 #endif /* CRYPTKIT_ELL_PROJ_ENABLE */
559 * FEE_SIG_USING_PROJ true : this is the "no Weierstrass" case
560 * feeSigVerifyNoProj false : this is redefined to feeSigVerify
562 feeReturn
feeSigVerifyNoProj ( feeSig sig
,
563 const unsigned char * data
,
568 giant messageGiant
= NULL
;
569 giant scratch
= NULL
;
570 sigInst
* sinst
= ( sigInst
*) sig
;
573 key origKey
; // may be plus or minus key
575 if ( sinst
-> PmX
== NULL
) {
576 dbgLog (( "sigVerify without parse! \n " ));
577 frtn
= FR_IllegalArg
;
581 cp
= feePubKeyCurveParams ( pubKey
);
582 Q
= newGiant ( cp
-> maxDigits
);
588 #pragma clang diagnostic push
589 #pragma clang diagnostic ignored "-Wunreachable-code"
590 if ( SIG_CURVE
== CURVE_PLUS
) {
591 origKey
= feePubKeyPlusCurve ( pubKey
);
595 origKey
= feePubKeyMinusCurve ( pubKey
);
596 gtog ( cp
-> x1Minus
, Q
);
598 #pragma clang diagnostic pop
600 messageGiant
= giant_with_data ( data
, dataLen
); // M(ciphertext)
603 elliptic_simple ( Q
, sinst
-> u
, cp
);
605 /* scratch := theirPub */
606 scratch
= newGiant ( cp
-> maxDigits
);
607 gtog ( origKey
-> x
, scratch
);
611 printf ( "verify origKey: \n " );
613 printf ( "messageGiant: " );
614 printGiant ( messageGiant
);
615 printf ( "curveParams: \n " );
616 printCurveParams ( cp
);
620 /* scratch := M 'o' theirPub */
621 elliptic_simple ( scratch
, messageGiant
, cp
);
625 printf ( "signature_compare, with \n " );
628 printf ( "p1 = Pm: \n " );
629 printGiant ( sinst
-> PmX
);
630 printf ( "p2 = scratch = R: \n " );
635 if ( signature_compare ( Q
, sinst
-> PmX
, scratch
, cp
)) {
637 frtn
= FR_InvalidSignature
;
639 printf ( "***yup, bad sig*** \n " );
640 #endif // LOG_BAD_SIG
646 if ( messageGiant
!= NULL
) {
647 freeGiant ( messageGiant
);
652 if ( scratch
!= NULL
) {
659 * For given key, calculate maximum signature size.
661 feeReturn
feeSigSize (
665 /* For now, assume that u and Pm.x in the signature are
666 * same size as the key's associated curveParams->basePrime.
667 * We might have to pad this a bit....
669 curveParams
* cp
= feePubKeyCurveParams ( pubKey
);
674 #if CRYPTKIT_DER_ENABLE
675 * maxSigLen
= feeSizeOfDERSig ( cp
-> basePrime
, cp
-> basePrime
);
677 * maxSigLen
= ( unsigned ) lengthOfByteRepSig ( cp
-> basePrime
, cp
-> basePrime
);