moduli.c revision 181111
1181111Sdes/* $OpenBSD: moduli.c,v 1.21 2008/06/26 09:19:40 djm 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" 41162852Sdes 42162852Sdes#include <sys/types.h> 43162852Sdes 44162852Sdes#include <openssl/bn.h> 45181111Sdes#include <openssl/dh.h> 46162852Sdes 47162852Sdes#include <stdio.h> 48162852Sdes#include <stdlib.h> 49162852Sdes#include <string.h> 50162852Sdes#include <stdarg.h> 51162852Sdes#include <time.h> 52162852Sdes 53124208Sdes#include "xmalloc.h" 54181111Sdes#include "dh.h" 55124208Sdes#include "log.h" 56124208Sdes 57124208Sdes/* 58124208Sdes * File output defines 59124208Sdes */ 60124208Sdes 61124208Sdes/* need line long enough for largest moduli plus headers */ 62137015Sdes#define QLINESIZE (100+8192) 63124208Sdes 64126274Sdes/* 65126274Sdes * Size: decimal. 66124208Sdes * Specifies the number of the most significant bit (0 to M). 67126274Sdes * WARNING: internally, usually 1 to N. 68124208Sdes */ 69137015Sdes#define QSIZE_MINIMUM (511) 70124208Sdes 71124208Sdes/* 72124208Sdes * Prime sieving defines 73124208Sdes */ 74124208Sdes 75124208Sdes/* Constant: assuming 8 bit bytes and 32 bit words */ 76137015Sdes#define SHIFT_BIT (3) 77137015Sdes#define SHIFT_BYTE (2) 78137015Sdes#define SHIFT_WORD (SHIFT_BIT+SHIFT_BYTE) 79137015Sdes#define SHIFT_MEGABYTE (20) 80137015Sdes#define SHIFT_MEGAWORD (SHIFT_MEGABYTE-SHIFT_BYTE) 81124208Sdes 82124208Sdes/* 83137015Sdes * Using virtual memory can cause thrashing. This should be the largest 84137015Sdes * number that is supported without a large amount of disk activity -- 85137015Sdes * that would increase the run time from hours to days or weeks! 86137015Sdes */ 87137015Sdes#define LARGE_MINIMUM (8UL) /* megabytes */ 88137015Sdes 89137015Sdes/* 90137015Sdes * Do not increase this number beyond the unsigned integer bit size. 91137015Sdes * Due to a multiple of 4, it must be LESS than 128 (yielding 2**30 bits). 92137015Sdes */ 93137015Sdes#define LARGE_MAXIMUM (127UL) /* megabytes */ 94137015Sdes 95137015Sdes/* 96124208Sdes * Constant: when used with 32-bit integers, the largest sieve prime 97124208Sdes * has to be less than 2**32. 98124208Sdes */ 99137015Sdes#define SMALL_MAXIMUM (0xffffffffUL) 100124208Sdes 101124208Sdes/* Constant: can sieve all primes less than 2**32, as 65537**2 > 2**32-1. */ 102137015Sdes#define TINY_NUMBER (1UL<<16) 103124208Sdes 104124208Sdes/* Ensure enough bit space for testing 2*q. */ 105149749Sdes#define TEST_MAXIMUM (1UL<<16) 106149749Sdes#define TEST_MINIMUM (QSIZE_MINIMUM + 1) 107149749Sdes/* real TEST_MINIMUM (1UL << (SHIFT_WORD - TEST_POWER)) */ 108149749Sdes#define TEST_POWER (3) /* 2**n, n < SHIFT_WORD */ 109124208Sdes 110124208Sdes/* bit operations on 32-bit words */ 111149749Sdes#define BIT_CLEAR(a,n) ((a)[(n)>>SHIFT_WORD] &= ~(1L << ((n) & 31))) 112149749Sdes#define BIT_SET(a,n) ((a)[(n)>>SHIFT_WORD] |= (1L << ((n) & 31))) 113149749Sdes#define BIT_TEST(a,n) ((a)[(n)>>SHIFT_WORD] & (1L << ((n) & 31))) 114124208Sdes 115124208Sdes/* 116124208Sdes * Prime testing defines 117124208Sdes */ 118124208Sdes 119137015Sdes/* Minimum number of primality tests to perform */ 120149749Sdes#define TRIAL_MINIMUM (4) 121137015Sdes 122124208Sdes/* 123124208Sdes * Sieving data (XXX - move to struct) 124124208Sdes */ 125124208Sdes 126124208Sdes/* sieve 2**16 */ 127124208Sdesstatic u_int32_t *TinySieve, tinybits; 128124208Sdes 129124208Sdes/* sieve 2**30 in 2**16 parts */ 130124208Sdesstatic u_int32_t *SmallSieve, smallbits, smallbase; 131124208Sdes 132124208Sdes/* sieve relative to the initial value */ 133124208Sdesstatic u_int32_t *LargeSieve, largewords, largetries, largenumbers; 134124208Sdesstatic u_int32_t largebits, largememory; /* megabytes */ 135124208Sdesstatic BIGNUM *largebase; 136124208Sdes 137149749Sdesint gen_candidates(FILE *, u_int32_t, u_int32_t, BIGNUM *); 138137015Sdesint prime_test(FILE *, FILE *, u_int32_t, u_int32_t); 139124208Sdes 140124208Sdes/* 141124208Sdes * print moduli out in consistent form, 142124208Sdes */ 143124208Sdesstatic int 144124208Sdesqfileout(FILE * ofile, u_int32_t otype, u_int32_t otests, u_int32_t otries, 145124208Sdes u_int32_t osize, u_int32_t ogenerator, BIGNUM * omodulus) 146124208Sdes{ 147124208Sdes struct tm *gtm; 148124208Sdes time_t time_now; 149124208Sdes int res; 150124208Sdes 151124208Sdes time(&time_now); 152124208Sdes gtm = gmtime(&time_now); 153126274Sdes 154124208Sdes res = fprintf(ofile, "%04d%02d%02d%02d%02d%02d %u %u %u %u %x ", 155124208Sdes gtm->tm_year + 1900, gtm->tm_mon + 1, gtm->tm_mday, 156124208Sdes gtm->tm_hour, gtm->tm_min, gtm->tm_sec, 157124208Sdes otype, otests, otries, osize, ogenerator); 158124208Sdes 159124208Sdes if (res < 0) 160124208Sdes return (-1); 161124208Sdes 162124208Sdes if (BN_print_fp(ofile, omodulus) < 1) 163124208Sdes return (-1); 164124208Sdes 165124208Sdes res = fprintf(ofile, "\n"); 166124208Sdes fflush(ofile); 167124208Sdes 168124208Sdes return (res > 0 ? 0 : -1); 169124208Sdes} 170124208Sdes 171124208Sdes 172124208Sdes/* 173124208Sdes ** Sieve p's and q's with small factors 174124208Sdes */ 175124208Sdesstatic void 176124208Sdessieve_large(u_int32_t s) 177124208Sdes{ 178124208Sdes u_int32_t r, u; 179124208Sdes 180126274Sdes debug3("sieve_large %u", s); 181124208Sdes largetries++; 182124208Sdes /* r = largebase mod s */ 183124208Sdes r = BN_mod_word(largebase, s); 184124208Sdes if (r == 0) 185124208Sdes u = 0; /* s divides into largebase exactly */ 186124208Sdes else 187124208Sdes u = s - r; /* largebase+u is first entry divisible by s */ 188124208Sdes 189124208Sdes if (u < largebits * 2) { 190124208Sdes /* 191124208Sdes * The sieve omits p's and q's divisible by 2, so ensure that 192124208Sdes * largebase+u is odd. Then, step through the sieve in 193124208Sdes * increments of 2*s 194124208Sdes */ 195124208Sdes if (u & 0x1) 196124208Sdes u += s; /* Make largebase+u odd, and u even */ 197124208Sdes 198124208Sdes /* Mark all multiples of 2*s */ 199124208Sdes for (u /= 2; u < largebits; u += s) 200124208Sdes BIT_SET(LargeSieve, u); 201124208Sdes } 202124208Sdes 203124208Sdes /* r = p mod s */ 204124208Sdes r = (2 * r + 1) % s; 205124208Sdes if (r == 0) 206124208Sdes u = 0; /* s divides p exactly */ 207124208Sdes else 208124208Sdes u = s - r; /* p+u is first entry divisible by s */ 209124208Sdes 210124208Sdes if (u < largebits * 4) { 211124208Sdes /* 212124208Sdes * The sieve omits p's divisible by 4, so ensure that 213124208Sdes * largebase+u is not. Then, step through the sieve in 214124208Sdes * increments of 4*s 215124208Sdes */ 216124208Sdes while (u & 0x3) { 217124208Sdes if (SMALL_MAXIMUM - u < s) 218124208Sdes return; 219124208Sdes u += s; 220124208Sdes } 221124208Sdes 222124208Sdes /* Mark all multiples of 4*s */ 223124208Sdes for (u /= 4; u < largebits; u += s) 224124208Sdes BIT_SET(LargeSieve, u); 225124208Sdes } 226124208Sdes} 227124208Sdes 228124208Sdes/* 229137015Sdes * list candidates for Sophie-Germain primes (where q = (p-1)/2) 230124208Sdes * to standard output. 231124208Sdes * The list is checked against small known primes (less than 2**30). 232124208Sdes */ 233124208Sdesint 234149749Sdesgen_candidates(FILE *out, u_int32_t memory, u_int32_t power, BIGNUM *start) 235124208Sdes{ 236124208Sdes BIGNUM *q; 237124208Sdes u_int32_t j, r, s, t; 238124208Sdes u_int32_t smallwords = TINY_NUMBER >> 6; 239124208Sdes u_int32_t tinywords = TINY_NUMBER >> 6; 240124208Sdes time_t time_start, time_stop; 241149749Sdes u_int32_t i; 242149749Sdes int ret = 0; 243124208Sdes 244124208Sdes largememory = memory; 245124208Sdes 246137015Sdes if (memory != 0 && 247149749Sdes (memory < LARGE_MINIMUM || memory > LARGE_MAXIMUM)) { 248137015Sdes error("Invalid memory amount (min %ld, max %ld)", 249137015Sdes LARGE_MINIMUM, LARGE_MAXIMUM); 250137015Sdes return (-1); 251137015Sdes } 252137015Sdes 253124208Sdes /* 254126274Sdes * Set power to the length in bits of the prime to be generated. 255126274Sdes * This is changed to 1 less than the desired safe prime moduli p. 256126274Sdes */ 257124208Sdes if (power > TEST_MAXIMUM) { 258124208Sdes error("Too many bits: %u > %lu", power, TEST_MAXIMUM); 259124208Sdes return (-1); 260124208Sdes } else if (power < TEST_MINIMUM) { 261124208Sdes error("Too few bits: %u < %u", power, TEST_MINIMUM); 262124208Sdes return (-1); 263124208Sdes } 264124208Sdes power--; /* decrement before squaring */ 265124208Sdes 266124208Sdes /* 267126274Sdes * The density of ordinary primes is on the order of 1/bits, so the 268126274Sdes * density of safe primes should be about (1/bits)**2. Set test range 269126274Sdes * to something well above bits**2 to be reasonably sure (but not 270126274Sdes * guaranteed) of catching at least one safe prime. 271124208Sdes */ 272124208Sdes largewords = ((power * power) >> (SHIFT_WORD - TEST_POWER)); 273124208Sdes 274124208Sdes /* 275126274Sdes * Need idea of how much memory is available. We don't have to use all 276126274Sdes * of it. 277124208Sdes */ 278124208Sdes if (largememory > LARGE_MAXIMUM) { 279124208Sdes logit("Limited memory: %u MB; limit %lu MB", 280124208Sdes largememory, LARGE_MAXIMUM); 281124208Sdes largememory = LARGE_MAXIMUM; 282124208Sdes } 283124208Sdes 284124208Sdes if (largewords <= (largememory << SHIFT_MEGAWORD)) { 285124208Sdes logit("Increased memory: %u MB; need %u bytes", 286124208Sdes largememory, (largewords << SHIFT_BYTE)); 287124208Sdes largewords = (largememory << SHIFT_MEGAWORD); 288124208Sdes } else if (largememory > 0) { 289124208Sdes logit("Decreased memory: %u MB; want %u bytes", 290124208Sdes largememory, (largewords << SHIFT_BYTE)); 291124208Sdes largewords = (largememory << SHIFT_MEGAWORD); 292124208Sdes } 293124208Sdes 294162852Sdes TinySieve = xcalloc(tinywords, sizeof(u_int32_t)); 295124208Sdes tinybits = tinywords << SHIFT_WORD; 296124208Sdes 297162852Sdes SmallSieve = xcalloc(smallwords, sizeof(u_int32_t)); 298124208Sdes smallbits = smallwords << SHIFT_WORD; 299124208Sdes 300124208Sdes /* 301124208Sdes * dynamically determine available memory 302124208Sdes */ 303124208Sdes while ((LargeSieve = calloc(largewords, sizeof(u_int32_t))) == NULL) 304124208Sdes largewords -= (1L << (SHIFT_MEGAWORD - 2)); /* 1/4 MB chunks */ 305124208Sdes 306124208Sdes largebits = largewords << SHIFT_WORD; 307124208Sdes largenumbers = largebits * 2; /* even numbers excluded */ 308124208Sdes 309124208Sdes /* validation check: count the number of primes tried */ 310124208Sdes largetries = 0; 311164146Sdes if ((q = BN_new()) == NULL) 312164146Sdes fatal("BN_new failed"); 313124208Sdes 314124208Sdes /* 315126274Sdes * Generate random starting point for subprime search, or use 316126274Sdes * specified parameter. 317124208Sdes */ 318164146Sdes if ((largebase = BN_new()) == NULL) 319164146Sdes fatal("BN_new failed"); 320164146Sdes if (start == NULL) { 321164146Sdes if (BN_rand(largebase, power, 1, 1) == 0) 322164146Sdes fatal("BN_rand failed"); 323164146Sdes } else { 324164146Sdes if (BN_copy(largebase, start) == NULL) 325164146Sdes fatal("BN_copy: failed"); 326164146Sdes } 327124208Sdes 328124208Sdes /* ensure odd */ 329164146Sdes if (BN_set_bit(largebase, 0) == 0) 330164146Sdes fatal("BN_set_bit: failed"); 331124208Sdes 332124208Sdes time(&time_start); 333124208Sdes 334126274Sdes logit("%.24s Sieve next %u plus %u-bit", ctime(&time_start), 335124208Sdes largenumbers, power); 336124208Sdes debug2("start point: 0x%s", BN_bn2hex(largebase)); 337124208Sdes 338124208Sdes /* 339126274Sdes * TinySieve 340126274Sdes */ 341124208Sdes for (i = 0; i < tinybits; i++) { 342124208Sdes if (BIT_TEST(TinySieve, i)) 343124208Sdes continue; /* 2*i+3 is composite */ 344124208Sdes 345124208Sdes /* The next tiny prime */ 346124208Sdes t = 2 * i + 3; 347124208Sdes 348124208Sdes /* Mark all multiples of t */ 349124208Sdes for (j = i + t; j < tinybits; j += t) 350124208Sdes BIT_SET(TinySieve, j); 351124208Sdes 352124208Sdes sieve_large(t); 353124208Sdes } 354124208Sdes 355124208Sdes /* 356126274Sdes * Start the small block search at the next possible prime. To avoid 357126274Sdes * fencepost errors, the last pass is skipped. 358126274Sdes */ 359124208Sdes for (smallbase = TINY_NUMBER + 3; 360149749Sdes smallbase < (SMALL_MAXIMUM - TINY_NUMBER); 361149749Sdes smallbase += TINY_NUMBER) { 362124208Sdes for (i = 0; i < tinybits; i++) { 363124208Sdes if (BIT_TEST(TinySieve, i)) 364124208Sdes continue; /* 2*i+3 is composite */ 365124208Sdes 366124208Sdes /* The next tiny prime */ 367124208Sdes t = 2 * i + 3; 368124208Sdes r = smallbase % t; 369124208Sdes 370124208Sdes if (r == 0) { 371124208Sdes s = 0; /* t divides into smallbase exactly */ 372124208Sdes } else { 373124208Sdes /* smallbase+s is first entry divisible by t */ 374124208Sdes s = t - r; 375124208Sdes } 376124208Sdes 377124208Sdes /* 378124208Sdes * The sieve omits even numbers, so ensure that 379124208Sdes * smallbase+s is odd. Then, step through the sieve 380124208Sdes * in increments of 2*t 381124208Sdes */ 382124208Sdes if (s & 1) 383124208Sdes s += t; /* Make smallbase+s odd, and s even */ 384124208Sdes 385124208Sdes /* Mark all multiples of 2*t */ 386124208Sdes for (s /= 2; s < smallbits; s += t) 387124208Sdes BIT_SET(SmallSieve, s); 388124208Sdes } 389124208Sdes 390124208Sdes /* 391126274Sdes * SmallSieve 392126274Sdes */ 393124208Sdes for (i = 0; i < smallbits; i++) { 394124208Sdes if (BIT_TEST(SmallSieve, i)) 395124208Sdes continue; /* 2*i+smallbase is composite */ 396124208Sdes 397124208Sdes /* The next small prime */ 398124208Sdes sieve_large((2 * i) + smallbase); 399124208Sdes } 400124208Sdes 401124208Sdes memset(SmallSieve, 0, smallwords << SHIFT_BYTE); 402124208Sdes } 403124208Sdes 404124208Sdes time(&time_stop); 405124208Sdes 406124208Sdes logit("%.24s Sieved with %u small primes in %ld seconds", 407124208Sdes ctime(&time_stop), largetries, (long) (time_stop - time_start)); 408124208Sdes 409124208Sdes for (j = r = 0; j < largebits; j++) { 410124208Sdes if (BIT_TEST(LargeSieve, j)) 411124208Sdes continue; /* Definitely composite, skip */ 412124208Sdes 413124208Sdes debug2("test q = largebase+%u", 2 * j); 414164146Sdes if (BN_set_word(q, 2 * j) == 0) 415164146Sdes fatal("BN_set_word failed"); 416164146Sdes if (BN_add(q, q, largebase) == 0) 417164146Sdes fatal("BN_add failed"); 418181111Sdes if (qfileout(out, MODULI_TYPE_SOPHIE_GERMAIN, 419181111Sdes MODULI_TESTS_SIEVE, largetries, 420181111Sdes (power - 1) /* MSB */, (0), q) == -1) { 421124208Sdes ret = -1; 422124208Sdes break; 423124208Sdes } 424124208Sdes 425124208Sdes r++; /* count q */ 426124208Sdes } 427124208Sdes 428124208Sdes time(&time_stop); 429124208Sdes 430124208Sdes xfree(LargeSieve); 431124208Sdes xfree(SmallSieve); 432124208Sdes xfree(TinySieve); 433124208Sdes 434124208Sdes logit("%.24s Found %u candidates", ctime(&time_stop), r); 435124208Sdes 436124208Sdes return (ret); 437124208Sdes} 438124208Sdes 439124208Sdes/* 440124208Sdes * perform a Miller-Rabin primality test 441124208Sdes * on the list of candidates 442124208Sdes * (checking both q and p) 443124208Sdes * The result is a list of so-call "safe" primes 444124208Sdes */ 445124208Sdesint 446137015Sdesprime_test(FILE *in, FILE *out, u_int32_t trials, u_int32_t generator_wanted) 447124208Sdes{ 448124208Sdes BIGNUM *q, *p, *a; 449124208Sdes BN_CTX *ctx; 450124208Sdes char *cp, *lp; 451124208Sdes u_int32_t count_in = 0, count_out = 0, count_possible = 0; 452124208Sdes u_int32_t generator_known, in_tests, in_tries, in_type, in_size; 453124208Sdes time_t time_start, time_stop; 454124208Sdes int res; 455124208Sdes 456137015Sdes if (trials < TRIAL_MINIMUM) { 457137015Sdes error("Minimum primality trials is %d", TRIAL_MINIMUM); 458137015Sdes return (-1); 459137015Sdes } 460137015Sdes 461124208Sdes time(&time_start); 462124208Sdes 463164146Sdes if ((p = BN_new()) == NULL) 464164146Sdes fatal("BN_new failed"); 465164146Sdes if ((q = BN_new()) == NULL) 466164146Sdes fatal("BN_new failed"); 467164146Sdes if ((ctx = BN_CTX_new()) == NULL) 468164146Sdes fatal("BN_CTX_new failed"); 469124208Sdes 470124208Sdes debug2("%.24s Final %u Miller-Rabin trials (%x generator)", 471124208Sdes ctime(&time_start), trials, generator_wanted); 472124208Sdes 473124208Sdes res = 0; 474124208Sdes lp = xmalloc(QLINESIZE + 1); 475181111Sdes while (fgets(lp, QLINESIZE + 1, in) != NULL) { 476124208Sdes count_in++; 477181111Sdes if (strlen(lp) < 14 || *lp == '!' || *lp == '#') { 478124208Sdes debug2("%10u: comment or short line", count_in); 479124208Sdes continue; 480124208Sdes } 481124208Sdes 482124208Sdes /* XXX - fragile parser */ 483124208Sdes /* time */ 484124208Sdes cp = &lp[14]; /* (skip) */ 485124208Sdes 486124208Sdes /* type */ 487124208Sdes in_type = strtoul(cp, &cp, 10); 488124208Sdes 489124208Sdes /* tests */ 490124208Sdes in_tests = strtoul(cp, &cp, 10); 491124208Sdes 492181111Sdes if (in_tests & MODULI_TESTS_COMPOSITE) { 493124208Sdes debug2("%10u: known composite", count_in); 494124208Sdes continue; 495124208Sdes } 496126274Sdes 497124208Sdes /* tries */ 498124208Sdes in_tries = strtoul(cp, &cp, 10); 499124208Sdes 500124208Sdes /* size (most significant bit) */ 501124208Sdes in_size = strtoul(cp, &cp, 10); 502124208Sdes 503124208Sdes /* generator (hex) */ 504124208Sdes generator_known = strtoul(cp, &cp, 16); 505124208Sdes 506124208Sdes /* Skip white space */ 507124208Sdes cp += strspn(cp, " "); 508124208Sdes 509124208Sdes /* modulus (hex) */ 510124208Sdes switch (in_type) { 511181111Sdes case MODULI_TYPE_SOPHIE_GERMAIN: 512137015Sdes debug2("%10u: (%u) Sophie-Germain", count_in, in_type); 513124208Sdes a = q; 514164146Sdes if (BN_hex2bn(&a, cp) == 0) 515164146Sdes fatal("BN_hex2bn failed"); 516124208Sdes /* p = 2*q + 1 */ 517164146Sdes if (BN_lshift(p, q, 1) == 0) 518164146Sdes fatal("BN_lshift failed"); 519164146Sdes if (BN_add_word(p, 1) == 0) 520164146Sdes fatal("BN_add_word failed"); 521124208Sdes in_size += 1; 522124208Sdes generator_known = 0; 523124208Sdes break; 524181111Sdes case MODULI_TYPE_UNSTRUCTURED: 525181111Sdes case MODULI_TYPE_SAFE: 526181111Sdes case MODULI_TYPE_SCHNORR: 527181111Sdes case MODULI_TYPE_STRONG: 528181111Sdes case MODULI_TYPE_UNKNOWN: 529124208Sdes debug2("%10u: (%u)", count_in, in_type); 530124208Sdes a = p; 531164146Sdes if (BN_hex2bn(&a, cp) == 0) 532164146Sdes fatal("BN_hex2bn failed"); 533124208Sdes /* q = (p-1) / 2 */ 534164146Sdes if (BN_rshift(q, p, 1) == 0) 535164146Sdes fatal("BN_rshift failed"); 536124208Sdes break; 537126274Sdes default: 538126274Sdes debug2("Unknown prime type"); 539126274Sdes break; 540124208Sdes } 541124208Sdes 542124208Sdes /* 543124208Sdes * due to earlier inconsistencies in interpretation, check 544124208Sdes * the proposed bit size. 545124208Sdes */ 546149749Sdes if ((u_int32_t)BN_num_bits(p) != (in_size + 1)) { 547124208Sdes debug2("%10u: bit size %u mismatch", count_in, in_size); 548124208Sdes continue; 549124208Sdes } 550124208Sdes if (in_size < QSIZE_MINIMUM) { 551124208Sdes debug2("%10u: bit size %u too short", count_in, in_size); 552124208Sdes continue; 553124208Sdes } 554124208Sdes 555181111Sdes if (in_tests & MODULI_TESTS_MILLER_RABIN) 556124208Sdes in_tries += trials; 557124208Sdes else 558124208Sdes in_tries = trials; 559126274Sdes 560124208Sdes /* 561124208Sdes * guess unknown generator 562124208Sdes */ 563124208Sdes if (generator_known == 0) { 564124208Sdes if (BN_mod_word(p, 24) == 11) 565124208Sdes generator_known = 2; 566124208Sdes else if (BN_mod_word(p, 12) == 5) 567124208Sdes generator_known = 3; 568124208Sdes else { 569124208Sdes u_int32_t r = BN_mod_word(p, 10); 570124208Sdes 571126274Sdes if (r == 3 || r == 7) 572124208Sdes generator_known = 5; 573124208Sdes } 574124208Sdes } 575124208Sdes /* 576124208Sdes * skip tests when desired generator doesn't match 577124208Sdes */ 578124208Sdes if (generator_wanted > 0 && 579124208Sdes generator_wanted != generator_known) { 580124208Sdes debug2("%10u: generator %d != %d", 581124208Sdes count_in, generator_known, generator_wanted); 582124208Sdes continue; 583124208Sdes } 584124208Sdes 585126274Sdes /* 586126274Sdes * Primes with no known generator are useless for DH, so 587126274Sdes * skip those. 588126274Sdes */ 589126274Sdes if (generator_known == 0) { 590126274Sdes debug2("%10u: no known generator", count_in); 591126274Sdes continue; 592126274Sdes } 593126274Sdes 594124208Sdes count_possible++; 595124208Sdes 596124208Sdes /* 597126274Sdes * The (1/4)^N performance bound on Miller-Rabin is 598126274Sdes * extremely pessimistic, so don't spend a lot of time 599126274Sdes * really verifying that q is prime until after we know 600126274Sdes * that p is also prime. A single pass will weed out the 601124208Sdes * vast majority of composite q's. 602124208Sdes */ 603124208Sdes if (BN_is_prime(q, 1, NULL, ctx, NULL) <= 0) { 604126274Sdes debug("%10u: q failed first possible prime test", 605124208Sdes count_in); 606124208Sdes continue; 607124208Sdes } 608126274Sdes 609124208Sdes /* 610126274Sdes * q is possibly prime, so go ahead and really make sure 611126274Sdes * that p is prime. If it is, then we can go back and do 612126274Sdes * the same for q. If p is composite, chances are that 613124208Sdes * will show up on the first Rabin-Miller iteration so it 614124208Sdes * doesn't hurt to specify a high iteration count. 615124208Sdes */ 616124208Sdes if (!BN_is_prime(p, trials, NULL, ctx, NULL)) { 617126274Sdes debug("%10u: p is not prime", count_in); 618124208Sdes continue; 619124208Sdes } 620124208Sdes debug("%10u: p is almost certainly prime", count_in); 621124208Sdes 622124208Sdes /* recheck q more rigorously */ 623124208Sdes if (!BN_is_prime(q, trials - 1, NULL, ctx, NULL)) { 624124208Sdes debug("%10u: q is not prime", count_in); 625124208Sdes continue; 626124208Sdes } 627124208Sdes debug("%10u: q is almost certainly prime", count_in); 628124208Sdes 629181111Sdes if (qfileout(out, MODULI_TYPE_SAFE, 630181111Sdes in_tests | MODULI_TESTS_MILLER_RABIN, 631124208Sdes in_tries, in_size, generator_known, p)) { 632124208Sdes res = -1; 633124208Sdes break; 634124208Sdes } 635124208Sdes 636124208Sdes count_out++; 637124208Sdes } 638124208Sdes 639124208Sdes time(&time_stop); 640124208Sdes xfree(lp); 641124208Sdes BN_free(p); 642124208Sdes BN_free(q); 643124208Sdes BN_CTX_free(ctx); 644124208Sdes 645124208Sdes logit("%.24s Found %u safe primes of %u candidates in %ld seconds", 646126274Sdes ctime(&time_stop), count_out, count_possible, 647124208Sdes (long) (time_stop - time_start)); 648124208Sdes 649124208Sdes return (res); 650124208Sdes} 651