diff options
Diffstat (limited to 'security/nss/lib/freebl/mpi/utils')
24 files changed, 1958 insertions, 0 deletions
diff --git a/security/nss/lib/freebl/mpi/utils/LICENSE b/security/nss/lib/freebl/mpi/utils/LICENSE new file mode 100644 index 000000000..5f96df7ab --- /dev/null +++ b/security/nss/lib/freebl/mpi/utils/LICENSE @@ -0,0 +1,4 @@ +Within this directory, each of the file listed below is licensed under +the terms given in the file LICENSE-MPL, also in this directory. + +PRIMES diff --git a/security/nss/lib/freebl/mpi/utils/LICENSE-MPL b/security/nss/lib/freebl/mpi/utils/LICENSE-MPL new file mode 100644 index 000000000..41dc2327f --- /dev/null +++ b/security/nss/lib/freebl/mpi/utils/LICENSE-MPL @@ -0,0 +1,3 @@ +This Source Code Form is subject to the terms of the Mozilla Public +License, v. 2.0. If a copy of the MPL was not distributed with this +file, You can obtain one at http://mozilla.org/MPL/2.0/. diff --git a/security/nss/lib/freebl/mpi/utils/PRIMES b/security/nss/lib/freebl/mpi/utils/PRIMES new file mode 100644 index 000000000..ed65703ff --- /dev/null +++ b/security/nss/lib/freebl/mpi/utils/PRIMES @@ -0,0 +1,41 @@ +Probable primes (sorted by number of significant bits) + + 128: 81386202757205669562183851789305348631 + + 128: 180241813863264101444573802809858694397 + + 128: 245274683055224433281596312431122059021 + + 128: 187522309397665259809392608791686659539 + + 256: 83252422946206411852330647237287722547866360773229941071371588246436\ + 513990159 + + 256: 79132571131322331023736933767063051273085304521895229780914612117520\ + 058517909 + + 256: 72081815425552909748220041100909735706208853818662000557743644603407\ + 965465527 + + 256: 87504602391905701494845474079163412737334477797316409702279059573654\ + 274811271 + + 512: 12233064210800062190450937494718705259777386009095453001870729392786\ + 63450255179083524798507997690270500580265258111668148238355016411719\ + 9168737693316468563 + + 512: 12003639081420725322369909586347545220275253633035565716386136197501\ + 88208318984400479275215620499883521216480724155582768193682335576385\ + 2069481074929084063 + +1024: 16467877625718912296741904171202513097057724053648819680815842057593\ + 20371835940722471475475803725455063836431454757000451907612224427007\ + 63984592414360595161051906727075047683803534852982766542661204179549\ + 77327573530800542562611753617736693359790119074768292178493884576587\ + 0230450429880021317876149636714743053 + +1024: 16602953991090311275234291158294516471009930684624948451178742895360\ + 86073703307475884280944414508444679430090561246728195735962931545473\ + 40743240318558456247740186704660778277799687988031119436541068736925\ + 20563780233711166724859277827382391527748470939542560819625727876091\ + 5372193745283891895989104479029844957 diff --git a/security/nss/lib/freebl/mpi/utils/README b/security/nss/lib/freebl/mpi/utils/README new file mode 100644 index 000000000..61c8e2efa --- /dev/null +++ b/security/nss/lib/freebl/mpi/utils/README @@ -0,0 +1,206 @@ +This Source Code Form is subject to the terms of the Mozilla Public +License, v. 2.0. If a copy of the MPL was not distributed with this +file, You can obtain one at http://mozilla.org/MPL/2.0/. + +Additional MPI utilities +------------------------ + +The files 'mpprime.h' and 'mpprime.c' define some useful extensions to +the MPI library for dealing with prime numbers (in particular, testing +for divisbility, and the Rabin-Miller probabilistic primality test). + +The files 'mplogic.h' and 'mplogic.c' define extensions to the MPI +library for doing bitwise logical operations and shifting. + +This document assumes you have read the help file for the MPI library +and understand its conventions. + +Divisibility (mpprime.h) +------------ + +To test a number for divisibility by another number: + +mpp_divis(a, b) - test if b|a +mpp_divis_d(a, d) - test if d|a + +Each of these functions returns MP_YES if its initial argument is +divisible by its second, or MP_NO if it is not. Other errors may be +returned as appropriate (such as MP_RANGE if you try to test for +divisibility by zero). + +Randomness (mpprime.h) +---------- + +To generate random data: + +mpp_random(a) - fill a with random data +mpp_random_size(a, p) - fill a with p digits of random data + +The mpp_random_size() function increases the precision of a to at +least p, then fills all those digits randomly. The mp_random() +function fills a to its current precision (as determined by the number +of significant digits, USED(a)) + +Note that these functions simply use the C library's rand() function +to fill a with random digits up to its precision. This should be +adequate for primality testing, but should not be used for +cryptographic applications where truly random values are required for +security. + +You should call srand() in your driver program in order to seed the +random generator; this function doesn't call it. + +Primality Testing (mpprime.h) +----------------- + +mpp_divis_vector(a, v, s, w) - is a divisible by any of the s values + in v, and if so, w = which. +mpp_divis_primes(a, np) - is a divisible by any of the first np primes? +mpp_fermat(a, w) - is a pseudoprime with respect to witness w? +mpp_pprime(a, nt) - run nt iterations of Rabin-Miller on a. + +The mpp_divis_vector() function tests a for divisibility by each +member of an array of digits. The array is v, the size of that array +is s. Returns MP_YES if a is divisible, and stores the index of the +offending digit in w. Returns MP_NO if a is not divisible by any of +the digits in the array. + +A small table of primes is compiled into the library (typically the +first 128 primes, although you can change this by editing the file +'primes.c' before you build). The global variable prime_tab_size +contains the number of primes in the table, and the values themselves +are in the array prime_tab[], which is an array of mp_digit. + +The mpp_divis_primes() function is basically just a wrapper around +mpp_divis_vector() that uses prime_tab[] as the test vector. The np +parameter is a pointer to an mp_digit -- on input, it should specify +the number of primes to be tested against. If a is divisible by any +of the primes, MP_YES is returned and np is given the prime value that +divided a (you can use this if you're factoring, for example). +Otherwise, MP_NO is returned and np is untouched. + +The function mpp_fermat() performs Fermat's test, using w as a +witness. This test basically relies on the fact that if a is prime, +and w is relatively prime to a, then: + + w^a = w (mod a) + +That is, + + w^(a - 1) = 1 (mod a) + +The function returns MP_YES if the test passes, MP_NO if it fails. If +w is relatively prime to a, and the test fails, a is definitely +composite. If w is relatively prime to a and the test passes, then a +is either prime, or w is a false witness (the probability of this +happening depends on the choice of w and of a ... consult a number +theory textbook for more information about this). + +Note: If (w, a) != 1, the output of this test is meaningless. +---- + +The function mpp_pprime() performs the Rabin-Miller probabilistic +primality test for nt rounds. If all the tests pass, MP_YES is +returned, and a is probably prime. The probability that an answer of +MP_YES is incorrect is no greater than 1 in 4^nt, and in fact is +usually much less than that (this is a pessimistic estimate). If any +test fails, MP_NO is returned, and a is definitely composite. + +Bruce Schneier recommends at least 5 iterations of this test for most +cryptographic applications; Knuth suggests that 25 are reasonable. +Run it as many times as you feel are necessary. + +See the programs 'makeprime.c' and 'isprime.c' for reasonable examples +of how to use these functions for primality testing. + + +Bitwise Logic (mplogic.c) +------------- + +The four commonest logical operations are implemented as: + +mpl_not(a, b) - Compute bitwise (one's) complement, b = ~a + +mpl_and(a, b, c) - Compute bitwise AND, c = a & b + +mpl_or(a, b, c) - Compute bitwise OR, c = a | b + +mpl_xor(a, b, c) - Compute bitwise XOR, c = a ^ b + +Left and right shifts are available as well. These take a number to +shift, a destination, and a shift amount. The shift amount must be a +digit value between 0 and DIGIT_BIT inclusive; if it is not, MP_RANGE +will be returned and the shift will not happen. + +mpl_rsh(a, b, d) - Compute logical right shift, b = a >> d + +mpl_lsh(a, b, d) - Compute logical left shift, b = a << d + +Since these are logical shifts, they fill with zeroes (the library +uses a signed magnitude representation, so there are no sign bits to +extend anyway). + + +Command-line Utilities +---------------------- + +A handful of interesting command-line utilities are provided. These +are: + +lap.c - Find the order of a mod m. Usage is 'lap <a> <m>'. + This uses a dumb algorithm, so don't use it for + a really big modulus. + +invmod.c - Find the inverse of a mod m, if it exists. Usage + is 'invmod <a> <m>' + +sieve.c - A simple bitmap-based implementation of the Sieve + of Eratosthenes. Used to generate the table of + primes in primes.c. Usage is 'sieve <nbits>' + +prng.c - Uses the routines in bbs_rand.{h,c} to generate + one or more 32-bit pseudo-random integers. This + is mainly an example, not intended for use in a + cryptographic application (the system time is + the only source of entropy used) + +dec2hex.c - Convert decimal to hexadecimal + +hex2dec.c - Convert hexadecimal to decimal + +basecvt.c - General radix conversion tool (supports 2-64) + +isprime.c - Probabilistically test an integer for primality + using the Rabin-Miller pseudoprime test combined + with division by small primes. + +primegen.c - Generate primes at random. + +exptmod.c - Perform modular exponentiation + +ptab.pl - A Perl script to munge the output of the sieve + program into a compilable C structure. + + +Other Files +----------- + +PRIMES - Some randomly generated numbers which are prime with + extremely high probability. + +README - You're reading me already. + + +About the Author +---------------- + +This software was written by Michael J. Fromberger. You can contact +the author as follows: + +E-mail: <sting@linguist.dartmouth.edu> + +Postal: 8000 Cummings Hall, Thayer School of Engineering + Dartmouth College, Hanover, New Hampshire, USA + +PGP key: http://linguist.dartmouth.edu/~sting/keys/mjf.html + 9736 188B 5AFA 23D6 D6AA BE0D 5856 4525 289D 9907 diff --git a/security/nss/lib/freebl/mpi/utils/basecvt.c b/security/nss/lib/freebl/mpi/utils/basecvt.c new file mode 100644 index 000000000..0e9915406 --- /dev/null +++ b/security/nss/lib/freebl/mpi/utils/basecvt.c @@ -0,0 +1,68 @@ +/* + * basecvt.c + * + * Convert integer values specified on the command line from one input + * base to another. Accepts input and output bases between 2 and 36 + * inclusive. + * + * This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ + +#include <stdio.h> +#include <stdlib.h> +#include <string.h> + +#include "mpi.h" + +#define IBASE 10 +#define OBASE 16 +#define USAGE "Usage: %s ibase obase [value]\n" +#define MAXBASE 64 +#define MINBASE 2 + +int +main(int argc, char *argv[]) +{ + int ix, ibase = IBASE, obase = OBASE; + mp_int val; + + ix = 1; + if (ix < argc) { + ibase = atoi(argv[ix++]); + + if (ibase < MINBASE || ibase > MAXBASE) { + fprintf(stderr, "%s: input radix must be between %d and %d inclusive\n", + argv[0], MINBASE, MAXBASE); + return 1; + } + } + if (ix < argc) { + obase = atoi(argv[ix++]); + + if (obase < MINBASE || obase > MAXBASE) { + fprintf(stderr, "%s: output radix must be between %d and %d inclusive\n", + argv[0], MINBASE, MAXBASE); + return 1; + } + } + + mp_init(&val); + while (ix < argc) { + char *out; + int outlen; + + mp_read_radix(&val, argv[ix++], ibase); + + outlen = mp_radix_size(&val, obase); + out = calloc(outlen, sizeof(char)); + mp_toradix(&val, out, obase); + + printf("%s\n", out); + free(out); + } + + mp_clear(&val); + + return 0; +} diff --git a/security/nss/lib/freebl/mpi/utils/bbs_rand.c b/security/nss/lib/freebl/mpi/utils/bbs_rand.c new file mode 100644 index 000000000..fed2fe2e6 --- /dev/null +++ b/security/nss/lib/freebl/mpi/utils/bbs_rand.c @@ -0,0 +1,65 @@ +/* + * Blum, Blum & Shub PRNG using the MPI library + * + * This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ + +#include "bbs_rand.h" + +#define SEED 1 +#define MODULUS 2 + +/* This modulus is the product of two randomly generated 512-bit + prime integers, each of which is congruent to 3 (mod 4). */ +static char *bbs_modulus = + "75A2A6E1D27393B86562B9CE7279A8403CB4258A637DAB5233465373E37837383EDC" + "332282B8575927BC4172CE8C147B4894050EE9D2BDEED355C121037270CA2570D127" + "7D2390CD1002263326635CC6B259148DE3A1A03201980A925E395E646A5E9164B0EC" + "28559EBA58C87447245ADD0651EDA507056A1129E3A3E16E903D64B437"; + +static int bbs_init = 0; /* flag set when library is initialized */ +static mp_int bbs_state; /* the current state of the generator */ + +/* Suggested size of random seed data */ +int bbs_seed_size = (sizeof(bbs_modulus) / 2); + +void +bbs_srand(unsigned char *data, int len) +{ + if ((bbs_init & SEED) == 0) { + mp_init(&bbs_state); + bbs_init |= SEED; + } + + mp_read_raw(&bbs_state, (char *)data, len); + +} /* end bbs_srand() */ + +unsigned int +bbs_rand(void) +{ + static mp_int modulus; + unsigned int result = 0, ix; + + if ((bbs_init & MODULUS) == 0) { + mp_init(&modulus); + mp_read_radix(&modulus, bbs_modulus, 16); + bbs_init |= MODULUS; + } + + for (ix = 0; ix < sizeof(unsigned int); ix++) { + mp_digit d; + + mp_sqrmod(&bbs_state, &modulus, &bbs_state); + d = DIGIT(&bbs_state, 0); + + result = (result << CHAR_BIT) | (d & UCHAR_MAX); + } + + return result; + +} /* end bbs_rand() */ + +/*------------------------------------------------------------------------*/ +/* HERE THERE BE DRAGONS */ diff --git a/security/nss/lib/freebl/mpi/utils/bbs_rand.h b/security/nss/lib/freebl/mpi/utils/bbs_rand.h new file mode 100644 index 000000000..d12269bf9 --- /dev/null +++ b/security/nss/lib/freebl/mpi/utils/bbs_rand.h @@ -0,0 +1,24 @@ +/* + * bbs_rand.h + * + * Blum, Blum & Shub PRNG using the MPI library + * + * This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ + +#ifndef _H_BBSRAND_ +#define _H_BBSRAND_ + +#include <limits.h> +#include "mpi.h" + +#define BBS_RAND_MAX UINT_MAX + +/* Suggested length of seed data */ +extern int bbs_seed_size; + +void bbs_srand(unsigned char *data, int len); +unsigned int bbs_rand(void); + +#endif /* end _H_BBSRAND_ */ diff --git a/security/nss/lib/freebl/mpi/utils/bbsrand.c b/security/nss/lib/freebl/mpi/utils/bbsrand.c new file mode 100644 index 000000000..d9151e005 --- /dev/null +++ b/security/nss/lib/freebl/mpi/utils/bbsrand.c @@ -0,0 +1,35 @@ +/* + * bbsrand.c + * + * Test driver for routines in bbs_rand.h + * + * This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ + +#include <stdio.h> +#include <stdlib.h> +#include <string.h> +#include <time.h> +#include <limits.h> + +#include "bbs_rand.h" + +#define NUM_TESTS 100 + +int +main(void) +{ + unsigned int seed, result, ix; + + seed = time(NULL); + bbs_srand((unsigned char *)&seed, sizeof(seed)); + + for (ix = 0; ix < NUM_TESTS; ix++) { + result = bbs_rand(); + + printf("Test %3u: %08X\n", ix + 1, result); + } + + return 0; +} diff --git a/security/nss/lib/freebl/mpi/utils/dec2hex.c b/security/nss/lib/freebl/mpi/utils/dec2hex.c new file mode 100644 index 000000000..ef3a52095 --- /dev/null +++ b/security/nss/lib/freebl/mpi/utils/dec2hex.c @@ -0,0 +1,40 @@ +/* + * dec2hex.c + * + * Convert decimal integers into hexadecimal + * + * This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ + +#include <stdio.h> +#include <stdlib.h> +#include <string.h> + +#include "mpi.h" + +int +main(int argc, char *argv[]) +{ + mp_int a; + char *buf; + int len; + + if (argc < 2) { + fprintf(stderr, "Usage: %s <a>\n", argv[0]); + return 1; + } + + mp_init(&a); + mp_read_radix(&a, argv[1], 10); + len = mp_radix_size(&a, 16); + buf = malloc(len); + mp_toradix(&a, buf, 16); + + printf("%s\n", buf); + + free(buf); + mp_clear(&a); + + return 0; +} diff --git a/security/nss/lib/freebl/mpi/utils/exptmod.c b/security/nss/lib/freebl/mpi/utils/exptmod.c new file mode 100644 index 000000000..3ac9078f4 --- /dev/null +++ b/security/nss/lib/freebl/mpi/utils/exptmod.c @@ -0,0 +1,55 @@ +/* + * exptmod.c + * + * Command line tool to perform modular exponentiation on arbitrary + * precision integers. + * + * This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ + +#include <stdio.h> +#include <stdlib.h> +#include <string.h> + +#include "mpi.h" + +int +main(int argc, char *argv[]) +{ + mp_int a, b, m; + mp_err res; + char *str; + int len, rval = 0; + + if (argc < 3) { + fprintf(stderr, "Usage: %s <a> <b> <m>\n", argv[0]); + return 1; + } + + mp_init(&a); + mp_init(&b); + mp_init(&m); + mp_read_radix(&a, argv[1], 10); + mp_read_radix(&b, argv[2], 10); + mp_read_radix(&m, argv[3], 10); + + if ((res = mp_exptmod(&a, &b, &m, &a)) != MP_OKAY) { + fprintf(stderr, "%s: error: %s\n", argv[0], mp_strerror(res)); + rval = 1; + } else { + len = mp_radix_size(&a, 10); + str = calloc(len, sizeof(char)); + mp_toradix(&a, str, 10); + + printf("%s\n", str); + + free(str); + } + + mp_clear(&a); + mp_clear(&b); + mp_clear(&m); + + return rval; +} diff --git a/security/nss/lib/freebl/mpi/utils/fact.c b/security/nss/lib/freebl/mpi/utils/fact.c new file mode 100644 index 000000000..da8e61a32 --- /dev/null +++ b/security/nss/lib/freebl/mpi/utils/fact.c @@ -0,0 +1,84 @@ +/* + * fact.c + * + * Compute factorial of input integer + * + * This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ + +#include <stdio.h> +#include <stdlib.h> +#include <string.h> + +#include "mpi.h" + +mp_err mp_fact(mp_int *a, mp_int *b); + +int +main(int argc, char *argv[]) +{ + mp_int a; + mp_err res; + + if (argc < 2) { + fprintf(stderr, "Usage: %s <number>\n", argv[0]); + return 1; + } + + mp_init(&a); + mp_read_radix(&a, argv[1], 10); + + if ((res = mp_fact(&a, &a)) != MP_OKAY) { + fprintf(stderr, "%s: error: %s\n", argv[0], + mp_strerror(res)); + mp_clear(&a); + return 1; + } + + { + char *buf; + int len; + + len = mp_radix_size(&a, 10); + buf = malloc(len); + mp_todecimal(&a, buf); + + puts(buf); + + free(buf); + } + + mp_clear(&a); + return 0; +} + +mp_err +mp_fact(mp_int *a, mp_int *b) +{ + mp_int ix, s; + mp_err res = MP_OKAY; + + if (mp_cmp_z(a) < 0) + return MP_UNDEF; + + mp_init(&s); + mp_add_d(&s, 1, &s); /* s = 1 */ + mp_init(&ix); + mp_add_d(&ix, 1, &ix); /* ix = 1 */ + + for (/* */; mp_cmp(&ix, a) <= 0; mp_add_d(&ix, 1, &ix)) { + if ((res = mp_mul(&s, &ix, &s)) != MP_OKAY) + break; + } + + mp_clear(&ix); + + /* Copy out results if we got them */ + if (res == MP_OKAY) + mp_copy(&s, b); + + mp_clear(&s); + + return res; +} diff --git a/security/nss/lib/freebl/mpi/utils/gcd.c b/security/nss/lib/freebl/mpi/utils/gcd.c new file mode 100644 index 000000000..9f11a250b --- /dev/null +++ b/security/nss/lib/freebl/mpi/utils/gcd.c @@ -0,0 +1,95 @@ +/* + * gcd.c + * + * Greatest common divisor + * + * This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ + +#include <stdio.h> +#include <stdlib.h> +#include <string.h> + +#include "mpi.h" + +char *g_prog = NULL; + +void print_mp_int(mp_int *mp, FILE *ofp); + +int +main(int argc, char *argv[]) +{ + mp_int a, b, x, y; + mp_err res; + int ext = 0; + + g_prog = argv[0]; + + if (argc < 3) { + fprintf(stderr, "Usage: %s <a> <b>\n", g_prog); + return 1; + } + + mp_init(&a); + mp_read_radix(&a, argv[1], 10); + mp_init(&b); + mp_read_radix(&b, argv[2], 10); + + /* If we were called 'xgcd', compute x, y so that g = ax + by */ + if (strcmp(g_prog, "xgcd") == 0) { + ext = 1; + mp_init(&x); + mp_init(&y); + } + + if (ext) { + if ((res = mp_xgcd(&a, &b, &a, &x, &y)) != MP_OKAY) { + fprintf(stderr, "%s: error: %s\n", g_prog, mp_strerror(res)); + mp_clear(&a); + mp_clear(&b); + mp_clear(&x); + mp_clear(&y); + return 1; + } + } else { + if ((res = mp_gcd(&a, &b, &a)) != MP_OKAY) { + fprintf(stderr, "%s: error: %s\n", g_prog, + mp_strerror(res)); + mp_clear(&a); + mp_clear(&b); + return 1; + } + } + + print_mp_int(&a, stdout); + if (ext) { + fputs("x = ", stdout); + print_mp_int(&x, stdout); + fputs("y = ", stdout); + print_mp_int(&y, stdout); + } + + mp_clear(&a); + mp_clear(&b); + + if (ext) { + mp_clear(&x); + mp_clear(&y); + } + + return 0; +} + +void +print_mp_int(mp_int *mp, FILE *ofp) +{ + char *buf; + int len; + + len = mp_radix_size(mp, 10); + buf = calloc(len, sizeof(char)); + mp_todecimal(mp, buf); + fprintf(ofp, "%s\n", buf); + free(buf); +} diff --git a/security/nss/lib/freebl/mpi/utils/hex2dec.c b/security/nss/lib/freebl/mpi/utils/hex2dec.c new file mode 100644 index 000000000..9b21d22e0 --- /dev/null +++ b/security/nss/lib/freebl/mpi/utils/hex2dec.c @@ -0,0 +1,40 @@ +/* + * hex2dec.c + * + * Convert decimal integers into hexadecimal + * + * This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ + +#include <stdio.h> +#include <stdlib.h> +#include <string.h> + +#include "mpi.h" + +int +main(int argc, char *argv[]) +{ + mp_int a; + char *buf; + int len; + + if (argc < 2) { + fprintf(stderr, "Usage: %s <a>\n", argv[0]); + return 1; + } + + mp_init(&a); + mp_read_radix(&a, argv[1], 16); + len = mp_radix_size(&a, 10); + buf = malloc(len); + mp_toradix(&a, buf, 10); + + printf("%s\n", buf); + + free(buf); + mp_clear(&a); + + return 0; +} diff --git a/security/nss/lib/freebl/mpi/utils/identest.c b/security/nss/lib/freebl/mpi/utils/identest.c new file mode 100644 index 000000000..321d2c2b0 --- /dev/null +++ b/security/nss/lib/freebl/mpi/utils/identest.c @@ -0,0 +1,84 @@ +/* This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ + +#include <stdio.h> +#include <stdlib.h> +#include "mpi.h" +#include "mpprime.h" +#include <sys/types.h> +#include <time.h> + +#define MAX_PREC (4096 / MP_DIGIT_BIT) + +mp_err +identity_test(void) +{ + mp_size preca, precb; + mp_err res; + mp_int a, b; + mp_int t1, t2, t3, t4, t5; + + preca = (rand() % MAX_PREC) + 1; + precb = (rand() % MAX_PREC) + 1; + + MP_DIGITS(&a) = 0; + MP_DIGITS(&b) = 0; + MP_DIGITS(&t1) = 0; + MP_DIGITS(&t2) = 0; + MP_DIGITS(&t3) = 0; + MP_DIGITS(&t4) = 0; + MP_DIGITS(&t5) = 0; + + MP_CHECKOK(mp_init(&a)); + MP_CHECKOK(mp_init(&b)); + MP_CHECKOK(mp_init(&t1)); + MP_CHECKOK(mp_init(&t2)); + MP_CHECKOK(mp_init(&t3)); + MP_CHECKOK(mp_init(&t4)); + MP_CHECKOK(mp_init(&t5)); + + MP_CHECKOK(mpp_random_size(&a, preca)); + MP_CHECKOK(mpp_random_size(&b, precb)); + + if (mp_cmp(&a, &b) < 0) + mp_exch(&a, &b); + + MP_CHECKOK(mp_mod(&a, &b, &t1)); /* t1 = a%b */ + MP_CHECKOK(mp_div(&a, &b, &t2, NULL)); /* t2 = a/b */ + MP_CHECKOK(mp_mul(&b, &t2, &t3)); /* t3 = (a/b)*b */ + MP_CHECKOK(mp_add(&t1, &t3, &t4)); /* t4 = a%b + (a/b)*b */ + MP_CHECKOK(mp_sub(&t4, &a, &t5)); /* t5 = a%b + (a/b)*b - a */ + if (mp_cmp_z(&t5) != 0) { + res = MP_UNDEF; + goto CLEANUP; + } + +CLEANUP: + mp_clear(&t5); + mp_clear(&t4); + mp_clear(&t3); + mp_clear(&t2); + mp_clear(&t1); + mp_clear(&b); + mp_clear(&a); + return res; +} + +int +main(void) +{ + unsigned int seed = (unsigned int)time(NULL); + unsigned long count = 0; + mp_err res; + + srand(seed); + + while (MP_OKAY == (res = identity_test())) { + if ((++count % 100) == 0) + fputc('.', stderr); + } + + fprintf(stderr, "\ntest failed, err %d\n", res); + return res; +} diff --git a/security/nss/lib/freebl/mpi/utils/invmod.c b/security/nss/lib/freebl/mpi/utils/invmod.c new file mode 100644 index 000000000..9b4b04d3f --- /dev/null +++ b/security/nss/lib/freebl/mpi/utils/invmod.c @@ -0,0 +1,61 @@ +/* + * invmod.c + * + * Compute modular inverses + * + * This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ + +#include <stdio.h> +#include <stdlib.h> + +#include "mpi.h" + +int +main(int argc, char *argv[]) +{ + mp_int a, m; + mp_err res; + char *buf; + int len, out = 0; + + if (argc < 3) { + fprintf(stderr, "Usage: %s <a> <m>\n", argv[0]); + return 1; + } + + mp_init(&a); + mp_init(&m); + mp_read_radix(&a, argv[1], 10); + mp_read_radix(&m, argv[2], 10); + + if (mp_cmp(&a, &m) > 0) + mp_mod(&a, &m, &a); + + switch ((res = mp_invmod(&a, &m, &a))) { + case MP_OKAY: + len = mp_radix_size(&a, 10); + buf = malloc(len); + + mp_toradix(&a, buf, 10); + printf("%s\n", buf); + free(buf); + break; + + case MP_UNDEF: + printf("No inverse\n"); + out = 1; + break; + + default: + printf("error: %s (%d)\n", mp_strerror(res), res); + out = 2; + break; + } + + mp_clear(&a); + mp_clear(&m); + + return out; +} diff --git a/security/nss/lib/freebl/mpi/utils/isprime.c b/security/nss/lib/freebl/mpi/utils/isprime.c new file mode 100644 index 000000000..d2d86957e --- /dev/null +++ b/security/nss/lib/freebl/mpi/utils/isprime.c @@ -0,0 +1,89 @@ +/* + * isprime.c + * + * Probabilistic primality tester command-line tool + * + * This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ + +#include <stdio.h> +#include <stdlib.h> +#include <string.h> + +#include "mpi.h" +#include "mpprime.h" + +#define RM_TESTS 15 /* how many iterations of Rabin-Miller? */ +#define MINIMUM 1024 /* don't bother us with a < this */ + +int g_tests = RM_TESTS; +char *g_prog = NULL; + +int +main(int argc, char *argv[]) +{ + mp_int a; + mp_digit np = prime_tab_size; /* from mpprime.h */ + int res = 0; + + g_prog = argv[0]; + + if (argc < 2) { + fprintf(stderr, "Usage: %s <a>, where <a> is a decimal integer\n" + "Use '0x' prefix for a hexadecimal value\n", + g_prog); + return 1; + } + + /* Read number of tests from environment, if present */ + { + char *tmp; + + if ((tmp = PR_GetEnvSecure("RM_TESTS")) != NULL) { + if ((g_tests = atoi(tmp)) <= 0) + g_tests = RM_TESTS; + } + } + + mp_init(&a); + if (argv[1][0] == '0' && argv[1][1] == 'x') + mp_read_radix(&a, argv[1] + 2, 16); + else + mp_read_radix(&a, argv[1], 10); + + if (mp_cmp_d(&a, MINIMUM) <= 0) { + fprintf(stderr, "%s: please use a value greater than %d\n", + g_prog, MINIMUM); + mp_clear(&a); + return 1; + } + + /* Test for divisibility by small primes */ + if (mpp_divis_primes(&a, &np) != MP_NO) { + printf("Not prime (divisible by small prime %d)\n", np); + res = 2; + goto CLEANUP; + } + + /* Test with Fermat's test, using 2 as a witness */ + if (mpp_fermat(&a, 2) != MP_YES) { + printf("Not prime (failed Fermat test)\n"); + res = 2; + goto CLEANUP; + } + + /* Test with Rabin-Miller probabilistic test */ + if (mpp_pprime(&a, g_tests) == MP_NO) { + printf("Not prime (failed pseudoprime test)\n"); + res = 2; + goto CLEANUP; + } + + printf("Probably prime, 1 in 4^%d chance of false positive\n", g_tests); + +CLEANUP: + mp_clear(&a); + + return res; +} diff --git a/security/nss/lib/freebl/mpi/utils/lap.c b/security/nss/lib/freebl/mpi/utils/lap.c new file mode 100644 index 000000000..501e4531d --- /dev/null +++ b/security/nss/lib/freebl/mpi/utils/lap.c @@ -0,0 +1,90 @@ +/* + * lap.c + * + * Find least annihilating power of a mod m + * + * This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ + +#include <stdio.h> +#include <stdlib.h> +#include <signal.h> + +#include "mpi.h" + +void sig_catch(int ign); + +int g_quit = 0; + +int +main(int argc, char *argv[]) +{ + mp_int a, m, p, k; + + if (argc < 3) { + fprintf(stderr, "Usage: %s <a> <m>\n", argv[0]); + return 1; + } + + mp_init(&a); + mp_init(&m); + mp_init(&p); + mp_add_d(&p, 1, &p); + + mp_read_radix(&a, argv[1], 10); + mp_read_radix(&m, argv[2], 10); + + mp_init_copy(&k, &a); + + signal(SIGINT, sig_catch); +#ifndef __OS2__ + signal(SIGHUP, sig_catch); +#endif + signal(SIGTERM, sig_catch); + + while (mp_cmp(&p, &m) < 0) { + if (g_quit) { + int len; + char *buf; + + len = mp_radix_size(&p, 10); + buf = malloc(len); + mp_toradix(&p, buf, 10); + + fprintf(stderr, "Terminated at: %s\n", buf); + free(buf); + return 1; + } + if (mp_cmp_d(&k, 1) == 0) { + int len; + char *buf; + + len = mp_radix_size(&p, 10); + buf = malloc(len); + mp_toradix(&p, buf, 10); + + printf("%s\n", buf); + + free(buf); + break; + } + + mp_mulmod(&k, &a, &m, &k); + mp_add_d(&p, 1, &p); + } + + if (mp_cmp(&p, &m) >= 0) + printf("No annihilating power.\n"); + + mp_clear(&p); + mp_clear(&m); + mp_clear(&a); + return 0; +} + +void +sig_catch(int ign) +{ + g_quit = 1; +} diff --git a/security/nss/lib/freebl/mpi/utils/makeprime.c b/security/nss/lib/freebl/mpi/utils/makeprime.c new file mode 100644 index 000000000..401b7532b --- /dev/null +++ b/security/nss/lib/freebl/mpi/utils/makeprime.c @@ -0,0 +1,116 @@ +/* + * makeprime.c + * + * A simple prime generator function (and test driver). Prints out the + * first prime it finds greater than or equal to the starting value. + * + * Usage: makeprime <start> + * + * This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ + +#include <stdio.h> +#include <stdlib.h> +#include <ctype.h> + +/* These two must be included for make_prime() to work */ + +#include "mpi.h" +#include "mpprime.h" + +/* + make_prime(p, nr) + + Find the smallest prime integer greater than or equal to p, where + primality is verified by 'nr' iterations of the Rabin-Miller + probabilistic primality test. The caller is responsible for + generating the initial value of p. + + Returns MP_OKAY if a prime has been generated, otherwise the error + code indicates some other problem. The value of p is clobbered; the + caller should keep a copy if the value is needed. + */ +mp_err make_prime(mp_int *p, int nr); + +/* The main() is not required -- it's just a test driver */ +int +main(int argc, char *argv[]) +{ + mp_int start; + mp_err res; + + if (argc < 2) { + fprintf(stderr, "Usage: %s <start-value>\n", argv[0]); + return 1; + } + + mp_init(&start); + if (argv[1][0] == '0' && tolower(argv[1][1]) == 'x') { + mp_read_radix(&start, argv[1] + 2, 16); + } else { + mp_read_radix(&start, argv[1], 10); + } + mp_abs(&start, &start); + + if ((res = make_prime(&start, 5)) != MP_OKAY) { + fprintf(stderr, "%s: error: %s\n", argv[0], mp_strerror(res)); + mp_clear(&start); + + return 1; + + } else { + char *buf = malloc(mp_radix_size(&start, 10)); + + mp_todecimal(&start, buf); + printf("%s\n", buf); + free(buf); + + mp_clear(&start); + + return 0; + } + +} /* end main() */ + +/*------------------------------------------------------------------------*/ + +mp_err +make_prime(mp_int *p, int nr) +{ + mp_err res; + + if (mp_iseven(p)) { + mp_add_d(p, 1, p); + } + + do { + mp_digit which = prime_tab_size; + + /* First test for divisibility by a few small primes */ + if ((res = mpp_divis_primes(p, &which)) == MP_YES) + continue; + else if (res != MP_NO) + goto CLEANUP; + + /* If that passes, try one iteration of Fermat's test */ + if ((res = mpp_fermat(p, 2)) == MP_NO) + continue; + else if (res != MP_YES) + goto CLEANUP; + + /* If that passes, run Rabin-Miller as often as requested */ + if ((res = mpp_pprime(p, nr)) == MP_YES) + break; + else if (res != MP_NO) + goto CLEANUP; + + } while ((res = mp_add_d(p, 2, p)) == MP_OKAY); + +CLEANUP: + return res; + +} /* end make_prime() */ + +/*------------------------------------------------------------------------*/ +/* HERE THERE BE DRAGONS */ diff --git a/security/nss/lib/freebl/mpi/utils/metime.c b/security/nss/lib/freebl/mpi/utils/metime.c new file mode 100644 index 000000000..122875ee0 --- /dev/null +++ b/security/nss/lib/freebl/mpi/utils/metime.c @@ -0,0 +1,102 @@ +/* + * metime.c + * + * Modular exponentiation timing test + * + * This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ + +#include <stdio.h> +#include <stdlib.h> +#include <string.h> +#include <limits.h> +#include <time.h> + +#include "mpi.h" +#include "mpprime.h" + +double clk_to_sec(clock_t start, clock_t stop); + +int +main(int argc, char *argv[]) +{ + int ix, num, prec = 8; + unsigned int seed; + clock_t start, stop; + double sec; + + mp_int a, m, c; + + if (PR_GetEnvSecure("SEED") != NULL) + seed = abs(atoi(PR_GetEnvSecure("SEED"))); + else + seed = (unsigned int)time(NULL); + + if (argc < 2) { + fprintf(stderr, "Usage: %s <num-tests> [<nbits>]\n", argv[0]); + return 1; + } + + if ((num = atoi(argv[1])) < 0) + num = -num; + + if (!num) { + fprintf(stderr, "%s: must perform at least 1 test\n", argv[0]); + return 1; + } + + if (argc > 2) { + if ((prec = atoi(argv[2])) <= 0) + prec = 8; + else + prec = (prec + (DIGIT_BIT - 1)) / DIGIT_BIT; + } + + printf("Modular exponentiation timing test\n" + "Precision: %d digits (%d bits)\n" + "# of tests: %d\n\n", + prec, prec * DIGIT_BIT, num); + + mp_init_size(&a, prec); + mp_init_size(&m, prec); + mp_init_size(&c, prec); + + srand(seed); + + start = clock(); + for (ix = 0; ix < num; ix++) { + + mpp_random_size(&a, prec); + mpp_random_size(&c, prec); + mpp_random_size(&m, prec); + /* set msb and lsb of m */ + DIGIT(&m, 0) |= 1; + DIGIT(&m, USED(&m) - 1) |= (mp_digit)1 << (DIGIT_BIT - 1); + if (mp_cmp(&a, &m) > 0) + mp_sub(&a, &m, &a); + + mp_exptmod(&a, &c, &m, &c); + } + stop = clock(); + + sec = clk_to_sec(start, stop); + + printf("Total: %.3f seconds\n", sec); + printf("Individual: %.3f seconds\n", sec / num); + + mp_clear(&c); + mp_clear(&a); + mp_clear(&m); + + return 0; +} + +double +clk_to_sec(clock_t start, clock_t stop) +{ + return (double)(stop - start) / CLOCKS_PER_SEC; +} + +/*------------------------------------------------------------------------*/ +/* HERE THERE BE DRAGONS */ diff --git a/security/nss/lib/freebl/mpi/utils/pi.c b/security/nss/lib/freebl/mpi/utils/pi.c new file mode 100644 index 000000000..7e3109786 --- /dev/null +++ b/security/nss/lib/freebl/mpi/utils/pi.c @@ -0,0 +1,171 @@ +/* + * pi.c + * + * Compute pi to an arbitrary number of digits. Uses Machin's formula, + * like everyone else on the planet: + * + * pi = 16 * arctan(1/5) - 4 * arctan(1/239) + * + * This is pretty effective for up to a few thousand digits, but it + * gets pretty slow after that. + * + * This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ + +#include <stdio.h> +#include <stdlib.h> +#include <string.h> +#include <limits.h> +#include <time.h> + +#include "mpi.h" + +mp_err arctan(mp_digit mul, mp_digit x, mp_digit prec, mp_int *sum); + +int +main(int argc, char *argv[]) +{ + mp_err res; + mp_digit ndigits; + mp_int sum1, sum2; + clock_t start, stop; + int out = 0; + + /* Make the user specify precision on the command line */ + if (argc < 2) { + fprintf(stderr, "Usage: %s <num-digits>\n", argv[0]); + return 1; + } + + if ((ndigits = abs(atoi(argv[1]))) == 0) { + fprintf(stderr, "%s: you must request at least 1 digit\n", argv[0]); + return 1; + } + + start = clock(); + mp_init(&sum1); + mp_init(&sum2); + + /* sum1 = 16 * arctan(1/5) */ + if ((res = arctan(16, 5, ndigits, &sum1)) != MP_OKAY) { + fprintf(stderr, "%s: arctan: %s\n", argv[0], mp_strerror(res)); + out = 1; + goto CLEANUP; + } + + /* sum2 = 4 * arctan(1/239) */ + if ((res = arctan(4, 239, ndigits, &sum2)) != MP_OKAY) { + fprintf(stderr, "%s: arctan: %s\n", argv[0], mp_strerror(res)); + out = 1; + goto CLEANUP; + } + + /* pi = sum1 - sum2 */ + if ((res = mp_sub(&sum1, &sum2, &sum1)) != MP_OKAY) { + fprintf(stderr, "%s: mp_sub: %s\n", argv[0], mp_strerror(res)); + out = 1; + goto CLEANUP; + } + stop = clock(); + + /* Write the output in decimal */ + { + char *buf = malloc(mp_radix_size(&sum1, 10)); + + if (buf == NULL) { + fprintf(stderr, "%s: out of memory\n", argv[0]); + out = 1; + goto CLEANUP; + } + mp_todecimal(&sum1, buf); + printf("%s\n", buf); + free(buf); + } + + fprintf(stderr, "Computation took %.2f sec.\n", + (double)(stop - start) / CLOCKS_PER_SEC); + +CLEANUP: + mp_clear(&sum1); + mp_clear(&sum2); + + return out; +} + +/* Compute sum := mul * arctan(1/x), to 'prec' digits of precision */ +mp_err +arctan(mp_digit mul, mp_digit x, mp_digit prec, mp_int *sum) +{ + mp_int t, v; + mp_digit q = 1, rd; + mp_err res; + int sign = 1; + + prec += 3; /* push inaccuracies off the end */ + + mp_init(&t); + mp_set(&t, 10); + mp_init(&v); + if ((res = mp_expt_d(&t, prec, &t)) != MP_OKAY || /* get 10^prec */ + (res = mp_mul_d(&t, mul, &t)) != MP_OKAY || /* ... times mul */ + (res = mp_mul_d(&t, x, &t)) != MP_OKAY) /* ... times x */ + goto CLEANUP; + + /* + The extra multiplication by x in the above takes care of what + would otherwise have to be a special case for 1 / x^1 during the + first loop iteration. A little sneaky, but effective. + + We compute arctan(1/x) by the formula: + + 1 1 1 1 + - - ----- + ----- - ----- + ... + x 3 x^3 5 x^5 7 x^7 + + We multiply through by 'mul' beforehand, which gives us a couple + more iterations and more precision + */ + + x *= x; /* works as long as x < sqrt(RADIX), which it is here */ + + mp_zero(sum); + + do { + if ((res = mp_div_d(&t, x, &t, &rd)) != MP_OKAY) + goto CLEANUP; + + if (sign < 0 && rd != 0) + mp_add_d(&t, 1, &t); + + if ((res = mp_div_d(&t, q, &v, &rd)) != MP_OKAY) + goto CLEANUP; + + if (sign < 0 && rd != 0) + mp_add_d(&v, 1, &v); + + if (sign > 0) + res = mp_add(sum, &v, sum); + else + res = mp_sub(sum, &v, sum); + + if (res != MP_OKAY) + goto CLEANUP; + + sign *= -1; + q += 2; + + } while (mp_cmp_z(&t) != 0); + + /* Chop off inaccurate low-order digits */ + mp_div_d(sum, 1000, sum, NULL); + +CLEANUP: + mp_clear(&v); + mp_clear(&t); + + return res; +} + +/*------------------------------------------------------------------------*/ +/* HERE THERE BE DRAGONS */ diff --git a/security/nss/lib/freebl/mpi/utils/primegen.c b/security/nss/lib/freebl/mpi/utils/primegen.c new file mode 100644 index 000000000..f62a56a4e --- /dev/null +++ b/security/nss/lib/freebl/mpi/utils/primegen.c @@ -0,0 +1,159 @@ +/* + * primegen.c + * + * Generates random integers which are prime with a high degree of + * probability using the Miller-Rabin probabilistic primality testing + * algorithm. + * + * Usage: + * primegen <bits> [<num>] + * + * <bits> - number of significant bits each prime should have + * <num> - number of primes to generate + * + * This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ + +#include <stdio.h> +#include <stdlib.h> +#include <string.h> +#include <limits.h> +#include <time.h> + +#include "mpi.h" +#include "mplogic.h" +#include "mpprime.h" + +#define NUM_TESTS 5 /* Number of Rabin-Miller iterations to test with */ + +#ifdef DEBUG +#define FPUTC(x, y) fputc(x, y) +#else +#define FPUTC(x, y) +#endif + +int +main(int argc, char *argv[]) +{ + unsigned char *raw; + char *out; + unsigned long nTries; + int rawlen, bits, outlen, ngen, ix, jx; + int g_strong = 0; + mp_int testval; + mp_err res; + clock_t start, end; + + /* We'll just use the C library's rand() for now, although this + won't be good enough for cryptographic purposes */ + if ((out = PR_GetEnvSecure("SEED")) == NULL) { + srand((unsigned int)time(NULL)); + } else { + srand((unsigned int)atoi(out)); + } + + if (argc < 2) { + fprintf(stderr, "Usage: %s <bits> [<count> [strong]]\n", argv[0]); + return 1; + } + + if ((bits = abs(atoi(argv[1]))) < CHAR_BIT) { + fprintf(stderr, "%s: please request at least %d bits.\n", + argv[0], CHAR_BIT); + return 1; + } + + /* If optional third argument is given, use that as the number of + primes to generate; otherwise generate one prime only. + */ + if (argc < 3) { + ngen = 1; + } else { + ngen = abs(atoi(argv[2])); + } + + /* If fourth argument is given, and is the word "strong", we'll + generate strong (Sophie Germain) primes. + */ + if (argc > 3 && strcmp(argv[3], "strong") == 0) + g_strong = 1; + + /* testval - candidate being tested; nTries - number tried so far */ + if ((res = mp_init(&testval)) != MP_OKAY) { + fprintf(stderr, "%s: error: %s\n", argv[0], mp_strerror(res)); + return 1; + } + + if (g_strong) { + printf("Requested %d strong prime value(s) of %d bits.\n", + ngen, bits); + } else { + printf("Requested %d prime value(s) of %d bits.\n", ngen, bits); + } + + rawlen = (bits / CHAR_BIT) + ((bits % CHAR_BIT) ? 1 : 0) + 1; + + if ((raw = calloc(rawlen, sizeof(unsigned char))) == NULL) { + fprintf(stderr, "%s: out of memory, sorry.\n", argv[0]); + return 1; + } + + /* This loop is one for each prime we need to generate */ + for (jx = 0; jx < ngen; jx++) { + + raw[0] = 0; /* sign is positive */ + + /* Pack the initializer with random bytes */ + for (ix = 1; ix < rawlen; ix++) + raw[ix] = (rand() * rand()) & UCHAR_MAX; + + raw[1] |= 0x80; /* set high-order bit of test value */ + raw[rawlen - 1] |= 1; /* set low-order bit of test value */ + + /* Make an mp_int out of the initializer */ + mp_read_raw(&testval, (char *)raw, rawlen); + + /* Initialize candidate counter */ + nTries = 0; + + start = clock(); /* time generation for this prime */ + do { + res = mpp_make_prime(&testval, bits, g_strong, &nTries); + if (res != MP_NO) + break; + /* This code works whether digits are 16 or 32 bits */ + res = mp_add_d(&testval, 32 * 1024, &testval); + res = mp_add_d(&testval, 32 * 1024, &testval); + FPUTC(',', stderr); + } while (1); + end = clock(); + + if (res != MP_YES) { + break; + } + FPUTC('\n', stderr); + puts("The following value is probably prime:"); + outlen = mp_radix_size(&testval, 10); + out = calloc(outlen, sizeof(unsigned char)); + mp_toradix(&testval, (char *)out, 10); + printf("10: %s\n", out); + mp_toradix(&testval, (char *)out, 16); + printf("16: %s\n\n", out); + free(out); + + printf("Number of candidates tried: %lu\n", nTries); + printf("This computation took %ld clock ticks (%.2f seconds)\n", + (end - start), ((double)(end - start) / CLOCKS_PER_SEC)); + + FPUTC('\n', stderr); + } /* end of loop to generate all requested primes */ + + if (res != MP_OKAY) + fprintf(stderr, "%s: error: %s\n", argv[0], mp_strerror(res)); + + free(raw); + mp_clear(&testval); + + return 0; +} diff --git a/security/nss/lib/freebl/mpi/utils/prng.c b/security/nss/lib/freebl/mpi/utils/prng.c new file mode 100644 index 000000000..38748d18e --- /dev/null +++ b/security/nss/lib/freebl/mpi/utils/prng.c @@ -0,0 +1,57 @@ +/* + * prng.c + * + * Command-line pseudo-random number generator + * + * This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ + +#include <stdio.h> +#include <stdlib.h> +#include <limits.h> +#include <time.h> + +#ifdef __OS2__ +#include <types.h> +#include <process.h> +#else +#include <unistd.h> +#endif + +#include "bbs_rand.h" + +int +main(int argc, char *argv[]) +{ + unsigned char *seed; + unsigned int ix, num = 1; + pid_t pid; + + if (argc > 1) { + num = atoi(argv[1]); + if (num <= 0) + num = 1; + } + + pid = getpid(); + srand(time(NULL) * (unsigned int)pid); + + /* Not a perfect seed, but not bad */ + seed = malloc(bbs_seed_size); + for (ix = 0; ix < bbs_seed_size; ix++) { + seed[ix] = rand() % UCHAR_MAX; + } + + bbs_srand(seed, bbs_seed_size); + memset(seed, 0, bbs_seed_size); + free(seed); + + while (num-- > 0) { + ix = bbs_rand(); + + printf("%u\n", ix); + } + + return 0; +} diff --git a/security/nss/lib/freebl/mpi/utils/ptab.pl b/security/nss/lib/freebl/mpi/utils/ptab.pl new file mode 100755 index 000000000..ef2e565be --- /dev/null +++ b/security/nss/lib/freebl/mpi/utils/ptab.pl @@ -0,0 +1,26 @@ +#!/usr/bin/perl + +# This Source Code Form is subject to the terms of the Mozilla Public +# License, v. 2.0. If a copy of the MPL was not distributed with this +# file, You can obtain one at http://mozilla.org/MPL/2.0/. + +while(<>) { + chomp; + push(@primes, $_); +} + +printf("mp_size prime_tab_size = %d;\n", ($#primes + 1)); +print "mp_digit prime_tab[] = {\n"; + +print "\t"; +$last = pop(@primes); +foreach $prime (sort {$a<=>$b} @primes) { + printf("0x%04X, ", $prime); + $brk = ($brk + 1) % 8; + print "\n\t" if(!$brk); +} +printf("0x%04X", $last); +print "\n" if($brk); +print "};\n\n"; + +exit 0; diff --git a/security/nss/lib/freebl/mpi/utils/sieve.c b/security/nss/lib/freebl/mpi/utils/sieve.c new file mode 100644 index 000000000..57768af9e --- /dev/null +++ b/security/nss/lib/freebl/mpi/utils/sieve.c @@ -0,0 +1,243 @@ +/* + * sieve.c + * + * Finds prime numbers using the Sieve of Eratosthenes + * + * This implementation uses a bitmap to represent all odd integers in a + * given range. We iterate over this bitmap, crossing off the + * multiples of each prime we find. At the end, all the remaining set + * bits correspond to prime integers. + * + * Here, we make two passes -- once we have generated a sieve-ful of + * primes, we copy them out, reset the sieve using the highest + * generated prime from the first pass as a base. Then we cross out + * all the multiples of all the primes we found the first time through, + * and re-sieve. In this way, we get double use of the memory we + * allocated for the sieve the first time though. Since we also + * implicitly ignore multiples of 2, this amounts to 4 times the + * values. + * + * This could (and probably will) be generalized to re-use the sieve a + * few more times. + * + * This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ + +#include <stdio.h> +#include <stdlib.h> +#include <limits.h> + +typedef unsigned char byte; + +typedef struct { + int size; + byte *bits; + long base; + int next; + int nbits; +} sieve; + +void sieve_init(sieve *sp, long base, int nbits); +void sieve_grow(sieve *sp, int nbits); +long sieve_next(sieve *sp); +void sieve_reset(sieve *sp, long base); +void sieve_cross(sieve *sp, long val); +void sieve_clear(sieve *sp); + +#define S_ISSET(S, B) (((S)->bits[(B) / CHAR_BIT] >> ((B) % CHAR_BIT)) & 1) +#define S_SET(S, B) ((S)->bits[(B) / CHAR_BIT] |= (1 << ((B) % CHAR_BIT))) +#define S_CLR(S, B) ((S)->bits[(B) / CHAR_BIT] &= ~(1 << ((B) % CHAR_BIT))) +#define S_VAL(S, B) ((S)->base + (2 * (B))) +#define S_BIT(S, V) (((V) - ((S)->base)) / 2) + +int +main(int argc, char *argv[]) +{ + sieve s; + long pr, *p; + int c, ix, cur = 0; + + if (argc < 2) { + fprintf(stderr, "Usage: %s <width>\n", argv[0]); + return 1; + } + + c = atoi(argv[1]); + if (c < 0) + c = -c; + + fprintf(stderr, "%s: sieving to %d positions\n", argv[0], c); + + sieve_init(&s, 3, c); + + c = 0; + while ((pr = sieve_next(&s)) > 0) { + ++c; + } + + p = calloc(c, sizeof(long)); + if (!p) { + fprintf(stderr, "%s: out of memory after first half\n", argv[0]); + sieve_clear(&s); + exit(1); + } + + fprintf(stderr, "%s: half done ... \n", argv[0]); + + for (ix = 0; ix < s.nbits; ix++) { + if (S_ISSET(&s, ix)) { + p[cur] = S_VAL(&s, ix); + printf("%ld\n", p[cur]); + ++cur; + } + } + + sieve_reset(&s, p[cur - 1]); + fprintf(stderr, "%s: crossing off %d found primes ... \n", argv[0], cur); + for (ix = 0; ix < cur; ix++) { + sieve_cross(&s, p[ix]); + if (!(ix % 1000)) + fputc('.', stderr); + } + fputc('\n', stderr); + + free(p); + + fprintf(stderr, "%s: sieving again from %ld ... \n", argv[0], p[cur - 1]); + c = 0; + while ((pr = sieve_next(&s)) > 0) { + ++c; + } + + fprintf(stderr, "%s: done!\n", argv[0]); + for (ix = 0; ix < s.nbits; ix++) { + if (S_ISSET(&s, ix)) { + printf("%ld\n", S_VAL(&s, ix)); + } + } + + sieve_clear(&s); + + return 0; +} + +void +sieve_init(sieve *sp, long base, int nbits) +{ + sp->size = (nbits / CHAR_BIT); + + if (nbits % CHAR_BIT) + ++sp->size; + + sp->bits = calloc(sp->size, sizeof(byte)); + memset(sp->bits, UCHAR_MAX, sp->size); + if (!(base & 1)) + ++base; + sp->base = base; + + sp->next = 0; + sp->nbits = sp->size * CHAR_BIT; +} + +void +sieve_grow(sieve *sp, int nbits) +{ + int ns = (nbits / CHAR_BIT); + + if (nbits % CHAR_BIT) + ++ns; + + if (ns > sp->size) { + byte *tmp; + int ix; + + tmp = calloc(ns, sizeof(byte)); + if (tmp == NULL) { + fprintf(stderr, "Error: out of memory in sieve_grow\n"); + return; + } + + memcpy(tmp, sp->bits, sp->size); + for (ix = sp->size; ix < ns; ix++) { + tmp[ix] = UCHAR_MAX; + } + + free(sp->bits); + sp->bits = tmp; + sp->size = ns; + + sp->nbits = sp->size * CHAR_BIT; + } +} + +long +sieve_next(sieve *sp) +{ + long out; + int ix = 0; + long val; + + if (sp->next > sp->nbits) + return -1; + + out = S_VAL(sp, sp->next); +#ifdef DEBUG + fprintf(stderr, "Sieving %ld\n", out); +#endif + + /* Sieve out all multiples of the current prime */ + val = out; + while (ix < sp->nbits) { + val += out; + ix = S_BIT(sp, val); + if ((val & 1) && ix < sp->nbits) { /* && S_ISSET(sp, ix)) { */ + S_CLR(sp, ix); +#ifdef DEBUG + fprintf(stderr, "Crossing out %ld (bit %d)\n", val, ix); +#endif + } + } + + /* Scan ahead to the next prime */ + ++sp->next; + while (sp->next < sp->nbits && !S_ISSET(sp, sp->next)) + ++sp->next; + + return out; +} + +void +sieve_cross(sieve *sp, long val) +{ + int ix = 0; + long cur = val; + + while (cur < sp->base) + cur += val; + + ix = S_BIT(sp, cur); + while (ix < sp->nbits) { + if (cur & 1) + S_CLR(sp, ix); + cur += val; + ix = S_BIT(sp, cur); + } +} + +void +sieve_reset(sieve *sp, long base) +{ + memset(sp->bits, UCHAR_MAX, sp->size); + sp->base = base; + sp->next = 0; +} + +void +sieve_clear(sieve *sp) +{ + if (sp->bits) + free(sp->bits); + + sp->bits = NULL; +} |