1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/security/nss/lib/freebl/mpi/utils/README Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,239 @@
1.4 +***** BEGIN LICENSE BLOCK *****
1.5 +Version: MPL 1.1/GPL 2.0/LGPL 2.1
1.6 +
1.7 +The contents of this file are subject to the Mozilla Public License Version
1.8 +1.1 (the "License"); you may not use this file except in compliance with
1.9 +the License. You may obtain a copy of the License at
1.10 +http://www.mozilla.org/MPL/
1.11 +
1.12 +Software distributed under the License is distributed on an "AS IS" basis,
1.13 +WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
1.14 +for the specific language governing rights and limitations under the
1.15 +License.
1.16 +
1.17 +The Original Code is the MPI Arbitrary Precision Integer Arithmetic
1.18 +library.
1.19 +
1.20 +The Initial Developer of the Original Code is
1.21 +Michael J. Fromberger <sting@linguist.dartmouth.edu>
1.22 +Portions created by the Initial Developer are Copyright (C) 1998, 2000
1.23 +the Initial Developer. All Rights Reserved.
1.24 +
1.25 +Contributor(s):
1.26 +
1.27 +Alternatively, the contents of this file may be used under the terms of
1.28 +either the GNU General Public License Version 2 or later (the "GPL"), or
1.29 +the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
1.30 +in which case the provisions of the GPL or the LGPL are applicable instead
1.31 +of those above. If you wish to allow use of your version of this file only
1.32 +under the terms of either the GPL or the LGPL, and not to allow others to
1.33 +use your version of this file under the terms of the MPL, indicate your
1.34 +decision by deleting the provisions above and replace them with the notice
1.35 +and other provisions required by the GPL or the LGPL. If you do not delete
1.36 +the provisions above, a recipient may use your version of this file under
1.37 +the terms of any one of the MPL, the GPL or the LGPL.
1.38 +
1.39 +***** END LICENSE BLOCK *****
1.40 +
1.41 +Additional MPI utilities
1.42 +------------------------
1.43 +
1.44 +The files 'mpprime.h' and 'mpprime.c' define some useful extensions to
1.45 +the MPI library for dealing with prime numbers (in particular, testing
1.46 +for divisbility, and the Rabin-Miller probabilistic primality test).
1.47 +
1.48 +The files 'mplogic.h' and 'mplogic.c' define extensions to the MPI
1.49 +library for doing bitwise logical operations and shifting.
1.50 +
1.51 +This document assumes you have read the help file for the MPI library
1.52 +and understand its conventions.
1.53 +
1.54 +Divisibility (mpprime.h)
1.55 +------------
1.56 +
1.57 +To test a number for divisibility by another number:
1.58 +
1.59 +mpp_divis(a, b) - test if b|a
1.60 +mpp_divis_d(a, d) - test if d|a
1.61 +
1.62 +Each of these functions returns MP_YES if its initial argument is
1.63 +divisible by its second, or MP_NO if it is not. Other errors may be
1.64 +returned as appropriate (such as MP_RANGE if you try to test for
1.65 +divisibility by zero).
1.66 +
1.67 +Randomness (mpprime.h)
1.68 +----------
1.69 +
1.70 +To generate random data:
1.71 +
1.72 +mpp_random(a) - fill a with random data
1.73 +mpp_random_size(a, p) - fill a with p digits of random data
1.74 +
1.75 +The mpp_random_size() function increases the precision of a to at
1.76 +least p, then fills all those digits randomly. The mp_random()
1.77 +function fills a to its current precision (as determined by the number
1.78 +of significant digits, USED(a))
1.79 +
1.80 +Note that these functions simply use the C library's rand() function
1.81 +to fill a with random digits up to its precision. This should be
1.82 +adequate for primality testing, but should not be used for
1.83 +cryptographic applications where truly random values are required for
1.84 +security.
1.85 +
1.86 +You should call srand() in your driver program in order to seed the
1.87 +random generator; this function doesn't call it.
1.88 +
1.89 +Primality Testing (mpprime.h)
1.90 +-----------------
1.91 +
1.92 +mpp_divis_vector(a, v, s, w) - is a divisible by any of the s values
1.93 + in v, and if so, w = which.
1.94 +mpp_divis_primes(a, np) - is a divisible by any of the first np primes?
1.95 +mpp_fermat(a, w) - is a pseudoprime with respect to witness w?
1.96 +mpp_pprime(a, nt) - run nt iterations of Rabin-Miller on a.
1.97 +
1.98 +The mpp_divis_vector() function tests a for divisibility by each
1.99 +member of an array of digits. The array is v, the size of that array
1.100 +is s. Returns MP_YES if a is divisible, and stores the index of the
1.101 +offending digit in w. Returns MP_NO if a is not divisible by any of
1.102 +the digits in the array.
1.103 +
1.104 +A small table of primes is compiled into the library (typically the
1.105 +first 128 primes, although you can change this by editing the file
1.106 +'primes.c' before you build). The global variable prime_tab_size
1.107 +contains the number of primes in the table, and the values themselves
1.108 +are in the array prime_tab[], which is an array of mp_digit.
1.109 +
1.110 +The mpp_divis_primes() function is basically just a wrapper around
1.111 +mpp_divis_vector() that uses prime_tab[] as the test vector. The np
1.112 +parameter is a pointer to an mp_digit -- on input, it should specify
1.113 +the number of primes to be tested against. If a is divisible by any
1.114 +of the primes, MP_YES is returned and np is given the prime value that
1.115 +divided a (you can use this if you're factoring, for example).
1.116 +Otherwise, MP_NO is returned and np is untouched.
1.117 +
1.118 +The function mpp_fermat() performs Fermat's test, using w as a
1.119 +witness. This test basically relies on the fact that if a is prime,
1.120 +and w is relatively prime to a, then:
1.121 +
1.122 + w^a = w (mod a)
1.123 +
1.124 +That is,
1.125 +
1.126 + w^(a - 1) = 1 (mod a)
1.127 +
1.128 +The function returns MP_YES if the test passes, MP_NO if it fails. If
1.129 +w is relatively prime to a, and the test fails, a is definitely
1.130 +composite. If w is relatively prime to a and the test passes, then a
1.131 +is either prime, or w is a false witness (the probability of this
1.132 +happening depends on the choice of w and of a ... consult a number
1.133 +theory textbook for more information about this).
1.134 +
1.135 +Note: If (w, a) != 1, the output of this test is meaningless.
1.136 +----
1.137 +
1.138 +The function mpp_pprime() performs the Rabin-Miller probabilistic
1.139 +primality test for nt rounds. If all the tests pass, MP_YES is
1.140 +returned, and a is probably prime. The probability that an answer of
1.141 +MP_YES is incorrect is no greater than 1 in 4^nt, and in fact is
1.142 +usually much less than that (this is a pessimistic estimate). If any
1.143 +test fails, MP_NO is returned, and a is definitely composite.
1.144 +
1.145 +Bruce Schneier recommends at least 5 iterations of this test for most
1.146 +cryptographic applications; Knuth suggests that 25 are reasonable.
1.147 +Run it as many times as you feel are necessary.
1.148 +
1.149 +See the programs 'makeprime.c' and 'isprime.c' for reasonable examples
1.150 +of how to use these functions for primality testing.
1.151 +
1.152 +
1.153 +Bitwise Logic (mplogic.c)
1.154 +-------------
1.155 +
1.156 +The four commonest logical operations are implemented as:
1.157 +
1.158 +mpl_not(a, b) - Compute bitwise (one's) complement, b = ~a
1.159 +
1.160 +mpl_and(a, b, c) - Compute bitwise AND, c = a & b
1.161 +
1.162 +mpl_or(a, b, c) - Compute bitwise OR, c = a | b
1.163 +
1.164 +mpl_xor(a, b, c) - Compute bitwise XOR, c = a ^ b
1.165 +
1.166 +Left and right shifts are available as well. These take a number to
1.167 +shift, a destination, and a shift amount. The shift amount must be a
1.168 +digit value between 0 and DIGIT_BIT inclusive; if it is not, MP_RANGE
1.169 +will be returned and the shift will not happen.
1.170 +
1.171 +mpl_rsh(a, b, d) - Compute logical right shift, b = a >> d
1.172 +
1.173 +mpl_lsh(a, b, d) - Compute logical left shift, b = a << d
1.174 +
1.175 +Since these are logical shifts, they fill with zeroes (the library
1.176 +uses a signed magnitude representation, so there are no sign bits to
1.177 +extend anyway).
1.178 +
1.179 +
1.180 +Command-line Utilities
1.181 +----------------------
1.182 +
1.183 +A handful of interesting command-line utilities are provided. These
1.184 +are:
1.185 +
1.186 +lap.c - Find the order of a mod m. Usage is 'lap <a> <m>'.
1.187 + This uses a dumb algorithm, so don't use it for
1.188 + a really big modulus.
1.189 +
1.190 +invmod.c - Find the inverse of a mod m, if it exists. Usage
1.191 + is 'invmod <a> <m>'
1.192 +
1.193 +sieve.c - A simple bitmap-based implementation of the Sieve
1.194 + of Eratosthenes. Used to generate the table of
1.195 + primes in primes.c. Usage is 'sieve <nbits>'
1.196 +
1.197 +prng.c - Uses the routines in bbs_rand.{h,c} to generate
1.198 + one or more 32-bit pseudo-random integers. This
1.199 + is mainly an example, not intended for use in a
1.200 + cryptographic application (the system time is
1.201 + the only source of entropy used)
1.202 +
1.203 +dec2hex.c - Convert decimal to hexadecimal
1.204 +
1.205 +hex2dec.c - Convert hexadecimal to decimal
1.206 +
1.207 +basecvt.c - General radix conversion tool (supports 2-64)
1.208 +
1.209 +isprime.c - Probabilistically test an integer for primality
1.210 + using the Rabin-Miller pseudoprime test combined
1.211 + with division by small primes.
1.212 +
1.213 +primegen.c - Generate primes at random.
1.214 +
1.215 +exptmod.c - Perform modular exponentiation
1.216 +
1.217 +ptab.pl - A Perl script to munge the output of the sieve
1.218 + program into a compilable C structure.
1.219 +
1.220 +
1.221 +Other Files
1.222 +-----------
1.223 +
1.224 +PRIMES - Some randomly generated numbers which are prime with
1.225 + extremely high probability.
1.226 +
1.227 +README - You're reading me already.
1.228 +
1.229 +
1.230 +About the Author
1.231 +----------------
1.232 +
1.233 +This software was written by Michael J. Fromberger. You can contact
1.234 +the author as follows:
1.235 +
1.236 +E-mail: <sting@linguist.dartmouth.edu>
1.237 +
1.238 +Postal: 8000 Cummings Hall, Thayer School of Engineering
1.239 + Dartmouth College, Hanover, New Hampshire, USA
1.240 +
1.241 +PGP key: http://linguist.dartmouth.edu/~sting/keys/mjf.html
1.242 + 9736 188B 5AFA 23D6 D6AA BE0D 5856 4525 289D 9907
