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#ifndef MIN 20 #define MIN(x,y) ((x)<(y)?(x):(y)) 21#endif 22 23#ifndef MAX 24 #define MAX(x,y) ((x)>(y)?(x):(y)) 25#endif 26 27/* externally define this symbol to ignore the default settings, useful for changing the build from the make process */ 28#ifndef TFM_ALREADY_SET 29 30/* do we want the large set of small multiplications ? 31 Enable these if you are going to be doing a lot of small (<= 16 digit) multiplications say in ECC 32 Or if you're on a 64-bit machine doing RSA as a 1024-bit integer == 16 digits ;-) 33 */ 34#define TFM_SMALL_SET 35 36/* do we want huge code 37 Enable these if you are doing 20, 24, 28, 32, 48, 64 digit multiplications (useful for RSA) 38 Less important on 64-bit machines as 32 digits == 2048 bits 39 */ 40#if 0 41#define TFM_MUL3 42#define TFM_MUL4 43#define TFM_MUL6 44#define TFM_MUL7 45#define TFM_MUL8 46#define TFM_MUL9 47#define TFM_MUL12 48#define TFM_MUL17 49#endif 50#define TFM_MUL20 51#define TFM_MUL24 52#define TFM_MUL28 53#define TFM_MUL32 54#define TFM_MUL48 55#define TFM_MUL64 56 57#if 0 58#define TFM_SQR3 59#define TFM_SQR4 60#define TFM_SQR6 61#define TFM_SQR7 62#define TFM_SQR8 63#define TFM_SQR9 64#define TFM_SQR12 65#define TFM_SQR17 66#endif 67#define TFM_SQR20 68#define TFM_SQR24 69#define TFM_SQR28 70#define TFM_SQR32 71#define TFM_SQR48 72#ifndef __ppc__ 73#define TFM_SQR64 74#endif 75 76#define TFM_NO_ASM 1 77 78/* do we want some overflow checks 79 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) 80 */ 81/* #define TFM_CHECK */ 82 83/* Is the target a P4 Prescott 84 */ 85/* #define TFM_PRESCOTT */ 86 87/* Do we want timing resistant fp_exptmod() ? 88 * This makes it slower but also timing invariant with respect to the exponent 89 */ 90#define TFM_TIMING_RESISTANT 1 91 92#endif 93 94/* Max size of any number in bits. Basically the largest size you will be multiplying 95 * should be half [or smaller] of FP_MAX_SIZE-four_digit 96 * 97 * You can externally define this or it defaults to 4096-bits [allowing multiplications upto 2048x2048 bits ] 98 */ 99#ifndef FP_MAX_SIZE 100 #define FP_MAX_SIZE (4096+(8*DIGIT_BIT)) 101#endif 102 103/* will this lib work? */ 104#if (CHAR_BIT & 7) 105 #error CHAR_BIT must be a multiple of eight. 106#endif 107#if FP_MAX_SIZE % CHAR_BIT 108 #error FP_MAX_SIZE must be a multiple of CHAR_BIT 109#endif 110 111/* autodetect x86-64 and make sure we are using 64-bit digits with x86-64 asm */ 112#if defined(__x86_64__) 113 #if defined(TFM_X86) || defined(TFM_SSE2) || defined(TFM_ARM) 114 #error x86-64 detected, x86-32/SSE2/ARM optimizations are not valid! 115 #endif 116 #if !defined(TFM_X86_64) && !defined(TFM_NO_ASM) 117 #define TFM_X86_64 118 #endif 119#endif 120#if defined(TFM_X86_64) 121 #if !defined(FP_64BIT) 122 #define FP_64BIT 123 #endif 124#endif 125 126/* try to detect x86-32 */ 127#if defined(__i386__) && !defined(TFM_SSE2) 128 #if defined(TFM_X86_64) || defined(TFM_ARM) 129 #error x86-32 detected, x86-64/ARM optimizations are not valid! 130 #endif 131 #if !defined(TFM_X86) && !defined(TFM_NO_ASM) 132 #define TFM_X86 133 #endif 134#endif 135 136/* make sure we're 32-bit for x86-32/sse/arm/ppc32 */ 137#if (defined(TFM_X86) || defined(TFM_SSE2) || defined(TFM_ARM) || defined(TFM_PPC32)) && defined(FP_64BIT) 138 #warning x86-32, SSE2 and ARM, PPC32 optimizations require 32-bit digits (undefining) 139 #undef FP_64BIT 140#endif 141 142/* multi asms? */ 143#ifdef TFM_X86 144 #define TFM_ASM 145#endif 146#ifdef TFM_X86_64 147 #ifdef TFM_ASM 148 #error TFM_ASM already defined! 149 #endif 150 #define TFM_ASM 151#endif 152#ifdef TFM_SSE2 153 #ifdef TFM_ASM 154 #error TFM_ASM already defined! 155 #endif 156 #define TFM_ASM 157#endif 158#ifdef TFM_ARM 159 #ifdef TFM_ASM 160 #error TFM_ASM already defined! 161 #endif 162 #define TFM_ASM 163#endif 164#ifdef TFM_PPC32 165 #ifdef TFM_ASM 166 #error TFM_ASM already defined! 167 #endif 168 #define TFM_ASM 169#endif 170#ifdef TFM_PPC64 171 #ifdef TFM_ASM 172 #error TFM_ASM already defined! 173 #endif 174 #define TFM_ASM 175#endif 176#ifdef TFM_AVR32 177 #ifdef TFM_ASM 178 #error TFM_ASM already defined! 179 #endif 180 #define TFM_ASM 181#endif 182 183/* we want no asm? */ 184#ifdef TFM_NO_ASM 185 #undef TFM_X86 186 #undef TFM_X86_64 187 #undef TFM_SSE2 188 #undef TFM_ARM 189 #undef TFM_PPC32 190 #undef TFM_PPC64 191 #undef TFM_AVR32 192 #undef TFM_ASM 193#endif 194 195/* ECC helpers */ 196#ifdef TFM_ECC192 197 #ifdef FP_64BIT 198 #define TFM_MUL3 199 #define TFM_SQR3 200 #else 201 #define TFM_MUL6 202 #define TFM_SQR6 203 #endif 204#endif 205 206#ifdef TFM_ECC224 207 #ifdef FP_64BIT 208 #define TFM_MUL4 209 #define TFM_SQR4 210 #else 211 #define TFM_MUL7 212 #define TFM_SQR7 213 #endif 214#endif 215 216#ifdef TFM_ECC256 217 #ifdef FP_64BIT 218 #define TFM_MUL4 219 #define TFM_SQR4 220 #else 221 #define TFM_MUL8 222 #define TFM_SQR8 223 #endif 224#endif 225 226#ifdef TFM_ECC384 227 #ifdef FP_64BIT 228 #define TFM_MUL6 229 #define TFM_SQR6 230 #else 231 #define TFM_MUL12 232 #define TFM_SQR12 233 #endif 234#endif 235 236#ifdef TFM_ECC521 237 #ifdef FP_64BIT 238 #define TFM_MUL9 239 #define TFM_SQR9 240 #else 241 #define TFM_MUL17 242 #define TFM_SQR17 243 #endif 244#endif 245 246 247/* some default configurations. 248 */ 249#if defined(FP_64BIT) 250 /* for GCC only on supported platforms */ 251#ifndef CRYPT 252 typedef unsigned long ulong64; 253#endif 254 typedef ulong64 fp_digit; 255 typedef unsigned long fp_word __attribute__ ((mode(TI))); 256#else 257 /* this is to make porting into LibTomCrypt easier :-) */ 258#ifndef CRYPT 259 #if defined(_MSC_VER) || defined(__BORLANDC__) 260 typedef unsigned __int64 ulong64; 261 typedef signed __int64 long64; 262 #else 263 typedef unsigned long long ulong64; 264 typedef signed long long long64; 265 #endif 266#endif 267#if 0 268 typedef unsigned long fp_digit; 269#else 270 typedef unsigned int fp_digit; 271#endif 272 typedef ulong64 fp_word; 273#endif 274 275/* # of digits this is */ 276#define DIGIT_BIT (int)((CHAR_BIT) * sizeof(fp_digit)) 277#define FP_MASK (fp_digit)(-1) 278#define FP_SIZE (FP_MAX_SIZE/DIGIT_BIT) 279 280/* signs */ 281#define FP_ZPOS 0 282#define FP_NEG 1 283 284/* return codes */ 285#define FP_OKAY 0 286#define FP_VAL 1 287#define FP_MEM 2 288 289/* equalities */ 290#define FP_LT -1 /* less than */ 291#define FP_EQ 0 /* equal to */ 292#define FP_GT 1 /* greater than */ 293 294/* replies */ 295#define FP_YES 1 /* yes response */ 296#define FP_NO 0 /* no response */ 297 298/* a FP type */ 299typedef struct { 300 fp_digit dp[FP_SIZE]; 301 int used, 302 sign; 303} fp_int; 304 305/* functions */ 306 307/* returns a TFM ident string useful for debugging... */ 308const char *fp_ident(void); 309 310/* initialize [or zero] an fp int */ 311#define fp_init(a) (void)memset((a), 0, sizeof(fp_int)) 312void fp_init_multi(fp_int *a, ...); 313#define fp_zero(a) fp_init(a) 314#define fp_zero_multi fp_init_multi 315 316/* zero/even/odd ? */ 317#define fp_iszero(a) (((a)->used == 0) ? FP_YES : FP_NO) 318#define fp_iseven(a) (((a)->used >= 0 && (((a)->dp[0] & 1) == 0)) ? FP_YES : FP_NO) 319#define fp_isodd(a) (((a)->used > 0 && (((a)->dp[0] & 1) == 1)) ? FP_YES : FP_NO) 320 321/* is negative ? */ 322#define fp_isneg(a) (((a)->sign) == FP_NEG) 323 324/* set to a small digit */ 325void fp_set(fp_int *a, fp_digit b); 326 327/* copy from a to b */ 328#define fp_copy(a, b) (void)(((a) != (b)) && memcpy((b), (a), sizeof(fp_int))) 329#define fp_init_copy(a, b) fp_copy(b, a) 330 331/* clamp digits */ 332#define fp_clamp(a) { while ((a)->used && (a)->dp[(a)->used-1] == 0) --((a)->used); (a)->sign = (a)->used ? (a)->sign : FP_ZPOS; } 333 334/* negate and absolute */ 335#define fp_neg(a, b) { fp_copy(a, b); (b)->sign ^= 1; fp_clamp(b); } 336#define fp_abs(a, b) { fp_copy(a, b); (b)->sign = 0; } 337 338/* right shift x digits */ 339void fp_rshd(fp_int *a, int x); 340 341/* left shift x digits */ 342void fp_lshd(fp_int *a, int x); 343 344/* signed comparison */ 345int fp_cmp(fp_int *a, fp_int *b); 346 347/* unsigned comparison */ 348int fp_cmp_mag(fp_int *a, fp_int *b); 349 350/* power of 2 operations */ 351void fp_div_2d(fp_int *a, int b, fp_int *c, fp_int *d); 352void fp_mod_2d(fp_int *a, int b, fp_int *c); 353void fp_mul_2d(fp_int *a, int b, fp_int *c); 354void fp_2expt (fp_int *a, int b); 355void fp_mul_2(fp_int *a, fp_int *c); 356void fp_div_2(fp_int *a, fp_int *c); 357 358/* Counts the number of lsbs which are zero before the first zero bit */ 359int fp_cnt_lsb(fp_int *a); 360 361/* c = a + b */ 362void fp_add(fp_int *a, fp_int *b, fp_int *c); 363 364/* c = a - b */ 365void fp_sub(fp_int *a, fp_int *b, fp_int *c); 366 367/* c = a * b */ 368void fp_mul(fp_int *a, fp_int *b, fp_int *c); 369 370/* b = a*a */ 371void fp_sqr(fp_int *a, fp_int *b); 372 373/* a/b => cb + d == a */ 374int fp_div(fp_int *a, fp_int *b, fp_int *c, fp_int *d); 375 376/* c = a mod b, 0 <= c < b */ 377int fp_mod(fp_int *a, fp_int *b, fp_int *c); 378 379/* compare against a single digit */ 380int fp_cmp_d(fp_int *a, fp_digit b); 381 382/* c = a + b */ 383void fp_add_d(fp_int *a, fp_digit b, fp_int *c); 384 385/* c = a - b */ 386void fp_sub_d(fp_int *a, fp_digit b, fp_int *c); 387 388/* c = a * b */ 389void fp_mul_d(fp_int *a, fp_digit b, fp_int *c); 390 391/* a/b => cb + d == a */ 392int fp_div_d(fp_int *a, fp_digit b, fp_int *c, fp_digit *d); 393 394/* c = a mod b, 0 <= c < b */ 395int fp_mod_d(fp_int *a, fp_digit b, fp_digit *c); 396 397/* ---> number theory <--- */ 398/* d = a + b (mod c) */ 399int fp_addmod(fp_int *a, fp_int *b, fp_int *c, fp_int *d); 400 401/* d = a - b (mod c) */ 402int fp_submod(fp_int *a, fp_int *b, fp_int *c, fp_int *d); 403 404/* d = a * b (mod c) */ 405int fp_mulmod(fp_int *a, fp_int *b, fp_int *c, fp_int *d); 406 407/* c = a * a (mod b) */ 408int fp_sqrmod(fp_int *a, fp_int *b, fp_int *c); 409 410/* c = 1/a (mod b) */ 411int fp_invmod(fp_int *a, fp_int *b, fp_int *c); 412 413/* c = (a, b) */ 414void fp_gcd(fp_int *a, fp_int *b, fp_int *c); 415 416/* c = [a, b] */ 417void fp_lcm(fp_int *a, fp_int *b, fp_int *c); 418 419/* setups the montgomery reduction */ 420int fp_montgomery_setup(fp_int *a, fp_digit *mp); 421 422/* computes a = B**n mod b without division or multiplication useful for 423 * normalizing numbers in a Montgomery system. 424 */ 425void fp_montgomery_calc_normalization(fp_int *a, fp_int *b); 426 427/* computes x/R == x (mod N) via Montgomery Reduction */ 428void fp_montgomery_reduce(fp_int *a, fp_int *m, fp_digit mp); 429 430/* d = a**b (mod c) */ 431int fp_exptmod(fp_int *a, fp_int *b, fp_int *c, fp_int *d); 432 433/* primality stuff */ 434 435/* perform a Miller-Rabin test of a to the base b and store result in "result" */ 436void fp_prime_miller_rabin (fp_int * a, fp_int * b, int *result); 437 438/* 256 trial divisions + 8 Miller-Rabins, returns FP_YES if probable prime */ 439int fp_isprime(fp_int *a); 440 441/* given a, find a prime a that same and larger, that is a fp_isprime think is a prime */ 442int fp_find_prime(fp_int *a); 443 444/* Primality generation flags */ 445#define TFM_PRIME_BBS 0x0001 /* BBS style prime */ 446#define TFM_PRIME_SAFE 0x0002 /* Safe prime (p-1)/2 == prime */ 447#define TFM_PRIME_2MSB_OFF 0x0004 /* force 2nd MSB to 0 */ 448#define TFM_PRIME_2MSB_ON 0x0008 /* force 2nd MSB to 1 */ 449 450/* callback for fp_prime_random, should fill dst with random bytes and return how many read [upto len] */ 451typedef int tfm_prime_callback(unsigned char *dst, int len, void *dat); 452 453#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) 454 455int fp_prime_random_ex(fp_int *a, int t, int size, int flags, tfm_prime_callback cb, void *dat); 456 457/* radix conersions */ 458int fp_count_bits(fp_int *a); 459 460int fp_radix_size(fp_int *a, int radix, int *size); 461 462int fp_unsigned_bin_size(fp_int *a); 463void fp_read_unsigned_bin(fp_int *a, unsigned char *b, int c); 464void fp_to_unsigned_bin(fp_int *a, unsigned char *b); 465 466int fp_signed_bin_size(fp_int *a); 467void fp_read_signed_bin(fp_int *a, unsigned char *b, int c); 468void fp_to_signed_bin(fp_int *a, unsigned char *b); 469 470int fp_read_radix(fp_int *a, char *str, int radix); 471int fp_toradix(fp_int *a, char *str, int radix); 472int fp_toradix_n(fp_int * a, char *str, int radix, int maxlen); 473 474 475/* VARIOUS LOW LEVEL STUFFS */ 476void s_fp_add(fp_int *a, fp_int *b, fp_int *c); 477void s_fp_sub(fp_int *a, fp_int *b, fp_int *c); 478void fp_reverse(unsigned char *s, int len); 479 480void fp_mul_comba(fp_int *A, fp_int *B, fp_int *C); 481 482#ifdef TFM_SMALL_SET 483void fp_mul_comba_small(fp_int *A, fp_int *B, fp_int *C); 484#endif 485 486#ifdef TFM_MUL3 487void fp_mul_comba3(fp_int *A, fp_int *B, fp_int *C); 488#endif 489#ifdef TFM_MUL4 490void fp_mul_comba4(fp_int *A, fp_int *B, fp_int *C); 491#endif 492#ifdef TFM_MUL6 493void fp_mul_comba6(fp_int *A, fp_int *B, fp_int *C); 494#endif 495#ifdef TFM_MUL7 496void fp_mul_comba7(fp_int *A, fp_int *B, fp_int *C); 497#endif 498#ifdef TFM_MUL8 499void fp_mul_comba8(fp_int *A, fp_int *B, fp_int *C); 500#endif 501#ifdef TFM_MUL9 502void fp_mul_comba9(fp_int *A, fp_int *B, fp_int *C); 503#endif 504#ifdef TFM_MUL12 505void fp_mul_comba12(fp_int *A, fp_int *B, fp_int *C); 506#endif 507#ifdef TFM_MUL17 508void fp_mul_comba17(fp_int *A, fp_int *B, fp_int *C); 509#endif 510 511#ifdef TFM_MUL20 512void fp_mul_comba20(fp_int *A, fp_int *B, fp_int *C); 513#endif 514#ifdef TFM_MUL24 515void fp_mul_comba24(fp_int *A, fp_int *B, fp_int *C); 516#endif 517#ifdef TFM_MUL28 518void fp_mul_comba28(fp_int *A, fp_int *B, fp_int *C); 519#endif 520#ifdef TFM_MUL32 521void fp_mul_comba32(fp_int *A, fp_int *B, fp_int *C); 522#endif 523#ifdef TFM_MUL48 524void fp_mul_comba48(fp_int *A, fp_int *B, fp_int *C); 525#endif 526#ifdef TFM_MUL64 527void fp_mul_comba64(fp_int *A, fp_int *B, fp_int *C); 528#endif 529 530void fp_sqr_comba(fp_int *A, fp_int *B); 531 532#ifdef TFM_SMALL_SET 533void fp_sqr_comba_small(fp_int *A, fp_int *B); 534#endif 535 536#ifdef TFM_SQR3 537void fp_sqr_comba3(fp_int *A, fp_int *B); 538#endif 539#ifdef TFM_SQR4 540void fp_sqr_comba4(fp_int *A, fp_int *B); 541#endif 542#ifdef TFM_SQR6 543void fp_sqr_comba6(fp_int *A, fp_int *B); 544#endif 545#ifdef TFM_SQR7 546void fp_sqr_comba7(fp_int *A, fp_int *B); 547#endif 548#ifdef TFM_SQR8 549void fp_sqr_comba8(fp_int *A, fp_int *B); 550#endif 551#ifdef TFM_SQR9 552void fp_sqr_comba9(fp_int *A, fp_int *B); 553#endif 554#ifdef TFM_SQR12 555void fp_sqr_comba12(fp_int *A, fp_int *B); 556#endif 557#ifdef TFM_SQR17 558void fp_sqr_comba17(fp_int *A, fp_int *B); 559#endif 560 561#ifdef TFM_SQR20 562void fp_sqr_comba20(fp_int *A, fp_int *B); 563#endif 564#ifdef TFM_SQR24 565void fp_sqr_comba24(fp_int *A, fp_int *B); 566#endif 567#ifdef TFM_SQR28 568void fp_sqr_comba28(fp_int *A, fp_int *B); 569#endif 570#ifdef TFM_SQR32 571void fp_sqr_comba32(fp_int *A, fp_int *B); 572#endif 573#ifdef TFM_SQR48 574void fp_sqr_comba48(fp_int *A, fp_int *B); 575#endif 576#ifdef TFM_SQR64 577void fp_sqr_comba64(fp_int *A, fp_int *B); 578#endif 579extern const char *fp_s_rmap; 580 581#endif 582 583 584/* $Source: /cvs/libtom/tomsfastmath/src/headers/tfm.h,v $ */ 585/* $Revision: 1.3 $ */ 586/* $Date: 2007/02/27 02:38:44 $ */ 587