lib/silcmath/tfm.h

   1 /* TomsFastMath, a fast ISO C bignum library.
   2  *
   3  * This project is meant to fill in where LibTomMath
   4  * falls short.  That is speed ;-)
   5  *
   6  * This project is public domain and free for all purposes.
   7  *
   8  * Tom St Denis, tomstdenis@iahu.ca
   9  */
  10 #ifndef TFM_H_
  11 #define TFM_H_
  12
  13 #include <stdio.h>
  14 #include <string.h>
  15 #include <stdlib.h>
  16 #include <ctype.h>
  17 #include <limits.h>
  18
  19 /* Assure these -Pekka */
  20 #undef CRYPT
  21
  22 #undef MIN
  23 #define MIN(x,y) ((x)<(y)?(x):(y))
  24 #undef MAX
  25 #define MAX(x,y) ((x)>(y)?(x):(y))
  26
  27 /* do we want large code? */
  28 #define TFM_LARGE
  29
  30 /* do we want huge code (implies large)?  The answer is, yes. */
  31 #define TFM_HUGE
  32
  33 /* imply TFM_LARGE as required */
  34 #if defined(TFM_HUGE)
  35    #if !defined(TFM_LARGE)
  36       #define TFM_LARGE
  37    #endif
  38 #endif
  39
  40 /* Max size of any number in bits.  Basically the largest size you will be multiplying
  41  * should be half [or smaller] of FP_MAX_SIZE-four_digit
  42  *
  43  * You can externally define this or it defaults to 4096-bits.
  44  */
  45 #ifndef FP_MAX_SIZE
  46 /* For SILC -Pekka */
  47    #define FP_MAX_SIZE           (8192+(4*DIGIT_BIT))
  48 /*   #define FP_MAX_SIZE           (4096+(4*DIGIT_BIT))*/
  49 #endif
  50
  51 /* will this lib work? */
  52 #if (CHAR_BIT & 7)
  53    #error CHAR_BIT must be a multiple of eight.
  54 #endif
  55 #if FP_MAX_SIZE % CHAR_BIT
  56    #error FP_MAX_SIZE must be a multiple of CHAR_BIT
  57 #endif
  58
  59 /* autodetect x86-64 and make sure we are using 64-bit digits with x86-64 asm */
  60 #if defined(__x86_64__)
  61    #if defined(TFM_X86) || defined(TFM_SSE2) || defined(TFM_ARM)
  62        #error x86-64 detected, x86-32/SSE2/ARM optimizations are not valid!
  63    #endif
  64    #if !defined(TFM_X86_64) && !defined(TFM_NO_ASM)
  65       #define TFM_X86_64
  66    #endif
  67 #endif
  68 #if defined(TFM_X86_64)
  69     #if !defined(FP_64BIT)
  70        #define FP_64BIT
  71     #endif
  72 #endif
  73
  74 /* try to detect x86-32 */
  75 #if defined(__i386__) && !defined(TFM_SSE2)
  76    #if defined(TFM_X86_64) || defined(TFM_ARM)
  77        #error x86-32 detected, x86-64/ARM optimizations are not valid!
  78    #endif
  79    #if !defined(TFM_X86) && !defined(TFM_NO_ASM)
  80       #define TFM_X86
  81    #endif
  82 #endif
  83
  84 /* make sure we're 32-bit for x86-32/sse/arm */
  85 #if (defined(TFM_X86) || defined(TFM_SSE2) || defined(TFM_ARM)) && defined(FP_64BIT)
  86    #warning x86-32, SSE2 and ARM optimizations require 32-bit digits (undefining)
  87    #undef FP_64BIT
  88 #endif
  89
  90 /* multi asms? */
  91 #ifdef TFM_X86
  92    #define TFM_ASM
  93 #endif
  94 #ifdef TFM_X86_64
  95    #ifdef TFM_ASM
  96       #error TFM_ASM already defined!
  97    #endif
  98    #define TFM_ASM
  99 #endif
 100 #ifdef TFM_SSE2
 101    #ifdef TFM_ASM
 102       #error TFM_ASM already defined!
 103    #endif
 104    #define TFM_ASM
 105 #endif
 106 #ifdef TFM_ARM
 107    #ifdef TFM_ASM
 108       #error TFM_ASM already defined!
 109    #endif
 110    #define TFM_ASM
 111 #endif
 112
 113 /* we want no asm? */
 114 #ifdef TFM_NO_ASM
 115    #undef TFM_X86
 116    #undef TFM_X86_64
 117    #undef TFM_SSE2
 118    #undef TFM_ARM
 119    #undef TFM_ASM
 120 #endif
 121
 122 /* some default configurations.
 123  */
 124 #if defined(FP_64BIT)
 125    /* for GCC only on supported platforms */
 126 #ifndef CRYPT
 127    typedef unsigned long ulong64;
 128 #endif
 129    typedef ulong64            fp_digit;
 130    typedef unsigned long      fp_word __attribute__ ((mode(TI)));
 131 #else
 132    /* this is to make porting into LibTomCrypt easier :-) */
 133 #ifndef CRYPT
 134    #if defined(_MSC_VER) || defined(__BORLANDC__)
 135       typedef unsigned __int64   ulong64;
 136       typedef signed __int64     long64;
 137    #else
 138       typedef unsigned long long ulong64;
 139       typedef signed long long   long64;
 140    #endif
 141 #endif
 142    typedef unsigned long      fp_digit;
 143    typedef ulong64            fp_word;
 144 #endif
 145
 146 /* # of digits this is */
 147 #define DIGIT_BIT  (int)((CHAR_BIT) * sizeof(fp_digit))
 148 #define FP_MASK    (fp_digit)(-1)
 149 #define FP_SIZE    (FP_MAX_SIZE/DIGIT_BIT)
 150
 151 /* signs */
 152 #define FP_ZPOS     0
 153 #define FP_NEG      1
 154
 155 /* return codes */
 156 #define FP_OKAY     0
 157 #define FP_VAL      1
 158 #define FP_MEM      2
 159
 160 /* equalities */
 161 #define FP_LT        -1   /* less than */
 162 #define FP_EQ         0   /* equal to */
 163 #define FP_GT         1   /* greater than */
 164
 165 /* replies */
 166 #define FP_YES        1   /* yes response */
 167 #define FP_NO         0   /* no response */
 168
 169 /* a FP type */
 170 typedef struct {
 171     fp_digit dp[FP_SIZE];
 172     int      used,
 173              sign;
 174 } fp_int;
 175
 176 /* functions */
 177
 178 /* returns a TFM ident string useful for debugging... */
 179 const char *fp_ident(void);
 180
 181 /* initialize [or zero] an fp int */
 182 #define fp_init(a)  (void)memset((a), 0, sizeof(fp_int))
 183 #define fp_zero(a)  fp_init(a)
 184
 185 /* zero/even/odd ? */
 186 #define fp_iszero(a) (((a)->used == 0) ? FP_YES : FP_NO)
 187 #define fp_iseven(a) (((a)->used > 0 && (((a)->dp[0] & 1) == 0)) ? FP_YES : FP_NO)
 188 #define fp_isodd(a)  (((a)->used > 0 && (((a)->dp[0] & 1) == 1)) ? FP_YES : FP_NO)
 189
 190 /* set to a small digit */
 191 void fp_set(fp_int *a, fp_digit b);
 192
 193 /* copy from a to b */
 194 #define fp_copy(a, b)      (void)(((a) != (b)) && memcpy((b), (a), sizeof(fp_int)))
 195 #define fp_init_copy(a, b) fp_copy(b, a)
 196
 197 /* negate and absolute */
 198 #define fp_neg(a, b)  { fp_copy(a, b); (b)->sign ^= 1; }
 199 #define fp_abs(a, b)  { fp_copy(a, b); (b)->sign  = 0; }
 200
 201 /* clamp digits */
 202 #define fp_clamp(a)   { while ((a)->used && (a)->dp[(a)->used-1] == 0) --((a)->used); (a)->sign = (a)->used ? (a)->sign : FP_ZPOS; }
 203
 204 /* right shift x digits */
 205 void fp_rshd(fp_int *a, int x);
 206
 207 /* left shift x digits */
 208 void fp_lshd(fp_int *a, int x);
 209
 210 /* signed comparison */
 211 int fp_cmp(fp_int *a, fp_int *b);
 212
 213 /* unsigned comparison */
 214 int fp_cmp_mag(fp_int *a, fp_int *b);
 215
 216 /* power of 2 operations */
 217 void fp_div_2d(fp_int *a, int b, fp_int *c, fp_int *d);
 218 void fp_mod_2d(fp_int *a, int b, fp_int *c);
 219 void fp_mul_2d(fp_int *a, int b, fp_int *c);
 220 void fp_2expt (fp_int *a, int b);
 221 void fp_mul_2(fp_int *a, fp_int *c);
 222 void fp_div_2(fp_int *a, fp_int *c);
 223
 224 /* Counts the number of lsbs which are zero before the first zero bit */
 225 int fp_cnt_lsb(fp_int *a);
 226
 227 /* c = a + b */
 228 void fp_add(fp_int *a, fp_int *b, fp_int *c);
 229
 230 /* c = a - b */
 231 void fp_sub(fp_int *a, fp_int *b, fp_int *c);
 232
 233 /* c = a * b */
 234 void fp_mul(fp_int *a, fp_int *b, fp_int *c);
 235
 236 /* b = a*a  */
 237 void fp_sqr(fp_int *a, fp_int *b);
 238
 239 /* a/b => cb + d == a */
 240 int fp_div(fp_int *a, fp_int *b, fp_int *c, fp_int *d);
 241
 242 /* c = a mod b, 0 <= c < b  */
 243 int fp_mod(fp_int *a, fp_int *b, fp_int *c);
 244
 245 /* compare against a single digit */
 246 int fp_cmp_d(fp_int *a, fp_digit b);
 247
 248 /* c = a + b */
 249 void fp_add_d(fp_int *a, fp_digit b, fp_int *c);
 250
 251 /* c = a - b */
 252 void fp_sub_d(fp_int *a, fp_digit b, fp_int *c);
 253
 254 /* c = a * b */
 255 void fp_mul_d(fp_int *a, fp_digit b, fp_int *c);
 256
 257 /* a/b => cb + d == a */
 258 int fp_div_d(fp_int *a, fp_digit b, fp_int *c, fp_digit *d);
 259
 260 /* c = a mod b, 0 <= c < b  */
 261 int fp_mod_d(fp_int *a, fp_digit b, fp_digit *c);
 262
 263 /* ---> number theory <--- */
 264 /* d = a + b (mod c) */
 265 int fp_addmod(fp_int *a, fp_int *b, fp_int *c, fp_int *d);
 266
 267 /* d = a - b (mod c) */
 268 int fp_submod(fp_int *a, fp_int *b, fp_int *c, fp_int *d);
 269
 270 /* d = a * b (mod c) */
 271 int fp_mulmod(fp_int *a, fp_int *b, fp_int *c, fp_int *d);
 272
 273 /* c = a * a (mod b) */
 274 int fp_sqrmod(fp_int *a, fp_int *b, fp_int *c);
 275
 276 /* c = 1/a (mod b) */
 277 int fp_invmod(fp_int *a, fp_int *b, fp_int *c);
 278
 279 /* c = (a, b) */
 280 void fp_gcd(fp_int *a, fp_int *b, fp_int *c);
 281
 282 /* c = [a, b] */
 283 void fp_lcm(fp_int *a, fp_int *b, fp_int *c);
 284
 285 /* setups the montgomery reduction */
 286 int fp_montgomery_setup(fp_int *a, fp_digit *mp);
 287
 288 /* computes a = B**n mod b without division or multiplication useful for
 289  * normalizing numbers in a Montgomery system.
 290  */
 291 void fp_montgomery_calc_normalization(fp_int *a, fp_int *b);
 292
 293 /* computes x/R == x (mod N) via Montgomery Reduction */
 294 void fp_montgomery_reduce(fp_int *a, fp_int *m, fp_digit mp);
 295
 296 /* d = a**b (mod c) */
 297 int fp_exptmod(fp_int *a, fp_int *b, fp_int *c, fp_int *d);
 298
 299 /* primality stuff */
 300
 301 /* perform a Miller-Rabin test of a to the base b and store result in "result" */
 302 void fp_prime_miller_rabin (fp_int * a, fp_int * b, int *result);
 303
 304 /* 256 trial divisions + 8 Miller-Rabins, returns FP_YES if probable prime  */
 305 int fp_isprime(fp_int *a);
 306
 307 /* Primality generation flags */
 308 #define TFM_PRIME_BBS      0x0001 /* BBS style prime */
 309 #define TFM_PRIME_SAFE     0x0002 /* Safe prime (p-1)/2 == prime */
 310 #define TFM_PRIME_2MSB_OFF 0x0004 /* force 2nd MSB to 0 */
 311 #define TFM_PRIME_2MSB_ON  0x0008 /* force 2nd MSB to 1 */
 312
 313 /* callback for fp_prime_random, should fill dst with random bytes and return how many read [upto len] */
 314 typedef int tfm_prime_callback(unsigned char *dst, int len, void *dat);
 315
 316 #define fp_prime_random(a, t, size, bbs, cb, dat) fp_prime_random_ex(a, t, ((size) * 8) + 1, (bbs==1)?TFM_PRIME_BBS:0, cb, dat)
 317
 318 int fp_prime_random_ex(fp_int *a, int t, int size, int flags, tfm_prime_callback cb, void *dat);
 319
 320 /* radix conersions */
 321 int fp_count_bits(fp_int *a);
 322
 323 int fp_unsigned_bin_size(fp_int *a);
 324 void fp_read_unsigned_bin(fp_int *a, unsigned char *b, int c);
 325 void fp_to_unsigned_bin(fp_int *a, unsigned char *b);
 326
 327 int fp_signed_bin_size(fp_int *a);
 328 void fp_read_signed_bin(fp_int *a, unsigned char *b, int c);
 329 void fp_to_signed_bin(fp_int *a, unsigned char *b);
 330
 331 int fp_read_radix(fp_int *a, char *str, int radix);
 332 int fp_toradix(fp_int *a, char *str, int radix);
 333 int fp_toradix_n(fp_int * a, char *str, int radix, int maxlen);
 334 int fp_radix_size(fp_int *a, int radix, int *size);
 335
 336 /* VARIOUS LOW LEVEL STUFFS */
 337 void s_fp_add(fp_int *a, fp_int *b, fp_int *c);
 338 void s_fp_sub(fp_int *a, fp_int *b, fp_int *c);
 339 void bn_reverse(unsigned char *s, int len);
 340 void fp_mul_comba(fp_int *A, fp_int *B, fp_int *C);
 341 #ifdef TFM_HUGE
 342 void fp_mul_comba32(fp_int *A, fp_int *B, fp_int *C);
 343 #endif
 344 #ifdef TFM_LARGE
 345 void fp_mul_comba16(fp_int *A, fp_int *B, fp_int *C);
 346 #endif
 347 void fp_mul_comba8(fp_int *A, fp_int *B, fp_int *C);
 348 void fp_mul_comba4(fp_int *A, fp_int *B, fp_int *C);
 349
 350 void fp_sqr_comba(fp_int *A, fp_int *B);
 351 void fp_sqr_comba4(fp_int *A, fp_int *B);
 352 void fp_sqr_comba8(fp_int *A, fp_int *B);
 353 #ifdef TFM_LARGE
 354 void fp_sqr_comba16(fp_int *A, fp_int *B);
 355 #endif
 356 #ifdef TFM_HUGE
 357 void fp_sqr_comba32(fp_int *A, fp_int *B);
 358 void fp_sqr_comba64(fp_int *A, fp_int *B);
 359 #endif
 360 extern const char *fp_s_rmap;
 361
 362 #endif