security/nss/lib/freebl/mpi/utils/primegen.c

   1 /*
   2  *  primegen.c
   3  *
   4  * Generates random integers which are prime with a high degree of
   5  * probability using the Miller-Rabin probabilistic primality testing
   6  * algorithm.
   7  *
   8  * Usage:
   9  *    primegen <bits> [<num>]
  10  *
  11  *    <bits>   - number of significant bits each prime should have
  12  *    <num>    - number of primes to generate
  13  *
  14  * ***** BEGIN LICENSE BLOCK *****
  15  * Version: MPL 1.1/GPL 2.0/LGPL 2.1
  16  *
  17  * The contents of this file are subject to the Mozilla Public License Version
  18  * 1.1 (the "License"); you may not use this file except in compliance with
  19  * the License. You may obtain a copy of the License at
  20  * http://www.mozilla.org/MPL/
  21  *
  22  * Software distributed under the License is distributed on an "AS IS" basis,
  23  * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
  24  * for the specific language governing rights and limitations under the
  25  * License.
  26  *
  27  * The Original Code is the MPI Arbitrary Precision Integer Arithmetic library.
  28  *
  29  * The Initial Developer of the Original Code is
  30  * Michael J. Fromberger.
  31  * Portions created by the Initial Developer are Copyright (C) 1998
  32  * the Initial Developer. All Rights Reserved.
  33  *
  34  * Contributor(s):
  35  *
  36  * Alternatively, the contents of this file may be used under the terms of
  37  * either the GNU General Public License Version 2 or later (the "GPL"), or
  38  * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
  39  * in which case the provisions of the GPL or the LGPL are applicable instead
  40  * of those above. If you wish to allow use of your version of this file only
  41  * under the terms of either the GPL or the LGPL, and not to allow others to
  42  * use your version of this file under the terms of the MPL, indicate your
  43  * decision by deleting the provisions above and replace them with the notice
  44  * and other provisions required by the GPL or the LGPL. If you do not delete
  45  * the provisions above, a recipient may use your version of this file under
  46  * the terms of any one of the MPL, the GPL or the LGPL.
  47  *
  48  * ***** END LICENSE BLOCK ***** */
  49 /* $Id: primegen.c,v 1.7 2004/04/27 23:04:37 gerv%gerv.net Exp $ */
  50
  51 #include <stdio.h>
  52 #include <stdlib.h>
  53 #include <string.h>
  54 #include <limits.h>
  55 #include <time.h>
  56
  57 #include "mpi.h"
  58 #include "mplogic.h"
  59 #include "mpprime.h"
  60
  61 #undef MACOS            /* define if running on a Macintosh */
  62
  63 #ifdef MACOS
  64 #include <console.h>
  65 #endif
  66
  67 #define NUM_TESTS 5  /* Number of Rabin-Miller iterations to test with */
  68
  69 #ifdef DEBUG
  70 #define FPUTC(x,y) fputc(x,y)
  71 #else
  72 #define FPUTC(x,y)
  73 #endif
  74
  75 int main(int argc, char *argv[])
  76 {
  77   unsigned char *raw;
  78   char          *out;
  79   unsigned long nTries;
  80   int           rawlen, bits, outlen, ngen, ix, jx;
  81   int           g_strong = 0;
  82   mp_int        testval;
  83   mp_err        res;
  84   clock_t       start, end;
  85
  86 #ifdef MACOS
  87   argc = ccommand(&argv);
  88 #endif
  89
  90   /* We'll just use the C library's rand() for now, although this
  91      won't be good enough for cryptographic purposes */
  92   if((out = getenv("SEED")) == NULL) {
  93     srand((unsigned int)time(NULL));
  94   } else {
  95     srand((unsigned int)atoi(out));
  96   }
  97
  98   if(argc < 2) {
  99     fprintf(stderr, "Usage: %s <bits> [<count> [strong]]\n", argv[0]);
 100     return 1;
 101   }
 102
 103   if((bits = abs(atoi(argv[1]))) < CHAR_BIT) {
 104     fprintf(stderr, "%s: please request at least %d bits.\n",
 105             argv[0], CHAR_BIT);
 106     return 1;
 107   }
 108
 109   /* If optional third argument is given, use that as the number of
 110      primes to generate; otherwise generate one prime only.
 111    */
 112   if(argc < 3) {
 113     ngen = 1;
 114   } else {
 115     ngen = abs(atoi(argv[2]));
 116   }
 117
 118   /* If fourth argument is given, and is the word "strong", we'll
 119      generate strong (Sophie Germain) primes.
 120    */
 121   if(argc > 3 && strcmp(argv[3], "strong") == 0)
 122     g_strong = 1;
 123
 124   /* testval - candidate being tested; nTries - number tried so far */
 125   if ((res = mp_init(&testval)) != MP_OKAY) {
 126     fprintf(stderr, "%s: error: %s\n", argv[0], mp_strerror(res));
 127     return 1;
 128   }
 129
 130   if(g_strong) {
 131     printf("Requested %d strong prime value(s) of %d bits.\n",
 132            ngen, bits);
 133   } else {
 134     printf("Requested %d prime value(s) of %d bits.\n", ngen, bits);
 135   }
 136
 137   rawlen = (bits / CHAR_BIT) + ((bits % CHAR_BIT) ? 1 : 0) + 1;
 138
 139   if((raw = calloc(rawlen, sizeof(unsigned char))) == NULL) {
 140     fprintf(stderr, "%s: out of memory, sorry.\n", argv[0]);
 141     return 1;
 142   }
 143
 144   /* This loop is one for each prime we need to generate */
 145   for(jx = 0; jx < ngen; jx++) {
 146
 147     raw[0] = 0;  /* sign is positive */
 148
 149     /*  Pack the initializer with random bytes  */
 150     for(ix = 1; ix < rawlen; ix++)
 151       raw[ix] = (rand() * rand()) & UCHAR_MAX;
 152
 153     raw[1] |= 0x80;             /* set high-order bit of test value     */
 154     raw[rawlen - 1] |= 1;       /* set low-order bit of test value      */
 155
 156     /* Make an mp_int out of the initializer */
 157     mp_read_raw(&testval, (char *)raw, rawlen);
 158
 159     /* Initialize candidate counter */
 160     nTries = 0;
 161
 162     start = clock(); /* time generation for this prime */
 163     do {
 164       res = mpp_make_prime(&testval, bits, g_strong, &nTries);
 165       if (res != MP_NO)
 166         break;
 167       /* This code works whether digits are 16 or 32 bits */
 168       res = mp_add_d(&testval, 32 * 1024, &testval);
 169       res = mp_add_d(&testval, 32 * 1024, &testval);
 170       FPUTC(',', stderr);
 171     } while (1);
 172     end = clock();
 173
 174     if (res != MP_YES) {
 175       break;
 176     }
 177     FPUTC('\n', stderr);
 178     puts("The following value is probably prime:");
 179     outlen = mp_radix_size(&testval, 10);
 180     out = calloc(outlen, sizeof(unsigned char));
 181     mp_toradix(&testval, (char *)out, 10);
 182     printf("10: %s\n", out);
 183     mp_toradix(&testval, (char *)out, 16);
 184     printf("16: %s\n\n", out);
 185     free(out);
 186
 187     printf("Number of candidates tried: %lu\n", nTries);
 188     printf("This computation took %ld clock ticks (%.2f seconds)\n",
 189            (end - start), ((double)(end - start) / CLOCKS_PER_SEC));
 190
 191     FPUTC('\n', stderr);
 192   } /* end of loop to generate all requested primes */
 193
 194   if(res != MP_OKAY)
 195     fprintf(stderr, "%s: error: %s\n", argv[0], mp_strerror(res));
 196
 197   free(raw);
 198   mp_clear(&testval);
 199
 200   return 0;
 201 }