moduli.c revision 137015
1137015Sdes/* $OpenBSD: moduli.c,v 1.9 2004/07/11 17:48:47 deraadt Exp $ */ 2124208Sdes/* 3124208Sdes * Copyright 1994 Phil Karn <karn@qualcomm.com> 4124208Sdes * Copyright 1996-1998, 2003 William Allen Simpson <wsimpson@greendragon.com> 5124208Sdes * Copyright 2000 Niels Provos <provos@citi.umich.edu> 6124208Sdes * All rights reserved. 7124208Sdes * 8124208Sdes * Redistribution and use in source and binary forms, with or without 9124208Sdes * modification, are permitted provided that the following conditions 10124208Sdes * are met: 11124208Sdes * 1. Redistributions of source code must retain the above copyright 12124208Sdes * notice, this list of conditions and the following disclaimer. 13124208Sdes * 2. Redistributions in binary form must reproduce the above copyright 14124208Sdes * notice, this list of conditions and the following disclaimer in the 15124208Sdes * documentation and/or other materials provided with the distribution. 16124208Sdes * 17124208Sdes * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 18124208Sdes * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 19124208Sdes * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 20124208Sdes * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 21124208Sdes * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 22124208Sdes * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 23124208Sdes * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 24124208Sdes * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 25124208Sdes * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 26124208Sdes * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 27124208Sdes */ 28124208Sdes 29124208Sdes/* 30124208Sdes * Two-step process to generate safe primes for DHGEX 31124208Sdes * 32124208Sdes * Sieve candidates for "safe" primes, 33124208Sdes * suitable for use as Diffie-Hellman moduli; 34124208Sdes * that is, where q = (p-1)/2 is also prime. 35124208Sdes * 36124208Sdes * First step: generate candidate primes (memory intensive) 37124208Sdes * Second step: test primes' safety (processor intensive) 38124208Sdes */ 39124208Sdes 40124208Sdes#include "includes.h" 41124208Sdes#include "xmalloc.h" 42124208Sdes#include "log.h" 43124208Sdes 44124208Sdes#include <openssl/bn.h> 45124208Sdes 46124208Sdes/* 47124208Sdes * File output defines 48124208Sdes */ 49124208Sdes 50124208Sdes/* need line long enough for largest moduli plus headers */ 51137015Sdes#define QLINESIZE (100+8192) 52124208Sdes 53124208Sdes/* Type: decimal. 54124208Sdes * Specifies the internal structure of the prime modulus. 55124208Sdes */ 56137015Sdes#define QTYPE_UNKNOWN (0) 57137015Sdes#define QTYPE_UNSTRUCTURED (1) 58137015Sdes#define QTYPE_SAFE (2) 59137015Sdes#define QTYPE_SCHNOOR (3) 60137015Sdes#define QTYPE_SOPHIE_GERMAIN (4) 61137015Sdes#define QTYPE_STRONG (5) 62124208Sdes 63124208Sdes/* Tests: decimal (bit field). 64124208Sdes * Specifies the methods used in checking for primality. 65124208Sdes * Usually, more than one test is used. 66124208Sdes */ 67137015Sdes#define QTEST_UNTESTED (0x00) 68137015Sdes#define QTEST_COMPOSITE (0x01) 69137015Sdes#define QTEST_SIEVE (0x02) 70137015Sdes#define QTEST_MILLER_RABIN (0x04) 71137015Sdes#define QTEST_JACOBI (0x08) 72137015Sdes#define QTEST_ELLIPTIC (0x10) 73124208Sdes 74126274Sdes/* 75126274Sdes * Size: decimal. 76124208Sdes * Specifies the number of the most significant bit (0 to M). 77126274Sdes * WARNING: internally, usually 1 to N. 78124208Sdes */ 79137015Sdes#define QSIZE_MINIMUM (511) 80124208Sdes 81124208Sdes/* 82124208Sdes * Prime sieving defines 83124208Sdes */ 84124208Sdes 85124208Sdes/* Constant: assuming 8 bit bytes and 32 bit words */ 86137015Sdes#define SHIFT_BIT (3) 87137015Sdes#define SHIFT_BYTE (2) 88137015Sdes#define SHIFT_WORD (SHIFT_BIT+SHIFT_BYTE) 89137015Sdes#define SHIFT_MEGABYTE (20) 90137015Sdes#define SHIFT_MEGAWORD (SHIFT_MEGABYTE-SHIFT_BYTE) 91124208Sdes 92124208Sdes/* 93137015Sdes * Using virtual memory can cause thrashing. This should be the largest 94137015Sdes * number that is supported without a large amount of disk activity -- 95137015Sdes * that would increase the run time from hours to days or weeks! 96137015Sdes */ 97137015Sdes#define LARGE_MINIMUM (8UL) /* megabytes */ 98137015Sdes 99137015Sdes/* 100137015Sdes * Do not increase this number beyond the unsigned integer bit size. 101137015Sdes * Due to a multiple of 4, it must be LESS than 128 (yielding 2**30 bits). 102137015Sdes */ 103137015Sdes#define LARGE_MAXIMUM (127UL) /* megabytes */ 104137015Sdes 105137015Sdes/* 106124208Sdes * Constant: when used with 32-bit integers, the largest sieve prime 107124208Sdes * has to be less than 2**32. 108124208Sdes */ 109137015Sdes#define SMALL_MAXIMUM (0xffffffffUL) 110124208Sdes 111124208Sdes/* Constant: can sieve all primes less than 2**32, as 65537**2 > 2**32-1. */ 112137015Sdes#define TINY_NUMBER (1UL<<16) 113124208Sdes 114124208Sdes/* Ensure enough bit space for testing 2*q. */ 115124208Sdes#define TEST_MAXIMUM (1UL<<16) 116124208Sdes#define TEST_MINIMUM (QSIZE_MINIMUM + 1) 117124208Sdes/* real TEST_MINIMUM (1UL << (SHIFT_WORD - TEST_POWER)) */ 118124208Sdes#define TEST_POWER (3) /* 2**n, n < SHIFT_WORD */ 119124208Sdes 120124208Sdes/* bit operations on 32-bit words */ 121124208Sdes#define BIT_CLEAR(a,n) ((a)[(n)>>SHIFT_WORD] &= ~(1L << ((n) & 31))) 122124208Sdes#define BIT_SET(a,n) ((a)[(n)>>SHIFT_WORD] |= (1L << ((n) & 31))) 123124208Sdes#define BIT_TEST(a,n) ((a)[(n)>>SHIFT_WORD] & (1L << ((n) & 31))) 124124208Sdes 125124208Sdes/* 126124208Sdes * Prime testing defines 127124208Sdes */ 128124208Sdes 129137015Sdes/* Minimum number of primality tests to perform */ 130137015Sdes#define TRIAL_MINIMUM (4) 131137015Sdes 132124208Sdes/* 133124208Sdes * Sieving data (XXX - move to struct) 134124208Sdes */ 135124208Sdes 136124208Sdes/* sieve 2**16 */ 137124208Sdesstatic u_int32_t *TinySieve, tinybits; 138124208Sdes 139124208Sdes/* sieve 2**30 in 2**16 parts */ 140124208Sdesstatic u_int32_t *SmallSieve, smallbits, smallbase; 141124208Sdes 142124208Sdes/* sieve relative to the initial value */ 143124208Sdesstatic u_int32_t *LargeSieve, largewords, largetries, largenumbers; 144124208Sdesstatic u_int32_t largebits, largememory; /* megabytes */ 145124208Sdesstatic BIGNUM *largebase; 146124208Sdes 147137015Sdesint gen_candidates(FILE *, int, int, BIGNUM *); 148137015Sdesint prime_test(FILE *, FILE *, u_int32_t, u_int32_t); 149124208Sdes 150124208Sdes/* 151124208Sdes * print moduli out in consistent form, 152124208Sdes */ 153124208Sdesstatic int 154124208Sdesqfileout(FILE * ofile, u_int32_t otype, u_int32_t otests, u_int32_t otries, 155124208Sdes u_int32_t osize, u_int32_t ogenerator, BIGNUM * omodulus) 156124208Sdes{ 157124208Sdes struct tm *gtm; 158124208Sdes time_t time_now; 159124208Sdes int res; 160124208Sdes 161124208Sdes time(&time_now); 162124208Sdes gtm = gmtime(&time_now); 163126274Sdes 164124208Sdes res = fprintf(ofile, "%04d%02d%02d%02d%02d%02d %u %u %u %u %x ", 165124208Sdes gtm->tm_year + 1900, gtm->tm_mon + 1, gtm->tm_mday, 166124208Sdes gtm->tm_hour, gtm->tm_min, gtm->tm_sec, 167124208Sdes otype, otests, otries, osize, ogenerator); 168124208Sdes 169124208Sdes if (res < 0) 170124208Sdes return (-1); 171124208Sdes 172124208Sdes if (BN_print_fp(ofile, omodulus) < 1) 173124208Sdes return (-1); 174124208Sdes 175124208Sdes res = fprintf(ofile, "\n"); 176124208Sdes fflush(ofile); 177124208Sdes 178124208Sdes return (res > 0 ? 0 : -1); 179124208Sdes} 180124208Sdes 181124208Sdes 182124208Sdes/* 183124208Sdes ** Sieve p's and q's with small factors 184124208Sdes */ 185124208Sdesstatic void 186124208Sdessieve_large(u_int32_t s) 187124208Sdes{ 188124208Sdes u_int32_t r, u; 189124208Sdes 190126274Sdes debug3("sieve_large %u", s); 191124208Sdes largetries++; 192124208Sdes /* r = largebase mod s */ 193124208Sdes r = BN_mod_word(largebase, s); 194124208Sdes if (r == 0) 195124208Sdes u = 0; /* s divides into largebase exactly */ 196124208Sdes else 197124208Sdes u = s - r; /* largebase+u is first entry divisible by s */ 198124208Sdes 199124208Sdes if (u < largebits * 2) { 200124208Sdes /* 201124208Sdes * The sieve omits p's and q's divisible by 2, so ensure that 202124208Sdes * largebase+u is odd. Then, step through the sieve in 203124208Sdes * increments of 2*s 204124208Sdes */ 205124208Sdes if (u & 0x1) 206124208Sdes u += s; /* Make largebase+u odd, and u even */ 207124208Sdes 208124208Sdes /* Mark all multiples of 2*s */ 209124208Sdes for (u /= 2; u < largebits; u += s) 210124208Sdes BIT_SET(LargeSieve, u); 211124208Sdes } 212124208Sdes 213124208Sdes /* r = p mod s */ 214124208Sdes r = (2 * r + 1) % s; 215124208Sdes if (r == 0) 216124208Sdes u = 0; /* s divides p exactly */ 217124208Sdes else 218124208Sdes u = s - r; /* p+u is first entry divisible by s */ 219124208Sdes 220124208Sdes if (u < largebits * 4) { 221124208Sdes /* 222124208Sdes * The sieve omits p's divisible by 4, so ensure that 223124208Sdes * largebase+u is not. Then, step through the sieve in 224124208Sdes * increments of 4*s 225124208Sdes */ 226124208Sdes while (u & 0x3) { 227124208Sdes if (SMALL_MAXIMUM - u < s) 228124208Sdes return; 229124208Sdes u += s; 230124208Sdes } 231124208Sdes 232124208Sdes /* Mark all multiples of 4*s */ 233124208Sdes for (u /= 4; u < largebits; u += s) 234124208Sdes BIT_SET(LargeSieve, u); 235124208Sdes } 236124208Sdes} 237124208Sdes 238124208Sdes/* 239137015Sdes * list candidates for Sophie-Germain primes (where q = (p-1)/2) 240124208Sdes * to standard output. 241124208Sdes * The list is checked against small known primes (less than 2**30). 242124208Sdes */ 243124208Sdesint 244124208Sdesgen_candidates(FILE *out, int memory, int power, BIGNUM *start) 245124208Sdes{ 246124208Sdes BIGNUM *q; 247124208Sdes u_int32_t j, r, s, t; 248124208Sdes u_int32_t smallwords = TINY_NUMBER >> 6; 249124208Sdes u_int32_t tinywords = TINY_NUMBER >> 6; 250124208Sdes time_t time_start, time_stop; 251124208Sdes int i, ret = 0; 252124208Sdes 253124208Sdes largememory = memory; 254124208Sdes 255137015Sdes if (memory != 0 && 256137015Sdes (memory < LARGE_MINIMUM || memory > LARGE_MAXIMUM)) { 257137015Sdes error("Invalid memory amount (min %ld, max %ld)", 258137015Sdes LARGE_MINIMUM, LARGE_MAXIMUM); 259137015Sdes return (-1); 260137015Sdes } 261137015Sdes 262124208Sdes /* 263126274Sdes * Set power to the length in bits of the prime to be generated. 264126274Sdes * This is changed to 1 less than the desired safe prime moduli p. 265126274Sdes */ 266124208Sdes if (power > TEST_MAXIMUM) { 267124208Sdes error("Too many bits: %u > %lu", power, TEST_MAXIMUM); 268124208Sdes return (-1); 269124208Sdes } else if (power < TEST_MINIMUM) { 270124208Sdes error("Too few bits: %u < %u", power, TEST_MINIMUM); 271124208Sdes return (-1); 272124208Sdes } 273124208Sdes power--; /* decrement before squaring */ 274124208Sdes 275124208Sdes /* 276126274Sdes * The density of ordinary primes is on the order of 1/bits, so the 277126274Sdes * density of safe primes should be about (1/bits)**2. Set test range 278126274Sdes * to something well above bits**2 to be reasonably sure (but not 279126274Sdes * guaranteed) of catching at least one safe prime. 280124208Sdes */ 281124208Sdes largewords = ((power * power) >> (SHIFT_WORD - TEST_POWER)); 282124208Sdes 283124208Sdes /* 284126274Sdes * Need idea of how much memory is available. We don't have to use all 285126274Sdes * of it. 286124208Sdes */ 287124208Sdes if (largememory > LARGE_MAXIMUM) { 288124208Sdes logit("Limited memory: %u MB; limit %lu MB", 289124208Sdes largememory, LARGE_MAXIMUM); 290124208Sdes largememory = LARGE_MAXIMUM; 291124208Sdes } 292124208Sdes 293124208Sdes if (largewords <= (largememory << SHIFT_MEGAWORD)) { 294124208Sdes logit("Increased memory: %u MB; need %u bytes", 295124208Sdes largememory, (largewords << SHIFT_BYTE)); 296124208Sdes largewords = (largememory << SHIFT_MEGAWORD); 297124208Sdes } else if (largememory > 0) { 298124208Sdes logit("Decreased memory: %u MB; want %u bytes", 299124208Sdes largememory, (largewords << SHIFT_BYTE)); 300124208Sdes largewords = (largememory << SHIFT_MEGAWORD); 301124208Sdes } 302124208Sdes 303124208Sdes TinySieve = calloc(tinywords, sizeof(u_int32_t)); 304124208Sdes if (TinySieve == NULL) { 305124208Sdes error("Insufficient memory for tiny sieve: need %u bytes", 306124208Sdes tinywords << SHIFT_BYTE); 307124208Sdes exit(1); 308124208Sdes } 309124208Sdes tinybits = tinywords << SHIFT_WORD; 310124208Sdes 311124208Sdes SmallSieve = calloc(smallwords, sizeof(u_int32_t)); 312124208Sdes if (SmallSieve == NULL) { 313124208Sdes error("Insufficient memory for small sieve: need %u bytes", 314124208Sdes smallwords << SHIFT_BYTE); 315124208Sdes xfree(TinySieve); 316124208Sdes exit(1); 317124208Sdes } 318124208Sdes smallbits = smallwords << SHIFT_WORD; 319124208Sdes 320124208Sdes /* 321124208Sdes * dynamically determine available memory 322124208Sdes */ 323124208Sdes while ((LargeSieve = calloc(largewords, sizeof(u_int32_t))) == NULL) 324124208Sdes largewords -= (1L << (SHIFT_MEGAWORD - 2)); /* 1/4 MB chunks */ 325124208Sdes 326124208Sdes largebits = largewords << SHIFT_WORD; 327124208Sdes largenumbers = largebits * 2; /* even numbers excluded */ 328124208Sdes 329124208Sdes /* validation check: count the number of primes tried */ 330124208Sdes largetries = 0; 331124208Sdes q = BN_new(); 332124208Sdes 333124208Sdes /* 334126274Sdes * Generate random starting point for subprime search, or use 335126274Sdes * specified parameter. 336124208Sdes */ 337124208Sdes largebase = BN_new(); 338124208Sdes if (start == NULL) 339124208Sdes BN_rand(largebase, power, 1, 1); 340124208Sdes else 341124208Sdes BN_copy(largebase, start); 342124208Sdes 343124208Sdes /* ensure odd */ 344124208Sdes BN_set_bit(largebase, 0); 345124208Sdes 346124208Sdes time(&time_start); 347124208Sdes 348126274Sdes logit("%.24s Sieve next %u plus %u-bit", ctime(&time_start), 349124208Sdes largenumbers, power); 350124208Sdes debug2("start point: 0x%s", BN_bn2hex(largebase)); 351124208Sdes 352124208Sdes /* 353126274Sdes * TinySieve 354126274Sdes */ 355124208Sdes for (i = 0; i < tinybits; i++) { 356124208Sdes if (BIT_TEST(TinySieve, i)) 357124208Sdes continue; /* 2*i+3 is composite */ 358124208Sdes 359124208Sdes /* The next tiny prime */ 360124208Sdes t = 2 * i + 3; 361124208Sdes 362124208Sdes /* Mark all multiples of t */ 363124208Sdes for (j = i + t; j < tinybits; j += t) 364124208Sdes BIT_SET(TinySieve, j); 365124208Sdes 366124208Sdes sieve_large(t); 367124208Sdes } 368124208Sdes 369124208Sdes /* 370126274Sdes * Start the small block search at the next possible prime. To avoid 371126274Sdes * fencepost errors, the last pass is skipped. 372126274Sdes */ 373124208Sdes for (smallbase = TINY_NUMBER + 3; 374124208Sdes smallbase < (SMALL_MAXIMUM - TINY_NUMBER); 375124208Sdes smallbase += TINY_NUMBER) { 376124208Sdes for (i = 0; i < tinybits; i++) { 377124208Sdes if (BIT_TEST(TinySieve, i)) 378124208Sdes continue; /* 2*i+3 is composite */ 379124208Sdes 380124208Sdes /* The next tiny prime */ 381124208Sdes t = 2 * i + 3; 382124208Sdes r = smallbase % t; 383124208Sdes 384124208Sdes if (r == 0) { 385124208Sdes s = 0; /* t divides into smallbase exactly */ 386124208Sdes } else { 387124208Sdes /* smallbase+s is first entry divisible by t */ 388124208Sdes s = t - r; 389124208Sdes } 390124208Sdes 391124208Sdes /* 392124208Sdes * The sieve omits even numbers, so ensure that 393124208Sdes * smallbase+s is odd. Then, step through the sieve 394124208Sdes * in increments of 2*t 395124208Sdes */ 396124208Sdes if (s & 1) 397124208Sdes s += t; /* Make smallbase+s odd, and s even */ 398124208Sdes 399124208Sdes /* Mark all multiples of 2*t */ 400124208Sdes for (s /= 2; s < smallbits; s += t) 401124208Sdes BIT_SET(SmallSieve, s); 402124208Sdes } 403124208Sdes 404124208Sdes /* 405126274Sdes * SmallSieve 406126274Sdes */ 407124208Sdes for (i = 0; i < smallbits; i++) { 408124208Sdes if (BIT_TEST(SmallSieve, i)) 409124208Sdes continue; /* 2*i+smallbase is composite */ 410124208Sdes 411124208Sdes /* The next small prime */ 412124208Sdes sieve_large((2 * i) + smallbase); 413124208Sdes } 414124208Sdes 415124208Sdes memset(SmallSieve, 0, smallwords << SHIFT_BYTE); 416124208Sdes } 417124208Sdes 418124208Sdes time(&time_stop); 419124208Sdes 420124208Sdes logit("%.24s Sieved with %u small primes in %ld seconds", 421124208Sdes ctime(&time_stop), largetries, (long) (time_stop - time_start)); 422124208Sdes 423124208Sdes for (j = r = 0; j < largebits; j++) { 424124208Sdes if (BIT_TEST(LargeSieve, j)) 425124208Sdes continue; /* Definitely composite, skip */ 426124208Sdes 427124208Sdes debug2("test q = largebase+%u", 2 * j); 428124208Sdes BN_set_word(q, 2 * j); 429124208Sdes BN_add(q, q, largebase); 430137015Sdes if (qfileout(out, QTYPE_SOPHIE_GERMAIN, QTEST_SIEVE, 431124208Sdes largetries, (power - 1) /* MSB */, (0), q) == -1) { 432124208Sdes ret = -1; 433124208Sdes break; 434124208Sdes } 435124208Sdes 436124208Sdes r++; /* count q */ 437124208Sdes } 438124208Sdes 439124208Sdes time(&time_stop); 440124208Sdes 441124208Sdes xfree(LargeSieve); 442124208Sdes xfree(SmallSieve); 443124208Sdes xfree(TinySieve); 444124208Sdes 445124208Sdes logit("%.24s Found %u candidates", ctime(&time_stop), r); 446124208Sdes 447124208Sdes return (ret); 448124208Sdes} 449124208Sdes 450124208Sdes/* 451124208Sdes * perform a Miller-Rabin primality test 452124208Sdes * on the list of candidates 453124208Sdes * (checking both q and p) 454124208Sdes * The result is a list of so-call "safe" primes 455124208Sdes */ 456124208Sdesint 457137015Sdesprime_test(FILE *in, FILE *out, u_int32_t trials, u_int32_t generator_wanted) 458124208Sdes{ 459124208Sdes BIGNUM *q, *p, *a; 460124208Sdes BN_CTX *ctx; 461124208Sdes char *cp, *lp; 462124208Sdes u_int32_t count_in = 0, count_out = 0, count_possible = 0; 463124208Sdes u_int32_t generator_known, in_tests, in_tries, in_type, in_size; 464124208Sdes time_t time_start, time_stop; 465124208Sdes int res; 466124208Sdes 467137015Sdes if (trials < TRIAL_MINIMUM) { 468137015Sdes error("Minimum primality trials is %d", TRIAL_MINIMUM); 469137015Sdes return (-1); 470137015Sdes } 471137015Sdes 472124208Sdes time(&time_start); 473124208Sdes 474124208Sdes p = BN_new(); 475124208Sdes q = BN_new(); 476124208Sdes ctx = BN_CTX_new(); 477124208Sdes 478124208Sdes debug2("%.24s Final %u Miller-Rabin trials (%x generator)", 479124208Sdes ctime(&time_start), trials, generator_wanted); 480124208Sdes 481124208Sdes res = 0; 482124208Sdes lp = xmalloc(QLINESIZE + 1); 483124208Sdes while (fgets(lp, QLINESIZE, in) != NULL) { 484124208Sdes int ll = strlen(lp); 485124208Sdes 486124208Sdes count_in++; 487124208Sdes if (ll < 14 || *lp == '!' || *lp == '#') { 488124208Sdes debug2("%10u: comment or short line", count_in); 489124208Sdes continue; 490124208Sdes } 491124208Sdes 492124208Sdes /* XXX - fragile parser */ 493124208Sdes /* time */ 494124208Sdes cp = &lp[14]; /* (skip) */ 495124208Sdes 496124208Sdes /* type */ 497124208Sdes in_type = strtoul(cp, &cp, 10); 498124208Sdes 499124208Sdes /* tests */ 500124208Sdes in_tests = strtoul(cp, &cp, 10); 501124208Sdes 502124208Sdes if (in_tests & QTEST_COMPOSITE) { 503124208Sdes debug2("%10u: known composite", count_in); 504124208Sdes continue; 505124208Sdes } 506126274Sdes 507124208Sdes /* tries */ 508124208Sdes in_tries = strtoul(cp, &cp, 10); 509124208Sdes 510124208Sdes /* size (most significant bit) */ 511124208Sdes in_size = strtoul(cp, &cp, 10); 512124208Sdes 513124208Sdes /* generator (hex) */ 514124208Sdes generator_known = strtoul(cp, &cp, 16); 515124208Sdes 516124208Sdes /* Skip white space */ 517124208Sdes cp += strspn(cp, " "); 518124208Sdes 519124208Sdes /* modulus (hex) */ 520124208Sdes switch (in_type) { 521137015Sdes case QTYPE_SOPHIE_GERMAIN: 522137015Sdes debug2("%10u: (%u) Sophie-Germain", count_in, in_type); 523124208Sdes a = q; 524124208Sdes BN_hex2bn(&a, cp); 525124208Sdes /* p = 2*q + 1 */ 526124208Sdes BN_lshift(p, q, 1); 527124208Sdes BN_add_word(p, 1); 528124208Sdes in_size += 1; 529124208Sdes generator_known = 0; 530124208Sdes break; 531126274Sdes case QTYPE_UNSTRUCTURED: 532126274Sdes case QTYPE_SAFE: 533126274Sdes case QTYPE_SCHNOOR: 534126274Sdes case QTYPE_STRONG: 535126274Sdes case QTYPE_UNKNOWN: 536124208Sdes debug2("%10u: (%u)", count_in, in_type); 537124208Sdes a = p; 538124208Sdes BN_hex2bn(&a, cp); 539124208Sdes /* q = (p-1) / 2 */ 540124208Sdes BN_rshift(q, p, 1); 541124208Sdes break; 542126274Sdes default: 543126274Sdes debug2("Unknown prime type"); 544126274Sdes break; 545124208Sdes } 546124208Sdes 547124208Sdes /* 548124208Sdes * due to earlier inconsistencies in interpretation, check 549124208Sdes * the proposed bit size. 550124208Sdes */ 551124208Sdes if (BN_num_bits(p) != (in_size + 1)) { 552124208Sdes debug2("%10u: bit size %u mismatch", count_in, in_size); 553124208Sdes continue; 554124208Sdes } 555124208Sdes if (in_size < QSIZE_MINIMUM) { 556124208Sdes debug2("%10u: bit size %u too short", count_in, in_size); 557124208Sdes continue; 558124208Sdes } 559124208Sdes 560124208Sdes if (in_tests & QTEST_MILLER_RABIN) 561124208Sdes in_tries += trials; 562124208Sdes else 563124208Sdes in_tries = trials; 564126274Sdes 565124208Sdes /* 566124208Sdes * guess unknown generator 567124208Sdes */ 568124208Sdes if (generator_known == 0) { 569124208Sdes if (BN_mod_word(p, 24) == 11) 570124208Sdes generator_known = 2; 571124208Sdes else if (BN_mod_word(p, 12) == 5) 572124208Sdes generator_known = 3; 573124208Sdes else { 574124208Sdes u_int32_t r = BN_mod_word(p, 10); 575124208Sdes 576126274Sdes if (r == 3 || r == 7) 577124208Sdes generator_known = 5; 578124208Sdes } 579124208Sdes } 580124208Sdes /* 581124208Sdes * skip tests when desired generator doesn't match 582124208Sdes */ 583124208Sdes if (generator_wanted > 0 && 584124208Sdes generator_wanted != generator_known) { 585124208Sdes debug2("%10u: generator %d != %d", 586124208Sdes count_in, generator_known, generator_wanted); 587124208Sdes continue; 588124208Sdes } 589124208Sdes 590126274Sdes /* 591126274Sdes * Primes with no known generator are useless for DH, so 592126274Sdes * skip those. 593126274Sdes */ 594126274Sdes if (generator_known == 0) { 595126274Sdes debug2("%10u: no known generator", count_in); 596126274Sdes continue; 597126274Sdes } 598126274Sdes 599124208Sdes count_possible++; 600124208Sdes 601124208Sdes /* 602126274Sdes * The (1/4)^N performance bound on Miller-Rabin is 603126274Sdes * extremely pessimistic, so don't spend a lot of time 604126274Sdes * really verifying that q is prime until after we know 605126274Sdes * that p is also prime. A single pass will weed out the 606124208Sdes * vast majority of composite q's. 607124208Sdes */ 608124208Sdes if (BN_is_prime(q, 1, NULL, ctx, NULL) <= 0) { 609126274Sdes debug("%10u: q failed first possible prime test", 610124208Sdes count_in); 611124208Sdes continue; 612124208Sdes } 613126274Sdes 614124208Sdes /* 615126274Sdes * q is possibly prime, so go ahead and really make sure 616126274Sdes * that p is prime. If it is, then we can go back and do 617126274Sdes * the same for q. If p is composite, chances are that 618124208Sdes * will show up on the first Rabin-Miller iteration so it 619124208Sdes * doesn't hurt to specify a high iteration count. 620124208Sdes */ 621124208Sdes if (!BN_is_prime(p, trials, NULL, ctx, NULL)) { 622126274Sdes debug("%10u: p is not prime", count_in); 623124208Sdes continue; 624124208Sdes } 625124208Sdes debug("%10u: p is almost certainly prime", count_in); 626124208Sdes 627124208Sdes /* recheck q more rigorously */ 628124208Sdes if (!BN_is_prime(q, trials - 1, NULL, ctx, NULL)) { 629124208Sdes debug("%10u: q is not prime", count_in); 630124208Sdes continue; 631124208Sdes } 632124208Sdes debug("%10u: q is almost certainly prime", count_in); 633124208Sdes 634126274Sdes if (qfileout(out, QTYPE_SAFE, (in_tests | QTEST_MILLER_RABIN), 635124208Sdes in_tries, in_size, generator_known, p)) { 636124208Sdes res = -1; 637124208Sdes break; 638124208Sdes } 639124208Sdes 640124208Sdes count_out++; 641124208Sdes } 642124208Sdes 643124208Sdes time(&time_stop); 644124208Sdes xfree(lp); 645124208Sdes BN_free(p); 646124208Sdes BN_free(q); 647124208Sdes BN_CTX_free(ctx); 648124208Sdes 649124208Sdes logit("%.24s Found %u safe primes of %u candidates in %ld seconds", 650126274Sdes ctime(&time_stop), count_out, count_possible, 651124208Sdes (long) (time_stop - time_start)); 652124208Sdes 653124208Sdes return (res); 654124208Sdes} 655