From: Phil Karn <karn@unix.ka9q.ampr.org>
Date: Sat, 21 May 94 01:46:36 PDT
To: cypherpunks@toad.com
Subject: Some 1024-bit DH moduli, and a program to generate them
Message-ID: <199405210847.BAA10936@unix.ka9q.ampr.org>
MIME-Version: 1.0
Content-Type: text/plain


Here are some randomly generated 1024-bit Diffie-Hellman moduli, along
with the smallest generator for each. Each modulus p is a strong
prime, i.e., both p and (p-1)/2 are prime.

I've appended the generating program, which uses the GNU gmp
library. On a 486-66 DX2 running BSDI 1.1, it generally runs in less
than an hour though of course the actual run time is probably a
Poisson distributed random variable. It turns out that almost any
amount of sieving is worthwhile given the cost of the Miller-Rabin
test and that the density of 1024-bit strong primes is on the order of
only one every 500,000 or so. Before running this again I'd probably
decrease the large number sieve size to perhaps 1 million and make the
small number sieve as large as possible, rather than keep them the
same size.

--Phil


a4788e2184b8d68bfe02690e4dbe485b17a80bc5f21d680f1a8413139734f7f2b0db4e253750018aad9e86d49b6004bbbcf051f52fcb66d0c5fca63fbfe634173485bbbf7642e9df9c74b85b6855e94213b8c2d89162abeff43424350e96be41edd42de99a6961638c1dac598bc90da069b50c414d8eb8652adcff4a270d567f
Generator = 5

de9b707d4c5a4633c0290c95ff30a605aeb7ae864ff48370f13cf01d49adb9f23d19a439f753ee7703cf342d87f431105c843c78ca4df639931f3458fae8a94d1687e99a76ed99d0ba87189f42fd31ad8262c54a8cf5914ae6c28c540d714a5f6087a171fb74f4814c6f968d72386ef356a05180c3bec7ddd5ef6fe76b0531c3
Generator = 2

97dd36c5a63213d5c9a6ab0e1dac722053e6f398beb699dcbaa17368406c9efe2d2b29ccd78fd6faa497d096e07854ea57cf51a621c8a7f01175d39c9b25cda8225b3b4318cfa7d42cf81437272d8d4a8bbb8450fe257a0554bf3c9e53f3c8fdfd7f5effe88885ebd1c36b7e3216e3b19b65a42ea07fe53d4e403d0a3235307f
Generator = 5

97f64261cab505dd2828e13f1d68b6d3dbd0f313047f40e856da58cb13b8a1bf2b783a4c6d59d5f92afc6cff3d693f78b23d4f3160a9502e3efaf7ab5e1ad5a65e554313828da83b9ff2d941dee95689fadaea0936addf1971fe635b20af470364603c2de059f54b650ad8fa0cf70121c74799d7587132be9b999bb9b787e8ab
Generator = 2

fc642ddf24aa0d3fc50f4bac2f616d1e556c413373fcf4e1188f1f416473d2ac447abba857f8f8d3ab63ba9ee5762b47c59e3048e19f05d84a161e46d319c78fae02779fb6e35a165902633a76fefec77d75c0703818a37fb1bff6613b63ebac287449a9f8a101a3b33769f6cc7a3576f06283e1d45738a88380ee3e85607523
Generator = 2

d4bd8e44f0a05dcb319025b47ff7da8702665c3d1b2a8518a0d46073b499014b6ad8655569cd1655766747cb1e5e1a1fa8a275fd83bc02297784c00952d04bb6b50f79ba9befb1696a85908221a4765880d6dc0680d2ac5c136cfe694255972cebf1f1239beee5b168054ea2b2c08a91b6f22e8bf14153d26f69999a1782990f
Generator = 5

da76402bdddbb5dda51f79dae442fe010688b652825ffecb6a04ec6e368a95ef35e729bc30e947ce19d7fa6946c7939d6c62791d9ac705f1509d496e10fbc7795e8197129a09283f5faf8636152c151c5f3910b06e485456fae1df094cb4da07f86e67054be8f2f0b94010d91fcd7fb66d03c57e1bea80839d874856b567403b
Generator = 2

f47bddad1d4cf2f8c14985b954e6a9dbd79bd72ee40691c288d34e922a4ffd5486d39fec4e9f6dd64f0b6e9b16b628e44602f701e736d735996b03163f7c6a63152e3d0a7f04f5a6490f2b845340e015dc3c63bd5f9e7d3aaf4c49cc4fa97ff19fa8446ceb7dc2ab632cc6ebccce60163eb1b7930afbcbf077726ffce904a583
Generator = 2

c292efe525ea4315de43b0c620448009100cbf68a83c948f72809bee0c77c13e166fb6264355bcfb8c4457291f82f080bf6ca8328fa52c1b1e4a8cce696026222db8d1122923d2072bde6e373b6a92acfe1c5107512ffaadd35fe5ef74e61dc025436b3715d07bb382f8d2e114dabe57b8b574aeb20fb9d287105d98d130792b
Generator = 2

bd36e0fa98b48c678052192bfe614c0b5d6f5d0c9fe906e1e279e03a935b73e47a334873eea7dcee079e685b0fe86220b90878f1949bec73263e68b1f5d1529a2d0fd334eddb33a1750e313e85fa635b04c58a9519eb2295cd8518a81ae294bec10f42e3f6e9e90298df2d1ae470dde6ad40a301877d8fbbabdedfced5fe5fbf
Generator = 7

/* Generate a prime suitable for use as a Diffie-Hellman modulus,
 * i.e., (p-1)/2 is also prime. Also find a generator.
 * P. Karn, April 1994.
 */
#include <stdio.h>
#include <gnu/gmp.h>
#define	PLEN	1024	/* 1024 bits */
#define	SEARCHSPACE	5000000	/* Search range beyond starting point */

#define SIEVESIZE (SEARCHSPACE/2)	/* Sieve only includes odd numbers */

#define	BIT_SET(a,n)	((a)[(n)>>5] |= 1 << ((n) & 31))
#define BIT_CLEAR(a,n)	((a)[(n)>>5] &= ~(1 << ((n) & 31)))
#define	BIT_TEST(a,n)	((a)[(n)>>5] & (1 << ((n) & 31)))

unsigned long Smallsieve[SIEVESIZE/32];

long generator(MP_INT *p);

/* Construct sieve of prime numbers [3...SIEVESIZE*2] (odd numbers only) */
smallsieve(void)
{
	int j,k,p;

	memset(Smallsieve,0,sizeof Smallsieve);
	for(k=0;k < SIEVESIZE;k++){
		if(BIT_TEST(Smallsieve,k))
			continue;	/* 2*k+3 is composite */
		p = 2*k+3;	/* The next small prime */
		for(j=k+p;j<SIEVESIZE;j += p){
			BIT_SET(Smallsieve,j);	/* Mark all multiples of p */
		}
	}
}

main(argc,argv)
int argc;
char *argv[];
{
	MP_INT p,q,start,g,f,two,tmp;
	unsigned long sieve[SIEVESIZE/32];
	char *cp;

	int i,j,k;
	memset(sieve,0,sizeof(sieve));
	mpz_init(&p);
	mpz_init(&q);
	mpz_init(&start);
	mpz_init(&f);
	mpz_init(&tmp);
	mpz_init_set_ui(&two,2);

	printf("Generating small prime numbers...\n");
	smallsieve();

	/* Generate random starting point for subprime search,
	 * and ensure that it's odd
	 */
	if(argc < 2){
		printf("Generate random starting point\n");
		mpz_random(&p,PLEN/32);
	} else {
		printf("Using specified starting point\n");
		mpz_set_str(&p,argv[1],0);
		mpz_mod_2exp(&p,&p,PLEN);
	}
	/* starting q = (p-1)/2 */
	mpz_div_2exp(&start,&p,1);

	if((mpz_get_ui(&start) & 1) == 0)
		mpz_sub_ui(&start,&start,1);

	printf("Start q search at\n");
	cp = mpz_get_str(NULL,16,&start);
	fputs(cp,stdout);
	free(cp);
	printf("\n");

	/* p = 2*start + 1 */
	mpz_mul_2exp(&p,&start,1);
	mpz_add_ui(&p,&p,1);

	/* Sieve out q's and p's with small factors */
	printf("Sieving from starting point to q+%d...\n",SEARCHSPACE);

	for(i=0;i<SIEVESIZE;i++){
		int s,r;

		/* Get next small prime */
		if(BIT_TEST(Smallsieve,i))
			continue;
		s = 2*i+3;

		/* r = start mod s */
		r = mpz_mmod_ui(NULL,&start,s);

		k = s - r;	/* start+k is first entry divisible by s */
		if(k == s)
			k = 0;	/* s divides start */
		if(k & 1)	/* start+k even? */
			k += s;	/* Make start+k odd, and k even */
		/* The sieve omits the even numbers */
		k >>= 1;
		for(;k < SIEVESIZE;k += s){
			BIT_SET(sieve,k);	/* s divides start+2*k */
		}

		/* r = p mod s */
		r = mpz_mmod_ui(NULL,&p,s);

		k = s - r;	/* p+k is first entry divisible by s */
		if(k == s)
			k = 0;	/* s divides p */
		while(k & 3)
			k += s;

		/* The sieve omits the numbers divisible by 4 */
		k >>= 2;
		for(;k < SIEVESIZE;k += s){
			BIT_SET(sieve,k);	/* s divides p+2*k */
		}
	}
	printf("Sieve done, checking remaining candidates...\n");
	for(k=0;k<SIEVESIZE;k++){

		if(BIT_TEST(sieve,k))
			continue;	/* Definitely composite, skip */

		/* Candidate prime */			
		printf("test prime candidate at start+%d\n",2*k);
		mpz_add_ui(&q,&start,2*k);

		if(!mpz_probab_prime_p(&q,1))
			continue;
		printf("q passed Rabin-Miller test...\n");

		/* p = 2*q + 1 */
		mpz_mul_2exp(&p,&q,1);
		mpz_add_ui(&p,&p,1);

		if(!mpz_probab_prime_p(&p,1))
			continue;
		printf("p passed Rabin-Miller test...\n");
			break;
	}
	if(k == SIEVESIZE){
		printf("Failed to find a strong prime\n");
		exit(1);
	}
	printf("Found modulus p =\n");
	cp = mpz_get_str(NULL,16,&p);
	fputs(cp,stdout);
	free(cp);
	printf("\n");

	/* Find g, primitive root mod p */
	printf("Finding generator\n");
	i = generator(&p);
	printf("Generator g = %d decimal\n",i);
}

/* Find smallest primitive root (generator) for strong prime p using
 * algorithm on p. 209 of Schneier. Since we know (p-1)/2 is prime,
 * we know the factorization of p-1: it's simply 2 * (p-1)/2.
 * This makes our job *much* easier.
 */
long
generator(p)
MP_INT *p;
{
	MP_INT g,tmp,q;
	int i;

	mpz_init(&g);
	mpz_init(&tmp);
	mpz_init(&q);

	mpz_sub_ui(&q,p,1);
	mpz_div_2exp(&q,&q,1);	/* q = (p-1)/2 */

	/* Try 2. No need to test 2^2 mod p != 1 :-) */
	printf("Trying 2");
	mpz_set_ui(&g,2);
	mpz_powm(&tmp,&g,&q,p);	/* tmp = 2^q mod p */
	if(mpz_cmp_ui(&tmp,1) != 0){
		mpz_clear(&g);
		mpz_clear(&tmp);
		mpz_clear(&q);
		return 2;		/* 2 is primitive */
	}
	/* Try small primes starting with 3 */
	for(i=0;i<SIEVESIZE;i++){
		/* Get next small prime */
		if(BIT_TEST(Smallsieve,i))
			continue;
		printf(" %d",2*i+3);
		mpz_set_ui(&g,2*i+3);		/* g = trial generator */

		mpz_powm(&tmp,&g,&q,p);	/* tmp = g^q mod p */
		if(mpz_cmp_ui(&tmp,1) == 0)
			continue;		/* g is not primitive */

		/* This test can't possibly fail for small values of g,
		 * but it's here for completeness anyway
		 */
		mpz_powm_ui(&tmp,&g,2,p);	/* tmp = g^2 mod p */
		if(mpz_cmp_ui(&tmp,1) == 0)
			continue;		/* g is not primitive */

		break;				/* Passes both tests */
	}
	printf("\n");
	mpz_clear(&g);
	mpz_clear(&tmp);
	mpz_clear(&q);

	if(i == SIEVESIZE){
		printf("Could not find a small generator\n");
		return -1;
	}
	return(2*i+3);
}