diff options
Diffstat (limited to 'security/nss/lib/freebl/mpi/utils/README')
| -rw-r--r-- | security/nss/lib/freebl/mpi/utils/README | 239 |
1 files changed, 239 insertions, 0 deletions
diff --git a/security/nss/lib/freebl/mpi/utils/README b/security/nss/lib/freebl/mpi/utils/README new file mode 100644 index 000000000..86887bf81 --- /dev/null +++ b/security/nss/lib/freebl/mpi/utils/README @@ -0,0 +1,239 @@ +The contents of this file are subject to the Mozilla Public +License Version 1.1 (the "License"); you may not use this file +except in compliance with the License. You may obtain a copy of +the License at http://www.mozilla.org/MPL/ + +Software distributed under the License is distributed on an "AS +IS" basis, WITHOUT WARRANTY OF ANY KIND, either express or +implied. See the License for the specific language governing +rights and limitations under the License. + +The Original Code is the MPI Arbitrary Precision Integer Arithmetic +library. + +The Initial Developer of the Original Code is +Michael J. Fromberger <sting@linguist.dartmouth.edu> + +Portions created by Michael J. Fromberger are +Copyright (C) 1998, 2000 Michael J. Fromberger. All Rights Reserved. + +Contributor(s): + +Alternatively, the contents of this file may be used under the +terms of the GNU General Public License Version 2 or later (the +"GPL"), in which case the provisions of the GPL are applicable +instead of those above. If you wish to allow use of your +version of this file only under the terms of the GPL and not to +allow others to use your version of this file under the MPL, +indicate your decision by deleting the provisions above and +replace them with the notice and other provisions required by +the GPL. If you do not delete the provisions above, a recipient +may use your version of this file under either the MPL or the +GPL. + + + +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 + +Last updated: $Id$ |