tfm.h (28403B)
1 /* tfm.h 2 * 3 * Copyright (C) 2006-2025 wolfSSL Inc. 4 * 5 * This file is part of wolfSSL. 6 * 7 * wolfSSL is free software; you can redistribute it and/or modify 8 * it under the terms of the GNU General Public License as published by 9 * the Free Software Foundation; either version 3 of the License, or 10 * (at your option) any later version. 11 * 12 * wolfSSL is distributed in the hope that it will be useful, 13 * but WITHOUT ANY WARRANTY; without even the implied warranty of 14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 15 * GNU General Public License for more details. 16 * 17 * You should have received a copy of the GNU General Public License 18 * along with this program; if not, write to the Free Software 19 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1335, USA 20 */ 21 22 23 24 /* 25 * Based on public domain TomsFastMath 0.10 by Tom St Denis, tomstdenis@iahu.ca, 26 * http://math.libtomcrypt.com 27 */ 28 29 30 /** 31 * Edited by Moises Guimaraes (moises.guimaraes@phoebus.com.br) 32 * to fit CyaSSL's needs. 33 */ 34 35 /*! 36 \file wolfssl/wolfcrypt/tfm.h 37 */ 38 39 #ifndef WOLF_CRYPT_TFM_H 40 #define WOLF_CRYPT_TFM_H 41 42 #include <wolfssl/wolfcrypt/types.h> 43 #include <wolfssl/wolfcrypt/error-crypt.h> 44 #ifndef CHAR_BIT 45 #include <limits.h> 46 #endif 47 48 #include <wolfssl/wolfcrypt/random.h> 49 50 #ifdef __cplusplus 51 extern "C" { 52 #endif 53 54 #ifdef WOLFSSL_NO_ASM 55 #undef TFM_NO_ASM 56 #define TFM_NO_ASM 57 #endif 58 59 #ifdef NO_64BIT 60 #undef NO_TFM_64BIT 61 #define NO_TFM_64BIT 62 #endif 63 64 #ifndef NO_TFM_64BIT 65 /* autodetect x86-64 and make sure we are using 64-bit digits with x86-64 asm */ 66 #if defined(__x86_64__) 67 #if defined(TFM_X86) || defined(TFM_SSE2) || defined(TFM_ARM) 68 #error x86-64 detected, x86-32/SSE2/ARM optimizations are not valid! 69 #endif 70 #if !defined(TFM_X86_64) && !defined(TFM_NO_ASM) 71 #define TFM_X86_64 72 #endif 73 #endif 74 #if defined(__aarch64__) && defined(__APPLE__) 75 #if !defined(TFM_AARCH_64) && !defined(TFM_NO_ASM) 76 #define TFM_AARCH_64 77 #endif 78 #endif 79 #if defined(TFM_X86_64) || defined(TFM_AARCH_64) 80 #if !defined(FP_64BIT) 81 #define FP_64BIT 82 #endif 83 #endif 84 /* use 64-bit digit even if not using asm on x86_64 */ 85 #if defined(__x86_64__) && !defined(FP_64BIT) 86 #define FP_64BIT 87 #endif 88 /* if intel compiler doesn't provide 128 bit type don't turn on 64bit */ 89 #if defined(FP_64BIT) && defined(__INTEL_COMPILER) && !defined(HAVE___UINT128_T) 90 #undef FP_64BIT 91 #undef TFM_X86_64 92 #endif 93 #endif /* NO_TFM_64BIT */ 94 95 /* try to detect x86-32 */ 96 #if defined(__i386__) && !defined(TFM_SSE2) 97 #if defined(TFM_X86_64) || defined(TFM_ARM) 98 #error x86-32 detected, x86-64/ARM optimizations are not valid! 99 #endif 100 #if !defined(TFM_X86) && !defined(TFM_NO_ASM) 101 #define TFM_X86 102 #endif 103 #endif 104 105 /* make sure we're 32-bit for x86-32/sse/arm/ppc32 */ 106 #if (defined(TFM_X86) || defined(TFM_SSE2) || defined(TFM_ARM) || defined(TFM_PPC32)) && defined(FP_64BIT) 107 #warning x86-32, SSE2 and ARM, PPC32 optimizations require 32-bit digits (undefining) 108 #undef FP_64BIT 109 #endif 110 111 /* multi asms? */ 112 #ifdef TFM_X86 113 #define TFM_ASM 114 #endif 115 #ifdef TFM_X86_64 116 #ifdef TFM_ASM 117 #error TFM_ASM already defined! 118 #endif 119 #define TFM_ASM 120 #endif 121 #ifdef TFM_SSE2 122 #ifdef TFM_ASM 123 #error TFM_ASM already defined! 124 #endif 125 #define TFM_ASM 126 #endif 127 #ifdef TFM_ARM 128 #ifdef TFM_ASM 129 #error TFM_ASM already defined! 130 #endif 131 #define TFM_ASM 132 #endif 133 #ifdef TFM_PPC32 134 #ifdef TFM_ASM 135 #error TFM_ASM already defined! 136 #endif 137 #define TFM_ASM 138 #endif 139 #ifdef TFM_PPC64 140 #ifdef TFM_ASM 141 #error TFM_ASM already defined! 142 #endif 143 #define TFM_ASM 144 #endif 145 #ifdef TFM_AVR32 146 #ifdef TFM_ASM 147 #error TFM_ASM already defined! 148 #endif 149 #define TFM_ASM 150 #endif 151 152 /* we want no asm? */ 153 #ifdef TFM_NO_ASM 154 #undef TFM_X86 155 #undef TFM_X86_64 156 #undef TFM_SSE2 157 #undef TFM_ARM 158 #undef TFM_PPC32 159 #undef TFM_PPC64 160 #undef TFM_AVR32 161 #undef TFM_ASM 162 #endif 163 164 /* ECC helpers */ 165 #ifdef TFM_ECC192 166 #ifdef FP_64BIT 167 #define TFM_MUL3 168 #define TFM_SQR3 169 #else 170 #define TFM_MUL6 171 #define TFM_SQR6 172 #endif 173 #endif 174 175 #ifdef TFM_ECC224 176 #ifdef FP_64BIT 177 #define TFM_MUL4 178 #define TFM_SQR4 179 #else 180 #define TFM_MUL7 181 #define TFM_SQR7 182 #endif 183 #endif 184 185 #ifdef TFM_ECC256 186 #ifdef FP_64BIT 187 #define TFM_MUL4 188 #define TFM_SQR4 189 #else 190 #define TFM_MUL8 191 #define TFM_SQR8 192 #endif 193 #endif 194 195 #ifdef TFM_ECC384 196 #ifdef FP_64BIT 197 #define TFM_MUL6 198 #define TFM_SQR6 199 #else 200 #define TFM_MUL12 201 #define TFM_SQR12 202 #endif 203 #endif 204 205 #ifdef TFM_ECC521 206 #ifdef FP_64BIT 207 #define TFM_MUL9 208 #define TFM_SQR9 209 #else 210 #define TFM_MUL17 211 #define TFM_SQR17 212 #endif 213 #endif 214 215 216 /* allow user to define on fp_digit, fp_word types */ 217 #ifndef WOLFSSL_BIGINT_TYPES 218 219 /* some default configurations. 220 */ 221 #if defined(WC_16BIT_CPU) 222 typedef unsigned int fp_digit; 223 #define SIZEOF_FP_DIGIT 2 224 typedef unsigned long fp_word; 225 typedef signed long fp_sword; 226 #elif defined(FP_64BIT) 227 /* for GCC only on supported platforms */ 228 typedef unsigned long long fp_digit; /* 64bit, 128 uses mode(TI) below */ 229 #define SIZEOF_FP_DIGIT 8 230 typedef unsigned long fp_word __attribute__ ((mode(TI))); 231 typedef signed long fp_sword __attribute__ ((mode(TI))); 232 #else 233 234 #ifndef NO_TFM_64BIT 235 #if defined(_MSC_VER) || defined(__BORLANDC__) 236 typedef unsigned __int64 ulong64; 237 typedef signed __int64 long64; 238 #else 239 typedef unsigned long long ulong64; 240 typedef signed long long long64; 241 #endif 242 typedef unsigned int fp_digit; 243 #define SIZEOF_FP_DIGIT 4 244 typedef ulong64 fp_word; 245 typedef long64 fp_sword; 246 #define FP_32BIT 247 #else 248 /* some procs like coldfire prefer not to place multiply into 64bit type 249 even though it exists */ 250 typedef unsigned short fp_digit; 251 #define SIZEOF_FP_DIGIT 2 252 typedef unsigned int fp_word; 253 typedef signed int fp_sword; 254 #endif 255 #endif 256 257 #endif /* WOLFSSL_BIGINT_TYPES */ 258 259 260 /* # of digits this is */ 261 #define DIGIT_BIT ((CHAR_BIT) * SIZEOF_FP_DIGIT) 262 263 /* Max size of any number in bits. Basically the largest size you will be 264 * multiplying should be half [or smaller] of FP_MAX_SIZE-four_digit 265 * 266 * It defaults to 4096-bits [allowing multiplications up to 2048x2048 bits ] 267 */ 268 269 270 #ifndef FP_MAX_BITS 271 #define FP_MAX_BITS 4096 272 #endif 273 #ifdef WOLFSSL_OPENSSH 274 /* OpenSSH uses some BIG primes so we need to accommodate for that */ 275 #undef FP_MAX_BITS 276 #define FP_MAX_BITS 16384 277 #endif 278 #define FP_MAX_SIZE (FP_MAX_BITS+(8*DIGIT_BIT)) 279 280 /* will this lib work? */ 281 #if CHAR_BIT == 0 282 #error CHAR_BIT must be nonzero 283 #endif 284 #if (CHAR_BIT & 7) 285 #error CHAR_BIT must be a multiple of eight. 286 #endif 287 #if FP_MAX_BITS % CHAR_BIT 288 #error FP_MAX_BITS must be a multiple of CHAR_BIT 289 #endif 290 291 #define FP_MASK (fp_digit)(-1) 292 #define FP_DIGIT_MAX FP_MASK 293 #define FP_SIZE (FP_MAX_SIZE/DIGIT_BIT) 294 #define MP_SIZE (FP_MAX_SIZE/DIGIT_BIT) /* for compatibility with SP_INT */ 295 296 297 #define FP_MAX_PRIME_SIZE (FP_MAX_BITS/(2*CHAR_BIT)) 298 /* In terms of FP_MAX_BITS, it is double the size possible for a number 299 * to allow for multiplication, divide that 2 out. Also divide by CHAR_BIT 300 * to convert from bits to bytes. (Note, FP_PRIME_SIZE is the number of 301 * values in the canned prime number list.) */ 302 303 /* signs */ 304 #define FP_ZPOS 0 305 #define FP_NEG 1 306 307 /* return codes */ 308 #define FP_OKAY 0 309 #define FP_VAL MP_VAL 310 #define FP_MEM MP_MEM 311 #define FP_NOT_INF MP_NOT_INF 312 #define FP_WOULDBLOCK MP_WOULDBLOCK 313 314 /* equalities */ 315 #define FP_LT (-1) /* less than */ 316 #define FP_EQ 0 /* equal to */ 317 #define FP_GT 1 /* greater than */ 318 319 /* replies */ 320 #define FP_YES 1 /* yes response */ 321 #define FP_NO 0 /* no response */ 322 323 324 #ifdef WOLFSSL_SMALL_STACK 325 /* 326 * Dynamic memory allocation of mp_int. 327 */ 328 /* Declare a dynamically allocated mp_int. */ 329 #define DECL_MP_INT_SIZE(name, bits) \ 330 mp_int* name = NULL 331 /* Declare a dynamically allocated mp_int. */ 332 #define DECL_MP_INT_SIZE_DYN(name, bits, max) \ 333 mp_int* name = NULL 334 /* Allocate an mp_int of minimal size and zero out. */ 335 #define NEW_MP_INT_SIZE(name, bits, heap, type) \ 336 do { \ 337 name = (mp_int*)XMALLOC(sizeof(mp_int), heap, type); \ 338 if (name != NULL) { \ 339 XMEMSET(name, 0, sizeof(mp_int)); \ 340 } \ 341 } \ 342 while (0) 343 /* Dispose of dynamically allocated mp_int. */ 344 #define FREE_MP_INT_SIZE(name, heap, type) \ 345 XFREE(name, heap, type) 346 /* Must check for mp_int pointer for NULL. */ 347 #define MP_INT_SIZE_CHECK_NULL 348 #else 349 /* 350 * Static allocation of mp_int. 351 */ 352 /* Declare a statically allocated mp_int. */ 353 #define DECL_MP_INT_SIZE(name, bits) \ 354 mp_int name[1] 355 /* Declare a statically allocated mp_int. */ 356 #define DECL_MP_INT_SIZE_DYN(name, bits, max) \ 357 mp_int name[1] 358 /* Zero out mp_int of minimal size. */ 359 #define NEW_MP_INT_SIZE(name, bits, heap, type) \ 360 XMEMSET(name, 0, sizeof(mp_int)) 361 /* Dispose of static mp_int. */ 362 #define FREE_MP_INT_SIZE(name, heap, type) WC_DO_NOTHING 363 #endif 364 365 /* Initialize an mp_int. */ 366 #define INIT_MP_INT_SIZE(name, bits) \ 367 mp_init(name) 368 /* Type to cast to when using size macros. */ 369 #define MP_INT_SIZE mp_int 370 371 372 #ifdef HAVE_WOLF_BIGINT 373 /* raw big integer */ 374 typedef struct WC_BIGINT { 375 byte* buf; 376 word32 len; 377 void* heap; 378 } WC_BIGINT; 379 #define WOLF_BIGINT_DEFINED 380 #endif 381 382 #define wc_mp_size_t int 383 #define wc_mp_sign_t int 384 385 /* a FP type */ 386 typedef struct fp_int { 387 int used; 388 int sign; 389 #if defined(ALT_ECC_SIZE) || defined(HAVE_WOLF_BIGINT) 390 int size; 391 #endif 392 fp_digit dp[FP_SIZE]; 393 394 #ifdef HAVE_WOLF_BIGINT 395 struct WC_BIGINT raw; /* unsigned binary (big endian) */ 396 #endif 397 } fp_int; 398 399 /* Types */ 400 typedef fp_digit mp_digit; 401 typedef fp_word mp_word; 402 typedef fp_int mp_int; 403 404 405 /* wolf big int and common functions */ 406 #include <wolfssl/wolfcrypt/wolfmath.h> 407 408 409 /* externally define this symbol to ignore the default settings, useful for changing the build from the make process */ 410 #ifndef TFM_ALREADY_SET 411 412 /* do we want the large set of small multiplications ? 413 Enable these if you are going to be doing a lot of small (<= 16 digit) multiplications say in ECC 414 Or if you're on a 64-bit machine doing RSA as a 1024-bit integer == 16 digits ;-) 415 */ 416 /* need to refactor the function */ 417 /*#define TFM_SMALL_SET */ 418 419 /* do we want huge code 420 Enable these if you are doing 20, 24, 28, 32, 48, 64 digit multiplications (useful for RSA) 421 Less important on 64-bit machines as 32 digits == 2048 bits 422 */ 423 #if 0 424 #define TFM_MUL3 425 #define TFM_MUL4 426 #define TFM_MUL6 427 #define TFM_MUL7 428 #define TFM_MUL8 429 #define TFM_MUL9 430 #define TFM_MUL12 431 #define TFM_MUL17 432 #endif 433 #ifdef TFM_HUGE_SET 434 #define TFM_MUL20 435 #define TFM_MUL24 436 #define TFM_MUL28 437 #define TFM_MUL32 438 #if (FP_MAX_BITS >= 6144) && defined(FP_64BIT) 439 #define TFM_MUL48 440 #endif 441 #if (FP_MAX_BITS >= 8192) && defined(FP_64BIT) 442 #define TFM_MUL64 443 #endif 444 #endif 445 446 #if 0 447 #define TFM_SQR3 448 #define TFM_SQR4 449 #define TFM_SQR6 450 #define TFM_SQR7 451 #define TFM_SQR8 452 #define TFM_SQR9 453 #define TFM_SQR12 454 #define TFM_SQR17 455 #endif 456 #ifdef TFM_HUGE_SET 457 #define TFM_SQR20 458 #define TFM_SQR24 459 #define TFM_SQR28 460 #define TFM_SQR32 461 #define TFM_SQR48 462 #define TFM_SQR64 463 #endif 464 465 /* Optional math checks (enable WOLFSSL_DEBUG_MATH to print info) */ 466 /* #define TFM_CHECK */ 467 468 /* Is the target a P4 Prescott 469 */ 470 /* #define TFM_PRESCOTT */ 471 472 /* Do we want timing resistant fp_exptmod() ? 473 * This makes it slower but also timing invariant with respect to the exponent 474 */ 475 /* #define TFM_TIMING_RESISTANT */ 476 477 #endif /* TFM_ALREADY_SET */ 478 479 /* functions */ 480 481 /* returns a TFM ident string useful for debugging... */ 482 /*const char *fp_ident(void);*/ 483 484 /* initialize [or zero] an fp int */ 485 void fp_init(fp_int *a); 486 MP_API void fp_zero(fp_int *a); 487 MP_API void fp_clear(fp_int *a); 488 /* uses ForceZero to clear sensitive memory */ 489 MP_API void fp_forcezero (fp_int * a); 490 MP_API void fp_free(fp_int* a); 491 492 /* zero/one/even/odd/neg/word ? */ 493 #define fp_iszero(a) (((a)->used == 0) ? FP_YES : FP_NO) 494 #define fp_isone(a) \ 495 ((((a)->used == 1) && ((a)->dp[0] == 1) && ((a)->sign == FP_ZPOS)) \ 496 ? FP_YES : FP_NO) 497 #define fp_iseven(a) \ 498 (((a)->used > 0 && (((a)->dp[0] & 1) == 0)) ? FP_YES : FP_NO) 499 #define fp_isodd(a) \ 500 (((a)->used > 0 && (((a)->dp[0] & 1) == 1)) ? FP_YES : FP_NO) 501 #define fp_isneg(a) (((a)->sign != FP_ZPOS) ? FP_YES : FP_NO) 502 #define fp_setneg(a) ((a)->sign = FP_NEG) 503 #define fp_isword(a, w) \ 504 (((((a)->used == 1) && ((a)->dp[0] == (w))) || \ 505 (((w) == 0) && ((a)->used == 0))) ? FP_YES : FP_NO) 506 /* Number of bits used based on used field only. */ 507 #define fp_bitsused(a) ((a)->used * DIGIT_BIT) 508 509 /* set to a small digit */ 510 void fp_set(fp_int *a, fp_digit b); 511 int fp_set_int(fp_int *a, unsigned long b); 512 513 /* check if a bit is set */ 514 int fp_is_bit_set(fp_int *a, fp_digit b); 515 /* set the b bit to 1 */ 516 int fp_set_bit (fp_int * a, fp_digit b); 517 518 /* copy from a to b */ 519 void fp_copy(const fp_int *a, fp_int *b); 520 void fp_init_copy(fp_int *a, fp_int *b); 521 522 /* clamp digits */ 523 #define fp_clamp(a) { while ((a)->used && (a)->dp[(a)->used-1] == 0) --((a)->used); (a)->sign = (a)->used ? (a)->sign : FP_ZPOS; } 524 #define mp_clamp(a) fp_clamp(a) 525 #define mp_grow(a,s) MP_OKAY 526 527 /* negate and absolute */ 528 #define fp_neg(a, b) { fp_copy(a, b); (b)->sign ^= 1; fp_clamp(b); } 529 #define fp_abs(a, b) { fp_copy(a, b); (b)->sign = 0; } 530 531 /* right shift x digits */ 532 void fp_rshd(fp_int *a, int x); 533 534 /* right shift x bits */ 535 void fp_rshb(fp_int *c, int x); 536 537 /* left shift x digits */ 538 int fp_lshd(fp_int *a, int x); 539 540 /* signed comparison */ 541 int fp_cmp(fp_int *a, fp_int *b); 542 543 /* unsigned comparison */ 544 int fp_cmp_mag(fp_int *a, fp_int *b); 545 546 /* power of 2 operations */ 547 void fp_div_2d(fp_int *a, int b, fp_int *c, fp_int *d); 548 void fp_mod_2d(fp_int *a, int b, fp_int *c); 549 int fp_mul_2d(fp_int *a, int b, fp_int *c); 550 void fp_2expt (fp_int *a, int b); 551 int fp_mul_2(fp_int *a, fp_int *b); 552 void fp_div_2(fp_int *a, fp_int *b); 553 /* c = a / 2 (mod b) - constant time (a < b and positive) */ 554 int fp_div_2_mod_ct(fp_int *a, fp_int *b, fp_int *c); 555 556 557 /* Counts the number of lsbs which are zero before the first zero bit */ 558 int fp_cnt_lsb(fp_int *a); 559 560 /* c = a + b */ 561 int fp_add(fp_int *a, fp_int *b, fp_int *c); 562 563 /* c = a - b */ 564 int fp_sub(fp_int *a, fp_int *b, fp_int *c); 565 566 /* c = a * b */ 567 int fp_mul(fp_int *a, fp_int *b, fp_int *c); 568 569 /* b = a*a */ 570 int fp_sqr(fp_int *a, fp_int *b); 571 572 /* a/b => cb + d == a */ 573 int fp_div(fp_int *a, fp_int *b, fp_int *c, fp_int *d); 574 575 /* c = a mod b, 0 <= c < b */ 576 int fp_mod(fp_int *a, fp_int *b, fp_int *c); 577 578 /* compare against a single digit */ 579 int fp_cmp_d(fp_int *a, fp_digit b); 580 581 /* c = a + b */ 582 int fp_add_d(fp_int *a, fp_digit b, fp_int *c); 583 584 /* c = a - b */ 585 int fp_sub_d(fp_int *a, fp_digit b, fp_int *c); 586 587 /* c = a * b */ 588 int fp_mul_d(fp_int *a, fp_digit b, fp_int *c); 589 590 /* a/b => cb + d == a */ 591 /*int fp_div_d(fp_int *a, fp_digit b, fp_int *c, fp_digit *d);*/ 592 593 /* c = a mod b, 0 <= c < b */ 594 /*int fp_mod_d(fp_int *a, fp_digit b, fp_digit *c);*/ 595 596 /* ---> number theory <--- */ 597 /* d = a + b (mod c) */ 598 /*int fp_addmod(fp_int *a, fp_int *b, fp_int *c, fp_int *d);*/ 599 600 /* d = a - b (mod c) */ 601 /*int fp_submod(fp_int *a, fp_int *b, fp_int *c, fp_int *d);*/ 602 603 /* d = a * b (mod c) */ 604 int fp_mulmod(fp_int *a, fp_int *b, fp_int *c, fp_int *d); 605 606 /* d = a - b (mod c) */ 607 int fp_submod(fp_int *a, fp_int *b, fp_int *c, fp_int *d); 608 609 /* d = a + b (mod c) */ 610 int fp_addmod(fp_int *a, fp_int *b, fp_int *c, fp_int *d); 611 612 /* d = a - b (mod c) - constant time (a < c and b < c) */ 613 int fp_submod_ct(fp_int *a, fp_int *b, fp_int *c, fp_int *d); 614 615 /* d = a + b (mod c) - constant time (a < c and b < c) */ 616 int fp_addmod_ct(fp_int *a, fp_int *b, fp_int *c, fp_int *d); 617 618 /* c = a * a (mod b) */ 619 int fp_sqrmod(fp_int *a, fp_int *b, fp_int *c); 620 621 /* c = 1/a (mod b) */ 622 int fp_invmod(fp_int *a, fp_int *b, fp_int *c); 623 int fp_invmod_mont_ct(fp_int *a, fp_int *b, fp_int *c, fp_digit mp); 624 625 /* c = (a, b) */ 626 /*int fp_gcd(fp_int *a, fp_int *b, fp_int *c);*/ 627 628 /* c = [a, b] */ 629 /*int fp_lcm(fp_int *a, fp_int *b, fp_int *c);*/ 630 631 /* setups the montgomery reduction */ 632 int fp_montgomery_setup(fp_int *a, fp_digit *rho); 633 634 /* computes a = B**n mod b without division or multiplication useful for 635 * normalizing numbers in a Montgomery system. 636 */ 637 int fp_montgomery_calc_normalization(fp_int *a, fp_int *b); 638 639 /* computes x/R == x (mod N) via Montgomery Reduction */ 640 int fp_montgomery_reduce(fp_int *a, fp_int *m, fp_digit mp); 641 int fp_montgomery_reduce_ex(fp_int *a, fp_int *m, fp_digit mp, int ct); 642 643 /* d = a**b (mod c) */ 644 int fp_exptmod(fp_int *G, fp_int *X, fp_int *P, fp_int *Y); 645 int fp_exptmod_ex(fp_int *G, fp_int *X, int minDigits, fp_int *P, fp_int *Y); 646 int fp_exptmod_nct(fp_int *G, fp_int *X, fp_int *P, fp_int *Y); 647 648 #ifdef WC_RSA_NONBLOCK 649 650 enum tfmExptModNbState { 651 TFM_EXPTMOD_NB_INIT = 0, 652 TFM_EXPTMOD_NB_MONT, 653 TFM_EXPTMOD_NB_MONT_RED, 654 TFM_EXPTMOD_NB_MONT_MUL, 655 TFM_EXPTMOD_NB_MONT_MOD, 656 TFM_EXPTMOD_NB_MONT_MODCHK, 657 TFM_EXPTMOD_NB_NEXT, 658 TFM_EXPTMOD_NB_MUL, 659 TFM_EXPTMOD_NB_MUL_RED, 660 TFM_EXPTMOD_NB_SQR, 661 TFM_EXPTMOD_NB_SQR_RED, 662 TFM_EXPTMOD_NB_RED, 663 TFM_EXPTMOD_NB_COUNT /* last item for total state count only */ 664 }; 665 666 typedef struct { 667 #ifndef WC_NO_CACHE_RESISTANT 668 fp_int R[3]; 669 #else 670 fp_int R[2]; 671 #endif 672 fp_digit buf; 673 fp_digit mp; 674 int bitcnt; 675 int digidx; 676 int y; 677 int state; /* tfmExptModNbState */ 678 #ifdef WC_RSA_NONBLOCK_TIME 679 word32 maxBlockInst; /* maximum instructions to block */ 680 word32 totalInst; /* tracks total instructions */ 681 #endif 682 } exptModNb_t; 683 684 #ifdef WC_RSA_NONBLOCK_TIME 685 enum { 686 TFM_EXPTMOD_NB_STOP = 0, /* stop and return FP_WOULDBLOCK */ 687 TFM_EXPTMOD_NB_CONTINUE = 1, /* keep blocking */ 688 }; 689 #endif 690 691 /* non-blocking version of timing resistant fp_exptmod function */ 692 /* supports cache resistance */ 693 int fp_exptmod_nb(exptModNb_t* nb, fp_int* G, fp_int* X, fp_int* P, fp_int* Y); 694 695 #endif /* WC_RSA_NONBLOCK */ 696 697 /* primality stuff */ 698 699 /* perform a Miller-Rabin test of a to the base b and store result in "result" */ 700 /*void fp_prime_miller_rabin (fp_int * a, fp_int * b, int *result);*/ 701 702 #define FP_PRIME_SIZE 256 703 /* 256 trial divisions + 8 Miller-Rabins, returns FP_YES if probable prime */ 704 /*int fp_isprime(fp_int *a);*/ 705 /* extended version of fp_isprime, do 't' Miller-Rabins instead of only 8 */ 706 /*int fp_isprime_ex(fp_int *a, int t, int* result);*/ 707 708 /* Primality generation flags */ 709 /*#define TFM_PRIME_BBS 0x0001 */ /* BBS style prime */ 710 /*#define TFM_PRIME_SAFE 0x0002 */ /* Safe prime (p-1)/2 == prime */ 711 /*#define TFM_PRIME_2MSB_OFF 0x0004 */ /* force 2nd MSB to 0 */ 712 /*#define TFM_PRIME_2MSB_ON 0x0008 */ /* force 2nd MSB to 1 */ 713 714 /* callback for fp_prime_random, should fill dst with random bytes and return how many read [up to len] */ 715 /*typedef int tfm_prime_callback(unsigned char *dst, int len, void *dat);*/ 716 717 /*#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)*/ 718 719 /*int fp_prime_random_ex(fp_int *a, int t, int size, int flags, tfm_prime_callback cb, void *dat);*/ 720 721 /* radix conversions */ 722 int fp_count_bits(const fp_int *a); 723 int fp_leading_bit(fp_int *a); 724 725 int fp_unsigned_bin_size(const fp_int *a); 726 int fp_read_unsigned_bin(fp_int *a, const unsigned char *b, int c); 727 int fp_to_unsigned_bin(fp_int *a, unsigned char *b); 728 int fp_to_unsigned_bin_len_ct(fp_int *a, unsigned char *out, int outSz); 729 int fp_to_unsigned_bin_len(fp_int *a, unsigned char *b, int c); 730 int fp_to_unsigned_bin_at_pos(int x, fp_int *t, unsigned char *b); 731 732 /*int fp_read_radix(fp_int *a, char *str, int radix);*/ 733 /*int fp_toradix(fp_int *a, char *str, int radix);*/ 734 /*int fp_toradix_n(fp_int * a, char *str, int radix, int maxlen);*/ 735 736 737 /* VARIOUS LOW LEVEL STUFFS */ 738 int s_fp_add(fp_int *a, fp_int *b, fp_int *c); 739 void s_fp_sub(fp_int *a, fp_int *b, fp_int *c); 740 741 int fp_mul_comba(fp_int *a, fp_int *b, fp_int *c); 742 743 int fp_mul_comba_small(fp_int *a, fp_int *b, fp_int *c); 744 int fp_mul_comba3(fp_int *a, fp_int *b, fp_int *c); 745 int fp_mul_comba4(fp_int *a, fp_int *b, fp_int *c); 746 int fp_mul_comba6(fp_int *a, fp_int *b, fp_int *c); 747 int fp_mul_comba7(fp_int *a, fp_int *b, fp_int *c); 748 int fp_mul_comba8(fp_int *a, fp_int *b, fp_int *c); 749 int fp_mul_comba9(fp_int *a, fp_int *b, fp_int *c); 750 int fp_mul_comba12(fp_int *a, fp_int *b, fp_int *c); 751 int fp_mul_comba17(fp_int *a, fp_int *b, fp_int *c); 752 int fp_mul_comba20(fp_int *a, fp_int *b, fp_int *c); 753 int fp_mul_comba24(fp_int *a, fp_int *b, fp_int *c); 754 int fp_mul_comba28(fp_int *a, fp_int *b, fp_int *c); 755 int fp_mul_comba32(fp_int *a, fp_int *b, fp_int *c); 756 int fp_mul_comba48(fp_int *a, fp_int *b, fp_int *c); 757 int fp_mul_comba64(fp_int *a, fp_int *b, fp_int *c); 758 int fp_sqr_comba(fp_int *a, fp_int *b); 759 int fp_sqr_comba_small(fp_int *a, fp_int *b); 760 int fp_sqr_comba3(fp_int *a, fp_int *b); 761 int fp_sqr_comba4(fp_int *a, fp_int *b); 762 int fp_sqr_comba6(fp_int *a, fp_int *b); 763 int fp_sqr_comba7(fp_int *a, fp_int *b); 764 int fp_sqr_comba8(fp_int *a, fp_int *b); 765 int fp_sqr_comba9(fp_int *a, fp_int *b); 766 int fp_sqr_comba12(fp_int *a, fp_int *b); 767 int fp_sqr_comba17(fp_int *a, fp_int *b); 768 int fp_sqr_comba20(fp_int *a, fp_int *b); 769 int fp_sqr_comba24(fp_int *a, fp_int *b); 770 int fp_sqr_comba28(fp_int *a, fp_int *b); 771 int fp_sqr_comba32(fp_int *a, fp_int *b); 772 int fp_sqr_comba48(fp_int *a, fp_int *b); 773 int fp_sqr_comba64(fp_int *a, fp_int *b); 774 775 776 /** 777 * Used by wolfSSL 778 */ 779 780 /* Constants */ 781 #define MP_LT FP_LT /* less than */ 782 #define MP_EQ FP_EQ /* equal to */ 783 #define MP_GT FP_GT /* greater than */ 784 #define MP_RANGE MP_NOT_INF 785 #define MP_OKAY FP_OKAY /* ok result */ 786 #define MP_NO FP_NO /* yes/no result */ 787 #define MP_YES FP_YES /* yes/no result */ 788 #define MP_ZPOS FP_ZPOS 789 #define MP_NEG FP_NEG 790 #define MP_MASK FP_MASK 791 792 /* Prototypes */ 793 #define mp_zero(a) fp_zero(a) 794 #define mp_isone(a) fp_isone(a) 795 #define mp_iseven(a) fp_iseven(a) 796 #define mp_isneg(a) fp_isneg(a) 797 #define mp_setneg(a) fp_setneg(a) 798 #define mp_isword(a, w) fp_isword(a, w) 799 #define mp_bitsused(a) fp_bitsused(a) 800 801 #define MP_RADIX_BIN 2 802 #define MP_RADIX_OCT 8 803 #define MP_RADIX_DEC 10 804 #define MP_RADIX_HEX 16 805 #define MP_RADIX_MAX 64 806 807 #define mp_tobinary(M, S) mp_toradix((M), (S), MP_RADIX_BIN) 808 #define mp_tooctal(M, S) mp_toradix((M), (S), MP_RADIX_OCT) 809 #define mp_todecimal(M, S) mp_toradix((M), (S), MP_RADIX_DEC) 810 #define mp_tohex(M, S) mp_toradix((M), (S), MP_RADIX_HEX) 811 812 MP_API int mp_init (mp_int * a); 813 MP_API int mp_init_copy(fp_int * a, fp_int * b); 814 MP_API void mp_clear (mp_int * a); 815 MP_API void mp_free (mp_int * a); 816 MP_API void mp_forcezero (mp_int * a); 817 MP_API int mp_init_multi(mp_int* a, mp_int* b, mp_int* c, mp_int* d, mp_int* e, 818 mp_int* f); 819 820 MP_API int mp_add (mp_int * a, mp_int * b, mp_int * c); 821 MP_API int mp_sub (mp_int * a, mp_int * b, mp_int * c); 822 MP_API int mp_add_d (mp_int * a, mp_digit b, mp_int * c); 823 824 MP_API int mp_mul (mp_int * a, mp_int * b, mp_int * c); 825 MP_API int mp_mul_d (mp_int * a, mp_digit b, mp_int * c); 826 MP_API int mp_mulmod (mp_int * a, mp_int * b, mp_int * c, mp_int * d); 827 MP_API int mp_submod (mp_int* a, mp_int* b, mp_int* c, mp_int* d); 828 MP_API int mp_addmod (mp_int* a, mp_int* b, mp_int* c, mp_int* d); 829 MP_API int mp_submod_ct (mp_int* a, mp_int* b, mp_int* c, mp_int* d); 830 MP_API int mp_addmod_ct (mp_int* a, mp_int* b, mp_int* c, mp_int* d); 831 MP_API int mp_mod(mp_int *a, mp_int *b, mp_int *c); 832 MP_API int mp_invmod(mp_int *a, mp_int *b, mp_int *c); 833 MP_API int mp_invmod_mont_ct(mp_int *a, mp_int *b, mp_int *c, fp_digit mp); 834 MP_API int mp_exptmod (mp_int * g, mp_int * x, mp_int * p, mp_int * y); 835 MP_API int mp_exptmod_ex (mp_int * g, mp_int * x, int minDigits, mp_int * p, 836 mp_int * y); 837 MP_API int mp_exptmod_nct (mp_int * g, mp_int * x, mp_int * p, mp_int * y); 838 MP_API int mp_mul_2d(mp_int *a, int b, mp_int *c); 839 MP_API int mp_2expt(mp_int* a, int b); 840 841 MP_API int mp_div(mp_int * a, mp_int * b, mp_int * c, mp_int * d); 842 843 MP_API int mp_cmp(mp_int *a, mp_int *b); 844 #define mp_cmp_ct(a, b, n) mp_cmp(a, b) 845 MP_API int mp_cmp_d(mp_int *a, mp_digit b); 846 847 MP_API int mp_unsigned_bin_size(const mp_int * a); 848 MP_API int mp_read_unsigned_bin (mp_int * a, const unsigned char *b, int c); 849 MP_API int mp_to_unsigned_bin_at_pos(int x, mp_int *t, unsigned char *b); 850 MP_API int mp_to_unsigned_bin (mp_int * a, unsigned char *b); 851 MP_API int mp_to_unsigned_bin_len_ct(mp_int * a, unsigned char *b, int c); 852 MP_API int mp_to_unsigned_bin_len(mp_int * a, unsigned char *b, int c); 853 854 MP_API int mp_sub_d(fp_int *a, fp_digit b, fp_int *c); 855 MP_API int mp_copy(const fp_int* a, fp_int* b); 856 MP_API int mp_isodd(const mp_int* a); 857 MP_API int mp_iszero(const mp_int* a); 858 MP_API int mp_count_bits(const mp_int *a); 859 MP_API int mp_leading_bit(mp_int *a); 860 MP_API int mp_set_int(mp_int *a, unsigned long b); 861 MP_API int mp_is_bit_set (mp_int * a, mp_digit b); 862 MP_API int mp_set_bit (mp_int * a, mp_digit b); 863 MP_API void mp_rshb(mp_int *a, int x); 864 MP_API void mp_rshd(mp_int *a, int x); 865 MP_API int mp_toradix (mp_int *a, char *str, int radix); 866 MP_API int mp_radix_size (mp_int * a, int radix, int *size); 867 868 #ifdef WOLFSSL_DEBUG_MATH 869 MP_API void mp_dump(const char* desc, mp_int* a, byte verbose); 870 #else 871 #define mp_dump(desc, a, verbose) WC_DO_NOTHING 872 #endif 873 874 #if defined(OPENSSL_EXTRA) || !defined(NO_DSA) || defined(HAVE_ECC) 875 MP_API int mp_read_radix(mp_int* a, const char* str, int radix); 876 #endif 877 878 #define mp_montgomery_reduce_ct(a, m, mp) \ 879 mp_montgomery_reduce_ex(a, m, mp, 1) 880 MP_API int mp_montgomery_reduce(fp_int *a, fp_int *m, fp_digit mp); 881 MP_API int mp_montgomery_reduce_ex(fp_int *a, fp_int *m, fp_digit mp, int ct); 882 MP_API int mp_montgomery_setup(fp_int *a, fp_digit *rho); 883 MP_API int mp_sqr(fp_int *a, fp_int *b); 884 885 #ifdef HAVE_ECC 886 MP_API int mp_div_2(fp_int * a, fp_int * b); 887 MP_API int mp_div_2_mod_ct(mp_int *a, mp_int *b, mp_int *c); 888 #endif 889 890 #if defined(HAVE_ECC) || !defined(NO_RSA) || !defined(NO_DSA) || \ 891 defined(WOLFSSL_KEY_GEN) 892 MP_API int mp_set(fp_int *a, fp_digit b); 893 #endif 894 895 #if defined(HAVE_ECC) || defined(WOLFSSL_KEY_GEN) || !defined(NO_RSA) || \ 896 !defined(NO_DSA) || !defined(NO_DH) 897 MP_API int mp_sqrmod(mp_int* a, mp_int* b, mp_int* c); 898 MP_API int mp_montgomery_calc_normalization(mp_int *a, mp_int *b); 899 #endif 900 901 #if !defined(NO_DH) || !defined(NO_DSA) || !defined(NO_RSA) || defined(WOLFSSL_KEY_GEN) 902 MP_API int mp_prime_is_prime(mp_int* a, int t, int* result); 903 MP_API int mp_prime_is_prime_ex(mp_int* a, int t, int* result, WC_RNG* rng); 904 #endif /* !NO_DH || !NO_DSA || !NO_RSA || WOLFSSL_KEY_GEN */ 905 #ifdef WOLFSSL_KEY_GEN 906 MP_API int mp_gcd(fp_int *a, fp_int *b, fp_int *c); 907 MP_API int mp_lcm(fp_int *a, fp_int *b, fp_int *c); 908 MP_API int mp_rand_prime(mp_int* a, int len, WC_RNG* rng, void* heap); 909 MP_API int mp_exch(mp_int *a, mp_int *b); 910 #endif /* WOLFSSL_KEY_GEN */ 911 MP_API int mp_cond_swap_ct_ex(mp_int* a, mp_int* b, int c, int m, mp_int* t); 912 MP_API int mp_cond_swap_ct(mp_int* a, mp_int* b, int c, int m); 913 914 MP_API int mp_cnt_lsb(fp_int *a); 915 MP_API int mp_div_2d(fp_int *a, int b, fp_int *c, fp_int *d); 916 MP_API int mp_mod_2d(fp_int *a, int b, fp_int *c); 917 MP_API int mp_mod_d(fp_int* a, fp_digit b, fp_digit* c); 918 MP_API int mp_lshd (mp_int * a, int b); 919 MP_API int mp_abs(mp_int* a, mp_int* b); 920 921 WOLFSSL_API word32 CheckRunTimeFastMath(void); 922 923 #ifdef WOLFSSL_CHECK_MEM_ZERO 924 void mp_memzero_add(const char* name, mp_int* a); 925 void mp_memzero_check(mp_int* a); 926 #endif 927 928 /* If user uses RSA, DH, DSA, or ECC math lib directly then fast math FP_SIZE 929 must match, return 1 if a match otherwise 0 */ 930 #define CheckFastMathSettings() (FP_SIZE == CheckRunTimeFastMath()) 931 932 933 #ifdef __cplusplus 934 } 935 #endif 936 937 #endif /* WOLF_CRYPT_TFM_H */ 938