bignum.h

windows的加密api源码

/*
        Macro to return 3^i (exponentiation), for 0 <= i <= 15.
        Intended for use with constant argument, such as
        in array dimensions.  The POWER3 array should
        be used if the subscript is variable.
*/

#define POWER3CON(i) (   ((i) & 1 ?  3 : 1)  *  ((i) & 2 ?    9 : 1) \
                       * ((i) & 4 ? 81 : 1)  *  ((i) & 8 ? 6561 : 1) )

exportable_var DWORDC POWER3[16];   /* See mpglobals.c */
/*
        kara.c repeatedly replaces an operand by three
        half-length operands and a sign.  The sign has
        type kara_sign_t.  The operands are partitioned
        in half until their size at most VMUL_MAX_LNG_SINGLE,
        and sometimes further (see padinfo_initialization in kara.c)
        This may require up to KARA_MAX_HALVINGS halvings,
        giving 3^KARA_MAX_HALVINGS outputs each with size
        as large as VMUL_MAX_SINGLE words.  The signs
        array has length (3^KARA_MAX_HALVINGS - 1)/2.
*/
#if TARGET == TARGET_ALPHA
    typedef int kara_sign_t;
                        /* Try to avoid char data on Alpha */
#else
    typedef unsigned char kara_sign_t;
                        /* Values SIGN_PLUS, SIGN_MINUS.  See kara.c. */
#endif

typedef const kara_sign_t kara_sign_tc;
#define VMUL_MAX_LNG_SINGLE 12
#define KARA_MAX_HALVINGS (LG2_MP_LONGEST - 2)
#if KARA_MAX_HALVINGS > 15
    #error -- "Extend POWER3CON macro"
#endif
#define KARA_MAX_LNG_DIFS ((MP_LONGEST >> KARA_MAX_HALVINGS) * POWER3CON(KARA_MAX_HALVINGS))
#define KARA_MAX_LNG_SIGNS ((POWER3CON(KARA_MAX_HALVINGS) - 1)/2)
#define MEMORY_BANK_ALLOWANCE 1

typedef struct  {
                  digit_t     difs[KARA_MAX_LNG_DIFS + MEMORY_BANK_ALLOWANCE];
                  kara_sign_t signs[KARA_MAX_LNG_SIGNS];
                } kara_longest_t;   /* For MP_LONGEST or less */
                       /* On the Pentium P5 and P6,
                          the two arguments to vmulnn
                          should lie in different memory banks
                          (i.e., different addresses mod 32 bytes).
                          We make the .difs arrays one digit_t entry
                          larger than essential, in an attempt to reduce
                          data cache conflicts.  Look for the
                          MEMORY_BANK_ALLOWANCE symbol in the source code.
                        */


typedef struct  {
                  digit_t     difs[KARA_MAX_LNG_DIFS/3 + MEMORY_BANK_ALLOWANCE];
                  kara_sign_t signs[KARA_MAX_LNG_SIGNS/3];
                } kara_half_longest_t;  /* For MP_LONGEST/2 or less */

typedef const kara_half_longest_t kara_half_longest_tc;
typedef const kara_longest_t      kara_longest_tc;

typedef struct {      /* Constants relating to padding lengths. */
                  DWORD  length;
                                /* length = length3[0] * 2^nhalving */
                  DWORD  nhalving;
                  DWORD  length3[KARA_MAX_HALVINGS+1];
                                /* length3[0] is 1, 2, 3, or 4 */
                                /* length3[i] is length3[0] * 3^i */
               } padinfo_t;

typedef const padinfo_t padinfo_tc;
#define padinfo_NULL ((padinfo_t*)0)

/*
        The reciprocal_1_t type is used when div21
        or divide or divide_immediate would otherwise
        divide by the same number repeatedly.  See file divide.c.
*/

typedef struct {
                digit_t multiplier;
                int     shiftamt;
               } reciprocal_1_t;

typedef const reciprocal_1_t reciprocal_1_tc;

/*
        mp_modulus_t struct has modulus-dependent constants
        used for fast reduction (typically for a fixed modulus,
        which will be used several times, as in modular exponentiation).
        These constants are initialized by function create_modulus:

        modulus -- Modulus used for computations.  Must be nonzero.

        length  -- Length of the modulus, without leading zeros.
                   Operands to mod_add, mod_mul, mod_sub, ...
                   are assumed to have this length.

        padinfo -- Pointer to a padinfo_t struct.  For fast arithmetic,
                   operands are padded to a length
                   length_padded >= length (see find_padinfo in kara.c).
                   The value of length_padded is stored in padinfo->length.
                   The present implementation requires length_padded be either
                   a power of 2, or 3 times a power of 2.
                   For example, if length = 19, then length_padded = 24,
                   and the operands are treated as 24-word
                   operands for Karatsuba.

        half_padinfo -- Pointer to a padinfo_t struct for length
                   CEIL(length/2).  Used in modular_reduce to
                   use Karatsuba multiplication on half-length operands.
                   We denote half_length_padded = half_padinfo->length.

        reddir  -- Equal to FROM_LEFT if reductions of
                   products are done from the left (traditional
                   division), and to FROM_RIGHT if reductions of
                   products are done from the right (Montgomery reduction).

                   When using FROM_RIGHT, the modulus must be odd.
                   Arguments to mod_mul should be pre-scaled by
                   RADIX^scaling_power (mod modulus).
                   The product will be similarly scaled.

        scaling_power --  Equal to 2*half_length_padded when
                   reddir = FROM_RIGHT.  Undefined
                   if reddir = FROM_LEFT.

        one --     Constant 1 (length length), scaled if reddir = FROM_RIGHT.
                   When reddir = FROM_RIGHT, this is
                   RADIX^scaling_power (mod modulus).

        left_multiplier_first -- The first multiplier when reducing from the
                   left.  Length length.

-RADIX^(length + half_length_padded)/2^(left_reciprocal_1.shiftamt) mod modulus

        left_reciprocal_1 -- Reciprocal of the divisor starting at the
                   leftmost digit (i.e., modulus[length-1]);

        right_reciprocal_1 -- If modulus is odd, this holds
                   1/modulus (mod RADIX), for use in mod_shift.
                   Otherwise the field is zero.

        right_multiplier_second -- If reddir = FROM_RIGHT,
                   then this has 1/modulus mod RADIX^(half_length_padded).

        right_multiplier_first --   -1/RADIX^half_length_padded mod modulus.
                   Equal to

        left_multiplier_second -- Contains the half_length_padded*RADIX_BITS

            (modulus * right_multiplier_second - 1)/RADIX^half_length_padded.
                   most significant bits of (high power of 2)/modulus
                   (excluding the leading -1-).  More precisely, this has

        RADIX^(length + half_length_padded) - 1
 FLOOR( --------------------------------------- ) - RADIX^(half_length_padded)
        modulus * 2^(left_reciprocal_1.shiftamt)


                   See file divide.c for an explanation
                   about how this constant is used to get accurate
                   quotients when dividing from the left.

        left_multiplier_second_over2 -- Left_multiplier_second/2.
*/


typedef enum {FROM_LEFT, FROM_RIGHT} reddir_t;
typedef const reddir_t reddir_tc;

typedef struct {
                  digit_t   modulus[MP_LONGEST];
                  DWORD     length;      /* Length passed to create_modulus */
                  DWORD     scaling_power; /* 2*half_padinfo->length */
                  padinfo_tc *padinfo;   /* Pointer to struct containing
                                            padded length and related info */
                  padinfo_tc *half_padinfo;
                                         /* Padinfo info for CEIL(length/2) */
                  reddir_t  reddir;      /* FROM_LEFT or FROM_RIGHT */
                  reciprocal_1_t  left_reciprocal_1;
                  digit_t  right_reciprocal_1;
                                        /* 1/modulus[0] mod RADIX,
                                           if modulus is odd */

                  kara_half_longest_t modulus_kara2[2];
                                        /*
                                            Copy of modulus.

                                            Lower half_length_padded
                                            and upper
                                            length - half_length_padded
                                            words separately passed
                                            to to_kara.
                                         */
                  kara_half_longest_t left_multiplier_first_kara2[2];
                                /* Remainder when dividing
                                     -RADIX^(length + half_length_padded)
                                   / 2^(left_reciprocal_1.shiftamt)
                                   by modulus.

                                   Lower and upper halvves separately
                                   passed to to_kara.
                                */

                  kara_half_longest_t left_multiplier_second_kara;
                                /* half_length_padded*RADIX_BITS
                                   most significant bits of (left)
                                   reciprocal of modulus,
                                   excluding the leading -1-. */

                  digit_t  left_multiplier_second_over2[MP_LONGEST/2];
                                /* left_multiplier_second/2 */
                  kara_half_longest_t right_multiplier_first_kara2[2];
                                        /*  -1/RADIX^half_length_padded
                                            mod modulus.
                                        */
                  digit_t             right_multiplier_second[MP_LONGEST/2];
                  kara_half_longest_t right_multiplier_second_kara;
                              /* 1/modulus mod RADIX^(half_length_padded) */
                  digit_t  cofactor[MP_LONGEST];
                  DWORD    lng_cofactor;
                             /*
                                In factorization programs, this
                                holds the cofactor after dividing
                                modulus by any factors found.
                                Used by gcdex_jacobi.
                             */
                  digit_t  one[MP_LONGEST];
                } mp_modulus_t;


typedef const mp_modulus_t mp_modulus_tc;
/*
       The modular multiplication code and its
       relatives (e.g., modular_reduce, to_kara)
       need large amounts of temporary space
       during processing.  All big temporaries
       are gathered into a modmultemp_t struct.
       Users of these routines can allocate the
       storage themselves, and pass a pointer
       to the temporary storage (fastest), or can pass
       a null pointer (modmultemp_NULL).

*/
typedef struct {
                   // mmul fields are for mod_mul,
                   // mod_mul_kara, mod_mul_kara1

        digit_t             mmul_adifs[KARA_MAX_LNG_DIFS];
        kara_sign_t         mmul_asigns[KARA_MAX_LNG_SIGNS];
        digit_t             mmul_bdifs[KARA_MAX_LNG_DIFS
                                       + MEMORY_BANK_ALLOWANCE];
        kara_sign_t         mmul_bsigns[KARA_MAX_LNG_SIGNS];

                   // mr_ fields are for modular_reduce.
                   // The input to modular_reduce can be stored
                   // in mr_dividend -- this will save a mp_copy call.

        digit_t             mr_dividend[MAX(2*MP_LONGEST,
                                            2*KARA_MAX_LNG_DIFS+1)];

        digit_t             mr_prd1[2*MP_LONGEST];
        digit_t             mr_prd2[2*MP_LONGEST];
        digit_t             mr_mptemp[2*MP_LONGEST];

                   // htk_ fields are for half_times_kara
                   // and half_times_kara2

        digit_t             htk_abprd[2][2*KARA_MAX_LNG_DIFS/3];
        kara_half_longest_t htk_ak;
        } modmultemp_t;

typedef struct {
        void             *pInfo;
        void             *pFuncRNG;
        } RNGINFO;

/*
        When an error is detected, variable mp_errno is set
        to the error number and execution continues.
        If the library was compiled with #define PRINT_ERROR_MESSAGES,
        then a message is written to file mp_errfil.

        The application program should occasionally check mp_errno.

        Except for MP_ERRNO_NO_ERROR, the error numbers are
        in alphabetical order by name.  The routine issuing
        each error number is part of the name.
*/

typedef enum {
        MP_ERRNO_NO_ERROR = 0,
        MP_ERRNO_CREATE_MODULUS_LEADING_ZERO,
        MP_ERRNO_CREATE_MODULUS_MONTGOMERY_EVEN,
        MP_ERRNO_CREATE_MODULUS_TOO_LONG,
        MP_ERRNO_DIGIT_JACOBI_EVEN_DENOMINATOR,
        MP_ERRNO_DIGIT_MOD_DIVIDE_ODD_EVEN_MODULUS,
        MP_ERRNO_DIGIT_MOD_DIVIDE_ODD_NONTRIVIAL_GCD,
        MP_ERRNO_DIGIT_MOD_DIVIDE_ODD_ZERO_DENOMINATOR,
        MP_ERRNO_DIGIT_NEXT_PRIME_TOO_HIGH,
        MP_ERRNO_DIV21_INVALID_ARGUMENT,
        MP_ERRNO_DIVIDE_ESTIMATION_ERROR,
        MP_ERRNO_DIVIDE_INVALID_LENGTHS,
        MP_ERRNO_DIVIDE_LEADING_ZERO,
        MP_ERRNO_DSA_KEY_GENERATION_INVALID_SIZES,
        MP_ERRNO_DSA_PRECOMPUTE_BAD_G,
        MP_ERRNO_DSA_PRECOMPUTE_INVALID_KEY,
        MP_ERRNO_DSA_PRECOMPUTE_PQ_NONPRIME,
        MP_ERRNO_DSA_PRECOMPUTE_WRONG_SC,
        MP_ERRNO_DSA_SIGNATURE_VERIFICATION_NONTRIVIAL_GCD,
        MP_ERRNO_FIND_BIG_PRIME_BAD_CONGRUENCE_CLASS,
        MP_ERRNO_FIND_BIG_PRIME_CONG_MOD_TOO_LARGE,
        MP_ERRNO_FIND_BIG_PRIME_CONG_TO_TOO_LARGE,
        MP_ERRNO_GCDEX_JACOBI_EVEN_MODULUS,
        MP_ERRNO_KP_TOO_SHORT,
        MP_ERRNO_KPDIV_ZERO_DENOMINATOR,
        MP_ERRNO_MOD_ADD_CARRY_NONZERO,
        MP_ERRNO_MOD_SHIFT_LEFT_CARRY_NONZERO,
        MP_ERRNO_MOD_SHIFT_RIGHT_CARRY_NONZERO,
        MP_ERRNO_MOD_SHIFT_RIGHT_EVEN,
        MP_ERRNO_MOD_SUB_BORROW_NONZERO,
        MP_ERRNO_MODULAR_REDUCE_BOTTOM_BITS_DIFFERENT,
        MP_ERRNO_MODULAR_REDUCE_TOO_LONG,
        MP_ERRNO_MODULAR_REDUCE_UNEXPECTED_CARRY,
        MP_ERRNO_MP_DECIMAL_INPUT_NONDIGIT,
        MP_ERRNO_MP_DECIMAL_INPUT_OVERFLOW,
        MP_ERRNO_MP_GCD_INTERMEDIATE_EVEN,
        MP_ERRNO_MP_GCD_TOO_LONG,
        MP_ERRNO_MP_GCDEX_INTERNAL_ERROR,
        MP_ERRNO_MP_GCDEX_NONZERO_REMAINDER,
        MP_ERRNO_MP_GCDEX_ZERO_OPERAND,
        MP_ERRNO_MP_SHIFT_INVALID_SHIFT_COUNT,
        MP_ERRNO_MP_TRAILING_ZERO_COUNT_ZERO_ARG,
        MP_ERRNO_MULTIPLY_LOW_INVALID_LENGTH,
        MP_ERRNO_NO_MEMORY,      // From mp_alloc_temp