1 /* $OpenBSD: moduli.c,v 1.41 2026/03/03 09:57:25 dtucker Exp $ */ 2 /* 3 * Copyright 1994 Phil Karn <karn@qualcomm.com> 4 * Copyright 1996-1998, 2003 William Allen Simpson <wsimpson@greendragon.com> 5 * Copyright 2000 Niels Provos <provos@citi.umich.edu> 6 * All rights reserved. 7 * 8 * Redistribution and use in source and binary forms, with or without 9 * modification, are permitted provided that the following conditions 10 * are met: 11 * 1. Redistributions of source code must retain the above copyright 12 * notice, this list of conditions and the following disclaimer. 13 * 2. Redistributions in binary form must reproduce the above copyright 14 * notice, this list of conditions and the following disclaimer in the 15 * documentation and/or other materials provided with the distribution. 16 * 17 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 18 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 19 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 20 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 21 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 22 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 23 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 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 26 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 27 */ 28 29 /* 30 * Two-step process to generate safe primes for DHGEX 31 * 32 * Sieve candidates for "safe" primes, 33 * suitable for use as Diffie-Hellman moduli; 34 * that is, where q = (p-1)/2 is also prime. 35 * 36 * First step: generate candidate primes (memory intensive) 37 * Second step: test primes' safety (processor intensive) 38 */ 39 40 #include "includes.h" 41 42 #ifdef WITH_OPENSSL 43 44 #include <sys/types.h> 45 46 #include <openssl/bn.h> 47 #include <openssl/dh.h> 48 49 #include <errno.h> 50 #include <stdio.h> 51 #include <stdlib.h> 52 #include <string.h> 53 #include <stdarg.h> 54 #include <time.h> 55 #include <unistd.h> 56 #include <limits.h> 57 58 #include "xmalloc.h" 59 #include "dh.h" 60 #include "log.h" 61 #include "misc.h" 62 63 #include "openbsd-compat/openssl-compat.h" 64 65 /* 66 * File output defines 67 */ 68 69 /* need line long enough for largest moduli plus headers */ 70 #define QLINESIZE (100+8192) 71 72 /* 73 * Size: decimal. 74 * Specifies the number of the most significant bit (0 to M). 75 * WARNING: internally, usually 1 to N. 76 */ 77 #define QSIZE_MINIMUM (511) 78 79 /* 80 * Prime sieving defines 81 */ 82 83 /* Constant: assuming 8 bit bytes and 32 bit words */ 84 #define SHIFT_BIT (3) 85 #define SHIFT_BYTE (2) 86 #define SHIFT_WORD (SHIFT_BIT+SHIFT_BYTE) 87 #define SHIFT_MEGABYTE (20) 88 #define SHIFT_MEGAWORD (SHIFT_MEGABYTE-SHIFT_BYTE) 89 90 /* 91 * Do not increase this number beyond the unsigned integer bit size. 92 * Due to a multiple of 4, it must be LESS than 128 (yielding 2**30 bits). 93 */ 94 #define LARGE_MAXIMUM (127UL) /* megabytes */ 95 96 /* 97 * Constant: when used with 32-bit integers, the largest sieve prime 98 * has to be less than 2**32. 99 */ 100 #define SMALL_MAXIMUM (0xffffffffUL) 101 102 /* Constant: can sieve all primes less than 2**32, as 65537**2 > 2**32-1. */ 103 #define TINY_NUMBER (1UL<<16) 104 105 /* Ensure enough bit space for testing 2*q. */ 106 #define TEST_MAXIMUM (1UL<<16) 107 #define TEST_MINIMUM (QSIZE_MINIMUM + 1) 108 /* real TEST_MINIMUM (1UL << (SHIFT_WORD - TEST_POWER)) */ 109 #define TEST_POWER (3) /* 2**n, n < SHIFT_WORD */ 110 111 /* bit operations on 32-bit words */ 112 #define BIT_CLEAR(a,n) ((a)[(n)>>SHIFT_WORD] &= ~(1L << ((n) & 31))) 113 #define BIT_SET(a,n) ((a)[(n)>>SHIFT_WORD] |= (1L << ((n) & 31))) 114 #define BIT_TEST(a,n) ((a)[(n)>>SHIFT_WORD] & (1L << ((n) & 31))) 115 116 /* 117 * Prime testing defines 118 */ 119 120 /* Minimum number of primality tests to perform */ 121 #define TRIAL_MINIMUM (4) 122 123 /* 124 * Sieving data (XXX - move to struct) 125 */ 126 127 /* sieve 2**16 */ 128 static uint32_t *TinySieve, tinybits; 129 130 /* sieve 2**30 in 2**16 parts */ 131 static uint32_t *SmallSieve, smallbits, smallbase; 132 133 /* sieve relative to the initial value */ 134 static uint32_t *LargeSieve, largewords, largetries, largenumbers; 135 static uint32_t largebits, largememory; /* megabytes */ 136 static BIGNUM *largebase; 137 138 int gen_candidates(FILE *, uint32_t, BIGNUM *); 139 int prime_test(FILE *, FILE *, uint32_t, uint32_t, char *, unsigned long, 140 unsigned long); 141 142 /* 143 * print moduli out in consistent form, 144 */ 145 static int 146 qfileout(FILE * ofile, uint32_t otype, uint32_t otests, uint32_t otries, 147 uint32_t osize, uint32_t ogenerator, BIGNUM * omodulus) 148 { 149 struct tm *gtm; 150 time_t time_now; 151 int res; 152 153 time(&time_now); 154 gtm = gmtime(&time_now); 155 if (gtm == NULL) 156 return -1; 157 158 res = fprintf(ofile, "%04d%02d%02d%02d%02d%02d %u %u %u %u %x ", 159 gtm->tm_year + 1900, gtm->tm_mon + 1, gtm->tm_mday, 160 gtm->tm_hour, gtm->tm_min, gtm->tm_sec, 161 otype, otests, otries, osize, ogenerator); 162 163 if (res < 0) 164 return (-1); 165 166 if (BN_print_fp(ofile, omodulus) < 1) 167 return (-1); 168 169 res = fprintf(ofile, "\n"); 170 fflush(ofile); 171 172 return (res > 0 ? 0 : -1); 173 } 174 175 176 /* 177 ** Sieve p's and q's with small factors 178 */ 179 static void 180 sieve_large(uint32_t s32) 181 { 182 uint64_t r, u, s = s32; 183 184 debug3("sieve_large %u", s32); 185 largetries++; 186 /* r = largebase mod s */ 187 r = BN_mod_word(largebase, s32); 188 if (r == 0) 189 u = 0; /* s divides into largebase exactly */ 190 else 191 u = s - r; /* largebase+u is first entry divisible by s */ 192 193 if (u < largebits * 2ULL) { 194 /* 195 * The sieve omits p's and q's divisible by 2, so ensure that 196 * largebase+u is odd. Then, step through the sieve in 197 * increments of 2*s 198 */ 199 if (u & 0x1) 200 u += s; /* Make largebase+u odd, and u even */ 201 202 /* Mark all multiples of 2*s */ 203 for (u /= 2; u < largebits; u += s) 204 BIT_SET(LargeSieve, u); 205 } 206 207 /* r = p mod s */ 208 r = (2 * r + 1) % s; 209 if (r == 0) 210 u = 0; /* s divides p exactly */ 211 else 212 u = s - r; /* p+u is first entry divisible by s */ 213 214 if (u < largebits * 4ULL) { 215 /* 216 * The sieve omits p's divisible by 4, so ensure that 217 * largebase+u is not. Then, step through the sieve in 218 * increments of 4*s 219 */ 220 while (u & 0x3) { 221 if (SMALL_MAXIMUM - u < s) 222 return; 223 u += s; 224 } 225 226 /* Mark all multiples of 4*s */ 227 for (u /= 4; u < largebits; u += s) 228 BIT_SET(LargeSieve, u); 229 } 230 } 231 232 /* 233 * list candidates for Sophie-Germain primes (where q = (p-1)/2) 234 * to standard output. 235 * The list is checked against small known primes (less than 2**30). 236 */ 237 int 238 gen_candidates(FILE *out, uint32_t power, BIGNUM *start) 239 { 240 BIGNUM *q; 241 uint32_t j, r, s, t; 242 uint32_t smallwords = TINY_NUMBER >> 6; 243 uint32_t tinywords = TINY_NUMBER >> 6; 244 time_t time_start, time_stop; 245 uint32_t i; 246 int ret = 0; 247 248 /* 249 * Set power to the length in bits of the prime to be generated. 250 * This is changed to 1 less than the desired safe prime moduli p. 251 */ 252 if (power > TEST_MAXIMUM) { 253 error("Too many bits: %u > %lu", power, TEST_MAXIMUM); 254 return (-1); 255 } else if (power < TEST_MINIMUM) { 256 error("Too few bits: %u < %u", power, TEST_MINIMUM); 257 return (-1); 258 } 259 power--; /* decrement before squaring */ 260 261 /* Always use the maximum amount of memory supported by the algorithm. */ 262 largememory = LARGE_MAXIMUM; 263 largewords = (largememory << SHIFT_MEGAWORD); 264 265 TinySieve = xcalloc(tinywords, sizeof(uint32_t)); 266 tinybits = tinywords << SHIFT_WORD; 267 268 SmallSieve = xcalloc(smallwords, sizeof(uint32_t)); 269 smallbits = smallwords << SHIFT_WORD; 270 271 LargeSieve = xcalloc(largewords, sizeof(uint32_t)); 272 largebits = largewords << SHIFT_WORD; 273 largenumbers = largebits * 2; /* even numbers excluded */ 274 275 /* validation check: count the number of primes tried */ 276 largetries = 0; 277 if ((q = BN_new()) == NULL) 278 fatal("BN_new failed"); 279 280 /* 281 * Generate random starting point for subprime search, or use 282 * specified parameter. 283 */ 284 if ((largebase = BN_new()) == NULL) 285 fatal("BN_new failed"); 286 if (start == NULL) { 287 if (BN_rand(largebase, power, 1, 1) == 0) 288 fatal("BN_rand failed"); 289 } else { 290 if (BN_copy(largebase, start) == NULL) 291 fatal("BN_copy: failed"); 292 } 293 294 /* ensure odd */ 295 if (BN_set_bit(largebase, 0) == 0) 296 fatal("BN_set_bit: failed"); 297 298 time(&time_start); 299 300 logit("%.24s Sieve next %u plus %u-bit", ctime(&time_start), 301 largenumbers, power); 302 debug2("start point: 0x%s", BN_bn2hex(largebase)); 303 304 /* 305 * TinySieve 306 */ 307 for (i = 0; i < tinybits; i++) { 308 if (BIT_TEST(TinySieve, i)) 309 continue; /* 2*i+3 is composite */ 310 311 /* The next tiny prime */ 312 t = 2 * i + 3; 313 314 /* Mark all multiples of t */ 315 for (j = i + t; j < tinybits; j += t) 316 BIT_SET(TinySieve, j); 317 318 sieve_large(t); 319 } 320 321 /* 322 * Start the small block search at the next possible prime. To avoid 323 * fencepost errors, the last pass is skipped. 324 */ 325 for (smallbase = TINY_NUMBER + 3; 326 smallbase < (SMALL_MAXIMUM - TINY_NUMBER); 327 smallbase += TINY_NUMBER) { 328 for (i = 0; i < tinybits; i++) { 329 if (BIT_TEST(TinySieve, i)) 330 continue; /* 2*i+3 is composite */ 331 332 /* The next tiny prime */ 333 t = 2 * i + 3; 334 r = smallbase % t; 335 336 if (r == 0) { 337 s = 0; /* t divides into smallbase exactly */ 338 } else { 339 /* smallbase+s is first entry divisible by t */ 340 s = t - r; 341 } 342 343 /* 344 * The sieve omits even numbers, so ensure that 345 * smallbase+s is odd. Then, step through the sieve 346 * in increments of 2*t 347 */ 348 if (s & 1) 349 s += t; /* Make smallbase+s odd, and s even */ 350 351 /* Mark all multiples of 2*t */ 352 for (s /= 2; s < smallbits; s += t) 353 BIT_SET(SmallSieve, s); 354 } 355 356 /* 357 * SmallSieve 358 */ 359 for (i = 0; i < smallbits; i++) { 360 if (BIT_TEST(SmallSieve, i)) 361 continue; /* 2*i+smallbase is composite */ 362 363 /* The next small prime */ 364 sieve_large((2 * i) + smallbase); 365 } 366 367 memset(SmallSieve, 0, smallwords << SHIFT_BYTE); 368 } 369 370 time(&time_stop); 371 372 logit("%.24s Sieved with %u small primes in %lld seconds", 373 ctime(&time_stop), largetries, (long long)(time_stop - time_start)); 374 375 for (j = r = 0; j < largebits; j++) { 376 if (BIT_TEST(LargeSieve, j)) 377 continue; /* Definitely composite, skip */ 378 379 debug2("test q = largebase+%u", 2 * j); 380 if (BN_set_word(q, 2 * j) == 0) 381 fatal("BN_set_word failed"); 382 if (BN_add(q, q, largebase) == 0) 383 fatal("BN_add failed"); 384 if (qfileout(out, MODULI_TYPE_SOPHIE_GERMAIN, 385 MODULI_TESTS_SIEVE, largetries, 386 (power - 1) /* MSB */, (0), q) == -1) { 387 ret = -1; 388 break; 389 } 390 391 r++; /* count q */ 392 } 393 394 time(&time_stop); 395 396 free(LargeSieve); 397 free(SmallSieve); 398 free(TinySieve); 399 400 logit("%.24s Found %u candidates", ctime(&time_stop), r); 401 402 return (ret); 403 } 404 405 static void 406 write_checkpoint(char *cpfile, uint32_t lineno) 407 { 408 FILE *fp; 409 char tmp[PATH_MAX]; 410 int r, writeok, closeok; 411 412 r = snprintf(tmp, sizeof(tmp), "%s.XXXXXXXXXX", cpfile); 413 if (r < 0 || r >= PATH_MAX) { 414 logit("write_checkpoint: temp pathname too long"); 415 return; 416 } 417 if ((r = mkstemp(tmp)) == -1) { 418 logit("mkstemp(%s): %s", tmp, strerror(errno)); 419 return; 420 } 421 if ((fp = fdopen(r, "w")) == NULL) { 422 logit("write_checkpoint: fdopen: %s", strerror(errno)); 423 unlink(tmp); 424 close(r); 425 return; 426 } 427 writeok = (fprintf(fp, "%lu\n", (unsigned long)lineno) > 0); 428 closeok = (fclose(fp) == 0); 429 if (writeok && closeok && rename(tmp, cpfile) == 0) { 430 debug3("wrote checkpoint line %lu to '%s'", 431 (unsigned long)lineno, cpfile); 432 } else { 433 logit("failed to write to checkpoint file '%s': %s", cpfile, 434 strerror(errno)); 435 (void)unlink(tmp); 436 } 437 } 438 439 static unsigned long 440 read_checkpoint(char *cpfile) 441 { 442 FILE *fp; 443 unsigned long lineno = 0; 444 445 if ((fp = fopen(cpfile, "r")) == NULL) 446 return 0; 447 if (fscanf(fp, "%lu\n", &lineno) < 1) 448 logit("Failed to load checkpoint from '%s'", cpfile); 449 else 450 logit("Loaded checkpoint from '%s' line %lu", cpfile, lineno); 451 fclose(fp); 452 return lineno; 453 } 454 455 static unsigned long 456 count_lines(FILE *f) 457 { 458 unsigned long count = 0; 459 char lp[QLINESIZE + 1]; 460 461 if (fseek(f, 0, SEEK_SET) != 0) { 462 debug("input file is not seekable"); 463 return ULONG_MAX; 464 } 465 while (fgets(lp, QLINESIZE + 1, f) != NULL) 466 count++; 467 rewind(f); 468 debug("input file has %lu lines", count); 469 return count; 470 } 471 472 static char * 473 fmt_time(time_t seconds) 474 { 475 int day, hr, min; 476 static char buf[128]; 477 478 min = (seconds / 60) % 60; 479 hr = (seconds / 60 / 60) % 24; 480 day = seconds / 60 / 60 / 24; 481 if (day > 0) 482 snprintf(buf, sizeof buf, "%dd %d:%02d", day, hr, min); 483 else 484 snprintf(buf, sizeof buf, "%d:%02d", hr, min); 485 return buf; 486 } 487 488 static void 489 print_progress(unsigned long start_lineno, unsigned long current_lineno, 490 unsigned long end_lineno) 491 { 492 static time_t time_start, time_prev; 493 time_t time_now, elapsed; 494 unsigned long num_to_process, processed, remaining, percent, eta; 495 double time_per_line; 496 char *eta_str; 497 498 time_now = monotime(); 499 if (time_start == 0) { 500 time_start = time_prev = time_now; 501 return; 502 } 503 /* print progress after 1m then once per 5m */ 504 if (time_now - time_prev < 5 * 60) 505 return; 506 time_prev = time_now; 507 elapsed = time_now - time_start; 508 processed = current_lineno - start_lineno; 509 remaining = end_lineno - current_lineno; 510 num_to_process = end_lineno - start_lineno; 511 time_per_line = (double)elapsed / processed; 512 /* if we don't know how many we're processing just report count+time */ 513 time(&time_now); 514 if (end_lineno == ULONG_MAX) { 515 logit("%.24s processed %lu in %s", ctime(&time_now), 516 processed, fmt_time(elapsed)); 517 return; 518 } 519 percent = 100 * processed / num_to_process; 520 eta = time_per_line * remaining; 521 eta_str = xstrdup(fmt_time(eta)); 522 logit("%.24s processed %lu of %lu (%lu%%) in %s, ETA %s", 523 ctime(&time_now), processed, num_to_process, percent, 524 fmt_time(elapsed), eta_str); 525 free(eta_str); 526 } 527 528 /* 529 * perform a Miller-Rabin primality test 530 * on the list of candidates 531 * (checking both q and p) 532 * The result is a list of so-call "safe" primes 533 */ 534 int 535 prime_test(FILE *in, FILE *out, uint32_t trials, uint32_t generator_wanted, 536 char *checkpoint_file, unsigned long start_lineno, unsigned long num_lines) 537 { 538 BIGNUM *q, *p, *a; 539 char *cp, *lp; 540 uint32_t count_in = 0, count_out = 0, count_possible = 0; 541 uint32_t generator_known, in_tests, in_tries, in_type, in_size; 542 unsigned long last_processed = 0, end_lineno; 543 time_t time_start, time_stop; 544 int res, is_prime; 545 546 if (trials < TRIAL_MINIMUM) { 547 error("Minimum primality trials is %d", TRIAL_MINIMUM); 548 return (-1); 549 } 550 551 if (num_lines == 0) 552 end_lineno = count_lines(in); 553 else 554 end_lineno = start_lineno + num_lines; 555 556 time(&time_start); 557 558 if ((p = BN_new()) == NULL) 559 fatal("BN_new failed"); 560 if ((q = BN_new()) == NULL) 561 fatal("BN_new failed"); 562 563 debug2("%.24s Final %u Miller-Rabin trials (%x generator)", 564 ctime(&time_start), trials, generator_wanted); 565 566 if (checkpoint_file != NULL) 567 last_processed = read_checkpoint(checkpoint_file); 568 last_processed = start_lineno = MAXIMUM(last_processed, start_lineno); 569 if (end_lineno == ULONG_MAX) 570 debug("process from line %lu from pipe", last_processed); 571 else 572 debug("process from line %lu to line %lu", last_processed, 573 end_lineno); 574 575 res = 0; 576 lp = xmalloc(QLINESIZE + 1); 577 while (fgets(lp, QLINESIZE + 1, in) != NULL && count_in < end_lineno) { 578 count_in++; 579 if (count_in <= last_processed) { 580 debug3("skipping line %u, before checkpoint or " 581 "specified start line", count_in); 582 continue; 583 } 584 if (checkpoint_file != NULL) 585 write_checkpoint(checkpoint_file, count_in); 586 print_progress(start_lineno, count_in, end_lineno); 587 if (strlen(lp) < 14 || *lp == '!' || *lp == '#') { 588 debug2("%10u: comment or short line", count_in); 589 continue; 590 } 591 592 /* XXX - fragile parser */ 593 /* time */ 594 cp = &lp[14]; /* (skip) */ 595 596 /* type */ 597 in_type = strtoul(cp, &cp, 10); 598 599 /* tests */ 600 in_tests = strtoul(cp, &cp, 10); 601 602 if (in_tests & MODULI_TESTS_COMPOSITE) { 603 debug2("%10u: known composite", count_in); 604 continue; 605 } 606 607 /* tries */ 608 in_tries = strtoul(cp, &cp, 10); 609 610 /* size (most significant bit) */ 611 in_size = strtoul(cp, &cp, 10); 612 613 /* generator (hex) */ 614 generator_known = strtoul(cp, &cp, 16); 615 616 /* Skip white space */ 617 cp += strspn(cp, " "); 618 619 /* modulus (hex) */ 620 switch (in_type) { 621 case MODULI_TYPE_SOPHIE_GERMAIN: 622 debug2("%10u: (%u) Sophie-Germain", count_in, in_type); 623 a = q; 624 if (BN_hex2bn(&a, cp) == 0) 625 fatal("BN_hex2bn failed"); 626 /* p = 2*q + 1 */ 627 if (BN_lshift(p, q, 1) == 0) 628 fatal("BN_lshift failed"); 629 if (BN_add_word(p, 1) == 0) 630 fatal("BN_add_word failed"); 631 in_size += 1; 632 generator_known = 0; 633 break; 634 case MODULI_TYPE_UNSTRUCTURED: 635 case MODULI_TYPE_SAFE: 636 case MODULI_TYPE_SCHNORR: 637 case MODULI_TYPE_STRONG: 638 case MODULI_TYPE_UNKNOWN: 639 debug2("%10u: (%u)", count_in, in_type); 640 a = p; 641 if (BN_hex2bn(&a, cp) == 0) 642 fatal("BN_hex2bn failed"); 643 /* q = (p-1) / 2 */ 644 if (BN_rshift(q, p, 1) == 0) 645 fatal("BN_rshift failed"); 646 break; 647 default: 648 debug2("Unknown prime type"); 649 break; 650 } 651 652 /* 653 * due to earlier inconsistencies in interpretation, check 654 * the proposed bit size. 655 */ 656 if ((uint32_t)BN_num_bits(p) != (in_size + 1)) { 657 debug2("%10u: bit size %u mismatch", count_in, in_size); 658 continue; 659 } 660 if (in_size < QSIZE_MINIMUM) { 661 debug2("%10u: bit size %u too short", count_in, in_size); 662 continue; 663 } 664 665 if (in_tests & MODULI_TESTS_MILLER_RABIN) 666 in_tries += trials; 667 else 668 in_tries = trials; 669 670 /* 671 * guess unknown generator 672 */ 673 if (generator_known == 0) { 674 if (BN_mod_word(p, 24) == 11) 675 generator_known = 2; 676 else { 677 uint32_t r = BN_mod_word(p, 10); 678 679 if (r == 3 || r == 7) 680 generator_known = 5; 681 } 682 } 683 /* 684 * skip tests when desired generator doesn't match 685 */ 686 if (generator_wanted > 0 && 687 generator_wanted != generator_known) { 688 debug2("%10u: generator %d != %d", 689 count_in, generator_known, generator_wanted); 690 continue; 691 } 692 693 /* 694 * Primes with no known generator are useless for DH, so 695 * skip those. 696 */ 697 if (generator_known == 0) { 698 debug2("%10u: no known generator", count_in); 699 continue; 700 } 701 702 count_possible++; 703 704 /* 705 * The (1/4)^N performance bound on Miller-Rabin is 706 * extremely pessimistic, so don't spend a lot of time 707 * really verifying that q is prime until after we know 708 * that p is also prime. A single pass will weed out the 709 * vast majority of composite q's. 710 */ 711 is_prime = BN_is_prime_ex(q, 1, NULL, NULL); 712 if (is_prime < 0) 713 fatal("BN_is_prime_ex failed"); 714 if (is_prime == 0) { 715 debug("%10u: q failed first possible prime test", 716 count_in); 717 continue; 718 } 719 720 /* 721 * q is possibly prime, so go ahead and really make sure 722 * that p is prime. If it is, then we can go back and do 723 * the same for q. If p is composite, chances are that 724 * will show up on the first Rabin-Miller iteration so it 725 * doesn't hurt to specify a high iteration count. 726 */ 727 is_prime = BN_is_prime_ex(p, trials, NULL, NULL); 728 if (is_prime < 0) 729 fatal("BN_is_prime_ex failed"); 730 if (is_prime == 0) { 731 debug("%10u: p is not prime", count_in); 732 continue; 733 } 734 debug("%10u: p is almost certainly prime", count_in); 735 736 /* recheck q more rigorously */ 737 is_prime = BN_is_prime_ex(q, trials - 1, NULL, NULL); 738 if (is_prime < 0) 739 fatal("BN_is_prime_ex failed"); 740 if (is_prime == 0) { 741 debug("%10u: q is not prime", count_in); 742 continue; 743 } 744 debug("%10u: q is almost certainly prime", count_in); 745 746 if (qfileout(out, MODULI_TYPE_SAFE, 747 in_tests | MODULI_TESTS_MILLER_RABIN, 748 in_tries, in_size, generator_known, p)) { 749 res = -1; 750 break; 751 } 752 753 count_out++; 754 } 755 756 time(&time_stop); 757 free(lp); 758 BN_free(p); 759 BN_free(q); 760 761 if (checkpoint_file != NULL) 762 unlink(checkpoint_file); 763 764 logit("%.24s Found %u safe primes of %u candidates in %ld seconds", 765 ctime(&time_stop), count_out, count_possible, 766 (long) (time_stop - time_start)); 767 768 return (res); 769 } 770 771 #endif /* WITH_OPENSSL */ 772