readme

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

The contents of this file are subject to the Mozilla Public
License Version 1.1 (the "License"); you may not use this file
except in compliance with the License. You may obtain a copy of
the License at http://www.mozilla.org/MPL/

Software distributed under the License is distributed on an "AS
IS" basis, WITHOUT WARRANTY OF ANY KIND, either express or
implied. See the License for the specific language governing
rights and limitations under the License.

The Original Code is the MPI Arbitrary Precision Integer Arithmetic
library.

The Initial Developer of the Original Code is 
Michael J. Fromberger <[e-mail]>

Portions created by Michael J. Fromberger are 
Copyright (C) 1997, 1998, 1999, 2000 Michael J. Fromberger. 
All Rights Reserved.

Contributor(s):

Alternatively, the contents of this file may be used under the
terms of the GNU General Public License Version 2 or later (the
"GPL"), in which case the provisions of the GPL are applicable
instead of those above.  If you wish to allow use of your
version of this file only under the terms of the GPL and not to
allow others to use your version of this file under the MPL,
indicate your decision by deleting the provisions above and
replace them with the notice and other provisions required by
the GPL.  If you do not delete the provisions above, a recipient
may use your version of this file under either the MPL or the GPL.

About the MPI Library
---------------------

The files 'mpi.h' and 'mpi.c' define a simple, arbitrary precision
signed integer arithmetic package.  The implementation is not the most
efficient possible, but the code is small and should be fairly easily
portable to just about any machine that supports an ANSI C compiler,
as long as it is capable of at least 16-bit arithmetic (but also see
below for more on this).

This library was written with an eye to cryptographic applications;
thus, some care is taken to make sure that temporary values are not
left lying around in memory when they are no longer in use.  This adds
some overhead for zeroing buffers before they are released back into
the free pool; however, it gives you the assurance that there is only
one copy of your important values residing in your process's address
space at a time.  Obviously, it is difficult to guarantee anything, in
a pre-emptive multitasking environment, but this at least helps you
keep a lid on the more obvious ways your data can get spread around in
memory.


Using the Library
-----------------

To use the MPI library in your program, you must include the header:

#include "mpi.h"

This header provides all the type and function declarations you'll
need to use the library.  Almost all the names defined by the library
begin with the prefix 'mp_', so it should be easy to keep them from
clashing with your program's namespace (he says, glibly, knowing full
well there are always pathological cases).

There are a few things you may want to configure about the library.
By default, the MPI library uses an unsigned short for its digit type,
and an unsigned int for its word type.  The word type must be big
enough to contain at least two digits, for the primitive arithmetic to
work out.  On my machine, a short is 2 bytes and an int is 4 bytes --
but if you have 64-bit ints, you might want to use a 4-byte digit and
an 8-byte word.  I have tested the library using 1-byte digits and
2-byte words, as well.  Whatever you choose to do, the things you need
to change are:

(1) The type definitions for mp_digit and mp_word.

(2) The macro DIGIT_FMT which tells mp_print() how to display a
    single digit.  This is just a printf() format string, so you
    can adjust it appropriately.

(3) The macros DIGIT_MAX and MP_WORD_MAX, which specify the 
    largest value expressible in an mp_digit and an mp_word,
    respectively.

Both the mp_digit and mp_word should be UNSIGNED integer types.  The
code relies on having the full positive precision of the type used for
digits and words.

The remaining type definitions should be left alone, for the most
part.  The code in the library does not make any significant
assumptions about the sizes of things, but there is little if any
reason to change the other parameters, so I would recommend you leave
them as you found them.

The library comes with a Perl script, 'types.pl', which will scan your
current Makefile settings, and attempt to find good definitions for
these types.  It relies on a Unix sort of build environment, so it
probably won't work under MacOS or Windows, but it can be convenient
if you're porting to a new flavour of Unix.  Just run 'types.pl' at
the command line, and it will spit out its results to the standard
output.


Conventions
-----------

Most functions in the library return a value of type mp_err.  This
permits the library to communicate success or various kinds of failure
to the calling program.  The return values currently defined are:

        MP_OKAY         - okay, operation succeeded, all's well
        MP_YES          - okay, the answer is yes (same as MP_OKAY)
        MP_NO           - okay, but answer is no (not MP_OKAY)
        MP_MEM          - operation ran out of memory
        MP_RANGE        - input parameter was out of range
        MP_BADARG       - an invalid input parameter was provided
        MP_UNDEF        - no output value is defined for this input

The only function which currently uses MP_UNDEF is mp_invmod().
Division by zero is undefined, but the division functions will return
MP_RANGE for a zero divisor.  MP_BADARG usually means you passed a
bogus mp_int structure to the function.  MP_YES and MP_NO are not used
by the library itself; they're defined so you can use them in your own
extensions.

If you need a readable interpretation of these error codes in your
program, you may also use the mp_strerror() function.  This function
takes an mp_err as input, and returns a pointer to a human-readable
string describing the meaning of the error.  These strings are stored
as constants within the library, so the caller should not attempt to
modify or free the memory associated with these strings.

The library represents values in signed-magnitude format.  Values
strictly less than zero are negative, all others are considered
positive (zero is positive by fiat).  You can access the 'sign' member
of the mp_int structure directly, but better is to use the mp_cmp_z()
function, to find out which side of zero the value lies on.

Most arithmetic functions have a single-digit variant, as well as the
full arbitrary-precision.  An mp_digit is an unsigned value between 0
and DIGIT_MAX inclusive.  The radix is available as RADIX.  The number
of bits in a given digit is given as DIGIT_BIT.

Generally, input parameters are given before output parameters.
Unless otherwise specified, any input parameter can be re-used as an
output parameter, without confusing anything.

The basic numeric type defined by the library is an mp_int.  Virtually
all the functions in the library take a pointer to an mp_int as one of
their parameters.  An explanation of how to create and use these
<HR>
<A NAME="p23">
<H3>Problem 23:</H3>

structures follows.  And so, without further ado...


Initialization and Cleanup
--------------------------

The basic numeric type defined by the library is an 'mp_int'.
However, it is not sufficient to simply declare a variable of type
mp_int in your program.  These variables also need to be initialized
before they can be used, to allocate the internal storage they require
for computation.

This is done using one of the following functions:

        mp_init(mp_int *mp);
        mp_init_copy(mp_int *mp, mp_int *from);
        mp_init_size(mp_int *mp, mp_size p);

Each of these requires a pointer to a structure of type mp_int.  The
basic mp_init() simply initializes the mp_int to a default size, and
sets its value to zero.  If you would like to initialize a copy of an
existing mp_int, use mp_init_copy(), where the 'from' parameter is the
mp_int you'd like to make a copy of.  The third function,
mp_init_size(), permits you to specify how many digits of precision
should be preallocated for your mp_int.  This can help the library
avoid unnecessary re-allocations later on.

The default precision used by mp_init() can be retrieved using:

        precision = mp_get_prec();

This returns the number of digits that will be allocated.  You can
change this value by using:

        mp_set_prec(unsigned int prec);

Any positive value is acceptable -- if you pass zero, the default
precision will be re-set to the compiled-in library default (this is
specified in the header file 'mpi-config.h', and typically defaults to
8 or 16).

Just as you must allocate an mp_int before you can use it, you must
clean up the structure when you are done with it.  This is performed
using the mp_clear() function.  Remember that any mp_int that you
create as a local variable in a function must be mp_clear()'d before
that function exits, or else the memory allocated to that mp_int will
be orphaned and unrecoverable.

To set an mp_int to a given value, the following functions are given:

        mp_set(mp_int *mp, mp_digit d);
        mp_set_int(mp_int *mp, long z);

The mp_set() function sets the mp_int to a single digit value, while
mp_set_int() sets the mp_int to a signed long integer value.

To set an mp_int to zero, use:

        mp_zero(mp_int *mp);


Copying and Moving
------------------

If you have two initialized mp_int's, and you want to copy the value
of one into the other, use:

        mp_copy(from, to)

This takes care of clearing the old value of 'to', and copies the new
value into it.  If 'to' is not yet initialized, use mp_init_copy()
instead (see above).

Note:   The library tries, whenever possible, to avoid allocating
----    new memory.  Thus, mp_copy() tries first to satisfy the needs
        of the copy by re-using the memory already allocated to 'to'.
        Only if this proves insufficient will mp_copy() actually
        allocate new memory.

        For this reason, if you know a priori that 'to' has enough
        available space to hold 'from', you don't need to check the
        return value of mp_copy() for memory failure.  The USED()
        macro tells you how many digits are used by an mp_int, and
        the ALLOC() macro tells you how many are allocated.

If you have two initialized mp_int's, and you want to exchange their
values, use:

        mp_exch(a, b)

This is better than using mp_copy() with a temporary, since it will
not (ever) touch the memory allocator -- it just swaps the exact
contents of the two structures.  The mp_exch() function cannot fail;
if you pass it an invalid structure, it just ignores it, and does
nothing.


Basic Arithmetic
----------------

Once you have initialized your integers, you can operate on them.  The
basic arithmetic functions on full mp_int values are:

mp_add(a, b, c)         - computes c = a + b
mp_sub(a, b, c)         - computes c = a - b
mp_mul(a, b, c)         - computes c = a * b
mp_sqr(a, b)            - computes b = a * a
mp_div(a, b, q, r)      - computes q, r such that a = bq + r