Back to index

lightning-sunbird  0.9+nobinonly
pqg.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  * PQG parameter generation/verification.  Based on FIPS 186-1.
00039  *
00040  * $Id: pqg.c,v 1.9.2.4 2006/05/12 16:51:28 wtchang%redhat.com Exp $
00041  */
00042 
00043 #include "prerr.h"
00044 #include "secerr.h"
00045 
00046 #include "prtypes.h"
00047 #include "blapi.h"
00048 #include "secitem.h"
00049 #include "mpi.h"
00050 #include "mpprime.h"
00051 #include "mplogic.h"
00052 #include "secmpi.h"
00053 
00054 #define MAX_ITERATIONS 600  /* Maximum number of iterations of primegen */
00055 #define PQG_Q_PRIMALITY_TESTS 18 /* from HAC table 4.4 */
00056 #define PQG_P_PRIMALITY_TESTS 5  /* from HAC table 4.4 */
00057 
00058  /* XXX to be replaced by define in blapit.h */
00059 #define BITS_IN_Q 160
00060 
00061 /* For FIPS-compliance testing.
00062 ** The following array holds the seed defined in FIPS 186-1 appendix 5.
00063 ** This seed is used to generate P and Q according to appendix 2; use of
00064 ** this seed will exactly generate the PQG specified in appendix 2.
00065 */
00066 #ifdef FIPS_186_1_A5_TEST
00067 static const unsigned char fips_186_1_a5_pqseed[] = {
00068     0xd5, 0x01, 0x4e, 0x4b, 0x60, 0xef, 0x2b, 0xa8,
00069     0xb6, 0x21, 0x1b, 0x40, 0x62, 0xba, 0x32, 0x24,
00070     0xe0, 0x42, 0x7d, 0xd3
00071 };
00072 #endif
00073 
00074 /* Get a seed for generating P and Q.  If in testing mode, copy in the
00075 ** seed from FIPS 186-1 appendix 5.  Otherwise, obtain bytes from the
00076 ** global random number generator.
00077 */
00078 static SECStatus
00079 getPQseed(SECItem *seed, PRArenaPool* arena)
00080 {
00081     SECStatus rv;
00082 
00083     if (!seed->data) {
00084         seed->data = (unsigned char*)PORT_ArenaZAlloc(arena, seed->len);
00085     }
00086     if (!seed->data) {
00087        PORT_SetError(SEC_ERROR_NO_MEMORY);
00088        return SECFailure;
00089     }
00090 #ifdef FIPS_186_1_A5_TEST
00091     memcpy(seed->data, fips_186_1_a5_pqseed, seed->len);
00092     return SECSuccess;
00093 #else
00094     rv = RNG_GenerateGlobalRandomBytes(seed->data, seed->len);
00095     /*
00096      * NIST CMVP disallows a sequence of 20 bytes with the most
00097      * significant byte equal to 0.  Perhaps they interpret
00098      * "a sequence of at least 160 bits" as "a number >= 2^159".
00099      * So we always set the most significant bit to 1. (bug 334533)
00100      */
00101     seed->data[0] |= 0x80;
00102     return rv;
00103 #endif
00104 }
00105 
00106 /* Generate a candidate h value.  If in testing mode, use the h value
00107 ** specified in FIPS 186-1 appendix 5, h = 2.  Otherwise, obtain bytes
00108 ** from the global random number generator.
00109 */
00110 static SECStatus
00111 generate_h_candidate(SECItem *hit, mp_int *H)
00112 {
00113     SECStatus rv = SECSuccess;
00114     mp_err   err = MP_OKAY;
00115 #ifdef FIPS_186_1_A5_TEST
00116     memset(hit->data, 0, hit->len);
00117     hit->data[hit->len-1] = 0x02;
00118 #else
00119     rv = RNG_GenerateGlobalRandomBytes(hit->data, hit->len);
00120 #endif
00121     if (rv)
00122        return SECFailure;
00123     err = mp_read_unsigned_octets(H, hit->data, hit->len);
00124     if (err) {
00125        MP_TO_SEC_ERROR(err);
00126        return SECFailure;
00127     }
00128     return SECSuccess;
00129 }
00130 
00131 /* Compute SHA[(SEED + addend) mod 2**g]
00132 ** Result is placed in shaOutBuf.
00133 ** This computation is used in steps 2 and 7 of FIPS 186 Appendix 2.2 .
00134 */
00135 static SECStatus
00136 addToSeedThenSHA(const SECItem * seed,
00137                  unsigned long   addend,
00138                  int             g,
00139                  unsigned char * shaOutBuf)
00140 {
00141     SECItem str = { 0, 0, 0 };
00142     mp_int s, sum, modulus, tmp;
00143     mp_err    err = MP_OKAY;
00144     SECStatus rv  = SECSuccess;
00145     MP_DIGITS(&s)       = 0;
00146     MP_DIGITS(&sum)     = 0;
00147     MP_DIGITS(&modulus) = 0;
00148     MP_DIGITS(&tmp)     = 0;
00149     CHECK_MPI_OK( mp_init(&s) );
00150     CHECK_MPI_OK( mp_init(&sum) );
00151     CHECK_MPI_OK( mp_init(&modulus) );
00152     SECITEM_TO_MPINT(*seed, &s); /* s = seed */
00153     /* seed += addend */
00154     if (addend < MP_DIGIT_MAX) {
00155        CHECK_MPI_OK( mp_add_d(&s, (mp_digit)addend, &s) );
00156     } else {
00157        CHECK_MPI_OK( mp_init(&tmp) );
00158        CHECK_MPI_OK( mp_set_ulong(&tmp, addend) );
00159        CHECK_MPI_OK( mp_add(&s, &tmp, &s) );
00160     }
00161     CHECK_MPI_OK( mp_div_2d(&s, (mp_digit)g, NULL, &sum) );/*sum = s mod 2**g */
00162     MPINT_TO_SECITEM(&sum, &str, NULL);
00163     rv = SHA1_HashBuf(shaOutBuf, str.data, str.len); /* SHA1 hash result */
00164 cleanup:
00165     mp_clear(&s);
00166     mp_clear(&sum);
00167     mp_clear(&modulus);
00168     mp_clear(&tmp);
00169     if (str.data)
00170        SECITEM_ZfreeItem(&str, PR_FALSE);
00171     if (err) {
00172        MP_TO_SEC_ERROR(err);
00173        return SECFailure;
00174     }
00175     return rv;
00176 }
00177 
00178 /*
00179 **  Perform steps 2 and 3 of FIPS 186, appendix 2.2.
00180 **  Generate Q from seed.
00181 */
00182 static SECStatus
00183 makeQfromSeed(
00184       unsigned int  g,          /* input.  Length of seed in bits. */
00185 const SECItem   *   seed,       /* input.  */
00186       mp_int    *   Q)          /* output. */
00187 {
00188     unsigned char sha1[SHA1_LENGTH];
00189     unsigned char sha2[SHA1_LENGTH];
00190     unsigned char U[SHA1_LENGTH];
00191     SECStatus rv  = SECSuccess;
00192     mp_err    err = MP_OKAY;
00193     int i;
00194     /* ******************************************************************
00195     ** Step 2.
00196     ** "Compute U = SHA[SEED] XOR SHA[(SEED+1) mod 2**g]."
00197     **/
00198     CHECK_SEC_OK( SHA1_HashBuf(sha1, seed->data, seed->len) );
00199     CHECK_SEC_OK( addToSeedThenSHA(seed, 1, g, sha2) );
00200     for (i=0; i<SHA1_LENGTH; ++i) 
00201        U[i] = sha1[i] ^ sha2[i];
00202     /* ******************************************************************
00203     ** Step 3.
00204     ** "Form Q from U by setting the most signficant bit (the 2**159 bit)
00205     **  and the least signficant bit to 1.  In terms of boolean operations,
00206     **  Q = U OR 2**159 OR 1.  Note that 2**159 < Q < 2**160."
00207     */
00208     U[0]             |= 0x80;  /* U is MSB first */
00209     U[SHA1_LENGTH-1] |= 0x01;
00210     err = mp_read_unsigned_octets(Q, U, SHA1_LENGTH);
00211 cleanup:
00212      memset(U, 0, SHA1_LENGTH);
00213      memset(sha1, 0, SHA1_LENGTH);
00214      memset(sha2, 0, SHA1_LENGTH);
00215      if (err) {
00216        MP_TO_SEC_ERROR(err);
00217        return SECFailure;
00218      }
00219      return rv;
00220 }
00221 
00222 /*  Perform steps 7, 8 and 9 of FIPS 186, appendix 2.2.
00223 **  Generate P from Q, seed, L, and offset.
00224 */
00225 static SECStatus
00226 makePfromQandSeed(
00227       unsigned int  L,          /* Length of P in bits.  Per FIPS 186. */
00228       unsigned int  offset,     /* Per FIPS 186, appendix 2.2. */
00229       unsigned int  g,          /* input.  Length of seed in bits. */
00230 const SECItem   *   seed,       /* input.  */
00231 const mp_int    *   Q,          /* input.  */
00232       mp_int    *   P)          /* output. */
00233 {
00234     unsigned int  k;            /* Per FIPS 186, appendix 2.2. */
00235     unsigned int  n;            /* Per FIPS 186, appendix 2.2. */
00236     mp_digit      b;            /* Per FIPS 186, appendix 2.2. */
00237     unsigned char V_k[SHA1_LENGTH];
00238     mp_int        W, X, c, twoQ, V_n, tmp;
00239     mp_err    err = MP_OKAY;
00240     SECStatus rv  = SECSuccess;
00241     /* Initialize bignums */
00242     MP_DIGITS(&W)     = 0;
00243     MP_DIGITS(&X)     = 0;
00244     MP_DIGITS(&c)     = 0;
00245     MP_DIGITS(&twoQ)  = 0;
00246     MP_DIGITS(&V_n)   = 0;
00247     MP_DIGITS(&tmp)   = 0;
00248     CHECK_MPI_OK( mp_init(&W)    );
00249     CHECK_MPI_OK( mp_init(&X)    );
00250     CHECK_MPI_OK( mp_init(&c)    );
00251     CHECK_MPI_OK( mp_init(&twoQ) );
00252     CHECK_MPI_OK( mp_init(&tmp)  );
00253     CHECK_MPI_OK( mp_init(&V_n)  );
00254     /* L - 1 = n*160 + b */
00255     n = (L - 1) / BITS_IN_Q;
00256     b = (L - 1) % BITS_IN_Q;
00257     /* ******************************************************************
00258     ** Step 7.
00259     **  "for k = 0 ... n let
00260     **           V_k = SHA[(SEED + offset + k) mod 2**g]."
00261     **
00262     ** Step 8.
00263     **  "Let W be the integer 
00264     **    W = V_0 + (V_1 * 2**160) + ... + (V_n-1 * 2**((n-1)*160)) 
00265     **         + ((V_n mod 2**b) * 2**(n*160))
00266     */
00267     for (k=0; k<n; ++k) { /* Do the first n terms of V_k */
00268        /* Do step 7 for iteration k.
00269        ** V_k = SHA[(seed + offset + k) mod 2**g]
00270        */
00271        CHECK_SEC_OK( addToSeedThenSHA(seed, offset + k, g, V_k) );
00272        /* Do step 8 for iteration k.
00273        ** W += V_k * 2**(k*160)
00274        */
00275        OCTETS_TO_MPINT(V_k, &tmp, SHA1_LENGTH);      /* get bignum V_k     */
00276        CHECK_MPI_OK( mpl_lsh(&tmp, &tmp, k*160) );   /* tmp = V_k << k*160 */
00277        CHECK_MPI_OK( mp_add(&W, &tmp, &W) );         /* W += tmp           */
00278     }
00279     /* Step 8, continued.
00280     **   [W += ((V_n mod 2**b) * 2**(n*160))] 
00281     */
00282     CHECK_SEC_OK( addToSeedThenSHA(seed, offset + n, g, V_k) );
00283     OCTETS_TO_MPINT(V_k, &V_n, SHA1_LENGTH);          /* get bignum V_n     */
00284     CHECK_MPI_OK( mp_div_2d(&V_n, b, NULL, &tmp) );   /* tmp = V_n mod 2**b */
00285     CHECK_MPI_OK( mpl_lsh(&tmp, &tmp, n*160) );       /* tmp = tmp << n*160 */
00286     CHECK_MPI_OK( mp_add(&W, &tmp, &W) );             /* W += tmp           */
00287     /* Step 8, continued.
00288     ** "and let X = W + 2**(L-1).
00289     **  Note that 0 <= W < 2**(L-1) and hence 2**(L-1) <= X < 2**L."
00290     */
00291     CHECK_MPI_OK( mpl_set_bit(&X, (mp_size)(L-1), 1) );    /* X = 2**(L-1) */
00292     CHECK_MPI_OK( mp_add(&X, &W, &X) );                    /* X += W       */
00293     /*************************************************************
00294     ** Step 9.
00295     ** "Let c = X mod 2q  and set p = X - (c - 1).
00296     **  Note that p is congruent to 1 mod 2q."
00297     */
00298     CHECK_MPI_OK( mp_mul_2(Q, &twoQ) );                    /* 2q           */
00299     CHECK_MPI_OK( mp_mod(&X, &twoQ, &c) );                 /* c = X mod 2q */
00300     CHECK_MPI_OK( mp_sub_d(&c, 1, &c) );                   /* c -= 1       */
00301     CHECK_MPI_OK( mp_sub(&X, &c, P) );                     /* P = X - c    */
00302 cleanup:
00303     mp_clear(&W);
00304     mp_clear(&X);
00305     mp_clear(&c);
00306     mp_clear(&twoQ);
00307     mp_clear(&V_n);
00308     mp_clear(&tmp);
00309     if (err) {
00310        MP_TO_SEC_ERROR(err);
00311        return SECFailure;
00312     }
00313     return rv;
00314 }
00315 
00316 /*
00317 ** Generate G from h, P, and Q.
00318 */
00319 static SECStatus
00320 makeGfromH(const mp_int *P,     /* input.  */
00321            const mp_int *Q,     /* input.  */
00322                  mp_int *H,     /* input and output. */
00323                  mp_int *G,     /* output. */
00324                  PRBool *passed)
00325 {
00326     mp_int exp, pm1;
00327     mp_err err = MP_OKAY;
00328     SECStatus rv = SECSuccess;
00329     *passed = PR_FALSE;
00330     MP_DIGITS(&exp) = 0;
00331     MP_DIGITS(&pm1) = 0;
00332     CHECK_MPI_OK( mp_init(&exp) );
00333     CHECK_MPI_OK( mp_init(&pm1) );
00334     CHECK_MPI_OK( mp_sub_d(P, 1, &pm1) );        /* P - 1            */
00335     if ( mp_cmp(H, &pm1) >= 0)                   /* H >= P-1         */
00336        CHECK_MPI_OK( mp_sub(H, &pm1, H) );      /* H = H mod (P-1)  */
00337     /* Let b = 2**n (smallest power of 2 greater than P).
00338     ** Since P-1 >= b/2, and H < b, quotient(H/(P-1)) = 0 or 1
00339     ** so the above operation safely computes H mod (P-1)
00340     */
00341     /* Check for H = to 0 or 1.  Regen H if so.  (Regen means return error). */
00342     if (mp_cmp_d(H, 1) <= 0) {
00343        rv = SECFailure;
00344        goto cleanup;
00345     }
00346     /* Compute G, according to the equation  G = (H ** ((P-1)/Q)) mod P */
00347     CHECK_MPI_OK( mp_div(&pm1, Q, &exp, NULL) );  /* exp = (P-1)/Q      */
00348     CHECK_MPI_OK( mp_exptmod(H, &exp, P, G) );    /* G = H ** exp mod P */
00349     /* Check for G == 0 or G == 1, return error if so. */
00350     if (mp_cmp_d(G, 1) <= 0) {
00351        rv = SECFailure;
00352        goto cleanup;
00353     }
00354     *passed = PR_TRUE;
00355 cleanup:
00356     mp_clear(&exp);
00357     mp_clear(&pm1);
00358     if (err) {
00359        MP_TO_SEC_ERROR(err);
00360        rv = SECFailure;
00361     }
00362     return rv;
00363 }
00364 
00365 SECStatus
00366 PQG_ParamGen(unsigned int j, PQGParams **pParams, PQGVerify **pVfy)
00367 {
00368     unsigned int L;            /* Length of P in bits.  Per FIPS 186. */
00369     unsigned int seedBytes;
00370 
00371     if (j > 8 || !pParams || !pVfy) {
00372        PORT_SetError(SEC_ERROR_INVALID_ARGS);
00373         return SECFailure;
00374     }
00375     L = 512 + (j * 64);         /* bits in P */
00376     seedBytes = L/8;
00377     return PQG_ParamGenSeedLen(j, seedBytes, pParams, pVfy);
00378 }
00379 
00380 /* This code uses labels and gotos, so that it can follow the numbered
00381 ** steps in the algorithms from FIPS 186 appendix 2.2 very closely,
00382 ** and so that the correctness of this code can be easily verified.
00383 ** So, please forgive the ugly c code.
00384 **/
00385 SECStatus
00386 PQG_ParamGenSeedLen(unsigned int j, unsigned int seedBytes,
00387                     PQGParams **pParams, PQGVerify **pVfy)
00388 {
00389     unsigned int  L;        /* Length of P in bits.  Per FIPS 186. */
00390     unsigned int  n;        /* Per FIPS 186, appendix 2.2. */
00391     unsigned int  b;        /* Per FIPS 186, appendix 2.2. */
00392     unsigned int  g;        /* Per FIPS 186, appendix 2.2. */
00393     unsigned int  counter;  /* Per FIPS 186, appendix 2.2. */
00394     unsigned int  offset;   /* Per FIPS 186, appendix 2.2. */
00395     SECItem      *seed;     /* Per FIPS 186, appendix 2.2. */
00396     PRArenaPool  *arena  = NULL;
00397     PQGParams    *params = NULL;
00398     PQGVerify    *verify = NULL;
00399     PRBool passed;
00400     SECItem hit = { 0, 0, 0 };
00401     mp_int P, Q, G, H, l;
00402     mp_err    err = MP_OKAY;
00403     SECStatus rv  = SECFailure;
00404     int iterations = 0;
00405     if (j > 8 || seedBytes < 20 || !pParams || !pVfy) {
00406        PORT_SetError(SEC_ERROR_INVALID_ARGS);
00407        return SECFailure;
00408     }
00409     /* Initialize an arena for the params. */
00410     arena = PORT_NewArena(NSS_FREEBL_DEFAULT_CHUNKSIZE);
00411     if (!arena) {
00412        PORT_SetError(SEC_ERROR_NO_MEMORY);
00413        return SECFailure;
00414     }
00415     params = (PQGParams *)PORT_ArenaZAlloc(arena, sizeof(PQGParams));
00416     if (!params) {
00417        PORT_SetError(SEC_ERROR_NO_MEMORY);
00418        PORT_FreeArena(arena, PR_TRUE);
00419        return SECFailure;
00420     }
00421     params->arena = arena;
00422     /* Initialize an arena for the verify. */
00423     arena = PORT_NewArena(NSS_FREEBL_DEFAULT_CHUNKSIZE);
00424     if (!arena) {
00425        PORT_SetError(SEC_ERROR_NO_MEMORY);
00426        PORT_FreeArena(params->arena, PR_TRUE);
00427        return SECFailure;
00428     }
00429     verify = (PQGVerify *)PORT_ArenaZAlloc(arena, sizeof(PQGVerify));
00430     if (!verify) {
00431        PORT_SetError(SEC_ERROR_NO_MEMORY);
00432        PORT_FreeArena(arena, PR_TRUE);
00433        PORT_FreeArena(params->arena, PR_TRUE);
00434        return SECFailure;
00435     }
00436     verify->arena = arena;
00437     seed = &verify->seed;
00438     arena = NULL;
00439     /* Initialize bignums */
00440     MP_DIGITS(&P) = 0;
00441     MP_DIGITS(&Q) = 0;
00442     MP_DIGITS(&G) = 0;
00443     MP_DIGITS(&H) = 0;
00444     MP_DIGITS(&l) = 0;
00445     CHECK_MPI_OK( mp_init(&P) );
00446     CHECK_MPI_OK( mp_init(&Q) );
00447     CHECK_MPI_OK( mp_init(&G) );
00448     CHECK_MPI_OK( mp_init(&H) );
00449     CHECK_MPI_OK( mp_init(&l) );
00450     /* Compute lengths. */
00451     L = 512 + (j * 64);               /* bits in P */
00452     n = (L - 1) / BITS_IN_Q;          /* BITS_IN_Q is 160 */  
00453     b = (L - 1) % BITS_IN_Q;
00454     g = seedBytes * BITS_PER_BYTE;    /* bits in seed, NOT G of PQG. */
00455 step_1:
00456     /* ******************************************************************
00457     ** Step 1.
00458     ** "Choose an abitrary sequence of at least 160 bits and call it SEED.
00459     **  Let g be the length of SEED in bits."
00460     */
00461     if (++iterations > MAX_ITERATIONS) {        /* give up after a while */
00462         PORT_SetError(SEC_ERROR_NEED_RANDOM);
00463         goto cleanup;
00464     }
00465     seed->len = seedBytes;
00466     CHECK_SEC_OK( getPQseed(seed, verify->arena) );
00467     /* ******************************************************************
00468     ** Step 2.
00469     ** "Compute U = SHA[SEED] XOR SHA[(SEED+1) mod 2**g]."
00470     **
00471     ** Step 3.
00472     ** "Form Q from U by setting the most signficant bit (the 2**159 bit) 
00473     **  and the least signficant bit to 1.  In terms of boolean operations,
00474     **  Q = U OR 2**159 OR 1.  Note that 2**159 < Q < 2**160."
00475     */
00476     CHECK_SEC_OK( makeQfromSeed(g, seed, &Q) );
00477     /* ******************************************************************
00478     ** Step 4.
00479     ** "Use a robust primality testing algorithm to test whether q is prime."
00480     **
00481     ** Appendix 2.1 states that a Rabin test with at least 50 iterations
00482     ** "will give an acceptable probability of error."
00483     */
00484     /*CHECK_SEC_OK( prm_RabinTest(&Q, &passed) );*/
00485     err = mpp_pprime(&Q, PQG_Q_PRIMALITY_TESTS);
00486     passed = (err == MP_YES) ? SECSuccess : SECFailure;
00487     /* ******************************************************************
00488     ** Step 5. "If q is not prime, goto step 1."
00489     */
00490     if (passed != SECSuccess)
00491         goto step_1;
00492     /* ******************************************************************
00493     ** Step 6. "Let counter = 0 and offset = 2."
00494     */
00495     counter = 0;
00496     offset  = 2;
00497 step_7:
00498     /* ******************************************************************
00499     ** Step 7.
00500     ** "for k = 0 ... n let
00501     **          V_k = SHA[(SEED + offset + k) mod 2**g]."
00502     **
00503     ** Step 8.
00504     ** "Let W be the sum of  (V_k * 2**(k*160)) for k = 0 ... n
00505     **  and let X = W + 2**(L-1).
00506     **  Note that 0 <= W < 2**(L-1) and hence 2**(L-1) <= X < 2**L."
00507     **
00508     ** Step 9.
00509     ** "Let c = X mod 2q  and set p = X - (c - 1).
00510     **  Note that p is congruent to 1 mod 2q."
00511     */
00512     CHECK_SEC_OK( makePfromQandSeed(L, offset, g, seed, &Q, &P) );
00513     /*************************************************************
00514     ** Step 10.
00515     ** "if p < 2**(L-1), then goto step 13."
00516     */
00517     CHECK_MPI_OK( mpl_set_bit(&l, (mp_size)(L-1), 1) ); /* l = 2**(L-1) */
00518     if (mp_cmp(&P, &l) < 0)
00519         goto step_13;
00520     /************************************************************
00521     ** Step 11.
00522     ** "Perform a robust primality test on p."
00523     */
00524     /*CHECK_SEC_OK( prm_RabinTest(&P, &passed) );*/
00525     err = mpp_pprime(&P, PQG_P_PRIMALITY_TESTS);
00526     passed = (err == MP_YES) ? SECSuccess : SECFailure;
00527     /* ******************************************************************
00528     ** Step 12. "If p passes the test performed in step 11, go to step 15."
00529     */
00530     if (passed == SECSuccess)
00531         goto step_15;
00532 step_13:
00533     /* ******************************************************************
00534     ** Step 13.  "Let counter = counter + 1 and offset = offset + n + 1."
00535     */
00536     counter++;
00537     offset += n + 1;
00538     /* ******************************************************************
00539     ** Step 14.  "If counter >= 4096 goto step 1, otherwise go to step 7."
00540     */
00541     if (counter >= 4096)
00542         goto step_1;
00543     goto step_7;
00544 step_15:
00545     /* ******************************************************************
00546     ** Step 15.  
00547     ** "Save the value of SEED and the value of counter for use
00548     **  in certifying the proper generation of p and q."
00549     */
00550     /* Generate h. */
00551     SECITEM_AllocItem(NULL, &hit, L/8); /* h is no longer than p */
00552     if (!hit.data) goto cleanup;
00553     do {
00554        /* loop generate h until 1<h<p-1 and (h**[(p-1)/q])mod p > 1 */
00555        CHECK_SEC_OK( generate_h_candidate(&hit, &H) );
00556         CHECK_SEC_OK( makeGfromH(&P, &Q, &H, &G, &passed) );
00557     } while (passed != PR_TRUE);
00558     /* All generation is done.  Now, save the PQG params.  */
00559     MPINT_TO_SECITEM(&P, &params->prime,    params->arena);
00560     MPINT_TO_SECITEM(&Q, &params->subPrime, params->arena);
00561     MPINT_TO_SECITEM(&G, &params->base,     params->arena);
00562     MPINT_TO_SECITEM(&H, &verify->h,        verify->arena);
00563     verify->counter = counter;
00564     *pParams = params;
00565     *pVfy = verify;
00566 cleanup:
00567     mp_clear(&P);
00568     mp_clear(&Q);
00569     mp_clear(&G);
00570     mp_clear(&H);
00571     mp_clear(&l);
00572     if (err) {
00573        MP_TO_SEC_ERROR(err);
00574        rv = SECFailure;
00575     }
00576     if (rv) {
00577        PORT_FreeArena(params->arena, PR_TRUE);
00578        PORT_FreeArena(verify->arena, PR_TRUE);
00579     }
00580     if (hit.data) {
00581         SECITEM_FreeItem(&hit, PR_FALSE);
00582     }
00583     return rv;
00584 }
00585 
00586 SECStatus   
00587 PQG_VerifyParams(const PQGParams *params, 
00588                  const PQGVerify *vfy, SECStatus *result)
00589 {
00590     SECStatus rv = SECSuccess;
00591     int passed;
00592     unsigned int g, n, L, offset;
00593     mp_int P, Q, G, P_, Q_, G_, r, h;
00594     mp_err err = MP_OKAY;
00595     int j;
00596 #define CHECKPARAM(cond)      \
00597     if (!(cond)) {            \
00598        *result = SECFailure; \
00599        goto cleanup;         \
00600     }
00601     if (!params || !vfy || !result) {
00602        PORT_SetError(SEC_ERROR_INVALID_ARGS);
00603        return SECFailure;
00604     }
00605     MP_DIGITS(&P) = 0;
00606     MP_DIGITS(&Q) = 0;
00607     MP_DIGITS(&G) = 0;
00608     MP_DIGITS(&P_) = 0;
00609     MP_DIGITS(&Q_) = 0;
00610     MP_DIGITS(&G_) = 0;
00611     MP_DIGITS(&r) = 0;
00612     MP_DIGITS(&h) = 0;
00613     CHECK_MPI_OK( mp_init(&P) );
00614     CHECK_MPI_OK( mp_init(&Q) );
00615     CHECK_MPI_OK( mp_init(&G) );
00616     CHECK_MPI_OK( mp_init(&P_) );
00617     CHECK_MPI_OK( mp_init(&Q_) );
00618     CHECK_MPI_OK( mp_init(&G_) );
00619     CHECK_MPI_OK( mp_init(&r) );
00620     CHECK_MPI_OK( mp_init(&h) );
00621     *result = SECSuccess;
00622     SECITEM_TO_MPINT(params->prime,    &P);
00623     SECITEM_TO_MPINT(params->subPrime, &Q);
00624     SECITEM_TO_MPINT(params->base,     &G);
00625     /* 1.  Q is 160 bits long. */
00626     CHECKPARAM( mpl_significant_bits(&Q) == 160 );
00627     /* 2.  P is one of the 9 valid lengths. */
00628     L = mpl_significant_bits(&P);
00629     j = PQG_PBITS_TO_INDEX(L);
00630     CHECKPARAM( j >= 0 && j <= 8 );
00631     /* 3.  G < P */
00632     CHECKPARAM( mp_cmp(&G, &P) < 0 );
00633     /* 4.  P % Q == 1 */
00634     CHECK_MPI_OK( mp_mod(&P, &Q, &r) );
00635     CHECKPARAM( mp_cmp_d(&r, 1) == 0 );
00636     /* 5.  Q is prime */
00637     CHECKPARAM( mpp_pprime(&Q, PQG_Q_PRIMALITY_TESTS) == MP_YES );
00638     /* 6.  P is prime */
00639     CHECKPARAM( mpp_pprime(&P, PQG_P_PRIMALITY_TESTS) == MP_YES );
00640     /* Steps 7-12 are done only if the optional PQGVerify is supplied. */
00641     /* 7.  counter < 4096 */
00642     CHECKPARAM( vfy->counter < 4096 );
00643     /* 8.  g >= 160 and g < 2048   (g is length of seed in bits) */
00644     g = vfy->seed.len * 8;
00645     CHECKPARAM( g >= 160 && g < 2048 );
00646     /* 9.  Q generated from SEED matches Q in PQGParams. */
00647     CHECK_SEC_OK( makeQfromSeed(g, &vfy->seed, &Q_) );
00648     CHECKPARAM( mp_cmp(&Q, &Q_) == 0 );
00649     /* 10. P generated from (L, counter, g, SEED, Q) matches P in PQGParams. */
00650     n = (L - 1) / BITS_IN_Q;
00651     offset = vfy->counter * (n + 1) + 2;
00652     CHECK_SEC_OK( makePfromQandSeed(L, offset, g, &vfy->seed, &Q, &P_) );
00653     CHECKPARAM( mp_cmp(&P, &P_) == 0 );
00654     /* Next two are optional: if h == 0 ignore */
00655     if (vfy->h.len == 0) goto cleanup;
00656     /* 11. 1 < h < P-1 */
00657     SECITEM_TO_MPINT(vfy->h, &h);
00658     CHECK_MPI_OK( mpl_set_bit(&P, 0, 0) ); /* P is prime, p-1 == zero 1st bit */
00659     CHECKPARAM( mp_cmp_d(&h, 1) > 0 && mp_cmp(&h, &P) );
00660     CHECK_MPI_OK( mpl_set_bit(&P, 0, 1) ); /* set it back */
00661     /* 12. G generated from h matches G in PQGParams. */
00662     CHECK_SEC_OK( makeGfromH(&P, &Q, &h, &G_, &passed) );
00663     CHECKPARAM( passed && mp_cmp(&G, &G_) == 0 );
00664 cleanup:
00665     mp_clear(&P);
00666     mp_clear(&Q);
00667     mp_clear(&G);
00668     mp_clear(&P_);
00669     mp_clear(&Q_);
00670     mp_clear(&G_);
00671     mp_clear(&r);
00672     mp_clear(&h);
00673     if (err) {
00674        MP_TO_SEC_ERROR(err);
00675        rv = SECFailure;
00676     }
00677     return rv;
00678 }
00679 
00680