开通博客赚积分
发布资源赚积分
分类

源码开发语言/平台
当前位置：首页 > 源码/资料 > 加密解密 > CA认证 > 查看源码
pqg.c
资源名称：nss-3.1.1.tar.gz　[点击查看]
上传用户：lyxiangda
上传日期：2007-01-12
资源大小：3042k
文件大小：22k
源码类别：

CA认证

开发平台：

WINDOWS

pqg.c：源码内容
  1. /*
  2.  * The contents of this file are subject to the Mozilla Public
  3.  * License Version 1.1 (the "License"); you may not use this file
  4.  * except in compliance with the License. You may obtain a copy of
  5.  * the License at http://www.mozilla.org/MPL/
  6.  * 
  7.  * Software distributed under the License is distributed on an "AS
  8.  * IS" basis, WITHOUT WARRANTY OF ANY KIND, either express or
  9.  * implied. See the License for the specific language governing
  10.  * rights and limitations under the License.
  11.  * 
  12.  * The Original Code is the Netscape security libraries.
  13.  * 
  14.  * The Initial Developer of the Original Code is Netscape
  15.  * Communications Corporation. Portions created by Netscape are 
  16.  * Copyright (C) 1994-2000 Netscape Communications Corporation.  All
  17.  * Rights Reserved.
  18.  * 
  19.  * Contributor(s):
  20.  * 
  21.  * Alternatively, the contents of this file may be used under the
  22.  * terms of the GNU General Public License Version 2 or later (the
  23.  * "GPL"), in which case the provisions of the GPL are applicable 
  24.  * instead of those above. If you wish to allow use of your 
  25.  * version of this file only under the terms of the GPL and not to
  26.  * allow others to use your version of this file under the MPL,
  27.  * indicate your decision by deleting the provisions above and
  28.  * replace them with the notice and other provisions required by
  29.  * the GPL.  If you do not delete the provisions above, a recipient
  30.  * may use your version of this file under either the MPL or the
  31.  * GPL.
  32.  */
  34. /*
  35.  * PQG parameter generation/verification.  Based on FIPS 186-1.
  36.  *
  37.  * $Id: pqg.c,v 1.5 2000/09/29 04:03:34 nelsonb%netscape.com Exp $
  38.  */
  40. #include "prerr.h"
  41. #include "secerr.h"
  43. #include "prtypes.h"
  44. #include "blapi.h"
  45. #include "secitem.h"
  46. #include "mpi.h"
  47. #include "mpprime.h"
  48. #include "mplogic.h"
  49. #include "secmpi.h"
  51. #define MAX_ITERATIONS 5  /* Maximum number of iterations of primegen */
  52. #define NUMITER        40 /* Number iterations for primality tests    */
  54.  /* XXX to be replaced by define in blapit.h */
  55. #define BITS_IN_Q 160
  57. /* For FIPS-compliance testing.
  58. ** The following array holds the seed defined in FIPS 186-1 appendix 5.
  59. ** This seed is used to generate P and Q according to appendix 2; use of
  60. ** this seed will exactly generate the PQG specified in appendix 2.
  61. */
  62. #ifdef FIPS_186_1_A5_TEST
  63. static const unsigned char fips_186_1_a5_pqseed[] = {
  64.     0xd5, 0x01, 0x4e, 0x4b, 0x60, 0xef, 0x2b, 0xa8,
  65.     0xb6, 0x21, 0x1b, 0x40, 0x62, 0xba, 0x32, 0x24,
  66.     0xe0, 0x42, 0x7d, 0xd3
  67. };
  68. #endif
  70. /* Get a seed for generating P and Q.  If in testing mode, copy in the
  71. ** seed from FIPS 186-1 appendix 5.  Otherwise, obtain bytes from the
  72. ** global random number generator.
  73. */
  74. static SECStatus
  75. getPQseed(SECItem *seed)
  76. {
  77.     if (seed->data) {
  78.         PORT_Free(seed->data);
  79.         seed->data = NULL;
  80.     }
  81.     seed->data = (unsigned char*)PORT_ZAlloc(seed->len);
  82.     if (!seed->data) {
  83. PORT_SetError(SEC_ERROR_NO_MEMORY);
  84. return SECFailure;
  85.     }
  86. #ifdef FIPS_186_1_A5_TEST
  87.     memcpy(seed->data, fips_186_1_a5_pqseed, seed->len);
  88.     return SECSuccess;
  89. #else
  90.     return RNG_GenerateGlobalRandomBytes(seed->data, seed->len);
  91. #endif
  92. }
  94. /* Generate a candidate h value.  If in testing mode, use the h value
  95. ** specified in FIPS 186-1 appendix 5, h = 2.  Otherwise, obtain bytes
  96. ** from the global random number generator.
  97. */
  98. static SECStatus
  99. generate_h_candidate(SECItem *hit, mp_int *H)
  100. {
  101.     SECStatus rv = SECSuccess;
  102.     mp_err   err = MP_OKAY;
  103. #ifdef FIPS_186_1_A5_TEST
  104.     memset(hit->data, 0, hit->len);
  105.     hit->data[hit->len-1] = 0x02;
  106. #else
  107.     rv = RNG_GenerateGlobalRandomBytes(hit->data, hit->len);
  108. #endif
  109.     if (rv)
  110. return SECFailure;
  111.     err = mp_read_unsigned_octets(H, hit->data, hit->len);
  112.     if (err) {
  113. MP_TO_SEC_ERROR(err);
  114. return SECFailure;
  115.     }
  116.     return SECSuccess;
  117. }
  119. /* Compute SHA[(SEED + addend) mod 2**g]
  120. ** Result is placed in shaOutBuf.
  121. ** This computation is used in steps 2 and 7 of FIPS 186 Appendix 2.2 .
  122. */
  123. static SECStatus
  124. addToSeedThenSHA(const SECItem * seed,
  125.                  unsigned long   addend,
  126.                  int             g,
  127.                  unsigned char * shaOutBuf)
  128. {
  129.     SECItem str = { 0, 0, 0 };
  130.     mp_int s, sum, modulus, tmp;
  131.     mp_err    err = MP_OKAY;
  132.     SECStatus rv  = SECSuccess;
  133.     MP_DIGITS(&s)       = 0;
  134.     MP_DIGITS(&sum)     = 0;
  135.     MP_DIGITS(&modulus) = 0;
  136.     MP_DIGITS(&tmp)     = 0;
  137.     CHECK_MPI_OK( mp_init(&s) );
  138.     CHECK_MPI_OK( mp_init(&sum) );
  139.     CHECK_MPI_OK( mp_init(&modulus) );
  140.     SECITEM_TO_MPINT(*seed, &s); /* s = seed */
  141.     /* seed += addend */
  142.     if (addend < MP_DIGIT_MAX) {
  143. CHECK_MPI_OK( mp_add_d(&s, (mp_digit)addend, &s) );
  144.     } else {
  145. CHECK_MPI_OK( mp_init(&tmp) );
  146. CHECK_MPI_OK( mp_set_ulong(&tmp, addend) );
  147. CHECK_MPI_OK( mp_add(&s, &tmp, &s) );
  148.     }
  149.     CHECK_MPI_OK( mp_div_2d(&s, (mp_digit)g, NULL, &sum) );/*sum = s mod 2**g */
  150.     MPINT_TO_SECITEM(&sum, &str, NULL);
  151.     rv = SHA1_HashBuf(shaOutBuf, str.data, str.len); /* SHA1 hash result */
  152. cleanup:
  153.     mp_clear(&s);
  154.     mp_clear(&sum);
  155.     mp_clear(&modulus);
  156.     mp_clear(&tmp);
  157.     if (str.data)
  158. SECITEM_ZfreeItem(&str, PR_FALSE);
  159.     if (err) {
  160. MP_TO_SEC_ERROR(err);
  161. return SECFailure;
  162.     }
  163.     return rv;
  164. }
  166. /*
  167. **  Perform steps 2 and 3 of FIPS 186, appendix 2.2.
  168. **  Generate Q from seed.
  169. */
  170. static SECStatus
  171. makeQfromSeed(
  172.       unsigned int  g,          /* input.  Length of seed in bits. */
  173. const SECItem   *   seed,       /* input.  */
  174.       mp_int    *   Q)          /* output. */
  175. {
  176.     unsigned char sha1[SHA1_LENGTH];
  177.     unsigned char sha2[SHA1_LENGTH];
  178.     unsigned char U[SHA1_LENGTH];
  179.     SECStatus rv  = SECSuccess;
  180.     mp_err    err = MP_OKAY;
  181.     int i;
  182.     /* ******************************************************************
  183.     ** Step 2.
  184.     ** "Compute U = SHA[SEED] XOR SHA[(SEED+1) mod 2**g]."
  185.     **/
  186.     CHECK_SEC_OK( SHA1_HashBuf(sha1, seed->data, seed->len) );
  187.     CHECK_SEC_OK( addToSeedThenSHA(seed, 1, g, sha2) );
  188.     for (i=0; i<SHA1_LENGTH; ++i) 
  189. U[i] = sha1[i] ^ sha2[i];
  190.     /* ******************************************************************
  191.     ** Step 3.
  192.     ** "Form Q from U by setting the most signficant bit (the 2**159 bit)
  193.     **  and the least signficant bit to 1.  In terms of boolean operations,
  194.     **  Q = U OR 2**159 OR 1.  Note that 2**159 < Q < 2**160."
  195.     */
  196.     U[0]             |= 0x80;  /* U is MSB first */
  197.     U[SHA1_LENGTH-1] |= 0x01;
  198.     err = mp_read_unsigned_octets(Q, U, SHA1_LENGTH);
  199. cleanup:
  200.      memset(U, 0, SHA1_LENGTH);
  201.      memset(sha1, 0, SHA1_LENGTH);
  202.      memset(sha2, 0, SHA1_LENGTH);
  203.      if (err) {
  204. MP_TO_SEC_ERROR(err);
  205. return SECFailure;
  206.      }
  207.      return rv;
  208. }
  210. /*  Perform steps 7, 8 and 9 of FIPS 186, appendix 2.2.
  211. **  Generate P from Q, seed, L, and offset.
  212. */
  213. static SECStatus
  214. makePfromQandSeed(
  215.       unsigned int  L,          /* Length of P in bits.  Per FIPS 186. */
  216.       unsigned int  offset,     /* Per FIPS 186, appendix 2.2. */
  217.       unsigned int  g,          /* input.  Length of seed in bits. */
  218. const SECItem   *   seed,       /* input.  */
  219. const mp_int    *   Q,          /* input.  */
  220.       mp_int    *   P)          /* output. */
  221. {
  222.     unsigned int  k;            /* Per FIPS 186, appendix 2.2. */
  223.     unsigned int  n;            /* Per FIPS 186, appendix 2.2. */
  224.     mp_digit      b;            /* Per FIPS 186, appendix 2.2. */
  225.     unsigned char V_k[SHA1_LENGTH];
  226.     mp_int        W, X, c, twoQ, V_n, tmp;
  227.     mp_err    err = MP_OKAY;
  228.     SECStatus rv  = SECSuccess;
  229.     /* Initialize bignums */
  230.     MP_DIGITS(&W)     = 0;
  231.     MP_DIGITS(&X)     = 0;
  232.     MP_DIGITS(&c)     = 0;
  233.     MP_DIGITS(&twoQ)  = 0;
  234.     MP_DIGITS(&V_n)   = 0;
  235.     MP_DIGITS(&tmp)   = 0;
  236.     CHECK_MPI_OK( mp_init(&W)    );
  237.     CHECK_MPI_OK( mp_init(&X)    );
  238.     CHECK_MPI_OK( mp_init(&c)    );
  239.     CHECK_MPI_OK( mp_init(&twoQ) );
  240.     CHECK_MPI_OK( mp_init(&tmp)  );
  241.     CHECK_MPI_OK( mp_init(&V_n)  );
  242.     /* L - 1 = n*160 + b */
  243.     n = (L - 1) / BITS_IN_Q;
  244.     b = (L - 1) % BITS_IN_Q;
  245.     /* ******************************************************************
  246.     ** Step 7.
  247.     **  "for k = 0 ... n let
  248.     **           V_k = SHA[(SEED + offset + k) mod 2**g]."
  249.     **
  250.     ** Step 8.
  251.     **  "Let W be the integer 
  252.     **    W = V_0 + (V_1 * 2**160) + ... + (V_n-1 * 2**((n-1)*160)) 
  253.     **         + ((V_n mod 2**b) * 2**(n*160))
  254.     */
  255.     for (k=0; k<n; ++k) { /* Do the first n terms of V_k */
  256. /* Do step 7 for iteration k.
  257. ** V_k = SHA[(seed + offset + k) mod 2**g]
  258. */
  259. CHECK_SEC_OK( addToSeedThenSHA(seed, offset + k, g, V_k) );
  260. /* Do step 8 for iteration k.
  261. ** W += V_k * 2**(k*160)
  262. */
  263. OCTETS_TO_MPINT(V_k, &tmp, SHA1_LENGTH);      /* get bignum V_k     */
  264. CHECK_MPI_OK( mpl_lsh(&tmp, &tmp, k*160) );   /* tmp = V_k << k*160 */
  265. CHECK_MPI_OK( mp_add(&W, &tmp, &W) );         /* W += tmp           */
  266.     }
  267.     /* Step 8, continued.
  268.     **   [W += ((V_n mod 2**b) * 2**(n*160))] 
  269.     */
  270.     CHECK_SEC_OK( addToSeedThenSHA(seed, offset + n, g, V_k) );
  271.     OCTETS_TO_MPINT(V_k, &V_n, SHA1_LENGTH);          /* get bignum V_n     */
  272.     CHECK_MPI_OK( mp_div_2d(&V_n, b, NULL, &tmp) );   /* tmp = V_n mod 2**b */
  273.     CHECK_MPI_OK( mpl_lsh(&tmp, &tmp, n*160) );       /* tmp = tmp << n*160 */
  274.     CHECK_MPI_OK( mp_add(&W, &tmp, &W) );             /* W += tmp           */
  275.     /* Step 8, continued.
  276.     ** "and let X = W + 2**(L-1).
  277.     **  Note that 0 <= W < 2**(L-1) and hence 2**(L-1) <= X < 2**L."
  278.     */
  279.     CHECK_MPI_OK( mpl_set_bit(&X, (mp_size)(L-1), 1) );    /* X = 2**(L-1) */
  280.     CHECK_MPI_OK( mp_add(&X, &W, &X) );                    /* X += W       */
  281.     /*************************************************************
  282.     ** Step 9.
  283.     ** "Let c = X mod 2q  and set p = X - (c - 1).
  284.     **  Note that p is congruent to 1 mod 2q."
  285.     */
  286.     CHECK_MPI_OK( mp_mul_2(Q, &twoQ) );                    /* 2q           */
  287.     CHECK_MPI_OK( mp_mod(&X, &twoQ, &c) );                 /* c = X mod 2q */
  288.     CHECK_MPI_OK( mp_sub_d(&c, 1, &c) );                   /* c -= 1       */
  289.     CHECK_MPI_OK( mp_sub(&X, &c, P) );                     /* P = X - c    */
  290. cleanup:
  291.     mp_clear(&W);
  292.     mp_clear(&X);
  293.     mp_clear(&c);
  294.     mp_clear(&twoQ);
  295.     mp_clear(&V_n);
  296.     mp_clear(&tmp);
  297.     if (err) {
  298. MP_TO_SEC_ERROR(err);
  299. return SECFailure;
  300.     }
  301.     return rv;
  302. }
  304. /*
  305. ** Generate G from h, P, and Q.
  306. */
  307. static SECStatus
  308. makeGfromH(const mp_int *P,     /* input.  */
  309.            const mp_int *Q,     /* input.  */
  310.                  mp_int *H,     /* input and output. */
  311.                  mp_int *G,     /* output. */
  312.                  PRBool *passed)
  313. {
  314.     mp_int exp, pm1;
  315.     mp_err err = MP_OKAY;
  316.     SECStatus rv = SECSuccess;
  317.     *passed = PR_FALSE;
  318.     MP_DIGITS(&exp) = 0;
  319.     MP_DIGITS(&pm1) = 0;
  320.     CHECK_MPI_OK( mp_init(&exp) );
  321.     CHECK_MPI_OK( mp_init(&pm1) );
  322.     CHECK_MPI_OK( mp_sub_d(P, 1, &pm1) );        /* P - 1            */
  323.     if ( mp_cmp(H, &pm1) > 0)                   /* H = H mod (P-1)  */
  324. CHECK_MPI_OK( mp_sub(H, &pm1, H) );
  325.     /* Let b = 2**n (smallest power of 2 greater than P).
  326.     ** Since P-1 >= b/2, and H < b, quotient(H/(P-1)) = 0 or 1
  327.     ** so the above operation safely computes H mod (P-1)
  328.     */
  329.     /* Check for H = to 0 or 1.  Regen H if so.  (Regen means return error). */
  330.     if (mp_cmp_d(H, 1) <= 0) {
  331. rv = SECFailure;
  332. goto cleanup;
  333.     }
  334.     /* Compute G, according to the equation  G = (H ** ((P-1)/Q)) mod P */
  335.     CHECK_MPI_OK( mp_div(&pm1, Q, &exp, NULL) );  /* exp = (P-1)/Q      */
  336.     CHECK_MPI_OK( mp_exptmod(H, &exp, P, G) );    /* G = H ** exp mod P */
  337.     /* Check for G == 0 or G == 1, return error if so. */
  338.     if (mp_cmp_d(G, 1) <= 0) {
  339. rv = SECFailure;
  340. goto cleanup;
  341.     }
  342.     *passed = PR_TRUE;
  343. cleanup:
  344.     mp_clear(&exp);
  345.     mp_clear(&pm1);
  346.     if (err) {
  347. MP_TO_SEC_ERROR(err);
  348. rv = SECFailure;
  349.     }
  350.     return rv;
  351. }
  353. SECStatus
  354. PQG_ParamGen(unsigned int j, PQGParams **pParams, PQGVerify **pVfy)
  355. {
  356.     unsigned int L;            /* Length of P in bits.  Per FIPS 186. */
  357.     unsigned int seedBytes;
  359.     if (j > 8 || !pParams || !pVfy) {
  360. PORT_SetError(SEC_ERROR_INVALID_ARGS);
  361.         return SECFailure;
  362.     }
  363.     L = 512 + (j * 64);         /* bits in P */
  364.     seedBytes = L/8;
  365.     return PQG_ParamGenSeedLen(j, seedBytes, pParams, pVfy);
  366. }
  368. /* This code uses labels and gotos, so that it can follow the numbered
  369. ** steps in the algorithms from FIPS 186 appendix 2.2 very closely,
  370. ** and so that the correctness of this code can be easily verified.
  371. ** So, please forgive the ugly c code.
  372. **/
  373. SECStatus
  374. PQG_ParamGenSeedLen(unsigned int j, unsigned int seedBytes,
  375.                     PQGParams **pParams, PQGVerify **pVfy)
  376. {
  377.     unsigned int  L;        /* Length of P in bits.  Per FIPS 186. */
  378.     unsigned int  n;        /* Per FIPS 186, appendix 2.2. */
  379.     unsigned int  b;        /* Per FIPS 186, appendix 2.2. */
  380.     unsigned int  g;        /* Per FIPS 186, appendix 2.2. */
  381.     unsigned int  counter;  /* Per FIPS 186, appendix 2.2. */
  382.     unsigned int  offset;   /* Per FIPS 186, appendix 2.2. */
  383.     SECItem      *seed;     /* Per FIPS 186, appendix 2.2. */
  384.     PRArenaPool  *arena  = NULL;
  385.     PQGParams    *params = NULL;
  386.     PQGVerify    *verify = NULL;
  387.     PRBool passed;
  388.     SECItem hit = { 0, 0, 0 };
  389.     mp_int P, Q, G, H, l;
  390.     mp_err    err = MP_OKAY;
  391.     SECStatus rv  = SECFailure;
  392.     int iterations = 0;
  393.     if (j > 8 || !pParams || !pVfy) {
  394. PORT_SetError(SEC_ERROR_INVALID_ARGS);
  395. return SECFailure;
  396.     }
  397.     /* Initialize an arena for the params. */
  398.     arena = PORT_NewArena(NSS_FREEBL_DEFAULT_CHUNKSIZE);
  399.     if (!arena) {
  400. PORT_SetError(SEC_ERROR_NO_MEMORY);
  401. return SECFailure;
  402.     }
  403.     params = (PQGParams *)PORT_ArenaZAlloc(arena, sizeof(PQGParams));
  404.     if (!params) {
  405. PORT_SetError(SEC_ERROR_NO_MEMORY);
  406. PORT_FreeArena(arena, PR_TRUE);
  407. return SECFailure;
  408.     }
  409.     params->arena = arena;
  410.     /* Initialize an arena for the verify. */
  411.     arena = PORT_NewArena(NSS_FREEBL_DEFAULT_CHUNKSIZE);
  412.     if (!arena) {
  413. PORT_SetError(SEC_ERROR_NO_MEMORY);
  414. return SECFailure;
  415.     }
  416.     verify = (PQGVerify *)PORT_ArenaZAlloc(arena, sizeof(PQGVerify));
  417.     if (!verify) {
  418. PORT_SetError(SEC_ERROR_NO_MEMORY);
  419. PORT_FreeArena(arena, PR_TRUE);
  420. PORT_FreeArena(params->arena, PR_TRUE);
  421. return SECFailure;
  422.     }
  423.     verify->arena = arena;
  424.     seed = &verify->seed;
  425.     arena = NULL;
  426.     /* Initialize bignums */
  427.     MP_DIGITS(&P) = 0;
  428.     MP_DIGITS(&Q) = 0;
  429.     MP_DIGITS(&G) = 0;
  430.     MP_DIGITS(&H) = 0;
  431.     MP_DIGITS(&l) = 0;
  432.     CHECK_MPI_OK( mp_init(&P) );
  433.     CHECK_MPI_OK( mp_init(&Q) );
  434.     CHECK_MPI_OK( mp_init(&G) );
  435.     CHECK_MPI_OK( mp_init(&H) );
  436.     CHECK_MPI_OK( mp_init(&l) );
  437.     /* Compute lengths. */
  438.     L = 512 + (j * 64);               /* bits in P */
  439.     n = (L - 1) / BITS_IN_Q;          /* BITS_IN_Q is 160 */  
  440.     b = (L - 1) % BITS_IN_Q;
  441.     g = seedBytes * BITS_PER_BYTE;    /* bits in seed, NOT G of PQG. */
  442. step_1:
  443.     /* ******************************************************************
  444.     ** Step 1.
  445.     ** "Choose an abitrary sequence of at least 160 bits and call it SEED.
  446.     **  Let g be the length of SEED in bits."
  447.     */
  448.     if (++iterations > MAX_ITERATIONS) {        /* give up after a while */
  449.         PORT_SetError(SEC_ERROR_NEED_RANDOM);
  450.         goto cleanup;
  451.     }
  452.     seed->len = seedBytes;
  453.     CHECK_SEC_OK( getPQseed(seed) );
  454.     /* ******************************************************************
  455.     ** Step 2.
  456.     ** "Compute U = SHA[SEED] XOR SHA[(SEED+1) mod 2**g]."
  457.     **
  458.     ** Step 3.
  459.     ** "Form Q from U by setting the most signficant bit (the 2**159 bit) 
  460.     **  and the least signficant bit to 1.  In terms of boolean operations,
  461.     **  Q = U OR 2**159 OR 1.  Note that 2**159 < Q < 2**160."
  462.     */
  463.     CHECK_SEC_OK( makeQfromSeed(g, seed, &Q) );
  464.     /* ******************************************************************
  465.     ** Step 4.
  466.     ** "Use a robust primality testing algorithm to test whether q is prime."
  467.     **
  468.     ** Appendix 2.1 states that a Rabin test with at least 50 iterations
  469.     ** "will give an acceptable probability of error."
  470.     */
  471.     /*CHECK_SEC_OK( prm_RabinTest(&Q, &passed) );*/
  472.     err = mpp_pprime(&Q, 40);
  473.     passed = (err == MP_YES) ? SECSuccess : SECFailure;
  474.     /* ******************************************************************
  475.     ** Step 5. "If q is not prime, goto step 1."
  476.     */
  477.     if (passed != SECSuccess)
  478.         goto step_1;
  479.     /* ******************************************************************
  480.     ** Step 6. "Let counter = 0 and offset = 2."
  481.     */
  482.     counter = 0;
  483.     offset  = 2;
  484. step_7:
  485.     /* ******************************************************************
  486.     ** Step 7.
  487.     ** "for k = 0 ... n let
  488.     **          V_k = SHA[(SEED + offset + k) mod 2**g]."
  489.     **
  490.     ** Step 8.
  491.     ** "Let W be the sum of  (V_k * 2**(k*160)) for k = 0 ... n
  492.     **  and let X = W + 2**(L-1).
  493.     **  Note that 0 <= W < 2**(L-1) and hence 2**(L-1) <= X < 2**L."
  494.     **
  495.     ** Step 9.
  496.     ** "Let c = X mod 2q  and set p = X - (c - 1).
  497.     **  Note that p is congruent to 1 mod 2q."
  498.     */
  499.     CHECK_SEC_OK( makePfromQandSeed(L, offset, g, seed, &Q, &P) );
  500.     /*************************************************************
  501.     ** Step 10.
  502.     ** "if p < 2**(L-1), then goto step 13."
  503.     */
  504.     CHECK_MPI_OK( mpl_set_bit(&l, (mp_size)(L-1), 1) ); /* l = 2**(L-1) */
  505.     if (mp_cmp(&P, &l) < 0)
  506.         goto step_13;
  507.     /************************************************************
  508.     ** Step 11.
  509.     ** "Perform a robust primality test on p."
  510.     */
  511.     /*CHECK_SEC_OK( prm_RabinTest(&P, &passed) );*/
  512.     err = mpp_pprime(&P, 40);
  513.     passed = (err == MP_YES) ? SECSuccess : SECFailure;
  514.     /* ******************************************************************
  515.     ** Step 12. "If p passes the test performed in step 11, go to step 15."
  516.     */
  517.     if (passed == SECSuccess)
  518.         goto step_15;
  519. step_13:
  520.     /* ******************************************************************
  521.     ** Step 13.  "Let counter = counter + 1 and offset = offset + n + 1."
  522.     */
  523.     counter++;
  524.     offset += n + 1;
  525.     /* ******************************************************************
  526.     ** Step 14.  "If counter >= 4096 goto step 1, otherwise go to step 7."
  527.     */
  528.     if (counter >= 4096)
  529.         goto step_1;
  530.     goto step_7;
  531. step_15:
  532.     /* ******************************************************************
  533.     ** Step 15.  
  534.     ** "Save the value of SEED and the value of counter for use
  535.     **  in certifying the proper generation of p and q."
  536.     */
  537.     /* Generate h. */
  538.     SECITEM_AllocItem(NULL, &hit, seedBytes); /* h is no longer than p */
  539.     if (!hit.data) goto cleanup;
  540.     do {
  541. /* loop generate h until 1<h<p-1 and (h**[(p-1)/q])mod p > 1 */
  542. CHECK_SEC_OK( generate_h_candidate(&hit, &H) );
  543.         CHECK_SEC_OK( makeGfromH(&P, &Q, &H, &G, &passed) );
  544.     } while (passed != PR_TRUE);
  545.     /* All generation is done.  Now, save the PQG params.  */
  546.     MPINT_TO_SECITEM(&P, &params->prime,    params->arena);
  547.     MPINT_TO_SECITEM(&Q, &params->subPrime, params->arena);
  548.     MPINT_TO_SECITEM(&G, &params->base,     params->arena);
  549.     MPINT_TO_SECITEM(&H, &verify->h,        verify->arena);
  550.     verify->counter = counter;
  551.     *pParams = params;
  552.     *pVfy = verify;
  553. cleanup:
  554.     mp_clear(&P);
  555.     mp_clear(&Q);
  556.     mp_clear(&G);
  557.     mp_clear(&H);
  558.     mp_clear(&l);
  559.     if (err) {
  560. MP_TO_SEC_ERROR(err);
  561. rv = SECFailure;
  562.     }
  563.     if (rv) {
  564. PORT_FreeArena(params->arena, PR_TRUE);
  565. PORT_FreeArena(verify->arena, PR_TRUE);
  566.     }
  567.     return rv;
  568. }
  570. SECStatus   
  571. PQG_VerifyParams(const PQGParams *params, 
  572.                  const PQGVerify *vfy, SECStatus *result)
  573. {
  574.     SECStatus rv = SECSuccess;
  575.     int passed;
  576.     unsigned int g, n, L, offset;
  577.     mp_int P, Q, G, P_, Q_, G_, r, h;
  578.     mp_err err = MP_OKAY;
  579.     int j;
  580. #define CHECKPARAM(cond)      
  581.     if (!(cond)) {            
  582. *result = SECFailure; 
  583. goto cleanup;         
  584.     }
  585.     if (!params || !vfy || !result) {
  586. PORT_SetError(SEC_ERROR_INVALID_ARGS);
  587. return SECFailure;
  588.     }
  589.     MP_DIGITS(&P) = 0;
  590.     MP_DIGITS(&Q) = 0;
  591.     MP_DIGITS(&G) = 0;
  592.     MP_DIGITS(&P_) = 0;
  593.     MP_DIGITS(&Q_) = 0;
  594.     MP_DIGITS(&G_) = 0;
  595.     MP_DIGITS(&r) = 0;
  596.     MP_DIGITS(&h) = 0;
  597.     CHECK_MPI_OK( mp_init(&P) );
  598.     CHECK_MPI_OK( mp_init(&Q) );
  599.     CHECK_MPI_OK( mp_init(&G) );
  600.     CHECK_MPI_OK( mp_init(&P_) );
  601.     CHECK_MPI_OK( mp_init(&Q_) );
  602.     CHECK_MPI_OK( mp_init(&G_) );
  603.     CHECK_MPI_OK( mp_init(&r) );
  604.     CHECK_MPI_OK( mp_init(&h) );
  605.     *result = SECSuccess;
  606.     SECITEM_TO_MPINT(params->prime,    &P);
  607.     SECITEM_TO_MPINT(params->subPrime, &Q);
  608.     SECITEM_TO_MPINT(params->base,     &G);
  609.     /* 1.  Q is 160 bits long. */
  610.     CHECKPARAM( mpl_significant_bits(&Q) == 160 );
  611.     /* 2.  P is one of the 9 valid lengths. */
  612.     L = mpl_significant_bits(&P);
  613.     j = PQG_PBITS_TO_INDEX(L);
  614.     CHECKPARAM( j >= 0 && j <= 8 );
  615.     /* 3.  G < P */
  616.     CHECKPARAM( mp_cmp(&G, &P) < 0 );
  617.     /* 4.  P % Q == 1 */
  618.     CHECK_MPI_OK( mp_mod(&P, &Q, &r) );
  619.     CHECKPARAM( mp_cmp_d(&r, 1) == 0 );
  620.     /* 5.  Q is prime */
  621.     CHECKPARAM( mpp_pprime(&Q, NUMITER) == MP_YES );
  622.     /* 6.  P is prime */
  623.     CHECKPARAM( mpp_pprime(&P, NUMITER) == MP_YES );
  624.     /* Steps 7-12 are done only if the optional PQGVerify is supplied. */
  625.     if (!vfy) goto cleanup;
  626.     /* 7.  counter < 4096 */
  627.     CHECKPARAM( vfy->counter < 4096 );
  628.     /* 8.  g >= 160 and g < 2048   (g is length of seed in bits) */
  629.     g = vfy->seed.len * 8;
  630.     CHECKPARAM( g >= 160 && g < 2048 );
  631.     /* 9.  Q generated from SEED matches Q in PQGParams. */
  632.     CHECK_SEC_OK( makeQfromSeed(g, &vfy->seed, &Q_) );
  633.     CHECKPARAM( mp_cmp(&Q, &Q_) == 0 );
  634.     /* 10. P generated from (L, counter, g, SEED, Q) matches P in PQGParams. */
  635.     n = (L - 1) / BITS_IN_Q;
  636.     offset = vfy->counter * (n + 1) + 2;
  637.     CHECK_SEC_OK( makePfromQandSeed(L, offset, g, &vfy->seed, &Q, &P_) );
  638.     CHECKPARAM( mp_cmp(&P, &P_) == 0 );
  639.     /* Next two are optional: if h == 0 ignore */
  640.     if (vfy->h.len == 0) goto cleanup;
  641.     /* 11. 1 < h < P-1 */
  642.     SECITEM_TO_MPINT(vfy->h, &h);
  643.     CHECK_MPI_OK( mpl_set_bit(&P, 0, 0) ); /* P is prime, p-1 == zero 1st bit */
  644.     CHECKPARAM( mp_cmp_d(&h, 1) > 0 && mp_cmp(&h, &P) );
  645.     CHECK_MPI_OK( mpl_set_bit(&P, 0, 1) ); /* set it back */
  646.     /* 12. G generated from h matches G in PQGParams. */
  647.     CHECK_SEC_OK( makeGfromH(&P, &Q, &h, &G_, &passed) );
  648.     CHECKPARAM( passed && mp_cmp(&G, &G_) == 0 );
  649. cleanup:
  650.     mp_clear(&P);
  651.     mp_clear(&Q);
  652.     mp_clear(&G);
  653.     mp_clear(&P_);
  654.     mp_clear(&Q_);
  655.     mp_clear(&G_);
  656.     mp_clear(&r);
  657.     mp_clear(&h);
  658.     if (err) {
  659. MP_TO_SEC_ERROR(err);
  660. rv = SECFailure;
  661.     }
  662.     return rv;
  663. }