readme

来自「支持SSL v2/v3, TLS, PKCS #5, PKCS #7, PKCS」· 代码 · 共 796 行 · 第 1/3 页

                  which is moderately useful for debugging.  This
                  implicitly includes <stdio.h>.

MP_MODARITH     - Define true to include the modular arithmetic
                  functions.  If you don't need modular arithmetic
                  in your application, you can set this to zero to
                  leave out all the modular routines.

MP_NUMTH        - Define true to include number theoretic functions
                  such as mp_gcd(), mp_lcm(), and mp_invmod().

MP_LOGTAB       - If true, the file "logtab.h" is included, which
                  is basically a static table of base 2 logarithms.
                  These are used to compute how big the buffers for
                  radix conversion need to be.  If you set this false,
                  the library includes <math.h> and uses log().  This
                  typically forces you to link against math libraries.

MP_MEMSET       - If true, use memset() to zero buffers.  If you run
                  into weird alignment related bugs, set this to zero
                  and an explicit loop will be used.

MP_MEMCPY       - If true, use memcpy() to copy buffers.  If you run
                  into weird alignment bugs, set this to zero and an
                  explicit loop will be used.

MP_CRYPTO       - If true, whenever arrays of digits are free'd, they
                  are zeroed first.  This is useful if you're using
                  the library in a cryptographic environment; however,
                  it does add overhead to each free operation.  For
                  performance, if you don't care about zeroing your
                  buffers, set this to false.

MP_ARGCHK       - Set to 0, 1, or 2.  This defines how the argument
                  checking macro, ARGCHK(), gets expanded.  If this 
                  is set to zero, ARGCHK() expands to nothing; no 
                  argument checks are performed.  If this is 1, the
                  ARGCHK() macro expands to code that returns MP_BADARG
                  or similar at runtime.  If it is 2, ARGCHK() expands 
                  to an assert() call that aborts the program on a 
                  bad input.

MP_DEBUG        - Turns on debugging output.  This is probably not at
                  all useful unless you are debugging the library.  It
                  tends to spit out a LOT of output.

MP_DEFPREC      - The default precision of a newly-created mp_int, in
                  digits.  The precision can be changed at runtime by
                  the mp_set_prec() function, but this is its initial
                  value.

MP_SQUARE       - If this is set to a nonzero value, the mp_sqr() 
                  function will use an alternate algorithm that takes
                  advantage of the redundant inner product computation
                  when both multiplicands are identical.  Unfortunately,
                  with some compilers this is actually SLOWER than just
                  calling mp_mul() with the same argument twice.  So
                  if you set MP_SQUARE to zero, mp_sqr() will be expan-
                  ded into a call to mp_mul().  This applies to all 
                  the uses of mp_sqr(), including mp_sqrmod() and the
                  internal calls to s_mp_sqr() inside mpi.c

                  The program 'mulsqr' (mulsqr.c) can be used to test
                  which works best for your configuration.  Set up the
                  CC and CFLAGS variables in the Makefile, then type:

                        make mulsqr

                  Invoke it with arguments similar to the following:

                        mulsqr 25000 1024

                  That is, 25000 products computed on 1024-bit values.
                  The output will compare the two timings, and recommend
                  a setting for MP_SQUARE.  It is off by default.

If you would like to use the mp_print() function (see above), be sure
to define MP_IOFUNC in mpi-config.h.  Many of the test drivers in the
'tests' subdirectory expect this to be defined (although the test
driver 'mpi-test' doesn't need it)

The Makefile which comes with the library should take care of building
the library for you, if you have set the CC and CFLAGS variables at
the top of the file appropriately.  By default, they are set up to
use the GNU C compiler:

CC=gcc
CFLAGS=-ansi -pedantic -Wall -O2

If all goes well, the library should compile without warnings using
this combination.  You should, of course, make whatever adjustments
you find necessary.  

The MPI library distribution comes with several additional programs
which are intended to demonstrate the use of the library, and provide
a framework for testing it.  There are a handful of test driver
programs, in the files named 'mptest-X.c', where X is a digit.  Also,
there are some simple command-line utilities (in the 'utils'
directory) for manipulating large numbers.  These include:

basecvt.c       A radix-conversion program, supporting bases from
                2 to 64 inclusive.

bbsrand.c       A BBS (quadratic residue) pseudo-random number 
                generator.  The file 'bbsrand.c' is just the driver
                for the program; the real code lives in the files
                'bbs_rand.h' and 'bbs_rand.c'

dec2hex.c       Converts decimal to hexadecimal

gcd.c           Computes the greatest common divisor of two values.
                If invoked as 'xgcd', also computes constants x and
                y such that (a, b) = ax + by, in accordance with
                Bezout's identity.

hex2dec.c       Converts hexadecimal to decimal

invmod.c        Computes modular inverses

isprime.c       Performs the Rabin-Miller probabilistic primality
                test on a number.  Values which fail this test are
                definitely composite, and those which pass are very
                likely to be prime (although there are no guarantees)

lap.c           Computes the order (least annihilating power) of
                a value v modulo m.  Very dumb algorithm.

primegen.c      Generates large (probable) primes.

prng.c          A pseudo-random number generator based on the
                BBS generator code in 'bbs_rand.c'

sieve.c         Implements the Sieve of Eratosthenes, using a big
                bitmap, to generate a list of prime numbers.

fact.c          Computes the factorial of an arbitrary precision
                integer (iterative).

exptmod.c       Computes arbitrary precision modular exponentiation
                from the command line (exptmod a b m -> a^b (mod m))

Most of these can be built from the Makefile that comes with the
library.  Try 'make tools', if your environment supports it.  (If you
are compiling on a Macintosh, I'm afraid you'll have to build them by
hand -- fortunately, this is not difficult -- the library itself
should compile just fine under Metrowerks CodeWarrior).


Testing the Library
-------------------

Automatic test vectors are included, in the form of a program called
'mpi-test'.  To build this program and run all the tests, simply
invoke the shell script 'all-tests'.  If all the tests pass, you
should see a message:

        All tests passed

If something went wrong, you'll get:

        One or more tests failed.

If this happens, scan back through the preceding lines, to see which
test failed.  Any failure indicates a bug in the library, which needs
to be fixed before it will give accurate results.  If you get any such
thing, please let me know, and I'll try to fix it.  Please let me know
what platform and compiler you were using, as well as which test
failed.  If a reason for failure was given, please send me that text
as well.

If you're on a system such as the Macintosh, where the standard Unix
build tools don't work, you can build the 'mpi-test' program manually,
and run it by hand.  This is tedious and obnoxious, sorry.

Further manual testing can be performed by building the manual testing
programs, whose source is found in the 'tests' subdirectory.  Each
test is in a source file called 'mptest-X.c'.  The Makefile contains a
target to build all of them at once:

        make tests

Read the comments at the top of each source file to see what the
driver is supposed to test.  You probably don't need to do this; these
programs were only written to help me as I was developing the library.

The relevant files are:

mpi-test.c              The source for the test driver

make-test-arrays        A Perl script to generate some of the internal
                        data structures used by mpi-test.c

test-arrays.txt         The source file for make-test-arrays

all-tests               A Bourne shell script which runs all the
                        tests in the mpi-test suite

Running 'make mpi-test' should build the mpi-test program.  If you
cannot use make, here is what needs to be done:

(1) Use 'make-test-arrays' to generate the file 'test-info.c' from
    the 'test-arrays.txt' file.  Since Perl can be found everywhere,
    even on the Macintosh, this should be no trouble.  Under Unix, 
    this looks like:

        make-test-arrays test-arrays.txt > test-info.c

(2) Build the MPI library:

        gcc -ansi -pedantic -Wall -c mpi.c

(3) Build the mpi-test program:

        gcc -ansi -pedantic -Wall -o mpi-test mpi.o mpi-test.c

When you've got mpi-test, you can use 'all-tests' to run all the tests
made available by mpi-test.  If any of them fail, there should be a
diagnostic indicating what went wrong.  These are fairly high-level
diagnostics, and won't really help you debug the problem; they're
simply intended to help you isolate which function caused the problem.
If you encounter a problem of this sort, feel free to e-mail me, and I
will certainly attempt to help you debug it.

Note:   Several of the tests hard-wired into 'mpi-test' operate under
----    the assumption that you are using at least a 16-bit mp_digit 
        type.  If that is not true, several tests might fail, because 
        of range problems with the maximum digit value.

        If you are using an 8-bit digit, you will also need to 
        modify the code for mp_read_raw(), which assumes that
        multiplication by 256 can be done with mp_mul_d(), a
        fact that fails when DIGIT_MAX is 255.  You can replace
        the call with s_mp_lshd(), which will give you the same
        effect, and without doing as much work. :)

Acknowledgements:
----------------

The algorithms used in this library were drawn primarily from Volume
2 of Donald Knuth's magnum opus, _The Art of Computer Programming_, 
"Semi-Numerical Methods".  Barrett's algorithm for modular reduction
came from Menezes, Oorschot, and Vanstone's _Handbook of Applied
Cryptography_, Chapter 14.

Thanks are due to Tom St. Denis, for finding an obnoxious sign-related
bug in mp_read_raw() that made things break on platforms which use
signed chars.

About the Author
----------------

This software was written by Michael J. Fromberger.  You can contact
the author as follows:

E-mail:   <[e-mail]>

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:  16-Jan-2000