The Tor Browser: security/nss/lib/freebl/mpi/utils/primegen.c@b8a032363ba2

Incorporate requested changes from Mozilla in review:
https://bugzilla.mozilla.org/show_bug.cgi?id=1123480#c6

     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  * This Source Code Form is subject to the terms of the Mozilla Public

    15  * License, v. 2.0. If a copy of the MPL was not distributed with this

    16  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */

    18 #include <stdio.h>

    19 #include <stdlib.h>

    20 #include <string.h>

    21 #include <limits.h>

    22 #include <time.h>

    24 #include "mpi.h"

    25 #include "mplogic.h"

    26 #include "mpprime.h"

    28 #define NUM_TESTS 5  /* Number of Rabin-Miller iterations to test with */

    30 #ifdef DEBUG

    31 #define FPUTC(x,y) fputc(x,y)

    32 #else

    33 #define FPUTC(x,y)

    34 #endif

    36 int main(int argc, char *argv[])

    37 {

    38   unsigned char *raw;

    39   char          *out;

    40   unsigned long nTries;

    41   int		rawlen, bits, outlen, ngen, ix, jx;

    42   int           g_strong = 0;

    43   mp_int	testval;

    44   mp_err	res;

    45   clock_t	start, end;

    47   /* We'll just use the C library's rand() for now, although this

    48      won't be good enough for cryptographic purposes */

    49   if((out = getenv("SEED")) == NULL) {

    50     srand((unsigned int)time(NULL));

    51   } else {

    52     srand((unsigned int)atoi(out));

    53   }

    55   if(argc < 2) {

    56     fprintf(stderr, "Usage: %s <bits> [<count> [strong]]\n", argv[0]);

    57     return 1;

    58   }

    60   if((bits = abs(atoi(argv[1]))) < CHAR_BIT) {

    61     fprintf(stderr, "%s: please request at least %d bits.\n",

    62 	    argv[0], CHAR_BIT);

    63     return 1;

    64   }

    66   /* If optional third argument is given, use that as the number of

    67      primes to generate; otherwise generate one prime only.

    68    */

    69   if(argc < 3) {

    70     ngen = 1;

    71   } else {

    72     ngen = abs(atoi(argv[2]));

    73   }

    75   /* If fourth argument is given, and is the word "strong", we'll

    76      generate strong (Sophie Germain) primes.

    77    */

    78   if(argc > 3 && strcmp(argv[3], "strong") == 0)

    79     g_strong = 1;

    81   /* testval - candidate being tested; nTries - number tried so far */

    82   if ((res = mp_init(&testval)) != MP_OKAY) {

    83     fprintf(stderr, "%s: error: %s\n", argv[0], mp_strerror(res));

    84     return 1;

    85   }

    87   if(g_strong) {

    88     printf("Requested %d strong prime value(s) of %d bits.\n",

    89 	   ngen, bits);

    90   } else {

    91     printf("Requested %d prime value(s) of %d bits.\n", ngen, bits);

    92   }

    94   rawlen = (bits / CHAR_BIT) + ((bits % CHAR_BIT) ? 1 : 0) + 1;

    96   if((raw = calloc(rawlen, sizeof(unsigned char))) == NULL) {

    97     fprintf(stderr, "%s: out of memory, sorry.\n", argv[0]);

    98     return 1;

    99   }

   101   /* This loop is one for each prime we need to generate */

   102   for(jx = 0; jx < ngen; jx++) {

   104     raw[0] = 0;  /* sign is positive */

   106     /*	Pack the initializer with random bytes	*/

   107     for(ix = 1; ix < rawlen; ix++)

   108       raw[ix] = (rand() * rand()) & UCHAR_MAX;

   110     raw[1] |= 0x80;             /* set high-order bit of test value     */

   111     raw[rawlen - 1] |= 1;       /* set low-order bit of test value      */

   113     /* Make an mp_int out of the initializer */

   114     mp_read_raw(&testval, (char *)raw, rawlen);

   116     /* Initialize candidate counter */

   117     nTries = 0;

   119     start = clock(); /* time generation for this prime */

   120     do {

   121       res = mpp_make_prime(&testval, bits, g_strong, &nTries);

   122       if (res != MP_NO)

   123 	break;

   124       /* This code works whether digits are 16 or 32 bits */

   125       res = mp_add_d(&testval, 32 * 1024, &testval);

   126       res = mp_add_d(&testval, 32 * 1024, &testval);

   127       FPUTC(',', stderr);

   128     } while (1);

   129     end = clock();

   131     if (res != MP_YES) {

   132       break;

   133     }

   134     FPUTC('\n', stderr);

   135     puts("The following value is probably prime:");

   136     outlen = mp_radix_size(&testval, 10);

   137     out = calloc(outlen, sizeof(unsigned char));

   138     mp_toradix(&testval, (char *)out, 10);

   139     printf("10: %s\n", out);

   140     mp_toradix(&testval, (char *)out, 16);

   141     printf("16: %s\n\n", out);

   142     free(out);

   144     printf("Number of candidates tried: %lu\n", nTries);

   145     printf("This computation took %ld clock ticks (%.2f seconds)\n",

   146 	   (end - start), ((double)(end - start) / CLOCKS_PER_SEC));

   148     FPUTC('\n', stderr);

   149   } /* end of loop to generate all requested primes */

   151   if(res != MP_OKAY)

   152     fprintf(stderr, "%s: error: %s\n", argv[0], mp_strerror(res));

   154   free(raw);

   155   mp_clear(&testval);

   157   return 0;

   158 }

The Tor Browser / file revision