Back to index

lightning-sunbird  0.9+nobinonly
dsa.c
Go to the documentation of this file.
00001 /*
00002  *
00003  * ***** BEGIN LICENSE BLOCK *****
00004  * Version: MPL 1.1/GPL 2.0/LGPL 2.1
00005  *
00006  * The contents of this file are subject to the Mozilla Public License Version
00007  * 1.1 (the "License"); you may not use this file except in compliance with
00008  * the License. You may obtain a copy of the License at
00009  * http://www.mozilla.org/MPL/
00010  *
00011  * Software distributed under the License is distributed on an "AS IS" basis,
00012  * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
00013  * for the specific language governing rights and limitations under the
00014  * License.
00015  *
00016  * The Original Code is the Netscape security libraries.
00017  *
00018  * The Initial Developer of the Original Code is
00019  * Netscape Communications Corporation.
00020  * Portions created by the Initial Developer are Copyright (C) 1994-2000
00021  * the Initial Developer. All Rights Reserved.
00022  *
00023  * Contributor(s):
00024  *
00025  * Alternatively, the contents of this file may be used under the terms of
00026  * either the GNU General Public License Version 2 or later (the "GPL"), or
00027  * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
00028  * in which case the provisions of the GPL or the LGPL are applicable instead
00029  * of those above. If you wish to allow use of your version of this file only
00030  * under the terms of either the GPL or the LGPL, and not to allow others to
00031  * use your version of this file under the terms of the MPL, indicate your
00032  * decision by deleting the provisions above and replace them with the notice
00033  * and other provisions required by the GPL or the LGPL. If you do not delete
00034  * the provisions above, a recipient may use your version of this file under
00035  * the terms of any one of the MPL, the GPL or the LGPL.
00036  *
00037  * ***** END LICENSE BLOCK ***** */
00038 /* $Id: dsa.c,v 1.18 2005/10/12 00:48:25 wtchang%redhat.com Exp $ */
00039 
00040 #include "secerr.h"
00041 
00042 #include "prtypes.h"
00043 #include "prinit.h"
00044 #include "blapi.h"
00045 #include "nssilock.h"
00046 #include "secitem.h"
00047 #include "blapi.h"
00048 #include "mpi.h"
00049 #include "secmpi.h"
00050 
00051  /* XXX to be replaced by define in blapit.h */
00052 #define NSS_FREEBL_DSA_DEFAULT_CHUNKSIZE 2048
00053 
00054 /* DSA-specific random number function defined in prng_fips1861.c. */
00055 extern SECStatus 
00056 DSA_GenerateGlobalRandomBytes(void *dest, size_t len, const unsigned char *q);
00057 
00058 static void translate_mpi_error(mp_err err)
00059 {
00060     MP_TO_SEC_ERROR(err);
00061 }
00062 
00063 SECStatus 
00064 dsa_NewKey(const PQGParams *params, DSAPrivateKey **privKey, 
00065            const unsigned char *xb)
00066 {
00067     mp_int p, g;
00068     mp_int x, y;
00069     mp_err err;
00070     PRArenaPool *arena;
00071     DSAPrivateKey *key;
00072     /* Check args. */
00073     if (!params || !privKey) {
00074        PORT_SetError(SEC_ERROR_INVALID_ARGS);
00075        return SECFailure;
00076     }
00077     /* Initialize an arena for the DSA key. */
00078     arena = PORT_NewArena(NSS_FREEBL_DSA_DEFAULT_CHUNKSIZE);
00079     if (!arena) {
00080        PORT_SetError(SEC_ERROR_NO_MEMORY);
00081        return SECFailure;
00082     }
00083     key = (DSAPrivateKey *)PORT_ArenaZAlloc(arena, sizeof(DSAPrivateKey));
00084     if (!key) {
00085        PORT_SetError(SEC_ERROR_NO_MEMORY);
00086        PORT_FreeArena(arena, PR_TRUE);
00087        return SECFailure;
00088     }
00089     key->params.arena = arena;
00090     /* Initialize MPI integers. */
00091     MP_DIGITS(&p) = 0;
00092     MP_DIGITS(&g) = 0;
00093     MP_DIGITS(&x) = 0;
00094     MP_DIGITS(&y) = 0;
00095     CHECK_MPI_OK( mp_init(&p) );
00096     CHECK_MPI_OK( mp_init(&g) );
00097     CHECK_MPI_OK( mp_init(&x) );
00098     CHECK_MPI_OK( mp_init(&y) );
00099     /* Copy over the PQG params */
00100     CHECK_MPI_OK( SECITEM_CopyItem(arena, &key->params.prime,
00101                                           &params->prime) );
00102     CHECK_MPI_OK( SECITEM_CopyItem(arena, &key->params.subPrime,
00103                                           &params->subPrime) );
00104     CHECK_MPI_OK( SECITEM_CopyItem(arena, &key->params.base, &params->base) );
00105     /* Convert stored p, g, and received x into MPI integers. */
00106     SECITEM_TO_MPINT(params->prime, &p);
00107     SECITEM_TO_MPINT(params->base,  &g);
00108     OCTETS_TO_MPINT(xb, &x, DSA_SUBPRIME_LEN);
00109     /* Store x in private key */
00110     SECITEM_AllocItem(arena, &key->privateValue, DSA_SUBPRIME_LEN);
00111     memcpy(key->privateValue.data, xb, DSA_SUBPRIME_LEN);
00112     /* Compute public key y = g**x mod p */
00113     CHECK_MPI_OK( mp_exptmod(&g, &x, &p, &y) );
00114     /* Store y in public key */
00115     MPINT_TO_SECITEM(&y, &key->publicValue, arena);
00116     *privKey = key;
00117     key = NULL;
00118 cleanup:
00119     mp_clear(&p);
00120     mp_clear(&g);
00121     mp_clear(&x);
00122     mp_clear(&y);
00123     if (key)
00124        PORT_FreeArena(key->params.arena, PR_TRUE);
00125     if (err) {
00126        translate_mpi_error(err);
00127        return SECFailure;
00128     }
00129     return SECSuccess;
00130 }
00131 
00132 /*
00133 ** Generate and return a new DSA public and private key pair,
00134 **     both of which are encoded into a single DSAPrivateKey struct.
00135 **     "params" is a pointer to the PQG parameters for the domain
00136 **     Uses a random seed.
00137 */
00138 SECStatus 
00139 DSA_NewKey(const PQGParams *params, DSAPrivateKey **privKey)
00140 {
00141     SECStatus rv;
00142     unsigned char seed[DSA_SUBPRIME_LEN];
00143     int retries = 10;
00144     int i;
00145     PRBool good;
00146 
00147     do {
00148        /* Generate seed bytes for x according to FIPS 186-1 appendix 3 */
00149        if (DSA_GenerateGlobalRandomBytes(seed, DSA_SUBPRIME_LEN,
00150                                      params->subPrime.data))
00151            return SECFailure;
00152        /* Disallow values of 0 and 1 for x. */
00153        good = PR_FALSE;
00154        for (i = 0; i < DSA_SUBPRIME_LEN-1; i++) {
00155            if (seed[i] != 0) {
00156               good = PR_TRUE;
00157               break;
00158            }
00159        }
00160        if (!good && seed[i] > 1) {
00161            good = PR_TRUE;
00162        }
00163     } while (!good && --retries > 0);
00164 
00165     if (!good) {
00166        PORT_SetError(SEC_ERROR_NEED_RANDOM);
00167        return SECFailure;
00168     }
00169 
00170     /* Generate a new DSA key using random seed. */
00171     rv = dsa_NewKey(params, privKey, seed);
00172     return rv;
00173 }
00174 
00175 /* For FIPS compliance testing. Seed must be exactly 20 bytes long */
00176 SECStatus 
00177 DSA_NewKeyFromSeed(const PQGParams *params, 
00178                    const unsigned char *seed,
00179                    DSAPrivateKey **privKey)
00180 {
00181     SECStatus rv;
00182     rv = dsa_NewKey(params, privKey, seed);
00183     return rv;
00184 }
00185 
00186 static SECStatus 
00187 dsa_SignDigest(DSAPrivateKey *key, SECItem *signature, const SECItem *digest,
00188                const unsigned char *kb)
00189 {
00190     mp_int p, q, g;  /* PQG parameters */
00191     mp_int x, k;     /* private key & pseudo-random integer */
00192     mp_int r, s;     /* tuple (r, s) is signature) */
00193     mp_err err   = MP_OKAY;
00194     SECStatus rv = SECSuccess;
00195 
00196     /* FIPS-compliance dictates that digest is a SHA1 hash. */
00197     /* Check args. */
00198     if (!key || !signature || !digest ||
00199         (signature->len < DSA_SIGNATURE_LEN) ||
00200        (digest->len != SHA1_LENGTH)) {
00201        PORT_SetError(SEC_ERROR_INVALID_ARGS);
00202        return SECFailure;
00203     }
00204 
00205     /* Initialize MPI integers. */
00206     MP_DIGITS(&p) = 0;
00207     MP_DIGITS(&q) = 0;
00208     MP_DIGITS(&g) = 0;
00209     MP_DIGITS(&x) = 0;
00210     MP_DIGITS(&k) = 0;
00211     MP_DIGITS(&r) = 0;
00212     MP_DIGITS(&s) = 0;
00213     CHECK_MPI_OK( mp_init(&p) );
00214     CHECK_MPI_OK( mp_init(&q) );
00215     CHECK_MPI_OK( mp_init(&g) );
00216     CHECK_MPI_OK( mp_init(&x) );
00217     CHECK_MPI_OK( mp_init(&k) );
00218     CHECK_MPI_OK( mp_init(&r) );
00219     CHECK_MPI_OK( mp_init(&s) );
00220     /*
00221     ** Convert stored PQG and private key into MPI integers.
00222     */
00223     SECITEM_TO_MPINT(key->params.prime,    &p);
00224     SECITEM_TO_MPINT(key->params.subPrime, &q);
00225     SECITEM_TO_MPINT(key->params.base,     &g);
00226     SECITEM_TO_MPINT(key->privateValue,    &x);
00227     OCTETS_TO_MPINT(kb, &k, DSA_SUBPRIME_LEN);
00228     /*
00229     ** FIPS 186-1, Section 5, Step 1
00230     **
00231     ** r = (g**k mod p) mod q
00232     */
00233     CHECK_MPI_OK( mp_exptmod(&g, &k, &p, &r) ); /* r = g**k mod p */
00234     CHECK_MPI_OK(     mp_mod(&r, &q, &r) );     /* r = r mod q    */
00235     /*                                  
00236     ** FIPS 186-1, Section 5, Step 2
00237     **
00238     ** s = (k**-1 * (SHA1(M) + x*r)) mod q
00239     */
00240     SECITEM_TO_MPINT(*digest, &s);         /* s = SHA1(M)     */
00241     CHECK_MPI_OK( mp_invmod(&k, &q, &k) );      /* k = k**-1 mod q */
00242     CHECK_MPI_OK( mp_mulmod(&x, &r, &q, &x) );  /* x = x * r mod q */
00243     CHECK_MPI_OK( mp_addmod(&s, &x, &q, &s) );  /* s = s + x mod q */
00244     CHECK_MPI_OK( mp_mulmod(&s, &k, &q, &s) );  /* s = s * k mod q */
00245     /*
00246     ** verify r != 0 and s != 0
00247     ** mentioned as optional in FIPS 186-1.
00248     */
00249     if (mp_cmp_z(&r) == 0 || mp_cmp_z(&s) == 0) {
00250        PORT_SetError(SEC_ERROR_NEED_RANDOM);
00251        rv = SECFailure;
00252        goto cleanup;
00253     }
00254     /*
00255     ** Step 4
00256     **
00257     ** Signature is tuple (r, s)
00258     */
00259     err = mp_to_fixlen_octets(&r, signature->data, DSA_SUBPRIME_LEN);
00260     if (err < 0) goto cleanup; 
00261     err = mp_to_fixlen_octets(&s, signature->data + DSA_SUBPRIME_LEN, 
00262                                   DSA_SUBPRIME_LEN);
00263     if (err < 0) goto cleanup; 
00264     err = MP_OKAY;
00265     signature->len = DSA_SIGNATURE_LEN;
00266 cleanup:
00267     mp_clear(&p);
00268     mp_clear(&q);
00269     mp_clear(&g);
00270     mp_clear(&x);
00271     mp_clear(&k);
00272     mp_clear(&r);
00273     mp_clear(&s);
00274     if (err) {
00275        translate_mpi_error(err);
00276        rv = SECFailure;
00277     }
00278     return rv;
00279 }
00280 
00281 /* signature is caller-supplied buffer of at least 40 bytes.
00282 ** On input,  signature->len == size of buffer to hold signature.
00283 **            digest->len    == size of digest.
00284 ** On output, signature->len == size of signature in buffer.
00285 ** Uses a random seed.
00286 */
00287 SECStatus 
00288 DSA_SignDigest(DSAPrivateKey *key, SECItem *signature, const SECItem *digest)
00289 {
00290     SECStatus rv;
00291     int       retries = 10;
00292     unsigned char kSeed[DSA_SUBPRIME_LEN];
00293     int       i;
00294     PRBool    good;
00295 
00296     PORT_SetError(0);
00297     do {
00298        rv = DSA_GenerateGlobalRandomBytes(kSeed, DSA_SUBPRIME_LEN, 
00299                                       key->params.subPrime.data);
00300        if (rv != SECSuccess) 
00301            break;
00302        /* Disallow a value of 0 for k. */
00303        good = PR_FALSE;
00304        for (i = 0; i < DSA_SUBPRIME_LEN; i++) {
00305            if (kSeed[i] != 0) {
00306               good = PR_TRUE;
00307               break;
00308            }
00309        }
00310        if (!good) {
00311            PORT_SetError(SEC_ERROR_NEED_RANDOM);
00312            rv = SECFailure;
00313            continue;
00314        }
00315        rv = dsa_SignDigest(key, signature, digest, kSeed);
00316     } while (rv != SECSuccess && PORT_GetError() == SEC_ERROR_NEED_RANDOM &&
00317             --retries > 0);
00318     return rv;
00319 }
00320 
00321 /* For FIPS compliance testing. Seed must be exactly 20 bytes. */
00322 SECStatus 
00323 DSA_SignDigestWithSeed(DSAPrivateKey * key,
00324                        SECItem *       signature,
00325                        const SECItem * digest,
00326                        const unsigned char * seed)
00327 {
00328     SECStatus rv;
00329     rv = dsa_SignDigest(key, signature, digest, seed);
00330     return rv;
00331 }
00332 
00333 /* signature is caller-supplied buffer of at least 20 bytes.
00334 ** On input,  signature->len == size of buffer to hold signature.
00335 **            digest->len    == size of digest.
00336 */
00337 SECStatus 
00338 DSA_VerifyDigest(DSAPublicKey *key, const SECItem *signature, 
00339                  const SECItem *digest)
00340 {
00341     /* FIPS-compliance dictates that digest is a SHA1 hash. */
00342     mp_int p, q, g;      /* PQG parameters */
00343     mp_int r_, s_;       /* tuple (r', s') is received signature) */
00344     mp_int u1, u2, v, w; /* intermediate values used in verification */
00345     mp_int y;            /* public key */
00346     mp_err err;
00347     SECStatus verified = SECFailure;
00348 
00349     /* Check args. */
00350     if (!key || !signature || !digest ||
00351         (signature->len != DSA_SIGNATURE_LEN) ||
00352        (digest->len != SHA1_LENGTH)) {
00353        PORT_SetError(SEC_ERROR_INVALID_ARGS);
00354        return SECFailure;
00355     }
00356     /* Initialize MPI integers. */
00357     MP_DIGITS(&p)  = 0;
00358     MP_DIGITS(&q)  = 0;
00359     MP_DIGITS(&g)  = 0;
00360     MP_DIGITS(&y)  = 0;
00361     MP_DIGITS(&r_) = 0;
00362     MP_DIGITS(&s_) = 0;
00363     MP_DIGITS(&u1) = 0;
00364     MP_DIGITS(&u2) = 0;
00365     MP_DIGITS(&v)  = 0;
00366     MP_DIGITS(&w)  = 0;
00367     CHECK_MPI_OK( mp_init(&p)  );
00368     CHECK_MPI_OK( mp_init(&q)  );
00369     CHECK_MPI_OK( mp_init(&g)  );
00370     CHECK_MPI_OK( mp_init(&y)  );
00371     CHECK_MPI_OK( mp_init(&r_) );
00372     CHECK_MPI_OK( mp_init(&s_) );
00373     CHECK_MPI_OK( mp_init(&u1) );
00374     CHECK_MPI_OK( mp_init(&u2) );
00375     CHECK_MPI_OK( mp_init(&v)  );
00376     CHECK_MPI_OK( mp_init(&w)  );
00377     /*
00378     ** Convert stored PQG and public key into MPI integers.
00379     */
00380     SECITEM_TO_MPINT(key->params.prime,    &p);
00381     SECITEM_TO_MPINT(key->params.subPrime, &q);
00382     SECITEM_TO_MPINT(key->params.base,     &g);
00383     SECITEM_TO_MPINT(key->publicValue,     &y);
00384     /*
00385     ** Convert received signature (r', s') into MPI integers.
00386     */
00387     OCTETS_TO_MPINT(signature->data, &r_, DSA_SUBPRIME_LEN);
00388     OCTETS_TO_MPINT(signature->data + DSA_SUBPRIME_LEN, &s_, DSA_SUBPRIME_LEN);
00389     /*
00390     ** Verify that 0 < r' < q and 0 < s' < q
00391     */
00392     if (mp_cmp_z(&r_) <= 0 || mp_cmp_z(&s_) <= 0 ||
00393         mp_cmp(&r_, &q) >= 0 || mp_cmp(&s_, &q) >= 0) {
00394        /* err is zero here. */
00395        PORT_SetError(SEC_ERROR_BAD_SIGNATURE);
00396        goto cleanup; /* will return verified == SECFailure */
00397     }
00398     /*
00399     ** FIPS 186-1, Section 6, Step 1
00400     **
00401     ** w = (s')**-1 mod q
00402     */
00403     CHECK_MPI_OK( mp_invmod(&s_, &q, &w) );      /* w = (s')**-1 mod q */
00404     /*
00405     ** FIPS 186-1, Section 6, Step 2
00406     **
00407     ** u1 = ((SHA1(M')) * w) mod q
00408     */
00409     SECITEM_TO_MPINT(*digest, &u1);              /* u1 = SHA1(M')     */
00410     CHECK_MPI_OK( mp_mulmod(&u1, &w, &q, &u1) ); /* u1 = u1 * w mod q */
00411     /*
00412     ** FIPS 186-1, Section 6, Step 3
00413     **
00414     ** u2 = ((r') * w) mod q
00415     */
00416     CHECK_MPI_OK( mp_mulmod(&r_, &w, &q, &u2) );
00417     /*
00418     ** FIPS 186-1, Section 6, Step 4
00419     **
00420     ** v = ((g**u1 * y**u2) mod p) mod q
00421     */
00422     CHECK_MPI_OK( mp_exptmod(&g, &u1, &p, &g) ); /* g = g**u1 mod p */
00423     CHECK_MPI_OK( mp_exptmod(&y, &u2, &p, &y) ); /* y = y**u2 mod p */
00424     CHECK_MPI_OK(  mp_mulmod(&g, &y, &p, &v)  ); /* v = g * y mod p */
00425     CHECK_MPI_OK(     mp_mod(&v, &q, &v)      ); /* v = v mod q     */
00426     /*
00427     ** Verification:  v == r'
00428     */
00429     if (mp_cmp(&v, &r_)) {
00430        PORT_SetError(SEC_ERROR_BAD_SIGNATURE);
00431        verified = SECFailure; /* Signature failed to verify. */
00432     } else {
00433        verified = SECSuccess; /* Signature verified. */
00434     }
00435 cleanup:
00436     mp_clear(&p);
00437     mp_clear(&q);
00438     mp_clear(&g);
00439     mp_clear(&y);
00440     mp_clear(&r_);
00441     mp_clear(&s_);
00442     mp_clear(&u1);
00443     mp_clear(&u2);
00444     mp_clear(&v);
00445     mp_clear(&w);
00446     if (err) {
00447        translate_mpi_error(err);
00448     }
00449     return verified;
00450 }