moduli.c revision 164146
1164146Sdes/* $OpenBSD: moduli.c,v 1.19 2006/11/06 21:25:28 markus 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> 45162852Sdes 46162852Sdes#include <stdio.h> 47162852Sdes#include <stdlib.h> 48162852Sdes#include <string.h> 49162852Sdes#include <stdarg.h> 50162852Sdes#include <time.h> 51162852Sdes 52124208Sdes#include "xmalloc.h" 53124208Sdes#include "log.h" 54124208Sdes 55124208Sdes/* 56124208Sdes * File output defines 57124208Sdes */ 58124208Sdes 59124208Sdes/* need line long enough for largest moduli plus headers */ 60137015Sdes#define QLINESIZE (100+8192) 61124208Sdes 62124208Sdes/* Type: decimal. 63124208Sdes * Specifies the internal structure of the prime modulus. 64124208Sdes */ 65137015Sdes#define QTYPE_UNKNOWN (0) 66137015Sdes#define QTYPE_UNSTRUCTURED (1) 67137015Sdes#define QTYPE_SAFE (2) 68146998Sdes#define QTYPE_SCHNORR (3) 69137015Sdes#define QTYPE_SOPHIE_GERMAIN (4) 70137015Sdes#define QTYPE_STRONG (5) 71124208Sdes 72124208Sdes/* Tests: decimal (bit field). 73124208Sdes * Specifies the methods used in checking for primality. 74124208Sdes * Usually, more than one test is used. 75124208Sdes */ 76137015Sdes#define QTEST_UNTESTED (0x00) 77137015Sdes#define QTEST_COMPOSITE (0x01) 78137015Sdes#define QTEST_SIEVE (0x02) 79137015Sdes#define QTEST_MILLER_RABIN (0x04) 80137015Sdes#define QTEST_JACOBI (0x08) 81137015Sdes#define QTEST_ELLIPTIC (0x10) 82124208Sdes 83126274Sdes/* 84126274Sdes * Size: decimal. 85124208Sdes * Specifies the number of the most significant bit (0 to M). 86126274Sdes * WARNING: internally, usually 1 to N. 87124208Sdes */ 88137015Sdes#define QSIZE_MINIMUM (511) 89124208Sdes 90124208Sdes/* 91124208Sdes * Prime sieving defines 92124208Sdes */ 93124208Sdes 94124208Sdes/* Constant: assuming 8 bit bytes and 32 bit words */ 95137015Sdes#define SHIFT_BIT (3) 96137015Sdes#define SHIFT_BYTE (2) 97137015Sdes#define SHIFT_WORD (SHIFT_BIT+SHIFT_BYTE) 98137015Sdes#define SHIFT_MEGABYTE (20) 99137015Sdes#define SHIFT_MEGAWORD (SHIFT_MEGABYTE-SHIFT_BYTE) 100124208Sdes 101124208Sdes/* 102137015Sdes * Using virtual memory can cause thrashing. This should be the largest 103137015Sdes * number that is supported without a large amount of disk activity -- 104137015Sdes * that would increase the run time from hours to days or weeks! 105137015Sdes */ 106137015Sdes#define LARGE_MINIMUM (8UL) /* megabytes */ 107137015Sdes 108137015Sdes/* 109137015Sdes * Do not increase this number beyond the unsigned integer bit size. 110137015Sdes * Due to a multiple of 4, it must be LESS than 128 (yielding 2**30 bits). 111137015Sdes */ 112137015Sdes#define LARGE_MAXIMUM (127UL) /* megabytes */ 113137015Sdes 114137015Sdes/* 115124208Sdes * Constant: when used with 32-bit integers, the largest sieve prime 116124208Sdes * has to be less than 2**32. 117124208Sdes */ 118137015Sdes#define SMALL_MAXIMUM (0xffffffffUL) 119124208Sdes 120124208Sdes/* Constant: can sieve all primes less than 2**32, as 65537**2 > 2**32-1. */ 121137015Sdes#define TINY_NUMBER (1UL<<16) 122124208Sdes 123124208Sdes/* Ensure enough bit space for testing 2*q. */ 124149749Sdes#define TEST_MAXIMUM (1UL<<16) 125149749Sdes#define TEST_MINIMUM (QSIZE_MINIMUM + 1) 126149749Sdes/* real TEST_MINIMUM (1UL << (SHIFT_WORD - TEST_POWER)) */ 127149749Sdes#define TEST_POWER (3) /* 2**n, n < SHIFT_WORD */ 128124208Sdes 129124208Sdes/* bit operations on 32-bit words */ 130149749Sdes#define BIT_CLEAR(a,n) ((a)[(n)>>SHIFT_WORD] &= ~(1L << ((n) & 31))) 131149749Sdes#define BIT_SET(a,n) ((a)[(n)>>SHIFT_WORD] |= (1L << ((n) & 31))) 132149749Sdes#define BIT_TEST(a,n) ((a)[(n)>>SHIFT_WORD] & (1L << ((n) & 31))) 133124208Sdes 134124208Sdes/* 135124208Sdes * Prime testing defines 136124208Sdes */ 137124208Sdes 138137015Sdes/* Minimum number of primality tests to perform */ 139149749Sdes#define TRIAL_MINIMUM (4) 140137015Sdes 141124208Sdes/* 142124208Sdes * Sieving data (XXX - move to struct) 143124208Sdes */ 144124208Sdes 145124208Sdes/* sieve 2**16 */ 146124208Sdesstatic u_int32_t *TinySieve, tinybits; 147124208Sdes 148124208Sdes/* sieve 2**30 in 2**16 parts */ 149124208Sdesstatic u_int32_t *SmallSieve, smallbits, smallbase; 150124208Sdes 151124208Sdes/* sieve relative to the initial value */ 152124208Sdesstatic u_int32_t *LargeSieve, largewords, largetries, largenumbers; 153124208Sdesstatic u_int32_t largebits, largememory; /* megabytes */ 154124208Sdesstatic BIGNUM *largebase; 155124208Sdes 156149749Sdesint gen_candidates(FILE *, u_int32_t, u_int32_t, BIGNUM *); 157137015Sdesint prime_test(FILE *, FILE *, u_int32_t, u_int32_t); 158124208Sdes 159124208Sdes/* 160124208Sdes * print moduli out in consistent form, 161124208Sdes */ 162124208Sdesstatic int 163124208Sdesqfileout(FILE * ofile, u_int32_t otype, u_int32_t otests, u_int32_t otries, 164124208Sdes u_int32_t osize, u_int32_t ogenerator, BIGNUM * omodulus) 165124208Sdes{ 166124208Sdes struct tm *gtm; 167124208Sdes time_t time_now; 168124208Sdes int res; 169124208Sdes 170124208Sdes time(&time_now); 171124208Sdes gtm = gmtime(&time_now); 172126274Sdes 173124208Sdes res = fprintf(ofile, "%04d%02d%02d%02d%02d%02d %u %u %u %u %x ", 174124208Sdes gtm->tm_year + 1900, gtm->tm_mon + 1, gtm->tm_mday, 175124208Sdes gtm->tm_hour, gtm->tm_min, gtm->tm_sec, 176124208Sdes otype, otests, otries, osize, ogenerator); 177124208Sdes 178124208Sdes if (res < 0) 179124208Sdes return (-1); 180124208Sdes 181124208Sdes if (BN_print_fp(ofile, omodulus) < 1) 182124208Sdes return (-1); 183124208Sdes 184124208Sdes res = fprintf(ofile, "\n"); 185124208Sdes fflush(ofile); 186124208Sdes 187124208Sdes return (res > 0 ? 0 : -1); 188124208Sdes} 189124208Sdes 190124208Sdes 191124208Sdes/* 192124208Sdes ** Sieve p's and q's with small factors 193124208Sdes */ 194124208Sdesstatic void 195124208Sdessieve_large(u_int32_t s) 196124208Sdes{ 197124208Sdes u_int32_t r, u; 198124208Sdes 199126274Sdes debug3("sieve_large %u", s); 200124208Sdes largetries++; 201124208Sdes /* r = largebase mod s */ 202124208Sdes r = BN_mod_word(largebase, s); 203124208Sdes if (r == 0) 204124208Sdes u = 0; /* s divides into largebase exactly */ 205124208Sdes else 206124208Sdes u = s - r; /* largebase+u is first entry divisible by s */ 207124208Sdes 208124208Sdes if (u < largebits * 2) { 209124208Sdes /* 210124208Sdes * The sieve omits p's and q's divisible by 2, so ensure that 211124208Sdes * largebase+u is odd. Then, step through the sieve in 212124208Sdes * increments of 2*s 213124208Sdes */ 214124208Sdes if (u & 0x1) 215124208Sdes u += s; /* Make largebase+u odd, and u even */ 216124208Sdes 217124208Sdes /* Mark all multiples of 2*s */ 218124208Sdes for (u /= 2; u < largebits; u += s) 219124208Sdes BIT_SET(LargeSieve, u); 220124208Sdes } 221124208Sdes 222124208Sdes /* r = p mod s */ 223124208Sdes r = (2 * r + 1) % s; 224124208Sdes if (r == 0) 225124208Sdes u = 0; /* s divides p exactly */ 226124208Sdes else 227124208Sdes u = s - r; /* p+u is first entry divisible by s */ 228124208Sdes 229124208Sdes if (u < largebits * 4) { 230124208Sdes /* 231124208Sdes * The sieve omits p's divisible by 4, so ensure that 232124208Sdes * largebase+u is not. Then, step through the sieve in 233124208Sdes * increments of 4*s 234124208Sdes */ 235124208Sdes while (u & 0x3) { 236124208Sdes if (SMALL_MAXIMUM - u < s) 237124208Sdes return; 238124208Sdes u += s; 239124208Sdes } 240124208Sdes 241124208Sdes /* Mark all multiples of 4*s */ 242124208Sdes for (u /= 4; u < largebits; u += s) 243124208Sdes BIT_SET(LargeSieve, u); 244124208Sdes } 245124208Sdes} 246124208Sdes 247124208Sdes/* 248137015Sdes * list candidates for Sophie-Germain primes (where q = (p-1)/2) 249124208Sdes * to standard output. 250124208Sdes * The list is checked against small known primes (less than 2**30). 251124208Sdes */ 252124208Sdesint 253149749Sdesgen_candidates(FILE *out, u_int32_t memory, u_int32_t power, BIGNUM *start) 254124208Sdes{ 255124208Sdes BIGNUM *q; 256124208Sdes u_int32_t j, r, s, t; 257124208Sdes u_int32_t smallwords = TINY_NUMBER >> 6; 258124208Sdes u_int32_t tinywords = TINY_NUMBER >> 6; 259124208Sdes time_t time_start, time_stop; 260149749Sdes u_int32_t i; 261149749Sdes int ret = 0; 262124208Sdes 263124208Sdes largememory = memory; 264124208Sdes 265137015Sdes if (memory != 0 && 266149749Sdes (memory < LARGE_MINIMUM || memory > LARGE_MAXIMUM)) { 267137015Sdes error("Invalid memory amount (min %ld, max %ld)", 268137015Sdes LARGE_MINIMUM, LARGE_MAXIMUM); 269137015Sdes return (-1); 270137015Sdes } 271137015Sdes 272124208Sdes /* 273126274Sdes * Set power to the length in bits of the prime to be generated. 274126274Sdes * This is changed to 1 less than the desired safe prime moduli p. 275126274Sdes */ 276124208Sdes if (power > TEST_MAXIMUM) { 277124208Sdes error("Too many bits: %u > %lu", power, TEST_MAXIMUM); 278124208Sdes return (-1); 279124208Sdes } else if (power < TEST_MINIMUM) { 280124208Sdes error("Too few bits: %u < %u", power, TEST_MINIMUM); 281124208Sdes return (-1); 282124208Sdes } 283124208Sdes power--; /* decrement before squaring */ 284124208Sdes 285124208Sdes /* 286126274Sdes * The density of ordinary primes is on the order of 1/bits, so the 287126274Sdes * density of safe primes should be about (1/bits)**2. Set test range 288126274Sdes * to something well above bits**2 to be reasonably sure (but not 289126274Sdes * guaranteed) of catching at least one safe prime. 290124208Sdes */ 291124208Sdes largewords = ((power * power) >> (SHIFT_WORD - TEST_POWER)); 292124208Sdes 293124208Sdes /* 294126274Sdes * Need idea of how much memory is available. We don't have to use all 295126274Sdes * of it. 296124208Sdes */ 297124208Sdes if (largememory > LARGE_MAXIMUM) { 298124208Sdes logit("Limited memory: %u MB; limit %lu MB", 299124208Sdes largememory, LARGE_MAXIMUM); 300124208Sdes largememory = LARGE_MAXIMUM; 301124208Sdes } 302124208Sdes 303124208Sdes if (largewords <= (largememory << SHIFT_MEGAWORD)) { 304124208Sdes logit("Increased memory: %u MB; need %u bytes", 305124208Sdes largememory, (largewords << SHIFT_BYTE)); 306124208Sdes largewords = (largememory << SHIFT_MEGAWORD); 307124208Sdes } else if (largememory > 0) { 308124208Sdes logit("Decreased memory: %u MB; want %u bytes", 309124208Sdes largememory, (largewords << SHIFT_BYTE)); 310124208Sdes largewords = (largememory << SHIFT_MEGAWORD); 311124208Sdes } 312124208Sdes 313162852Sdes TinySieve = xcalloc(tinywords, sizeof(u_int32_t)); 314124208Sdes tinybits = tinywords << SHIFT_WORD; 315124208Sdes 316162852Sdes SmallSieve = xcalloc(smallwords, sizeof(u_int32_t)); 317124208Sdes smallbits = smallwords << SHIFT_WORD; 318124208Sdes 319124208Sdes /* 320124208Sdes * dynamically determine available memory 321124208Sdes */ 322124208Sdes while ((LargeSieve = calloc(largewords, sizeof(u_int32_t))) == NULL) 323124208Sdes largewords -= (1L << (SHIFT_MEGAWORD - 2)); /* 1/4 MB chunks */ 324124208Sdes 325124208Sdes largebits = largewords << SHIFT_WORD; 326124208Sdes largenumbers = largebits * 2; /* even numbers excluded */ 327124208Sdes 328124208Sdes /* validation check: count the number of primes tried */ 329124208Sdes largetries = 0; 330164146Sdes if ((q = BN_new()) == NULL) 331164146Sdes fatal("BN_new failed"); 332124208Sdes 333124208Sdes /* 334126274Sdes * Generate random starting point for subprime search, or use 335126274Sdes * specified parameter. 336124208Sdes */ 337164146Sdes if ((largebase = BN_new()) == NULL) 338164146Sdes fatal("BN_new failed"); 339164146Sdes if (start == NULL) { 340164146Sdes if (BN_rand(largebase, power, 1, 1) == 0) 341164146Sdes fatal("BN_rand failed"); 342164146Sdes } else { 343164146Sdes if (BN_copy(largebase, start) == NULL) 344164146Sdes fatal("BN_copy: failed"); 345164146Sdes } 346124208Sdes 347124208Sdes /* ensure odd */ 348164146Sdes if (BN_set_bit(largebase, 0) == 0) 349164146Sdes fatal("BN_set_bit: failed"); 350124208Sdes 351124208Sdes time(&time_start); 352124208Sdes 353126274Sdes logit("%.24s Sieve next %u plus %u-bit", ctime(&time_start), 354124208Sdes largenumbers, power); 355124208Sdes debug2("start point: 0x%s", BN_bn2hex(largebase)); 356124208Sdes 357124208Sdes /* 358126274Sdes * TinySieve 359126274Sdes */ 360124208Sdes for (i = 0; i < tinybits; i++) { 361124208Sdes if (BIT_TEST(TinySieve, i)) 362124208Sdes continue; /* 2*i+3 is composite */ 363124208Sdes 364124208Sdes /* The next tiny prime */ 365124208Sdes t = 2 * i + 3; 366124208Sdes 367124208Sdes /* Mark all multiples of t */ 368124208Sdes for (j = i + t; j < tinybits; j += t) 369124208Sdes BIT_SET(TinySieve, j); 370124208Sdes 371124208Sdes sieve_large(t); 372124208Sdes } 373124208Sdes 374124208Sdes /* 375126274Sdes * Start the small block search at the next possible prime. To avoid 376126274Sdes * fencepost errors, the last pass is skipped. 377126274Sdes */ 378124208Sdes for (smallbase = TINY_NUMBER + 3; 379149749Sdes smallbase < (SMALL_MAXIMUM - TINY_NUMBER); 380149749Sdes smallbase += TINY_NUMBER) { 381124208Sdes for (i = 0; i < tinybits; i++) { 382124208Sdes if (BIT_TEST(TinySieve, i)) 383124208Sdes continue; /* 2*i+3 is composite */ 384124208Sdes 385124208Sdes /* The next tiny prime */ 386124208Sdes t = 2 * i + 3; 387124208Sdes r = smallbase % t; 388124208Sdes 389124208Sdes if (r == 0) { 390124208Sdes s = 0; /* t divides into smallbase exactly */ 391124208Sdes } else { 392124208Sdes /* smallbase+s is first entry divisible by t */ 393124208Sdes s = t - r; 394124208Sdes } 395124208Sdes 396124208Sdes /* 397124208Sdes * The sieve omits even numbers, so ensure that 398124208Sdes * smallbase+s is odd. Then, step through the sieve 399124208Sdes * in increments of 2*t 400124208Sdes */ 401124208Sdes if (s & 1) 402124208Sdes s += t; /* Make smallbase+s odd, and s even */ 403124208Sdes 404124208Sdes /* Mark all multiples of 2*t */ 405124208Sdes for (s /= 2; s < smallbits; s += t) 406124208Sdes BIT_SET(SmallSieve, s); 407124208Sdes } 408124208Sdes 409124208Sdes /* 410126274Sdes * SmallSieve 411126274Sdes */ 412124208Sdes for (i = 0; i < smallbits; i++) { 413124208Sdes if (BIT_TEST(SmallSieve, i)) 414124208Sdes continue; /* 2*i+smallbase is composite */ 415124208Sdes 416124208Sdes /* The next small prime */ 417124208Sdes sieve_large((2 * i) + smallbase); 418124208Sdes } 419124208Sdes 420124208Sdes memset(SmallSieve, 0, smallwords << SHIFT_BYTE); 421124208Sdes } 422124208Sdes 423124208Sdes time(&time_stop); 424124208Sdes 425124208Sdes logit("%.24s Sieved with %u small primes in %ld seconds", 426124208Sdes ctime(&time_stop), largetries, (long) (time_stop - time_start)); 427124208Sdes 428124208Sdes for (j = r = 0; j < largebits; j++) { 429124208Sdes if (BIT_TEST(LargeSieve, j)) 430124208Sdes continue; /* Definitely composite, skip */ 431124208Sdes 432124208Sdes debug2("test q = largebase+%u", 2 * j); 433164146Sdes if (BN_set_word(q, 2 * j) == 0) 434164146Sdes fatal("BN_set_word failed"); 435164146Sdes if (BN_add(q, q, largebase) == 0) 436164146Sdes fatal("BN_add failed"); 437137015Sdes if (qfileout(out, QTYPE_SOPHIE_GERMAIN, QTEST_SIEVE, 438124208Sdes largetries, (power - 1) /* MSB */, (0), q) == -1) { 439124208Sdes ret = -1; 440124208Sdes break; 441124208Sdes } 442124208Sdes 443124208Sdes r++; /* count q */ 444124208Sdes } 445124208Sdes 446124208Sdes time(&time_stop); 447124208Sdes 448124208Sdes xfree(LargeSieve); 449124208Sdes xfree(SmallSieve); 450124208Sdes xfree(TinySieve); 451124208Sdes 452124208Sdes logit("%.24s Found %u candidates", ctime(&time_stop), r); 453124208Sdes 454124208Sdes return (ret); 455124208Sdes} 456124208Sdes 457124208Sdes/* 458124208Sdes * perform a Miller-Rabin primality test 459124208Sdes * on the list of candidates 460124208Sdes * (checking both q and p) 461124208Sdes * The result is a list of so-call "safe" primes 462124208Sdes */ 463124208Sdesint 464137015Sdesprime_test(FILE *in, FILE *out, u_int32_t trials, u_int32_t generator_wanted) 465124208Sdes{ 466124208Sdes BIGNUM *q, *p, *a; 467124208Sdes BN_CTX *ctx; 468124208Sdes char *cp, *lp; 469124208Sdes u_int32_t count_in = 0, count_out = 0, count_possible = 0; 470124208Sdes u_int32_t generator_known, in_tests, in_tries, in_type, in_size; 471124208Sdes time_t time_start, time_stop; 472124208Sdes int res; 473124208Sdes 474137015Sdes if (trials < TRIAL_MINIMUM) { 475137015Sdes error("Minimum primality trials is %d", TRIAL_MINIMUM); 476137015Sdes return (-1); 477137015Sdes } 478137015Sdes 479124208Sdes time(&time_start); 480124208Sdes 481164146Sdes if ((p = BN_new()) == NULL) 482164146Sdes fatal("BN_new failed"); 483164146Sdes if ((q = BN_new()) == NULL) 484164146Sdes fatal("BN_new failed"); 485164146Sdes if ((ctx = BN_CTX_new()) == NULL) 486164146Sdes fatal("BN_CTX_new failed"); 487124208Sdes 488124208Sdes debug2("%.24s Final %u Miller-Rabin trials (%x generator)", 489124208Sdes ctime(&time_start), trials, generator_wanted); 490124208Sdes 491124208Sdes res = 0; 492124208Sdes lp = xmalloc(QLINESIZE + 1); 493124208Sdes while (fgets(lp, QLINESIZE, in) != NULL) { 494124208Sdes int ll = strlen(lp); 495124208Sdes 496124208Sdes count_in++; 497124208Sdes if (ll < 14 || *lp == '!' || *lp == '#') { 498124208Sdes debug2("%10u: comment or short line", count_in); 499124208Sdes continue; 500124208Sdes } 501124208Sdes 502124208Sdes /* XXX - fragile parser */ 503124208Sdes /* time */ 504124208Sdes cp = &lp[14]; /* (skip) */ 505124208Sdes 506124208Sdes /* type */ 507124208Sdes in_type = strtoul(cp, &cp, 10); 508124208Sdes 509124208Sdes /* tests */ 510124208Sdes in_tests = strtoul(cp, &cp, 10); 511124208Sdes 512124208Sdes if (in_tests & QTEST_COMPOSITE) { 513124208Sdes debug2("%10u: known composite", count_in); 514124208Sdes continue; 515124208Sdes } 516126274Sdes 517124208Sdes /* tries */ 518124208Sdes in_tries = strtoul(cp, &cp, 10); 519124208Sdes 520124208Sdes /* size (most significant bit) */ 521124208Sdes in_size = strtoul(cp, &cp, 10); 522124208Sdes 523124208Sdes /* generator (hex) */ 524124208Sdes generator_known = strtoul(cp, &cp, 16); 525124208Sdes 526124208Sdes /* Skip white space */ 527124208Sdes cp += strspn(cp, " "); 528124208Sdes 529124208Sdes /* modulus (hex) */ 530124208Sdes switch (in_type) { 531137015Sdes case QTYPE_SOPHIE_GERMAIN: 532137015Sdes debug2("%10u: (%u) Sophie-Germain", count_in, in_type); 533124208Sdes a = q; 534164146Sdes if (BN_hex2bn(&a, cp) == 0) 535164146Sdes fatal("BN_hex2bn failed"); 536124208Sdes /* p = 2*q + 1 */ 537164146Sdes if (BN_lshift(p, q, 1) == 0) 538164146Sdes fatal("BN_lshift failed"); 539164146Sdes if (BN_add_word(p, 1) == 0) 540164146Sdes fatal("BN_add_word failed"); 541124208Sdes in_size += 1; 542124208Sdes generator_known = 0; 543124208Sdes break; 544126274Sdes case QTYPE_UNSTRUCTURED: 545126274Sdes case QTYPE_SAFE: 546146998Sdes case QTYPE_SCHNORR: 547126274Sdes case QTYPE_STRONG: 548126274Sdes case QTYPE_UNKNOWN: 549124208Sdes debug2("%10u: (%u)", count_in, in_type); 550124208Sdes a = p; 551164146Sdes if (BN_hex2bn(&a, cp) == 0) 552164146Sdes fatal("BN_hex2bn failed"); 553124208Sdes /* q = (p-1) / 2 */ 554164146Sdes if (BN_rshift(q, p, 1) == 0) 555164146Sdes fatal("BN_rshift failed"); 556124208Sdes break; 557126274Sdes default: 558126274Sdes debug2("Unknown prime type"); 559126274Sdes break; 560124208Sdes } 561124208Sdes 562124208Sdes /* 563124208Sdes * due to earlier inconsistencies in interpretation, check 564124208Sdes * the proposed bit size. 565124208Sdes */ 566149749Sdes if ((u_int32_t)BN_num_bits(p) != (in_size + 1)) { 567124208Sdes debug2("%10u: bit size %u mismatch", count_in, in_size); 568124208Sdes continue; 569124208Sdes } 570124208Sdes if (in_size < QSIZE_MINIMUM) { 571124208Sdes debug2("%10u: bit size %u too short", count_in, in_size); 572124208Sdes continue; 573124208Sdes } 574124208Sdes 575124208Sdes if (in_tests & QTEST_MILLER_RABIN) 576124208Sdes in_tries += trials; 577124208Sdes else 578124208Sdes in_tries = trials; 579126274Sdes 580124208Sdes /* 581124208Sdes * guess unknown generator 582124208Sdes */ 583124208Sdes if (generator_known == 0) { 584124208Sdes if (BN_mod_word(p, 24) == 11) 585124208Sdes generator_known = 2; 586124208Sdes else if (BN_mod_word(p, 12) == 5) 587124208Sdes generator_known = 3; 588124208Sdes else { 589124208Sdes u_int32_t r = BN_mod_word(p, 10); 590124208Sdes 591126274Sdes if (r == 3 || r == 7) 592124208Sdes generator_known = 5; 593124208Sdes } 594124208Sdes } 595124208Sdes /* 596124208Sdes * skip tests when desired generator doesn't match 597124208Sdes */ 598124208Sdes if (generator_wanted > 0 && 599124208Sdes generator_wanted != generator_known) { 600124208Sdes debug2("%10u: generator %d != %d", 601124208Sdes count_in, generator_known, generator_wanted); 602124208Sdes continue; 603124208Sdes } 604124208Sdes 605126274Sdes /* 606126274Sdes * Primes with no known generator are useless for DH, so 607126274Sdes * skip those. 608126274Sdes */ 609126274Sdes if (generator_known == 0) { 610126274Sdes debug2("%10u: no known generator", count_in); 611126274Sdes continue; 612126274Sdes } 613126274Sdes 614124208Sdes count_possible++; 615124208Sdes 616124208Sdes /* 617126274Sdes * The (1/4)^N performance bound on Miller-Rabin is 618126274Sdes * extremely pessimistic, so don't spend a lot of time 619126274Sdes * really verifying that q is prime until after we know 620126274Sdes * that p is also prime. A single pass will weed out the 621124208Sdes * vast majority of composite q's. 622124208Sdes */ 623124208Sdes if (BN_is_prime(q, 1, NULL, ctx, NULL) <= 0) { 624126274Sdes debug("%10u: q failed first possible prime test", 625124208Sdes count_in); 626124208Sdes continue; 627124208Sdes } 628126274Sdes 629124208Sdes /* 630126274Sdes * q is possibly prime, so go ahead and really make sure 631126274Sdes * that p is prime. If it is, then we can go back and do 632126274Sdes * the same for q. If p is composite, chances are that 633124208Sdes * will show up on the first Rabin-Miller iteration so it 634124208Sdes * doesn't hurt to specify a high iteration count. 635124208Sdes */ 636124208Sdes if (!BN_is_prime(p, trials, NULL, ctx, NULL)) { 637126274Sdes debug("%10u: p is not prime", count_in); 638124208Sdes continue; 639124208Sdes } 640124208Sdes debug("%10u: p is almost certainly prime", count_in); 641124208Sdes 642124208Sdes /* recheck q more rigorously */ 643124208Sdes if (!BN_is_prime(q, trials - 1, NULL, ctx, NULL)) { 644124208Sdes debug("%10u: q is not prime", count_in); 645124208Sdes continue; 646124208Sdes } 647124208Sdes debug("%10u: q is almost certainly prime", count_in); 648124208Sdes 649126274Sdes if (qfileout(out, QTYPE_SAFE, (in_tests | QTEST_MILLER_RABIN), 650124208Sdes in_tries, in_size, generator_known, p)) { 651124208Sdes res = -1; 652124208Sdes break; 653124208Sdes } 654124208Sdes 655124208Sdes count_out++; 656124208Sdes } 657124208Sdes 658124208Sdes time(&time_stop); 659124208Sdes xfree(lp); 660124208Sdes BN_free(p); 661124208Sdes BN_free(q); 662124208Sdes BN_CTX_free(ctx); 663124208Sdes 664124208Sdes logit("%.24s Found %u safe primes of %u candidates in %ld seconds", 665126274Sdes ctime(&time_stop), count_out, count_possible, 666124208Sdes (long) (time_stop - time_start)); 667124208Sdes 668124208Sdes return (res); 669124208Sdes} 670