The Tor Browser / file comparison
comparison: security/nss/lib/freebl/mpi/utils/primegen.c
security/nss/lib/freebl/mpi/utils/primegen.c
- changeset 0
- 6474c204b198
equal
deleted
inserted
replaced
| -1:000000000000 | 0:2a775c34d12e |
|---|---|
| 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/. */ | |
| 17 | |
| 18 #include <stdio.h> | |
| 19 #include <stdlib.h> | |
| 20 #include <string.h> | |
| 21 #include <limits.h> | |
| 22 #include <time.h> | |
| 23 | |
| 24 #include "mpi.h" | |
| 25 #include "mplogic.h" | |
| 26 #include "mpprime.h" | |
| 27 | |
| 28 #define NUM_TESTS 5 /* Number of Rabin-Miller iterations to test with */ | |
| 29 | |
| 30 #ifdef DEBUG | |
| 31 #define FPUTC(x,y) fputc(x,y) | |
| 32 #else | |
| 33 #define FPUTC(x,y) | |
| 34 #endif | |
| 35 | |
| 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; | |
| 46 | |
| 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 } | |
| 54 | |
| 55 if(argc < 2) { | |
| 56 fprintf(stderr, "Usage: %s <bits> [<count> [strong]]\n", argv[0]); | |
| 57 return 1; | |
| 58 } | |
| 59 | |
| 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 } | |
| 65 | |
| 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 } | |
| 74 | |
| 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; | |
| 80 | |
| 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 } | |
| 86 | |
| 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 } | |
| 93 | |
| 94 rawlen = (bits / CHAR_BIT) + ((bits % CHAR_BIT) ? 1 : 0) + 1; | |
| 95 | |
| 96 if((raw = calloc(rawlen, sizeof(unsigned char))) == NULL) { | |
| 97 fprintf(stderr, "%s: out of memory, sorry.\n", argv[0]); | |
| 98 return 1; | |
| 99 } | |
| 100 | |
| 101 /* This loop is one for each prime we need to generate */ | |
| 102 for(jx = 0; jx < ngen; jx++) { | |
| 103 | |
| 104 raw[0] = 0; /* sign is positive */ | |
| 105 | |
| 106 /* Pack the initializer with random bytes */ | |
| 107 for(ix = 1; ix < rawlen; ix++) | |
| 108 raw[ix] = (rand() * rand()) & UCHAR_MAX; | |
| 109 | |
| 110 raw[1] |= 0x80; /* set high-order bit of test value */ | |
| 111 raw[rawlen - 1] |= 1; /* set low-order bit of test value */ | |
| 112 | |
| 113 /* Make an mp_int out of the initializer */ | |
| 114 mp_read_raw(&testval, (char *)raw, rawlen); | |
| 115 | |
| 116 /* Initialize candidate counter */ | |
| 117 nTries = 0; | |
| 118 | |
| 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(); | |
| 130 | |
| 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); | |
| 143 | |
| 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)); | |
| 147 | |
| 148 FPUTC('\n', stderr); | |
| 149 } /* end of loop to generate all requested primes */ | |
| 150 | |
| 151 if(res != MP_OKAY) | |
| 152 fprintf(stderr, "%s: error: %s\n", argv[0], mp_strerror(res)); | |
| 153 | |
| 154 free(raw); | |
| 155 mp_clear(&testval); | |
| 156 | |
| 157 return 0; | |
| 158 } |
