--- /dev/null
+/* Copyright (c) 1998,2011,2014 Apple Inc. All Rights Reserved.
+ *
+ * NOTICE: USE OF THE MATERIALS ACCOMPANYING THIS NOTICE IS SUBJECT
+ * TO THE TERMS OF THE SIGNED "FAST ELLIPTIC ENCRYPTION (FEE) REFERENCE
+ * SOURCE CODE EVALUATION AGREEMENT" BETWEEN APPLE, INC. AND THE
+ * ORIGINAL LICENSEE THAT OBTAINED THESE MATERIALS FROM APPLE,
+ * INC. ANY USE OF THESE MATERIALS NOT PERMITTED BY SUCH AGREEMENT WILL
+ * EXPOSE YOU TO LIABILITY.
+ ***************************************************************************
+ *
+ * feeECDSA.c - Elliptic Curve Digital Signature Algorithm (per IEEE 1363)
+ *
+ * Revision History
+ * ----------------
+ * 11/27/98 dmitch
+ * Added ECDSA_VERIFY_ONLY dependencies.
+ * 10/06/98 ap
+ * Changed to compile with C++.
+ * 3 Sep 98 at Apple
+ * Rewrote using projective elliptic algebra, per IEEE P1363.
+ * 17 Dec 97 at Apple
+ * Fixed c==0 bug in feeECDSAVerify()
+ * Created.
+ */
+
+/****
+ Nomenclature, per IEEE P1363 D1, Dec. 1997
+
+ G = initial public point = (x1Plus, y1Plus) as usual
+ x1OrderPlus = IEEE r = (always prime) order of x1Plus
+ f = message to be signed, generally a SHA1 message digest
+ s = signer's private key
+ W = signer's public key
+ * : integer multiplication, as in (x * y)
+ 'o' : elliptic multiply, as in (u 'o' G)
+
+ Signing algorithm:
+
+ 1) Obtain random u in [2, x1OrderPlus-2];
+ 2) Compute x coordinate, call it c, of u 'o' G (elliptic mul);
+ 3) Reduce: c := c mod x1OrderPlus;
+ 4) If c = 0, goto (1);
+ 5) Compute u^(-1) (mod x1OrderPlus);
+ 6) Compute signature s as:
+
+ d = [u^(-1) (f + (s*c))] (mod x1OrderPlus)
+
+ 7) If d = 0, goto (1);
+ 8) Signature is the integer pair (c, d). Each integer
+ in the pair must be in [1, x1OrderPlus-1].
+
+ Note: therefore a component of the signature could be slightly
+ larger than base prime.
+
+ Verification algorithm, given signature (c, d):
+
+ 1) Compute h = d^(-1) (mod x1OrderPlus);
+ 2) Compute h1 = digest as giant integer (skips assigning to 'f' as in
+ IEEE spec)
+ 3) Compute h1 = h1 * h (mod x1OrderPlus) (i.e., = f * h)
+ 4) Compute h2 = c * h (mod x1OrderPlus);
+ 5) Compute h2W = h2 'o' W
+ 6) Compute h1G = h1 'o' G
+ 7) Compute elliptic sum of h1G + h2W
+ 8) If elliptic sum is point at infinity, signature is bad; stop.
+ 9) cPrime = x coordinate of elliptic sum, mod x1OrderPlus
+ 10) Signature is good iff cPrime == c.
+
+***********/
+
+#include "ckconfig.h"
+
+#if CRYPTKIT_ECDSA_ENABLE
+
+#include "feeTypes.h"
+#include "feePublicKey.h"
+#include "feePublicKeyPrivate.h"
+#include "giantIntegers.h"
+#include "elliptic.h"
+#include "feeRandom.h"
+#include "curveParams.h"
+#include "falloc.h"
+#include "ckutilities.h"
+#include "feeDebug.h"
+#include "platform.h"
+#include "byteRep.h"
+#include <stdlib.h>
+#include "feeECDSA.h"
+#include "byteRep.h"
+#include "feeDigitalSignature.h"
+#include "ECDSA_Profile.h"
+#include "ellipticProj.h"
+#if CRYPTKIT_DER_ENABLE
+#include "CryptKitDER.h"
+#endif
+
+#ifndef ECDSA_VERIFY_ONLY
+static void ECDSA_encode(
+ feeSigFormat format, // Signature format DER 9.62 / RAW
+ unsigned groupBytesLen,
+ giant c,
+ giant d,
+ unsigned char **sigData, // malloc'd and RETURNED
+ unsigned *sigDataLen); // RETURNED
+#endif /* ECDSA_VERIFY_ONLY */
+
+static feeReturn ECDSA_decode(
+ feeSigFormat format, // Signature format DER 9.62 / RAW
+ unsigned groupBytesLen,
+ const unsigned char *sigData,
+ size_t sigDataLen,
+ giant *gs, // alloc'd & RETURNED
+ giant *x0, // alloc'd & RETURNED
+ unsigned *sigVersion); // RETURNED
+
+
+#define ECDSA_DEBUG 0
+#if ECDSA_DEBUG
+int ecdsaDebug=1; /* tweakable at runtime via debugger */
+#define sigDbg(x) \
+ if(ecdsaDebug) { \
+ printf x; \
+ }
+#define sigLogGiant(s, g) \
+ if(ecdsaDebug) { \
+ printf(s); \
+ printGiant(g) /*printGiantExp(g)*/; \
+ }
+#else // ECDSA_DEBUG
+#define sigDbg(x)
+#define sigLogGiant(s, g)
+#endif // ECDSA_DEBUG
+
+#if ECDSA_PROFILE
+/*
+ * Profiling accumulators.
+ */
+unsigned signStep1;
+unsigned signStep2;
+unsigned signStep34;
+unsigned signStep5;
+unsigned signStep67;
+unsigned signStep8;
+unsigned vfyStep1;
+unsigned vfyStep3;
+unsigned vfyStep4;
+unsigned vfyStep5;
+unsigned vfyStep6;
+unsigned vfyStep7;
+unsigned vfyStep8;
+#endif // ECDSA_PROFILE
+
+/*
+ * Totally incompatible with feeDigitalSignature.c. Caller must be aware of
+ * signature format. We will detect an ElGamal signature, however, and
+ * return FR_WrongSignatureType from feeECDSAVerify().
+ */
+#define FEE_ECDSA_VERSION 2
+#define FEE_ECDSA_VERSION_MIN 2
+
+/*
+ * When true, use ellMulProjSimple rather than elliptic_simple in
+ * sign operation. Using ellMulProjSimple is a *big* win.
+ */
+#define ECDSA_SIGN_USE_PROJ 1
+
+/*
+ * Sign specified block of data (most likely a hash result) using
+ * specified private key. Result, an enc64-encoded signature block,
+ * is returned in *sigData.
+ */
+
+#ifndef ECDSA_VERIFY_ONLY
+
+feeReturn feeECDSASign(
+ feePubKey pubKey,
+ feeSigFormat format, // Signature format DER 9.62 / RAW
+ const unsigned char *data, // data to be signed
+ unsigned dataLen, // in bytes
+ feeRandFcn randFcn, // optional
+ void *randRef, // optional
+ unsigned char **sigData, // malloc'd and RETURNED
+ unsigned *sigDataLen) // RETURNED
+{
+ curveParams *cp;
+
+ /* giant integers per IEEE P1363 notation */
+
+ giant c; // both 1363 'c' and 'i'
+ // i.e., x-coord of u's pub key
+ giant d;
+ giant u; // random private key
+ giant s; // private key as giant
+ giant f; // data (message) as giant
+
+ feeReturn frtn = FR_Success;
+ feeRand frand;
+ unsigned char *randBytes;
+ unsigned randBytesLen;
+ unsigned groupBytesLen;
+ giant privGiant;
+ #if ECDSA_SIGN_USE_PROJ
+ pointProjStruct pt; // pt->x = c
+ giant pty; // pt->y
+ giant ptz; // pt->z
+ #endif // ECDSA_SIGN_USE_PROJ
+
+ if(pubKey == NULL) {
+ return FR_BadPubKey;
+ }
+ cp = feePubKeyCurveParams(pubKey);
+ if(cp == NULL) {
+ return FR_BadPubKey;
+ }
+ if(cp->curveType != FCT_Weierstrass) {
+ return FR_IllegalCurve;
+ }
+
+ CKASSERT(!isZero(cp->x1OrderPlus));
+
+ /*
+ * Private key and message to be signed as giants
+ */
+ privGiant = feePubKeyPrivData(pubKey);
+ if(privGiant == NULL) {
+ dbgLog(("Attempt to Sign without private data\n"));
+ return FR_IllegalArg;
+ }
+ s = borrowGiant(cp->maxDigits);
+ gtog(privGiant, s);
+ if(dataLen > (cp->maxDigits * GIANT_BYTES_PER_DIGIT)) {
+ f = borrowGiant(BYTES_TO_GIANT_DIGITS(dataLen));
+ }
+ else {
+ f = borrowGiant(cp->maxDigits);
+ }
+ deserializeGiant(data, f, dataLen);
+
+ /*
+ * Certicom SEC1 states that if the digest is larger than the modulus,
+ * use the left q bits of the digest.
+ */
+ unsigned hashBits = dataLen * 8;
+ if(hashBits > cp->q) {
+ gshiftright(hashBits - cp->q, f);
+ }
+
+ sigDbg(("ECDSA sign:\n"));
+ sigLogGiant(" s : ", s);
+ sigLogGiant(" f : ", f);
+
+ c = borrowGiant(cp->maxDigits);
+ d = borrowGiant(cp->maxDigits);
+ u = borrowGiant(cp->maxDigits);
+ if(randFcn == NULL) {
+ frand = feeRandAlloc();
+ }
+ else {
+ frand = NULL;
+ }
+
+ /*
+ * Random size is just larger than base prime
+ */
+ groupBytesLen = ((feePubKeyBitsize(pubKey)+7) / 8);
+ randBytesLen = groupBytesLen+8; // +8bytes (64bits) to reduce the biais when with reduction mod prime. Per FIPS186-4 - "Using Extra Random Bits"
+ randBytes = (unsigned char*) fmalloc(randBytesLen);
+
+ #if ECDSA_SIGN_USE_PROJ
+ /* quick temp pointProj */
+ pty = borrowGiant(cp->maxDigits);
+ ptz = borrowGiant(cp->maxDigits);
+ pt.x = c;
+ pt.y = pty;
+ pt.z = ptz;
+ #endif // ECDSA_SIGN_USE_PROJ
+
+ while(1) {
+ /* Repeat this loop until we have a non-zero c and d */
+
+ /*
+ * 1) Obtain random u in [2, x1OrderPlus-2]
+ */
+ SIGPROF_START;
+ if(randFcn) {
+ randFcn(randRef, randBytes, randBytesLen);
+ }
+ else {
+ feeRandBytes(frand, randBytes, randBytesLen);
+ }
+ deserializeGiant(randBytes, u, randBytesLen);
+ sigLogGiant(" raw u : ", u);
+ sigLogGiant(" order : ", cp->x1OrderPlus);
+ x1OrderPlusJustify(u, cp);
+ SIGPROF_END(signStep1);
+ sigLogGiant(" in range u : ", u);
+
+ /*
+ * note 'o' indicates elliptic multiply, * is integer mult.
+ *
+ * 2) Compute x coordinate, call it c, of u 'o' G
+ * 3) Reduce: c := c mod x1OrderPlus;
+ * 4) If c == 0, goto (1);
+ */
+ SIGPROF_START;
+ gtog(cp->x1Plus, c);
+
+ #if ECDSA_SIGN_USE_PROJ
+
+ /* projective coordinates */
+ gtog(cp->y1Plus, pty);
+ int_to_giant(1, ptz);
+ ellMulProjSimple(&pt, u, cp);
+
+ #else /* ECDSA_SIGN_USE_PROJ */
+
+ /* the FEE way */
+ elliptic_simple(c, u, cp);
+
+ #endif /* ECDSA_SIGN_USE_PROJ */
+
+ SIGPROF_END(signStep2);
+ SIGPROF_START;
+ x1OrderPlusMod(c, cp);
+ SIGPROF_END(signStep34);
+ if(isZero(c)) {
+ dbgLog(("feeECDSASign: zero modulo (1)\n"));
+ continue;
+ }
+
+ /*
+ * 5) Compute u^(-1) mod x1OrderPlus;
+ */
+ SIGPROF_START;
+ gtog(u, d);
+ binvg_x1OrderPlus(cp, d);
+ SIGPROF_END(signStep5);
+ sigLogGiant(" u^(-1) : ", d);
+
+ /*
+ * 6) Compute signature d as:
+ * d = [u^(-1) (f + s*c)] (mod x1OrderPlus)
+ */
+ SIGPROF_START;
+ mulg(c, s); // s *= c
+ x1OrderPlusMod(s, cp);
+ addg(f, s); // s := f + (s * c)
+ x1OrderPlusMod(s, cp);
+ mulg(s, d); // d := u^(-1) (f + (s * c))
+ x1OrderPlusMod(d, cp);
+ SIGPROF_END(signStep67);
+
+ /*
+ * 7) If d = 0, goto (1);
+ */
+ if(isZero(d)) {
+ dbgLog(("feeECDSASign: zero modulo (2)\n"));
+ continue;
+ }
+ sigLogGiant(" c : ", c);
+ sigLogGiant(" d : ", d);
+ break; // normal successful exit
+ }
+
+ /*
+ * 8) signature is now the integer pair (c, d).
+ */
+
+ /*
+ * Cook up raw data representing the signature.
+ */
+ SIGPROF_START;
+ ECDSA_encode(format,groupBytesLen, c, d, sigData, sigDataLen);
+ SIGPROF_END(signStep8);
+
+ if(frand != NULL) {
+ feeRandFree(frand);
+ }
+ ffree(randBytes);
+ returnGiant(u);
+ returnGiant(d);
+ returnGiant(c);
+ returnGiant(f);
+ returnGiant(s);
+ #if ECDSA_SIGN_USE_PROJ
+ returnGiant(pty);
+ returnGiant(ptz);
+ #endif /* ECDSA_SIGN_USE_PROJ */
+ return frtn;
+}
+
+#endif /* ECDSA_VERIFY_ONLY */
+
+/*
+ * Verify signature for specified data (most likely a hash result) and
+ * feePubKey. Returns FR_Success or FR_InvalidSignature.
+ */
+
+#define LOG_BAD_SIG 0
+
+feeReturn feeECDSAVerify(const unsigned char *sigData,
+ size_t sigDataLen,
+ const unsigned char *data,
+ unsigned dataLen,
+ feePubKey pubKey,
+ feeSigFormat format)
+{
+ /* giant integers per IEEE P1363 notation */
+ giant h; // s^(-1)
+ giant h1; // f h
+ giant h2; // c times h
+ giant littleC; // newGiant from ECDSA_decode
+ giant littleD; // ditto
+ giant c; // borrowed, full size
+ giant d; // ditto
+ giant cPrime = NULL; // i mod r
+ pointProj h1G = NULL; // h1 'o' G
+ pointProj h2W = NULL; // h2 'o' W
+ key W; // i.e., their public key
+
+ unsigned version;
+ feeReturn frtn;
+ curveParams *cp = feePubKeyCurveParams(pubKey);
+ unsigned groupBytesLen = ((feePubKeyBitsize(pubKey)+7) / 8);
+ int result;
+
+ if(cp == NULL) {
+ return FR_BadPubKey;
+ }
+
+ /*
+ * First decode the byteRep string.
+ */
+ frtn = ECDSA_decode(
+ format,
+ groupBytesLen,
+ sigData,
+ sigDataLen,
+ &littleC,
+ &littleD,
+ &version);
+ if(frtn) {
+ return frtn;
+ }
+
+ /*
+ * littleC and littleD have capacity = abs(sign), probably
+ * not big enough....
+ */
+ c = borrowGiant(cp->maxDigits);
+ d = borrowGiant(cp->maxDigits);
+ gtog(littleC, c);
+ gtog(littleD, d);
+ freeGiant(littleC);
+ freeGiant(littleD);
+
+ sigDbg(("ECDSA verify:\n"));
+
+ /*
+ * W = signer's public key
+ */
+ W = feePubKeyPlusCurve(pubKey);
+
+ /*
+ * 1) Compute h = d^(-1) (mod x1OrderPlus);
+ */
+ SIGPROF_START;
+ h = borrowGiant(cp->maxDigits);
+ gtog(d, h);
+ binvg_x1OrderPlus(cp, h);
+ SIGPROF_END(vfyStep1);
+
+ /*
+ * 2) h1 = digest as giant (skips assigning to 'f' in P1363)
+ */
+ if(dataLen > (cp->maxDigits * GIANT_BYTES_PER_DIGIT)) {
+ h1 = borrowGiant(BYTES_TO_GIANT_DIGITS(dataLen));
+ }
+ else {
+ h1 = borrowGiant(cp->maxDigits);
+ }
+ deserializeGiant(data, h1, dataLen);
+
+ /*
+ * Certicom SEC1 states that if the digest is larger than the modulus,
+ * use the left q bits of the digest.
+ */
+ unsigned hashBits = dataLen * 8;
+ if(hashBits > cp->q) {
+ gshiftright(hashBits - cp->q, h1);
+ }
+
+ sigLogGiant(" Wx : ", W->x);
+ sigLogGiant(" f : ", h1);
+ sigLogGiant(" c : ", c);
+ sigLogGiant(" d : ", d);
+ sigLogGiant(" s^(-1) : ", h);
+
+ /*
+ * 3) Compute h1 = f * h mod x1OrderPlus;
+ */
+ SIGPROF_START;
+ mulg(h, h1); // h1 := f * h
+ x1OrderPlusMod(h1, cp);
+ SIGPROF_END(vfyStep3);
+
+ /*
+ * 4) Compute h2 = c * h (mod x1OrderPlus);
+ */
+ SIGPROF_START;
+ h2 = borrowGiant(cp->maxDigits);
+ gtog(c, h2);
+ mulg(h, h2); // h2 := c * h
+ x1OrderPlusMod(h2, cp);
+ SIGPROF_END(vfyStep4);
+
+ /*
+ * 5) Compute h2W = h2 'o' W (W = theirPub)
+ */
+ CKASSERT((W->y != NULL) && !isZero(W->y));
+ h2W = newPointProj(cp->maxDigits);
+ gtog(W->x, h2W->x);
+ gtog(W->y, h2W->y);
+ int_to_giant(1, h2W->z);
+ ellMulProjSimple(h2W, h2, cp);
+
+ /*
+ * 6) Compute h1G = h1 'o' G (G = {x1Plus, y1Plus, 1} )
+ */
+ CKASSERT((cp->y1Plus != NULL) && !isZero(cp->y1Plus));
+ h1G = newPointProj(cp->maxDigits);
+ gtog(cp->x1Plus, h1G->x);
+ gtog(cp->y1Plus, h1G->y);
+ int_to_giant(1, h1G->z);
+ ellMulProjSimple(h1G, h1, cp);
+
+ /*
+ * 7) h1G := (h1 'o' G) + (h2 'o' W)
+ */
+ ellAddProj(h1G, h2W, cp);
+
+ /*
+ * 8) If elliptic sum is point at infinity, signature is bad; stop.
+ */
+ if(isZero(h1G->z)) {
+ dbgLog(("feeECDSAVerify: h1 * G = point at infinity\n"));
+ result = 1;
+ goto vfyDone;
+ }
+ normalizeProj(h1G, cp);
+
+ /*
+ * 9) cPrime = x coordinate of elliptic sum, mod x1OrderPlus
+ */
+ cPrime = borrowGiant(cp->maxDigits);
+ gtog(h1G->x, cPrime);
+ x1OrderPlusMod(cPrime, cp);
+
+ /*
+ * 10) Good sig iff cPrime == c
+ */
+ result = gcompg(c, cPrime);
+
+vfyDone:
+ if(result) {
+ frtn = FR_InvalidSignature;
+ #if LOG_BAD_SIG
+ printf("***yup, bad sig***\n");
+ #endif // LOG_BAD_SIG
+ }
+ else {
+ frtn = FR_Success;
+ }
+
+ returnGiant(c);
+ returnGiant(d);
+ returnGiant(h);
+ returnGiant(h1);
+ returnGiant(h2);
+ if(h1G != NULL) {
+ freePointProj(h1G);
+ }
+ if(h2W != NULL) {
+ freePointProj(h2W);
+ }
+ if(cPrime != NULL) {
+ returnGiant(cPrime);
+ }
+ return frtn;
+}
+
+#ifndef ECDSA_VERIFY_ONLY
+
+/*
+ * Encode to/from byteRep.
+ */
+static void ECDSA_encode(
+ feeSigFormat format, // Signature format DER 9.62 / RAW
+ unsigned groupBytesLen,
+ giant c,
+ giant d,
+ unsigned char **sigData, // malloc'd and RETURNED
+ unsigned *sigDataLen) // RETURNED
+{
+ #if CRYPTKIT_DER_ENABLE
+ if (format==FSF_RAW) {
+ feeRAWEncodeECDSASignature(groupBytesLen,c, d, sigData, sigDataLen);
+ } else {
+ feeDEREncodeECDSASignature(c, d, sigData, sigDataLen);
+ }
+ #else
+ *sigDataLen = lengthOfByteRepSig(c, d);
+ *sigData = (unsigned char*) fmalloc(*sigDataLen);
+ sigToByteRep(FEE_ECDSA_MAGIC,
+ FEE_ECDSA_VERSION,
+ FEE_ECDSA_VERSION_MIN,
+ c,
+ d,
+ *sigData);
+ #endif
+}
+
+#endif /* ECDSA_VERIFY_ONLY */
+
+static feeReturn ECDSA_decode(
+ feeSigFormat format, // Signature format DER 9.62 / RAW
+ unsigned groupBytesLen,
+ const unsigned char *sigData,
+ size_t sigDataLen,
+ giant *c, // alloc'd & RETURNED
+ giant *d, // alloc'd & RETURNED
+ unsigned *sigVersion) // RETURNED
+{
+ #if CRYPTKIT_DER_ENABLE
+ feeReturn frtn;
+ if (format==FSF_RAW) {
+ frtn = feeRAWDecodeECDSASignature(groupBytesLen, sigData, sigDataLen, c, d);
+ } else {
+ frtn = feeDERDecodeECDSASignature(sigData, sigDataLen, c, d);
+ }
+ if(frtn == FR_Success) {
+ *sigVersion = FEE_ECDSA_VERSION;
+ }
+ return frtn;
+ #else
+ int magic;
+ int minVersion;
+ int rtn;
+
+ rtn = byteRepToSig(sigData,
+ sigDataLen,
+ FEE_ECDSA_VERSION,
+ &magic,
+ (int *)sigVersion,
+ &minVersion,
+ c,
+ d);
+ if(rtn == 0) {
+ return FR_BadSignatureFormat;
+ }
+ switch(magic) {
+ case FEE_ECDSA_MAGIC:
+ return FR_Success;
+ case FEE_SIG_MAGIC: // ElGamal sig!
+ return FR_WrongSignatureType;
+ default:
+ return FR_BadSignatureFormat;
+ }
+ #endif
+}
+
+/*
+ * For given key, calculate maximum signature size.
+ */
+feeReturn feeECDSASigSize(
+ feePubKey pubKey,
+ unsigned *maxSigLen)
+{
+ /* For now, assume that c and d in the signature are
+ * same size as the key's associated curveParams->basePrime.
+ * We might have to pad this a bit....
+ */
+ curveParams *cp = feePubKeyCurveParams(pubKey);
+
+ if(cp == NULL) {
+ return FR_BadPubKey;
+ }
+ #if CRYPTKIT_DER_ENABLE
+ *maxSigLen = feeSizeOfDERSig(cp->basePrime, cp->basePrime);
+ #else
+ *maxSigLen = (unsigned)lengthOfByteRepSig(cp->basePrime, cp->basePrime);
+ #endif
+ return FR_Success;
+}
+
+#endif /* CRYPTKIT_ECDSA_ENABLE */
+
projects / apple / security.git / blobdiff