diff options
Diffstat (limited to 'libtommath/tommath.h')
| -rw-r--r-- | libtommath/tommath.h | 224 |
1 files changed, 114 insertions, 110 deletions
diff --git a/libtommath/tommath.h b/libtommath/tommath.h index e696779..b706576 100644 --- a/libtommath/tommath.h +++ b/libtommath/tommath.h @@ -10,25 +10,44 @@ * The library is free for all purposes without any express * guarantee it works. * - * Tom St Denis, tstdenis82@gmail.com, http://math.libtomcrypt.com + * Tom St Denis, tomstdenis@gmail.com, http://math.libtomcrypt.com */ #ifndef BN_H_ #define BN_H_ #include <stdio.h> +#include <string.h> #include <stdlib.h> -#include <stdint.h> +#include <ctype.h> #include <limits.h> #include <tommath_class.h> +#ifndef MIN + #define MIN(x,y) ((x)<(y)?(x):(y)) +#endif + +#ifndef MAX + #define MAX(x,y) ((x)>(y)?(x):(y)) +#endif + #ifdef __cplusplus extern "C" { + +/* C++ compilers don't like assigning void * to mp_digit * */ +#define OPT_CAST(x) (x *) + +#else + +/* C on the other hand doesn't care */ +#define OPT_CAST(x) + #endif + /* detect 64-bit mode if possible */ -#if defined(__x86_64__) - #if !(defined(MP_32BIT) || defined(MP_16BIT) || defined(MP_8BIT)) +#if defined(__x86_64__) + #if !(defined(MP_64BIT) && defined(MP_16BIT) && defined(MP_8BIT)) #define MP_64BIT #endif #endif @@ -42,78 +61,70 @@ extern "C" { * [any size beyond that is ok provided it doesn't overflow the data type] */ #ifdef MP_8BIT - typedef uint8_t mp_digit; - typedef uint16_t mp_word; -#define MP_SIZEOF_MP_DIGIT 1 -#ifdef DIGIT_BIT -#error You must not define DIGIT_BIT when using MP_8BIT -#endif + typedef unsigned char mp_digit; + typedef unsigned short mp_word; #elif defined(MP_16BIT) - typedef uint16_t mp_digit; - typedef uint32_t mp_word; -#define MP_SIZEOF_MP_DIGIT 2 -#ifdef DIGIT_BIT -#error You must not define DIGIT_BIT when using MP_16BIT -#endif + typedef unsigned short mp_digit; + typedef unsigned long mp_word; #elif defined(MP_64BIT) /* for GCC only on supported platforms */ #ifndef CRYPT - typedef unsigned long long ulong64; - typedef signed long long long64; + typedef unsigned long long ulong64; + typedef signed long long long64; #endif - typedef ulong64 mp_digit; -#if defined(_WIN32) - typedef unsigned __int128 mp_word; -#elif defined(__GNUC__) - typedef unsigned long mp_word __attribute__ ((mode(TI))); -#else - /* it seems you have a problem - * but we assume you can somewhere define your own uint128_t */ - typedef uint128_t mp_word; -#endif + typedef unsigned long mp_digit; + typedef unsigned long mp_word __attribute__ ((mode(TI))); - #define DIGIT_BIT 60 + #define DIGIT_BIT 60 #else /* this is the default case, 28-bit digits */ - + /* this is to make porting into LibTomCrypt easier :-) */ #ifndef CRYPT - typedef unsigned long long ulong64; - typedef signed long long long64; + #if defined(_MSC_VER) || defined(__BORLANDC__) + typedef unsigned __int64 ulong64; + typedef signed __int64 long64; + #else + typedef unsigned long long ulong64; + typedef signed long long long64; + #endif #endif - typedef uint32_t mp_digit; - typedef ulong64 mp_word; + typedef unsigned long mp_digit; + typedef ulong64 mp_word; -#ifdef MP_31BIT +#ifdef MP_31BIT /* this is an extension that uses 31-bit digits */ - #define DIGIT_BIT 31 + #define DIGIT_BIT 31 #else /* default case is 28-bit digits, defines MP_28BIT as a handy macro to test */ - #define DIGIT_BIT 28 + #define DIGIT_BIT 28 #define MP_28BIT -#endif +#endif #endif -/* otherwise the bits per digit is calculated automatically from the size of a mp_digit */ -#ifndef DIGIT_BIT - #define DIGIT_BIT (((CHAR_BIT * MP_SIZEOF_MP_DIGIT) - 1)) /* bits per digit */ - typedef uint_least32_t mp_min_u32; -#else - typedef mp_digit mp_min_u32; +/* define heap macros */ +#ifndef CRYPT + /* default to libc stuff */ + #ifndef XMALLOC + #define XMALLOC malloc + #define XFREE free + #define XREALLOC realloc + #define XCALLOC calloc + #else + /* prototypes for our heap functions */ + extern void *XMALLOC(size_t n); + extern void *XREALLOC(void *p, size_t n); + extern void *XCALLOC(size_t n, size_t s); + extern void XFREE(void *p); + #endif #endif -/* platforms that can use a better rand function */ -#if defined(__FreeBSD__) || defined(__OpenBSD__) || defined(__NetBSD__) || defined(__DragonFly__) - #define MP_USE_ALT_RAND 1 -#endif -/* use arc4random on platforms that support it */ -#ifdef MP_USE_ALT_RAND - #define MP_GEN_RANDOM() arc4random() -#else - #define MP_GEN_RANDOM() rand() +/* otherwise the bits per digit is calculated automatically from the size of a mp_digit */ +#ifndef DIGIT_BIT + #define DIGIT_BIT ((int)((CHAR_BIT * sizeof(mp_digit) - 1))) /* bits per digit */ #endif #define MP_DIGIT_BIT DIGIT_BIT @@ -158,11 +169,11 @@ extern int KARATSUBA_MUL_CUTOFF, #define MP_PREC 32 /* default digits of precision */ #else #define MP_PREC 8 /* default digits of precision */ - #endif + #endif #endif /* size of comba arrays, should be at least 2 * 2**(BITS_PER_WORD - BITS_PER_DIGIT*2) */ -#define MP_WARRAY (1 << (((sizeof(mp_word) * CHAR_BIT) - (2 * DIGIT_BIT)) + 1)) +#define MP_WARRAY (1 << (sizeof(mp_word) * CHAR_BIT - 2 * DIGIT_BIT + 1)) /* the infamous mp_int structure */ typedef struct { @@ -179,7 +190,7 @@ typedef int ltm_prime_callback(unsigned char *dst, int len, void *dat); #define SIGN(m) ((m)->sign) /* error code to char* string */ -const char *mp_error_to_string(int code); +char *mp_error_to_string(int code); /* ---> init and deinit bignum functions <--- */ /* init a bignum */ @@ -208,9 +219,8 @@ int mp_init_size(mp_int *a, int size); /* ---> Basic Manipulations <--- */ #define mp_iszero(a) (((a)->used == 0) ? MP_YES : MP_NO) -#define mp_iseven(a) ((((a)->used == 0) || (((a)->dp[0] & 1u) == 0u)) ? MP_YES : MP_NO) -#define mp_isodd(a) ((((a)->used > 0) && (((a)->dp[0] & 1u) == 1u)) ? MP_YES : MP_NO) -#define mp_isneg(a) (((a)->sign != MP_ZPOS) ? MP_YES : MP_NO) +#define mp_iseven(a) (((a)->used == 0 || (((a)->dp[0] & 1) == 0)) ? MP_YES : MP_NO) +#define mp_isodd(a) (((a)->used > 0 && (((a)->dp[0] & 1) == 1)) ? MP_YES : MP_NO) /* set to zero */ void mp_zero(mp_int *a); @@ -221,21 +231,9 @@ void mp_set(mp_int *a, mp_digit b); /* set a 32-bit const */ int mp_set_int(mp_int *a, unsigned long b); -/* set a platform dependent unsigned long value */ -int mp_set_long(mp_int *a, unsigned long b); - -/* set a platform dependent unsigned long long value */ -int mp_set_long_long(mp_int *a, unsigned long long b); - /* get a 32-bit value */ unsigned long mp_get_int(mp_int * a); -/* get a platform dependent unsigned long value */ -unsigned long mp_get_long(mp_int * a); - -/* get a platform dependent unsigned long long value */ -unsigned long long mp_get_long_long(mp_int * a); - /* initialize and set a digit */ int mp_init_set (mp_int * a, mp_digit b); @@ -243,20 +241,14 @@ int mp_init_set (mp_int * a, mp_digit b); int mp_init_set_int (mp_int * a, unsigned long b); /* copy, b = a */ -int mp_copy(const mp_int *a, mp_int *b); +int mp_copy(mp_int *a, mp_int *b); /* inits and copies, a = b */ -int mp_init_copy(mp_int *a, const mp_int *b); +int mp_init_copy(mp_int *a, mp_int *b); /* trim unused digits */ void mp_clamp(mp_int *a); -/* import binary data */ -int mp_import(mp_int* rop, size_t count, int order, size_t size, int endian, size_t nails, const void* op); - -/* export binary data */ -int mp_export(void* rop, size_t* countp, int order, size_t size, int endian, size_t nails, mp_int* op); - /* ---> digit manipulation <--- */ /* right shift by "b" digits */ @@ -265,26 +257,26 @@ void mp_rshd(mp_int *a, int b); /* left shift by "b" digits */ int mp_lshd(mp_int *a, int b); -/* c = a / 2**b, implemented as c = a >> b */ -int mp_div_2d(const mp_int *a, int b, mp_int *c, mp_int *d); +/* c = a / 2**b */ +int mp_div_2d(mp_int *a, int b, mp_int *c, mp_int *d); /* b = a/2 */ int mp_div_2(mp_int *a, mp_int *b); -/* c = a * 2**b, implemented as c = a << b */ -int mp_mul_2d(const mp_int *a, int b, mp_int *c); +/* c = a * 2**b */ +int mp_mul_2d(mp_int *a, int b, mp_int *c); /* b = a*2 */ int mp_mul_2(mp_int *a, mp_int *b); -/* c = a mod 2**b */ -int mp_mod_2d(const mp_int *a, int b, mp_int *c); +/* c = a mod 2**d */ +int mp_mod_2d(mp_int *a, int b, mp_int *c); /* computes a = 2**b */ int mp_2expt(mp_int *a, int b); /* Counts the number of lsbs which are zero before the first zero bit */ -int mp_cnt_lsb(const mp_int *a); +int mp_cnt_lsb(mp_int *a); /* I Love Earth! */ @@ -304,16 +296,16 @@ int mp_and(mp_int *a, mp_int *b, mp_int *c); /* ---> Basic arithmetic <--- */ /* b = -a */ -int mp_neg(const mp_int *a, mp_int *b); +int mp_neg(mp_int *a, mp_int *b); /* b = |a| */ int mp_abs(mp_int *a, mp_int *b); /* compare a to b */ -int mp_cmp(const mp_int *a, const mp_int *b); +int mp_cmp(mp_int *a, mp_int *b); /* compare |a| to |b| */ -int mp_cmp_mag(const mp_int *a, const mp_int *b); +int mp_cmp_mag(mp_int *a, mp_int *b); /* c = a + b */ int mp_add(mp_int *a, mp_int *b, mp_int *c); @@ -336,7 +328,7 @@ int mp_mod(mp_int *a, mp_int *b, mp_int *c); /* ---> single digit functions <--- */ /* compare against a single digit */ -int mp_cmp_d(const mp_int *a, mp_digit b); +int mp_cmp_d(mp_int *a, mp_digit b); /* c = a + b */ int mp_add_d(mp_int *a, mp_digit b, mp_int *c); @@ -355,7 +347,6 @@ int mp_div_3(mp_int *a, mp_int *c, mp_digit *d); /* c = a**b */ int mp_expt_d(mp_int *a, mp_digit b, mp_int *c); -int mp_expt_d_ex (mp_int * a, mp_digit b, mp_int * c, int fast); /* c = a mod b, 0 <= c < b */ int mp_mod_d(mp_int *a, mp_digit b, mp_digit *c); @@ -391,14 +382,10 @@ int mp_lcm(mp_int *a, mp_int *b, mp_int *c); * returns error if a < 0 and b is even */ int mp_n_root(mp_int *a, mp_digit b, mp_int *c); -int mp_n_root_ex (mp_int * a, mp_digit b, mp_int * c, int fast); /* special sqrt algo */ int mp_sqrt(mp_int *arg, mp_int *ret); -/* special sqrt (mod prime) */ -int mp_sqrtmod_prime(mp_int *arg, mp_int *prime, mp_int *ret); - /* is number a square? */ int mp_is_square(mp_int *arg, int *ret); @@ -460,13 +447,13 @@ int mp_exptmod(mp_int *a, mp_int *b, mp_int *c, mp_int *d); /* number of primes */ #ifdef MP_8BIT -# define PRIME_SIZE 31 + #define PRIME_SIZE 31 #else -# define PRIME_SIZE 256 + #define PRIME_SIZE 256 #endif /* table of first PRIME_SIZE primes */ -extern const mp_digit ltm_prime_tab[PRIME_SIZE]; +extern const mp_digit ltm_prime_tab[]; /* result=1 if a is divisible by one of the first PRIME_SIZE primes */ int mp_prime_is_divisible(mp_int *a, int *result); @@ -482,7 +469,7 @@ int mp_prime_fermat(mp_int *a, mp_int *b, int *result); int mp_prime_miller_rabin(mp_int *a, mp_int *b, int *result); /* This gives [for a given bit size] the number of trials required - * such that Miller-Rabin gives a prob of failure lower than 2^-96 + * such that Miller-Rabin gives a prob of failure lower than 2^-96 */ int mp_prime_rabin_miller_trials(int size); @@ -503,7 +490,7 @@ int mp_prime_is_prime(mp_int *a, int t, int *result); int mp_prime_next_prime(mp_int *a, int t, int bbs_style); /* makes a truly random prime of a given size (bytes), - * call with bbs = 1 if you want it to be congruent to 3 mod 4 + * call with bbs = 1 if you want it to be congruent to 3 mod 4 * * You have to supply a callback which fills in a buffer with random bytes. "dat" is a parameter you can * have passed to the callback (e.g. a state or something). This function doesn't use "dat" itself @@ -516,9 +503,10 @@ int mp_prime_next_prime(mp_int *a, int t, int bbs_style); /* makes a truly random prime of a given size (bits), * * Flags are as follows: - * + * * LTM_PRIME_BBS - make prime congruent to 3 mod 4 * LTM_PRIME_SAFE - make sure (p-1)/2 is prime as well (implies LTM_PRIME_BBS) + * LTM_PRIME_2MSB_OFF - make the 2nd highest bit zero * LTM_PRIME_2MSB_ON - make the 2nd highest bit one * * You have to supply a callback which fills in a buffer with random bytes. "dat" is a parameter you can @@ -529,7 +517,7 @@ int mp_prime_next_prime(mp_int *a, int t, int bbs_style); int mp_prime_random_ex(mp_int *a, int t, int size, int flags, ltm_prime_callback cb, void *dat); /* ---> radix conversion <--- */ -int mp_count_bits(const mp_int *a); +int mp_count_bits(mp_int *a); int mp_unsigned_bin_size(mp_int *a); int mp_read_unsigned_bin(mp_int *a, const unsigned char *b, int c); @@ -544,12 +532,10 @@ int mp_to_signed_bin_n (mp_int * a, unsigned char *b, unsigned long *outlen); int mp_read_radix(mp_int *a, const char *str, int radix); int mp_toradix(mp_int *a, char *str, int radix); int mp_toradix_n(mp_int * a, char *str, int radix, int maxlen); -int mp_radix_size(const mp_int *a, int radix, int *size); +int mp_radix_size(mp_int *a, int radix, int *size); -#ifndef LTM_NO_FILE int mp_fread(mp_int *a, int radix, FILE *stream); int mp_fwrite(mp_int *a, int radix, FILE *stream); -#endif #define mp_read_raw(mp, str, len) mp_read_signed_bin((mp), (str), (len)) #define mp_raw_size(mp) mp_signed_bin_size(mp) @@ -563,13 +549,31 @@ int mp_fwrite(mp_int *a, int radix, FILE *stream); #define mp_todecimal(M, S) mp_toradix((M), (S), 10) #define mp_tohex(M, S) mp_toradix((M), (S), 16) +/* lowlevel functions, do not call! */ +int s_mp_add(mp_int *a, mp_int *b, mp_int *c); +int s_mp_sub(mp_int *a, mp_int *b, mp_int *c); +#define s_mp_mul(a, b, c) s_mp_mul_digs(a, b, c, (a)->used + (b)->used + 1) +int fast_s_mp_mul_digs(mp_int *a, mp_int *b, mp_int *c, int digs); +int s_mp_mul_digs(mp_int *a, mp_int *b, mp_int *c, int digs); +int fast_s_mp_mul_high_digs(mp_int *a, mp_int *b, mp_int *c, int digs); +int s_mp_mul_high_digs(mp_int *a, mp_int *b, mp_int *c, int digs); +int fast_s_mp_sqr(mp_int *a, mp_int *b); +int s_mp_sqr(mp_int *a, mp_int *b); +int mp_karatsuba_mul(mp_int *a, mp_int *b, mp_int *c); +int mp_toom_mul(mp_int *a, mp_int *b, mp_int *c); +int mp_karatsuba_sqr(mp_int *a, mp_int *b); +int mp_toom_sqr(mp_int *a, mp_int *b); +int fast_mp_invmod(mp_int *a, mp_int *b, mp_int *c); +int mp_invmod_slow (mp_int * a, mp_int * b, mp_int * c); +int fast_mp_montgomery_reduce(mp_int *a, mp_int *m, mp_digit mp); +int mp_exptmod_fast(mp_int *G, mp_int *X, mp_int *P, mp_int *Y, int mode); +int s_mp_exptmod (mp_int * G, mp_int * X, mp_int * P, mp_int * Y, int mode); +void bn_reverse(unsigned char *s, int len); + +extern const char *mp_s_rmap; + #ifdef __cplusplus } #endif #endif - - -/* $Source$ */ -/* $Revision$ */ -/* $Date$ */ |