]>
git.saurik.com Git - apple/security.git/blob - libsecurity_cryptkit/lib/feeECDSA.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 * feeECDSA.c - Elliptic Curve Digital Signature Algorithm (per IEEE 1363)
16 * Added ECDSA_VERIFY_ONLY dependencies.
18 * Changed to compile with C++.
19 * 3 Sep 98 Doug Mitchell at Apple
20 * Rewrote using projective elliptic algebra, per IEEE P1363.
21 * 17 Dec 97 Doug Mitchell at Apple
22 * Fixed c==0 bug in feeECDSAVerify()
23 * 16 Jul 97 Doug Mitchell at Apple, based on algorithms by Richard Crandall
28 Nomenclature, per IEEE P1363 D1, Dec. 1997
30 G = initial public point = (x1Plus, y1Plus) as usual
31 x1OrderPlus = IEEE r = (always prime) order of x1Plus
32 f = message to be signed, generally a SHA1 message digest
33 s = signer's private key
34 W = signer's public key
35 * : integer multiplication, as in (x * y)
36 'o' : elliptic multiply, as in (u 'o' G)
40 1) Obtain random u in [2, x1OrderPlus-2];
41 2) Compute x coordinate, call it c, of u 'o' G (elliptic mul);
42 3) Reduce: c := c mod x1OrderPlus;
43 4) If c = 0, goto (1);
44 5) Compute u^(-1) (mod x1OrderPlus);
45 6) Compute signature s as:
47 d = [u^(-1) (f + (s*c))] (mod x1OrderPlus)
49 7) If d = 0, goto (1);
50 8) Signature is the integer pair (c, d). Each integer
51 in the pair must be in [1, x1OrderPlus-1].
53 Note: therefore a component of the signature could be slightly
54 larger than base prime.
56 Verification algorithm, given signature (c, d):
58 1) Compute h = d^(-1) (mod x1OrderPlus);
59 2) Compute h1 = digest as giant integer (skips assigning to 'f' as in
61 3) Compute h1 = h1 * h (mod x1OrderPlus) (i.e., = f * h)
62 4) Compute h2 = c * h (mod x1OrderPlus);
63 5) Compute h2W = h2 'o' W
64 6) Compute h1G = h1 'o' G
65 7) Compute elliptic sum of h1G + h2W
66 8) If elliptic sum is point at infinity, signature is bad; stop.
67 9) cPrime = x coordinate of elliptic sum, mod x1OrderPlus
68 10) Signature is good iff cPrime == c.
74 #if CRYPTKIT_ECDSA_ENABLE
77 #include "feePublicKey.h"
78 #include "feePublicKeyPrivate.h"
79 #include "giantIntegers.h"
81 #include "feeRandom.h"
82 #include "curveParams.h"
84 #include "ckutilities.h"
91 #include "feeDigitalSignature.h"
92 #include "ECDSA_Profile.h"
93 #include "ellipticProj.h"
94 #if CRYPTKIT_DER_ENABLE
95 #include "CryptKitDER.h"
98 #ifndef ECDSA_VERIFY_ONLY
99 static void ECDSA_encode(giant c
,
101 unsigned char **sigData
, // malloc'd and RETURNED
102 unsigned *sigDataLen
); // RETURNED
103 #endif /* ECDSA_VERIFY_ONLY */
105 static feeReturn
ECDSA_decode(const unsigned char *sigData
,
107 giant
*gs
, // alloc'd & RETURNED
108 giant
*x0
, // alloc'd & RETURNED
109 unsigned *sigVersion
); // RETURNED
112 #define ECDSA_DEBUG 0
114 int ecdsaDebug
=1; /* tweakable at runtime via debugger */
119 #define sigLogGiant(s, g) \
122 printGiant(g) /*printGiantExp(g)*/; \
126 #define sigLogGiant(s, g)
127 #endif // ECDSA_DEBUG
131 * Profiling accumulators.
146 #endif // ECDSA_PROFILE
149 * Totally incompatible with feeDigitalSignature.c. Caller must be aware of
150 * signature format. We will detect an ElGamal signature, however, and
151 * return FR_WrongSignatureType from feeECDSAVerify().
153 #define FEE_ECDSA_VERSION 2
154 #define FEE_ECDSA_VERSION_MIN 2
157 * When true, use ellMulProjSimple rather than elliptic_simple in
158 * sign operation. Using ellMulProjSimple is a *big* win.
160 #define ECDSA_SIGN_USE_PROJ 1
163 * Sign specified block of data (most likely a hash result) using
164 * specified private key. Result, an enc64-encoded signature block,
165 * is returned in *sigData.
168 #ifndef ECDSA_VERIFY_ONLY
170 feeReturn
feeECDSASign(feePubKey pubKey
,
171 const unsigned char *data
, // data to be signed
172 unsigned dataLen
, // in bytes
173 feeRandFcn randFcn
, // optional
174 void *randRef
, // optional
175 unsigned char **sigData
, // malloc'd and RETURNED
176 unsigned *sigDataLen
) // RETURNED
180 /* giant integers per IEEE P1363 notation */
182 giant c
; // both 1363 'c' and 'i'
183 // i.e., x-coord of u's pub key
185 giant u
; // random private key
186 giant s
; // private key as giant
187 giant f
; // data (message) as giant
189 feeReturn frtn
= FR_Success
;
191 unsigned char *randBytes
;
192 unsigned randBytesLen
;
194 #if ECDSA_SIGN_USE_PROJ
195 pointProjStruct pt
; // pt->x = c
198 #endif // ECDSA_SIGN_USE_PROJ
203 cp
= feePubKeyCurveParams(pubKey
);
207 if(cp
->curveType
!= FCT_Weierstrass
) {
208 return FR_IllegalCurve
;
211 CKASSERT(!isZero(cp
->x1OrderPlus
));
214 * Private key and message to be signed as giants
216 privGiant
= feePubKeyPrivData(pubKey
);
217 if(privGiant
== NULL
) {
218 dbgLog(("Attempt to Sign without private data\n"));
219 return FR_IllegalArg
;
221 s
= borrowGiant(cp
->maxDigits
);
223 if(dataLen
> (cp
->maxDigits
* GIANT_BYTES_PER_DIGIT
)) {
224 f
= borrowGiant(BYTES_TO_GIANT_DIGITS(dataLen
));
227 f
= borrowGiant(cp
->maxDigits
);
229 deserializeGiant(data
, f
, dataLen
);
232 * Certicom SEC1 states that if the digest is larger than the modulus,
233 * use the left q bits of the digest.
235 unsigned hashBits
= dataLen
* 8;
236 if(hashBits
> cp
->q
) {
237 gshiftright(hashBits
- cp
->q
, f
);
240 sigDbg(("ECDSA sign:\n"));
241 sigLogGiant(" s : ", s
);
242 sigLogGiant(" f : ", f
);
244 c
= borrowGiant(cp
->maxDigits
);
245 d
= borrowGiant(cp
->maxDigits
);
246 u
= borrowGiant(cp
->maxDigits
);
247 if(randFcn
== NULL
) {
248 frand
= feeRandAlloc();
255 * Random size is just larger than base prime
257 randBytesLen
= (feePubKeyBitsize(pubKey
) / 8) + 1;
258 randBytes
= (unsigned char*) fmalloc(randBytesLen
);
260 #if ECDSA_SIGN_USE_PROJ
261 /* quick temp pointProj */
262 pty
= borrowGiant(cp
->maxDigits
);
263 ptz
= borrowGiant(cp
->maxDigits
);
267 #endif // ECDSA_SIGN_USE_PROJ
270 /* Repeat this loop until we have a non-zero c and d */
273 * 1) Obtain random u in [2, x1OrderPlus-2]
277 randFcn(randRef
, randBytes
, randBytesLen
);
280 feeRandBytes(frand
, randBytes
, randBytesLen
);
282 deserializeGiant(randBytes
, u
, randBytesLen
);
283 x1OrderPlusJustify(u
, cp
);
284 SIGPROF_END(signStep1
);
285 sigLogGiant(" u : ", u
);
288 * note 'o' indicates elliptic multiply, * is integer mult.
290 * 2) Compute x coordinate, call it c, of u 'o' G
291 * 3) Reduce: c := c mod x1OrderPlus;
292 * 4) If c == 0, goto (1);
297 #if ECDSA_SIGN_USE_PROJ
299 /* projective coordinates */
300 gtog(cp
->y1Plus
, pty
);
301 int_to_giant(1, ptz
);
302 ellMulProjSimple(&pt
, u
, cp
);
304 #else /* ECDSA_SIGN_USE_PROJ */
307 elliptic_simple(c
, u
, cp
);
309 #endif /* ECDSA_SIGN_USE_PROJ */
311 SIGPROF_END(signStep2
);
313 x1OrderPlusMod(c
, cp
);
314 SIGPROF_END(signStep34
);
316 dbgLog(("feeECDSASign: zero modulo (1)\n"));
321 * 5) Compute u^(-1) mod x1OrderPlus;
325 binvg_x1OrderPlus(cp
, d
);
326 SIGPROF_END(signStep5
);
327 sigLogGiant(" u^(-1) : ", d
);
330 * 6) Compute signature d as:
331 * d = [u^(-1) (f + s*c)] (mod x1OrderPlus)
334 mulg(c
, s
); // s *= c
335 x1OrderPlusMod(s
, cp
);
336 addg(f
, s
); // s := f + (s * c)
337 x1OrderPlusMod(s
, cp
);
338 mulg(s
, d
); // d := u^(-1) (f + (s * c))
339 x1OrderPlusMod(d
, cp
);
340 SIGPROF_END(signStep67
);
343 * 7) If d = 0, goto (1);
346 dbgLog(("feeECDSASign: zero modulo (2)\n"));
349 sigLogGiant(" c : ", c
);
350 sigLogGiant(" d : ", d
);
351 break; // normal successful exit
355 * 8) signature is now the integer pair (c, d).
359 * Cook up raw data representing the signature.
362 ECDSA_encode(c
, d
, sigData
, sigDataLen
);
363 SIGPROF_END(signStep8
);
374 #if ECDSA_SIGN_USE_PROJ
377 #endif /* ECDSA_SIGN_USE_PROJ */
381 #endif /* ECDSA_VERIFY_ONLY */
384 * Verify signature for specified data (most likely a hash result) and
385 * feePubKey. Returns FR_Success or FR_InvalidSignature.
388 #define LOG_BAD_SIG 0
390 feeReturn
feeECDSAVerify(const unsigned char *sigData
,
392 const unsigned char *data
,
396 /* giant integers per IEEE P1363 notation */
399 giant h2
; // c times h
400 giant littleC
; // newGiant from ECDSA_decode
401 giant littleD
; // ditto
402 giant c
; // borrowed, full size
404 giant cPrime
= NULL
; // i mod r
405 pointProj h1G
= NULL
; // h1 'o' G
406 pointProj h2W
= NULL
; // h2 'o' W
407 key W
; // i.e., their public key
411 curveParams
*cp
= feePubKeyCurveParams(pubKey
);
419 * First decode the byteRep string.
421 frtn
= ECDSA_decode(sigData
,
431 * littleC and littleD have capacity = abs(sign), probably
434 c
= borrowGiant(cp
->maxDigits
);
435 d
= borrowGiant(cp
->maxDigits
);
441 sigDbg(("ECDSA verify:\n"));
444 * W = signer's public key
446 W
= feePubKeyPlusCurve(pubKey
);
449 * 1) Compute h = d^(-1) (mod x1OrderPlus);
452 h
= borrowGiant(cp
->maxDigits
);
454 binvg_x1OrderPlus(cp
, h
);
455 SIGPROF_END(vfyStep1
);
458 * 2) h1 = digest as giant (skips assigning to 'f' in P1363)
460 if(dataLen
> (cp
->maxDigits
* GIANT_BYTES_PER_DIGIT
)) {
461 h1
= borrowGiant(BYTES_TO_GIANT_DIGITS(dataLen
));
464 h1
= borrowGiant(cp
->maxDigits
);
466 deserializeGiant(data
, h1
, dataLen
);
469 * Certicom SEC1 states that if the digest is larger than the modulus,
470 * use the left q bits of the digest.
472 unsigned hashBits
= dataLen
* 8;
473 if(hashBits
> cp
->q
) {
474 gshiftright(hashBits
- cp
->q
, h1
);
477 sigLogGiant(" Wx : ", W
->x
);
478 sigLogGiant(" f : ", h1
);
479 sigLogGiant(" c : ", c
);
480 sigLogGiant(" d : ", d
);
481 sigLogGiant(" s^(-1) : ", h
);
484 * 3) Compute h1 = f * h mod x1OrderPlus;
487 mulg(h
, h1
); // h1 := f * h
488 x1OrderPlusMod(h1
, cp
);
489 SIGPROF_END(vfyStep3
);
492 * 4) Compute h2 = c * h (mod x1OrderPlus);
495 h2
= borrowGiant(cp
->maxDigits
);
497 mulg(h
, h2
); // h2 := c * h
498 x1OrderPlusMod(h2
, cp
);
499 SIGPROF_END(vfyStep4
);
502 * 5) Compute h2W = h2 'o' W (W = theirPub)
504 CKASSERT((W
->y
!= NULL
) && !isZero(W
->y
));
505 h2W
= newPointProj(cp
->maxDigits
);
508 int_to_giant(1, h2W
->z
);
509 ellMulProjSimple(h2W
, h2
, cp
);
512 * 6) Compute h1G = h1 'o' G (G = {x1Plus, y1Plus, 1} )
514 CKASSERT((cp
->y1Plus
!= NULL
) && !isZero(cp
->y1Plus
));
515 h1G
= newPointProj(cp
->maxDigits
);
516 gtog(cp
->x1Plus
, h1G
->x
);
517 gtog(cp
->y1Plus
, h1G
->y
);
518 int_to_giant(1, h1G
->z
);
519 ellMulProjSimple(h1G
, h1
, cp
);
522 * 7) h1G := (h1 'o' G) + (h2 'o' W)
524 ellAddProj(h1G
, h2W
, cp
);
527 * 8) If elliptic sum is point at infinity, signature is bad; stop.
530 dbgLog(("feeECDSAVerify: h1 * G = point at infinity\n"));
534 normalizeProj(h1G
, cp
);
537 * 9) cPrime = x coordinate of elliptic sum, mod x1OrderPlus
539 cPrime
= borrowGiant(cp
->maxDigits
);
540 gtog(h1G
->x
, cPrime
);
541 x1OrderPlusMod(cPrime
, cp
);
544 * 10) Good sig iff cPrime == c
546 result
= gcompg(c
, cPrime
);
550 frtn
= FR_InvalidSignature
;
552 printf("***yup, bad sig***\n");
553 #endif // LOG_BAD_SIG
576 #ifndef ECDSA_VERIFY_ONLY
579 * Encode to/from byteRep.
581 static void ECDSA_encode(giant c
,
583 unsigned char **sigData
, // malloc'd and RETURNED
584 unsigned *sigDataLen
) // RETURNED
586 #if CRYPTKIT_DER_ENABLE
587 feeDEREncodeECDSASignature(c
, d
, sigData
, sigDataLen
);
589 *sigDataLen
= lengthOfByteRepSig(c
, d
);
590 *sigData
= (unsigned char*) fmalloc(*sigDataLen
);
591 sigToByteRep(FEE_ECDSA_MAGIC
,
593 FEE_ECDSA_VERSION_MIN
,
600 #endif /* ECDSA_VERIFY_ONLY */
602 static feeReturn
ECDSA_decode(const unsigned char *sigData
,
604 giant
*c
, // alloc'd & RETURNED
605 giant
*d
, // alloc'd & RETURNED
606 unsigned *sigVersion
) // RETURNED
608 #if CRYPTKIT_DER_ENABLE
609 feeReturn frtn
= feeDERDecodeECDSASignature(sigData
, sigDataLen
, c
, d
);
610 if(frtn
== FR_Success
) {
611 *sigVersion
= FEE_ECDSA_VERSION
;
619 rtn
= byteRepToSig(sigData
,
628 return FR_BadSignatureFormat
;
631 case FEE_ECDSA_MAGIC
:
633 case FEE_SIG_MAGIC
: // ElGamal sig!
634 return FR_WrongSignatureType
;
636 return FR_BadSignatureFormat
;
642 * For given key, calculate maximum signature size.
644 feeReturn
feeECDSASigSize(
648 /* For now, assume that c and d in the signature are
649 * same size as the key's associated curveParams->basePrime.
650 * We might have to pad this a bit....
652 curveParams
*cp
= feePubKeyCurveParams(pubKey
);
657 #if CRYPTKIT_DER_ENABLE
658 *maxSigLen
= feeSizeOfDERSig(cp
->basePrime
, cp
->basePrime
);
660 *maxSigLen
= (unsigned)lengthOfByteRepSig(cp
->basePrime
, cp
->basePrime
);
665 #endif /* CRYPTKIT_ECDSA_ENABLE */