DSA stuff and tests.

9 files changed, 564 insertions, 5 deletions

diff --git a/crypto/dsa/dsa_gen.c b/crypto/dsa/dsa_gen.c
index dc9c249310..0cff5c066d 100644
--- a/crypto/dsa/dsa_gen.c
+++ b/crypto/dsa/dsa_gen.c
@@ -80,6 +80,7 @@
 #include <openssl/rand.h>
 #include <openssl/sha.h>
 
+#ifndef FIPS
 DSA *DSA_generate_parameters(int bits,
 		unsigned char *seed_in, int seed_len,
 		int *counter_ret, unsigned long *h_ret,
@@ -293,4 +294,6 @@ err:
 	if (mont != NULL) BN_MONT_CTX_free(mont);
 	return(ok?ret:NULL);
 	}
-#endif
+#endif /* ndef FIPS */
+#endif /* ndef OPENSSL_NO_SHA */
+
diff --git a/fips/dsa/Makefile.ssl b/fips/dsa/Makefile.ssl
index 1b58c6cf8b..93a889c36f 100644
--- a/fips/dsa/Makefile.ssl
+++ b/fips/dsa/Makefile.ssl
@@ -23,8 +23,8 @@ TEST=fips_dsatest.c
 APPS=
 
 LIB=$(TOP)/libcrypto.a
-LIBSRC=fips_dsa_ossl.c
-LIBOBJ=fips_dsa_ossl.o
+LIBSRC=fips_dsa_ossl.c fips_dsa_gen.c
+LIBOBJ=fips_dsa_ossl.o fips_dsa_gen.o
 
 SRC= $(LIBSRC)
 
@@ -67,6 +67,21 @@ tags:
 
 tests:
 
+top_fips_dssvs:
+	(cd ../..; $(MAKE) DIRS=fips FDIRS=$(DIR) TARGET=fips_dssvs sub_target)
+
+fips_dssvs: fips_dssvs.o ../../libcrypto.a
+	$(CC) $(CFLAGS) -o fips_dssvs fips_dssvs.o ../../libcrypto.a
+
+Q=../testvectors/dsa/req
+A=../testvectors/dsa/rsp
+
+fips_test: top_fips_dssvs
+	-rm -rf $A
+	mkdir $A
+	./fips_dssvs prime < $Q/prime.req > $A/prime.rsp
+	./fips_dssvs pqg < $Q/pqg.req > $A/pqg.rsp
+
 lint:
 	lint -DLINT $(INCLUDES) $(SRC)>fluff
 
diff --git a/fips/dsa/fingerprint.sha1 b/fips/dsa/fingerprint.sha1
index 8fb34544d9..9bc57da539 100644
--- a/fips/dsa/fingerprint.sha1
+++ b/fips/dsa/fingerprint.sha1
@@ -1 +1,2 @@
 SHA1(fips_dsa_ossl.c)= eb769361b524507754bcbfbda92b973e37433478
+SHA1(fips_dsa_gen.c)= 07c884d8f11b41ae7f4bce4803ae918e25f05680
diff --git a/fips/dsa/fips_dsa_gen.c b/fips/dsa/fips_dsa_gen.c
new file mode 100644
index 0000000000..69501803a9
--- /dev/null
+++ b/fips/dsa/fips_dsa_gen.c
@@ -0,0 +1,298 @@
+/* crypto/dsa/dsa_gen.c */
+/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
+ * All rights reserved.
+ *
+ * This package is an SSL implementation written
+ * by Eric Young (eay@cryptsoft.com).
+ * The implementation was written so as to conform with Netscapes SSL.
+ * 
+ * This library is free for commercial and non-commercial use as long as
+ * the following conditions are aheared to.  The following conditions
+ * apply to all code found in this distribution, be it the RC4, RSA,
+ * lhash, DES, etc., code; not just the SSL code.  The SSL documentation
+ * included with this distribution is covered by the same copyright terms
+ * except that the holder is Tim Hudson (tjh@cryptsoft.com).
+ * 
+ * Copyright remains Eric Young's, and as such any Copyright notices in
+ * the code are not to be removed.
+ * If this package is used in a product, Eric Young should be given attribution
+ * as the author of the parts of the library used.
+ * This can be in the form of a textual message at program startup or
+ * in documentation (online or textual) provided with the package.
+ * 
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ * 3. All advertising materials mentioning features or use of this software
+ *    must display the following acknowledgement:
+ *    "This product includes cryptographic software written by
+ *     Eric Young (eay@cryptsoft.com)"
+ *    The word 'cryptographic' can be left out if the rouines from the library
+ *    being used are not cryptographic related :-).
+ * 4. If you include any Windows specific code (or a derivative thereof) from 
+ *    the apps directory (application code) you must include an acknowledgement:
+ *    "This product includes software written by Tim Hudson (tjh@cryptsoft.com)"
+ * 
+ * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ * 
+ * The licence and distribution terms for any publically available version or
+ * derivative of this code cannot be changed.  i.e. this code cannot simply be
+ * copied and put under another distribution licence
+ * [including the GNU Public Licence.]
+ */
+
+#undef GENUINE_DSA
+
+#ifdef GENUINE_DSA
+/* Parameter generation follows the original release of FIPS PUB 186,
+ * Appendix 2.2 (i.e. use SHA as defined in FIPS PUB 180) */
+#define HASH    EVP_sha()
+#else
+/* Parameter generation follows the updated Appendix 2.2 for FIPS PUB 186,
+ * also Appendix 2.2 of FIPS PUB 186-1 (i.e. use SHA as defined in
+ * FIPS PUB 180-1) */
+#define HASH    EVP_sha1()
+#endif 
+
+#ifndef OPENSSL_NO_SHA
+
+#include <stdio.h>
+#include <time.h>
+//#include "cryptlib.h"
+#include <openssl/evp.h>
+#include <openssl/bn.h>
+#include <openssl/dsa.h>
+#include <openssl/rand.h>
+#include <openssl/sha.h>
+
+DSA *DSA_generate_parameters(int bits,
+		unsigned char *seed_in, int seed_len,
+		int *counter_ret, unsigned long *h_ret,
+		void (*callback)(int, int, void *),
+		void *cb_arg)
+	{
+	int ok=0;
+	unsigned char seed[SHA_DIGEST_LENGTH];
+	unsigned char md[SHA_DIGEST_LENGTH];
+	unsigned char buf[SHA_DIGEST_LENGTH],buf2[SHA_DIGEST_LENGTH];
+	BIGNUM *r0,*W,*X,*c,*test;
+	BIGNUM *g=NULL,*q=NULL,*p=NULL;
+	BN_MONT_CTX *mont=NULL;
+	int k,n=0,i,b,m=0;
+	int counter=0;
+	int r=0;
+	BN_CTX *ctx=NULL,*ctx2=NULL,*ctx3=NULL;
+	unsigned int h=2;
+	DSA *ret=NULL;
+	unsigned char *seed_out=seed_in;
+
+	if (bits < 512) bits=512;
+	bits=(bits+63)/64*64;
+
+	if (seed_len < 20)
+		seed_in = NULL; /* seed buffer too small -- ignore */
+	if (seed_len > 20) 
+		seed_len = 20; /* App. 2.2 of FIPS PUB 186 allows larger SEED,
+		                * but our internal buffers are restricted to 160 bits*/
+	if ((seed_in != NULL) && (seed_len == 20))
+		memcpy(seed,seed_in,seed_len);
+
+	if ((ctx=BN_CTX_new()) == NULL) goto err;
+	if ((ctx2=BN_CTX_new()) == NULL) goto err;
+	if ((ctx3=BN_CTX_new()) == NULL) goto err;
+	if ((ret=DSA_new()) == NULL) goto err;
+
+	if ((mont=BN_MONT_CTX_new()) == NULL) goto err;
+
+	BN_CTX_start(ctx2);
+	r0 = BN_CTX_get(ctx2);
+	g = BN_CTX_get(ctx2);
+	W = BN_CTX_get(ctx2);
+	q = BN_CTX_get(ctx2);
+	X = BN_CTX_get(ctx2);
+	c = BN_CTX_get(ctx2);
+	p = BN_CTX_get(ctx2);
+	test = BN_CTX_get(ctx2);
+
+	BN_lshift(test,BN_value_one(),bits-1);
+
+	for (;;)
+		{
+		for (;;) /* find q */
+			{
+			int seed_is_random;
+
+			/* step 1 */
+			if (callback != NULL) callback(0,m++,cb_arg);
+
+			if (!seed_len)
+				{
+				if(RAND_pseudo_bytes(seed,SHA_DIGEST_LENGTH) < 0)
+					goto err;
+				seed_is_random = 1;
+				}
+			else
+				{
+				seed_is_random = 0;
+				seed_len=0; /* use random seed if 'seed_in' turns out to be bad*/
+				}
+			memcpy(buf,seed,SHA_DIGEST_LENGTH);
+			memcpy(buf2,seed,SHA_DIGEST_LENGTH);
+			/* precompute "SEED + 1" for step 7: */
+			for (i=SHA_DIGEST_LENGTH-1; i >= 0; i--)
+				{
+				buf[i]++;
+				if (buf[i] != 0) break;
+				}
+
+			/* step 2 */
+			EVP_Digest(seed,SHA_DIGEST_LENGTH,md,NULL,HASH, NULL);
+			EVP_Digest(buf,SHA_DIGEST_LENGTH,buf2,NULL,HASH, NULL);
+			for (i=0; i<SHA_DIGEST_LENGTH; i++)
+				md[i]^=buf2[i];
+
+			/* step 3 */
+			md[0]|=0x80;
+			md[SHA_DIGEST_LENGTH-1]|=0x01;
+			if (!BN_bin2bn(md,SHA_DIGEST_LENGTH,q)) goto err;
+
+			/* step 4 */
+			r = BN_is_prime_fasttest(q, DSS_prime_checks, callback, ctx3, cb_arg, seed_is_random);
+			if (r > 0)
+				break;
+			if (r != 0)
+				goto err;
+
+			/* do a callback call */
+			/* step 5 */
+			}
+
+		if (callback != NULL) callback(2,0,cb_arg);
+		if (callback != NULL) callback(3,0,cb_arg);
+
+		/* step 6 */
+		counter=0;
+		/* "offset = 2" */
+
+		n=(bits-1)/160;
+		b=(bits-1)-n*160;
+
+		for (;;)
+			{
+			if (callback != NULL && counter != 0)
+				callback(0,counter,cb_arg);
+
+			/* step 7 */
+			BN_zero(W);
+			/* now 'buf' contains "SEED + offset - 1" */
+			for (k=0; k<=n; k++)
+				{
+				/* obtain "SEED + offset + k" by incrementing: */
+				for (i=SHA_DIGEST_LENGTH-1; i >= 0; i--)
+					{
+					buf[i]++;
+					if (buf[i] != 0) break;
+					}
+
+				EVP_Digest(buf,SHA_DIGEST_LENGTH,md,NULL,HASH, NULL);
+
+				/* step 8 */
+				if (!BN_bin2bn(md,SHA_DIGEST_LENGTH,r0))
+					goto err;
+				BN_lshift(r0,r0,160*k);
+				BN_add(W,W,r0);
+				}
+
+			/* more of step 8 */
+			BN_mask_bits(W,bits-1);
+			BN_copy(X,W); /* this should be ok */
+			BN_add(X,X,test); /* this should be ok */
+
+			/* step 9 */
+			BN_lshift1(r0,q);
+			BN_mod(c,X,r0,ctx);
+			BN_sub(r0,c,BN_value_one());
+			BN_sub(p,X,r0);
+
+			/* step 10 */
+			if (BN_cmp(p,test) >= 0)
+				{
+				/* step 11 */
+				r = BN_is_prime_fasttest(p, DSS_prime_checks, callback, ctx3, cb_arg, 1);
+				if (r > 0)
+						goto end; /* found it */
+				if (r != 0)
+					goto err;
+				}
+
+			/* step 13 */
+			counter++;
+			/* "offset = offset + n + 1" */
+
+			/* step 14 */
+			if (counter >= 4096) break;
+			}
+		}
+end:
+	if (callback != NULL) callback(2,1,cb_arg);
+
+	/* We now need to generate g */
+	/* Set r0=(p-1)/q */
+	BN_sub(test,p,BN_value_one());
+	BN_div(r0,NULL,test,q,ctx);
+
+	BN_set_word(test,h);
+	BN_MONT_CTX_set(mont,p,ctx);
+
+	for (;;)
+		{
+		/* g=test^r0%p */
+		BN_mod_exp_mont(g,test,r0,p,ctx,mont);
+		if (!BN_is_one(g)) break;
+		BN_add(test,test,BN_value_one());
+		h++;
+		}
+
+	if (callback != NULL) callback(3,1,cb_arg);
+
+	ok=1;
+err:
+	if (!ok)
+		{
+		if (ret != NULL) DSA_free(ret);
+		}
+	else
+		{
+		ret->p=BN_dup(p);
+		ret->q=BN_dup(q);
+		ret->g=BN_dup(g);
+		if(seed_out != NULL) memcpy(seed_out,seed,20);
+		if (counter_ret != NULL) *counter_ret=counter;
+		if (h_ret != NULL) *h_ret=h;
+		}
+	if (ctx != NULL) BN_CTX_free(ctx);
+	if (ctx2 != NULL)
+		{
+		BN_CTX_end(ctx2);
+		BN_CTX_free(ctx2);
+		}
+	if (ctx3 != NULL) BN_CTX_free(ctx3);
+	if (mont != NULL) BN_MONT_CTX_free(mont);
+	return(ok?ret:NULL);
+	}
+#endif
diff --git a/fips/dsa/fips_dssvs.c b/fips/dsa/fips_dssvs.c
new file mode 100644
index 0000000000..2fba010b34
--- /dev/null
+++ b/fips/dsa/fips_dssvs.c
@@ -0,0 +1,136 @@
+#include <openssl/bn.h>
+#include <openssl/dsa.h>
+#include <string.h>
+
+int hex2bin(const char *in, unsigned char *out)
+    {
+    int n1, n2;
+    unsigned char ch;
+
+    for (n1=0,n2=0 ; in[n1] ; )
+	{ /* first byte */
+	if ((in[n1] >= '0') && (in[n1] <= '9'))
+	    ch = in[n1++] - '0';
+	else if ((in[n1] >= 'A') && (in[n1] <= 'F'))
+	    ch = in[n1++] - 'A' + 10;
+	else if ((in[n1] >= 'a') && (in[n1] <= 'f'))
+	    ch = in[n1++] - 'a' + 10;
+	else
+	    return -1;
+	if(!in[n1])
+	    {
+	    out[n2++]=ch;
+	    break;
+	    }
+	out[n2] = ch << 4;
+	/* second byte */
+	if ((in[n1] >= '0') && (in[n1] <= '9'))
+	    ch = in[n1++] - '0';
+	else if ((in[n1] >= 'A') && (in[n1] <= 'F'))
+	    ch = in[n1++] - 'A' + 10;
+	else if ((in[n1] >= 'a') && (in[n1] <= 'f'))
+	    ch = in[n1++] - 'a' + 10;
+	else
+	    return -1;
+	out[n2++] |= ch;
+	}
+    return n2;
+    }
+
+int bin2hex(const unsigned char *in,int len,char *out)
+    {
+    int n1, n2;
+    unsigned char ch;
+
+    for (n1=0,n2=0 ; n1 < len ; ++n1)
+	{
+	ch=in[n1] >> 4;
+	if (ch <= 0x09)
+	    out[n2++]=ch+'0';
+	else
+	    out[n2++]=ch-10+'a';
+	ch=in[n1] & 0x0f;
+	if(ch <= 0x09)
+	    out[n2++]=ch+'0';
+	else
+	    out[n2++]=ch-10+'a';
+	}
+    out[n2]='\0';
+    return n2;
+    }
+
+void pv(char *tag,const unsigned char *val,int len)
+    {
+    char obuf[2048];
+    int olen;
+
+    olen=bin2hex(val,len,obuf);
+    printf("%s= %s\n", tag,obuf);
+    }
+
+void primes()
+    {
+    char buf[10240];
+
+    while(fgets(buf,sizeof buf,stdin) != NULL)
+	{
+	fputs(buf,stdout);
+	if(!strncmp(buf,"Prime= ",7))
+	    {
+	    BIGNUM *pp;
+
+	    pp=BN_new();
+	    BN_hex2bn(&pp,buf+7);
+	    printf("result= %c\n",
+		   BN_is_prime(pp,20,NULL,NULL,NULL) ? 'P' : 'F');
+	    }	    
+	}
+    }
+
+void pqg()
+    {
+    char buf[1024];
+    int nmod=0;
+
+    while(fgets(buf,sizeof buf,stdin) != NULL)
+	{
+	fputs(buf,stdout);
+	if(!strncmp(buf,"[mod=",5))
+	    nmod=atoi(buf+5);
+	else if(!strncmp(buf,"N= ",3))
+	    {
+	    int n=atoi(buf+3);
+
+	    while(n--)
+		{
+		unsigned char seed[20];
+		DSA *dsa;
+		int counter;
+		unsigned long h;
+
+		dsa=DSA_generate_parameters(nmod,seed,0,&counter,&h,NULL,NULL);
+		printf("P= %s\n",BN_bn2hex(dsa->p));
+		printf("Q= %s\n",BN_bn2hex(dsa->q));
+		printf("G= %s\n",BN_bn2hex(dsa->g));
+		pv("Seed",seed,20);
+		printf("H= %lx\n",h);
+		printf("C= %d\n",counter);
+		}
+	    }
+	}
+    }
+
+int main(int argc,char **argv)
+    {
+    if(argc != 2)
+	{
+	fprintf(stderr,"%s [primes|pqg]\n",argv[0]);
+	exit(1);
+	}
+    if(!strcmp(argv[1],"primes"))
+	primes();
+    else
+	pqg();
+
+    return 0;
+    }
diff --git a/fips/fips_make_sha1 b/fips/fips_make_sha1
index d1bdd65684..7cb167591b 100755
--- a/fips/fips_make_sha1
+++ b/fips/fips_make_sha1
@@ -18,7 +18,7 @@ cd ../aes
 $S fips_aes_core.c fips_aes_locl.h > fingerprint.sha1
 
 cd ../dsa
-$S fips_dsa_ossl.c > fingerprint.sha1
+$S fips_dsa_ossl.c fips_dsa_gen.c > fingerprint.sha1
 
 cd ../des
 $S fips_des_enc.c fips_des_locl.h > fingerprint.sha1
diff --git a/fips/sha1/standalone.sha1 b/fips/sha1/standalone.sha1
index f09e843bec..5c60da0ae9 100644
--- a/fips/sha1/standalone.sha1
+++ b/fips/sha1/standalone.sha1
@@ -1,4 +1,4 @@
-SHA1(fips_sha1dgst.c)= 609e2cbf5d3cdcf318ec10238a0e82b93b78e6b5
 SHA1(fips_standalone_sha1.c)= 74df91daa6670c9989b9395492a4b2627d115574
+SHA1(fips_sha1dgst.c)= 609e2cbf5d3cdcf318ec10238a0e82b93b78e6b5
 SHA1(fips_sha_locl.h)= 677427c495b571991f013939ea7e5dea87828f8c
 SHA1(fips_md32_common.h)= 4f41bcde24750b3b8c99a06bcba2fe06ff8db4d0
diff --git a/fips/testvectors/dsa/req/pqg.req b/fips/testvectors/dsa/req/pqg.req
new file mode 100644
index 0000000000..d3266772b0
--- /dev/null
+++ b/fips/testvectors/dsa/req/pqg.req
@@ -0,0 +1,20 @@
+#  Configuration information for "OpenSSL FIPS Cryptographic Module"
+#  Mod sizes selected: 512 576 640 704 768 832 896 960 1024 
+[mod=512]
+N= 15
+[mod=576]
+N= 15
+[mod=640]
+N= 13
+[mod=704]
+N= 9
+[mod=768]
+N= 7
+[mod=832]
+N= 6
+[mod=896]
+N= 4
+[mod=960]
+N= 3
+[mod=1024]
+N= 3
diff --git a/fips/testvectors/dsa/req/prime.req b/fips/testvectors/dsa/req/prime.req
new file mode 100644
index 0000000000..ac39ab3678
--- /dev/null
+++ b/fips/testvectors/dsa/req/prime.req
@@ -0,0 +1,86 @@
+#  Configuration information for "OpenSSL FIPS Cryptographic Module"
+#  Mod sizes selected are: 512 576 640 704 768 832 896 960 1024 
+[mod=512]
+Prime= ef37b140f287e1958a9509d0c7bea5798ab11719c8d0a90e32f3c10f265ea3e24c34cd2ca899a4cd70e23cc335422a0435f92bff5b5d6f204c2c5bfb19a5b965
+Prime= fb1ab1810041c62af6e5174f3eeb078710f13776955eddb4b37308fea8c72e2ed0783639b598f8f736e05517f36cf93ce5f27f0f1cc93f49e2d3718e2fb7e04f
+Prime= f7817a850c8000918ec8837615ce6864b8a71c3ecf3f59e073544312788e5e33d342009d159abf3024e9c6866e566893a4ae3517f39d4930c81c41b6530d8189
+Prime= f97bcbfc752c218f753c001a0bf78f8c59d5a1518584800ab60116c812c94e928fa06bfb9334c5edeab66ba21422db4cb26c25eaba00bd45344e8a0d4ceca0a7
+Prime= 94a5473dc9a47c6950d94a680bfe45ee03882040468d47d5e6bc8dbbdd9cc6daaa67f5f82f555a1ee5265926dce131a76c49dba51dc419c17d9721d10fdd494f
+Prime= 802cd608b11c0e56723bf7326a0f6656f41e005535272968ef807e794983251a33c72c7042d264ccf213399512738fc973ba32b9919d45b99be0a5d5c7b9c443
+Prime= b7d595a475dcae68fe687b408f80feb08c4c51ca7b9c334e00621001e869a6dff6ed75a24b16dc2d161a9f0a33a350ed10abe0f740c2a71166c63842b126dc65
+Prime= e3063abec7a1a51d4f46c3fb748a82cbce0d90aaf756ce9b392b2ff2044c676f218f4b5d9bf0d37cba86ce5ae362d5f08d8c3feefc99be243f15df1865b90f61
+Prime= d64639d2bdc6661287cff99a549b90d73ea0f3bb18aad0c24dc99631de2745387ae6df34df8d73d8d5b6522822724db1d9706ddca82d255f361846a518f8d6d5
+Prime= e10d8d7ac60248d265425904be877bfdba44321cdac21e5928387d5663797f0debeb1980e4fd6f33680f8a5eefeeba587d2aa532f8482687b50b606dd666d22b
+Prime= fc2e924867c5b45ba194f47125045bd89ef8d393f0bdf9bcc0ca01cfc2ad794e792d0ae78fdb2fe4146dbae9020a01f153bcbeeb7e30a8a8ca47ef1bc567d243
+Prime= 97d0ffebe0ac05857d6231ba07fe7b8a6d8e2a1487d5958090db28d6fb9a0552d1302ac28824baaebb839cd3463c1aca65d1b94e4a12d2b09c0e66c8081727f3
+Prime= c761900df45575da50f8b607e0169bcbbfc98cad52436d707292cb32496bc5f7b4dbeaf260b24b673bbf384ccb66d217a48a4543774d1ea1cb670a68c760d701
+Prime= 8ca896fe246c6ec9b0059ff478ad558ff3da6e97a1d0d994d008769b9ab3d257bb72cd64bb5853e358e96929394cdc6c0725461193d2d7058580371c84d95b09
+Prime= 9a97ce075f3fe7f48306a6810cf419b1eb2c083968460b9bdb568bf340aae2e6ad9d2ea6d203d9965254678cce65182f6fc8e5adbf708c58e51c514271b2c357
+[mod=576]
+Prime= e3ac2e1264ab57bac2a5cc330e14ffd28a3843202b707bd0dfef2e561168a2d54618a683ff03d26758d27c0a254b5f46be04ad3050eb68dbc4f4931c53bbe106bc990039dd111769
+Prime= fe1c0ab9d6becc015ebaba3b41b7f7dba11eef08d42ffabd76197b76056dc21910f2f54dceb133a6e68e54dedc3c89a8aafa7027c204a87ca541eb79b823a9326d5048d071912383
+Prime= c7c9bbb397313ba7e8eaddbb5b8e450c916839163d5123715fbab01a13441ebf7fc89c85e96b621e5aae309c12b9c47b8c57fc1e66e8599cace716e802dcc993088799cb3b0f5983
+Prime= e88e7c15998acfbc94cf60a7e23ba374cad951a6e02ba3fd4b5bf83eee352dee5b1e5ef79377c9b036ef12391ca9a49f579631273f52f705c12e260ba68becc7e611a1aaaeddb96b
+Prime= 94b175345a73f4a01bfc02d871d8e8de4aa08c78974824db4c2b9bb7f2a2bf238457354307aedff842844916d1c9ec88145694833938b81ec21927a153b9f0758b2a2676cb32d137
+Prime= ff11dbc74607b4c1e7479fe13cd3765b49d68d088d4981e0319b9b6279705dc1cc2b281847fc9e74b8113f95f65d45d9019da36f25ed1d3795c1ce5e014f13d36ee863c97a996d05
+Prime= 893953147807f766833b9ca49e73b92d092b7d838d9749a626db3372b12248b2f6b4ae8636a74010fefc9a84b00077cf783fc1bbc7fa3b8cafb1cfa7f54ce248d88afc4c74672ff3
+Prime= 8b9e79167e1f2f4e03c4e368d52c7470b684959e90fc16613bbea2fee92185bab0b82c76f1da166efb64da2f5623a9e67f032f2242c6e7301c6d96d124063f0ec517a7f51c21ffc3
+Prime= 8a83493f9eb5ab1a8f92ea4f868ff2ce5f2d062a49368fddffeb07053c44b7e5df436afa3ba1721579efc4f7946386c2a8f07e9bedd17ee8169f43776fb5faab7b82a18f6c3dca23
+Prime= a3c608bb1ae0b49c2ecc3e134bd74dcff077717b49a8c55c2337f962f2f5909c269cf1da1e1f3ce8a76412ad73a817942b0f33eade22add16153b7398fe28156172c21203ae9a19d
+Prime= e23222456407449ebe4c9548183908e84f703d79248684240c465a46bad2a370500aeb3163efd8eca00f41d7e250c784e67cb11888411c08b7084a012848184021a1246b2e5ebdd5
+Prime= d46a4bdd24754bf139a562a5c010def7d23d723d5d97b757613467285f526084efea11e2665433ea8e586c57e0203a6f189114ce06b0f8ba47c032e2b1df022b89bb8b4da12ecff3
+Prime= b5394d8866249ad5ceb47f8e637d789eccee9b6cf0fc4c22b3fba2913fdf8098ed3a838951bbc2af83c85ca31b52a37b789787ee9d1eb634afa51732cc52ffbe701e6915a89dcff9
+Prime= 92b81c52a6bb29f40b1ddcc1c5df00c5fb2381352379113ecf32bd461a6c55894450f20417797ca681a3f60ca4c9b3030a382ed4fb29820708ae8629df0138805c40cd244283c56d
+Prime= c0aa45180605bcc063de0bf99e4324db38f8f630dbefa19e961c36cb9a39efc16c2019a8b4e43306bed254be0f983b537a5b1c5eb51f8ba3da21fcc96846d716858f51ce9ab24c33
+[mod=640]
+Prime= bf30f1132bd4163fc59e2919d37220961d94ab1a418c076bba48b213281913575865acbe97bf209fde3b9b296c2546e7ef1f042eef08e0b6dbd4f665b5d2a5c79dd33b13e3b34d091e693abecec061ed
+Prime= c518a81c8c02f434198839a47cbdf6333fb76b24b910c3d94a0864f50aff8f6f32f5831c43d6a4903fd5c835f939804ca80d9c7808126d93c352134474748127a0f876fdbeb29c97c94d1a456167f759
+Prime= ec2c06d1248bb3eb12718b8e927c141ddf18a6028514898189d50c7d129c007c611b61051215a8b0d0f9ea4f8a0ea0314af8d1640df0040fc607e52acdfd10f6453c9faa9333abcc64458dcd32b8b16b
+Prime= 993b92b2a260b4e937c5a924664e48bbfb1fa110f4c22a7e5161f1e5e3c4f35e87c1fc37c3a04ee6242efe19be071b88f3f203c8753327a1d1d57883ab7e06ddb3b05158f1eaa065182a3b1c10910b69
+Prime= d976a11b01046f7ef0c04cbd3ecd786bf6f91544f7893a9314c69175208857e0a2948f78f35ed9be0cc432839343481cb234b1915d7fd8c55d366427e7df6a27277e36cd74d71812a2d3f5c6b1a09167
+Prime= f57a8afe2d63999e574e7d58f516eca74cbc36260c516669737717132c9970c9610ed21c29856298d25159a78fe0709f30bd592c73573a15ed1c5aa2b16952c5e31226268f6fa47b73b24bf60d939b53
+Prime= c4e35cb1142a9a0c36628943a824a42f7135fbad41d0d99df300a67262e2fd0ed4a12f6e5b8c5f6ec16aa24604aa8c569760747c8103b3b4e65121a33dafc94924de3754e080f8ed17fdc273a44250e5
+Prime= 8e652546ebe5c0414c0fe863e7ce2b140403df9f86f44751d406889397af547fe8fa7c9cf38eeee75a9132ad6f26475059ad70c47cf19f5d05097a68593045cbbf7c11b24bd55c4ed22fde62698ed75f
+Prime= fee267ff4e3479a61c4f42ca265917acbeb986e80f5438389693c64832acbe9df517d215777c20150b932717f7bb459ea2c773eb8153dd6f29261a7a47a5969c045225e3612b147c7ea6da819fc03171
+Prime= a1e2ec8883a79b7162e2fcef4f641fbdbdb416f0619011d25909dee3b68963850352b9cddc4ee8ef90cb123d4aee2ff605c189bdb57476e9252219fde09e69679ac354584396d57fb441181d0d6846ed
+Prime= e0f981f9220716a229afaae0bc2c82c6968455baab74538a8412524b1793d5b3de614b788015a17e4a970bde5243c5bcbbcacaa2c6fdf5332efe736669eb312d0adc8f561b119ef4c40df7531329a50f
+Prime= dc63210e2db090ddc3aece02c78c72f012a1bcce822d3309d551ec56fdab28a68b1264101acbf8b6338c813b7dcff969eed609b447d33a994b0622e66995be76f2aa078c7f7dba2ff0b545ef8d05d843
+Prime= bec017126ceb1369026646dd0be0c859c7a3342fb6cc02a22d5c750f4a3a3da8b200409011a20a7f70f6ada6ed67eed4b0c1bbcf557f9f8fb9a40b4fdb82aa90fdba010d776e631787d82967c0bdee19
+[mod=704]
+Prime= 80c889e92e4b9e695ff73bcb4e583edb31ce791dbe448ada8afc371b6170cbc87fa613b6515618f5f9256c50c102e8814f19d7867915ce74664fa27296e748c0e66a8cc82acaaec21ab86ae8f5509f4484ae36683cf52483
+Prime= d0da00ccb3a7464091d7bce54cd8d931eab4549c706269a110e7e5c1a185e16e0582520fcd772fac0c1ddedcd3ac483ec73fdb123ccdc65364648baa8b8fa8a0e1e2f2c34d15abc9b60f29af697e7f025539216ee2c20b31
+Prime= 8dd691fd6573f37d3102d0e25470a19b0f33736053e0e9e3df298f48cfce6f35c0b35cf2f2ce7f3e72f71f5efcd50330c5190b2d860675de02b56282df67652f26fd1a885d41b2b64e3253a23c6eb09e053caaf788351b67
+Prime= ab65341fabd3d9031af67152aa7960ade10db3b910ef44f1cc2dc067e231c15ca0027671654f222d3d06e9a8c98bbcd2ff8da83bcce048cf2658bcdcdd1c871fd27e0b5fbbc15dd39c62b1fedee1264a0f8db1b8dbd0fb21
+Prime= dc27533747998f3c17079800d03ac9117b5ef2e443e6b4e5fb03531d2aa63e19ba757eb1af6d66697866b1c024171d5d2b0fcb69f83fd7cf8cf2b27bd7d5d00f55d4f5895e286d39ff879ea26d5cbce5c7d92537fb2ec773
+Prime= fee205aa567ce27c42bcf4be1ac6d524c980f4f8f3479fa2586bc9d6adf63d48e0f0b4eef00adfbd9e770ad5ab0fdf5c6184831accacf0ba8b1ac6cdb0fd0957df64ed959d897c3c4ed5af071c45e4d70b28c0f5c9272e21
+Prime= b4d2340c866ddff204ad50da612d9c1a7e24ffa0a30fbaaa1d019526a08924bda1ef202e0655693ca8cb3746c8f2a6eef4add287368a81360b38bcc93242d53ec5f3932dacc1462bc7539c5f8e88e834aa5a02ac39ca8447
+Prime= cb5bf83eee352dee5b1e5ef79377c9b036ef12391ca9a49f5796312881ebbdeb9d5f7fa86155c2808462b4270bee3c852817c2a59ef74ba571e6b733b7c58a9c9c4d9b85a7de78cc93acd49d6db04baf54dcfebd373947f7
+Prime= fe03daf544a50d2060ddd4c348800b9434697d2e6d8a8773e7633ea75dbfc250bc651032bbeca571ddfdb1fec1f9b3c94c26863626f33c3e35a707c3142f2218b16f0d01badc544ee9600980b4ed3f518f4201596b6af007
+[mod=768]
+Prime= f9bba0c002e2883a0de58fc82a57653dbe250064a127fbb842e8778eae9e46b44b414a81020dbde15bd99126564d513b7cba72eb2ccb53dfeb4b308a685a8521b64b85f976a24f87fbf6a39454e4b16789cc055cfbf34ebd540837fbe52e6a39
+Prime= a3f6e111b12aa3ec2d124f1a57d295f12001f569c661a6ba82298b853d39d9b88ddaaa96bf4e320ebbc3c50ddfe5e4d1b6e249cde3943d1443facdc31ff64168327aa3c32250bdfd98320ee49cea59ffa61873c031b87103097ef8cce5970f51
+Prime= c3e69ad672ee56a309c322900f636545ec8847f5d63fcaf303531c79485cbe809729f8bea99c027f571bdb2043c742749ceefc9eb0e20c1e1b10b4bb1ab67985c2c7c7efe41da6d5b297ce654a77cfe5670de53ec84bd9d7f9638430445c6deb
+Prime= f3472312a4ca35cd37641b98f327fa6817ac9fbc79d58f5f16939b540fb596f2a9fc7cc48d518c258b182a8687d096a0d93455005b01e83831071c6d3b80b5952665feec53c37769b39de17a5baffed612291f7726477b826476be680625076d
+Prime= eea19ebd063028bef6f3e38061694f358a17716bcc196076717bc25ddec3e4d3473a5b660f3424cd551cc66549ec826742bcd8014cab19b319ea43fd113baeffed64b0d8ed85cc8ddb0ebbe427d3e55581ca22df55dd82103ec2521736181741
+Prime= 98f30150769dad70ebd891cad5c8486b1e49385d140b5b6edc156db0dbcc5e921adfb7704a294be8d52952fa660d5c26710e18961576fcd1f10155742a3b6c7482091a827f7ca08b19141f6cdc22c4c7f03966572c953cdcc260fef39a362d75
+Prime= 8d1bacb1b8fe1d032a3ad58b12ec6c5a41bc94f3d0d77aa7298a10d56deaedf67136965b2ffc0f1d268b1e14f25850f5f48bb94fd19824eb3c70eea7b654af9b3eb7b873f7d649210c40f22e3a99df9d530899038a5d2041069917686e091103
+[mod=832]
+Prime= edf3fc06f94d16617c3e1ccab973485d5b418d3cb60e5579c9427472312af25d449b5cf0836169d019fbf03dd01a2c23eb183cb6a44fb16a8ce674f04e244b146a69eb8c253ecad4180a2f035533c5da68668fc38eccdba980364e3b77bb4df0f84ab21ef1c335cd
+Prime= f4fa3cfeb339c3398cb3bc75e8325ddfca0ea980a264c80b3c6a06e4fbc9df27c421f702ce4e2687aa738e2b9100eb15f234e4af028ff0dbf6dcf0ba4d7009b39100f7100de7183cd693cb4dae5247cdea82afaa20d5d4d6bd329c169a97efa449880a4c40d5cb2d
+Prime= 8004f1c6b65c730f7da6165d54d590680efa5e306e6e3b400acde5f08b4ec51a78178c351e3981871d1c46c727d362849dc4331224c72814405df2358b46bd46d137eda0db160970af8ab7d44dd76188c36092966254bc9ed986dbb8da56587f0ce533dacda0d98d
+Prime= cdeead4e1afce22b98ff9f195569f886c0636a1a04d16c5aa57f8bb967707080ca06d2207c5e86d74f140711c04d00c5a8b6987e8f8e497f9b55c7d4da9245b95c1e51e4a4e0e9b64b069987c600307a5ba32ac6228c613d82b5c56364b4e44fb322b2ac5ca5fe83
+Prime= f154110fc692f9b2f03e970757c9d828dbd797191566296bfaa02e15b1af1df31e0b8c02c3745e151905f9ce139fcd567c43e8a69968d283d2f394b369572f82ebdfe6888d09b93f03fb35cb57f1c9a625178adfb79407a7fd86dda7802043a415b5d8cc3e9da883
+Prime= fde1fadf7d89831736a92f28a590ee20fed1edda15c7b72d85a7ffa3d8e8bda9d9a64b41ecf877cff146925be1fce18ca01dae130191c19eb0bf7d1414a1f6dd1f970bc21828b0811586c4e99f7871d91bb816f6e9973275c486a3d3360aa0f7d4b357ca7cfe007f
+[mod=896]
+Prime= e71771e26c7f14cef0572b53454177d692a12a7b4f34b27603d9bb67c64dbe6185ab05ca24f3b6fb427a156da170474fcdee5452d93dc616feef7ca6e54e182c608d30243d1faf8d064b866b04396f4d692d78f2d8926dda49e0de398a75e2845dfe63ead69c894bc4e4fba045376b83
+Prime= c71c72bdde589979d10a2a63b11249c7983b1377ff7d24ffa521b1e3a8ab6f7cfc5a4efa77595f98ca1b2f15ad7f410d63dea0aafa1a0cdd863cea63e9fa07f9d42372e557d976e55e3ac4c0d23876d95c742d4b39a433c521cba132241aa864b1ef4f929007b9098f3208377f7ff82d
+Prime= 9aadfd94ca25595bbfa3ecb783cb1076095f0a3f583114e3fd0ec837f630aba217d4e4eeca4162509099dd7a4558058dfbf29633169618326e919fea6538c8b92b4827b9acee113c8f170c5765db215d6599428e3b19db1b3990eb2f64c8b5b24d3804ce3bc84859bda3d9300d092e65
+Prime= a946c8c3d0d96a4b6ef8e423b808639829167d58bbdcb00a535e1198829160c2be34527fc11f47956d8231b2f6cf50b2e2a24be4a36481936334cc4a074b2c99159e633cfaab7feec3c65fabad36f8508b2290e4e651f230ad3223fd406da1a6ca96fc0a74057030ec1f5bcd52398de5
+[mod=960]
+Prime= b5124ff28d9aa05937246cd173290e07f4fd03c6dd406e0d2db64c74f7ec146d859898338cfec1d7cc7f0a59ace80768800907cd2f0063819acf3e12cb87ae6de0c3d51e4c59c44ba0e33dea0d706e22390ffe7041b97a8612a845ed976b988ed0c41c26727710ba3e71d9d7907b6c6ca1dac2b1eb3abd03
+Prime= b13c989d09be9a60547cc0f2d212257af34f48d6860267b2108d57ab4afbc27761a54cbf0668f3de31c60d30e084641bcbea171fad369605632119e62f4ee91c6973e131d61a00f2db150879adebb01944d47395318cc1a20e6d12afceeb4e27c457da6bd2d2d9aca8b505a15217d6253ae4a54f16fd6445
+Prime= d94afec01613a46d5e86f43901901d2338a1357e8ba59a877fad4839cc92fea3ce643b6daef678763f55a0db5b650675585d8c7e84ba067b61a91f9d567f3e00a3f732cb0866f5b2173d791be112e61ebcc0dfd73877ad5f82457a3fc5c92e9b966658fd9a06fdf270e5956540eb18700f144051a2deb7e5
+[mod=1024]
+Prime= f1eda3e7c73a135d61080f9f54509bbddbc4cd2717cce9a92a6cbec57fa82bf7671594ea25f2525e2fdfd7a8c3206972430b42d20297e615ba7068b0c07673a6b34174eff0543fd67bde7a35b57658bd72f9ec7ef8b56d1103931089f3ab5003b84f0c5300deb1fdb2631ff0094bc037b04a5ff33069c51ef88b6a613b3eaf75
+Prime= a8c8945215954a71570443b87d3a0e6cc24567429cfdb68917a0c60c65e2fef14a66c1c94d23a88546e41d39118b58aeafe339be3b8977749a3a1b7f5f0fcc83c2b6796ec331b33e6f10b4d70ee82a56e4d16d4d5e3cac64b6de7abe5e357104660ff85f3edabaed3324dcf5d965f6c425a072a35c2161b49b00e7b4b5425a3b
+Prime= f4fab32eaece36943e0b7ced6663fa777527a8b462c9e0b8ca6542c007e9a0cc45d4f38e154e8798448f9cead4b7c8acea64aede994abb70fd0d8306818ce21c7636b5f5f7aacb863bd42ce520308c0748d7c1a3efcee8b546969053bee5a60a0561508cc04157e326f17c0c8ffb70dcd863e4d8cd9a1a63cf74b83f48f7bd39