readme

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

mp_div_2d(a, d, q, r)   - computes q = a / 2^d, r = a % 2^d
mp_expt(a, b, c)        - computes c = a ** b
mp_2expt(a, k)          - computes a = 2^k
mp_sqrt(a, c)           - computes c = floor(sqrt(a))

The mp_div_2d() function efficiently computes division by powers of
two.  Either the q or r parameter may be NULL, in which case that
portion of the computation will be discarded.

The algorithms used for some of the computations here are described in
the following files which are included with this distribution:

mul.txt         Describes the multiplication algorithm
div.txt         Describes the division algorithm
expt.txt        Describes the exponentiation algorithm
sqrt.txt        Describes the square-root algorithm
square.txt      Describes the squaring algorithm

There are single-digit versions of most of these routines, as well.
In the following prototypes, 'd' is a single mp_digit:

mp_add_d(a, d, c)       - computes c = a + d
mp_sub_d(a, d, c)       - computes c = a - d
mp_mul_d(a, d, c)       - computes c = a * d
mp_mul_2(a, c)          - computes c = a * 2
mp_div_d(a, d, q, r)    - computes q, r such that a = bq + r
mp_div_2(a, c)          - computes c = a / 2
mp_expt_d(a, d, c)      - computes c = a ** d

The mp_mul_2() and mp_div_2() functions take advantage of the internal
representation of an mp_int to do multiplication by two more quickly
than mp_mul_d() would.  Other basic functions of an arithmetic variety
include:

mp_zero(a)              - assign 0 to a
mp_neg(a, c)            - negate a: c = -a
mp_abs(a, c)            - absolute value: c = |a|


Comparisons
-----------

Several comparison functions are provided.  Each of these, unless
otherwise specified, returns zero if the comparands are equal, < 0 if
the first is less than the second, and > 0 if the first is greater
than the second:

mp_cmp_z(a)             - compare a <=> 0
mp_cmp_d(a, d)          - compare a <=> d, d is a single digit
mp_cmp(a, b)            - compare a <=> b
mp_cmp_mag(a, b)        - compare |a| <=> |b|
mp_cmp_int(a, z)        - compare a <=> z, z is a signed long integer
mp_isodd(a)             - return nonzero if odd, zero otherwise
mp_iseven(a)            - return nonzero if even, zero otherwise


Modular Arithmetic
------------------

Modular variations of the basic arithmetic functions are also
supported.  These are available if the MP_MODARITH parameter in
mpi-config.h is turned on (it is by default).  The modular arithmetic
functions are:

mp_mod(a, m, c)         - compute c = a (mod m), 0 <= c < m
mp_mod_d(a, d, c)       - compute c = a (mod d), 0 <= c < d (see below)
mp_addmod(a, b, m, c)   - compute c = (a + b) mod m
mp_submod(a, b, m, c)   - compute c = (a - b) mod m
mp_mulmod(a, b, m, c)   - compute c = (a * b) mod m
mp_sqrmod(a, m, c)      - compute c = (a * a) mod m
mp_exptmod(a, b, m, c)  - compute c = (a ** b) mod m
mp_exptmod_d(a, d, m, c)- compute c = (a ** d) mod m

The mp_sqr() function squares its input argument.  A call to mp_sqr(a,
c) is identical in meaning to mp_mul(a, a, c); however, if the
MP_SQUARE variable is set true in mpi-config.h (see below), then it
will be implemented with a different algorithm, that is supposed to
take advantage of the redundant computation that takes place during
squaring.  Unfortunately, some compilers result in worse performance
on this code, so you can change the behaviour at will.  There is a
utility program "mulsqr.c" that lets you test which does better on
your system.

The mp_sqrmod() function is analogous to the mp_sqr() function; it
uses the mp_sqr() function rather than mp_mul(), and then performs the
modular reduction.  This probably won't help much unless you are doing
a lot of them.

See the file 'square.txt' for a synopsis of the algorithm used.

Note:   The mp_mod_d() function computes a modular reduction around
----    a single digit d.  The result is a single digit c.

Because an inverse is defined for a (mod m) if and only if (a, m) = 1
(that is, if a and m are relatively prime), mp_invmod() may not be
able to compute an inverse for the arguments.  In this case, it
returns the value MP_UNDEF, and does not modify c.  If an inverse is
defined, however, it returns MP_OKAY, and sets c to the value of the
inverse (mod m).

See the file 'redux.txt' for a description of the modular reduction
algorithm used by mp_exptmod().


Greatest Common Divisor
-----------------------

If The greates common divisor of two values can be found using one of the
following functions:

mp_gcd(a, b, c)         - compute c = (a, b) using binary algorithm
mp_lcm(a, b, c)         - compute c = [a, b] = ab / (a, b)
mp_xgcd(a, b, g, x, y)  - compute g, x, y so that ax + by = g = (a, b)

Also provided is a function to compute modular inverses, if they
exist:

mp_invmod(a, m, c)      - compute c = a^-1 (mod m), if it exists

The function mp_xgcd() computes the greatest common divisor, and also
returns values of x and y satisfying Bezout's identity.  This is used
by mp_invmod() to find modular inverses.  However, if you do not need
these values, you will find that mp_gcd() is MUCH more efficient,
since it doesn't need all the intermediate values that mp_xgcd()
requires in order to compute x and y. 

The mp_gcd() (and mp_xgcd()) functions use the binary (extended) GCD
algorithm due to Josef Stein.


Input & Output Functions
------------------------

The following basic I/O routines are provided.  These are present at
all times:

mp_read_radix(mp, str, r)  - convert a string in radix r to an mp_int
mp_read_raw(mp, s, len)    - convert a string of bytes to an mp_int
mp_radix_size(mp, r)       - return length of buffer needed by mp_toradix()
mp_raw_size(mp)            - return length of buffer needed by mp_toraw()
mp_toradix(mp, str, r)     - convert an mp_int to a string of radix r 
                             digits
mp_toraw(mp, str)          - convert an mp_int to a string of bytes
mp_tovalue(ch, r)          - convert ch to its value when taken as
                             a radix r digit, or -1 if invalid
mp_strerror(err)           - get a string describing mp_err value 'err'

If you compile the MPI library with MP_IOFUNC defined, you will also
have access to the following additional I/O function:

mp_print(mp, ofp)       - print an mp_int as text to output stream ofp

Note that mp_radix_size() returns a size in bytes guaranteed to be AT
LEAST big enough for the digits output by mp_toradix().  Because it
uses an approximation technique to figure out how many digits will be
needed, it may return a figure which is larger than necessary.  Thus,
the caller should not rely on the value to determine how many bytes
will actually be written by mp_toradix().  The string mp_toradix()
creates will be NUL terminated, so the standard C library function
strlen() should be able to ascertain this for you, if you need it.

The mp_read_radix() and mp_toradix() functions support bases from 2 to
64 inclusive.  If you require more general radix conversion facilities
than this, you will need to write them yourself (that's why mp_div_d()
is provided, after all).

Note:   mp_read_radix() will accept as digits either capital or 
----    lower-case letters.  However, the current implementation of
        mp_toradix() only outputs upper-case letters, when writing
        bases betwee 10 and 36.  The underlying code supports using
        lower-case letters, but the interface stub does not have a
        selector for it.  You can add one yourself if you think it
        is worthwhile -- I do not.  Bases from 36 to 64 use lower-
        case letters as distinct from upper-case.  Bases 63 and
        64 use the characters '+' and '/' as digits.

        Note also that compiling with MP_IOFUNC defined will cause
        inclusion of <stdio.h>, so if you are trying to write code
        which does not depend on the standard C library, you will
        probably want to avoid this option.  This is needed because
        the mp_print() function takes a standard library FILE * as
        one of its parameters, and uses the fprintf() function.

The mp_toraw() function converts the integer to a sequence of bytes,
in big-endian ordering (most-significant byte first).  Assuming your
bytes are 8 bits wide, this corresponds to base 256.  The sign is
encoded as a single leading byte, whose value is 0 for zero or
positive values, or 1 for negative values.  The mp_read_raw() function
reverses this process -- it takes a buffer of bytes, interprets the
first as a sign indicator (0 = zero/positive, nonzero = negative), and
the rest as a sequence of 1-byte digits in big-endian ordering.

The mp_raw_size() function returns the exact number of bytes required
to store the given integer in "raw" format (as described in the
previous paragraph).  Zero is returned in case of error; a valid
integer will require at least three bytes of storage.

In previous versions of the MPI library, an "external representation
format" was supported.  This was removed, however, because I found I
was never using it, it was not as portable as I would have liked, and
I decided it was a waste of space.


Other Functions
---------------

The files 'mpprime.h' and 'mpprime.c' define some routines which are
useful for divisibility testing and probabilistic primality testing.
The routines defined are:

mpp_divis(a, b)          - is a divisible by b?
mpp_divis_d(a, d)        - is a divisible by digit d?
mpp_random(a)            - set a to random value at current precision
mpp_random_size(a, prec) - set a to random value at given precision

Note:  The mpp_random() and mpp_random_size() functions use the C
----   library's rand() function to generate random values.  It is
       up to the caller to seed this generator before it is called.
       These functions are not suitable for generating quantities
       requiring cryptographic-quality randomness; they are intended
       primarily for use in primality testing.

       Note too that the MPI library does not call srand(), so your
       application should do this, if you ever want the sequence
       to change.

mpp_divis_vector(a, v, s, w)  - is a divisible by any of the s digits
                                in v?  If so, let w be the index of 
                                that digit

mpp_divis_primes(a, np)       - is a divisible by any of the first np
                                primes?  If so, set np to the prime 
                                which divided a.

mpp_fermat(a, d)              - test if w^a = w (mod a).  If so, 
                                returns MP_YES, otherwise MP_NO.

mpp_pprime(a, nt)             - perform nt iterations of the Rabin-
                                Miller probabilistic primality test
                                on a.  Returns MP_YES if all tests
                                passed, or MP_NO if any test fails.

The mpp_fermat() function works based on Fermat's little theorem, a
consequence of which is that if p is a prime, and (w, p) = 1, then:

        w^p = w (mod p)

Put another way, if w^p != w (mod p), then p is not prime.  The test
is expensive to compute, but it helps to quickly eliminate an enormous
class of composite numbers prior to Rabin-Miller testing.

Building the Library
--------------------

The MPI library is designed to be as self-contained as possible.  You
should be able to compile it with your favourite ANSI C compiler, and
link it into your program directly.  If you are on a Unix system using
the GNU C compiler (gcc), the following should work:

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

The file 'mpi-config.h' defines several configurable parameters for
the library, which you can adjust to suit your application.  At the
time of this writing, the available options are:

MP_IOFUNC       - Define true to include the mp_print() function,