-/* 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(giant c,
- giant d,
- unsigned char **sigData, // malloc'd and RETURNED
- unsigned *sigDataLen); // RETURNED
-#endif /* ECDSA_VERIFY_ONLY */
-
-static feeReturn ECDSA_decode(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,
- 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;
- 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
- */
- randBytesLen = (feePubKeyBitsize(pubKey) / 8) + 1;
- 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);
- x1OrderPlusJustify(u, cp);
- SIGPROF_END(signStep1);
- sigLogGiant(" 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(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)
-{
- /* 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);
- int result;
-
- if(cp == NULL) {
- return FR_BadPubKey;
- }
-
- /*
- * First decode the byteRep string.
- */
- frtn = ECDSA_decode(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(giant c,
- giant d,
- unsigned char **sigData, // malloc'd and RETURNED
- unsigned *sigDataLen) // RETURNED
-{
- #if CRYPTKIT_DER_ENABLE
- 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(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 = 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