diff options
Diffstat (limited to '')
-rw-r--r-- | security/nss/lib/freebl/mpi/mpi.h | 363 |
1 files changed, 363 insertions, 0 deletions
diff --git a/security/nss/lib/freebl/mpi/mpi.h b/security/nss/lib/freebl/mpi/mpi.h new file mode 100644 index 0000000000..dd129db0d6 --- /dev/null +++ b/security/nss/lib/freebl/mpi/mpi.h @@ -0,0 +1,363 @@ +/* + * mpi.h + * + * Arbitrary precision integer arithmetic library + * + * This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ + +#ifndef _H_MPI_ +#define _H_MPI_ + +#include "mpi-config.h" + +#include "seccomon.h" +SEC_BEGIN_PROTOS + +#if MP_DEBUG +#undef MP_IOFUNC +#define MP_IOFUNC 1 +#endif + +#if MP_IOFUNC +#include <stdio.h> +#include <ctype.h> +#endif + +#include <limits.h> + +#if defined(BSDI) +#undef ULLONG_MAX +#endif + +#include <sys/types.h> + +#define MP_NEG 1 +#define MP_ZPOS 0 + +#define MP_OKAY 0 /* no error, all is well */ +#define MP_YES 0 /* yes (boolean result) */ +#define MP_NO -1 /* no (boolean result) */ +#define MP_MEM -2 /* out of memory */ +#define MP_RANGE -3 /* argument out of range */ +#define MP_BADARG -4 /* invalid parameter */ +#define MP_UNDEF -5 /* answer is undefined */ +#define MP_LAST_CODE MP_UNDEF + +typedef unsigned int mp_sign; +typedef unsigned int mp_size; +typedef int mp_err; + +#define MP_32BIT_MAX 4294967295U + +#if !defined(ULONG_MAX) +#error "ULONG_MAX not defined" +#elif !defined(UINT_MAX) +#error "UINT_MAX not defined" +#elif !defined(USHRT_MAX) +#error "USHRT_MAX not defined" +#endif + +#if defined(ULLONG_MAX) /* C99, Solaris */ +#define MP_ULONG_LONG_MAX ULLONG_MAX +/* MP_ULONG_LONG_MAX was defined to be ULLONG_MAX */ +#elif defined(ULONG_LONG_MAX) /* HPUX */ +#define MP_ULONG_LONG_MAX ULONG_LONG_MAX +#elif defined(ULONGLONG_MAX) /* AIX */ +#define MP_ULONG_LONG_MAX ULONGLONG_MAX +#endif + +/* We only use unsigned long for mp_digit iff long is more than 32 bits. */ +#if !defined(MP_USE_UINT_DIGIT) && ULONG_MAX > MP_32BIT_MAX +typedef unsigned long mp_digit; +#define MP_DIGIT_MAX ULONG_MAX +#define MP_DIGIT_FMT "%016lX" /* printf() format for 1 digit */ +#define MP_HALF_DIGIT_MAX UINT_MAX +#undef MP_NO_MP_WORD +#define MP_NO_MP_WORD 1 +#undef MP_USE_LONG_DIGIT +#define MP_USE_LONG_DIGIT 1 +#undef MP_USE_LONG_LONG_DIGIT + +#elif !defined(MP_USE_UINT_DIGIT) && defined(MP_ULONG_LONG_MAX) +typedef unsigned long long mp_digit; +#define MP_DIGIT_MAX MP_ULONG_LONG_MAX +#define MP_DIGIT_FMT "%016llX" /* printf() format for 1 digit */ +#define MP_HALF_DIGIT_MAX UINT_MAX +#undef MP_NO_MP_WORD +#define MP_NO_MP_WORD 1 +#undef MP_USE_LONG_LONG_DIGIT +#define MP_USE_LONG_LONG_DIGIT 1 +#undef MP_USE_LONG_DIGIT + +#else +typedef unsigned int mp_digit; +#define MP_DIGIT_MAX UINT_MAX +#define MP_DIGIT_FMT "%08X" /* printf() format for 1 digit */ +#define MP_HALF_DIGIT_MAX USHRT_MAX +#undef MP_USE_UINT_DIGIT +#define MP_USE_UINT_DIGIT 1 +#undef MP_USE_LONG_LONG_DIGIT +#undef MP_USE_LONG_DIGIT +#endif + +#if !defined(MP_NO_MP_WORD) +#if defined(MP_USE_UINT_DIGIT) && \ + (defined(MP_ULONG_LONG_MAX) || (ULONG_MAX > UINT_MAX)) + +#if (ULONG_MAX > UINT_MAX) +typedef unsigned long mp_word; +typedef long mp_sword; +#define MP_WORD_MAX ULONG_MAX + +#else +typedef unsigned long long mp_word; +typedef long long mp_sword; +#define MP_WORD_MAX MP_ULONG_LONG_MAX +#endif + +#else +#define MP_NO_MP_WORD 1 +#endif +#endif /* !defined(MP_NO_MP_WORD) */ + +#if !defined(MP_WORD_MAX) && defined(MP_DEFINE_SMALL_WORD) +typedef unsigned int mp_word; +typedef int mp_sword; +#define MP_WORD_MAX UINT_MAX +#endif + +#define MP_DIGIT_SIZE sizeof(mp_digit) +#define MP_DIGIT_BIT (CHAR_BIT * MP_DIGIT_SIZE) +#define MP_WORD_BIT (CHAR_BIT * sizeof(mp_word)) +#define MP_RADIX (1 + (mp_word)MP_DIGIT_MAX) + +#define MP_HALF_DIGIT_BIT (MP_DIGIT_BIT / 2) +#define MP_HALF_RADIX (1 + (mp_digit)MP_HALF_DIGIT_MAX) +/* MP_HALF_RADIX really ought to be called MP_SQRT_RADIX, but it's named +** MP_HALF_RADIX because it's the radix for MP_HALF_DIGITs, and it's +** consistent with the other _HALF_ names. +*/ + +/* Macros for accessing the mp_int internals */ +#define MP_SIGN(MP) ((MP)->sign) +#define MP_USED(MP) ((MP)->used) +#define MP_ALLOC(MP) ((MP)->alloc) +#define MP_DIGITS(MP) ((MP)->dp) +#define MP_DIGIT(MP, N) (MP)->dp[(N)] + +/* This defines the maximum I/O base (minimum is 2) */ +#define MP_MAX_RADIX 64 + +/* Constant Time Macros on mp_digits */ +#define MP_CT_HIGH_TO_LOW(x) ((mp_digit)((mp_digit)(x) >> (MP_DIGIT_BIT - 1))) +#define MP_CT_TRUE ((mp_digit)1) +#define MP_CT_FALSE ((mp_digit)0) + +/* basic zero and non zero tests */ +#define MP_CT_NOT_ZERO(x) (MP_CT_HIGH_TO_LOW(((x) | (((mp_digit)0) - (x))))) +#define MP_CT_ZERO(x) (MP_CT_TRUE ^ MP_CT_HIGH_TO_LOW(((x) | (((mp_digit)0) - (x))))) + +/* basic constant-time helper macro for equalities and inequalities. + * The inequalities will produce incorrect results if + * abs(a-b) >= MP_DIGIT_SIZE/2. This can be avoided if unsigned values stay + * within the range 0-MP_DIGIT_MAX/2. */ +#define MP_CT_EQ(a, b) MP_CT_ZERO(((a) ^ (b))) +#define MP_CT_NE(a, b) MP_CT_NOT_ZERO(((a) ^ (b))) +#define MP_CT_GT(a, b) MP_CT_HIGH_TO_LOW((b) - (a)) +#define MP_CT_LT(a, b) MP_CT_HIGH_TO_LOW((a) - (b)) +#define MP_CT_GE(a, b) (MP_CT_TRUE ^ MP_CT_LT(a, b)) +#define MP_CT_LE(a, b) (MP_CT_TRUE ^ MP_CT_GT(a, b)) + +/* use constant time result to select a boolean value + * or an mp digit depending on the args */ +#define MP_CT_SEL(m, l, r) ((r) ^ ((m) & ((r) ^ (l)))) +#define MP_CT_SELB(m, l, r) MP_CT_SEL(m, l, r) /* mask, l and r are booleans */ +#define MP_CT_SEL_DIGIT(m, l, r) MP_CT_SEL(m, l, r) /*mask, l, and r are mp_digit */ + +/* full inequalities that work with full mp_digit values */ +#define MP_CT_OVERFLOW(a, b, c, d) \ + MP_CT_SELB(MP_CT_HIGH_TO_LOW((a) ^ (b)), \ + (MP_CT_HIGH_TO_LOW(d)), c) +#define MP_CT_LTU(a, b) MP_CT_OVERFLOW(a, b, MP_CT_LT(a, b), b) + +typedef struct { + mp_sign sign; /* sign of this quantity */ + mp_size alloc; /* how many digits allocated */ + mp_size used; /* how many digits used */ + mp_digit *dp; /* the digits themselves */ +} mp_int; + +/* Default precision */ +mp_size mp_get_prec(void); +void mp_set_prec(mp_size prec); + +/* Memory management */ +mp_err mp_init(mp_int *mp); +mp_err mp_init_size(mp_int *mp, mp_size prec); +mp_err mp_init_copy(mp_int *mp, const mp_int *from); +mp_err mp_copy(const mp_int *from, mp_int *to); +void mp_exch(mp_int *mp1, mp_int *mp2); +void mp_clear(mp_int *mp); +void mp_zero(mp_int *mp); +void mp_set(mp_int *mp, mp_digit d); +mp_err mp_set_int(mp_int *mp, long z); +#define mp_set_long(mp, z) mp_set_int(mp, z) +mp_err mp_set_ulong(mp_int *mp, unsigned long z); + +/* Single digit arithmetic */ +mp_err mp_add_d(const mp_int *a, mp_digit d, mp_int *b); +mp_err mp_sub_d(const mp_int *a, mp_digit d, mp_int *b); +mp_err mp_mul_d(const mp_int *a, mp_digit d, mp_int *b); +mp_err mp_mul_2(const mp_int *a, mp_int *c); +mp_err mp_div_d(const mp_int *a, mp_digit d, mp_int *q, mp_digit *r); +mp_err mp_div_2(const mp_int *a, mp_int *c); +mp_err mp_expt_d(const mp_int *a, mp_digit d, mp_int *c); + +/* Sign manipulations */ +mp_err mp_abs(const mp_int *a, mp_int *b); +mp_err mp_neg(const mp_int *a, mp_int *b); + +/* Full arithmetic */ +mp_err mp_add(const mp_int *a, const mp_int *b, mp_int *c); +mp_err mp_sub(const mp_int *a, const mp_int *b, mp_int *c); +mp_err mp_subCT(const mp_int *a, mp_int *b, mp_int *c, mp_digit *borrow); +mp_err mp_mul(const mp_int *a, const mp_int *b, mp_int *c); +mp_err mp_mulCT(mp_int *a, mp_int *b, mp_int *c, mp_size setSize); +#if MP_SQUARE +mp_err mp_sqr(const mp_int *a, mp_int *b); +#else +#define mp_sqr(a, b) mp_mul(a, a, b) +#endif +mp_err mp_div(const mp_int *a, const mp_int *b, mp_int *q, mp_int *r); +mp_err mp_div_2d(const mp_int *a, mp_digit d, mp_int *q, mp_int *r); +mp_err mp_expt(mp_int *a, mp_int *b, mp_int *c); +mp_err mp_2expt(mp_int *a, mp_digit k); + +/* Modular arithmetic */ +#if MP_MODARITH +mp_err mp_mod(const mp_int *a, const mp_int *m, mp_int *c); +mp_err mp_mod_d(const mp_int *a, mp_digit d, mp_digit *c); +mp_err mp_addmod(const mp_int *a, const mp_int *b, const mp_int *m, mp_int *c); +mp_err mp_submod(const mp_int *a, const mp_int *b, const mp_int *m, mp_int *c); +mp_err mp_mulmod(const mp_int *a, const mp_int *b, const mp_int *m, mp_int *c); +#if MP_SQUARE +mp_err mp_sqrmod(const mp_int *a, const mp_int *m, mp_int *c); +#else +#define mp_sqrmod(a, m, c) mp_mulmod(a, a, m, c) +#endif +mp_err mp_exptmod(const mp_int *a, const mp_int *b, const mp_int *m, mp_int *c); +mp_err mp_exptmod_d(const mp_int *a, mp_digit d, const mp_int *m, mp_int *c); +#endif /* MP_MODARITH */ + +/* montgomery math */ +mp_err mp_to_mont(const mp_int *x, const mp_int *N, mp_int *xMont); +mp_digit mp_calculate_mont_n0i(const mp_int *N); +mp_err mp_reduceCT(const mp_int *a, const mp_int *m, mp_digit n0i, mp_int *ct); +mp_err mp_mulmontmodCT(mp_int *a, mp_int *b, const mp_int *m, mp_digit n0i, mp_int *c); + +/* Comparisons */ +int mp_cmp_z(const mp_int *a); +int mp_cmp_d(const mp_int *a, mp_digit d); +int mp_cmp(const mp_int *a, const mp_int *b); +int mp_cmp_mag(const mp_int *a, const mp_int *b); +int mp_isodd(const mp_int *a); +int mp_iseven(const mp_int *a); +mp_err mp_selectCT(mp_digit cond, const mp_int *a, const mp_int *b, mp_int *ret); + +/* Number theoretic */ +mp_err mp_gcd(mp_int *a, mp_int *b, mp_int *c); +mp_err mp_lcm(mp_int *a, mp_int *b, mp_int *c); +mp_err mp_xgcd(const mp_int *a, const mp_int *b, mp_int *g, mp_int *x, mp_int *y); +mp_err mp_invmod(const mp_int *a, const mp_int *m, mp_int *c); +mp_err mp_invmod_xgcd(const mp_int *a, const mp_int *m, mp_int *c); + +/* Input and output */ +#if MP_IOFUNC +void mp_print(mp_int *mp, FILE *ofp); +#endif /* end MP_IOFUNC */ + +/* Base conversion */ +mp_err mp_read_raw(mp_int *mp, char *str, int len); +int mp_raw_size(mp_int *mp); +mp_err mp_toraw(mp_int *mp, char *str); +mp_err mp_read_radix(mp_int *mp, const char *str, int radix); +mp_err mp_read_variable_radix(mp_int *a, const char *str, int default_radix); +int mp_radix_size(mp_int *mp, int radix); +mp_err mp_toradix(mp_int *mp, char *str, int radix); +int mp_tovalue(char ch, int r); + +#define mp_tobinary(M, S) mp_toradix((M), (S), 2) +#define mp_tooctal(M, S) mp_toradix((M), (S), 8) +#define mp_todecimal(M, S) mp_toradix((M), (S), 10) +#define mp_tohex(M, S) mp_toradix((M), (S), 16) + +/* Error strings */ +const char *mp_strerror(mp_err ec); + +/* Octet string conversion functions */ +mp_err mp_read_unsigned_octets(mp_int *mp, const unsigned char *str, mp_size len); +unsigned int mp_unsigned_octet_size(const mp_int *mp); +mp_err mp_to_unsigned_octets(const mp_int *mp, unsigned char *str, mp_size maxlen); +mp_err mp_to_signed_octets(const mp_int *mp, unsigned char *str, mp_size maxlen); +mp_err mp_to_fixlen_octets(const mp_int *mp, unsigned char *str, mp_size len); + +/* Miscellaneous */ +mp_size mp_trailing_zeros(const mp_int *mp); +void freebl_cpuid(unsigned long op, unsigned long *eax, + unsigned long *ebx, unsigned long *ecx, + unsigned long *edx); +mp_err mp_cswap(mp_digit condition, mp_int *a, mp_int *b, mp_size numdigits); + +#define MP_CHECKOK(x) \ + if (MP_OKAY > (res = (x))) \ + goto CLEANUP +#define MP_CHECKERR(x) \ + if (MP_OKAY > (res = (x))) \ + goto CLEANUP + +#define NEG MP_NEG +#define ZPOS MP_ZPOS +#define DIGIT_MAX MP_DIGIT_MAX +#define DIGIT_BIT MP_DIGIT_BIT +#define DIGIT_FMT MP_DIGIT_FMT +#define RADIX MP_RADIX +#define MAX_RADIX MP_MAX_RADIX +#define SIGN(MP) MP_SIGN(MP) +#define USED(MP) MP_USED(MP) +#define ALLOC(MP) MP_ALLOC(MP) +#define DIGITS(MP) MP_DIGITS(MP) +#define DIGIT(MP, N) MP_DIGIT(MP, N) + +/* Functions which return an mp_err value will NULL-check their arguments via + * ARGCHK(condition, return), where the caller is responsible for checking the + * mp_err return code. For functions that return an integer type, the caller + * has no way to tell if the value is an error code or a legitimate value. + * Therefore, ARGMPCHK(condition) will trigger an assertion failure on debug + * builds, but no-op in optimized builds. */ +#if MP_ARGCHK == 1 +#define ARGMPCHK(X) /* */ +#define ARGCHK(X, Y) \ + { \ + if (!(X)) { \ + return (Y); \ + } \ + } +#elif MP_ARGCHK == 2 +#include <assert.h> +#define ARGMPCHK(X) assert(X) +#define ARGCHK(X, Y) assert(X) +#else +#define ARGMPCHK(X) /* */ +#define ARGCHK(X, Y) /* */ +#endif + +#ifdef CT_VERIF +void mp_taint(mp_int *mp); +void mp_untaint(mp_int *mp); +#endif + +SEC_END_PROTOS + +#endif /* end _H_MPI_ */ |