1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/security/nss/lib/freebl/mpi/utils/primegen.c Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,158 @@
1.4 +/*
1.5 + * primegen.c
1.6 + *
1.7 + * Generates random integers which are prime with a high degree of
1.8 + * probability using the Miller-Rabin probabilistic primality testing
1.9 + * algorithm.
1.10 + *
1.11 + * Usage:
1.12 + * primegen <bits> [<num>]
1.13 + *
1.14 + * <bits> - number of significant bits each prime should have
1.15 + * <num> - number of primes to generate
1.16 + *
1.17 + * This Source Code Form is subject to the terms of the Mozilla Public
1.18 + * License, v. 2.0. If a copy of the MPL was not distributed with this
1.19 + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
1.20 +
1.21 +#include <stdio.h>
1.22 +#include <stdlib.h>
1.23 +#include <string.h>
1.24 +#include <limits.h>
1.25 +#include <time.h>
1.26 +
1.27 +#include "mpi.h"
1.28 +#include "mplogic.h"
1.29 +#include "mpprime.h"
1.30 +
1.31 +#define NUM_TESTS 5 /* Number of Rabin-Miller iterations to test with */
1.32 +
1.33 +#ifdef DEBUG
1.34 +#define FPUTC(x,y) fputc(x,y)
1.35 +#else
1.36 +#define FPUTC(x,y)
1.37 +#endif
1.38 +
1.39 +int main(int argc, char *argv[])
1.40 +{
1.41 + unsigned char *raw;
1.42 + char *out;
1.43 + unsigned long nTries;
1.44 + int rawlen, bits, outlen, ngen, ix, jx;
1.45 + int g_strong = 0;
1.46 + mp_int testval;
1.47 + mp_err res;
1.48 + clock_t start, end;
1.49 +
1.50 + /* We'll just use the C library's rand() for now, although this
1.51 + won't be good enough for cryptographic purposes */
1.52 + if((out = getenv("SEED")) == NULL) {
1.53 + srand((unsigned int)time(NULL));
1.54 + } else {
1.55 + srand((unsigned int)atoi(out));
1.56 + }
1.57 +
1.58 + if(argc < 2) {
1.59 + fprintf(stderr, "Usage: %s <bits> [<count> [strong]]\n", argv[0]);
1.60 + return 1;
1.61 + }
1.62 +
1.63 + if((bits = abs(atoi(argv[1]))) < CHAR_BIT) {
1.64 + fprintf(stderr, "%s: please request at least %d bits.\n",
1.65 + argv[0], CHAR_BIT);
1.66 + return 1;
1.67 + }
1.68 +
1.69 + /* If optional third argument is given, use that as the number of
1.70 + primes to generate; otherwise generate one prime only.
1.71 + */
1.72 + if(argc < 3) {
1.73 + ngen = 1;
1.74 + } else {
1.75 + ngen = abs(atoi(argv[2]));
1.76 + }
1.77 +
1.78 + /* If fourth argument is given, and is the word "strong", we'll
1.79 + generate strong (Sophie Germain) primes.
1.80 + */
1.81 + if(argc > 3 && strcmp(argv[3], "strong") == 0)
1.82 + g_strong = 1;
1.83 +
1.84 + /* testval - candidate being tested; nTries - number tried so far */
1.85 + if ((res = mp_init(&testval)) != MP_OKAY) {
1.86 + fprintf(stderr, "%s: error: %s\n", argv[0], mp_strerror(res));
1.87 + return 1;
1.88 + }
1.89 +
1.90 + if(g_strong) {
1.91 + printf("Requested %d strong prime value(s) of %d bits.\n",
1.92 + ngen, bits);
1.93 + } else {
1.94 + printf("Requested %d prime value(s) of %d bits.\n", ngen, bits);
1.95 + }
1.96 +
1.97 + rawlen = (bits / CHAR_BIT) + ((bits % CHAR_BIT) ? 1 : 0) + 1;
1.98 +
1.99 + if((raw = calloc(rawlen, sizeof(unsigned char))) == NULL) {
1.100 + fprintf(stderr, "%s: out of memory, sorry.\n", argv[0]);
1.101 + return 1;
1.102 + }
1.103 +
1.104 + /* This loop is one for each prime we need to generate */
1.105 + for(jx = 0; jx < ngen; jx++) {
1.106 +
1.107 + raw[0] = 0; /* sign is positive */
1.108 +
1.109 + /* Pack the initializer with random bytes */
1.110 + for(ix = 1; ix < rawlen; ix++)
1.111 + raw[ix] = (rand() * rand()) & UCHAR_MAX;
1.112 +
1.113 + raw[1] |= 0x80; /* set high-order bit of test value */
1.114 + raw[rawlen - 1] |= 1; /* set low-order bit of test value */
1.115 +
1.116 + /* Make an mp_int out of the initializer */
1.117 + mp_read_raw(&testval, (char *)raw, rawlen);
1.118 +
1.119 + /* Initialize candidate counter */
1.120 + nTries = 0;
1.121 +
1.122 + start = clock(); /* time generation for this prime */
1.123 + do {
1.124 + res = mpp_make_prime(&testval, bits, g_strong, &nTries);
1.125 + if (res != MP_NO)
1.126 + break;
1.127 + /* This code works whether digits are 16 or 32 bits */
1.128 + res = mp_add_d(&testval, 32 * 1024, &testval);
1.129 + res = mp_add_d(&testval, 32 * 1024, &testval);
1.130 + FPUTC(',', stderr);
1.131 + } while (1);
1.132 + end = clock();
1.133 +
1.134 + if (res != MP_YES) {
1.135 + break;
1.136 + }
1.137 + FPUTC('\n', stderr);
1.138 + puts("The following value is probably prime:");
1.139 + outlen = mp_radix_size(&testval, 10);
1.140 + out = calloc(outlen, sizeof(unsigned char));
1.141 + mp_toradix(&testval, (char *)out, 10);
1.142 + printf("10: %s\n", out);
1.143 + mp_toradix(&testval, (char *)out, 16);
1.144 + printf("16: %s\n\n", out);
1.145 + free(out);
1.146 +
1.147 + printf("Number of candidates tried: %lu\n", nTries);
1.148 + printf("This computation took %ld clock ticks (%.2f seconds)\n",
1.149 + (end - start), ((double)(end - start) / CLOCKS_PER_SEC));
1.150 +
1.151 + FPUTC('\n', stderr);
1.152 + } /* end of loop to generate all requested primes */
1.153 +
1.154 + if(res != MP_OKAY)
1.155 + fprintf(stderr, "%s: error: %s\n", argv[0], mp_strerror(res));
1.156 +
1.157 + free(raw);
1.158 + mp_clear(&testval);
1.159 +
1.160 + return 0;
1.161 +}
