Bug 475578 - Implement Extended DSA as defined in FIPS 186-3 (DSS)
authorrrelyea%redhat.com
Tue, 12 Jun 2012 16:39:03 +0000
changeset 10368 8011ef5d178f39acfb83e2522cb320f53aacd033
parent 10367 e83eeff08cada278fe62987ba6df524438d46f41
child 10369 0d345e41c91a80b43597faadd0bc2e60da93a346
push idunknown
push userunknown
push dateunknown
bugs475578
Bug 475578 - Implement Extended DSA as defined in FIPS 186-3 (DSS) r wtc Patches 1 and 4 in the original bug (lib/softoken lib/freebl, and lib/ssl)
security/nss/lib/freebl/blapi.h
security/nss/lib/freebl/blapit.h
security/nss/lib/freebl/dsa.c
security/nss/lib/freebl/ldvector.c
security/nss/lib/freebl/loader.c
security/nss/lib/freebl/loader.h
security/nss/lib/freebl/pqg.c
security/nss/lib/freebl/pqg.h
security/nss/lib/freebl/rawhash.c
security/nss/lib/freebl/shvfy.c
security/nss/lib/softoken/pkcs11.c
security/nss/lib/softoken/pkcs11c.c
security/nss/lib/ssl/ssl3con.c
--- a/security/nss/lib/freebl/blapi.h
+++ b/security/nss/lib/freebl/blapi.h
@@ -1227,59 +1227,78 @@ PRNGTEST_Generate(PRUint8 *bytes, unsign
 		  const PRUint8 *additional, unsigned int additional_len);
 
 extern SECStatus
 PRNGTEST_Uninstantiate(void);
 
 /* Generate PQGParams and PQGVerify structs.
  * Length of seed and length of h both equal length of P. 
  * All lengths are specified by "j", according to the table above.
+ *
+ * The verify parameters will conform to FIPS186-1.
  */
 extern SECStatus
 PQG_ParamGen(unsigned int j, 	   /* input : determines length of P. */
              PQGParams **pParams,  /* output: P Q and G returned here */
 	     PQGVerify **pVfy);    /* output: counter and seed. */
 
 /* Generate PQGParams and PQGVerify structs.
  * Length of P specified by j.  Length of h will match length of P.
  * Length of SEED in bytes specified in seedBytes.
  * seedBbytes must be in the range [20..255] or an error will result.
+ *
+ * The verify parameters will conform to FIPS186-1.
  */
 extern SECStatus
 PQG_ParamGenSeedLen(
              unsigned int j, 	     /* input : determines length of P. */
 	     unsigned int seedBytes, /* input : length of seed in bytes.*/
              PQGParams **pParams,    /* output: P Q and G returned here */
 	     PQGVerify **pVfy);      /* output: counter and seed. */
 
+/* Generate PQGParams and PQGVerify structs.
+ * Length of P specified by L in bits.  
+ * Length of Q specified by N in bits.  
+ * Length of SEED in bytes specified in seedBytes.
+ * seedBbytes must be in the range [N..L*2] or an error will result.
+ *
+ * Not that J uses the above table, L is the length exact. L and N must
+ * match the table below or an error will result:
+ *
+ *  L            N
+ * 1024         160
+ * 2048         224
+ * 2048         256
+ * 3072         256
+ *
+ * The verify parameters will conform to FIPS186-3 using the smallest 
+ * permissible hash for the key strength.
+ */
+extern SECStatus
+PQG_ParamGenV2(
+             unsigned int L, 	     /* input : determines length of P. */
+             unsigned int N, 	     /* input : determines length of Q. */
+	     unsigned int seedBytes, /* input : length of seed in bytes.*/
+             PQGParams **pParams,    /* output: P Q and G returned here */
+	     PQGVerify **pVfy);      /* output: counter and seed. */
+
 
 /*  Test PQGParams for validity as DSS PQG values.
  *  If vfy is non-NULL, test PQGParams to make sure they were generated
  *       using the specified seed, counter, and h values.
  *
  *  Return value indicates whether Verification operation ran successfully
  *  to completion, but does not indicate if PQGParams are valid or not.
  *  If return value is SECSuccess, then *pResult has these meanings:
  *       SECSuccess: PQGParams are valid.
  *       SECFailure: PQGParams are invalid.
  *
- * Verify the following 12 facts about PQG counter SEED g and h
- * 1.  Q is 160 bits long.
- * 2.  P is one of the 9 valid lengths.
- * 3.  G < P
- * 4.  P % Q == 1
- * 5.  Q is prime
- * 6.  P is prime
- * Steps 7-12 are done only if the optional PQGVerify is supplied.
- * 7.  counter < 4096
- * 8.  g >= 160 and g < 2048   (g is length of seed in bits)
- * 9.  Q generated from SEED matches Q in PQGParams.
- * 10. P generated from (L, counter, g, SEED, Q) matches P in PQGParams.
- * 11. 1 < h < P-1
- * 12. G generated from h matches G in PQGParams.
+ * Verify the PQG againts the counter, SEED and h.
+ * These tests are specified in FIPS 186-3 Appendix A.1.1.1, A.1.1.3, and A.2.2
+ * PQG_VerifyParams will automatically choose the appropriate test.
  */
 
 extern SECStatus   PQG_VerifyParams(const PQGParams *params, 
                                     const PQGVerify *vfy, SECStatus *result);
 
 extern void PQG_DestroyParams(PQGParams *params);
 
 extern void PQG_DestroyVerify(PQGVerify *vfy);
--- a/security/nss/lib/freebl/blapit.h
+++ b/security/nss/lib/freebl/blapit.h
@@ -38,18 +38,42 @@
 /* Camellia operation modes */
 #define NSS_CAMELLIA                 0
 #define NSS_CAMELLIA_CBC             1
 
 /* SEED operation modes */
 #define NSS_SEED		0
 #define NSS_SEED_CBC		1
 
-#define DSA_SIGNATURE_LEN 	40	/* Bytes */
-#define DSA_SUBPRIME_LEN	20	/* Bytes */
+#define DSA1_SUBPRIME_LEN	20			/* Bytes */
+#define DSA1_SIGNATURE_LEN 	(DSA1_SUBPRIME_LEN*2)	/* Bytes */
+#define DSA_MAX_SUBPRIME_LEN	32			/* Bytes */
+#define DSA_MAX_SIGNATURE_LEN 	(DSA_MAX_SUBPRIME_LEN*2)/* Bytes */
+
+/*
+ * Mark the old defines as deprecated. This will warn code that expected
+ * DSA1 only that they need to change if the are to support DSA2.
+ */
+#if defined(__GNUC__) && (__GNUC__ > 3)
+/* make GCC warn when we use these #defines */
+typedef int __BLAPI_DEPRECATED __attribute__((deprecated));
+#define DSA_SUBPRIME_LEN ((__BLAPI_DEPRECATED)DSA1_SUBPRIME_LEN)
+#define DSA_SIGNATURE_LEN ((__BLAPI_DEPRECATED)DSA1_SIGNATURE_LEN)
+#define DSA_Q_BITS ((__BLAPI_DEPRECATED)(DSA1_SUBPRIME_LEN*8))
+#else
+#ifdef _WIN32
+/* This magic gets the windows compiler to give us a deprecation
+ * warning */
+#pragma deprecated(DSA_SUBPRIME_LEN, DSA_SIGNATURE_LEN, DSA_QBITS)
+#endif
+#define DSA_SUBPRIME_LEN  DSA1_SUBPRIME_LEN
+#define DSA_SIGNATURE_LEN DSA1_SIGNATURE_LEN
+#define DSA_Q_BITS 	  (DSA1_SUBPRIME_LEN*8)
+#endif
+
 
 /* XXX We shouldn't have to hard code this limit. For
  * now, this is the quickest way to support ECDSA signature
  * processing (ECDSA signature lengths depend on curve
  * size). This limit is sufficient for curves upto
  * 576 bits.
  */
 #define MAX_ECKEY_LEN 	        72	/* Bytes */
@@ -106,17 +130,17 @@
  */
 #define RSA_MIN_MODULUS_BITS   128
 #define RSA_MAX_MODULUS_BITS  8192
 #define RSA_MAX_EXPONENT_BITS   64
 #define DH_MIN_P_BITS	       128
 #define DH_MAX_P_BITS         3072
 
 /*
- * The FIPS 186 algorithm for generating primes P and Q allows only 9
+ * The FIPS 186-1 algorithm for generating primes P and Q allows only 9
  * distinct values for the length of P, and only one value for the
  * length of Q.
  * The algorithm uses a variable j to indicate which of the 9 lengths
  * of P is to be used.
  * The following table relates j to the lengths of P and Q in bits.
  *
  *	j	bits in P	bits in Q
  *	_	_________	_________
@@ -125,22 +149,41 @@
  *	2	 640		160
  *	3	 704		160
  *	4	 768		160
  *	5	 832		160
  *	6	 896		160
  *	7	 960		160
  *	8	1024		160
  *
- * The FIPS-186 compliant PQG generator takes j as an input parameter.
+ * The FIPS-186-1 compliant PQG generator takes j as an input parameter.
+ *
+ * FIPS 186-3 algorithm specifies 4 distinct P and Q sizes:
+ *
+ *     bits in P       bits in Q
+ *     _________       _________
+ *      1024           160
+ *      2048           224
+ *      2048           256
+ *      3072           256
+ *
+ * The FIPS-186-3 complaiant PQG generator (PQG V2) takes arbitrary p and q
+ * lengths as input and returns an error if they aren't in this list.
  */
 
-#define DSA_Q_BITS       160
-#define DSA_MAX_P_BITS	1024
+#define DSA1_Q_BITS      160
+#define DSA_MAX_P_BITS	3072
 #define DSA_MIN_P_BITS	 512
+#define DSA_MAX_Q_BITS   256
+#define DSA_MIN_Q_BITS   160
+
+#if DSA_MAX_Q_BITS != DSA_MAX_SUBPRIME_LEN*8
+#error "Inconsistent declaration of DSA SUBPRIME/Q parameters in blapit.h"
+#endif
+
 
 /*
  * function takes desired number of bits in P,
  * returns index (0..8) or -1 if number of bits is invalid.
  */
 #define PQG_PBITS_TO_INDEX(bits) \
     (((bits) < 512 || (bits) > 1024 || (bits) % 64) ? \
     -1 : (int)((bits)-512)/64)
--- a/security/nss/lib/freebl/dsa.c
+++ b/security/nss/lib/freebl/dsa.c
@@ -15,16 +15,17 @@
 #include "prtypes.h"
 #include "prinit.h"
 #include "blapi.h"
 #include "nssilock.h"
 #include "secitem.h"
 #include "blapi.h"
 #include "mpi.h"
 #include "secmpi.h"
+#include "pqg.h"
 
  /* XXX to be replaced by define in blapit.h */
 #define NSS_FREEBL_DSA_DEFAULT_CHUNKSIZE 2048
 
 /*
  * FIPS 186-2 requires result from random output to be reduced mod q when 
  * generating random numbers for DSA. 
  *
@@ -74,17 +75,17 @@ cleanup:
 /*
  * FIPS 186-2 requires result from random output to be reduced mod q when 
  * generating random numbers for DSA. 
  */
 SECStatus
 FIPS186Change_ReduceModQForDSA(const unsigned char *w,
                                const unsigned char *q,
                                unsigned char *xj) {
-    return fips186Change_ReduceModQForDSA(w, q, DSA_SUBPRIME_LEN, xj);
+    return fips186Change_ReduceModQForDSA(w, q, DSA1_SUBPRIME_LEN, xj);
 }
 
 /*
  * The core of Algorithm 1 of FIPS 186-2 Change Notice 1.
  *
  * We no longer support FIPS 186-2 RNG. This function was exported
  * for power-up self tests and FIPS tests. Keep this stub, which fails,
  * to prevent crashes, but also to signal to test code that FIPS 186-2
@@ -122,17 +123,17 @@ dsa_GenerateGlobalRandomBytes(const SECI
     unsigned int qLen = qItem->len;
 
     if (*q == 0) {
         ++q;
         --qLen;
     }
     if (maxDestLen < qLen) {
         /* This condition can occur when DSA_SignDigest is passed a group
-           with a subprime that is larger than DSA_SUBPRIME_LEN. */
+           with a subprime that is larger than DSA_MAX_SUBPRIME_LEN. */
         PORT_SetError(SEC_ERROR_INVALID_ARGS);
         return SECFailure;
     }
     w.data = NULL; /* otherwise SECITEM_AllocItem asserts */
     if (!SECITEM_AllocItem(NULL, &w, 2*qLen)) {
         return SECFailure;
     }
     *destLen = qLen;
@@ -274,63 +275,89 @@ loser:	if (arena != NULL) {
 **	Uses a random seed.
 */
 SECStatus 
 DSA_NewKey(const PQGParams *params, DSAPrivateKey **privKey)
 {
     SECItem seed;
     SECStatus rv;
 
+    rv = PQG_Check(params);
+    if (rv != SECSuccess) {
+	return rv;
+    }
     seed.data = NULL;
 
     rv = DSA_NewRandom(NULL, &params->subPrime, &seed);
     if (rv == SECSuccess) {
-        if (seed.len != DSA_SUBPRIME_LEN) {
+        if (seed.len != PQG_GetLength(&params->subPrime)) {
             PORT_SetError(SEC_ERROR_INVALID_ARGS);
             rv = SECFailure;
         } else {
             rv = dsa_NewKeyExtended(params, &seed, privKey);
         }
     }
     SECITEM_FreeItem(&seed, PR_FALSE);
     return rv;
 }
 
-/* For FIPS compliance testing. Seed must be exactly 20 bytes long */
+/* For FIPS compliance testing. Seed must be exactly the size of subPrime  */
 SECStatus 
 DSA_NewKeyFromSeed(const PQGParams *params, 
                    const unsigned char *seed,
                    DSAPrivateKey **privKey)
 {
-    /* TODO: check Q size */
     SECItem seedItem;
     seedItem.data = (unsigned char*) seed;
-    seedItem.len = DSA_SUBPRIME_LEN;
+    seedItem.len = PQG_GetLength(&params->subPrime);
     return dsa_NewKeyExtended(params, &seedItem, privKey);
 }
 
 static SECStatus 
 dsa_SignDigest(DSAPrivateKey *key, SECItem *signature, const SECItem *digest,
                const unsigned char *kb)
 {
     mp_int p, q, g;  /* PQG parameters */
     mp_int x, k;     /* private key & pseudo-random integer */
     mp_int r, s;     /* tuple (r, s) is signature) */
     mp_err err   = MP_OKAY;
     SECStatus rv = SECSuccess;
+    unsigned int dsa_subprime_len, dsa_signature_len, offset;
+    SECItem localDigest;
+    unsigned char localDigestData[DSA_MAX_SUBPRIME_LEN];
+    
 
-    /* FIPS-compliance dictates that digest is a SHA1 hash. */
+    /* FIPS-compliance dictates that digest is a SHA hash. */
     /* Check args. */
-    if (!key || !signature || !digest ||
-        (signature->len < DSA_SIGNATURE_LEN) ||
-	(digest->len != SHA1_LENGTH)) {
+    if (!key || !signature || !digest) {
 	PORT_SetError(SEC_ERROR_INVALID_ARGS);
 	return SECFailure;
     }
 
+    dsa_subprime_len = PQG_GetLength(&key->params.subPrime);
+    dsa_signature_len = dsa_subprime_len*2;
+    if ((signature->len < dsa_signature_len) ||
+	(digest->len > HASH_LENGTH_MAX)  ||
+	(digest->len < SHA1_LENGTH)) {
+	PORT_SetError(SEC_ERROR_INVALID_ARGS);
+	return SECFailure;
+    }
+
+    /* DSA accepts digests not equal to dsa_subprime_len, if the 
+     * digests are greater, then they are truncated to the size of 
+     * dsa_subprime_len, using the left most bits. If they are less
+     * then they are padded on the left.*/
+    PORT_Memset(localDigestData, 0, dsa_subprime_len);
+    offset = (digest->len < dsa_subprime_len) ? 
+			(dsa_subprime_len - digest->len) : 0;
+    PORT_Memcpy(localDigestData+offset, digest->data, 
+		dsa_subprime_len - offset);
+    localDigest.data = localDigestData;
+    localDigest.len = dsa_subprime_len;
+
     /* Initialize MPI integers. */
     MP_DIGITS(&p) = 0;
     MP_DIGITS(&q) = 0;
     MP_DIGITS(&g) = 0;
     MP_DIGITS(&x) = 0;
     MP_DIGITS(&k) = 0;
     MP_DIGITS(&r) = 0;
     MP_DIGITS(&s) = 0;
@@ -343,30 +370,30 @@ dsa_SignDigest(DSAPrivateKey *key, SECIt
     CHECK_MPI_OK( mp_init(&s) );
     /*
     ** Convert stored PQG and private key into MPI integers.
     */
     SECITEM_TO_MPINT(key->params.prime,    &p);
     SECITEM_TO_MPINT(key->params.subPrime, &q);
     SECITEM_TO_MPINT(key->params.base,     &g);
     SECITEM_TO_MPINT(key->privateValue,    &x);
-    OCTETS_TO_MPINT(kb, &k, DSA_SUBPRIME_LEN);
+    OCTETS_TO_MPINT(kb, &k, dsa_subprime_len);
     /*
     ** FIPS 186-1, Section 5, Step 1
     **
     ** r = (g**k mod p) mod q
     */
     CHECK_MPI_OK( mp_exptmod(&g, &k, &p, &r) ); /* r = g**k mod p */
     CHECK_MPI_OK(     mp_mod(&r, &q, &r) );     /* r = r mod q    */
     /*                                  
     ** FIPS 186-1, Section 5, Step 2
     **
-    ** s = (k**-1 * (SHA1(M) + x*r)) mod q
+    ** s = (k**-1 * (HASH(M) + x*r)) mod q
     */
-    SECITEM_TO_MPINT(*digest, &s);         /* s = SHA1(M)     */
+    SECITEM_TO_MPINT(localDigest, &s);          /* s = HASH(M)     */
     CHECK_MPI_OK( mp_invmod(&k, &q, &k) );      /* k = k**-1 mod q */
     CHECK_MPI_OK( mp_mulmod(&x, &r, &q, &x) );  /* x = x * r mod q */
     CHECK_MPI_OK( mp_addmod(&s, &x, &q, &s) );  /* s = s + x mod q */
     CHECK_MPI_OK( mp_mulmod(&s, &k, &q, &s) );  /* s = s * k mod q */
     /*
     ** verify r != 0 and s != 0
     ** mentioned as optional in FIPS 186-1.
     */
@@ -375,24 +402,25 @@ dsa_SignDigest(DSAPrivateKey *key, SECIt
 	rv = SECFailure;
 	goto cleanup;
     }
     /*
     ** Step 4
     **
     ** Signature is tuple (r, s)
     */
-    err = mp_to_fixlen_octets(&r, signature->data, DSA_SUBPRIME_LEN);
+    err = mp_to_fixlen_octets(&r, signature->data, dsa_subprime_len);
     if (err < 0) goto cleanup; 
-    err = mp_to_fixlen_octets(&s, signature->data + DSA_SUBPRIME_LEN, 
-                                  DSA_SUBPRIME_LEN);
+    err = mp_to_fixlen_octets(&s, signature->data + dsa_subprime_len, 
+                                  dsa_subprime_len);
     if (err < 0) goto cleanup; 
     err = MP_OKAY;
-    signature->len = DSA_SIGNATURE_LEN;
+    signature->len = dsa_signature_len;
 cleanup:
+    PORT_Memset(localDigestData, 0, DSA_MAX_SUBPRIME_LEN);
     mp_clear(&p);
     mp_clear(&q);
     mp_clear(&g);
     mp_clear(&x);
     mp_clear(&k);
     mp_clear(&r);
     mp_clear(&s);
     if (err) {
@@ -408,28 +436,29 @@ cleanup:
 ** On output, signature->len == size of signature in buffer.
 ** Uses a random seed.
 */
 SECStatus 
 DSA_SignDigest(DSAPrivateKey *key, SECItem *signature, const SECItem *digest)
 {
     SECStatus rv;
     int       retries = 10;
-    unsigned char kSeed[DSA_SUBPRIME_LEN];
+    unsigned char kSeed[DSA_MAX_SUBPRIME_LEN];
     unsigned int kSeedLen = 0;
     unsigned int i;
+    unsigned int dsa_subprime_len = PQG_GetLength(&key->params.subPrime);
     PRBool    good;
 
     PORT_SetError(0);
     do {
 	rv = dsa_GenerateGlobalRandomBytes(&key->params.subPrime,
                                            kSeed, &kSeedLen, sizeof kSeed);
 	if (rv != SECSuccess) 
 	    break;
-        if (kSeedLen != DSA_SUBPRIME_LEN) {
+        if (kSeedLen != dsa_subprime_len) {
             PORT_SetError(SEC_ERROR_INVALID_ARGS);
             rv = SECFailure;
             break;
         }
 	/* Disallow a value of 0 for k. */
 	good = PR_FALSE;
 	for (i = 0; i < kSeedLen; i++) {
 	    if (kSeed[i] != 0) {
@@ -463,31 +492,54 @@ DSA_SignDigestWithSeed(DSAPrivateKey * k
 /* signature is caller-supplied buffer of at least 20 bytes.
 ** On input,  signature->len == size of buffer to hold signature.
 **            digest->len    == size of digest.
 */
 SECStatus 
 DSA_VerifyDigest(DSAPublicKey *key, const SECItem *signature, 
                  const SECItem *digest)
 {
-    /* FIPS-compliance dictates that digest is a SHA1 hash. */
+    /* FIPS-compliance dictates that digest is a SHA hash. */
     mp_int p, q, g;      /* PQG parameters */
     mp_int r_, s_;       /* tuple (r', s') is received signature) */
     mp_int u1, u2, v, w; /* intermediate values used in verification */
     mp_int y;            /* public key */
     mp_err err;
+    int dsa_subprime_len, dsa_signature_len, offset;
+    SECItem localDigest;
+    unsigned char localDigestData[DSA_MAX_SUBPRIME_LEN];
     SECStatus verified = SECFailure;
 
     /* Check args. */
-    if (!key || !signature || !digest ||
-        (signature->len != DSA_SIGNATURE_LEN) ||
-	(digest->len != SHA1_LENGTH)) {
+    if (!key || !signature || !digest ) {
+	PORT_SetError(SEC_ERROR_INVALID_ARGS);
+	return SECFailure;
+    }
+
+    dsa_subprime_len = PQG_GetLength(&key->params.subPrime);
+    dsa_signature_len = dsa_subprime_len*2;
+    if ((signature->len != dsa_signature_len) ||
+	(digest->len > HASH_LENGTH_MAX)  ||
+	(digest->len < SHA1_LENGTH)) {
 	PORT_SetError(SEC_ERROR_INVALID_ARGS);
 	return SECFailure;
     }
+
+    /* DSA accepts digests not equal to dsa_subprime_len, if the 
+     * digests are greater, than they are truncated to the size of 
+     * dsa_subprime_len, using the left most bits. If they are less
+     * then they are padded on the left.*/
+    PORT_Memset(localDigestData, 0, dsa_subprime_len);
+    offset = (digest->len < dsa_subprime_len) ? 
+			(dsa_subprime_len - digest->len) : 0;
+    PORT_Memcpy(localDigestData+offset, digest->data, 
+		dsa_subprime_len - offset);
+    localDigest.data = localDigestData;
+    localDigest.len = dsa_subprime_len;
+
     /* Initialize MPI integers. */
     MP_DIGITS(&p)  = 0;
     MP_DIGITS(&q)  = 0;
     MP_DIGITS(&g)  = 0;
     MP_DIGITS(&y)  = 0;
     MP_DIGITS(&r_) = 0;
     MP_DIGITS(&s_) = 0;
     MP_DIGITS(&u1) = 0;
@@ -509,18 +561,18 @@ DSA_VerifyDigest(DSAPublicKey *key, cons
     */
     SECITEM_TO_MPINT(key->params.prime,    &p);
     SECITEM_TO_MPINT(key->params.subPrime, &q);
     SECITEM_TO_MPINT(key->params.base,     &g);
     SECITEM_TO_MPINT(key->publicValue,     &y);
     /*
     ** Convert received signature (r', s') into MPI integers.
     */
-    OCTETS_TO_MPINT(signature->data, &r_, DSA_SUBPRIME_LEN);
-    OCTETS_TO_MPINT(signature->data + DSA_SUBPRIME_LEN, &s_, DSA_SUBPRIME_LEN);
+    OCTETS_TO_MPINT(signature->data, &r_, dsa_subprime_len);
+    OCTETS_TO_MPINT(signature->data + dsa_subprime_len, &s_, dsa_subprime_len);
     /*
     ** Verify that 0 < r' < q and 0 < s' < q
     */
     if (mp_cmp_z(&r_) <= 0 || mp_cmp_z(&s_) <= 0 ||
         mp_cmp(&r_, &q) >= 0 || mp_cmp(&s_, &q) >= 0) {
 	/* err is zero here. */
 	PORT_SetError(SEC_ERROR_BAD_SIGNATURE);
 	goto cleanup; /* will return verified == SECFailure */
@@ -529,19 +581,19 @@ DSA_VerifyDigest(DSAPublicKey *key, cons
     ** FIPS 186-1, Section 6, Step 1
     **
     ** w = (s')**-1 mod q
     */
     CHECK_MPI_OK( mp_invmod(&s_, &q, &w) );      /* w = (s')**-1 mod q */
     /*
     ** FIPS 186-1, Section 6, Step 2
     **
-    ** u1 = ((SHA1(M')) * w) mod q
+    ** u1 = ((Hash(M')) * w) mod q
     */
-    SECITEM_TO_MPINT(*digest, &u1);              /* u1 = SHA1(M')     */
+    SECITEM_TO_MPINT(localDigest, &u1);              /* u1 = HASH(M')     */
     CHECK_MPI_OK( mp_mulmod(&u1, &w, &q, &u1) ); /* u1 = u1 * w mod q */
     /*
     ** FIPS 186-1, Section 6, Step 3
     **
     ** u2 = ((r') * w) mod q
     */
     CHECK_MPI_OK( mp_mulmod(&r_, &w, &q, &u2) );
     /*
--- a/security/nss/lib/freebl/ldvector.c
+++ b/security/nss/lib/freebl/ldvector.c
@@ -248,19 +248,23 @@ static const struct FREEBLVectorStr vect
     SHA224_End,
     SHA224_HashBuf,
     SHA224_Hash,
     SHA224_TraceState,
     SHA224_FlattenSize,
     SHA224_Flatten,
     SHA224_Resurrect,
     SHA224_Clone,
-    BLAPI_SHVerifyFile
+    BLAPI_SHVerifyFile,
 
     /* End of Version 3.013 */
+
+    PQG_ParamGenV2
+
+    /* End of Version 3.014 */
 };
 
 const FREEBLVector * 
 FREEBL_GetVector(void)
 {
     extern const char __nss_freebl_rcsid[];
     extern const char __nss_freebl_sccsid[];
 
--- a/security/nss/lib/freebl/loader.c
+++ b/security/nss/lib/freebl/loader.c
@@ -845,16 +845,17 @@ SECStatus
 PQG_ParamGenSeedLen( unsigned int j, unsigned int seedBytes, 
                      PQGParams **pParams, PQGVerify **pVfy)
 {
   if (!vector && PR_SUCCESS != freebl_RunLoaderOnce())
       return SECFailure;
   return (vector->p_PQG_ParamGenSeedLen)(j, seedBytes, pParams, pVfy);
 }
 
+
 SECStatus   
 PQG_VerifyParams(const PQGParams *params, const PQGVerify *vfy, 
 		 SECStatus *result)
 {
   if (!vector && PR_SUCCESS != freebl_RunLoaderOnce())
       return SECFailure;
   return (vector->p_PQG_VerifyParams)(params, vfy, result);
 }
@@ -1834,8 +1835,18 @@ SHA224_Clone(SHA224Context *dest, SHA224
 
 PRBool
 BLAPI_SHVerifyFile(const char *name)
 {
   if (!vector && PR_SUCCESS != freebl_RunLoaderOnce())
       return PR_FALSE;
   return vector->p_BLAPI_SHVerifyFile(name);
 }
+
+/* === new for DSA-2 === */
+SECStatus
+PQG_ParamGenV2( unsigned int L, unsigned int N, unsigned int seedBytes, 
+               PQGParams **pParams, PQGVerify **pVfy)
+{
+  if (!vector && PR_SUCCESS != freebl_RunLoaderOnce())
+      return SECFailure;
+  return (vector->p_PQG_ParamGenV2)(L, N, seedBytes, pParams, pVfy); 
+}
--- a/security/nss/lib/freebl/loader.h
+++ b/security/nss/lib/freebl/loader.h
@@ -6,17 +6,17 @@
  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
 /* $Id$ */
 
 #ifndef _LOADER_H_
 #define _LOADER_H_ 1
 
 #include "blapi.h"
 
-#define FREEBL_VERSION 0x030D
+#define FREEBL_VERSION 0x030E
 
 struct FREEBLVectorStr {
 
   unsigned short length;  /* of this struct in bytes */
   unsigned short version; /* of this struct. */
 
   RSAPrivateKey * (* p_RSA_NewKey)(int         keySizeInBits,
 				 SECItem *   publicExponent);
@@ -558,16 +558,22 @@ struct FREEBLVectorStr {
  unsigned int (* p_SHA224_FlattenSize)(SHA224Context *cx);
  SECStatus (* p_SHA224_Flatten)(SHA224Context *cx,unsigned char *space);
  SHA224Context * (* p_SHA224_Resurrect)(unsigned char *space, void *arg);
  void (* p_SHA224_Clone)(SHA224Context *dest, SHA224Context *src);
  PRBool (*p_BLAPI_SHVerifyFile)(const char *name);
 
   /* Version 3.013 came to here */
 
+ SECStatus (* p_PQG_ParamGenV2)( unsigned int L, unsigned int N,
+                                unsigned int seedBytes, 
+                                PQGParams **pParams, PQGVerify **pVfy); 
+
+  /* Version 3.014 came to here */
+
 };
 
 typedef struct FREEBLVectorStr FREEBLVector;
 
 SEC_BEGIN_PROTOS
 
 typedef const FREEBLVector * FREEBLGetVectorFn(void);
 
--- a/security/nss/lib/freebl/pqg.c
+++ b/security/nss/lib/freebl/pqg.c
@@ -1,14 +1,14 @@
 /* This Source Code Form is subject to the terms of the Mozilla Public
  * License, v. 2.0. If a copy of the MPL was not distributed with this
  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
 
 /*
- * PQG parameter generation/verification.  Based on FIPS 186-1.
+ * PQG parameter generation/verification.  Based on FIPS 186-3.
  *
  * $Id$
  */
 #ifdef FREEBL_NO_DEPEND
 #include "stubs.h"
 #endif
 
 #include "prerr.h"
@@ -16,36 +16,210 @@
 
 #include "prtypes.h"
 #include "blapi.h"
 #include "secitem.h"
 #include "mpi.h"
 #include "mpprime.h"
 #include "mplogic.h"
 #include "secmpi.h"
+#include "sechash.h"
 
 #define MAX_ITERATIONS 1000  /* Maximum number of iterations of primegen */
-#define PQG_Q_PRIMALITY_TESTS 18 /* from HAC table 4.4 */
-#define PQG_P_PRIMALITY_TESTS 5  /* from HAC table 4.4 */
+
+typedef enum {
+    FIPS186_1_TYPE,		/* Probablistic */
+    FIPS186_3_TYPE,		/* Probablistic */
+    FIPS186_3_ST_TYPE		/* Shawne-Taylor provable */
+} pqgGenType;
+
+/*
+ * These test iterations are quite a bit larger than we previously had.
+ * This is because FIPS 186-3 is worried about the primes in PQG generation.
+ * It may be possible to purposefully construct composites which more 
+ * iterations of Miller-Rabin than the for your normal randomly selected 
+ * numbers.There are 3 ways to counter this: 1) use one of the cool provably 
+ * prime algorithms (which would require a lot more work than DSA-2 deservers.
+ * 2) add a Lucas primality test (which requires coding a Lucas primality test,
+ * or 3) use a larger M-R test count. I chose the latter. It increases the time
+ * that it takes to prove the selected prime, but it shouldn't increase the
+ * overall time to run the algorithm (non-primes should still faile M-R
+ * realively quickly). If you want to get that last bit of performance,
+ * implement Lucas and adjust these two functions.  See FIPS 186-3 Appendix C
+ * and F for more information.
+ */
+int prime_testcount_p(int L, int N)
+{
+    switch (L) {
+    case 1024:
+	return 40;
+    case 2048:
+	return 56;
+    case 3072:
+	return 64;
+    default:
+ 	break;
+    }
+    return 50; /* L = 512-960 */
+}
 
- /* XXX to be replaced by define in blapit.h */
-#define BITS_IN_Q 160
+/* The q numbers are different if you run M-R followd by Lucas. I created
+ * a separate function so if someone wanted to add the Lucas check, they
+ * could do so fairly easily */
+int prime_testcount_q(int L, int N)
+{
+    return prime_testcount_p(L,N);
+}
+
+/*
+ * generic function to make sure our input matches DSA2 requirements 
+ * this gives us one place to go if we need to bump the requirements in the
+ * future.
+ */
+SECStatus static
+pqg_validate_dsa2(unsigned int L, unsigned int N)
+{
+
+    switch (L) {
+    case 1024:
+	if (N != DSA1_Q_BITS) {
+	    PORT_SetError(SEC_ERROR_INVALID_ARGS);
+	    return SECFailure;
+	}
+	break;
+    case 2048:
+	if ((N != 224) && (N != 256)) {
+	    PORT_SetError(SEC_ERROR_INVALID_ARGS);
+	    return SECFailure;
+	}
+	break;
+    case 3072:
+	if (N != 256) {
+	    PORT_SetError(SEC_ERROR_INVALID_ARGS);
+	    return SECFailure;
+	}
+	break;
+    default:
+	PORT_SetError(SEC_ERROR_INVALID_ARGS);
+	return SECFailure;
+    }
+    return SECSuccess;
+}
 
-/* For FIPS-compliance testing.
-** The following array holds the seed defined in FIPS 186-1 appendix 5.
-** This seed is used to generate P and Q according to appendix 2; use of
-** this seed will exactly generate the PQG specified in appendix 2.
-*/
-#ifdef FIPS_186_1_A5_TEST
-static const unsigned char fips_186_1_a5_pqseed[] = {
-    0xd5, 0x01, 0x4e, 0x4b, 0x60, 0xef, 0x2b, 0xa8,
-    0xb6, 0x21, 0x1b, 0x40, 0x62, 0xba, 0x32, 0x24,
-    0xe0, 0x42, 0x7d, 0xd3
-};
-#endif
+/*
+ * Select the lowest hash algorithm usable
+ */
+static HASH_HashType
+getFirstHash(unsigned int L, unsigned int N)
+{
+    if (N < 224) {
+	return HASH_AlgSHA1;
+    }
+    if (N < 256) {
+	return HASH_AlgSHA224;
+    }
+    if (N < 384) {
+	return HASH_AlgSHA256;
+    }
+    if (N < 512) {
+	return HASH_AlgSHA384;
+    }
+    return HASH_AlgSHA512;
+}
+
+/*
+ * find the next usable hash algorthim
+ */
+static HASH_HashType
+getNextHash(HASH_HashType hashtype)
+{
+    switch (hashtype) {
+    case HASH_AlgSHA1:
+	hashtype = HASH_AlgSHA224;
+	break;
+    case HASH_AlgSHA224:
+	hashtype = HASH_AlgSHA256;
+	break;
+    case HASH_AlgSHA256:
+	hashtype = HASH_AlgSHA384;
+	break;
+    case HASH_AlgSHA384:
+	hashtype = HASH_AlgSHA512;
+	break;
+    case HASH_AlgSHA512:
+    default:
+	hashtype = HASH_AlgTOTAL;
+	break;
+    }
+    return hashtype;
+}
+
+
+unsigned int
+PQG_GetLength(const SECItem *obj)
+{
+    unsigned int len = obj->len;
+
+    if (obj->data == NULL) {
+	return 0;
+    }
+    if (len > 1 && obj->data[0] == 0) {
+	len--;
+    }
+    return len;
+}
+
+SECStatus
+PQG_Check(const PQGParams *params)
+{
+    unsigned int L,N;
+    SECStatus rv = SECSuccess;
+
+    if (params == NULL) {
+	PORT_SetError(SEC_ERROR_INVALID_ARGS);
+	return SECFailure;
+    }
+
+    L = PQG_GetLength(&params->prime)*BITS_PER_BYTE;
+    N = PQG_GetLength(&params->subPrime)*BITS_PER_BYTE;
+
+    if (L < 1024) {
+	int j;
+
+	/* handle DSA1 pqg parameters with less thatn 1024 bits*/
+	if ( N != DSA1_Q_BITS ) {
+	    PORT_SetError(SEC_ERROR_INVALID_ARGS);
+	    return SECFailure;
+	}
+	j = PQG_PBITS_TO_INDEX(L);
+	if ( j >= 0 && j <= 8 ) {
+	    PORT_SetError(SEC_ERROR_INVALID_ARGS);
+	    rv = SECFailure;
+	}
+    } else {
+	/* handle DSA2 parameters (includes DSA1, 1024 bits) */
+	rv = pqg_validate_dsa2(L, N);
+    }
+    return rv;
+}
+
+HASH_HashType
+PQG_GetHashType(const PQGParams *params)
+{
+    unsigned int L,N;
+
+    if (params == NULL) {
+	PORT_SetError(SEC_ERROR_INVALID_ARGS);
+	return SECFailure;
+    }
+
+    L = PQG_GetLength(&params->prime)*BITS_PER_BYTE;
+    N = PQG_GetLength(&params->subPrime)*BITS_PER_BYTE;
+    return getFirstHash(L, N);
+}
 
 /* Get a seed for generating P and Q.  If in testing mode, copy in the
 ** seed from FIPS 186-1 appendix 5.  Otherwise, obtain bytes from the
 ** global random number generator.
 */
 static SECStatus
 getPQseed(SECItem *seed, PRArenaPool* arena)
 {
@@ -53,30 +227,25 @@ getPQseed(SECItem *seed, PRArenaPool* ar
 
     if (!seed->data) {
         seed->data = (unsigned char*)PORT_ArenaZAlloc(arena, seed->len);
     }
     if (!seed->data) {
 	PORT_SetError(SEC_ERROR_NO_MEMORY);
 	return SECFailure;
     }
-#ifdef FIPS_186_1_A5_TEST
-    memcpy(seed->data, fips_186_1_a5_pqseed, seed->len);
-    return SECSuccess;
-#else
     rv = RNG_GenerateGlobalRandomBytes(seed->data, seed->len);
     /*
      * NIST CMVP disallows a sequence of 20 bytes with the most
      * significant byte equal to 0.  Perhaps they interpret
      * "a sequence of at least 160 bits" as "a number >= 2^159".
      * So we always set the most significant bit to 1. (bug 334533)
      */
     seed->data[0] |= 0x80;
     return rv;
-#endif
 }
 
 /* Generate a candidate h value.  If in testing mode, use the h value
 ** specified in FIPS 186-1 appendix 5, h = 2.  Otherwise, obtain bytes
 ** from the global random number generator.
 */
 static SECStatus
 generate_h_candidate(SECItem *hit, mp_int *H)
@@ -94,27 +263,22 @@ generate_h_candidate(SECItem *hit, mp_in
     err = mp_read_unsigned_octets(H, hit->data, hit->len);
     if (err) {
 	MP_TO_SEC_ERROR(err);
 	return SECFailure;
     }
     return SECSuccess;
 }
 
-/* Compute SHA[(SEED + addend) mod 2**g]
-** Result is placed in shaOutBuf.
-** This computation is used in steps 2 and 7 of FIPS 186 Appendix 2.2 .
-*/
 static SECStatus
-addToSeedThenSHA(const SECItem * seed,
-                 unsigned long   addend,
-                 int             g,
-                 unsigned char * shaOutBuf)
+addToSeed(const SECItem * seed,
+          unsigned long   addend,
+          int             seedlen, /* g in 186-1 */
+          SECItem * seedout)
 {
-    SECItem str = { 0, 0, 0 };
     mp_int s, sum, modulus, tmp;
     mp_err    err = MP_OKAY;
     SECStatus rv  = SECSuccess;
     MP_DIGITS(&s)       = 0;
     MP_DIGITS(&sum)     = 0;
     MP_DIGITS(&modulus) = 0;
     MP_DIGITS(&tmp)     = 0;
     CHECK_MPI_OK( mp_init(&s) );
@@ -124,35 +288,60 @@ addToSeedThenSHA(const SECItem * seed,
     /* seed += addend */
     if (addend < MP_DIGIT_MAX) {
 	CHECK_MPI_OK( mp_add_d(&s, (mp_digit)addend, &s) );
     } else {
 	CHECK_MPI_OK( mp_init(&tmp) );
 	CHECK_MPI_OK( mp_set_ulong(&tmp, addend) );
 	CHECK_MPI_OK( mp_add(&s, &tmp, &s) );
     }
-    CHECK_MPI_OK( mp_div_2d(&s, (mp_digit)g, NULL, &sum) );/*sum = s mod 2**g */
-    MPINT_TO_SECITEM(&sum, &str, NULL);
-    rv = SHA1_HashBuf(shaOutBuf, str.data, str.len); /* SHA1 hash result */
+    /*sum = s mod 2**seedlen */
+    CHECK_MPI_OK( mp_div_2d(&s, (mp_digit)seedlen, NULL, &sum) );
+    if (seedout->data != NULL) {
+	SECITEM_ZfreeItem(seedout, PR_FALSE);
+    }
+    MPINT_TO_SECITEM(&sum, seedout, NULL);
 cleanup:
     mp_clear(&s);
     mp_clear(&sum);
     mp_clear(&modulus);
     mp_clear(&tmp);
-    if (str.data)
-	SECITEM_ZfreeItem(&str, PR_FALSE);
     if (err) {
 	MP_TO_SEC_ERROR(err);
 	return SECFailure;
     }
     return rv;
 }
 
+/* Compute Hash[(SEED + addend) mod 2**g]
+** Result is placed in shaOutBuf.
+** This computation is used in steps 2 and 7 of FIPS 186 Appendix 2.2  and
+** step 11.2 of FIPS 186-3 Appendix A.1.1.2 .
+*/
+static SECStatus
+addToSeedThenHash( HASH_HashType   hashtype,
+                 const SECItem * seed,
+                 unsigned long   addend,
+                 int             seedlen, /* g in 186-1 */
+                 unsigned char * hashOutBuf)
+{
+    SECItem str = { 0, 0, 0 };
+    SECStatus rv;
+    rv = addToSeed(seed, addend, seedlen, &str);
+    if (rv != SECSuccess) {
+	return rv;
+    }
+    rv = HASH_HashBuf(hashtype, hashOutBuf, str.data, str.len);/* hash result */
+    if (str.data)
+	SECITEM_ZfreeItem(&str, PR_FALSE);
+    return rv;
+}
+
 /*
-**  Perform steps 2 and 3 of FIPS 186, appendix 2.2.
+**  Perform steps 2 and 3 of FIPS 186-1, appendix 2.2.
 **  Generate Q from seed.
 */
 static SECStatus
 makeQfromSeed(
       unsigned int  g,          /* input.  Length of seed in bits. */
 const SECItem   *   seed,       /* input.  */
       mp_int    *   Q)          /* output. */
 {
@@ -162,17 +351,17 @@ const SECItem   *   seed,       /* input
     SECStatus rv  = SECSuccess;
     mp_err    err = MP_OKAY;
     int i;
     /* ******************************************************************
     ** Step 2.
     ** "Compute U = SHA[SEED] XOR SHA[(SEED+1) mod 2**g]."
     **/
     CHECK_SEC_OK( SHA1_HashBuf(sha1, seed->data, seed->len) );
-    CHECK_SEC_OK( addToSeedThenSHA(seed, 1, g, sha2) );
+    CHECK_SEC_OK( addToSeedThenHash(HASH_AlgSHA1, seed, 1, g, sha2) );
     for (i=0; i<SHA1_LENGTH; ++i) 
 	U[i] = sha1[i] ^ sha2[i];
     /* ******************************************************************
     ** Step 3.
     ** "Form Q from U by setting the most signficant bit (the 2**159 bit)
     **  and the least signficant bit to 1.  In terms of boolean operations,
     **  Q = U OR 2**159 OR 1.  Note that 2**159 < Q < 2**160."
     */
@@ -185,94 +374,648 @@ cleanup:
      memset(sha2, 0, SHA1_LENGTH);
      if (err) {
 	MP_TO_SEC_ERROR(err);
 	return SECFailure;
      }
      return rv;
 }
 
-/*  Perform steps 7, 8 and 9 of FIPS 186, appendix 2.2.
+/*
+**  Perform steps 6 and 7 of FIPS 186-3, appendix A.1.1.2.
+**  Generate Q from seed.
+*/
+static SECStatus
+makeQ2fromSeed(
+      HASH_HashType hashtype,	/* selected Hashing algorithm */
+      unsigned int  N,          /* input.  Length of q in bits. */
+const SECItem   *   seed,       /* input.  */
+      mp_int    *   Q)          /* output. */
+{
+    unsigned char U[HASH_LENGTH_MAX];
+    SECStatus rv  = SECSuccess;
+    mp_err    err = MP_OKAY;
+    int N_bytes = N/BITS_PER_BYTE; /* length of N in bytes rather than bits */
+    int hashLen = HASH_ResultLen(hashtype);
+    int offset = 0;
+
+    /* ******************************************************************
+    ** Step 6.
+    ** "Compute U = hash[SEED] mod 2**N-1]."
+    **/
+    CHECK_SEC_OK( HASH_HashBuf(hashtype, U, seed->data, seed->len) );
+    /* mod 2**N . Step 7 will explicitly set the top bit to 1, so no need
+     * to handle mod 2**N-1 */
+    if 	(hashLen > N_bytes) {
+	offset = hashLen - N_bytes;
+    }
+    /* ******************************************************************
+    ** Step 7.
+    ** computed_q = 2**(N-1) + U + 1 - (U mod 2)
+    ** 
+    ** This is the same as:
+    ** computed_q = 2**(N-1) | U | 1;
+    */
+    U[offset]    |= 0x80;  /* U is MSB first */
+    U[hashLen-1] |= 0x01;
+    err = mp_read_unsigned_octets(Q, &U[offset], N_bytes);
+cleanup:
+     memset(U, 0, HASH_LENGTH_MAX);
+     if (err) {
+	MP_TO_SEC_ERROR(err);
+	return SECFailure;
+     }
+     return rv;
+}
+
+/*
+**  Perform steps from  FIPS 186-3, Appendix A.1.2.1 and Appendix C.6
+**
+**  This generates a provable prime from two smaller prime. The resulting
+**  prime p will have q0 as a multiple of p-1. q0 can be 1.
+**
+** This implments steps 4 thorough 22 of FIPS 186-3 A.1.2.1 and
+**                steps 16 through 34 of FIPS 186-2 C.6
+*/
+#define MAX_ST_SEED_BITS HASH_LENGTH_MAX*BITS_PER_BYTE
+SECStatus
+makePrimefromPrimesShawneTaylor(
+      HASH_HashType hashtype,	/* selected Hashing algorithm */
+      unsigned int  length,     /* input. Length of prime in bits. */
+      mp_int    *   c0,         /* seed prime */
+      mp_int    *   q,          /* sub prime, can be 1 */
+      mp_int    *   prime,      /* output.  */
+      SECItem   *   prime_seed, /* input/output.  */
+      int       *   prime_gen_counter) /* input/output.  */
+{
+    mp_int c;
+    mp_int c0_2;
+    mp_int t;
+    mp_int a;
+    mp_int z;
+    mp_int two_length_minus_1;
+    SECStatus rv = SECFailure;
+    int hashlen = HASH_ResultLen(hashtype);
+    int outlen = hashlen*BITS_PER_BYTE;
+    int offset;
+    unsigned char bit, mask;
+    /* x needs to hold roundup(L/outlen)*outlen.
+     * This can be no larger than L+outlen-1, So we set it's size to
+     * our max L + max outlen and know we are safe */
+    unsigned char x[DSA_MAX_P_BITS/8+HASH_LENGTH_MAX];
+    mp_err err = MP_OKAY;
+    int i;
+
+    MP_DIGITS(&c) = 0;
+    MP_DIGITS(&c0_2) = 0;
+    MP_DIGITS(&t) = 0;
+    MP_DIGITS(&a) = 0;
+    MP_DIGITS(&z) = 0;
+    MP_DIGITS(&two_length_minus_1) = 0;
+    CHECK_MPI_OK( mp_init(&c) );
+    CHECK_MPI_OK( mp_init(&c0_2) );
+    CHECK_MPI_OK( mp_init(&t) );
+    CHECK_MPI_OK( mp_init(&a) );
+    CHECK_MPI_OK( mp_init(&z) );
+    CHECK_MPI_OK( mp_init(&two_length_minus_1) );
+
+    int iterations;
+    int old_counter;
+
+    /*
+    ** There is a slight mapping of variable names depending on which
+    ** FIPS 186 steps are being carried out. The mapping is as follows:
+    **  variable          A.1.2.1           C.6
+    **    c0                p0               c0
+    **    q                 q                1
+    **    c                 p                c
+    **    c0_2            2*p0*q            2*c0
+    **    length            L               length
+    **    prime_seed       pseed            prime_seed
+    **  prime_gen_counter pgen_counter     prime_gen_counter
+    **
+    ** Also note: or iterations variable is actually iterations+1, since
+    ** iterations+1 works better in C.
+    */
+
+    /* Step 4/16 iterations = ceiling(length/outlen)-1 */
+    iterations = (length+outlen-1)/outlen;  /* NOTE: iterations +1 */
+    /* Step 5/17 old_counter = prime_gen_counter */
+    old_counter = *prime_gen_counter;
+    /* 
+    ** Comment: Generate a pseudorandom integer x in the interval
+    ** [2**(lenght-1), 2**length].
+    **
+    ** Step 6/18 x = 0
+    */
+    PORT_Memset(x, 0, sizeof(x));
+    /*
+    ** Step 7/19 for i = 0 to iterations do
+    **  x = x + (HASH(prime_seed + i) * 2^(i*outlen))
+    */
+    for (i=0; i < iterations; i++) {
+	/* is bigger than prime_seed should get to */
+	CHECK_SEC_OK( addToSeedThenHash(hashtype, prime_seed, i, 
+		MAX_ST_SEED_BITS,&x[(iterations - i - 1)*hashlen]));
+    }
+    /* Step 8/20 prime_seed = prime_seed + iterations + 1 */
+    CHECK_SEC_OK(addToSeed(prime_seed, iterations, MAX_ST_SEED_BITS, 
+					prime_seed));
+    /*
+    ** Step 9/21 x = 2 ** (length-1) + x mod 2 ** (length-1) 
+    **
+    **   This step mathematically sets the high bit and clears out
+    **  all the other bits higher than length. 'x' is stored
+    **  in the x array, MSB first. The above formula gives us an 'x' 
+    **  which is length bytes long and has the high bit set. We also know 
+    **  that length <= iterations*outlen since 
+    **  iterations=ceiling(length/outlen). First we find the offset in 
+    **  bytes into the array where the high bit is.
+    */
+    offset = (outlen*iterations - length)/BITS_PER_BYTE;
+    /* now we want to set the 'high bit', since length may not be a 
+     * multiple of 8,*/
+    bit = 1 << ((length-1) & 0x7); /* select the proper bit in the byte */
+    /* we need to zero out the rest of the bits in the byte above */
+    mask = (bit-1);
+    /* now we set it */
+    x[offset] = (mask & x[offset]) | bit;
+    /*
+    ** Comment: Generate a candidate prime c in the interval
+    ** [2**(lenght-1), 2**length].
+    **
+    ** Step 10 t = ceiling(x/(2q(p0)))
+    ** Step 22 t = ceiling(x/(2(c0)))
+    */
+    CHECK_MPI_OK( mp_read_unsigned_octets(&t, &x[offset], 
+			hashlen*iterations - offset ) ); /* t = x */
+    CHECK_MPI_OK( mp_mul(c0, q, &c0_2) );        /* c0_2 is now c0*q */
+    CHECK_MPI_OK( mp_add(&c0_2, &c0_2, &c0_2) ); /* c0_2 is now 2*q*c0 */
+    CHECK_MPI_OK( mp_add(&t, &c0_2, &t) );       /* t = x+2*q*c0 */
+    CHECK_MPI_OK( mp_sub_d(&t, (mp_digit) 1, &t) ); /* t = x+2*q*c0 -1 */
+    /* t = floor((x+2qc0-1)/2qc0) = ceil(x/2qc0) */
+    CHECK_MPI_OK( mp_div(&t, &c0_2, &t, NULL) );
+    /* 
+    ** step 11: if (2tqp0 +1 > 2**length), then t = ceiling(2**(length-1)/2qp0)
+    ** step 12: t = 2tqp0 +1.
+    **
+    ** step 23: if (2tc0 +1 > 2**length), then t = ceiling(2**(length-1)/2c0)
+    ** step 24: t = 2tc0 +1.
+    */
+    CHECK_MPI_OK( mp_2expt(&two_length_minus_1, length-1) );
+step_23:
+    CHECK_MPI_OK( mp_mul(&t, &c0_2, &c) );               /* c = t*2qc0 */
+    CHECK_MPI_OK( mp_add_d(&c, (mp_digit)1, &c) );       /* c= 2tqc0 + 1*/
+    if (mpl_significant_bits(&c) > length) {     /* if c > 2**length */
+	    CHECK_MPI_OK( mp_sub_d(&c0_2, (mp_digit) 1, &t) ); /* t = 2qc0-1 */
+	    /* t = 2**(length-1) + 2qc0 -1 */
+	    CHECK_MPI_OK( mp_add(&two_length_minus_1,&t, &t) );
+	    /* t = floor((2**(length-1)+2qc0 -1)/2qco) 
+	     *   = ceil(2**(lenght-2)/2qc0) */
+	    CHECK_MPI_OK( mp_div(&t, &c0_2, &t, NULL) );
+	    CHECK_MPI_OK( mp_mul(&t, &c0_2, &c) );         
+	    CHECK_MPI_OK( mp_add_d(&c, (mp_digit)1, &c) );  /* c= 2tqc0 + 1*/
+    }
+    /* Step 13/25 prime_gen_counter = prime_gen_counter + 1*/
+    (*prime_gen_counter)++;
+    /*
+    ** Comment: Test the candidate prime c for primality; first pick an
+    ** integer a between 2 and c-2.
+    **
+    ** Step 14/26 a=0
+    */
+    PORT_Memset(x, 0, sizeof(x));    /* use x for a */
+    /*
+    ** Step 15/27 for i = 0 to iterations do
+    **  a = a + (HASH(prime_seed + i) * 2^(i*outlen))
+    **
+    ** NOTE: we reuse the x array for 'a' initially.
+    */
+    for (i=0; i < iterations; i++) {
+	/* MAX_ST_SEED_BITS is bigger than prime_seed should get to */
+	CHECK_SEC_OK(addToSeedThenHash(hashtype, prime_seed, i, 
+			MAX_ST_SEED_BITS,&x[(iterations - i - 1)*hashlen]));
+    }
+    /* Step 16/28 prime_seed = prime_seed + iterations + 1 */
+    CHECK_SEC_OK(addToSeed(prime_seed, iterations, MAX_ST_SEED_BITS, 
+					prime_seed));
+    /* Step 17/29 a = 2 + (a mod (c-3)). */
+    CHECK_MPI_OK( mp_read_unsigned_octets(&a, x, iterations*hashlen) );
+    CHECK_MPI_OK( mp_sub_d(&c, (mp_digit) 3, &z) ); /* z = c -3 */
+    CHECK_MPI_OK( mp_mod(&a, &z, &a) );             /* a = a mod c -3 */
+    CHECK_MPI_OK( mp_add_d(&a, (mp_digit) 2, &a) ); /* a = 2 + a mod c -3 */
+    /*
+    ** Step 18 z = a**(2tq) mod p.
+    ** Step 30 z = a**(2t) mod c.
+    */
+    CHECK_MPI_OK( mp_mul(&t, q, &z) );              /* z = tq */
+    CHECK_MPI_OK( mp_add(&z, &z, &z) );             /* z = 2tq */
+    CHECK_MPI_OK( mp_exptmod(&a, &z, &c, &z) );     /* z = a**(2tq) mod c */
+    /*
+    ** Step 19 if (( 1 == GCD(z-1,p)) and ( 1 == z**p0 mod p )), then 
+    ** Step 31 if (( 1 == GCD(z-1,c)) and ( 1 == z**c0 mod c )), then
+    */
+    CHECK_MPI_OK( mp_sub_d(&z, (mp_digit) 1, &a) );
+    CHECK_MPI_OK( mp_gcd(&a,&c,&a ));
+    if (mp_cmp_d(&a, (mp_digit)1) == 0) {
+	CHECK_MPI_OK( mp_exptmod(&z, c0, &c, &a) );
+	if (mp_cmp_d(&a, (mp_digit)1) == 0) {
+	    /* Step 31.1 prime = c */
+	    CHECK_MPI_OK( mp_copy(&c, prime) );
+	    /*
+	    ** Step 31.2 return Success, prime, prime_seed, 
+	    **    prime_gen_counter 
+	    */
+	    rv = SECSuccess;
+	    goto cleanup;
+	}
+    }
+    /*
+    ** Step 20/32 If (prime_gen_counter > 4 * length + old_counter then
+    **   return (FAILURE, 0, 0, 0).
+    ** NOTE: the test is reversed, so we fall through on failure to the
+    ** cleanup routine
+    */
+    if (*prime_gen_counter < (4*length + old_counter)) {
+	/* Step 21/33 t = t + 1 */
+	CHECK_MPI_OK( mp_add_d(&t, (mp_digit) 1, &t) );
+	/* Step 22/34 Go to step 23/11 */
+	goto step_23;
+    }
+
+    /* if (prime_gencont > (4*length + old_counter), fall through to failure */
+    rv = SECFailure; /* really is already set, but paranoia is good */
+	
+cleanup:
+    mp_clear(&c);
+    mp_clear(&c0_2);
+    mp_clear(&t);
+    mp_clear(&a);
+    mp_clear(&z);
+    mp_clear(&two_length_minus_1);
+    if (err) {
+	MP_TO_SEC_ERROR(err);
+	rv = SECFailure;
+    }
+    if (rv == SECFailure) {
+	mp_zero(prime);
+	if (prime_seed->data) {
+	    SECITEM_FreeItem(prime_seed, PR_FALSE);
+	}
+	*prime_gen_counter = 0;
+    }
+    return rv;
+}
+
+/*
+**  Perform steps from  FIPS 186-3, Appendix C.6
+**
+**  This generates a provable prime from a seed
+*/
+SECStatus
+makePrimefromSeedShawneTaylor(
+      HASH_HashType hashtype,	/* selected Hashing algorithm */
+      unsigned int  length,     /* input.  Length of prime in bits. */
+const SECItem   *   input_seed,       /* input.  */
+      mp_int    *   prime,      /* output.  */
+      SECItem   *   prime_seed, /* output.  */
+      int       *   prime_gen_counter) /* output.  */
+{
+    mp_int c;
+    mp_int c0;
+    mp_int one;
+    SECStatus rv = SECFailure;
+    int hashlen = HASH_ResultLen(hashtype);
+    int outlen = hashlen*BITS_PER_BYTE;
+    int offset;
+    unsigned char bit, mask;
+    unsigned char x[HASH_LENGTH_MAX*2];
+    mp_digit dummy;
+    mp_err err = MP_OKAY;
+    int i;
+
+    MP_DIGITS(&c) = 0;
+    MP_DIGITS(&c0) = 0;
+    MP_DIGITS(&one) = 0;
+    CHECK_MPI_OK( mp_init(&c) );
+    CHECK_MPI_OK( mp_init(&c0) );
+    CHECK_MPI_OK( mp_init(&one) );
+
+    /* Step 1. if length < 2 then return (FAILURE, 0, 0, 0) */
+    if (length < 2) {
+	rv = SECFailure;
+	goto cleanup;
+    }
+    /* Step 2. if length >= 33 then goto step 14 */
+    if (length >= 33) {
+	mp_zero(&one);
+	CHECK_MPI_OK( mp_add_d(&one, (mp_digit) 1, &one) );
+
+	/* Step 14 (status, c0, prime_seed, prime_gen_counter) =
+	** (ST_Random_Prime((ceil(length/2)+1, input_seed)
+	*/
+	rv = makePrimefromSeedShawneTaylor(hashtype, (length+1)/2+1,
+			input_seed, &c0, prime_seed, prime_gen_counter);
+	/* Step 15 if FAILURE is returned, return (FAILURE, 0, 0, 0). */
+	if (rv != SECSuccess) {
+	    goto cleanup;
+	}
+	/* Steps 16-34 */
+	rv = makePrimefromPrimesShawneTaylor(hashtype,length, &c0, &one,
+		prime, prime_seed, prime_gen_counter);
+	goto cleanup; /* we're done, one way or the other */
+    }
+    /* Step 3 prime_seed = input_seed */
+    CHECK_SEC_OK(SECITEM_CopyItem(NULL, prime_seed, input_seed));
+    /* Step 4 prime_gen_count = 0 */
+    *prime_gen_counter = 0;
+
+step_5:
+    /* Step 5 c = Hash(prime_seed) xor Hash(prime_seed+1). */
+    CHECK_SEC_OK(HASH_HashBuf(hashtype, x, prime_seed->data, prime_seed->len) );
+    CHECK_SEC_OK(addToSeedThenHash(hashtype, prime_seed, 1, 
+					MAX_ST_SEED_BITS, &x[hashlen]) );
+    for (i=0; i < hashlen; i++) {
+	x[i] = x[i] ^ x[i+hashlen];
+    }
+    /* Step 6 c = 2**length-1 + c mod 2**length-1 */
+    /*   This step mathematically sets the high bit and clears out
+    **  all the other bits higher than length. Right now c is stored
+    **  in the x array, MSB first. The above formula gives us a c which
+    **  is length bytes long and has the high bit set. We also know that
+    **  length < outlen since the smallest outlen is 160 bits and the largest
+    **  length at this point is 32 bits. So first we find the offset in bytes
+    **  into the array where the high bit is.
+    */
+    offset = (outlen - length)/BITS_PER_BYTE;
+    /* now we want to set the 'high bit'. We have to calculate this since 
+     * length may not be a multiple of 8.*/
+    bit = 1 << ((length-1) & 0x7); /* select the proper bit in the byte */
+    /* we need to zero out the rest of the bits  in the byte above */
+    mask = (bit-1);
+    /* now we set it */
+    x[offset] = (mask & x[offset]) | bit;
+    /* Step 7 c = c*floor(c/2) + 1 */
+    /* set the low bit. much easier to find (the end of the array) */
+    x[hashlen-1] |= 1;
+    /* now that we've set our bits, we can create our candidate "c" */
+    CHECK_MPI_OK( mp_read_unsigned_octets(&c, &x[offset], hashlen-offset) );
+    /* Step 8 prime_gen_counter = prime_gen_counter + 1 */
+    (*prime_gen_counter)++;
+    /* Step 9 prime_seed = prime_seed + 2 */
+    CHECK_SEC_OK(addToSeed(prime_seed, 2, MAX_ST_SEED_BITS, prime_seed));
+    /* Step 10 Perform deterministic primality test on c. For example, since
+    ** c is small, it's primality can be tested by trial division, See
+    ** See Appendic C.7.
+    **
+    ** We in fact test with trial division. mpi has a built int trial divider
+    ** that divides all divisors up to 2^16.
+    */
+    if (prime_tab[prime_tab_size-1] < 0xFFF1) {
+ 	/* we aren't testing all the primes between 0 and 2^16, we really
+	 * can't use this construction. Just fail. */
+	rv = SECFailure;
+	goto cleanup;
+    }
+    dummy = prime_tab_size;
+    err = mpp_divis_primes(&c, &dummy);
+    /* Step 11 if c is prime then */
+    if (err == MP_NO) {
+	/* Step 11.1 prime = c */
+	CHECK_MPI_OK( mp_copy(&c, prime) );
+	/* Step 11.2 return SUCCESS prime, prime_seed, prime_gen_counter */
+	err = MP_OKAY;
+	rv = SECSuccess;
+	goto cleanup;
+    } else if (err != MP_YES) {
+	goto cleanup;  /* function failed, bail out */
+    } else {
+	/* reset mp_err */
+	err = MP_OKAY;
+    }
+    /*
+    ** Step 12 if (prime_gen_counter > (4*len)) 
+    ** then return (FAILURE, 0, 0, 0)) 
+    ** Step 13 goto step 5
+    */
+    if (*prime_gen_counter <= (4*length)) {
+	goto step_5;
+    }
+    /* if (prime_gencont > 4*length), fall through to failure */
+    rv = SECFailure; /* really is already set, but paranoia is good */
+	
+cleanup:
+    mp_clear(&c);
+    mp_clear(&c0);
+    mp_clear(&one);
+    if (err) {
+	MP_TO_SEC_ERROR(err);
+	rv = SECFailure;
+    }
+    if (rv == SECFailure) {
+	mp_zero(prime);
+	if (prime_seed->data) {
+	    SECITEM_FreeItem(prime_seed, PR_FALSE);
+	}
+	*prime_gen_counter = 0;
+    }
+    return rv;
+}
+
+
+/*
+ * Find a Q and algorithm from Seed.
+ */
+static SECStatus
+findQfromSeed(
+      unsigned int  L,          /* input.  Length of p in bits. */
+      unsigned int  N,          /* input.  Length of q in bits. */
+      unsigned int  g,          /* input.  Length of seed in bits. */
+const SECItem   *   seed,       /* input.  */
+      mp_int    *   Q,          /* input. */
+      mp_int    *   Q_,         /* output. */
+      int       *  qseed_len,   /* output */
+      HASH_HashType *hashtypePtr,  /* output. Hash uses */
+      pqgGenType    *typePtr)      /* output. Generation Type used */
+{
+    HASH_HashType hashtype;
+    SECItem  firstseed = { 0, 0, 0 };
+    SECItem  qseed = { 0, 0, 0 };
+    SECStatus rv;
+
+    *qseed_len = 0; /* only set if FIPS186_3_ST_TYPE */
+
+    /* handle legacy small DSA first can only be FIPS186_1_TYPE */
+    if (L < 1024) {
+	rv =makeQfromSeed(g,seed,Q_);
+	if ((rv == SECSuccess) && (mp_cmp(Q,Q_) == 0)) {
+	    *hashtypePtr = HASH_AlgSHA1;
+	    *typePtr = FIPS186_1_TYPE;
+	    return SECSuccess;
+	}
+	return SECFailure;
+    } 
+    /* 1024 could use FIPS186_1 or FIPS186_3 algorithms, we need to try 
+     * them both */
+    if (L == 1024) {
+	rv = makeQfromSeed(g,seed,Q_);
+	if (rv == SECSuccess) {
+	    if (mp_cmp(Q,Q_) == 0) {
+		*hashtypePtr = HASH_AlgSHA1;
+		*typePtr = FIPS186_1_TYPE;
+		return SECSuccess;
+	    }
+	}
+	/* fall through for FIPS186_3 types */
+    }
+    /* at this point we know we aren't using FIPS186_1, start trying FIPS186_3
+     * with appropriate hash types */
+    for (hashtype = getFirstHash(L,N); hashtype != HASH_AlgTOTAL; 
+					hashtype=getNextHash(hashtype)) {
+	rv = makeQ2fromSeed(hashtype, N, seed, Q_);
+	if (rv != SECSuccess) {
+	    continue;
+	}
+	if (mp_cmp(Q,Q_) == 0) {
+	    *hashtypePtr = hashtype;
+	    *typePtr = FIPS186_3_TYPE;
+	    return SECSuccess;
+	}
+    }
+    /*
+     * OK finally try FIPS186_3 Shawne-Taylor 
+     */
+    firstseed = *seed;
+    firstseed.len = seed->len/3;
+    for (hashtype = getFirstHash(L,N); hashtype != HASH_AlgTOTAL; 
+					hashtype=getNextHash(hashtype)) {
+	int count;
+
+	rv = makePrimefromSeedShawneTaylor(hashtype, N, &firstseed, Q_, 
+		&qseed, &count);
+	if (rv != SECSuccess) {
+	    continue;
+	}
+	if (mp_cmp(Q,Q_) == 0) {
+	    /* check qseed as well... */
+	    int offset = seed->len - qseed.len;
+	    if ((offset < 0) || 
+	       (PORT_Memcmp(&seed->data[offset],qseed.data,qseed.len) != 0)) {
+		/* we found q, but the seeds don't match. This isn't an
+		 * accident, someone has been tweeking with the seeds, just
+		 * fail a this point. */
+		SECITEM_FreeItem(&qseed,PR_FALSE);
+		return SECFailure;
+	    }
+	    *qseed_len = qseed.len;
+	    *hashtypePtr = hashtype;
+	    *typePtr = FIPS186_3_ST_TYPE;
+	    SECITEM_FreeItem(&qseed, PR_FALSE);
+	    return SECSuccess;
+	}
+	SECITEM_FreeItem(&qseed, PR_FALSE);
+    }
+    /* no hash algorithms found which match seed to Q, fail */
+    return SECFailure;
+}
+	
+
+
+/*
+**  Perform steps 7, 8 and 9 of FIPS 186, appendix 2.2.
+**  which are the same as steps 11.1-11.5 of FIPS 186-2, App A.1.1.2
 **  Generate P from Q, seed, L, and offset.
 */
 static SECStatus
 makePfromQandSeed(
+      HASH_HashType hashtype,	/* selected Hashing algorithm */
       unsigned int  L,          /* Length of P in bits.  Per FIPS 186. */
-      unsigned int  offset,     /* Per FIPS 186, appendix 2.2. */
-      unsigned int  g,          /* input.  Length of seed in bits. */
+      unsigned int  N,          /* Length of Q in bits.  Per FIPS 186. */
+      unsigned int  offset,     /* Per FIPS 186, App 2.2. & 186-3 App A.1.1.2 */
+      unsigned int  seedlen,    /* input. Length of seed in bits. (g in 186-1)*/
 const SECItem   *   seed,       /* input.  */
 const mp_int    *   Q,          /* input.  */
       mp_int    *   P)          /* output. */
 {
-    unsigned int  k;            /* Per FIPS 186, appendix 2.2. */
+    unsigned int  j;            /* Per FIPS 186-3 App. A.1.1.2  (k in 186-1)*/
     unsigned int  n;            /* Per FIPS 186, appendix 2.2. */
     mp_digit      b;            /* Per FIPS 186, appendix 2.2. */
-    unsigned char V_k[SHA1_LENGTH];
+    unsigned int outlen;        /* Per FIPS 186-3 App. A.1.1.2 */
+    unsigned int hashlen;       /* outlen in bytes */
+    unsigned char V_j[HASH_LENGTH_MAX];
     mp_int        W, X, c, twoQ, V_n, tmp;
     mp_err    err = MP_OKAY;
     SECStatus rv  = SECSuccess;
     /* Initialize bignums */
     MP_DIGITS(&W)     = 0;
     MP_DIGITS(&X)     = 0;
     MP_DIGITS(&c)     = 0;
     MP_DIGITS(&twoQ)  = 0;
     MP_DIGITS(&V_n)   = 0;
     MP_DIGITS(&tmp)   = 0;
     CHECK_MPI_OK( mp_init(&W)    );
     CHECK_MPI_OK( mp_init(&X)    );
     CHECK_MPI_OK( mp_init(&c)    );
     CHECK_MPI_OK( mp_init(&twoQ) );
     CHECK_MPI_OK( mp_init(&tmp)  );
     CHECK_MPI_OK( mp_init(&V_n)  );
-    /* L - 1 = n*160 + b */
-    n = (L - 1) / BITS_IN_Q;
-    b = (L - 1) % BITS_IN_Q;
+
+    hashlen = HASH_ResultLen(hashtype);
+    outlen = hashlen*BITS_PER_BYTE; 
+
+    /* L - 1 = n*outlen + b */
+    n = (L - 1) / outlen;
+    b = (L - 1) % outlen;
+
     /* ******************************************************************
-    ** Step 7.
-    **  "for k = 0 ... n let
-    **           V_k = SHA[(SEED + offset + k) mod 2**g]."
+    ** Step 11.1 (Step 7 in 186-1)
+    **  "for j = 0 ... n let
+    **           V_j = SHA[(SEED + offset + j) mod 2**seedlen]."
     **
-    ** Step 8.
-    **  "Let W be the integer 
-    **    W = V_0 + (V_1 * 2**160) + ... + (V_n-1 * 2**((n-1)*160)) 
-    **         + ((V_n mod 2**b) * 2**(n*160))
+    ** Step 11.2 (Step 8 in 186-1)
+    **   "W = V_0 + (V_1 * 2**outlen) + ... + (V_n-1 * 2**((n-1)*outlen)) 
+    **         + ((V_n mod 2**b) * 2**(n*outlen))
     */
-    for (k=0; k<n; ++k) { /* Do the first n terms of V_k */
-	/* Do step 7 for iteration k.
-	** V_k = SHA[(seed + offset + k) mod 2**g]
+    for (j=0; j<n; ++j) { /* Do the first n terms of V_j */
+	/* Do step 11.1 for iteration j.
+	** V_j = HASH[(seed + offset + j) mod 2**g]
 	*/
-	CHECK_SEC_OK( addToSeedThenSHA(seed, offset + k, g, V_k) );
-	/* Do step 8 for iteration k.
-	** W += V_k * 2**(k*160)
+	CHECK_SEC_OK( addToSeedThenHash(hashtype,seed,offset+j, seedlen, V_j) );
+	/* Do step 11.2 for iteration j.
+	** W += V_j * 2**(j*outlen)
 	*/
-	OCTETS_TO_MPINT(V_k, &tmp, SHA1_LENGTH);      /* get bignum V_k     */
-	CHECK_MPI_OK( mpl_lsh(&tmp, &tmp, k*160) );   /* tmp = V_k << k*160 */
+	OCTETS_TO_MPINT(V_j, &tmp, hashlen);          /* get bignum V_j     */
+	CHECK_MPI_OK( mpl_lsh(&tmp, &tmp, j*outlen) );/* tmp=V_j << j*outlen */
 	CHECK_MPI_OK( mp_add(&W, &tmp, &W) );         /* W += tmp           */
     }
-    /* Step 8, continued.
-    **   [W += ((V_n mod 2**b) * 2**(n*160))] 
+    /* Step 11.2, continued.
+    **   [W += ((V_n mod 2**b) * 2**(n*outlen))] 
     */
-    CHECK_SEC_OK( addToSeedThenSHA(seed, offset + n, g, V_k) );
-    OCTETS_TO_MPINT(V_k, &V_n, SHA1_LENGTH);          /* get bignum V_n     */
-    CHECK_MPI_OK( mp_div_2d(&V_n, b, NULL, &tmp) );   /* tmp = V_n mod 2**b */
-    CHECK_MPI_OK( mpl_lsh(&tmp, &tmp, n*160) );       /* tmp = tmp << n*160 */
-    CHECK_MPI_OK( mp_add(&W, &tmp, &W) );             /* W += tmp           */
-    /* Step 8, continued.
-    ** "and let X = W + 2**(L-1).
+    CHECK_SEC_OK( addToSeedThenHash(hashtype, seed, offset + n, seedlen, V_j) );
+    OCTETS_TO_MPINT(V_j, &V_n, hashlen);          /* get bignum V_n     */
+    CHECK_MPI_OK( mp_div_2d(&V_n, b, NULL, &tmp) ); /* tmp = V_n mod 2**b */
+    CHECK_MPI_OK( mpl_lsh(&tmp, &tmp, n*outlen) );  /* tmp = tmp << n*outlen */
+    CHECK_MPI_OK( mp_add(&W, &tmp, &W) );           /* W += tmp           */
+    /* Step 11.3, (Step 8 in 186-1) 
+    ** "X = W + 2**(L-1).
     **  Note that 0 <= W < 2**(L-1) and hence 2**(L-1) <= X < 2**L."
     */
     CHECK_MPI_OK( mpl_set_bit(&X, (mp_size)(L-1), 1) );    /* X = 2**(L-1) */
     CHECK_MPI_OK( mp_add(&X, &W, &X) );                    /* X += W       */
     /*************************************************************
-    ** Step 9.
-    ** "Let c = X mod 2q  and set p = X - (c - 1).
-    **  Note that p is congruent to 1 mod 2q."
+    ** Step 11.4. (Step 9 in 186-1)
+    ** "c = X mod 2q"
     */
     CHECK_MPI_OK( mp_mul_2(Q, &twoQ) );                    /* 2q           */
     CHECK_MPI_OK( mp_mod(&X, &twoQ, &c) );                 /* c = X mod 2q */
+    /*************************************************************
+    ** Step 11.5. (Step 9 in 186-1)
+    ** "p = X - (c - 1).
+    **  Note that p is congruent to 1 mod 2q."
+    */
     CHECK_MPI_OK( mp_sub_d(&c, 1, &c) );                   /* c -= 1       */
     CHECK_MPI_OK( mp_sub(&X, &c, P) );                     /* P = X - c    */
 cleanup:
     mp_clear(&W);
     mp_clear(&X);
     mp_clear(&c);
     mp_clear(&twoQ);
     mp_clear(&V_n);
@@ -328,57 +1071,141 @@ cleanup:
     mp_clear(&pm1);
     if (err) {
 	MP_TO_SEC_ERROR(err);
 	rv = SECFailure;
     }
     return rv;
 }
 
-SECStatus
-PQG_ParamGen(unsigned int j, PQGParams **pParams, PQGVerify **pVfy)
+/*
+** Generate G from seed, index, P, and Q.
+*/
+static SECStatus
+makeGfromIndex(HASH_HashType hashtype,
+		const mp_int *P,	/* input.  */
+           	const mp_int *Q,	/* input.  */
+                const SECItem *seed,	/* input. */
+		unsigned char index,	/* input. */
+		mp_int *G)		/* input/output */
 {
-    unsigned int L;            /* Length of P in bits.  Per FIPS 186. */
-    unsigned int seedBytes;
+    mp_int e, pm1, W;
+    unsigned int count;
+    unsigned char data[HASH_LENGTH_MAX];
+    unsigned int len;
+    mp_err err = MP_OKAY;
+    SECStatus rv = SECSuccess;
+    const SECHashObject *hashobj;
+    void *hashcx = NULL;
+
+    MP_DIGITS(&e) = 0;
+    MP_DIGITS(&pm1) = 0;
+    MP_DIGITS(&W) = 0;
+    CHECK_MPI_OK( mp_init(&e) );
+    CHECK_MPI_OK( mp_init(&pm1) );
+    CHECK_MPI_OK( mp_init(&W) );
+
+    /* initialize our hash stuff */
+    hashobj = HASH_GetRawHashObject(hashtype);
+    if (hashobj == NULL) {
+	/* shouldn't happen */
+	PORT_SetError(SEC_ERROR_LIBRARY_FAILURE);
+	rv = SECFailure;
+	goto cleanup;
+    }
+    hashcx = hashobj->create();
+    if (hashcx == NULL) {
+	rv = SECFailure;
+	goto cleanup;
+    }
 
-    if (j > 8 || !pParams || !pVfy) {
-	PORT_SetError(SEC_ERROR_INVALID_ARGS);
-        return SECFailure;
+    CHECK_MPI_OK( mp_sub_d(P, 1, &pm1) );        /* P - 1            */
+    /* Step 3 e = (p-1)/q */
+    CHECK_MPI_OK( mp_div(&pm1, Q, &e, NULL) );  /* e = (P-1)/Q      */
+    /* Steps 4, 5, and 6 */
+    /* count is a 16 bit value in the spec. We actually represent count
+     * as more than 16 bits so we can easily detect the 16 bit overflow */
+#define MAX_COUNT 0x10000
+    for (count = 1; count < MAX_COUNT; count++) {
+	/* step 7
+	 * U = domain_param_seed || "ggen" || index || count
+         * step 8
+	 * W = HASH(U)
+	 */
+	hashobj->begin(hashcx);
+	hashobj->update(hashcx,seed->data,seed->len);
+	hashobj->update(hashcx, (unsigned char *)"ggen", 4);
+	hashobj->update(hashcx,&index, 1);
+	data[0] = (count >> 8) & 0xff;
+	data[1] = count & 0xff;
+	hashobj->update(hashcx, data, 2);
+	hashobj->end(hashcx, data, &len, sizeof(data));
+	OCTETS_TO_MPINT(data, &W, len);
+	/* step 9. g = W**e mod p */
+	CHECK_MPI_OK( mp_exptmod(&W, &e, P, G) );
+	/* step 10. if (g < 2) then goto step 5 */
+	/* NOTE: this weird construct is to keep the flow according to the spec.
+	 * the continue puts us back to step 5 of the for loop */
+    	if (mp_cmp_d(G, 2) < 0) {
+	     continue;
+	}
+	break; /* step 11 follows step 10 if the test condition is false */
     }
-    L = 512 + (j * 64);         /* bits in P */
-    seedBytes = L/8;
-    return PQG_ParamGenSeedLen(j, seedBytes, pParams, pVfy);
+    if (count >= MAX_COUNT) { 
+	rv = SECFailure; /* last part of step 6 */
+    }
+    /* step 11. 
+     * return valid G */
+cleanup:
+    PORT_Memset(data, 0, sizeof(data));
+    if (hashcx) {
+	hashobj->destroy(hashcx, PR_TRUE);
+    }
+    mp_clear(&e);
+    mp_clear(&pm1);
+    mp_clear(&W);
+    if (err) {
+	MP_TO_SEC_ERROR(err);
+	rv = SECFailure;
+    }
+    return rv;
 }
 
 /* This code uses labels and gotos, so that it can follow the numbered
-** steps in the algorithms from FIPS 186 appendix 2.2 very closely,
+** steps in the algorithms from FIPS 186-3 appendix A.1.1.2 very closely,
 ** and so that the correctness of this code can be easily verified.
 ** So, please forgive the ugly c code.
 **/
-SECStatus
-PQG_ParamGenSeedLen(unsigned int j, unsigned int seedBytes,
-                    PQGParams **pParams, PQGVerify **pVfy)
+static SECStatus
+pqg_ParamGen(unsigned int L, unsigned int N, pqgGenType type,
+	 unsigned int seedBytes, PQGParams **pParams, PQGVerify **pVfy)
 {
-    unsigned int  L;        /* Length of P in bits.  Per FIPS 186. */
-    unsigned int  n;        /* Per FIPS 186, appendix 2.2. */
-    unsigned int  b;        /* Per FIPS 186, appendix 2.2. */
-    unsigned int  g;        /* Per FIPS 186, appendix 2.2. */
-    unsigned int  counter;  /* Per FIPS 186, appendix 2.2. */
-    unsigned int  offset;   /* Per FIPS 186, appendix 2.2. */
-    SECItem      *seed;     /* Per FIPS 186, appendix 2.2. */
+    unsigned int  n;        /* Per FIPS 186, app 2.2. 186-3 app A.1.1.2 */
+    unsigned int  b;        /* Per FIPS 186, app 2.2. 186-3 app A.1.1.2 */
+    unsigned int  seedlen;  /* Per FIPS 186-3 app A.1.1.2  (was 'g' 186-1)*/
+    unsigned int  counter;  /* Per FIPS 186, app 2.2. 186-3 app A.1.1.2 */
+    unsigned int  offset;   /* Per FIPS 186, app 2.2. 186-3 app A.1.1.2 */
+    unsigned int  outlen;   /* Per FIPS 186-3, appendix A.1.1.2. */
+    unsigned int  maxCount;
+    HASH_HashType hashtype;
+    SECItem      *seed;     /* Per FIPS 186, app 2.2. 186-3 app A.1.1.2 */
     PRArenaPool  *arena  = NULL;
     PQGParams    *params = NULL;
     PQGVerify    *verify = NULL;
     PRBool passed;
     SECItem hit = { 0, 0, 0 };
     mp_int P, Q, G, H, l;
     mp_err    err = MP_OKAY;
     SECStatus rv  = SECFailure;
     int iterations = 0;
-    if (j > 8 || seedBytes < 20 || !pParams || !pVfy) {
+
+
+    /* Step 1. L and N already checked by caller*/
+    /* Step 2. if (seedlen < N) return INVALID; */
+    if (seedBytes < N/BITS_PER_BYTE || !pParams || !pVfy) {
 	PORT_SetError(SEC_ERROR_INVALID_ARGS);
 	return SECFailure;
     }
     /* Initialize an arena for the params. */
     arena = PORT_NewArena(NSS_FREEBL_DEFAULT_CHUNKSIZE);
     if (!arena) {
 	PORT_SetError(SEC_ERROR_NO_MEMORY);
 	return SECFailure;
@@ -413,129 +1240,171 @@ PQG_ParamGenSeedLen(unsigned int j, unsi
     MP_DIGITS(&G) = 0;
     MP_DIGITS(&H) = 0;
     MP_DIGITS(&l) = 0;
     CHECK_MPI_OK( mp_init(&P) );
     CHECK_MPI_OK( mp_init(&Q) );
     CHECK_MPI_OK( mp_init(&G) );
     CHECK_MPI_OK( mp_init(&H) );
     CHECK_MPI_OK( mp_init(&l) );
-    /* Compute lengths. */
-    L = 512 + (j * 64);               /* bits in P */
-    n = (L - 1) / BITS_IN_Q;          /* BITS_IN_Q is 160 */  
-    b = (L - 1) % BITS_IN_Q;
-    g = seedBytes * BITS_PER_BYTE;    /* bits in seed, NOT G of PQG. */
-step_1:
+
+    /* Select Hash and Compute lengths. */
+    /* getFirstHash gives us the smallest acceptable hash for this key
+     * strength */
+    hashtype = getFirstHash(L,N);
+    outlen = HASH_ResultLen(hashtype)*BITS_PER_BYTE;
+
+    /* Step 3: n = Ceil(L/outlen)-1; (same as n = Floor((L-1)/outlen)) */
+    n = (L - 1) / outlen; 
+    /* Step 4: b = L -1 - (n*outlen); (same as n = (L-1) mod outlen) */
+    b = (L - 1) % outlen;
+    seedlen = seedBytes * BITS_PER_BYTE;    /* bits in seed */
+step_5:
     /* ******************************************************************
-    ** Step 1.
-    ** "Choose an abitrary sequence of at least 160 bits and call it SEED.
+    ** Step 5. (Step 1 in 186-1)
+    ** "Choose an abitrary sequence of at least N bits and call it SEED.
     **  Let g be the length of SEED in bits."
     */
     if (++iterations > MAX_ITERATIONS) {        /* give up after a while */
         PORT_SetError(SEC_ERROR_NEED_RANDOM);
         goto cleanup;
     }
     seed->len = seedBytes;
     CHECK_SEC_OK( getPQseed(seed, verify->arena) );
     /* ******************************************************************
-    ** Step 2.
-    ** "Compute U = SHA[SEED] XOR SHA[(SEED+1) mod 2**g]."
+    ** Step 6. (Step 2 in 186-1)
     **
-    ** Step 3.
+    ** "Compute U = SHA[SEED] XOR SHA[(SEED+1) mod 2**g].  (186-1)"
+    ** "Compute U = HASH[SEED] 2**(N-1).  (186-3)"
+    **
+    ** Step 7. (Step 3 in 186-1)
     ** "Form Q from U by setting the most signficant bit (the 2**159 bit) 
     **  and the least signficant bit to 1.  In terms of boolean operations,
-    **  Q = U OR 2**159 OR 1.  Note that 2**159 < Q < 2**160."
+    **  Q = U OR 2**159 OR 1.  Note that 2**159 < Q < 2**160. (186-1)"
+    **
+    ** "q = 2**(N-1) + U + 1 - (U mod 2) (186-3)
+    **
+    ** Note: Both formulations are the same for U < 2**(N-1) and N=160
     */
-    CHECK_SEC_OK( makeQfromSeed(g, seed, &Q) );
+    if (type == FIPS186_1_TYPE) {
+	CHECK_SEC_OK( makeQfromSeed(seedlen, seed, &Q) );
+    } else {
+	CHECK_SEC_OK( makeQ2fromSeed(hashtype, N, seed, &Q) );
+    }
     /* ******************************************************************
-    ** Step 4.
+    ** Step 8. (Step 4 in 186-1)
     ** "Use a robust primality testing algorithm to test whether q is prime."
     **
     ** Appendix 2.1 states that a Rabin test with at least 50 iterations
     ** "will give an acceptable probability of error."
     */
     /*CHECK_SEC_OK( prm_RabinTest(&Q, &passed) );*/
-    err = mpp_pprime(&Q, PQG_Q_PRIMALITY_TESTS);
+    err = mpp_pprime(&Q, prime_testcount_q(L,N));
     passed = (err == MP_YES) ? SECSuccess : SECFailure;
     /* ******************************************************************
-    ** Step 5. "If q is not prime, goto step 1."
+    ** Step 9. (Step 5 in 186-1) "If q is not prime, goto step 5 (1 in 186-1)."
     */
     if (passed != SECSuccess)
-        goto step_1;
+        goto step_5;
     /* ******************************************************************
-    ** Step 6. "Let counter = 0 and offset = 2."
+    ** Step 10. 
+    **      offset = 1;
+    **(     Step 6b 186-1)"Let counter = 0 and offset = 2."
     */
-    counter = 0;
-    offset  = 2;
-step_7:
-    /* ******************************************************************
-    ** Step 7.
-    ** "for k = 0 ... n let
-    **          V_k = SHA[(SEED + offset + k) mod 2**g]."
+    offset = (type == FIPS186_1_TYPE) ? 2 : 1;
+    /*
+    ** Step 11. (Step 6a,13a,14 in 186-1)
+    **  For counter - 0 to (4L-1) do
     **
-    ** Step 8.
-    ** "Let W be the sum of  (V_k * 2**(k*160)) for k = 0 ... n
-    **  and let X = W + 2**(L-1).
-    **  Note that 0 <= W < 2**(L-1) and hence 2**(L-1) <= X < 2**L."
-    **
-    ** Step 9.
-    ** "Let c = X mod 2q  and set p = X - (c - 1).
-    **  Note that p is congruent to 1 mod 2q."
-    */
-    CHECK_SEC_OK( makePfromQandSeed(L, offset, g, seed, &Q, &P) );
-    /*************************************************************
-    ** Step 10.
-    ** "if p < 2**(L-1), then goto step 13."
-    */
-    CHECK_MPI_OK( mpl_set_bit(&l, (mp_size)(L-1), 1) ); /* l = 2**(L-1) */
-    if (mp_cmp(&P, &l) < 0)
-        goto step_13;
-    /************************************************************
-    ** Step 11.
-    ** "Perform a robust primality test on p."
     */
-    /*CHECK_SEC_OK( prm_RabinTest(&P, &passed) );*/
-    err = mpp_pprime(&P, PQG_P_PRIMALITY_TESTS);
-    passed = (err == MP_YES) ? SECSuccess : SECFailure;
+    maxCount = L >= 1024 ? (4*L - 1) : 4095;
+    for (counter = 0; counter <= maxCount; counter++) {
+	/* ******************************************************************
+	** Step 11.1  (Step 7 in 186-1)
+	** "for j = 0 ... n let
+	**          V_j = HASH[(SEED + offset + j) mod 2**seedlen]."
+	**
+	** Step 11.2 (Step 8 in 186-1)
+	** "W = V_0 + V_1*2**outlen+...+ V_n-1 * 2**((n-1)*outlen) + 
+	**                               ((Vn* mod 2**b)*2**(n*outlen))"
+	** Step 11.3 (Step 8 in 186-1)
+	** "X = W + 2**(L-1)
+	**  Note that 0 <= W < 2**(L-1) and hence 2**(L-1) <= X < 2**L."
+	**
+	** Step 11.4 (Step 9 in 186-1).
+	** "c = X mod 2q"
+	**
+	** Step 11.5 (Step 9 in 186-1).
+	** " p = X - (c - 1).
+	**  Note that p is congruent to 1 mod 2q."
+	*/
+	CHECK_SEC_OK( makePfromQandSeed(hashtype, L, N, offset, seedlen, 
+					seed, &Q, &P) );
+	/*************************************************************
+	** Step 11.6. (Step 10 in 186-1)
+	** "if p < 2**(L-1), then goto step 11.9. (step 13 in 186-1)"
+	*/
+	CHECK_MPI_OK( mpl_set_bit(&l, (mp_size)(L-1), 1) ); /* l = 2**(L-1) */
+	if (mp_cmp(&P, &l) < 0)
+            goto step_11_9;
+	/************************************************************
+	** Step 11.7 (step 11 in 186-1)
+	** "Perform a robust primality test on p."
+	*/
+	/*CHECK_SEC_OK( prm_RabinTest(&P, &passed) );*/
+	err = mpp_pprime(&P, prime_testcount_p(L, N));
+	passed = (err == MP_YES) ? SECSuccess : SECFailure;
+	/* ******************************************************************
+	** Step 11.8. "If p is determined to be primed return VALID 
+        ** values of p, q, seed and counter."
+	*/
+	if (passed == SECSuccess)
+	    break;
+step_11_9:
+	/* ******************************************************************
+	** Step 11.9.  "offset = offset + n + 1."
+	*/
+	offset += n + 1;
+    }
     /* ******************************************************************
-    ** Step 12. "If p passes the test performed in step 11, go to step 15."
-    */
-    if (passed == SECSuccess)
-        goto step_15;
-step_13:
-    /* ******************************************************************
-    ** Step 13.  "Let counter = counter + 1 and offset = offset + n + 1."
-    */
-    counter++;
-    offset += n + 1;
-    /* ******************************************************************
-    ** Step 14.  "If counter >= 4096 goto step 1, otherwise go to step 7."
+    ** Step 12.  "goto step 5."
+    **
+    ** NOTE: if counter <= maxCount, then we exited the loop at Step 11.8
+    ** and now need to return p,q, seed, and counter.
     */
-    if (counter >= 4096)
-        goto step_1;
-    goto step_7;
-step_15:
+    if (counter > maxCount) 
+	     goto step_5;
     /* ******************************************************************
-    ** Step 15.  
-    ** "Save the value of SEED and the value of counter for use
-    **  in certifying the proper generation of p and q."
+    ** returning p, q, seed and counter
     */
-    /* Generate h. */
-    SECITEM_AllocItem(NULL, &hit, L/8); /* h is no longer than p */
-    if (!hit.data) goto cleanup;
-    do {
-	/* loop generate h until 1<h<p-1 and (h**[(p-1)/q])mod p > 1 */
-	CHECK_SEC_OK( generate_h_candidate(&hit, &H) );
-        CHECK_SEC_OK( makeGfromH(&P, &Q, &H, &G, &passed) );
-    } while (passed != PR_TRUE);
+    if (type == FIPS186_1_TYPE) {
+	/* Generate g, This is called the "Unverifiable Generation of g
+	 * in FIPA186-3 Appedix A.2.1. For compatibility we maintain
+	 * this version of the code */
+	SECITEM_AllocItem(NULL, &hit, L/8); /* h is no longer than p */
+	if (!hit.data) goto cleanup;
+ 	do {
+	    /* loop generate h until 1<h<p-1 and (h**[(p-1)/q])mod p > 1 */
+	    CHECK_SEC_OK( generate_h_candidate(&hit, &H) );
+            CHECK_SEC_OK( makeGfromH(&P, &Q, &H, &G, &passed) );
+	} while (passed != PR_TRUE);
+        MPINT_TO_SECITEM(&H, &verify->h,        verify->arena);
+    } else {
+	unsigned char index = 1; /* default to 1 */
+	verify->h.data = (unsigned char *)PORT_ArenaZAlloc(verify->arena, 1);
+	if (verify->h.data == NULL) { goto cleanup; }
+	verify->h.len = 1;
+	verify->h.data[0] = index;
+	/* Generate g, using the FIPS 186-3 Appendix A.23 */
+	CHECK_SEC_OK(makeGfromIndex(hashtype, &P, &Q, seed, index, &G) );
+    }
     /* All generation is done.  Now, save the PQG params.  */
     MPINT_TO_SECITEM(&P, &params->prime,    params->arena);
     MPINT_TO_SECITEM(&Q, &params->subPrime, params->arena);
     MPINT_TO_SECITEM(&G, &params->base,     params->arena);
-    MPINT_TO_SECITEM(&H, &verify->h,        verify->arena);
     verify->counter = counter;
     *pParams = params;
     *pVfy = verify;
 cleanup:
     mp_clear(&P);
     mp_clear(&Q);
     mp_clear(&G);
     mp_clear(&H);
@@ -549,103 +1418,288 @@ cleanup:
 	PORT_FreeArena(verify->arena, PR_TRUE);
     }
     if (hit.data) {
         SECITEM_FreeItem(&hit, PR_FALSE);
     }
     return rv;
 }
 
+SECStatus
+PQG_ParamGen(unsigned int j, PQGParams **pParams, PQGVerify **pVfy)
+{
+    unsigned int L;            /* Length of P in bits.  Per FIPS 186. */
+    unsigned int seedBytes;
+
+    if (j > 8 || !pParams || !pVfy) {
+	PORT_SetError(SEC_ERROR_INVALID_ARGS);
+        return SECFailure;
+    }
+    L = 512 + (j * 64);         /* bits in P */
+    seedBytes = L/8;
+    return pqg_ParamGen(L, DSA1_Q_BITS, FIPS186_1_TYPE, seedBytes, 
+                        pParams, pVfy);
+}
+
+SECStatus
+PQG_ParamGenSeedLen(unsigned int j, unsigned int seedBytes,
+                    PQGParams **pParams, PQGVerify **pVfy)
+{
+    unsigned int L;            /* Length of P in bits.  Per FIPS 186. */
+
+    if (j > 8 || !pParams || !pVfy) {
+	PORT_SetError(SEC_ERROR_INVALID_ARGS);
+        return SECFailure;
+    }
+    L = 512 + (j * 64);         /* bits in P */
+    return pqg_ParamGen(L, DSA1_Q_BITS, FIPS186_1_TYPE, seedBytes,
+                        pParams, pVfy);
+}
+
+SECStatus
+PQG_ParamGenV2(unsigned int L, unsigned int N, unsigned int seedBytes,
+                    PQGParams **pParams, PQGVerify **pVfy)
+{
+    if (pqg_validate_dsa2(L,N) != SECSuccess) {
+	/* error code already set */
+	return SECFailure;
+    }
+    return pqg_ParamGen(L, N, FIPS186_3_TYPE, seedBytes, pParams, pVfy);
+}
+
+
+/*
+ * verify can use vfy structures returned from either FIPS186-1 or
+ * FIPS186-2, and can handle differences in selected Hash functions to
+ * generate the parameters.
+ */
 SECStatus   
 PQG_VerifyParams(const PQGParams *params, 
                  const PQGVerify *vfy, SECStatus *result)
 {
     SECStatus rv = SECSuccess;
-    int passed;
-    unsigned int g, n, L, offset;
-    mp_int P, Q, G, P_, Q_, G_, r, h;
+    unsigned int g, n, L, N, offset, outlen;
+    mp_int p0, P, Q, G, P_, Q_, G_, r, h;
     mp_err err = MP_OKAY;
     int j;
+    unsigned int counter_max = 0; /* handle legacy L < 1024 */
+    int qseed_len;
+    SECItem pseed_ = {0, 0, 0};
+    HASH_HashType hashtype;
+    pqgGenType type;
+
 #define CHECKPARAM(cond)      \
     if (!(cond)) {            \
 	*result = SECFailure; \
 	goto cleanup;         \
     }
     if (!params || !vfy || !result) {
 	PORT_SetError(SEC_ERROR_INVALID_ARGS);
 	return SECFailure;
     }
+    /* always need at least p, q, and seed for any meaningful check */
+    if ((params->prime.len == 0) || (params->subPrime.len == 0) ||
+        (vfy->seed.len == 0)) {
+	PORT_SetError(SEC_ERROR_INVALID_ARGS);
+	return SECFailure;
+    }
+    /* we want to either check PQ or G or both. If we don't have G, make
+     * sure we have count so we can check P. */
+    if ((params->base.len == 0) && (vfy->counter == -1)) {
+	PORT_SetError(SEC_ERROR_INVALID_ARGS);
+	return SECFailure;
+    }
+
+    MP_DIGITS(&p0) = 0;
     MP_DIGITS(&P) = 0;
     MP_DIGITS(&Q) = 0;
     MP_DIGITS(&G) = 0;
     MP_DIGITS(&P_) = 0;
     MP_DIGITS(&Q_) = 0;
     MP_DIGITS(&G_) = 0;
     MP_DIGITS(&r) = 0;
     MP_DIGITS(&h) = 0;
+    CHECK_MPI_OK( mp_init(&p0) );
     CHECK_MPI_OK( mp_init(&P) );
     CHECK_MPI_OK( mp_init(&Q) );
     CHECK_MPI_OK( mp_init(&G) );
     CHECK_MPI_OK( mp_init(&P_) );
     CHECK_MPI_OK( mp_init(&Q_) );
     CHECK_MPI_OK( mp_init(&G_) );
     CHECK_MPI_OK( mp_init(&r) );
     CHECK_MPI_OK( mp_init(&h) );
     *result = SECSuccess;
     SECITEM_TO_MPINT(params->prime,    &P);
     SECITEM_TO_MPINT(params->subPrime, &Q);
-    SECITEM_TO_MPINT(params->base,     &G);
-    /* 1.  Q is 160 bits long. */
-    CHECKPARAM( mpl_significant_bits(&Q) == 160 );
-    /* 2.  P is one of the 9 valid lengths. */
+    /* if G isn't specified, just check P and Q */
+    if (params->base.len != 0) {
+	SECITEM_TO_MPINT(params->base,     &G);
+    }
+    /* 1.  Check (L,N) pair */
+    N = mpl_significant_bits(&Q);
     L = mpl_significant_bits(&P);
-    j = PQG_PBITS_TO_INDEX(L);
-    CHECKPARAM( j >= 0 && j <= 8 );
+    if (L < 1024) {
+	/* handle DSA1 pqg parameters with less thatn 1024 bits*/
+	CHECKPARAM( N == DSA1_Q_BITS );
+	j = PQG_PBITS_TO_INDEX(L);
+	CHECKPARAM( j >= 0 && j <= 8 );
+	counter_max = 4096;
+    } else {
+	/* handle DSA2 parameters (includes DSA1, 1024 bits) */
+	CHECKPARAM(pqg_validate_dsa2(L, N) == SECSuccess);
+	counter_max = 4*L;
+    }
     /* 3.  G < P */
-    CHECKPARAM( mp_cmp(&G, &P) < 0 );
+    if (params->base.len != 0) {
+	CHECKPARAM( mp_cmp(&G, &P) < 0 );
+    }
     /* 4.  P % Q == 1 */
     CHECK_MPI_OK( mp_mod(&P, &Q, &r) );
     CHECKPARAM( mp_cmp_d(&r, 1) == 0 );
     /* 5.  Q is prime */
-    CHECKPARAM( mpp_pprime(&Q, PQG_Q_PRIMALITY_TESTS) == MP_YES );
+    CHECKPARAM( mpp_pprime(&Q, prime_testcount_q(L,N)) == MP_YES );
     /* 6.  P is prime */
-    CHECKPARAM( mpp_pprime(&P, PQG_P_PRIMALITY_TESTS) == MP_YES );
+    CHECKPARAM( mpp_pprime(&P, prime_testcount_p(L,N)) == MP_YES );
     /* Steps 7-12 are done only if the optional PQGVerify is supplied. */
-    /* 7.  counter < 4096 */
-    CHECKPARAM( vfy->counter < 4096 );
-    /* 8.  g >= 160 and g < 2048   (g is length of seed in bits) */
+    /* continue processing P */
+    /* 7.  counter < 4*L */
+    CHECKPARAM( (vfy->counter == -1) || (vfy->counter < counter_max) );
+    /* 8.  g >= N and g < 2*L   (g is length of seed in bits) */
     g = vfy->seed.len * 8;
-    CHECKPARAM( g >= 160 && g < 2048 );
+    CHECKPARAM( g >= N && g < counter_max/2 );
     /* 9.  Q generated from SEED matches Q in PQGParams. */
-    CHECK_SEC_OK( makeQfromSeed(g, &vfy->seed, &Q_) );
+    /* This function checks all possible hash and generation types to
+     * find a Q_ which matches Q. */
+    CHECKPARAM( findQfromSeed(L, N, g, &vfy->seed, &Q, &Q_, &qseed_len,
+					&hashtype, &type) == SECSuccess );
     CHECKPARAM( mp_cmp(&Q, &Q_) == 0 );
-    /* 10. P generated from (L, counter, g, SEED, Q) matches P in PQGParams. */
-    n = (L - 1) / BITS_IN_Q;
-    offset = vfy->counter * (n + 1) + 2;
-    CHECK_SEC_OK( makePfromQandSeed(L, offset, g, &vfy->seed, &Q, &P_) );
-    CHECKPARAM( mp_cmp(&P, &P_) == 0 );
-    /* Next two are optional: if h == 0 ignore */
-    if (vfy->h.len == 0) goto cleanup;
-    /* 11. 1 < h < P-1 */
-    SECITEM_TO_MPINT(vfy->h, &h);
-    CHECK_MPI_OK( mpl_set_bit(&P, 0, 0) ); /* P is prime, p-1 == zero 1st bit */
-    CHECKPARAM( mp_cmp_d(&h, 1) > 0 && mp_cmp(&h, &P) );
+    if (type == FIPS186_3_ST_TYPE) {
+	SECItem qseed = { 0, 0, 0 };
+	SECItem pseed = { 0, 0, 0 };
+	int first_seed_len;
+	int pgen_counter = 0;
+
+	/* extract pseed and qseed from domain_parameter_seed, which is
+	 * first_seed || pseed || qseed. qseed is first_seed + small_integer
+	 * pseed is qseed + small_integer. This means most of the time 
+	 * first_seed.len == qseed.len == pseed.len. Rarely qseed.len and/or
+	 * pseed.len will be one greater than first_seed.len, so we can
+	 * depend on the fact that 
+	 *   first_seed.len = floor(domain_parameter_seed.len/3).
+	 * findQfromSeed returned qseed.len, so we can calculate pseed.len as
+	 *   pseed.len = domain_parameter_seed.len - first_seed.len - qseed.len
+	 * this is probably over kill, since 99.999% of the time they will all
+	 * be equal.
+	 *
+	 * With the lengths, we can now find the offsets;
+	 * first_seed.data = domain_parameter_seed.data + 0
+	 * pseed.data = domain_parameter_seed.data + first_seed.len
+	 * qseed.data = domain_parameter_seed.data 
+	 *         + domain_paramter_seed.len - qseed.len
+	 *
+	 */
+	first_seed_len = vfy->seed.len/3;
+	CHECKPARAM(qseed_len < vfy->seed.len);
+	CHECKPARAM(first_seed_len*8 > N-1);
+	CHECKPARAM(first_seed_len+qseed_len < vfy->seed.len);
+	qseed.len = qseed_len;
+	qseed.data = vfy->seed.data + vfy->seed.len - qseed.len;
+	pseed.len = vfy->seed.len - (first_seed_len+qseed_len);
+	pseed.data = vfy->seed.data + first_seed_len;
+
+	/*
+	 * now complete FIPS 186-3 A.1.2.1.2. Step 1 was completed
+	 * above in our initial checks, Step 2 was completed by
+	 * findQfromSeed */
+
+	/* Step 3 (status, c0, prime_seed, prime_gen_counter) =
+	** (ST_Random_Prime((ceil(length/2)+1, input_seed)
+	*/
+	CHECK_SEC_OK( makePrimefromSeedShawneTaylor(hashtype, (L+1)/2+1,
+			&qseed, &p0, &pseed_, &pgen_counter) );
+	/* Steps 4-22 FIPS 186-3 appendix A.1.2.1.2 */
+	CHECK_SEC_OK( makePrimefromPrimesShawneTaylor(hashtype, L, 
+		&p0, &Q_, &P_, &pseed_, &pgen_counter) );
+	CHECKPARAM( mp_cmp(&P, &P_) == 0 );
+	/* make sure pseed wasn't tampered with (since it is part of 
+	 * calculating G) */
+	CHECKPARAM( SECITEM_CompareItem(&pseed, &pseed_) == SECEqual );
+    } else if (vfy->counter == -1) {
+	/* If counter is set to -1, we are really only verifying G, skip
+	 * the remainder of the checks for P */
+	CHECKPARAM(type != FIPS186_1_TYPE); /* we only do this for DSA2 */
+    } else {
+	/* 10. P generated from (L, counter, g, SEED, Q) matches P 
+	 * in PQGParams. */
+	outlen = HASH_ResultLen(hashtype)*BITS_PER_BYTE;
+	n = (L - 1) / outlen;
+	offset = vfy->counter * (n + 1) + ((type == FIPS186_1_TYPE) ? 2 : 1);
+	CHECK_SEC_OK( makePfromQandSeed(hashtype, L, N, offset, g, &vfy->seed, 
+				    	&Q, &P_) );
+	CHECKPARAM( mp_cmp(&P, &P_) == 0 );
+    }
+
+    /* now check G, skip if don't have a g */
+    if (params->base.len == 0) goto cleanup;
+
+    /* first Always check that G is OK  FIPS186-3 A.2.2  & A.2.4*/
+    /* 1. 2 < G < P-1 */
+    /* P is prime, p-1 == zero 1st bit */
+    CHECK_MPI_OK( mpl_set_bit(&P, 0, 0) );
+    CHECKPARAM( mp_cmp_d(&G, 2) > 0 && mp_cmp(&G, &P) < 0 );
     CHECK_MPI_OK( mpl_set_bit(&P, 0, 1) ); /* set it back */
-    /* 12. G generated from h matches G in PQGParams. */
-    CHECK_SEC_OK( makeGfromH(&P, &Q, &h, &G_, &passed) );
-    CHECKPARAM( passed && mp_cmp(&G, &G_) == 0 );
+    /* 2. verify g**q mod p == 1 */
+    CHECK_MPI_OK( mp_exptmod(&G, &Q, &P, &h) );    /* h = G ** Q mod P */
+    CHECKPARAM(mp_cmp_d(&h, 1) == 0);
+
+    /* no h, the above is the best we can do */
+    if (vfy->h.len == 0) {
+	if (type != FIPS186_1_TYPE) {
+	    *result = SECWouldBlock;
+	}
+	goto cleanup;
+    }
+
+    /*
+     * If h is one byte and FIPS186-3 was used to generate Q (we've verified
+     * Q was generated from seed already, then we assume that FIPS 186-3
+     * appendix A.2.3 was used to generate G. Otherwise we assume A.2.1 was
+     * used to generate G.
+     */
+    if ((vfy->h.len == 1) && (type != FIPS186_1_TYPE)) {
+	/* A.2.3 */
+	CHECK_SEC_OK(makeGfromIndex(hashtype, &P, &Q, &vfy->seed,
+				 vfy->h.data[0], &G_) );
+	CHECKPARAM( mp_cmp(&G, &G_) == 0 );
+    } else {
+	int passed;
+	/* A.2.1 */
+	SECITEM_TO_MPINT(vfy->h, &h);
+	/* 11. 1 < h < P-1 */
+	/* P is prime, p-1 == zero 1st bit */
+	CHECK_MPI_OK( mpl_set_bit(&P, 0, 0) );
+	CHECKPARAM( mp_cmp_d(&G, 2) > 0 && mp_cmp(&G, &P) );
+	CHECK_MPI_OK( mpl_set_bit(&P, 0, 1) ); /* set it back */
+	/* 12. G generated from h matches G in PQGParams. */
+ 	CHECK_SEC_OK( makeGfromH(&P, &Q, &h, &G_, &passed) );
+	CHECKPARAM( passed && mp_cmp(&G, &G_) == 0 );
+    }
 cleanup:
+    mp_clear(&p0);
     mp_clear(&P);
     mp_clear(&Q);
     mp_clear(&G);
     mp_clear(&P_);
     mp_clear(&Q_);
     mp_clear(&G_);
     mp_clear(&r);
     mp_clear(&h);
+    if (pseed_.data) {
+	SECITEM_FreeItem(&pseed_,PR_FALSE);
+    }
     if (err) {
 	MP_TO_SEC_ERROR(err);
 	rv = SECFailure;
     }
     return rv;
 }
 
 /**************************************************************************
new file mode 100644
--- /dev/null
+++ b/security/nss/lib/freebl/pqg.h
@@ -0,0 +1,25 @@
+/* This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
+
+/*
+ *  pqg.h
+ *
+ *  header file for pqg functions exported just to freebl
+ */
+
+#ifndef _PQG_H_
+#define _PQG_H_ 1
+
+/* PQG_GetLength returns the significant bytes in the SECItem object (that is 
+ * the length of the object minus any leading zeros. Any SECItem may be used,
+ * though this function is usually used for P, Q, or G values */
+unsigned int PQG_GetLength(const SECItem *obj);
+/* Check to see the PQG parameters patch a NIST defined DSA size,
+ * returns SECFaillure and sets SEC_ERROR_INVALID_ARGS if it doesn't.
+ * See blapi.h for legal DSA PQG sizes. */
+SECStatus PQG_Check(const PQGParams *params);
+/* Return the prefered hash algorithm for the given PQGParameters. */
+HASH_HashType PQG_GetHashType(const PQGParams *params);
+
+#endif
--- a/security/nss/lib/freebl/rawhash.c
+++ b/security/nss/lib/freebl/rawhash.c
@@ -140,8 +140,42 @@ const SECHashObject *
 HASH_GetRawHashObject(HASH_HashType hashType)
 {
     if (hashType < HASH_AlgNULL || hashType >= HASH_AlgTOTAL) {
 	PORT_SetError(SEC_ERROR_INVALID_ARGS);
 	return NULL;
     }
     return &SECRawHashObjects[hashType];
 }
+
+unsigned int
+HASH_ResultLen(HASH_HashType type)
+{
+    const SECHashObject *hash_obj = HASH_GetRawHashObject(type);
+    if (hash_obj == NULL) {
+	return 0;
+    }
+    return hash_obj->length;
+}
+
+
+SECStatus
+HASH_HashBuf(HASH_HashType type, unsigned char *dest, unsigned char *src,
+				 PRUint32 src_len)
+{
+    const SECHashObject *hash_obj = HASH_GetRawHashObject(type);
+    void *hashcx = NULL;
+    unsigned int dummy;
+
+    if (hash_obj == NULL) {
+	return SECFailure;
+    }
+
+    hashcx = hash_obj->create();
+    if (hashcx == NULL) {
+	return SECFailure;
+    }
+    hash_obj->begin(hashcx);
+    hash_obj->update(hashcx,src,src_len);
+    hash_obj->end(hashcx,dest, &dummy, hash_obj->length);
+    hash_obj->destroy(hashcx, PR_TRUE);
+    return SECSuccess;
+}
--- a/security/nss/lib/freebl/shvfy.c
+++ b/security/nss/lib/freebl/shvfy.c
@@ -10,16 +10,18 @@
 
 #include "shsign.h"
 #include "prlink.h"
 #include "prio.h"
 #include "blapi.h"
 #include "seccomon.h"
 #include "stdio.h"
 #include "prmem.h"
+#include "hasht.h"
+#include "pqg.h"
 
 /*
  * Most modern version of Linux support a speed optimization scheme where an
  * application called prelink modifies programs and shared libraries to quickly
  * load if they fit into an already designed address space. In short, prelink
  * scans the list of programs and libraries on your system, assigns them a
  * predefined space in the the address space, then provides the fixups to the
  * library.
@@ -293,31 +295,32 @@ loser:
 }
 
 PRBool
 BLAPI_SHVerifyFile(const char *shName)
 {
     char *checkName = NULL;
     PRFileDesc *checkFD = NULL;
     PRFileDesc *shFD = NULL;
-    SHA1Context *hashcx = NULL;
+    void  *hashcx = NULL;
+    SECHashObject *hashObj = NULL;
     SECItem signature = { 0, NULL, 0 };
     SECItem hash;
     int bytesRead, offset;
     SECStatus rv;
     DSAPublicKey key;
     int count;
 #ifdef FREEBL_USE_PRELINK
     int pid = 0;
 #endif
 
     PRBool result = PR_FALSE; /* if anything goes wrong,
 			       * the signature does not verify */
     unsigned char buf[4096];
-    unsigned char hashBuf[SHA1_LENGTH];
+    unsigned char hashBuf[HASH_LENGTH_MAX];
 
     PORT_Memset(&key,0,sizeof(key));
     hash.data = hashBuf;
     hash.len = sizeof(hashBuf);
 
     if (!shName) {
 	goto loser;
     }
@@ -382,50 +385,55 @@ BLAPI_SHVerifyFile(const char *shName)
     if (rv != SECSuccess) {
 	goto loser;
     }
 
     /* done with the check file */
     PR_Close(checkFD);
     checkFD = NULL;
 
+    hashObj = HASH_GetRawHashObject(PQG_GetHashType(&key.params));
+    if (hashObj == NULL) {
+	goto loser;
+    }
+
     /* open our library file */
 #ifdef FREEBL_USE_PRELINK
     shFD = bl_OpenUnPrelink(shName,&pid);
 #else
     shFD = PR_Open(shName, PR_RDONLY, 0);
 #endif
     if (shFD == NULL) {
 #ifdef DEBUG_SHVERIFY
         fprintf(stderr, "Failed to open the library file %s: (%d, %d)\n",
                 shName, (int)PR_GetError(), (int)PR_GetOSError());
 #endif /* DEBUG_SHVERIFY */
 	goto loser;
     }
 
     /* hash our library file with SHA1 */
-    hashcx = SHA1_NewContext();
+    hashcx = hashObj->create();
     if (hashcx == NULL) {
 	goto loser;
     }
-    SHA1_Begin(hashcx);
+    hashObj->begin(hashcx);
 
     count = 0;
     while ((bytesRead = PR_Read(shFD, buf, sizeof(buf))) > 0) {
-	SHA1_Update(hashcx, buf, bytesRead);
+	hashObj->update(hashcx, buf, bytesRead);
 	count += bytesRead;
     }
 #ifdef FREEBL_USE_PRELINK
     bl_CloseUnPrelink(shFD, pid);
 #else
     PR_Close(shFD);
 #endif
     shFD = NULL;
 
-    SHA1_End(hashcx, hash.data, &hash.len, hash.len);
+    hashObj->end(hashcx, hash.data, &hash.len, hash.len);
 
 
     /* verify the hash against the check file */
     if (DSA_VerifyDigest(&key, &signature, &hash) == SECSuccess) {
 	result = PR_TRUE;
     }
 #ifdef DEBUG_SHVERIFY
   {
@@ -459,17 +467,19 @@ loser:
     }
     if (checkFD != NULL) {
 	PR_Close(checkFD);
     }
     if (shFD != NULL) {
 	PR_Close(shFD);
     }
     if (hashcx != NULL) {
-	SHA1_DestroyContext(hashcx,PR_TRUE);
+	if (hashObj) {
+	    hashObj->destroy(hashcx,PR_TRUE);
+	}
     }
     if (signature.data != NULL) {
 	PORT_Free(signature.data);
     }
     if (key.params.prime.data != NULL) {
 	PORT_Free(key.params.prime.data);
     }
     if (key.params.subPrime.data != NULL) {
--- a/security/nss/lib/softoken/pkcs11.c
+++ b/security/nss/lib/softoken/pkcs11.c
@@ -285,16 +285,18 @@ static const struct mechanismList mechan
 				 CKF_SN_VR}, 	PR_TRUE},
      {CKM_SHA512_RSA_PKCS,	{RSA_MIN_MODULUS_BITS,CK_MAX,
 				 CKF_SN_VR}, 	PR_TRUE},
      /* ------------------------- DSA Operations --------------------------- */
      {CKM_DSA_KEY_PAIR_GEN,	{DSA_MIN_P_BITS, DSA_MAX_P_BITS,
 				 CKF_GENERATE_KEY_PAIR}, PR_TRUE},
      {CKM_DSA,			{DSA_MIN_P_BITS, DSA_MAX_P_BITS, 
 				 CKF_SN_VR},              PR_TRUE},
+     {CKM_DSA_PARAMETER_GEN,	{DSA_MIN_P_BITS, DSA_MAX_P_BITS, 
+				 CKF_GENERATE},           PR_TRUE},
      {CKM_DSA_SHA1,		{DSA_MIN_P_BITS, DSA_MAX_P_BITS,
 				 CKF_SN_VR},              PR_TRUE},
      /* -------------------- Diffie Hellman Operations --------------------- */
      /* no diffie hellman yet */
      {CKM_DH_PKCS_KEY_PAIR_GEN,	{DH_MIN_P_BITS, DH_MAX_P_BITS, 
 				 CKF_GENERATE_KEY_PAIR}, PR_TRUE}, 
      {CKM_DH_PKCS_DERIVE,	{DH_MIN_P_BITS, DH_MAX_P_BITS,
 				 CKF_DERIVE}, 	PR_TRUE}, 
@@ -855,48 +857,48 @@ sftk_handlePublicKeyObject(SFTKSession *
 	}
 	crv = sftk_ConstrainAttribute(object, CKA_PUBLIC_EXPONENT, 2, 0, 0);
 	if (crv != CKR_OK) {
 	    return crv;
 	}
 	break;
     case CKK_DSA:
 	crv = sftk_ConstrainAttribute(object, CKA_SUBPRIME, 
-						DSA_Q_BITS, DSA_Q_BITS, 0);
+					DSA_MIN_Q_BITS, DSA_MAX_Q_BITS, 0);
 	if (crv != CKR_OK) {
 	    return crv;
 	}
 	crv = sftk_ConstrainAttribute(object, CKA_PRIME, 
 					DSA_MIN_P_BITS, DSA_MAX_P_BITS, 64);
 	if (crv != CKR_OK) {
 	    return crv;
 	}
-	crv = sftk_ConstrainAttribute(object, CKA_BASE, 1, DSA_MAX_P_BITS, 0);
+	crv = sftk_ConstrainAttribute(object, CKA_BASE, 2, DSA_MAX_P_BITS, 0);
 	if (crv != CKR_OK) {
 	    return crv;
 	}
-	crv = sftk_ConstrainAttribute(object, CKA_VALUE, 1, DSA_MAX_P_BITS, 0);
+	crv = sftk_ConstrainAttribute(object, CKA_VALUE, 2, DSA_MAX_P_BITS, 0);
 	if (crv != CKR_OK) {
 	    return crv;
 	}
 	encrypt = CK_FALSE;
 	recover = CK_FALSE;
 	wrap = CK_FALSE;
 	break;
     case CKK_DH:
 	crv = sftk_ConstrainAttribute(object, CKA_PRIME, 
 					DH_MIN_P_BITS, DH_MAX_P_BITS, 0);
 	if (crv != CKR_OK) {
 	    return crv;
 	}
-	crv = sftk_ConstrainAttribute(object, CKA_BASE, 1, DH_MAX_P_BITS, 0);
+	crv = sftk_ConstrainAttribute(object, CKA_BASE, 2, DH_MAX_P_BITS, 0);
 	if (crv != CKR_OK) {
 	    return crv;
 	}
-	crv = sftk_ConstrainAttribute(object, CKA_VALUE, 1, DH_MAX_P_BITS, 0);
+	crv = sftk_ConstrainAttribute(object, CKA_VALUE, 2, DH_MAX_P_BITS, 0);
 	if (crv != CKR_OK) {
 	    return crv;
 	}
 	verify = CK_FALSE;
 	derive = CK_TRUE;
 	encrypt = CK_FALSE;
 	recover = CK_FALSE;
 	wrap = CK_FALSE;
@@ -1344,48 +1346,82 @@ sftk_handleDSAParameterObject(SFTKSessio
     SFTKAttribute *baseAttr = NULL;
     SFTKAttribute *seedAttr = NULL;
     SFTKAttribute *hAttr = NULL;
     SFTKAttribute *attribute;
     CK_RV crv = CKR_TEMPLATE_INCOMPLETE;
     PQGParams params;
     PQGVerify vfy, *verify = NULL;
     SECStatus result,rv;
+    /* This bool keeps track of whether or not we need verify parameters.
+     * If a P, Q and G or supplied, we dont' need verify parameters, as we
+     * have PQ and G. 
+     *   - If G is not supplied, the presumption is that we want to
+     * verify P and Q only.
+     *   - If counter is supplied, it is presumed we want to verify PQ because
+     * the counter is only used in verification.
+     *   - If H is supplied, is is presumed we want to verify G because H is
+     * only used to verify G.
+     *   - Any verification step must have the SEED (counter or H could be 
+     * missing depending on exactly what we want to verify). If SEED is supplied,
+     * the code just goes ahead and runs verify (other errors are parameter
+     * errors are detected by the PQG_VerifyParams function). If SEED is not
+     * supplied, but we determined that we are trying to verify (because needVfy
+     * is set, go ahead and return CKR_TEMPLATE_INCOMPLETE.
+     */
+    PRBool needVfy = PR_FALSE;      
 
     primeAttr = sftk_FindAttribute(object,CKA_PRIME);
     if (primeAttr == NULL) goto loser;
     params.prime.data = primeAttr->attrib.pValue;
     params.prime.len = primeAttr->attrib.ulValueLen;
 
     subPrimeAttr = sftk_FindAttribute(object,CKA_SUBPRIME);
     if (subPrimeAttr == NULL) goto loser;
     params.subPrime.data = subPrimeAttr->attrib.pValue;
     params.subPrime.len = subPrimeAttr->attrib.ulValueLen;
 
     baseAttr = sftk_FindAttribute(object,CKA_BASE);
-    if (baseAttr == NULL) goto loser;
-    params.base.data = baseAttr->attrib.pValue;
-    params.base.len = baseAttr->attrib.ulValueLen;
+    if (baseAttr != NULL) {
+	params.base.data = baseAttr->attrib.pValue;
+	params.base.len = baseAttr->attrib.ulValueLen;
+    } else {
+	params.base.data = NULL;
+	params.base.len = 0;
+	needVfy = PR_TRUE; /* presumably only including PQ so we can verify
+			    * them. */
+    }
 
     attribute = sftk_FindAttribute(object, CKA_NETSCAPE_PQG_COUNTER);
     if (attribute != NULL) {
 	vfy.counter = *(CK_ULONG *) attribute->attrib.pValue;
 	sftk_FreeAttribute(attribute);
-
-	seedAttr = sftk_FindAttribute(object, CKA_NETSCAPE_PQG_SEED);
-	if (seedAttr == NULL) goto loser;
+	needVfy = PR_TRUE; /* included a count so we can verify PQ */
+    } else {
+	vfy.counter = -1;
+    }
+
+    hAttr = sftk_FindAttribute(object, CKA_NETSCAPE_PQG_H);
+    if (hAttr != NULL) {
+	vfy.h.data = hAttr->attrib.pValue;
+	vfy.h.len = hAttr->attrib.ulValueLen;
+	needVfy = PR_TRUE; /* included H so we can verify G */
+    } else {
+	vfy.h.data = NULL;
+	vfy.h.len = 0;
+    }
+    seedAttr = sftk_FindAttribute(object, CKA_NETSCAPE_PQG_SEED);
+    if (seedAttr != NULL) {
 	vfy.seed.data = seedAttr->attrib.pValue;
 	vfy.seed.len = seedAttr->attrib.ulValueLen;
 
-	hAttr = sftk_FindAttribute(object, CKA_NETSCAPE_PQG_H);
-	if (hAttr == NULL) goto loser;
-	vfy.h.data = hAttr->attrib.pValue;
-	vfy.h.len = hAttr->attrib.ulValueLen;
-
 	verify = &vfy;
+    } else if (needVfy) {
+	goto loser; /* Verify always needs seed, if we need verify and not seed
+		     * then fail */
     }
 
     crv = CKR_FUNCTION_FAILED;
     rv = PQG_VerifyParams(&params,verify,&result);
     if (rv == SECSuccess) {
 	crv = (result== SECSuccess) ? CKR_OK : CKR_ATTRIBUTE_VALUE_INVALID;
     }
 
--- a/security/nss/lib/softoken/pkcs11c.c
+++ b/security/nss/lib/softoken/pkcs11c.c
@@ -2052,17 +2052,17 @@ finish_rsa:
 	privKey = sftk_GetPrivKey(key,CKK_DSA,&crv);
 	if (privKey == NULL) {
 	    break;
 	}
 	context->cipherInfo = privKey;
 	context->update     = (SFTKCipher) nsc_DSA_Sign_Stub;
 	context->destroy    = (privKey == key->objectInfo) ?
 		(SFTKDestroy) sftk_Null:(SFTKDestroy)sftk_FreePrivKey;
-	context->maxLen     = DSA_SIGNATURE_LEN;
+	context->maxLen     = DSA_MAX_SIGNATURE_LEN;
 
 	break;
 
 #ifdef NSS_ENABLE_ECC
     case CKM_ECDSA_SHA1:
 	context->multi = PR_TRUE;
 	crv = sftk_doSubSHA1(context);
 	if (crv != CKR_OK) break;
@@ -2900,54 +2900,98 @@ nsc_pbe_key_gen(NSSPKCS5PBEParameter *pk
         if (pbe_params && pbe_params->pInitVector != NULL) {
 	    PORT_Memcpy(pbe_params->pInitVector, iv.data, iv.len);
         }
         PORT_Free(iv.data);
     }
 
     return CKR_OK;
 }
+
+/* 
+ * this is coded for "full" support. These selections will be limitted to
+ * the official subset by freebl.
+ */
+static unsigned int
+sftk_GetSubPrimeFromPrime(unsigned int primeBits)
+{
+   if (primeBits <= 1024) {
+	return 160;
+   } else if (primeBits <= 2048) {
+	return 224;
+   } else if (primeBits <= 3072) {
+	return 256;
+   } else if (primeBits <= 7680) {
+	return 384;
+   } else {
+	return 512;
+   }
+}
+
 static CK_RV
 nsc_parameter_gen(CK_KEY_TYPE key_type, SFTKObject *key)
 {
     SFTKAttribute *attribute;
     CK_ULONG counter;
     unsigned int seedBits = 0;
+    unsigned int subprimeBits = 0;
     unsigned int primeBits;
-    unsigned int j;
+    unsigned int j = 8; /* default to 1024 bits */
     CK_RV crv = CKR_OK;
     PQGParams *params = NULL;
     PQGVerify *vfy = NULL;
     SECStatus rv;
 
     attribute = sftk_FindAttribute(key, CKA_PRIME_BITS);
     if (attribute == NULL) {
 	return CKR_TEMPLATE_INCOMPLETE;
     }
     primeBits = (unsigned int) *(CK_ULONG *)attribute->attrib.pValue;
     sftk_FreeAttribute(attribute);
-    j = PQG_PBITS_TO_INDEX(primeBits);
-    if (j == (unsigned int)-1) {
-	return CKR_ATTRIBUTE_VALUE_INVALID;
+    if (primeBits < 1024) {
+	j = PQG_PBITS_TO_INDEX(primeBits);
+	if (j == (unsigned int)-1) {
+	    return CKR_ATTRIBUTE_VALUE_INVALID;
+	}
     }
 
     attribute = sftk_FindAttribute(key, CKA_NETSCAPE_PQG_SEED_BITS);
     if (attribute != NULL) {
 	seedBits = (unsigned int) *(CK_ULONG *)attribute->attrib.pValue;
 	sftk_FreeAttribute(attribute);
     }
 
+    attribute = sftk_FindAttribute(key, CKA_SUBPRIME_BITS);
+    if (attribute != NULL) {
+	subprimeBits = (unsigned int) *(CK_ULONG *)attribute->attrib.pValue;
+	sftk_FreeAttribute(attribute);
+    }
+
     sftk_DeleteAttributeType(key,CKA_PRIME_BITS);
+    sftk_DeleteAttributeType(key,CKA_SUBPRIME_BITS);
     sftk_DeleteAttributeType(key,CKA_NETSCAPE_PQG_SEED_BITS);
 
-    if (seedBits == 0) {
-	rv = PQG_ParamGen(j, &params, &vfy);
+    /* use the old PQG interface if we have old input data */
+    if ((primeBits < 1024) || ((primeBits == 1024) && (subprimeBits == 0))) {
+	if (seedBits == 0) {
+	    rv = PQG_ParamGen(j, &params, &vfy);
+	} else {
+	    rv = PQG_ParamGenSeedLen(j,seedBits/8, &params, &vfy);
+	}
     } else {
-	rv = PQG_ParamGenSeedLen(j,seedBits/8, &params, &vfy);
-    }
+	if (subprimeBits == 0) {
+	    subprimeBits = sftk_GetSubPrimeFromPrime(primeBits);
+        }
+	if (seedBits == 0) {
+	    seedBits = primeBits;
+	}
+	rv = PQG_ParamGenV2(primeBits, subprimeBits, seedBits/8, &params, &vfy);
+    }
+	
+
 
     if (rv != SECSuccess) {
 	if (PORT_GetError() == SEC_ERROR_LIBRARY_FAILURE) {
 	    sftk_fatalError = PR_TRUE;
 	}
 	return sftk_MapCryptError(PORT_GetError());
     }
     crv = sftk_AddAttributeType(key,CKA_PRIME,
@@ -3454,49 +3498,65 @@ sftk_PairwiseConsistencyCheck(CK_SESSION
      *                      CKK_EC   => CKM_ECDSA
      *                      others   => CKM_INVALID_MECHANISM
      *
      * None of these mechanisms has a parameter.
      */
     CK_MECHANISM mech = {0, NULL, 0};
 
     CK_ULONG modulusLen;
+    CK_ULONG subPrimeLen;
     PRBool isEncryptable = PR_FALSE;
     PRBool canSignVerify = PR_FALSE;
     PRBool isDerivable = PR_FALSE;
     CK_RV crv;
 
     /* Variables used for Encrypt/Decrypt functions. */
     unsigned char *known_message = (unsigned char *)"Known Crypto Message";
     unsigned char plaintext[PAIRWISE_MESSAGE_LENGTH];
     CK_ULONG bytes_decrypted;
     unsigned char *ciphertext;
     unsigned char *text_compared;
     CK_ULONG bytes_encrypted;
     CK_ULONG bytes_compared;
+    CK_ULONG pairwise_digest_length = PAIRWISE_DIGEST_LENGTH;
 
     /* Variables used for Signature/Verification functions. */
-    /* always uses SHA-1 digest */
-    unsigned char *known_digest = (unsigned char *)"Mozilla Rules World!";
+    /* Must be at least 256 bits for DSA2 digest */
+    unsigned char *known_digest = (unsigned char *)
+				"Mozilla Rules the World through NSS!";
     unsigned char *signature;
     CK_ULONG signature_length;
 
     if (keyType == CKK_RSA) {
 	SFTKAttribute *attribute;
 
 	/* Get modulus length of private key. */
 	attribute = sftk_FindAttribute(privateKey, CKA_MODULUS);
 	if (attribute == NULL) {
 	    return CKR_DEVICE_ERROR;
 	}
 	modulusLen = attribute->attrib.ulValueLen;
 	if (*(unsigned char *)attribute->attrib.pValue == 0) {
 	    modulusLen--;
 	}
 	sftk_FreeAttribute(attribute);
+    } else if (keyType == CKK_DSA) {
+	SFTKAttribute *attribute;
+
+	/* Get subprime length of private key. */
+	attribute = sftk_FindAttribute(privateKey, CKA_SUBPRIME);
+	if (attribute == NULL) {
+	    return CKR_DEVICE_ERROR;
+	}
+	subPrimeLen = attribute->attrib.ulValueLen;
+	if (subPrimeLen > 1 && *(unsigned char *)attribute->attrib.pValue == 0) {
+	    subPrimeLen--;
+	}
+	sftk_FreeAttribute(attribute);
     }
 
     /**************************************************/
     /* Pairwise Consistency Check of Encrypt/Decrypt. */
     /**************************************************/
 
     isEncryptable = sftk_isTrue(privateKey, CKA_DECRYPT); 
 
@@ -3612,17 +3672,18 @@ sftk_PairwiseConsistencyCheck(CK_SESSION
     if (canSignVerify) {
 	/* Determine length of signature. */
 	switch (keyType) {
 	case CKK_RSA:
 	    signature_length = modulusLen;
 	    mech.mechanism = CKM_RSA_PKCS;
 	    break;
 	case CKK_DSA:
-	    signature_length = DSA_SIGNATURE_LEN;
+	    signature_length = DSA_MAX_SIGNATURE_LEN;
+	    pairwise_digest_length = subPrimeLen;
 	    mech.mechanism = CKM_DSA;
 	    break;
 #ifdef NSS_ENABLE_ECC
 	case CKK_EC:
 	    signature_length = MAX_ECKEY_LEN * 2;
 	    mech.mechanism = CKM_ECDSA;
 	    break;
 #endif
@@ -3640,34 +3701,34 @@ sftk_PairwiseConsistencyCheck(CK_SESSION
 	crv = NSC_SignInit(hSession, &mech, privateKey->handle);
 	if (crv != CKR_OK) {
 	    PORT_Free(signature);
 	    return crv;
 	}
 
 	crv = NSC_Sign(hSession,
 		       known_digest,
-		       PAIRWISE_DIGEST_LENGTH,
+		       pairwise_digest_length,
 		       signature,
 		       &signature_length);
 	if (crv != CKR_OK) {
 	    PORT_Free(signature);
 	    return crv;
 	}
 	
 	/* Verify the known hash using the public key. */
 	crv = NSC_VerifyInit(hSession, &mech, publicKey->handle);
 	if (crv != CKR_OK) {
 	    PORT_Free(signature);
 	    return crv;
 	}
 
 	crv = NSC_Verify(hSession,
 			 known_digest,
-			 PAIRWISE_DIGEST_LENGTH,
+			 pairwise_digest_length,
 			 signature,
 			 signature_length);
 
 	/* Free signature data. */
 	PORT_Free(signature);
 
 	if ((crv == CKR_SIGNATURE_LEN_RANGE) ||
 		(crv == CKR_SIGNATURE_INVALID)) {
@@ -3940,35 +4001,38 @@ kpg_done:
 			    	    sftk_item_expand(&pqgParam.base));
 	if (crv != CKR_OK) {
 	    PORT_Free(pqgParam.prime.data);
 	    PORT_Free(pqgParam.subPrime.data);
 	    PORT_Free(pqgParam.base.data);
 	    break;
 	}
 
+	/*
+	 * these are checked by DSA_NewKey
+	 */
         bitSize = sftk_GetLengthInBits(pqgParam.subPrime.data, 
 							pqgParam.subPrime.len);
-        if (bitSize != DSA_Q_BITS)  {
+        if ((bitSize < DSA_MIN_Q_BITS) || (bitSize > DSA_MAX_Q_BITS))  {
 	    crv = CKR_TEMPLATE_INCOMPLETE;
 	    PORT_Free(pqgParam.prime.data);
 	    PORT_Free(pqgParam.subPrime.data);
 	    PORT_Free(pqgParam.base.data);
 	    break;
 	}
         bitSize = sftk_GetLengthInBits(pqgParam.prime.data,pqgParam.prime.len);
         if ((bitSize <  DSA_MIN_P_BITS) || (bitSize > DSA_MAX_P_BITS)) {
 	    crv = CKR_TEMPLATE_INCOMPLETE;
 	    PORT_Free(pqgParam.prime.data);
 	    PORT_Free(pqgParam.subPrime.data);
 	    PORT_Free(pqgParam.base.data);
 	    break;
 	}
         bitSize = sftk_GetLengthInBits(pqgParam.base.data,pqgParam.base.len);
-        if ((bitSize <  1) || (bitSize > DSA_MAX_P_BITS)) {
+        if ((bitSize <  2) || (bitSize > DSA_MAX_P_BITS)) {
 	    crv = CKR_TEMPLATE_INCOMPLETE;
 	    PORT_Free(pqgParam.prime.data);
 	    PORT_Free(pqgParam.subPrime.data);
 	    PORT_Free(pqgParam.base.data);
 	    break;
 	}
 	    
 	/* Generate the key */
--- a/security/nss/lib/ssl/ssl3con.c
+++ b/security/nss/lib/ssl/ssl3con.c
@@ -896,17 +896,17 @@ ssl3_VerifySignedHashes(SSL3Hashes *hash
     case rsaKey:
     	hashItem.data = hash->md5;
     	hashItem.len = sizeof(SSL3Hashes);
 	break;
     case dsaKey:
 	hashItem.data = hash->sha;
 	hashItem.len = sizeof(hash->sha);
 	/* Allow DER encoded DSA signatures in SSL 3.0 */
-	if (isTLS || buf->len != DSA_SIGNATURE_LEN) {
+	if (isTLS || buf->len != SECKEY_SignatureLen(key)) {
 	    signature = DSAU_DecodeDerSig(buf);
 	    if (!signature) {
 	    	PORT_SetError(SSL_ERROR_BAD_HANDSHAKE_HASH_VALUE);
 		return SECFailure;
 	    }
 	    buf = signature;
 	}
 	break;