diff options
Diffstat (limited to 'security/nss/lib/freebl/mpi/utils/README')
| -rw-r--r-- | security/nss/lib/freebl/mpi/utils/README | 206 |
1 files changed, 0 insertions, 206 deletions
diff --git a/security/nss/lib/freebl/mpi/utils/README b/security/nss/lib/freebl/mpi/utils/README deleted file mode 100644 index 61c8e2efa..000000000 --- a/security/nss/lib/freebl/mpi/utils/README +++ /dev/null @@ -1,206 +0,0 @@ -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 |