Back to index

lightning-sunbird  0.9+nobinonly
dh.c
Go to the documentation of this file.
00001 /* ***** BEGIN LICENSE BLOCK *****
00002  * Version: MPL 1.1/GPL 2.0/LGPL 2.1
00003  *
00004  * The contents of this file are subject to the Mozilla Public License Version
00005  * 1.1 (the "License"); you may not use this file except in compliance with
00006  * the License. You may obtain a copy of the License at
00007  * http://www.mozilla.org/MPL/
00008  *
00009  * Software distributed under the License is distributed on an "AS IS" basis,
00010  * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
00011  * for the specific language governing rights and limitations under the
00012  * License.
00013  *
00014  * The Original Code is the Netscape security libraries.
00015  *
00016  * The Initial Developer of the Original Code is
00017  * Netscape Communications Corporation.
00018  * Portions created by the Initial Developer are Copyright (C) 1994-2000
00019  * the Initial Developer. All Rights Reserved.
00020  *
00021  * Contributor(s):
00022  *
00023  * Alternatively, the contents of this file may be used under the terms of
00024  * either the GNU General Public License Version 2 or later (the "GPL"), or
00025  * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
00026  * in which case the provisions of the GPL or the LGPL are applicable instead
00027  * of those above. If you wish to allow use of your version of this file only
00028  * under the terms of either the GPL or the LGPL, and not to allow others to
00029  * use your version of this file under the terms of the MPL, indicate your
00030  * decision by deleting the provisions above and replace them with the notice
00031  * and other provisions required by the GPL or the LGPL. If you do not delete
00032  * the provisions above, a recipient may use your version of this file under
00033  * the terms of any one of the MPL, the GPL or the LGPL.
00034  *
00035  * ***** END LICENSE BLOCK ***** */
00036 
00037 /*
00038  * Diffie-Hellman parameter generation, key generation, and secret derivation.
00039  * KEA secret generation and verification.
00040  *
00041  * $Id: dh.c,v 1.7 2004/04/25 15:03:08 gerv%gerv.net Exp $
00042  */
00043 
00044 #include "prerr.h"
00045 #include "secerr.h"
00046 
00047 #include "blapi.h"
00048 #include "secitem.h"
00049 #include "mpi.h"
00050 #include "mpprime.h"
00051 #include "secmpi.h"
00052 
00053 #define DH_SECRET_KEY_LEN      20
00054 #define KEA_DERIVED_SECRET_LEN 128
00055 
00056 SECStatus 
00057 DH_GenParam(int primeLen, DHParams **params)
00058 {
00059     PRArenaPool *arena;
00060     DHParams *dhparams;
00061     unsigned char *pb = NULL;
00062     unsigned char *ab = NULL;
00063     unsigned long counter = 0;
00064     mp_int p, q, a, h, psub1, test;
00065     mp_err err = MP_OKAY;
00066     SECStatus rv = SECSuccess;
00067     if (!params || primeLen < 0) {
00068        PORT_SetError(SEC_ERROR_INVALID_ARGS);
00069        return SECFailure;
00070     }
00071     arena = PORT_NewArena(NSS_FREEBL_DEFAULT_CHUNKSIZE);
00072     if (!arena) {
00073        PORT_SetError(SEC_ERROR_NO_MEMORY);
00074        return SECFailure;
00075     }
00076     dhparams = (DHParams *)PORT_ArenaZAlloc(arena, sizeof(DHParams));
00077     if (!dhparams) {
00078        PORT_SetError(SEC_ERROR_NO_MEMORY);
00079        PORT_FreeArena(arena, PR_TRUE);
00080        return SECFailure;
00081     }
00082     dhparams->arena = arena;
00083     MP_DIGITS(&p) = 0;
00084     MP_DIGITS(&q) = 0;
00085     MP_DIGITS(&a) = 0;
00086     MP_DIGITS(&h) = 0;
00087     MP_DIGITS(&psub1) = 0;
00088     MP_DIGITS(&test) = 0;
00089     CHECK_MPI_OK( mp_init(&p) );
00090     CHECK_MPI_OK( mp_init(&q) );
00091     CHECK_MPI_OK( mp_init(&a) );
00092     CHECK_MPI_OK( mp_init(&h) );
00093     CHECK_MPI_OK( mp_init(&psub1) );
00094     CHECK_MPI_OK( mp_init(&test) );
00095     /* generate prime with MPI, uses Miller-Rabin to generate strong prime. */
00096     pb = PORT_Alloc(primeLen);
00097     CHECK_SEC_OK( RNG_GenerateGlobalRandomBytes(pb, primeLen) );
00098     pb[0]          |= 0x80; /* set high-order bit */
00099     pb[primeLen-1] |= 0x01; /* set low-order bit  */
00100     CHECK_MPI_OK( mp_read_unsigned_octets(&p, pb, primeLen) );
00101     CHECK_MPI_OK( mpp_make_prime(&p, primeLen * 8, PR_TRUE, &counter) );
00102     /* construct Sophie-Germain prime q = (p-1)/2. */
00103     CHECK_MPI_OK( mp_sub_d(&p, 1, &psub1) );
00104     CHECK_MPI_OK( mp_div_2(&psub1, &q)    );
00105     /* construct a generator from the prime. */
00106     ab = PORT_Alloc(primeLen);
00107     /* generate a candidate number a in p's field */
00108     CHECK_SEC_OK( RNG_GenerateGlobalRandomBytes(ab, primeLen) );
00109     CHECK_MPI_OK( mp_read_unsigned_octets(&a, ab, primeLen) );
00110     /* force a < p (note that quot(a/p) <= 1) */
00111     if ( mp_cmp(&a, &p) > 0 )
00112        CHECK_MPI_OK( mp_sub(&a, &p, &a) );
00113     do {
00114        /* check that a is in the range [2..p-1] */
00115        if ( mp_cmp_d(&a, 2) < 0 || mp_cmp(&a, &psub1) >= 0) {
00116            /* a is outside of the allowed range.  Set a=3 and keep going. */
00117             mp_set(&a, 3);
00118        }
00119        /* if a**q mod p != 1 then a is a generator */
00120        CHECK_MPI_OK( mp_exptmod(&a, &q, &p, &test) );
00121        if ( mp_cmp_d(&test, 1) != 0 )
00122            break;
00123        /* increment the candidate and try again. */
00124        CHECK_MPI_OK( mp_add_d(&a, 1, &a) );
00125     } while (PR_TRUE);
00126     MPINT_TO_SECITEM(&p, &dhparams->prime, arena);
00127     MPINT_TO_SECITEM(&a, &dhparams->base, arena);
00128     *params = dhparams;
00129 cleanup:
00130     mp_clear(&p);
00131     mp_clear(&q);
00132     mp_clear(&a);
00133     mp_clear(&h);
00134     mp_clear(&psub1);
00135     mp_clear(&test);
00136     if (pb) PORT_ZFree(pb, primeLen);
00137     if (ab) PORT_ZFree(ab, primeLen);
00138     if (err) {
00139        MP_TO_SEC_ERROR(err);
00140        rv = SECFailure;
00141     }
00142     if (rv)
00143        PORT_FreeArena(arena, PR_TRUE);
00144     return rv;
00145 }
00146 
00147 SECStatus 
00148 DH_NewKey(DHParams *params, DHPrivateKey **privKey)
00149 {
00150     PRArenaPool *arena;
00151     DHPrivateKey *key;
00152     mp_int g, xa, p, Ya;
00153     mp_err   err = MP_OKAY;
00154     SECStatus rv = SECSuccess;
00155     if (!params || !privKey) {
00156        PORT_SetError(SEC_ERROR_INVALID_ARGS);
00157        return SECFailure;
00158     }
00159     arena = PORT_NewArena(NSS_FREEBL_DEFAULT_CHUNKSIZE);
00160     if (!arena) {
00161        PORT_SetError(SEC_ERROR_NO_MEMORY);
00162        return SECFailure;
00163     }
00164     key = (DHPrivateKey *)PORT_ArenaZAlloc(arena, sizeof(DHPrivateKey));
00165     if (!key) {
00166        PORT_SetError(SEC_ERROR_NO_MEMORY);
00167        PORT_FreeArena(arena, PR_TRUE);
00168        return SECFailure;
00169     }
00170     key->arena = arena;
00171     MP_DIGITS(&g)  = 0;
00172     MP_DIGITS(&xa) = 0;
00173     MP_DIGITS(&p)  = 0;
00174     MP_DIGITS(&Ya) = 0;
00175     CHECK_MPI_OK( mp_init(&g)  );
00176     CHECK_MPI_OK( mp_init(&xa) );
00177     CHECK_MPI_OK( mp_init(&p)  );
00178     CHECK_MPI_OK( mp_init(&Ya) );
00179     /* Set private key's p */
00180     CHECK_SEC_OK( SECITEM_CopyItem(arena, &key->prime, &params->prime) );
00181     SECITEM_TO_MPINT(key->prime, &p);
00182     /* Set private key's g */
00183     CHECK_SEC_OK( SECITEM_CopyItem(arena, &key->base, &params->base) );
00184     SECITEM_TO_MPINT(key->base, &g);
00185     /* Generate private key xa */
00186     SECITEM_AllocItem(arena, &key->privateValue, DH_SECRET_KEY_LEN);
00187     RNG_GenerateGlobalRandomBytes(key->privateValue.data, 
00188                                   key->privateValue.len);
00189     SECITEM_TO_MPINT( key->privateValue, &xa );
00190     /* xa < p */
00191     CHECK_MPI_OK( mp_mod(&xa, &p, &xa) );
00192     /* Compute public key Ya = g ** xa mod p */
00193     CHECK_MPI_OK( mp_exptmod(&g, &xa, &p, &Ya) );
00194     MPINT_TO_SECITEM(&Ya, &key->publicValue, key->arena);
00195     *privKey = key;
00196 cleanup:
00197     mp_clear(&g);
00198     mp_clear(&xa);
00199     mp_clear(&p);
00200     mp_clear(&Ya);
00201     if (err) {
00202        MP_TO_SEC_ERROR(err);
00203        rv = SECFailure;
00204     }
00205     if (rv)
00206        PORT_FreeArena(arena, PR_TRUE);
00207     return rv;
00208 }
00209 
00210 SECStatus 
00211 DH_Derive(SECItem *publicValue, 
00212           SECItem *prime, 
00213           SECItem *privateValue, 
00214           SECItem *derivedSecret, 
00215           unsigned int maxOutBytes)
00216 {
00217     mp_int p, Xa, Yb, ZZ;
00218     mp_err err = MP_OKAY;
00219     unsigned int len = 0, nb;
00220     unsigned char *secret = NULL;
00221     if (!publicValue || !prime || !privateValue || !derivedSecret) {
00222        PORT_SetError(SEC_ERROR_INVALID_ARGS);
00223        return SECFailure;
00224     }
00225     memset(derivedSecret, 0, sizeof *derivedSecret);
00226     MP_DIGITS(&p)  = 0;
00227     MP_DIGITS(&Xa) = 0;
00228     MP_DIGITS(&Yb) = 0;
00229     MP_DIGITS(&ZZ) = 0;
00230     CHECK_MPI_OK( mp_init(&p)  );
00231     CHECK_MPI_OK( mp_init(&Xa) );
00232     CHECK_MPI_OK( mp_init(&Yb) );
00233     CHECK_MPI_OK( mp_init(&ZZ) );
00234     SECITEM_TO_MPINT(*publicValue,  &Yb);
00235     SECITEM_TO_MPINT(*privateValue, &Xa);
00236     SECITEM_TO_MPINT(*prime,        &p);
00237     /* ZZ = (Yb)**Xa mod p */
00238     CHECK_MPI_OK( mp_exptmod(&Yb, &Xa, &p, &ZZ) );
00239     /* number of bytes in the derived secret */
00240     len = mp_unsigned_octet_size(&ZZ);
00241     /* allocate a buffer which can hold the entire derived secret. */
00242     secret = PORT_Alloc(len);
00243     /* grab the derived secret */
00244     err = mp_to_unsigned_octets(&ZZ, secret, len);
00245     if (err >= 0) err = MP_OKAY;
00246     /* Take minimum of bytes requested and bytes in derived secret,
00247     ** if maxOutBytes is 0 take all of the bytes from the derived secret.
00248     */
00249     if (maxOutBytes > 0)
00250        nb = PR_MIN(len, maxOutBytes);
00251     else
00252        nb = len;
00253     SECITEM_AllocItem(NULL, derivedSecret, nb);
00254     memcpy(derivedSecret->data, secret, nb);
00255 cleanup:
00256     mp_clear(&p);
00257     mp_clear(&Xa);
00258     mp_clear(&Yb);
00259     mp_clear(&ZZ);
00260     if (secret) {
00261        /* free the buffer allocated for the full secret. */
00262        PORT_ZFree(secret, len);
00263     }
00264     if (err) {
00265        MP_TO_SEC_ERROR(err);
00266        if (derivedSecret->data) 
00267            PORT_ZFree(derivedSecret->data, derivedSecret->len);
00268        return SECFailure;
00269     }
00270     return SECSuccess;
00271 }
00272 
00273 SECStatus 
00274 KEA_Derive(SECItem *prime, 
00275            SECItem *public1, 
00276            SECItem *public2, 
00277            SECItem *private1, 
00278            SECItem *private2,
00279            SECItem *derivedSecret)
00280 {
00281     mp_int p, Y, R, r, x, t, u, w;
00282     mp_err err;
00283     unsigned char *secret = NULL;
00284     unsigned int len = 0, offset;
00285     if (!prime || !public1 || !public2 || !private1 || !private2 ||
00286         !derivedSecret) {
00287        PORT_SetError(SEC_ERROR_INVALID_ARGS);
00288        return SECFailure;
00289     }
00290     memset(derivedSecret, 0, sizeof *derivedSecret);
00291     MP_DIGITS(&p) = 0;
00292     MP_DIGITS(&Y) = 0;
00293     MP_DIGITS(&R) = 0;
00294     MP_DIGITS(&r) = 0;
00295     MP_DIGITS(&x) = 0;
00296     MP_DIGITS(&t) = 0;
00297     MP_DIGITS(&u) = 0;
00298     MP_DIGITS(&w) = 0;
00299     CHECK_MPI_OK( mp_init(&p) );
00300     CHECK_MPI_OK( mp_init(&Y) );
00301     CHECK_MPI_OK( mp_init(&R) );
00302     CHECK_MPI_OK( mp_init(&r) );
00303     CHECK_MPI_OK( mp_init(&x) );
00304     CHECK_MPI_OK( mp_init(&t) );
00305     CHECK_MPI_OK( mp_init(&u) );
00306     CHECK_MPI_OK( mp_init(&w) );
00307     SECITEM_TO_MPINT(*prime,    &p);
00308     SECITEM_TO_MPINT(*public1,  &Y);
00309     SECITEM_TO_MPINT(*public2,  &R);
00310     SECITEM_TO_MPINT(*private1, &r);
00311     SECITEM_TO_MPINT(*private2, &x);
00312     /* t = DH(Y, r, p) = Y ** r mod p */
00313     CHECK_MPI_OK( mp_exptmod(&Y, &r, &p, &t) );
00314     /* u = DH(R, x, p) = R ** x mod p */
00315     CHECK_MPI_OK( mp_exptmod(&R, &x, &p, &u) );
00316     /* w = (t + u) mod p */
00317     CHECK_MPI_OK( mp_addmod(&t, &u, &p, &w) );
00318     /* allocate a buffer for the full derived secret */
00319     len = mp_unsigned_octet_size(&w);
00320     secret = PORT_Alloc(len);
00321     /* grab the secret */
00322     err = mp_to_unsigned_octets(&w, secret, len);
00323     if (err > 0) err = MP_OKAY;
00324     /* allocate output buffer */
00325     SECITEM_AllocItem(NULL, derivedSecret, KEA_DERIVED_SECRET_LEN);
00326     memset(derivedSecret->data, 0, derivedSecret->len);
00327     /* copy in the 128 lsb of the secret */
00328     if (len >= KEA_DERIVED_SECRET_LEN) {
00329        memcpy(derivedSecret->data, secret + (len - KEA_DERIVED_SECRET_LEN),
00330               KEA_DERIVED_SECRET_LEN);
00331     } else {
00332        offset = KEA_DERIVED_SECRET_LEN - len;
00333        memcpy(derivedSecret->data + offset, secret, len);
00334     }
00335 cleanup:
00336     mp_clear(&p);
00337     mp_clear(&Y);
00338     mp_clear(&R);
00339     mp_clear(&r);
00340     mp_clear(&x);
00341     mp_clear(&t);
00342     mp_clear(&u);
00343     mp_clear(&w);
00344     if (secret)
00345        PORT_ZFree(secret, len);
00346     if (err) {
00347        MP_TO_SEC_ERROR(err);
00348        return SECFailure;
00349     }
00350     return SECSuccess;
00351 }
00352 
00353 PRBool 
00354 KEA_Verify(SECItem *Y, SECItem *prime, SECItem *subPrime)
00355 {
00356     mp_int p, q, y, r;
00357     mp_err err;
00358     int cmp = 1;  /* default is false */
00359     if (!Y || !prime || !subPrime) {
00360        PORT_SetError(SEC_ERROR_INVALID_ARGS);
00361        return SECFailure;
00362     }
00363     MP_DIGITS(&p) = 0;
00364     MP_DIGITS(&q) = 0;
00365     MP_DIGITS(&y) = 0;
00366     MP_DIGITS(&r) = 0;
00367     CHECK_MPI_OK( mp_init(&p) );
00368     CHECK_MPI_OK( mp_init(&q) );
00369     CHECK_MPI_OK( mp_init(&y) );
00370     CHECK_MPI_OK( mp_init(&r) );
00371     SECITEM_TO_MPINT(*prime,    &p);
00372     SECITEM_TO_MPINT(*subPrime, &q);
00373     SECITEM_TO_MPINT(*Y,        &y);
00374     /* compute r = y**q mod p */
00375     CHECK_MPI_OK( mp_exptmod(&y, &q, &p, &r) );
00376     /* compare to 1 */
00377     cmp = mp_cmp_d(&r, 1);
00378 cleanup:
00379     mp_clear(&p);
00380     mp_clear(&q);
00381     mp_clear(&y);
00382     mp_clear(&r);
00383     if (err) {
00384        MP_TO_SEC_ERROR(err);
00385        return PR_FALSE;
00386     }
00387     return (cmp == 0) ? PR_TRUE : PR_FALSE;
00388 }