[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Some 1024-bit DH moduli, and a program to generate them
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);
}