← Back to branch summary

~ubuntu-branches/ubuntu/lucid/seamonkey/lucid-security

« back to all changes in this revision

Viewing changes to security/nss-fips/lib/freebl/mpi/utils/README

  • Committer: Bazaar Package Importer
  • Author(s): Fabien Tassin
  • Date: 2008-07-29 21:29:02 UTC
  • mfrom: (1.1.4 upstream)
  • Revision ID: james.westby@ubuntu.com-20080729212902-spm9kpvchp9udwbw
Tags: 1.1.11+nobinonly-0ubuntu1
https://launchpad.net/bugs/218534
* New security upstream release: 1.1.11 (LP: #218534)
  Fixes USN-602-1, USN-619-1, USN-623-1 and USN-629-1
* Refresh diverged patch:
  - update debian/patches/80_security_build.patch
* Fix FTBFS with missing -lfontconfig
  - add debian/patches/11_fix_ftbfs_with_fontconfig.patch
  - update debian/patches/series
* Build with default gcc (hardy: 4.2, intrepid: 4.3)
  - update debian/rules
  - update debian/control

Show diffs side-by-side

added added

removed removed

Lines of Context:
security/nss-fips/lib/freebl/mpi/utils/README
 
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
 
240
 
 
241
Last updated:  $Id: README,v 1.3 2005/02/02 22:28:23 gerv%gerv.net Exp $