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@gmail.com
   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 typedef struct tfm_fp_int_struct tfm_fp_int;
  20
  21 #include <silccrypto.h>
  22
  23 #undef CRYPT
  24
  25 #ifdef SILC_X86_64
  26 #define TFM_X86_64
  27 #endif /* SILC_X86_64 */
  28
  29 #ifdef SILC_I386
  30 #define TFM_X86
  31 #ifdef SILC_CPU_SSE2
  32 #define TFM_SSE2
  33 #endif /* SILC_CPU_SSE2 */
  34 #endif /* SILC_I386 */
  35
  36 #ifndef MIN
  37    #define MIN(x,y) ((x)<(y)?(x):(y))
  38 #endif
  39
  40 #ifndef MAX
  41    #define MAX(x,y) ((x)>(y)?(x):(y))
  42 #endif
  43
  44 /* externally define this symbol to ignore the default settings, useful for changing the build from the make process */
  45 #ifndef TFM_ALREADY_SET
  46
  47 /* do we want the large set of small multiplications ?
  48    Enable these if you are going to be doing a lot of small (<= 16 digit) multiplications say in ECC
  49    Or if you're on a 64-bit machine doing RSA as a 1024-bit integer == 16 digits ;-)
  50  */
  51 #define TFM_SMALL_SET
  52
  53 /* do we want huge code
  54    Enable these if you are doing 20, 24, 28, 32, 48, 64 digit multiplications (useful for RSA)
  55    Less important on 64-bit machines as 32 digits == 2048 bits
  56  */
  57 #define TFM_MUL20
  58 #define TFM_MUL24
  59 #define TFM_MUL28
  60 #define TFM_MUL32
  61 #define TFM_MUL48
  62 #define TFM_MUL64
  63
  64 #define TFM_SQR20
  65 #define TFM_SQR24
  66 #define TFM_SQR28
  67 #define TFM_SQR32
  68 #define TFM_SQR48
  69 #define TFM_SQR64
  70
  71 /* do we want some overflow checks
  72    Not required if you make sure your numbers are within range (e.g. by default a modulus for tfm_fp_exptmod() can only be upto 2048 bits long)
  73  */
  74 #define TFM_CHECK
  75
  76 /* Is the target a P4 Prescott
  77  */
  78 /* #define TFM_PRESCOTT */
  79
  80 /* Do we want timing resistant tfm_fp_exptmod() ?
  81  * This makes it slower but also timing invariant with respect to the exponent
  82  */
  83 /* #define TFM_TIMING_RESISTANT */
  84
  85 #endif
  86
  87 /* Max size of any number in bits.  Basically the largest size you will be multiplying
  88  * should be half [or smaller] of TFM_FP_MAX_SIZE-four_digit
  89  *
  90  * You can externally define this or it defaults to 4096-bits [allowing multiplications upto 2048x2048 bits ]
  91  */
  92 #ifndef TFM_FP_MAX_SIZE
  93    #define TFM_FP_MAX_SIZE           (8192+(8*DIGIT_BIT))
  94 #endif
  95
  96 /* will this lib work? */
  97 #if (CHAR_BIT & 7)
  98    #error CHAR_BIT must be a multiple of eight.
  99 #endif
 100 #if TFM_FP_MAX_SIZE % CHAR_BIT
 101    #error TFM_FP_MAX_SIZE must be a multiple of CHAR_BIT
 102 #endif
 103
 104 /* autodetect x86-64 and make sure we are using 64-bit digits with x86-64 asm */
 105 #if defined(__x86_64__)
 106    #if defined(TFM_X86) || defined(TFM_SSE2) || defined(TFM_ARM)
 107        #error x86-64 detected, x86-32/SSE2/ARM optimizations are not valid!
 108    #endif
 109    #if !defined(TFM_X86_64) && !defined(TFM_NO_ASM)
 110       #define TFM_X86_64
 111    #endif
 112 #endif
 113 #if defined(TFM_X86_64)
 114     #if !defined(TFM_FP_64BIT)
 115        #define TFM_FP_64BIT
 116     #endif
 117 #endif
 118
 119 /* try to detect x86-32 */
 120 #if defined(__i386__) && !defined(TFM_SSE2)
 121    #if defined(TFM_X86_64) || defined(TFM_ARM)
 122        #error x86-32 detected, x86-64/ARM optimizations are not valid!
 123    #endif
 124    #if !defined(TFM_X86) && !defined(TFM_NO_ASM)
 125       #define TFM_X86
 126    #endif
 127 #endif
 128
 129 /* make sure we're 32-bit for x86-32/sse/arm/ppc32 */
 130 #if (defined(TFM_X86) || defined(TFM_SSE2) || defined(TFM_ARM) || defined(TFM_PPC32)) && defined(TFM_FP_64BIT)
 131    #warning x86-32, SSE2 and ARM, PPC32 optimizations require 32-bit digits (undefining)
 132    #undef TFM_FP_64BIT
 133 #endif
 134
 135 /* multi asms? */
 136 #ifdef TFM_X86
 137    #define TFM_ASM
 138 #endif
 139 #ifdef TFM_X86_64
 140    #ifdef TFM_ASM
 141       #error TFM_ASM already defined!
 142    #endif
 143    #define TFM_ASM
 144 #endif
 145 #ifdef TFM_SSE2
 146    #ifdef TFM_ASM
 147       #error TFM_ASM already defined!
 148    #endif
 149    #define TFM_ASM
 150 #endif
 151 #ifdef TFM_ARM
 152    #ifdef TFM_ASM
 153       #error TFM_ASM already defined!
 154    #endif
 155    #define TFM_ASM
 156 #endif
 157 #ifdef TFM_PPC32
 158    #ifdef TFM_ASM
 159       #error TFM_ASM already defined!
 160    #endif
 161    #define TFM_ASM
 162 #endif
 163 #ifdef TFM_PPC64
 164    #ifdef TFM_ASM
 165       #error TFM_ASM already defined!
 166    #endif
 167    #define TFM_ASM
 168 #endif
 169 #ifdef TFM_AVR32
 170    #ifdef TFM_ASM
 171       #error TFM_ASM already defined!
 172    #endif
 173    #define TFM_ASM
 174 #endif
 175
 176 /* we want no asm? */
 177 #ifdef TFM_NO_ASM
 178    #undef TFM_X86
 179    #undef TFM_X86_64
 180    #undef TFM_SSE2
 181    #undef TFM_ARM
 182    #undef TFM_PPC32
 183    #undef TFM_PPC64
 184    #undef TFM_AVR32
 185    #undef TFM_ASM
 186 #endif
 187
 188 /* ECC helpers */
 189 #ifdef TFM_ECC192
 190    #ifdef TFM_FP_64BIT
 191        #define TFM_MUL3
 192        #define TFM_SQR3
 193    #else
 194        #define TFM_MUL6
 195        #define TFM_SQR6
 196    #endif
 197 #endif
 198
 199 #ifdef TFM_ECC224
 200    #ifdef TFM_FP_64BIT
 201        #define TFM_MUL4
 202        #define TFM_SQR4
 203    #else
 204        #define TFM_MUL7
 205        #define TFM_SQR7
 206    #endif
 207 #endif
 208
 209 #ifdef TFM_ECC256
 210    #ifdef TFM_FP_64BIT
 211        #define TFM_MUL4
 212        #define TFM_SQR4
 213    #else
 214        #define TFM_MUL8
 215        #define TFM_SQR8
 216    #endif
 217 #endif
 218
 219 #ifdef TFM_ECC384
 220    #ifdef TFM_FP_64BIT
 221        #define TFM_MUL6
 222        #define TFM_SQR6
 223    #else
 224        #define TFM_MUL12
 225        #define TFM_SQR12
 226    #endif
 227 #endif
 228
 229 #ifdef TFM_ECC521
 230    #ifdef TFM_FP_64BIT
 231        #define TFM_MUL9
 232        #define TFM_SQR9
 233    #else
 234        #define TFM_MUL17
 235        #define TFM_SQR17
 236    #endif
 237 #endif
 238
 239
 240 /* some default configurations.
 241  */
 242 #if defined(TFM_FP_64BIT)
 243    /* for GCC only on supported platforms */
 244 #ifndef CRYPT
 245    typedef SilcUInt64 ulong64;
 246 #endif
 247    typedef ulong64            tfm_fp_digit;
 248    typedef unsigned long      tfm_fp_word __attribute__ ((mode(TI)));
 249 #else
 250    /* this is to make porting into LibTomCrypt easier :-) */
 251 #ifndef CRYPT
 252    #if defined(_MSC_VER) || defined(__BORLANDC__)
 253       typedef unsigned __int64   ulong64;
 254       typedef signed __int64     long64;
 255    #else
 256       typedef unsigned long long ulong64;
 257       typedef signed long long   long64;
 258    #endif
 259 #endif
 260    typedef unsigned long      tfm_fp_digit;
 261    typedef ulong64            tfm_fp_word;
 262 #endif
 263
 264 /* # of digits this is */
 265 #define DIGIT_BIT  (int)((CHAR_BIT) * sizeof(tfm_fp_digit))
 266 #define TFM_FP_MASK    (tfm_fp_digit)(-1)
 267 #define TFM_FP_SIZE    (TFM_FP_MAX_SIZE/DIGIT_BIT)
 268
 269 /* signs */
 270 #define TFM_FP_ZPOS     0
 271 #define TFM_FP_NEG      1
 272
 273 /* return codes */
 274 #define TFM_FP_OKAY     0
 275 #define TFM_FP_VAL      1
 276 #define TFM_FP_MEM      2
 277
 278 /* equalities */
 279 #define TFM_FP_LT        -1   /* less than */
 280 #define TFM_FP_EQ         0   /* equal to */
 281 #define TFM_FP_GT         1   /* greater than */
 282
 283 /* replies */
 284 #define TFM_FP_YES        1   /* yes response */
 285 #define TFM_FP_NO         0   /* no response */
 286
 287 /* a FP type */
 288 struct tfm_fp_int_struct {
 289   SilcStack stack;
 290   tfm_fp_digit *dp;
 291   unsigned int used;
 292   unsigned int alloc : 31;
 293   unsigned int sign  : 1;
 294 };
 295
 296 /* functions */
 297
 298 /* initialize [or zero] an fp int */
 299 #define tfm_fp_init(a) tfm_fp_sinit(NULL, a)
 300 #define tfm_fp_sinit(s, a)                                              \
 301   { (a)->stack = s; (a)->dp = NULL; (a)->alloc = (a)->used = (a)->sign = 0; }
 302 int tfm_fp_init_size(SilcStack stack, tfm_fp_int *a, int size);
 303 void tfm_fp_zero(tfm_fp_int *a);
 304
 305 /* zero/even/odd ? */
 306 #define tfm_fp_iszero(a) (((a)->used == 0) ? TFM_FP_YES : TFM_FP_NO)
 307 #define tfm_fp_iseven(a) (((a)->used >= 0 && (((a)->dp[0] & 1) == 0)) ? TFM_FP_YES : TFM_FP_NO)
 308 #define tfm_fp_isodd(a)  (((a)->used > 0  && (((a)->dp[0] & 1) == 1)) ? TFM_FP_YES : TFM_FP_NO)
 309
 310 /* set to a small digit */
 311 int tfm_fp_set(tfm_fp_int *a, tfm_fp_digit b);
 312
 313 /* copy from a to b */
 314 int tfm_fp_copy(tfm_fp_int *a, tfm_fp_int *b);
 315 int tfm_fp_init_copy(tfm_fp_int *a, tfm_fp_int *b, SilcStack stack);
 316 void tfm_fp_exch(tfm_fp_int *a, tfm_fp_int *b);
 317
 318 /* clamp digits */
 319 #define tfm_fp_clamp(a)   { while ((a)->used && (a)->dp[(a)->used-1] == 0) --((a)->used); (a)->sign = (a)->used ? (a)->sign : TFM_FP_ZPOS; }
 320
 321 /* negate and absolute */
 322 #define tfm_fp_neg(a, b)  { tfm_fp_copy(a, b); (b)->sign ^= 1; tfm_fp_clamp(b); }
 323 #define tfm_fp_abs(a, b)  { tfm_fp_copy(a, b); (b)->sign  = 0; }
 324
 325 /* right shift x digits */
 326 void tfm_fp_rshd(tfm_fp_int *a, int x);
 327
 328 /* left shift x digits */
 329 int tfm_fp_lshd(tfm_fp_int *a, int x);
 330
 331 /* signed comparison */
 332 int tfm_fp_cmp(tfm_fp_int *a, tfm_fp_int *b);
 333
 334 /* unsigned comparison */
 335 int tfm_fp_cmp_mag(tfm_fp_int *a, tfm_fp_int *b);
 336
 337 /* power of 2 operations */
 338 int tfm_fp_div_2d(tfm_fp_int *a, int b, tfm_fp_int *c, tfm_fp_int *d);
 339 int tfm_fp_mod_2d(tfm_fp_int *a, int b, tfm_fp_int *c);
 340 int tfm_fp_mul_2d(tfm_fp_int *a, int b, tfm_fp_int *c);
 341 int tfm_fp_2expt (tfm_fp_int *a, int b);
 342 int tfm_fp_mul_2(tfm_fp_int *a, tfm_fp_int *c);
 343 int tfm_fp_div_2(tfm_fp_int *a, tfm_fp_int *c);
 344
 345 /* Counts the number of lsbs which are zero before the first zero bit */
 346 int tfm_fp_cnt_lsb(tfm_fp_int *a);
 347
 348 /* c = a + b */
 349 int tfm_fp_add(tfm_fp_int *a, tfm_fp_int *b, tfm_fp_int *c);
 350
 351 /* c = a - b */
 352 int tfm_fp_sub(tfm_fp_int *a, tfm_fp_int *b, tfm_fp_int *c);
 353
 354 /* c = a * b */
 355 int tfm_fp_mul(tfm_fp_int *a, tfm_fp_int *b, tfm_fp_int *c);
 356
 357 /* b = a*a  */
 358 int tfm_fp_sqr(tfm_fp_int *a, tfm_fp_int *b);
 359
 360 /* a/b => cb + d == a */
 361 int tfm_fp_div(tfm_fp_int *a, tfm_fp_int *b, tfm_fp_int *c, tfm_fp_int *d);
 362
 363 /* c = a mod b, 0 <= c < b  */
 364 int tfm_fp_mod(tfm_fp_int *a, tfm_fp_int *b, tfm_fp_int *c);
 365
 366 /* compare against a single digit */
 367 int tfm_fp_cmp_d(tfm_fp_int *a, tfm_fp_digit b);
 368
 369 /* c = a + b */
 370 int tfm_fp_add_d(tfm_fp_int *a, tfm_fp_digit b, tfm_fp_int *c);
 371
 372 /* c = a - b */
 373 int tfm_fp_sub_d(tfm_fp_int *a, tfm_fp_digit b, tfm_fp_int *c);
 374
 375 /* c = a * b */
 376 int tfm_fp_mul_d(tfm_fp_int *a, tfm_fp_digit b, tfm_fp_int *c);
 377
 378 /* a/b => cb + d == a */
 379 int tfm_fp_div_d(tfm_fp_int *a, tfm_fp_digit b, tfm_fp_int *c, tfm_fp_digit *d);
 380
 381 /* c = a mod b, 0 <= c < b  */
 382 int tfm_fp_mod_d(tfm_fp_int *a, tfm_fp_digit b, tfm_fp_digit *c);
 383
 384 /* ---> number theory <--- */
 385 /* d = a + b (mod c) */
 386 int tfm_fp_addmod(tfm_fp_int *a, tfm_fp_int *b, tfm_fp_int *c, tfm_fp_int *d);
 387
 388 /* d = a - b (mod c) */
 389 int tfm_fp_submod(tfm_fp_int *a, tfm_fp_int *b, tfm_fp_int *c, tfm_fp_int *d);
 390
 391 /* d = a * b (mod c) */
 392 int tfm_fp_mulmod(tfm_fp_int *a, tfm_fp_int *b, tfm_fp_int *c, tfm_fp_int *d);
 393
 394 /* c = a * a (mod b) */
 395 int tfm_fp_sqrmod(tfm_fp_int *a, tfm_fp_int *b, tfm_fp_int *c);
 396
 397 /* c = 1/a (mod b) */
 398 int tfm_fp_invmod(tfm_fp_int *a, tfm_fp_int *b, tfm_fp_int *c);
 399
 400 /* c = (a, b) */
 401 int tfm_fp_gcd(tfm_fp_int *a, tfm_fp_int *b, tfm_fp_int *c);
 402
 403 /* c = [a, b] */
 404 int tfm_fp_lcm(tfm_fp_int *a, tfm_fp_int *b, tfm_fp_int *c);
 405
 406 int tfm_fp_sqrt(tfm_fp_int *arg, tfm_fp_int *ret);
 407 int tfm_fp_expt_d(tfm_fp_int * a, tfm_fp_digit b, tfm_fp_int * c);
 408 int tfm_fp_xor(tfm_fp_int * a, tfm_fp_int * b, tfm_fp_int * c);
 409 int tfm_fp_and(tfm_fp_int * a, tfm_fp_int * b, tfm_fp_int * c);
 410 int tfm_fp_or(tfm_fp_int * a, tfm_fp_int * b, tfm_fp_int * c);
 411
 412 /* setups the montgomery reduction */
 413 int tfm_fp_montgomery_setup(tfm_fp_int *a, tfm_fp_digit *mp);
 414
 415 /* computes a = B**n mod b without division or multiplication useful for
 416  * normalizing numbers in a Montgomery system.
 417  */
 418 int tfm_fp_montgomery_calc_normalization(tfm_fp_int *a, tfm_fp_int *b);
 419
 420 /* computes x/R == x (mod N) via Montgomery Reduction */
 421 int tfm_fp_montgomery_reduce(tfm_fp_int *a, tfm_fp_int *m, tfm_fp_digit mp);
 422
 423 /* d = a**b (mod c) */
 424 int tfm_fp_exptmod(tfm_fp_int *a, tfm_fp_int *b, tfm_fp_int *c, tfm_fp_int *d);
 425
 426 /* radix conersions */
 427 int tfm_fp_count_bits(tfm_fp_int *a);
 428
 429 int tfm_fp_unsigned_bin_size(tfm_fp_int *a);
 430 void tfm_fp_read_unsigned_bin(tfm_fp_int *a, unsigned char *b, int c);
 431 void tfm_fp_to_unsigned_bin(tfm_fp_int *a, unsigned char *b);
 432
 433 int tfm_fp_signed_bin_size(tfm_fp_int *a);
 434 void tfm_fp_to_signed_bin(tfm_fp_int *a, unsigned char *b);
 435
 436 int tfm_fp_read_radix(tfm_fp_int *a, char *str, int radix);
 437 int tfm_fp_toradix(tfm_fp_int *a, char *str, int radix);
 438 int tfm_fp_toradix_n(tfm_fp_int * a, char *str, int radix, int maxlen);
 439 int tfm_fp_radix_size(tfm_fp_int *a, int radix, int *size);
 440
 441
 442 /* VARIOUS LOW LEVEL STUFFS */
 443 int s_tfm_fp_add(tfm_fp_int *a, tfm_fp_int *b, tfm_fp_int *c);
 444 int s_tfm_fp_sub(tfm_fp_int *a, tfm_fp_int *b, tfm_fp_int *c);
 445 void tfm_fp_reverse(unsigned char *s, int len);
 446
 447 int tfm_fp_mul_comba(tfm_fp_int *A, tfm_fp_int *B, tfm_fp_int *C);
 448
 449 #ifdef TFM_SMALL_SET
 450 void tfm_fp_mul_comba_small(tfm_fp_int *A, tfm_fp_int *B, tfm_fp_int *C);
 451 #endif
 452
 453 #ifdef TFM_MUL20
 454 void tfm_fp_mul_comba20(tfm_fp_int *A, tfm_fp_int *B, tfm_fp_int *C);
 455 #endif
 456 #ifdef TFM_MUL24
 457 void tfm_fp_mul_comba24(tfm_fp_int *A, tfm_fp_int *B, tfm_fp_int *C);
 458 #endif
 459 #ifdef TFM_MUL28
 460 void tfm_fp_mul_comba28(tfm_fp_int *A, tfm_fp_int *B, tfm_fp_int *C);
 461 #endif
 462 #ifdef TFM_MUL32
 463 void tfm_fp_mul_comba32(tfm_fp_int *A, tfm_fp_int *B, tfm_fp_int *C);
 464 #endif
 465 #ifdef TFM_MUL48
 466 void tfm_fp_mul_comba48(tfm_fp_int *A, tfm_fp_int *B, tfm_fp_int *C);
 467 #endif
 468 #ifdef TFM_MUL64
 469 void tfm_fp_mul_comba64(tfm_fp_int *A, tfm_fp_int *B, tfm_fp_int *C);
 470 #endif
 471
 472 int tfm_fp_sqr_comba(tfm_fp_int *A, tfm_fp_int *B);
 473
 474 #ifdef TFM_SMALL_SET
 475 void tfm_fp_sqr_comba_small(tfm_fp_int *A, tfm_fp_int *B);
 476 #endif
 477
 478 #ifdef TFM_SQR20
 479 void tfm_fp_sqr_comba20(tfm_fp_int *A, tfm_fp_int *B);
 480 #endif
 481 #ifdef TFM_SQR24
 482 void tfm_fp_sqr_comba24(tfm_fp_int *A, tfm_fp_int *B);
 483 #endif
 484 #ifdef TFM_SQR28
 485 void tfm_fp_sqr_comba28(tfm_fp_int *A, tfm_fp_int *B);
 486 #endif
 487 #ifdef TFM_SQR32
 488 void tfm_fp_sqr_comba32(tfm_fp_int *A, tfm_fp_int *B);
 489 #endif
 490 #ifdef TFM_SQR48
 491 void tfm_fp_sqr_comba48(tfm_fp_int *A, tfm_fp_int *B);
 492 #endif
 493 #ifdef TFM_SQR64
 494 void tfm_fp_sqr_comba64(tfm_fp_int *A, tfm_fp_int *B);
 495 #endif
 496
 497 #endif