4  * Copyright 1996-1998, 2003 William Allen Simpson <wsimpson@greendragon.com>
8  * Redistribution and use in source and binary forms, with or without
13  * 2. Redistributions in binary form must reproduce the above copyright
14  *    notice, this list of conditions and the following disclaimer in the
20  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
24  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
30  * Two-step process to generate safe primes for DHGEX
33  *  suitable for use as Diffie-Hellman moduli;
34  *  that is, where q = (p-1)/2 is also prime.
63 #include "openbsd-compat/openssl-compat.h"
88 #define SHIFT_MEGAWORD	(SHIFT_MEGABYTE-SHIFT_BYTE)
92  * number that is supported without a large amount of disk activity --
104  * Constant: when used with 32-bit integers, the largest sieve prime
109 /* Constant: can sieve all primes less than 2**32, as 65537**2 > 2**32-1. */
115 /* real TEST_MINIMUM	(1UL << (SHIFT_WORD - TEST_POWER)) */
118 /* bit operations on 32-bit words */
131  * Sieving data (XXX - move to struct)
137 /* sieve 2**30 in 2**16 parts */
150  * print moduli out in consistent form,
163 		return -1;  in qfileout()
166 	    gtm->tm_year + 1900, gtm->tm_mon + 1, gtm->tm_mday,  in qfileout()
167 	    gtm->tm_hour, gtm->tm_min, gtm->tm_sec,  in qfileout()
171 		return (-1);  in qfileout()
174 		return (-1);  in qfileout()
179 	return (res > 0 ? 0 : -1);  in qfileout()
198 		u = s - r; /* largebase+u is first entry divisible by s */  in sieve_large()
203 		 * largebase+u is odd. Then, step through the sieve in  in sieve_large()
219 		u = s - r; /* p+u is first entry divisible by s */  in sieve_large()
224 		 * largebase+u is not. Then, step through the sieve in  in sieve_large()
228 			if (SMALL_MAXIMUM - u < s)  in sieve_large()
240  * list candidates for Sophie-Germain primes (where q = (p-1)/2)
261 		return (-1);  in gen_candidates()
265 	 * Set power to the length in bits of the prime to be generated.  in gen_candidates()
270 		return (-1);  in gen_candidates()
273 		return (-1);  in gen_candidates()
275 	power--; /* decrement before squaring */  in gen_candidates()
283 	largewords = ((power * power) >> (SHIFT_WORD - TEST_POWER));  in gen_candidates()
315 		largewords -= (1L << (SHIFT_MEGAWORD - 2)); /* 1/4 MB chunks */  in gen_candidates()
345 	logit("%.24s Sieve next %u plus %u-bit", ctime(&time_start),  in gen_candidates()
354 			continue; /* 2*i+3 is composite */  in gen_candidates()
371 	    smallbase < (SMALL_MAXIMUM - TINY_NUMBER);  in gen_candidates()
375 				continue; /* 2*i+3 is composite */  in gen_candidates()
385 				s = t - r;  in gen_candidates()
391 			 * in increments of 2*t  in gen_candidates()
406 				continue; /* 2*i+smallbase is composite */  in gen_candidates()
417 	logit("%.24s Sieved with %u small primes in %lld seconds",  in gen_candidates()
418 	    ctime(&time_stop), largetries, (long long)(time_stop - time_start));  in gen_candidates()
422 			continue; /* Definitely composite, skip */  in gen_candidates()
431 		    (power - 1) /* MSB */, (0), q) == -1) {  in gen_candidates()
432 			ret = -1;  in gen_candidates()
462 	if ((r = mkstemp(tmp)) == -1) {  in write_checkpoint()
549 	if (time_now - time_prev < 5 * 60)  in print_progress()
552 	elapsed = time_now - time_start;  in print_progress()
553 	processed = current_lineno - start_lineno;  in print_progress()
554 	remaining = end_lineno - current_lineno;  in print_progress()
555 	num_to_process = end_lineno - start_lineno;  in print_progress()
560 		logit("%.24s processed %lu in %s", ctime(&time_now),  in print_progress()
567 	logit("%.24s processed %lu of %lu (%lu%%) in %s, ETA %s",  in print_progress()
574  * perform a Miller-Rabin primality test
577  * The result is a list of so-call "safe" primes
580 prime_test(FILE *in, FILE *out, u_int32_t trials, u_int32_t generator_wanted,  in prime_test()  argument
593 		return (-1);  in prime_test()
597 		end_lineno = count_lines(in);  in prime_test()
608 	debug2("%.24s Final %u Miller-Rabin trials (%x generator)",  in prime_test()
622 	while (fgets(lp, QLINESIZE + 1, in) != NULL && count_in < end_lineno) {  in prime_test()
637 		/* XXX - fragile parser */  in prime_test()
648 			debug2("%10u: known composite", count_in);  in prime_test()
667 			debug2("%10u: (%u) Sophie-Germain", count_in, in_type);  in prime_test()
688 			/* q = (p-1) / 2 */  in prime_test()
698 		 * due to earlier inconsistencies in interpretation, check  in prime_test()
750 		 * The (1/4)^N performance bound on Miller-Rabin is  in prime_test()
754 		 * vast majority of composite q's.  in prime_test()
768 		 * the same for q. If p is composite, chances are that  in prime_test()
769 		 * will show up on the first Rabin-Miller iteration so it  in prime_test()
782 		is_prime = BN_is_prime_ex(q, trials - 1, NULL, NULL);  in prime_test()
794 			res = -1;  in prime_test()
809 	logit("%.24s Found %u safe primes of %u candidates in %ld seconds",  in prime_test()
811 	    (long) (time_stop - time_start));  in prime_test()