tfm.h

00001 /* TomsFastMath, a fast ISO C bignum library.
00002  * 
00003  * This project is meant to fill in where LibTomMath
00004  * falls short.  That is speed ;-)
00005  *
00006  * This project is public domain and free for all purposes.
00007  * 
00008  * Tom St Denis, tomstdenis@gmail.com
00009  */
00010 #ifndef TFM_H_
00011 #define TFM_H_
00012 
00013 #include <stdio.h>
00014 #include <string.h>
00015 #include <stdint.h>
00016 #include <stdlib.h>
00017 #include <ctype.h>
00018 #include <limits.h>
00019 
00020 /* Specific Config */
00021 #include "inc/minitls_config.h"
00022 #define TFM_ECC192 CRYPTO_ECC192 //Enable stuff needed for ECC 192 computations
00023 #define TFM_NO_ASM 1
00024 #define TFM_TIMING_RESISTANT //Slower but fixed computation times and lower stack usage
00025 #define FP_MAX_SIZE 2*(DIGIT_BIT+CRYPTO_MAX_KEY_SIZE)//ECC192 max
00026 
00027 /* */
00028 
00029 #ifndef MIN
00030    #define MIN(x,y) ((x)<(y)?(x):(y))
00031 #endif
00032 
00033 #ifndef MAX
00034    #define MAX(x,y) ((x)>(y)?(x):(y))
00035 #endif
00036 
00037 /* externally define this symbol to ignore the default settings, useful for changing the build from the make process */
00038 #ifndef TFM_ALREADY_SET
00039 
00040 /* do we want the large set of small multiplications ? 
00041    Enable these if you are going to be doing a lot of small (<= 16 digit) multiplications say in ECC
00042    Or if you're on a 64-bit machine doing RSA as a 1024-bit integer == 16 digits ;-)
00043  */
00044 //#define TFM_SMALL_SET
00045 
00046 /* do we want huge code 
00047    Enable these if you are doing 20, 24, 28, 32, 48, 64 digit multiplications (useful for RSA)
00048    Less important on 64-bit machines as 32 digits == 2048 bits
00049  */
00050 #if 0 //DG
00051 #if 0
00052 #define TFM_MUL3
00053 #define TFM_MUL4
00054 #define TFM_MUL6
00055 #define TFM_MUL7
00056 #define TFM_MUL8
00057 #define TFM_MUL9
00058 #define TFM_MUL12
00059 #define TFM_MUL17
00060 #endif
00061 #define TFM_MUL20
00062 #define TFM_MUL24
00063 #define TFM_MUL28
00064 #define TFM_MUL32
00065 #define TFM_MUL48
00066 #define TFM_MUL64
00067 #if 0
00068 #define TFM_SQR3
00069 #define TFM_SQR4
00070 #define TFM_SQR6
00071 #define TFM_SQR7
00072 #define TFM_SQR8
00073 #define TFM_SQR9
00074 #define TFM_SQR12
00075 #define TFM_SQR17
00076 #endif
00077 #define TFM_SQR20
00078 #define TFM_SQR24
00079 #define TFM_SQR28
00080 #define TFM_SQR32
00081 #define TFM_SQR48
00082 #define TFM_SQR64
00083 #endif
00084 
00085 /* do we want some overflow checks
00086    Not required if you make sure your numbers are within range (e.g. by default a modulus for fp_exptmod() can only be upto 2048 bits long)
00087  */
00088 /* #define TFM_CHECK */
00089 
00090 /* Is the target a P4 Prescott
00091  */
00092 /* #define TFM_PRESCOTT */
00093 
00094 /* Do we want timing resistant fp_exptmod() ?
00095  * This makes it slower but also timing invariant with respect to the exponent 
00096  */
00097 //#define TFM_TIMING_RESISTANT
00098 
00099 #endif
00100 
00101 /* Max size of any number in bits.  Basically the largest size you will be multiplying
00102  * should be half [or smaller] of FP_MAX_SIZE-four_digit
00103  *
00104  * You can externally define this or it defaults to 4096-bits [allowing multiplications upto 2048x2048 bits ]
00105  */
00106 #ifndef FP_MAX_SIZE
00107    #define FP_MAX_SIZE           (4096+(8*DIGIT_BIT))
00108 #endif
00109 
00110 /* will this lib work? */
00111 #if (CHAR_BIT & 7)
00112    #error CHAR_BIT must be a multiple of eight.
00113 #endif
00114 #if FP_MAX_SIZE % CHAR_BIT
00115    #error FP_MAX_SIZE must be a multiple of CHAR_BIT
00116 #endif
00117 
00118 /* autodetect x86-64 and make sure we are using 64-bit digits with x86-64 asm */
00119 #if defined(__x86_64__)
00120    #if defined(TFM_X86) || defined(TFM_SSE2) || defined(TFM_ARM) 
00121        #error x86-64 detected, x86-32/SSE2/ARM optimizations are not valid!
00122    #endif
00123    #if !defined(TFM_X86_64) && !defined(TFM_NO_ASM)
00124       #define TFM_X86_64
00125    #endif
00126 #endif
00127 #if defined(TFM_X86_64)
00128     #if !defined(FP_64BIT)
00129        #define FP_64BIT
00130     #endif
00131 #endif
00132 
00133 /* try to detect x86-32 */
00134 #if defined(__i386__) && !defined(TFM_SSE2)
00135    #if defined(TFM_X86_64) || defined(TFM_ARM) 
00136        #error x86-32 detected, x86-64/ARM optimizations are not valid!
00137    #endif
00138    #if !defined(TFM_X86) && !defined(TFM_NO_ASM)
00139       #define TFM_X86
00140    #endif
00141 #endif
00142 
00143 /* make sure we're 32-bit for x86-32/sse/arm/ppc32 */
00144 #if (defined(TFM_X86) || defined(TFM_SSE2) || defined(TFM_ARM) || defined(TFM_PPC32)) && defined(FP_64BIT)
00145    #warning x86-32, SSE2 and ARM, PPC32 optimizations require 32-bit digits (undefining)
00146    #undef FP_64BIT
00147 #endif
00148 
00149 /* multi asms? */
00150 #ifdef TFM_X86
00151    #define TFM_ASM
00152 #endif
00153 #ifdef TFM_X86_64
00154    #ifdef TFM_ASM
00155       #error TFM_ASM already defined!
00156    #endif
00157    #define TFM_ASM
00158 #endif
00159 #ifdef TFM_SSE2
00160    #ifdef TFM_ASM
00161       #error TFM_ASM already defined!
00162    #endif
00163    #define TFM_ASM
00164 #endif
00165 #ifdef TFM_ARM
00166    #ifdef TFM_ASM
00167       #error TFM_ASM already defined!
00168    #endif
00169    #define TFM_ASM
00170 #endif
00171 #ifdef TFM_PPC32
00172    #ifdef TFM_ASM
00173       #error TFM_ASM already defined!
00174    #endif
00175    #define TFM_ASM
00176 #endif
00177 #ifdef TFM_PPC64
00178    #ifdef TFM_ASM
00179       #error TFM_ASM already defined!
00180    #endif
00181    #define TFM_ASM
00182 #endif
00183 #ifdef TFM_AVR32
00184    #ifdef TFM_ASM
00185       #error TFM_ASM already defined!
00186    #endif
00187    #define TFM_ASM
00188 #endif
00189 
00190 /* we want no asm? */
00191 #ifdef TFM_NO_ASM
00192    #undef TFM_X86
00193    #undef TFM_X86_64
00194    #undef TFM_SSE2
00195    #undef TFM_ARM
00196    #undef TFM_PPC32
00197    #undef TFM_PPC64
00198    #undef TFM_AVR32
00199    #undef TFM_ASM   
00200 #endif
00201 
00202 /* ECC helpers */
00203 #ifdef TFM_ECC192
00204    #ifdef FP_64BIT
00205        #define TFM_MUL3
00206        #define TFM_SQR3
00207    #else
00208        #define TFM_MUL6
00209        #define TFM_SQR6
00210    #endif
00211 #endif
00212 
00213 #ifdef TFM_ECC224
00214    #ifdef FP_64BIT
00215        #define TFM_MUL4
00216        #define TFM_SQR4
00217    #else
00218        #define TFM_MUL7
00219        #define TFM_SQR7
00220    #endif
00221 #endif
00222 
00223 #ifdef TFM_ECC256
00224    #ifdef FP_64BIT
00225        #define TFM_MUL4
00226        #define TFM_SQR4
00227    #else
00228        #define TFM_MUL8
00229        #define TFM_SQR8
00230    #endif
00231 #endif
00232 
00233 #ifdef TFM_ECC384
00234    #ifdef FP_64BIT
00235        #define TFM_MUL6
00236        #define TFM_SQR6
00237    #else
00238        #define TFM_MUL12
00239        #define TFM_SQR12
00240    #endif
00241 #endif
00242 
00243 #ifdef TFM_ECC521
00244    #ifdef FP_64BIT
00245        #define TFM_MUL9
00246        #define TFM_SQR9
00247    #else
00248        #define TFM_MUL17
00249        #define TFM_SQR17
00250    #endif
00251 #endif
00252 
00253 
00254 /* some default configurations.
00255  */
00256 #if 0
00257 #if defined(FP_64BIT)
00258    /* for GCC only on supported platforms */
00259 #ifndef CRYPT
00260    typedef unsigned long ulong64;
00261 #endif
00262    typedef ulong64            fp_digit;
00263    typedef unsigned long      fp_word __attribute__ ((mode(TI)));
00264 #else
00265    /* this is to make porting into LibTomCrypt easier :-) */
00266 #ifndef CRYPT
00267    #if defined(_MSC_VER) || defined(__BORLANDC__) 
00268       typedef unsigned __int64   ulong64;
00269       typedef signed __int64     long64;
00270    #else
00271       typedef unsigned long long ulong64;
00272       typedef signed long long   long64;
00273    #endif
00274 #endif
00275    typedef unsigned long      fp_digit;
00276    typedef ulong64            fp_word;
00277 #endif
00278 #endif
00279 
00280    typedef uint32_t     fp_digit;
00281    typedef uint64_t     fp_word;
00282 
00283 /* # of digits this is */
00284 #define DIGIT_BIT  (int)((CHAR_BIT) * sizeof(fp_digit))
00285 #define FP_MASK    (fp_digit)(-1)
00286 #define FP_SIZE    (FP_MAX_SIZE/DIGIT_BIT)
00287 
00288 /* signs */
00289 #define FP_ZPOS     0
00290 #define FP_NEG      1
00291 
00292 /* return codes */
00293 #include "inc/minitls_errors.h"
00294 #define FP_OKAY     MINITLS_OK
00295 #define FP_VAL      MINITLS_ERR_PARAMETERS
00296 #define FP_MEM      MINITLS_ERR_MEMORY
00297 
00298 /* equalities */
00299 #define FP_LT        -1   /* less than */
00300 #define FP_EQ         0   /* equal to */
00301 #define FP_GT         1   /* greater than */
00302 
00303 /* replies */
00304 #define FP_YES        1   /* yes response */
00305 #define FP_NO         0   /* no response */
00306 
00307 /* a FP type */
00308 typedef struct {
00309     fp_digit dp[FP_SIZE];
00310     int      used, 
00311              sign;
00312 } fp_int;
00313 
00314 /* functions */
00315 
00316 /* returns a TFM ident string useful for debugging... */
00317 const char *fp_ident(void);
00318 
00319 /* initialize [or zero] an fp int */
00320 #define fp_init(a)  (void)memset((a), 0, sizeof(fp_int))
00321 #define fp_zero(a)  fp_init(a)
00322 
00323 /* zero/even/odd ? */
00324 #define fp_iszero(a) (((a)->used == 0) ? FP_YES : FP_NO)
00325 #define fp_iseven(a) (((a)->used >= 0 && (((a)->dp[0] & 1) == 0)) ? FP_YES : FP_NO)
00326 #define fp_isodd(a)  (((a)->used > 0  && (((a)->dp[0] & 1) == 1)) ? FP_YES : FP_NO)
00327 
00328 /* set to a small digit */
00329 void fp_set(fp_int *a, fp_digit b);
00330 
00331 /* copy from a to b */
00332 #define fp_copy(a, b)      (void)(((a) != (b)) && memcpy((b), (a), sizeof(fp_int)))
00333 #define fp_init_copy(a, b) fp_copy(b, a)
00334 
00335 /* clamp digits */
00336 #define fp_clamp(a)   { while ((a)->used && (a)->dp[(a)->used-1] == 0) --((a)->used); (a)->sign = (a)->used ? (a)->sign : FP_ZPOS; }
00337 
00338 /* negate and absolute */
00339 #define fp_neg(a, b)  { fp_copy(a, b); (b)->sign ^= 1; fp_clamp(b); }
00340 #define fp_abs(a, b)  { fp_copy(a, b); (b)->sign  = 0; }
00341 
00342 /* right shift x digits */
00343 void fp_rshd(fp_int *a, int x);
00344 
00345 /* left shift x digits */
00346 void fp_lshd(fp_int *a, int x);
00347 
00348 /* signed comparison */
00349 int fp_cmp(fp_int *a, fp_int *b);
00350 
00351 /* unsigned comparison */
00352 int fp_cmp_mag(fp_int *a, fp_int *b);
00353 
00354 /* power of 2 operations */
00355 void fp_div_2d(fp_int *a, int b, fp_int *c, fp_int *d);
00356 void fp_mod_2d(fp_int *a, int b, fp_int *c);
00357 void fp_mul_2d(fp_int *a, int b, fp_int *c);
00358 void fp_2expt (fp_int *a, int b);
00359 void fp_mul_2(fp_int *a, fp_int *c);
00360 void fp_div_2(fp_int *a, fp_int *c);
00361 
00362 /* Counts the number of lsbs which are zero before the first zero bit */
00363 int fp_cnt_lsb(fp_int *a);
00364 
00365 /* c = a + b */
00366 void fp_add(fp_int *a, fp_int *b, fp_int *c);
00367 
00368 /* c = a - b */
00369 void fp_sub(fp_int *a, fp_int *b, fp_int *c);
00370 
00371 /* c = a * b */
00372 void fp_mul(fp_int *a, fp_int *b, fp_int *c);
00373 
00374 /* b = a*a  */
00375 void fp_sqr(fp_int *a, fp_int *b);
00376 
00377 /* a/b => cb + d == a */
00378 int fp_div(fp_int *a, fp_int *b, fp_int *c, fp_int *d);
00379 
00380 /* c = a mod b, 0 <= c < b  */
00381 int fp_mod(fp_int *a, fp_int *b, fp_int *c);
00382 
00383 /* compare against a single digit */
00384 int fp_cmp_d(fp_int *a, fp_digit b);
00385 
00386 /* c = a + b */
00387 void fp_add_d(fp_int *a, fp_digit b, fp_int *c);
00388 
00389 /* c = a - b */
00390 void fp_sub_d(fp_int *a, fp_digit b, fp_int *c);
00391 
00392 /* c = a * b */
00393 void fp_mul_d(fp_int *a, fp_digit b, fp_int *c);
00394 
00395 /* a/b => cb + d == a */
00396 int fp_div_d(fp_int *a, fp_digit b, fp_int *c, fp_digit *d);
00397 
00398 /* c = a mod b, 0 <= c < b  */
00399 int fp_mod_d(fp_int *a, fp_digit b, fp_digit *c);
00400 
00401 /* ---> number theory <--- */
00402 /* d = a + b (mod c) */
00403 int fp_addmod(fp_int *a, fp_int *b, fp_int *c, fp_int *d);
00404 
00405 /* d = a - b (mod c) */
00406 int fp_submod(fp_int *a, fp_int *b, fp_int *c, fp_int *d);
00407 
00408 /* d = a * b (mod c) */
00409 int fp_mulmod(fp_int *a, fp_int *b, fp_int *c, fp_int *d);
00410 
00411 /* c = a * a (mod b) */
00412 int fp_sqrmod(fp_int *a, fp_int *b, fp_int *c);
00413 
00414 /* c = 1/a (mod b) */
00415 int fp_invmod(fp_int *a, fp_int *b, fp_int *c);
00416 
00417 /* c = (a, b) */
00418 void fp_gcd(fp_int *a, fp_int *b, fp_int *c);
00419 
00420 /* c = [a, b] */
00421 void fp_lcm(fp_int *a, fp_int *b, fp_int *c);
00422 
00423 /* setups the montgomery reduction */
00424 int fp_montgomery_setup(fp_int *a, fp_digit *mp);
00425 
00426 /* computes a = B**n mod b without division or multiplication useful for
00427  * normalizing numbers in a Montgomery system.
00428  */
00429 void fp_montgomery_calc_normalization(fp_int *a, fp_int *b);
00430 
00431 /* computes x/R == x (mod N) via Montgomery Reduction */
00432 void fp_montgomery_reduce(fp_int *a, fp_int *m, fp_digit mp);
00433 
00434 /* d = a**b (mod c) */
00435 int fp_exptmod(fp_int *a, fp_int *b, fp_int *c, fp_int *d);
00436 
00437 /* primality stuff */
00438 
00439 /* perform a Miller-Rabin test of a to the base b and store result in "result" */
00440 void fp_prime_miller_rabin (fp_int * a, fp_int * b, int *result);
00441 
00442 /* 256 trial divisions + 8 Miller-Rabins, returns FP_YES if probable prime  */
00443 int fp_isprime(fp_int *a);
00444 
00445 /* Primality generation flags */
00446 #define TFM_PRIME_BBS      0x0001 /* BBS style prime */
00447 #define TFM_PRIME_SAFE     0x0002 /* Safe prime (p-1)/2 == prime */
00448 #define TFM_PRIME_2MSB_OFF 0x0004 /* force 2nd MSB to 0 */
00449 #define TFM_PRIME_2MSB_ON  0x0008 /* force 2nd MSB to 1 */
00450 
00451 /* callback for fp_prime_random, should fill dst with random bytes and return how many read [upto len] */
00452 typedef int tfm_prime_callback(unsigned char *dst, int len, void *dat);
00453 
00454 #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)
00455 
00456 int fp_prime_random_ex(fp_int *a, int t, int size, int flags, tfm_prime_callback cb, void *dat);
00457 
00458 /* radix conersions */
00459 int fp_count_bits(fp_int *a);
00460 
00461 int fp_unsigned_bin_size(fp_int *a);
00462 void fp_read_unsigned_bin(fp_int *a, unsigned char *b, int c);
00463 void fp_to_unsigned_bin(fp_int *a, unsigned char *b);
00464 
00465 int fp_signed_bin_size(fp_int *a);
00466 void fp_read_signed_bin(fp_int *a, unsigned char *b, int c);
00467 void fp_to_signed_bin(fp_int *a, unsigned char *b);
00468 
00469 int fp_read_radix(fp_int *a, char *str, int radix);
00470 int fp_toradix(fp_int *a, char *str, int radix);
00471 int fp_toradix_n(fp_int * a, char *str, int radix, int maxlen);
00472 
00473 
00474 /* VARIOUS LOW LEVEL STUFFS */
00475 void s_fp_add(fp_int *a, fp_int *b, fp_int *c);
00476 void s_fp_sub(fp_int *a, fp_int *b, fp_int *c);
00477 void fp_reverse(unsigned char *s, int len);
00478 
00479 void fp_mul_comba(fp_int *A, fp_int *B, fp_int *C);
00480 
00481 #ifdef TFM_SMALL_SET
00482 void fp_mul_comba_small(fp_int *A, fp_int *B, fp_int *C);
00483 #endif
00484 
00485 #ifdef TFM_MUL3
00486 void fp_mul_comba3(fp_int *A, fp_int *B, fp_int *C);
00487 #endif
00488 #ifdef TFM_MUL4
00489 void fp_mul_comba4(fp_int *A, fp_int *B, fp_int *C);
00490 #endif
00491 #ifdef TFM_MUL6
00492 void fp_mul_comba6(fp_int *A, fp_int *B, fp_int *C);
00493 #endif
00494 #ifdef TFM_MUL7
00495 void fp_mul_comba7(fp_int *A, fp_int *B, fp_int *C);
00496 #endif
00497 #ifdef TFM_MUL8
00498 void fp_mul_comba8(fp_int *A, fp_int *B, fp_int *C);
00499 #endif
00500 #ifdef TFM_MUL9
00501 void fp_mul_comba9(fp_int *A, fp_int *B, fp_int *C);
00502 #endif
00503 #ifdef TFM_MUL12
00504 void fp_mul_comba12(fp_int *A, fp_int *B, fp_int *C);
00505 #endif
00506 #ifdef TFM_MUL17
00507 void fp_mul_comba17(fp_int *A, fp_int *B, fp_int *C);
00508 #endif
00509 
00510 #ifdef TFM_MUL20
00511 void fp_mul_comba20(fp_int *A, fp_int *B, fp_int *C);
00512 #endif
00513 #ifdef TFM_MUL24
00514 void fp_mul_comba24(fp_int *A, fp_int *B, fp_int *C);
00515 #endif
00516 #ifdef TFM_MUL28
00517 void fp_mul_comba28(fp_int *A, fp_int *B, fp_int *C);
00518 #endif
00519 #ifdef TFM_MUL32
00520 void fp_mul_comba32(fp_int *A, fp_int *B, fp_int *C);
00521 #endif
00522 #ifdef TFM_MUL48
00523 void fp_mul_comba48(fp_int *A, fp_int *B, fp_int *C);
00524 #endif
00525 #ifdef TFM_MUL64
00526 void fp_mul_comba64(fp_int *A, fp_int *B, fp_int *C);
00527 #endif
00528 
00529 void fp_sqr_comba(fp_int *A, fp_int *B);
00530 
00531 #ifdef TFM_SMALL_SET
00532 void fp_sqr_comba_small(fp_int *A, fp_int *B);
00533 #endif
00534 
00535 #ifdef TFM_SQR3
00536 void fp_sqr_comba3(fp_int *A, fp_int *B);
00537 #endif
00538 #ifdef TFM_SQR4
00539 void fp_sqr_comba4(fp_int *A, fp_int *B);
00540 #endif
00541 #ifdef TFM_SQR6
00542 void fp_sqr_comba6(fp_int *A, fp_int *B);
00543 #endif
00544 #ifdef TFM_SQR7
00545 void fp_sqr_comba7(fp_int *A, fp_int *B);
00546 #endif
00547 #ifdef TFM_SQR8
00548 void fp_sqr_comba8(fp_int *A, fp_int *B);
00549 #endif
00550 #ifdef TFM_SQR9
00551 void fp_sqr_comba9(fp_int *A, fp_int *B);
00552 #endif
00553 #ifdef TFM_SQR12
00554 void fp_sqr_comba12(fp_int *A, fp_int *B);
00555 #endif
00556 #ifdef TFM_SQR17
00557 void fp_sqr_comba17(fp_int *A, fp_int *B);
00558 #endif
00559 
00560 #ifdef TFM_SQR20
00561 void fp_sqr_comba20(fp_int *A, fp_int *B);
00562 #endif
00563 #ifdef TFM_SQR24
00564 void fp_sqr_comba24(fp_int *A, fp_int *B);
00565 #endif
00566 #ifdef TFM_SQR28
00567 void fp_sqr_comba28(fp_int *A, fp_int *B);
00568 #endif
00569 #ifdef TFM_SQR32
00570 void fp_sqr_comba32(fp_int *A, fp_int *B);
00571 #endif
00572 #ifdef TFM_SQR48
00573 void fp_sqr_comba48(fp_int *A, fp_int *B);
00574 #endif
00575 #ifdef TFM_SQR64
00576 void fp_sqr_comba64(fp_int *A, fp_int *B);
00577 #endif
00578 extern const char *fp_s_rmap;
00579 
00580 #endif
00581 
00582 
00583 /* $Source: /cvs/libtom/tomsfastmath/src/headers/tfm.h,v $ */
00584 /* $Revision: 1.3 $ */
00585 /* $Date: 2007/02/27 02:38:44 $ */