usr.bin/moduli/qsafe/qsafe.c

   1 /* $NetBSD: qsafe.c,v 1.1 2006/01/24 18:59:23 elad Exp $ */
   2
   3 /*-
   4  * Copyright 1994 Phil Karn <karn@qualcomm.com>
   5  * Copyright 1996-1998, 2003 William Allen206 Simpson <wsimpson@greendragon.com>
   6  * Copyright 2000 Niels Provos <provos@citi.umich.edu>
   7  * All rights reserved.
   8  *
   9  * Redistribution and use in source and binary forms, with or without
  10  * modification, are permitted provided that the following conditions
  11  * are met:
  12  * 1. Redistributions of source code must retain the above copyright
  13  *    notice, this list of conditions and the following disclaimer.
  14  * 2. Redistributions in binary form must reproduce the above copyright
  15  *    notice, this list of conditions and the following disclaimer in the
  16  *    documentation and/or other materials provided with the distribution.
  17  *
  18  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
  19  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  20  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
  21  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
  22  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  23  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  24  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  25  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  26  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
  27  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  28  */
  29
  30 /*
  31  * Test probable "safe" primes,
  32  *
  33  *  suitable for use as Diffie-Hellman moduli;
  34  *  that is, where q = (p-1)/2 is also prime.
  35  *
  36  * This is the second of two steps.
  37  * This step is processor intensive.
  38  *
  39  * 1996 May     William Allen Simpson
  40  *              extracted from earlier code by Phil Karn, April 1994.
  41  *              read large prime candidates list (q),
  42  *              and check prime probability of (p).
  43  * 1998 May     William Allen Simpson
  44  *              parameterized.
  45  *              optionally limit to a single generator.
  46  * 2000 Dec     Niels Provos
  47  *              convert from GMP to openssl BN.
  48  * 2003 Jun     William Allen Simpson
  49  *              change outfile definition slightly to match openssh mistake.
  50  *              move common file i/o to own file for better documentation.
  51  *              redo debugprint again.
  52  */
  53
  54 #include <stdlib.h>
  55 #include <stdio.h>
  56 #include <string.h>
  57 #include <time.h>
  58 #include <openssl/bn.h>
  59 #include "qfile.h"
  60
  61 /* define DEBUGPRINT     1 */
  62 #define TRIAL_MINIMUM           (4)
  63
  64 static void     usage(void);
  65
  66 /*
  67  * perform a Miller-Rabin primality test
  68  * on the list of candidates
  69  * (checking both q and p)
  70  * from standard input.
  71  * The result is a list of so-call "safe" primes
  72  * to standard output,
  73  */
  74 int
  75 main(int argc, char *argv[])
  76 {
  77         BIGNUM         *q, *p, *a;
  78         BN_CTX         *ctx;
  79         char           *cp;
  80         char           *lp;
  81         uint32_t        count_in = 0;
  82         uint32_t        count_out = 0;
  83         uint32_t        count_possible = 0;
  84         uint32_t        generator_known;
  85         uint32_t        generator_wanted = 0;
  86         uint32_t        in_tests;
  87         uint32_t        in_tries;
  88         uint32_t        in_type;
  89         uint32_t        in_size;
  90         int             trials;
  91         time_t          time_start;
  92         time_t          time_stop;
  93
  94         setprogname(argv[0]);
  95
  96         if (argc < 2) {
  97                 usage();
  98         }
  99
 100         if ((trials = strtoul(argv[1], NULL, 10)) < TRIAL_MINIMUM) {
 101                 trials = TRIAL_MINIMUM;
 102         }
 103
 104         if (argc > 2) {
 105                 generator_wanted = strtoul(argv[2], NULL, 16);
 106         }
 107
 108         time(&time_start);
 109
 110         p = BN_new();
 111         q = BN_new();
 112         ctx = BN_CTX_new();
 113
 114         (void)fprintf(stderr,
 115                 "%.24s Final %d Miller-Rabin trials (%x generator)\n",
 116                 ctime(&time_start), trials, generator_wanted);
 117
 118         lp = (char *) malloc((unsigned long) QLINESIZE + 1);
 119
 120         while (fgets(lp, QLINESIZE, stdin) != NULL) {
 121                 size_t          ll = strlen(lp);
 122
 123                 count_in++;
 124
 125                 if (ll < 14 || *lp == '!' || *lp == '#') {
 126 #ifdef  DEBUGPRINT
 127                         (void)fprintf(stderr, "%10lu: comment or short"
 128                                       " line\n", count_in);
 129 #endif
 130                         continue;
 131                 }
 132
 133                 /* time */
 134                 cp = &lp[14];   /* (skip) */
 135
 136                 /* type */
 137                 in_type = strtoul(cp, &cp, 10);
 138
 139                 /* tests */
 140                 in_tests = strtoul(cp, &cp, 10);
 141                 if (in_tests & QTEST_COMPOSITE) {
 142 #ifdef  DEBUGPRINT
 143                         (void)fprintf(stderr, "%10lu: known composite\n",
 144                                 count_in);
 145 #endif
 146                         continue;
 147                 }
 148
 149                 /* tries */
 150                 in_tries = (uint32_t) strtoul(cp, &cp, 10);
 151
 152                 /* size (most significant bit) */
 153                 in_size = (uint32_t) strtoul(cp, &cp, 10);
 154
 155                 /* generator (hex) */
 156                 generator_known = (uint32_t) strtoul(cp, &cp, 16);
 157
 158                 /* Skip white space */
 159                 cp += strspn(cp, " ");
 160
 161                 /* modulus (hex) */
 162                 switch (in_type) {
 163                 case QTYPE_SOPHIE_GERMAINE:
 164 #ifdef  DEBUGPRINT
 165                         (void)fprintf(stderr, "%10lu: (%lu) "
 166                                       "Sophie-Germaine\n", count_in,
 167                                       in_type);
 168 #endif
 169
 170                         a = q;
 171                         BN_hex2bn(&a, cp);
 172                         /* p = 2*q + 1 */
 173                         BN_lshift(p, q, 1);
 174                         BN_add_word(p, 1UL);
 175                         in_size += 1;
 176                         generator_known = 0;
 177
 178                         break;
 179
 180                 default:
 181 #ifdef  DEBUGPRINT
 182                         (void)fprintf(stderr, "%10lu: (%lu)\n",
 183                                       count_in, in_type);
 184 #endif
 185                         a = p;
 186                         BN_hex2bn(&a, cp);
 187                         /* q = (p-1) / 2 */
 188                         BN_rshift(q, p, 1);
 189
 190                         break;
 191                 }
 192
 193                 /*
 194                  * due to earlier inconsistencies in interpretation, check the
 195                  * proposed bit size.
 196                  */
 197                 if ((uint32_t)BN_num_bits(p) != (in_size + 1)) {
 198 #ifdef  DEBUGPRINT
 199                         (void)fprintf(stderr, "%10lu: bit size %ul "
 200                                       "mismatch\n", count_in, in_size);
 201 #endif
 202                         continue;
 203                 }
 204
 205                 if (in_size < QSIZE_MINIMUM) {
 206 #ifdef  DEBUGPRINT
 207                         (void)fprintf(stderr, "%10lu: bit size %ul "
 208                                       "too short\n", count_in, in_size);
 209 #endif
 210                         continue;
 211                 }
 212
 213                 if (in_tests & QTEST_MILLER_RABIN)
 214                         in_tries += trials;
 215                 else
 216                         in_tries = trials;
 217
 218                 /*
 219                  * guess unknown generator
 220                  */
 221                 if (generator_known == 0) {
 222                         if (BN_mod_word(p, 24UL) == 11)
 223                                 generator_known = 2;
 224                         else if (BN_mod_word(p, 12UL) == 5)
 225                                 generator_known = 3;
 226                         else {
 227                                 BN_ULONG        r = BN_mod_word(p, 10UL);
 228
 229                                 if (r == 3 || r == 7) {
 230                                         generator_known = 5;
 231                                 }
 232                         }
 233                 }
 234
 235                 /*
 236                  * skip tests when desired generator doesn't match
 237                  */
 238                 if (generator_wanted > 0 &&
 239                     generator_wanted != generator_known) {
 240 #ifdef  DEBUGPRINT
 241                         (void)fprintf(stderr,
 242                                       "%10lu: generator %ld != %ld\n",
 243                                 count_in, generator_known, generator_wanted);
 244 #endif
 245                         continue;
 246                 }
 247
 248                 count_possible++;
 249
 250                 /*
 251                  * The (1/4)^N performance bound on Miller-Rabin is extremely
 252                  * pessimistic, so don't spend a lot of time really verifying
 253                  * that q is prime until after we know that p is also prime. A
 254                  * single pass will weed out the vast majority of composite
 255                  * q's.
 256                  */
 257                 if (BN_is_prime(q, 1, NULL, ctx, NULL) <= 0) {
 258 #ifdef  DEBUGPRINT
 259                         (void)fprintf(stderr, "%10lu: q failed first "
 260                                       "possible prime test\n", count_in);
 261 #endif
 262                         continue;
 263                 }
 264
 265                 /*
 266                  * q is possibly prime, so go ahead and really make sure that
 267                  * p is prime. If it is, then we can go back and do the same
 268                  * for q. If p is composite, chances are that will show up on
 269                  * the first Rabin-Miller iteration so it doesn't hurt to
 270                  * specify a high iteration count.
 271                  */
 272                 if (!BN_is_prime(p, trials, NULL, ctx, NULL)) {
 273 #ifdef  DEBUGPRINT
 274                         (void)fprintf(stderr, "%10lu: p is not prime\n",
 275                                       count_in);
 276 #endif
 277                         continue;
 278                 }
 279
 280 #ifdef  DEBUGPRINT
 281                 (void)fprintf(stderr, "%10lu: p is almost certainly "
 282                               "prime\n", count_in);
 283 #endif
 284
 285                 /* recheck q more rigorously */
 286                 if (!BN_is_prime(q, trials - 1, NULL, ctx, NULL)) {
 287 #ifdef  DEBUGPRINT
 288                         (void)fprintf(stderr, "%10lu: q is not prime\n",
 289                                       count_in);
 290 #endif
 291                         continue;
 292                 }
 293 #ifdef  DEBUGPRINT
 294                 fprintf(stderr, "%10lu: q is almost certainly prime\n",
 295                         count_in);
 296 #endif
 297                 if (0 > qfileout(stdout,
 298                                  QTYPE_SAFE,
 299                                  (in_tests | QTEST_MILLER_RABIN),
 300                                  in_tries,
 301                                  in_size,
 302                                  generator_known,
 303                                  p)) {
 304                         break;
 305                 }
 306                 count_out++;
 307 #ifdef  DEBUGPRINT
 308                 fflush(stderr);
 309                 fflush(stdout);
 310 #endif
 311         }
 312
 313         time(&time_stop);
 314         free(lp);
 315         BN_free(p);
 316         BN_free(q);
 317         BN_CTX_free(ctx);
 318         fflush(stdout);         /* fclose(stdout); */
 319         /* fclose(stdin); */
 320         (void)fprintf(stderr,
 321            "%.24s Found %u safe primes of %u candidates in %lu seconds\n",
 322                 ctime(&time_stop), count_out, count_possible,
 323                 (long) (time_stop - time_start));
 324
 325         return (0);
 326 }
 327
 328 static void
 329 usage(void)
 330 {
 331         (void)fprintf(stderr, "Usage: %s <trials> [generator]\n",
 332                       getprogname());
 333         exit(1);
 334 }