The Tor Browser / file comparison
comparison: security/nss/lib/freebl/mpi/utils/README
security/nss/lib/freebl/mpi/utils/README
- branch
- TOR_BUG_9701
- changeset 15
- b8a032363ba2
equal
deleted
inserted
replaced
| -1:000000000000 | 0:a08ade0af50b |
|---|---|
| 1 ***** BEGIN LICENSE BLOCK ***** | |
| 2 Version: MPL 1.1/GPL 2.0/LGPL 2.1 | |
| 3 | |
| 4 The contents of this file are subject to the Mozilla Public License Version | |
| 5 1.1 (the "License"); you may not use this file except in compliance with | |
| 6 the License. You may obtain a copy of the License at | |
| 7 http://www.mozilla.org/MPL/ | |
| 8 | |
| 9 Software distributed under the License is distributed on an "AS IS" basis, | |
| 10 WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License | |
| 11 for the specific language governing rights and limitations under the | |
| 12 License. | |
| 13 | |
| 14 The Original Code is the MPI Arbitrary Precision Integer Arithmetic | |
| 15 library. | |
| 16 | |
| 17 The Initial Developer of the Original Code is | |
| 18 Michael J. Fromberger <sting@linguist.dartmouth.edu> | |
| 19 Portions created by the Initial Developer are Copyright (C) 1998, 2000 | |
| 20 the Initial Developer. All Rights Reserved. | |
| 21 | |
| 22 Contributor(s): | |
| 23 | |
| 24 Alternatively, the contents of this file may be used under the terms of | |
| 25 either the GNU General Public License Version 2 or later (the "GPL"), or | |
| 26 the GNU Lesser General Public License Version 2.1 or later (the "LGPL"), | |
| 27 in which case the provisions of the GPL or the LGPL are applicable instead | |
| 28 of those above. If you wish to allow use of your version of this file only | |
| 29 under the terms of either the GPL or the LGPL, and not to allow others to | |
| 30 use your version of this file under the terms of the MPL, indicate your | |
| 31 decision by deleting the provisions above and replace them with the notice | |
| 32 and other provisions required by the GPL or the LGPL. If you do not delete | |
| 33 the provisions above, a recipient may use your version of this file under | |
| 34 the terms of any one of the MPL, the GPL or the LGPL. | |
| 35 | |
| 36 ***** END LICENSE BLOCK ***** | |
| 37 | |
| 38 Additional MPI utilities | |
| 39 ------------------------ | |
| 40 | |
| 41 The files 'mpprime.h' and 'mpprime.c' define some useful extensions to | |
| 42 the MPI library for dealing with prime numbers (in particular, testing | |
| 43 for divisbility, and the Rabin-Miller probabilistic primality test). | |
| 44 | |
| 45 The files 'mplogic.h' and 'mplogic.c' define extensions to the MPI | |
| 46 library for doing bitwise logical operations and shifting. | |
| 47 | |
| 48 This document assumes you have read the help file for the MPI library | |
| 49 and understand its conventions. | |
| 50 | |
| 51 Divisibility (mpprime.h) | |
| 52 ------------ | |
| 53 | |
| 54 To test a number for divisibility by another number: | |
| 55 | |
| 56 mpp_divis(a, b) - test if b|a | |
| 57 mpp_divis_d(a, d) - test if d|a | |
| 58 | |
| 59 Each of these functions returns MP_YES if its initial argument is | |
| 60 divisible by its second, or MP_NO if it is not. Other errors may be | |
| 61 returned as appropriate (such as MP_RANGE if you try to test for | |
| 62 divisibility by zero). | |
| 63 | |
| 64 Randomness (mpprime.h) | |
| 65 ---------- | |
| 66 | |
| 67 To generate random data: | |
| 68 | |
| 69 mpp_random(a) - fill a with random data | |
| 70 mpp_random_size(a, p) - fill a with p digits of random data | |
| 71 | |
| 72 The mpp_random_size() function increases the precision of a to at | |
| 73 least p, then fills all those digits randomly. The mp_random() | |
| 74 function fills a to its current precision (as determined by the number | |
| 75 of significant digits, USED(a)) | |
| 76 | |
| 77 Note that these functions simply use the C library's rand() function | |
| 78 to fill a with random digits up to its precision. This should be | |
| 79 adequate for primality testing, but should not be used for | |
| 80 cryptographic applications where truly random values are required for | |
| 81 security. | |
| 82 | |
| 83 You should call srand() in your driver program in order to seed the | |
| 84 random generator; this function doesn't call it. | |
| 85 | |
| 86 Primality Testing (mpprime.h) | |
| 87 ----------------- | |
| 88 | |
| 89 mpp_divis_vector(a, v, s, w) - is a divisible by any of the s values | |
| 90 in v, and if so, w = which. | |
| 91 mpp_divis_primes(a, np) - is a divisible by any of the first np primes? | |
| 92 mpp_fermat(a, w) - is a pseudoprime with respect to witness w? | |
| 93 mpp_pprime(a, nt) - run nt iterations of Rabin-Miller on a. | |
| 94 | |
| 95 The mpp_divis_vector() function tests a for divisibility by each | |
| 96 member of an array of digits. The array is v, the size of that array | |
| 97 is s. Returns MP_YES if a is divisible, and stores the index of the | |
| 98 offending digit in w. Returns MP_NO if a is not divisible by any of | |
| 99 the digits in the array. | |
| 100 | |
| 101 A small table of primes is compiled into the library (typically the | |
| 102 first 128 primes, although you can change this by editing the file | |
| 103 'primes.c' before you build). The global variable prime_tab_size | |
| 104 contains the number of primes in the table, and the values themselves | |
| 105 are in the array prime_tab[], which is an array of mp_digit. | |
| 106 | |
| 107 The mpp_divis_primes() function is basically just a wrapper around | |
| 108 mpp_divis_vector() that uses prime_tab[] as the test vector. The np | |
| 109 parameter is a pointer to an mp_digit -- on input, it should specify | |
| 110 the number of primes to be tested against. If a is divisible by any | |
| 111 of the primes, MP_YES is returned and np is given the prime value that | |
| 112 divided a (you can use this if you're factoring, for example). | |
| 113 Otherwise, MP_NO is returned and np is untouched. | |
| 114 | |
| 115 The function mpp_fermat() performs Fermat's test, using w as a | |
| 116 witness. This test basically relies on the fact that if a is prime, | |
| 117 and w is relatively prime to a, then: | |
| 118 | |
| 119 w^a = w (mod a) | |
| 120 | |
| 121 That is, | |
| 122 | |
| 123 w^(a - 1) = 1 (mod a) | |
| 124 | |
| 125 The function returns MP_YES if the test passes, MP_NO if it fails. If | |
| 126 w is relatively prime to a, and the test fails, a is definitely | |
| 127 composite. If w is relatively prime to a and the test passes, then a | |
| 128 is either prime, or w is a false witness (the probability of this | |
| 129 happening depends on the choice of w and of a ... consult a number | |
| 130 theory textbook for more information about this). | |
| 131 | |
| 132 Note: If (w, a) != 1, the output of this test is meaningless. | |
| 133 ---- | |
| 134 | |
| 135 The function mpp_pprime() performs the Rabin-Miller probabilistic | |
| 136 primality test for nt rounds. If all the tests pass, MP_YES is | |
| 137 returned, and a is probably prime. The probability that an answer of | |
| 138 MP_YES is incorrect is no greater than 1 in 4^nt, and in fact is | |
| 139 usually much less than that (this is a pessimistic estimate). If any | |
| 140 test fails, MP_NO is returned, and a is definitely composite. | |
| 141 | |
| 142 Bruce Schneier recommends at least 5 iterations of this test for most | |
| 143 cryptographic applications; Knuth suggests that 25 are reasonable. | |
| 144 Run it as many times as you feel are necessary. | |
| 145 | |
| 146 See the programs 'makeprime.c' and 'isprime.c' for reasonable examples | |
| 147 of how to use these functions for primality testing. | |
| 148 | |
| 149 | |
| 150 Bitwise Logic (mplogic.c) | |
| 151 ------------- | |
| 152 | |
| 153 The four commonest logical operations are implemented as: | |
| 154 | |
| 155 mpl_not(a, b) - Compute bitwise (one's) complement, b = ~a | |
| 156 | |
| 157 mpl_and(a, b, c) - Compute bitwise AND, c = a & b | |
| 158 | |
| 159 mpl_or(a, b, c) - Compute bitwise OR, c = a | b | |
| 160 | |
| 161 mpl_xor(a, b, c) - Compute bitwise XOR, c = a ^ b | |
| 162 | |
| 163 Left and right shifts are available as well. These take a number to | |
| 164 shift, a destination, and a shift amount. The shift amount must be a | |
| 165 digit value between 0 and DIGIT_BIT inclusive; if it is not, MP_RANGE | |
| 166 will be returned and the shift will not happen. | |
| 167 | |
| 168 mpl_rsh(a, b, d) - Compute logical right shift, b = a >> d | |
| 169 | |
| 170 mpl_lsh(a, b, d) - Compute logical left shift, b = a << d | |
| 171 | |
| 172 Since these are logical shifts, they fill with zeroes (the library | |
| 173 uses a signed magnitude representation, so there are no sign bits to | |
| 174 extend anyway). | |
| 175 | |
| 176 | |
| 177 Command-line Utilities | |
| 178 ---------------------- | |
| 179 | |
| 180 A handful of interesting command-line utilities are provided. These | |
| 181 are: | |
| 182 | |
| 183 lap.c - Find the order of a mod m. Usage is 'lap <a> <m>'. | |
| 184 This uses a dumb algorithm, so don't use it for | |
| 185 a really big modulus. | |
| 186 | |
| 187 invmod.c - Find the inverse of a mod m, if it exists. Usage | |
| 188 is 'invmod <a> <m>' | |
| 189 | |
| 190 sieve.c - A simple bitmap-based implementation of the Sieve | |
| 191 of Eratosthenes. Used to generate the table of | |
| 192 primes in primes.c. Usage is 'sieve <nbits>' | |
| 193 | |
| 194 prng.c - Uses the routines in bbs_rand.{h,c} to generate | |
| 195 one or more 32-bit pseudo-random integers. This | |
| 196 is mainly an example, not intended for use in a | |
| 197 cryptographic application (the system time is | |
| 198 the only source of entropy used) | |
| 199 | |
| 200 dec2hex.c - Convert decimal to hexadecimal | |
| 201 | |
| 202 hex2dec.c - Convert hexadecimal to decimal | |
| 203 | |
| 204 basecvt.c - General radix conversion tool (supports 2-64) | |
| 205 | |
| 206 isprime.c - Probabilistically test an integer for primality | |
| 207 using the Rabin-Miller pseudoprime test combined | |
| 208 with division by small primes. | |
| 209 | |
| 210 primegen.c - Generate primes at random. | |
| 211 | |
| 212 exptmod.c - Perform modular exponentiation | |
| 213 | |
| 214 ptab.pl - A Perl script to munge the output of the sieve | |
| 215 program into a compilable C structure. | |
| 216 | |
| 217 | |
| 218 Other Files | |
| 219 ----------- | |
| 220 | |
| 221 PRIMES - Some randomly generated numbers which are prime with | |
| 222 extremely high probability. | |
| 223 | |
| 224 README - You're reading me already. | |
| 225 | |
| 226 | |
| 227 About the Author | |
| 228 ---------------- | |
| 229 | |
| 230 This software was written by Michael J. Fromberger. You can contact | |
| 231 the author as follows: | |
| 232 | |
| 233 E-mail: <sting@linguist.dartmouth.edu> | |
| 234 | |
| 235 Postal: 8000 Cummings Hall, Thayer School of Engineering | |
| 236 Dartmouth College, Hanover, New Hampshire, USA | |
| 237 | |
| 238 PGP key: http://linguist.dartmouth.edu/~sting/keys/mjf.html | |
| 239 9736 188B 5AFA 23D6 D6AA BE0D 5856 4525 289D 9907 |
