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); }