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