]>
git.saurik.com Git - apple/security.git/blob - Security/libsecurity_cryptkit/lib/feeECDSA.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 * feeECDSA.c - Elliptic Curve Digital Signature Algorithm (per IEEE 1363)
16 * Added ECDSA_VERIFY_ONLY dependencies.
18 * Changed to compile with C++.
20 * Rewrote using projective elliptic algebra, per IEEE P1363.
22 * Fixed c==0 bug in feeECDSAVerify()
27 Nomenclature, per IEEE P1363 D1, Dec. 1997
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)
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:
46 d = [u^(-1) (f + (s*c))] (mod x1OrderPlus)
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].
52 Note: therefore a component of the signature could be slightly
53 larger than base prime.
55 Verification algorithm, given signature (c, d):
57 1) Compute h = d^(-1) (mod x1OrderPlus);
58 2) Compute h1 = digest as giant integer (skips assigning to 'f' as in
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.
73 #if CRYPTKIT_ECDSA_ENABLE
76 #include "feePublicKey.h"
77 #include "feePublicKeyPrivate.h"
78 #include "giantIntegers.h"
80 #include "feeRandom.h"
81 #include "curveParams.h"
83 #include "ckutilities.h"
90 #include "feeDigitalSignature.h"
91 #include "ECDSA_Profile.h"
92 #include "ellipticProj.h"
93 #if CRYPTKIT_DER_ENABLE
94 #include "CryptKitDER.h"
97 #ifndef ECDSA_VERIFY_ONLY
98 static void ECDSA_encode(giant c
,
100 unsigned char **sigData
, // malloc'd and RETURNED
101 unsigned *sigDataLen
); // RETURNED
102 #endif /* ECDSA_VERIFY_ONLY */
104 static feeReturn
ECDSA_decode(const unsigned char *sigData
,
106 giant
*gs
, // alloc'd & RETURNED
107 giant
*x0
, // alloc'd & RETURNED
108 unsigned *sigVersion
); // RETURNED
111 #define ECDSA_DEBUG 0
113 int ecdsaDebug
=1; /* tweakable at runtime via debugger */
118 #define sigLogGiant(s, g) \
121 printGiant(g) /*printGiantExp(g)*/; \
125 #define sigLogGiant(s, g)
126 #endif // ECDSA_DEBUG
130 * Profiling accumulators.
145 #endif // ECDSA_PROFILE
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().
152 #define FEE_ECDSA_VERSION 2
153 #define FEE_ECDSA_VERSION_MIN 2
156 * When true, use ellMulProjSimple rather than elliptic_simple in
157 * sign operation. Using ellMulProjSimple is a *big* win.
159 #define ECDSA_SIGN_USE_PROJ 1
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.
167 #ifndef ECDSA_VERIFY_ONLY
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
179 /* giant integers per IEEE P1363 notation */
181 giant c
; // both 1363 'c' and 'i'
182 // i.e., x-coord of u's pub key
184 giant u
; // random private key
185 giant s
; // private key as giant
186 giant f
; // data (message) as giant
188 feeReturn frtn
= FR_Success
;
190 unsigned char *randBytes
;
191 unsigned randBytesLen
;
193 #if ECDSA_SIGN_USE_PROJ
194 pointProjStruct pt
; // pt->x = c
197 #endif // ECDSA_SIGN_USE_PROJ
202 cp
= feePubKeyCurveParams(pubKey
);
206 if(cp
->curveType
!= FCT_Weierstrass
) {
207 return FR_IllegalCurve
;
210 CKASSERT(!isZero(cp
->x1OrderPlus
));
213 * Private key and message to be signed as giants
215 privGiant
= feePubKeyPrivData(pubKey
);
216 if(privGiant
== NULL
) {
217 dbgLog(("Attempt to Sign without private data\n"));
218 return FR_IllegalArg
;
220 s
= borrowGiant(cp
->maxDigits
);
222 if(dataLen
> (cp
->maxDigits
* GIANT_BYTES_PER_DIGIT
)) {
223 f
= borrowGiant(BYTES_TO_GIANT_DIGITS(dataLen
));
226 f
= borrowGiant(cp
->maxDigits
);
228 deserializeGiant(data
, f
, dataLen
);
231 * Certicom SEC1 states that if the digest is larger than the modulus,
232 * use the left q bits of the digest.
234 unsigned hashBits
= dataLen
* 8;
235 if(hashBits
> cp
->q
) {
236 gshiftright(hashBits
- cp
->q
, f
);
239 sigDbg(("ECDSA sign:\n"));
240 sigLogGiant(" s : ", s
);
241 sigLogGiant(" f : ", f
);
243 c
= borrowGiant(cp
->maxDigits
);
244 d
= borrowGiant(cp
->maxDigits
);
245 u
= borrowGiant(cp
->maxDigits
);
246 if(randFcn
== NULL
) {
247 frand
= feeRandAlloc();
254 * Random size is just larger than base prime
256 randBytesLen
= (feePubKeyBitsize(pubKey
) / 8) + 1;
257 randBytes
= (unsigned char*) fmalloc(randBytesLen
);
259 #if ECDSA_SIGN_USE_PROJ
260 /* quick temp pointProj */
261 pty
= borrowGiant(cp
->maxDigits
);
262 ptz
= borrowGiant(cp
->maxDigits
);
266 #endif // ECDSA_SIGN_USE_PROJ
269 /* Repeat this loop until we have a non-zero c and d */
272 * 1) Obtain random u in [2, x1OrderPlus-2]
276 randFcn(randRef
, randBytes
, randBytesLen
);
279 feeRandBytes(frand
, randBytes
, randBytesLen
);
281 deserializeGiant(randBytes
, u
, randBytesLen
);
282 x1OrderPlusJustify(u
, cp
);
283 SIGPROF_END(signStep1
);
284 sigLogGiant(" u : ", u
);
287 * note 'o' indicates elliptic multiply, * is integer mult.
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);
296 #if ECDSA_SIGN_USE_PROJ
298 /* projective coordinates */
299 gtog(cp
->y1Plus
, pty
);
300 int_to_giant(1, ptz
);
301 ellMulProjSimple(&pt
, u
, cp
);
303 #else /* ECDSA_SIGN_USE_PROJ */
306 elliptic_simple(c
, u
, cp
);
308 #endif /* ECDSA_SIGN_USE_PROJ */
310 SIGPROF_END(signStep2
);
312 x1OrderPlusMod(c
, cp
);
313 SIGPROF_END(signStep34
);
315 dbgLog(("feeECDSASign: zero modulo (1)\n"));
320 * 5) Compute u^(-1) mod x1OrderPlus;
324 binvg_x1OrderPlus(cp
, d
);
325 SIGPROF_END(signStep5
);
326 sigLogGiant(" u^(-1) : ", d
);
329 * 6) Compute signature d as:
330 * d = [u^(-1) (f + s*c)] (mod x1OrderPlus)
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
);
342 * 7) If d = 0, goto (1);
345 dbgLog(("feeECDSASign: zero modulo (2)\n"));
348 sigLogGiant(" c : ", c
);
349 sigLogGiant(" d : ", d
);
350 break; // normal successful exit
354 * 8) signature is now the integer pair (c, d).
358 * Cook up raw data representing the signature.
361 ECDSA_encode(c
, d
, sigData
, sigDataLen
);
362 SIGPROF_END(signStep8
);
373 #if ECDSA_SIGN_USE_PROJ
376 #endif /* ECDSA_SIGN_USE_PROJ */
380 #endif /* ECDSA_VERIFY_ONLY */
383 * Verify signature for specified data (most likely a hash result) and
384 * feePubKey. Returns FR_Success or FR_InvalidSignature.
387 #define LOG_BAD_SIG 0
389 feeReturn
feeECDSAVerify(const unsigned char *sigData
,
391 const unsigned char *data
,
395 /* giant integers per IEEE P1363 notation */
398 giant h2
; // c times h
399 giant littleC
; // newGiant from ECDSA_decode
400 giant littleD
; // ditto
401 giant c
; // borrowed, full size
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
410 curveParams
*cp
= feePubKeyCurveParams(pubKey
);
418 * First decode the byteRep string.
420 frtn
= ECDSA_decode(sigData
,
430 * littleC and littleD have capacity = abs(sign), probably
433 c
= borrowGiant(cp
->maxDigits
);
434 d
= borrowGiant(cp
->maxDigits
);
440 sigDbg(("ECDSA verify:\n"));
443 * W = signer's public key
445 W
= feePubKeyPlusCurve(pubKey
);
448 * 1) Compute h = d^(-1) (mod x1OrderPlus);
451 h
= borrowGiant(cp
->maxDigits
);
453 binvg_x1OrderPlus(cp
, h
);
454 SIGPROF_END(vfyStep1
);
457 * 2) h1 = digest as giant (skips assigning to 'f' in P1363)
459 if(dataLen
> (cp
->maxDigits
* GIANT_BYTES_PER_DIGIT
)) {
460 h1
= borrowGiant(BYTES_TO_GIANT_DIGITS(dataLen
));
463 h1
= borrowGiant(cp
->maxDigits
);
465 deserializeGiant(data
, h1
, dataLen
);
468 * Certicom SEC1 states that if the digest is larger than the modulus,
469 * use the left q bits of the digest.
471 unsigned hashBits
= dataLen
* 8;
472 if(hashBits
> cp
->q
) {
473 gshiftright(hashBits
- cp
->q
, h1
);
476 sigLogGiant(" Wx : ", W
->x
);
477 sigLogGiant(" f : ", h1
);
478 sigLogGiant(" c : ", c
);
479 sigLogGiant(" d : ", d
);
480 sigLogGiant(" s^(-1) : ", h
);
483 * 3) Compute h1 = f * h mod x1OrderPlus;
486 mulg(h
, h1
); // h1 := f * h
487 x1OrderPlusMod(h1
, cp
);
488 SIGPROF_END(vfyStep3
);
491 * 4) Compute h2 = c * h (mod x1OrderPlus);
494 h2
= borrowGiant(cp
->maxDigits
);
496 mulg(h
, h2
); // h2 := c * h
497 x1OrderPlusMod(h2
, cp
);
498 SIGPROF_END(vfyStep4
);
501 * 5) Compute h2W = h2 'o' W (W = theirPub)
503 CKASSERT((W
->y
!= NULL
) && !isZero(W
->y
));
504 h2W
= newPointProj(cp
->maxDigits
);
507 int_to_giant(1, h2W
->z
);
508 ellMulProjSimple(h2W
, h2
, cp
);
511 * 6) Compute h1G = h1 'o' G (G = {x1Plus, y1Plus, 1} )
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
);
521 * 7) h1G := (h1 'o' G) + (h2 'o' W)
523 ellAddProj(h1G
, h2W
, cp
);
526 * 8) If elliptic sum is point at infinity, signature is bad; stop.
529 dbgLog(("feeECDSAVerify: h1 * G = point at infinity\n"));
533 normalizeProj(h1G
, cp
);
536 * 9) cPrime = x coordinate of elliptic sum, mod x1OrderPlus
538 cPrime
= borrowGiant(cp
->maxDigits
);
539 gtog(h1G
->x
, cPrime
);
540 x1OrderPlusMod(cPrime
, cp
);
543 * 10) Good sig iff cPrime == c
545 result
= gcompg(c
, cPrime
);
549 frtn
= FR_InvalidSignature
;
551 printf("***yup, bad sig***\n");
552 #endif // LOG_BAD_SIG
575 #ifndef ECDSA_VERIFY_ONLY
578 * Encode to/from byteRep.
580 static void ECDSA_encode(giant c
,
582 unsigned char **sigData
, // malloc'd and RETURNED
583 unsigned *sigDataLen
) // RETURNED
585 #if CRYPTKIT_DER_ENABLE
586 feeDEREncodeECDSASignature(c
, d
, sigData
, sigDataLen
);
588 *sigDataLen
= lengthOfByteRepSig(c
, d
);
589 *sigData
= (unsigned char*) fmalloc(*sigDataLen
);
590 sigToByteRep(FEE_ECDSA_MAGIC
,
592 FEE_ECDSA_VERSION_MIN
,
599 #endif /* ECDSA_VERIFY_ONLY */
601 static feeReturn
ECDSA_decode(const unsigned char *sigData
,
603 giant
*c
, // alloc'd & RETURNED
604 giant
*d
, // alloc'd & RETURNED
605 unsigned *sigVersion
) // RETURNED
607 #if CRYPTKIT_DER_ENABLE
608 feeReturn frtn
= feeDERDecodeECDSASignature(sigData
, sigDataLen
, c
, d
);
609 if(frtn
== FR_Success
) {
610 *sigVersion
= FEE_ECDSA_VERSION
;
618 rtn
= byteRepToSig(sigData
,
627 return FR_BadSignatureFormat
;
630 case FEE_ECDSA_MAGIC
:
632 case FEE_SIG_MAGIC
: // ElGamal sig!
633 return FR_WrongSignatureType
;
635 return FR_BadSignatureFormat
;
641 * For given key, calculate maximum signature size.
643 feeReturn
feeECDSASigSize(
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....
651 curveParams
*cp
= feePubKeyCurveParams(pubKey
);
656 #if CRYPTKIT_DER_ENABLE
657 *maxSigLen
= feeSizeOfDERSig(cp
->basePrime
, cp
->basePrime
);
659 *maxSigLen
= (unsigned)lengthOfByteRepSig(cp
->basePrime
, cp
->basePrime
);
664 #endif /* CRYPTKIT_ECDSA_ENABLE */