luna - wolfssl/wolfcrypt/src/tfm.c

   1/* tfm.c
   2 *
   3 * Copyright (C) 2006-2026 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#include <wolfssl/wolfcrypt/libwolfssl_sources.h>
  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 *  Edited by Moises Guimaraes (moises@wolfssl.com)
  31 *  to fit wolfSSL's needs.
  32 */
  33
  34#ifdef USE_FAST_MATH
  35
  36#ifdef NO_INLINE
  37    #include <wolfssl/wolfcrypt/misc.h>
  38#else
  39    #define WOLFSSL_MISC_INCLUDED
  40    #include <wolfcrypt/src/misc.c>
  41#endif
  42
  43#include <wolfssl/wolfcrypt/random.h>
  44#include <wolfssl/wolfcrypt/tfm.h>
  45#include <wolfcrypt/src/asm.c>  /* will define asm MACROS or C ones */
  46#include <wolfssl/wolfcrypt/wolfmath.h> /* common functions */
  47#include <wolfssl/wolfcrypt/logging.h>
  48
  49#ifdef WOLFSSL_ESPIDF
  50    #include <esp_log.h>
  51    #include <wolfssl/wolfcrypt/port/Espressif/esp32-crypt.h>
  52#endif
  53
  54#if defined(WOLFSSL_ESP32_CRYPT_RSA_PRI)
  55    static const char* TAG = "TFM"; /* esp log breadcrumb */
  56    #if !defined(NO_WOLFSSL_ESP32_CRYPT_RSA_PRI)
  57        /* Each individual math HW can be turned on or off.
  58         * Listed in order of complexity and historical difficulty. */
  59        #define WOLFSSL_ESP32_CRYPT_RSA_PRI_MP_MUL
  60        #define WOLFSSL_ESP32_CRYPT_RSA_PRI_EXPTMOD
  61        #define WOLFSSL_ESP32_CRYPT_RSA_PRI_MULMOD
  62    #endif
  63
  64    #if defined(NO_WOLFSSL_ESP32_CRYPT_RSA_PRI_MP_MUL)
  65        #undef WOLFSSL_ESP32_CRYPT_RSA_PRI_MP_MUL
  66    #endif
  67
  68    #if defined(NO_WOLFSSL_ESP32_CRYPT_RSA_PRI_EXPTMOD)
  69        #undef WOLFSSL_ESP32_CRYPT_RSA_PRI_EXPTMOD
  70    #endif
  71
  72    #if defined(NO_WOLFSSL_ESP32_CRYPT_RSA_PRI_MULMOD)
  73        #undef WOLFSSL_ESP32_CRYPT_RSA_PRI_MULMOD
  74    #endif
  75
  76    /* Note with HW there's a ESP_RSA_EXPT_XBITS setting
  77     * as for some small numbers, SW may be faster.
  78     * See ESP_LOGV messages for ESP_RSA_EXPT_XBITS values. */
  79
  80#endif /* WOLFSSL_ESP32_CRYPT_RSA_PRI */
  81
  82#if defined(FREESCALE_LTC_TFM)
  83    #include <wolfssl/wolfcrypt/port/nxp/ksdk_port.h>
  84#endif
  85#ifdef WOLFSSL_DEBUG_MATH
  86    #include <stdio.h>
  87#endif
  88
  89#if defined(WOLFSSL_HAVE_SP_RSA) || defined(WOLFSSL_HAVE_SP_DH)
  90#ifdef __cplusplus
  91    extern "C" {
  92#endif
  93WOLFSSL_LOCAL int sp_ModExp_1024(mp_int* base, mp_int* exp, mp_int* mod,
  94    mp_int* res);
  95WOLFSSL_LOCAL int sp_ModExp_1536(mp_int* base, mp_int* exp, mp_int* mod,
  96    mp_int* res);
  97WOLFSSL_LOCAL int sp_ModExp_2048(mp_int* base, mp_int* exp, mp_int* mod,
  98    mp_int* res);
  99WOLFSSL_LOCAL int sp_ModExp_3072(mp_int* base, mp_int* exp, mp_int* mod,
 100    mp_int* res);
 101WOLFSSL_LOCAL int sp_ModExp_4096(mp_int* base, mp_int* exp, mp_int* mod,
 102    mp_int* res);
 103#ifdef __cplusplus
 104    } /* extern "C" */
 105#endif
 106#endif
 107
 108
 109#if !defined(WOLFSSL_SP_MATH) && !defined(WOLFSSL_SP_MATH_ALL)
 110/* math settings check */
 111word32 CheckRunTimeSettings(void)
 112{
 113    return CTC_SETTINGS;
 114}
 115
 116/* math settings size check */
 117word32 CheckRunTimeFastMath(void)
 118{
 119    return FP_SIZE;
 120}
 121#endif
 122
 123
 124/* Functions */
 125
 126int fp_add(fp_int *a, fp_int *b, fp_int *c)
 127{
 128  int sa, sb;
 129  int ret = FP_OKAY;
 130
 131  /* get sign of both inputs */
 132  sa = a->sign;
 133  sb = b->sign;
 134
 135  /* handle two cases, not four */
 136  if (sa == sb) {
 137    /* both positive or both negative */
 138    /* add their magnitudes, copy the sign */
 139    c->sign = sa;
 140    ret = s_fp_add (a, b, c);
 141  } else {
 142    /* one positive, the other negative */
 143    /* subtract the one with the greater magnitude from */
 144    /* the one of the lesser magnitude.  The result gets */
 145    /* the sign of the one with the greater magnitude. */
 146    if (fp_cmp_mag (a, b) == FP_LT) {
 147      c->sign = sb;
 148      s_fp_sub (b, a, c);
 149    } else {
 150      c->sign = sa;
 151      s_fp_sub (a, b, c);
 152    }
 153  }
 154
 155  return ret;
 156}
 157
 158/* unsigned addition */
 159int s_fp_add(fp_int *a, fp_int *b, fp_int *c)
 160{
 161  int      x, y, oldused;
 162  fp_word  t;
 163
 164  y       = MAX(a->used, b->used);
 165  oldused = MIN(c->used, FP_SIZE);   /* help static analysis w/ largest size */
 166  c->used = y;
 167
 168  t = 0;
 169#ifdef HONOR_MATH_USED_LENGTH
 170  for (x = 0; x < y; x++) {
 171      if ( (x < a->used) && (x < b->used) ) {
 172          /* x is less than both [a].used and [b].used, so we add both */
 173                  t += ((fp_word)a->dp[x])    +    ((fp_word)b->dp[x]);
 174      }
 175      else {
 176          /* Here we honor the actual [a].used and [b].used values
 177           * and NOT assume that values beyond [used] are zero. */
 178          if ((x >= a->used) && (x < b->used)) {
 179                  /* x more than [a].used, [b] ok, so just add [b] */
 180                  t += /* ((fp_word)(0))      + */ ((fp_word)b->dp[x]);
 181          }
 182          else {
 183              if ((x < a->used) && (x >= b->used)) {
 184                  /* x more than [b].used, [a] ok, so just add [a] */
 185                  t += ((fp_word)a->dp[x]) /* +     (fp_word)(0) */;
 186              }
 187              else {
 188                  /* we should never get here, as a.used cannot be greater
 189                   * than b.used, while b.used is greater than a.used! */
 190               /* t += 0 + 0 */
 191              }
 192          }
 193      }
 194      c->dp[x]   = (fp_digit)t;
 195      t        >>= DIGIT_BIT;
 196  }
 197
 198#else
 199  /* the original code */
 200  for (x = 0; x < y; x++) {
 201      t         += ((fp_word)a->dp[x]) + ((fp_word)b->dp[x]);
 202      c->dp[x]   = (fp_digit)t;
 203      t        >>= DIGIT_BIT;
 204  }
 205#endif /* HONOR_MATH_USED_LENGTH */
 206
 207  if (t != 0) {
 208     if (x == FP_SIZE)
 209         return FP_VAL;
 210     c->dp[c->used++] = (fp_digit)t;
 211     ++x;
 212  }
 213
 214  c->used = x;
 215
 216  /* zero any excess digits on the destination that we didn't write to */
 217  for (; x < oldused; x++) {
 218     c->dp[x] = 0;
 219  }
 220  fp_clamp(c);
 221  return FP_OKAY;
 222}
 223
 224/* c = a - b */
 225int fp_sub(fp_int *a, fp_int *b, fp_int *c)
 226{
 227  int sa, sb;
 228  int ret = FP_OKAY;
 229
 230  sa = a->sign;
 231  sb = b->sign;
 232
 233  if (sa != sb) {
 234    /* subtract a negative from a positive, OR */
 235    /* subtract a positive from a negative. */
 236    /* In either case, ADD their magnitudes, */
 237    /* and use the sign of the first number. */
 238    c->sign = sa;
 239    ret = s_fp_add (a, b, c);
 240  } else {
 241    /* subtract a positive from a positive, OR */
 242    /* subtract a negative from a negative. */
 243    /* First, take the difference between their */
 244    /* magnitudes, then... */
 245    if (fp_cmp_mag (a, b) != FP_LT) {
 246      /* Copy the sign from the first */
 247      c->sign = sa;
 248      /* The first has a larger or equal magnitude */
 249      s_fp_sub (a, b, c);
 250    } else {
 251      /* The result has the *opposite* sign from */
 252      /* the first number. */
 253      c->sign = (sa == FP_ZPOS) ? FP_NEG : FP_ZPOS;
 254      /* The second has a larger magnitude */
 255      s_fp_sub (b, a, c);
 256    }
 257  }
 258  return ret;
 259}
 260
 261/* unsigned subtraction ||a|| >= ||b|| ALWAYS! */
 262void s_fp_sub(fp_int *a, fp_int *b, fp_int *c)
 263{
 264  int      x, oldbused, oldused;
 265  fp_word  t;
 266
 267  oldused  = c->used;
 268  oldbused = b->used;
 269  c->used  = a->used;
 270  t       = 0;
 271  for (x = 0; x < oldbused; x++) {
 272     t         = ((fp_word)a->dp[x]) - (((fp_word)b->dp[x]) + t);
 273     c->dp[x]  = (fp_digit)t;
 274     t         = (t >> DIGIT_BIT)&1;
 275  }
 276  for (; x < a->used; x++) {
 277     t         = ((fp_word)a->dp[x]) - t;
 278     c->dp[x]  = (fp_digit)t;
 279     t         = (t >> DIGIT_BIT)&1;
 280   }
 281
 282  /* zero any excess digits on the destination that we didn't write to */
 283  for (; x < oldused; x++) {
 284     c->dp[x] = 0;
 285  }
 286  fp_clamp(c);
 287}
 288
 289/* c = a * b */
 290int fp_mul(fp_int *A, fp_int *B, fp_int *C)
 291{
 292    int   ret = FP_OKAY;
 293    int   y, yy, oldused;
 294
 295    oldused = C->used;
 296
 297    y  = MAX(A->used, B->used);
 298    yy = MIN(A->used, B->used);
 299
 300    /* fail if we are out of range */
 301    if (y + yy >= FP_SIZE) {
 302       ret = FP_VAL;
 303       goto clean;
 304    }
 305
 306#if defined(WOLFSSL_ESP32_CRYPT_RSA_PRI_MP_MUL)
 307    if (esp_hw_validation_active()) {
 308        ESP_LOGV(TAG, "Skipping call to esp_mp_mul "
 309                      "during active validation.");
 310    }
 311    else {
 312        ret = esp_mp_mul(A, B, C); /* HW accelerated multiply  */
 313        switch (ret) {
 314            case MP_OKAY:
 315                goto clean; /* success */
 316                break;
 317
 318            case WC_NO_ERR_TRACE(WC_HW_WAIT_E): /* MP_HW_BUSY math HW busy, fall back */
 319            case MP_HW_FALLBACK:    /* forced fallback from HW to SW */
 320            case MP_HW_VALIDATION_ACTIVE: /* use SW to compare to HW */
 321                /* fall back to software, below */
 322                break;
 323
 324            default:
 325                /* Once we've failed, exit without trying to continue.
 326                 * We may have mangled operands: (e.g. Z = X * Z)
 327                 * Future implementation may consider saving operands,
 328                 * but errors should never occur. */
 329                goto clean;  /* error */
 330                break;
 331        }
 332    }
 333    /* fall through to software calcs */
 334#endif /* WOLFSSL_ESP32_CRYPT_RSA_PRI_MP_MUL */
 335
 336    /* pick a comba (unrolled 4/8/16/32 x or rolled) based on the size
 337       of the largest input.  We also want to avoid doing excess mults if the
 338       inputs are not close to the next power of two.  That is, for example,
 339       if say y=17 then we would do (32-17)^2 = 225 unneeded multiplications
 340    */
 341
 342#if defined(TFM_MUL3) && FP_SIZE >= 6
 343        if (y <= 3) {
 344           ret = fp_mul_comba3(A,B,C);
 345           goto clean;
 346        }
 347#endif
 348#if defined(TFM_MUL4) && FP_SIZE >= 8
 349        if (y == 4) {
 350           ret = fp_mul_comba4(A,B,C);
 351           goto clean;
 352        }
 353#endif
 354#if defined(TFM_MUL6) && FP_SIZE >= 12
 355        if (y <= 6) {
 356           ret = fp_mul_comba6(A,B,C);
 357           goto clean;
 358        }
 359#endif
 360#if defined(TFM_MUL7) && FP_SIZE >= 14
 361        if (y == 7) {
 362           ret = fp_mul_comba7(A,B,C);
 363           goto clean;
 364        }
 365#endif
 366#if defined(TFM_MUL8) && FP_SIZE >= 16
 367        if (y == 8) {
 368           ret = fp_mul_comba8(A,B,C);
 369           goto clean;
 370        }
 371#endif
 372#if defined(TFM_MUL9) && FP_SIZE >= 18
 373        if (y == 9) {
 374           ret = fp_mul_comba9(A,B,C);
 375           goto clean;
 376        }
 377#endif
 378#if defined(TFM_MUL12) && FP_SIZE >= 24
 379        if (y <= 12) {
 380           ret = fp_mul_comba12(A,B,C);
 381           goto clean;
 382        }
 383#endif
 384#if defined(TFM_MUL17) && FP_SIZE >= 34
 385        if (y <= 17) {
 386           ret = fp_mul_comba17(A,B,C);
 387           goto clean;
 388        }
 389#endif
 390
 391#if defined(TFM_SMALL_SET) && FP_SIZE >= 32
 392        if (y <= 16) {
 393           ret = fp_mul_comba_small(A,B,C);
 394           goto clean;
 395        }
 396#endif
 397#if defined(TFM_MUL20) && FP_SIZE >= 40
 398        if (y <= 20) {
 399           ret = fp_mul_comba20(A,B,C);
 400           goto clean;
 401        }
 402#endif
 403#if defined(TFM_MUL24) && FP_SIZE >= 48
 404        if (yy >= 16 && y <= 24) {
 405           ret = fp_mul_comba24(A,B,C);
 406           goto clean;
 407        }
 408#endif
 409#if defined(TFM_MUL28) && FP_SIZE >= 56
 410        if (yy >= 20 && y <= 28) {
 411           ret = fp_mul_comba28(A,B,C);
 412           goto clean;
 413        }
 414#endif
 415#if defined(TFM_MUL32) && FP_SIZE >= 64
 416        if (yy >= 24 && y <= 32) {
 417           ret = fp_mul_comba32(A,B,C);
 418           goto clean;
 419        }
 420#endif
 421#if defined(TFM_MUL48) && FP_SIZE >= 96
 422        if (yy >= 40 && y <= 48) {
 423          ret = fp_mul_comba48(A,B,C);
 424          goto clean;
 425        }
 426#endif
 427#if defined(TFM_MUL64) && FP_SIZE >= 128
 428        if (yy >= 56 && y <= 64) {
 429           ret = fp_mul_comba64(A,B,C);
 430           goto clean;
 431        }
 432#endif
 433        ret = fp_mul_comba(A,B,C);
 434
 435clean:
 436    /* zero any excess digits on the destination that we didn't write to */
 437    for (y = C->used; y >= 0 && y < oldused; y++) {
 438        C->dp[y] = 0;
 439    }
 440
 441    return ret;
 442}
 443
 444int fp_mul_2(fp_int * a, fp_int * b)
 445{
 446  int     x, oldused;
 447
 448  /* Make sure value to double and result are in range. */
 449  if ((a->used > (FP_SIZE-1)) || ((a->used == (FP_SIZE - 1)) &&
 450              ((a->dp[FP_SIZE - 1] & ((fp_digit)1 << (DIGIT_BIT - 1))) != 0))) {
 451    return FP_VAL;
 452  }
 453
 454  oldused = b->used;
 455  b->used = a->used;
 456
 457  {
 458    fp_digit r, rr, *tmpa, *tmpb;
 459
 460    /* alias for source */
 461    tmpa = a->dp;
 462
 463    /* alias for dest */
 464    tmpb = b->dp;
 465
 466    /* carry */
 467    r = 0;
 468    for (x = 0; x < a->used; x++) {
 469
 470      /* get what will be the *next* carry bit from the
 471       * MSB of the current digit
 472       */
 473      rr = *tmpa >> ((fp_digit)(DIGIT_BIT - 1));
 474
 475      /* now shift up this digit, add in the carry [from the previous] */
 476      *tmpb++ = ((*tmpa++ << ((fp_digit)1)) | r);
 477
 478      /* copy the carry that would be from the source
 479       * digit into the next iteration
 480       */
 481      r = rr;
 482    }
 483
 484    /* new leading digit? */
 485    if (r != 0) {
 486      /* add a MSB which is always 1 at this point */
 487      *tmpb = 1;
 488      ++(b->used);
 489    }
 490
 491    /* zero any excess digits on the destination that we didn't write to */
 492    tmpb = b->dp + b->used;
 493    for (x = b->used; x < oldused; x++) {
 494      *tmpb++ = 0;
 495    }
 496  }
 497  b->sign = a->sign;
 498
 499  return FP_OKAY;
 500}
 501
 502/* c = a * b */
 503int fp_mul_d(fp_int *a, fp_digit b, fp_int *c)
 504{
 505   fp_word  w;
 506   int      x, oldused;
 507
 508   oldused = c->used;
 509   c->used = a->used;
 510   c->sign = a->sign;
 511   w       = 0;
 512   for (x = 0; x < a->used; x++) {
 513       w         = ((fp_word)a->dp[x]) * ((fp_word)b) + w;
 514       c->dp[x]  = (fp_digit)w;
 515       w         = w >> DIGIT_BIT;
 516   }
 517   if (w != 0) {
 518      if (a->used == FP_SIZE)
 519          return FP_VAL;
 520      c->dp[c->used++] = (fp_digit) w;
 521      ++x;
 522   }
 523
 524   /* zero any excess digits on the destination that we didn't write to */
 525   /* also checking FP_SIZE here for static analysis */
 526   for (; x < oldused && x < FP_SIZE; x++) {
 527      c->dp[x] = 0;
 528   }
 529
 530   fp_clamp(c);
 531   return FP_OKAY;
 532}
 533
 534/* c = a * 2**d */
 535int fp_mul_2d(fp_int *a, int b, fp_int *c)
 536{
 537   fp_digit carry, carrytmp, shift;
 538   int x;
 539
 540   /* copy it */
 541   fp_copy(a, c);
 542
 543   /* handle whole digits */
 544   if (b >= DIGIT_BIT) {
 545      int ret = fp_lshd(c, b/DIGIT_BIT);
 546      if (ret != FP_OKAY)
 547         return ret;
 548   }
 549   b %= DIGIT_BIT;
 550
 551   /* shift the digits */
 552   if (b != 0) {
 553      carry = 0;
 554      shift = DIGIT_BIT - b;
 555      for (x = 0; x < c->used; x++) {
 556          carrytmp = c->dp[x] >> shift;
 557          c->dp[x] = (c->dp[x] << b) + carry;
 558          carry = carrytmp;
 559      }
 560      /* store last carry if room */
 561      if (carry && x < FP_SIZE) {
 562         c->dp[c->used++] = carry;
 563      }
 564      if (x == FP_SIZE)
 565         return FP_VAL;
 566   }
 567   fp_clamp(c);
 568   return FP_OKAY;
 569}
 570
 571/* generic PxQ multiplier */
 572#if defined(HAVE_INTEL_MULX)
 573
 574WC_INLINE static int fp_mul_comba_mulx(fp_int *A, fp_int *B, fp_int *C)
 575
 576{
 577   int       ix, iy, iz, pa;
 578   fp_int    *dst;
 579   WC_DECLARE_VAR(tmp, fp_int, 1, 0);
 580   fp_digit  carry;
 581
 582   /* Variables used but not seen by cppcheck. */
 583   (void)ix; (void)iy; (void)iz;
 584
 585   WC_ALLOC_VAR_EX(tmp, fp_int, 1, NULL, DYNAMIC_TYPE_BIGINT,
 586       return FP_MEM);
 587
 588   /* get size of output and trim */
 589   pa = A->used + B->used;
 590   if (pa >= FP_SIZE) {
 591      pa = FP_SIZE-1;
 592   }
 593
 594   /* Always take branch to use tmp variable. This avoids a cache attack for
 595    * determining if C equals A */
 596   if (1) {
 597      fp_init(tmp);
 598      dst = tmp;
 599   }
 600
 601   TFM_INTEL_MUL_COMBA(A, B, carry, dst) ;
 602
 603  dst->used = pa;
 604  dst->sign = A->sign ^ B->sign;
 605  fp_clamp(dst);
 606  fp_copy(dst, C);
 607
 608  WC_FREE_VAR_EX(tmp, NULL, DYNAMIC_TYPE_BIGINT);
 609
 610  return FP_OKAY;
 611}
 612#endif
 613
 614/*  C = (A * B)   */
 615int fp_mul_comba(fp_int *A, fp_int *B, fp_int *C)
 616{
 617   int       ret = 0;
 618   int       ix, iy, iz, tx, ty, pa;
 619   fp_digit  c0, c1, c2, *tmpx, *tmpy;
 620   fp_int    *dst;
 621   WC_DECLARE_VAR(tmp, fp_int, 1, 0);
 622
 623   if (A->used + B->used >= FP_SIZE) return FP_VAL;
 624
 625   IF_HAVE_INTEL_MULX(ret = fp_mul_comba_mulx(A, B, C), return ret) ;
 626
 627   WC_ALLOC_VAR_EX(tmp, fp_int, 1, NULL, DYNAMIC_TYPE_BIGINT,
 628       return FP_MEM);
 629
 630   COMBA_START;
 631   COMBA_CLEAR;
 632
 633   /* get size of output and trim */
 634   pa = A->used + B->used;
 635   if (pa >= FP_SIZE) {
 636      pa = FP_SIZE-1;
 637   }
 638
 639   /* Always take branch to use tmp variable. This avoids a cache attack for
 640    * determining if C equals A */
 641   if (1) {
 642      fp_init(tmp);
 643      dst = tmp;
 644   }
 645
 646   for (ix = 0; ix < pa; ix++) {
 647      /* get offsets into the two bignums */
 648      ty = MIN(ix, (B->used > 0 ? B->used - 1 : 0));
 649      tx = ix - ty;
 650
 651      /* setup temp aliases */
 652      tmpx = A->dp + tx;
 653      tmpy = B->dp + ty;
 654
 655      /* this is the number of times the loop will iterate, essentially its
 656         while (tx++ < a->used && ty-- >= 0) { ... }
 657       */
 658      iy = MIN(A->used-tx, ty+1);
 659
 660      /* execute loop */
 661      COMBA_FORWARD;
 662      for (iz = 0; iz < iy; ++iz) {
 663          fp_digit _tmpx = *tmpx++;
 664          fp_digit _tmpy = *tmpy--;
 665          MULADD(_tmpx, _tmpy);
 666      }
 667
 668      /* store term */
 669      COMBA_STORE(dst->dp[ix]);
 670  }
 671  COMBA_FINI;
 672
 673  dst->used = pa;
 674
 675  /* warning: WOLFSSL_SP_INT_NEGATIVE may disable negative numbers */
 676  dst->sign = A->sign ^ B->sign;
 677  fp_clamp(dst);
 678  fp_copy(dst, C);
 679
 680  /* Variables used but not seen by cppcheck. */
 681  (void)c0; (void)c1; (void)c2;
 682
 683  WC_FREE_VAR_EX(tmp, NULL, DYNAMIC_TYPE_BIGINT);
 684  return ret;
 685}
 686
 687/* a/b => cb + d == a */
 688int fp_div(fp_int *a, fp_int *b, fp_int *c, fp_int *d)
 689{
 690  int     n, t, i, norm, neg;
 691  int     ret;
 692#ifndef WOLFSSL_SMALL_STACK
 693  fp_int  q[1], x[1], y[1], t1[1], t2[1];
 694#else
 695  fp_int  *q, *x, *y, *t1, *t2;
 696#endif
 697
 698  /* is divisor zero ? */
 699  if (fp_iszero (b) == FP_YES) {
 700    return FP_VAL;
 701  }
 702
 703  /* if a < b then q=0, r = a */
 704  if (fp_cmp_mag (a, b) == FP_LT)
 705  {
 706    if (d != NULL) {
 707      fp_copy (a, d);
 708    }
 709    if (c != NULL) {
 710      fp_zero (c);
 711    }
 712    return FP_OKAY;
 713  }
 714
 715#ifdef WOLFSSL_SMALL_STACK          /* 0  1  2  3   4  */
 716  /* allocate 5 elements of fp_int for q, x, y, t1, t2 */
 717  q = (fp_int*)XMALLOC(sizeof(fp_int) * 5, NULL, DYNAMIC_TYPE_BIGINT);
 718  if (q == NULL) {
 719      return FP_MEM;
 720  }
 721  x = &q[1]; y = &q[2]; t1 = &q[3]; t2 = &q[4];
 722#endif
 723
 724  fp_init(q);
 725  /* qb + d = a, and b is an integer > 0, therefore q <= a */
 726  q->used = a->used;
 727
 728  fp_init(t1);
 729  fp_init(t2);
 730
 731  /* Init a copy (y) of the input (b) and
 732  ** Init a copy (x) of the input (a)
 733  **
 734  ** ALERT: Not calling fp_init_copy() as some compiler optimization settings
 735  ** such as -O2 will complain that (x) or (y) "may be used uninitialized".
 736  ** The fp_init() is here only to appease the compiler.  */
 737  fp_init(x);
 738  fp_copy(a, x); /* copy (src = a) to (dst = x) */
 739
 740  fp_init(y);
 741  fp_copy(b, y); /* copy (src = b) to (dst = y) */
 742
 743  /* fix the sign */
 744  neg = (a->sign == b->sign) ? FP_ZPOS : FP_NEG;
 745  x->sign = y->sign = FP_ZPOS;
 746
 747  /* normalize both x and y, ensure that y >= b/2, [b == 2**DIGIT_BIT] */
 748  norm = fp_count_bits(y) % DIGIT_BIT;
 749  if (norm < (int)(DIGIT_BIT-1)) {
 750    norm = (DIGIT_BIT-1) - norm;
 751    ret = fp_mul_2d (x, norm, x);
 752    if (ret != FP_OKAY) {
 753      WC_FREE_VAR_EX(q, NULL, DYNAMIC_TYPE_BIGINT);
 754      return ret;
 755    }
 756    ret = fp_mul_2d (y, norm, y);
 757    if (ret != FP_OKAY) {
 758      WC_FREE_VAR_EX(q, NULL, DYNAMIC_TYPE_BIGINT);
 759      return ret;
 760    }
 761  } else {
 762    norm = 0;
 763  }
 764
 765  /* note hac does 0 based, so if used==5 then its 0,1,2,3,4, e.g. use 4 */
 766  n = x->used - 1;
 767  t = y->used - 1;
 768
 769  /* while (x >= y*b**n-t) do { q[n-t] += 1; x -= y*b**{n-t} } */
 770  ret = fp_lshd (y, n - t); /* y = y*b**{n-t} */
 771  if (ret != FP_OKAY) {
 772    WC_FREE_VAR_EX(q, NULL, DYNAMIC_TYPE_BIGINT);
 773    return ret;
 774  }
 775
 776  while (fp_cmp (x, y) != FP_LT) {
 777    ++(q->dp[n - t]);
 778    ret = fp_sub (x, y, x);
 779    if (ret != FP_OKAY) {
 780      WC_FREE_VAR_EX(q, NULL, DYNAMIC_TYPE_BIGINT);
 781      return ret;
 782    }
 783  }
 784
 785  /* reset y by shifting it back down */
 786  fp_rshd (y, n - t);
 787
 788  /* step 3. for i from n down to (t + 1) */
 789  for (i = n; i >= (t + 1); i--) {
 790    if (i > x->used) {
 791      continue;
 792    }
 793
 794    /* step 3.1 if xi == yt then set q{i-t-1} to b-1,
 795     * otherwise set q{i-t-1} to (xi*b + x{i-1})/yt */
 796    if (x->dp[i] == y->dp[t]) {
 797      q->dp[i - t - 1] = (fp_digit) ((((fp_word)1) << DIGIT_BIT) - 1);
 798    } else {
 799      fp_word tmp;
 800      tmp = ((fp_word) x->dp[i]) << ((fp_word) DIGIT_BIT);
 801      tmp |= ((fp_word) x->dp[i - 1]);
 802#ifdef WOLFSSL_LINUXKM
 803      /* Linux kernel macro for in-place 64 bit integer division. */
 804      do_div(tmp, (fp_word)y->dp[t]);
 805#else
 806      tmp /= ((fp_word)y->dp[t]);
 807#endif
 808      q->dp[i - t - 1] = (fp_digit) (tmp);
 809    }
 810
 811    /* while (q{i-t-1} * (yt * b + y{t-1})) >
 812             xi * b**2 + xi-1 * b + xi-2
 813
 814       do q{i-t-1} -= 1;
 815    */
 816    q->dp[i - t - 1] = (q->dp[i - t - 1] + 1);
 817    do {
 818      q->dp[i - t - 1] = (q->dp[i - t - 1] - 1);
 819
 820      /* find left hand */
 821      fp_zero (t1);
 822      t1->dp[0] = (t - 1 < 0) ? 0 : y->dp[t - 1];
 823      t1->dp[1] = y->dp[t];
 824      t1->used = 2;
 825      ret = fp_mul_d (t1, q->dp[i - t - 1], t1);
 826      if (ret != FP_OKAY) {
 827        WC_FREE_VAR_EX(q, NULL, DYNAMIC_TYPE_BIGINT);
 828        return ret;
 829      }
 830
 831      /* find right hand */
 832      t2->dp[0] = (i - 2 < 0) ? 0 : x->dp[i - 2];
 833      t2->dp[1] = (i - 1 < 0) ? 0 : x->dp[i - 1];
 834      t2->dp[2] = x->dp[i];
 835      t2->used = 3;
 836    } while (fp_cmp_mag(t1, t2) == FP_GT);
 837
 838    /* step 3.3 x = x - q{i-t-1} * y * b**{i-t-1} */
 839    ret = fp_mul_d (y, q->dp[i - t - 1], t1);
 840    if (ret != FP_OKAY) {
 841      WC_FREE_VAR_EX(q, NULL, DYNAMIC_TYPE_BIGINT);
 842      return ret;
 843    }
 844    ret = fp_lshd  (t1, i - t - 1);
 845    if (ret != FP_OKAY) {
 846      WC_FREE_VAR_EX(q, NULL, DYNAMIC_TYPE_BIGINT);
 847      return ret;
 848    }
 849    ret = fp_sub   (x, t1, x);
 850    if (ret != FP_OKAY) {
 851      WC_FREE_VAR_EX(q, NULL, DYNAMIC_TYPE_BIGINT);
 852      return ret;
 853    }
 854
 855    /* if x < 0 then { x = x + y*b**{i-t-1}; q{i-t-1} -= 1; } */
 856    if (x->sign == FP_NEG) {
 857      fp_copy (y, t1);
 858      ret = fp_lshd (t1, i - t - 1);
 859      if (ret != FP_OKAY) {
 860        WC_FREE_VAR_EX(q, NULL, DYNAMIC_TYPE_BIGINT);
 861        return ret;
 862      }
 863      ret = fp_add (x, t1, x);
 864      if (ret != FP_OKAY) {
 865        WC_FREE_VAR_EX(q, NULL, DYNAMIC_TYPE_BIGINT);
 866        return ret;
 867      }
 868      q->dp[i - t - 1] = q->dp[i - t - 1] - 1;
 869    }
 870  }
 871
 872  /* now q is the quotient and x is the remainder
 873   * [which we have to normalize]
 874   */
 875
 876  /* get sign before writing to c */
 877  x->sign = x->used == 0 ? FP_ZPOS : a->sign;
 878
 879  if (c != NULL) {
 880    fp_clamp (q);
 881    fp_copy (q, c);
 882    c->sign = neg;
 883  }
 884
 885  if (d != NULL) {
 886    fp_div_2d (x, norm, x, NULL);
 887
 888    /* zero any excess digits on the destination that we didn't write to */
 889    for (i = b->used; i < x->used; i++) {
 890        x->dp[i] = 0;
 891    }
 892    fp_clamp(x);
 893    fp_copy (x, d);
 894  }
 895
 896  WC_FREE_VAR_EX(q, NULL, DYNAMIC_TYPE_BIGINT);
 897  return FP_OKAY;
 898}
 899
 900/* b = a/2 */
 901void fp_div_2(fp_int * a, fp_int * b)
 902{
 903  int     x, oldused;
 904
 905  oldused = b->used;
 906  b->used = a->used;
 907  {
 908    fp_digit r, rr, *tmpa, *tmpb;
 909
 910    /* source alias */
 911    tmpa = a->dp + b->used - 1;
 912
 913    /* dest alias */
 914    tmpb = b->dp + b->used - 1;
 915
 916    /* carry */
 917    r = 0;
 918    for (x = b->used - 1; x >= 0; x--) {
 919      /* get the carry for the next iteration */
 920      rr = *tmpa & 1;
 921
 922      /* shift the current digit, add in carry and store */
 923      *tmpb-- = (*tmpa-- >> 1) | (r << (DIGIT_BIT - 1));
 924
 925      /* forward carry to next iteration */
 926      r = rr;
 927    }
 928
 929    /* zero any excess digits on the destination that we didn't write to */
 930    tmpb = b->dp + b->used;
 931    for (x = b->used; x < oldused; x++) {
 932      *tmpb++ = 0;
 933    }
 934  }
 935  b->sign = a->sign;
 936  fp_clamp (b);
 937}
 938
 939/* c = a / 2 (mod b) - constant time (a < b and positive) */
 940int fp_div_2_mod_ct(fp_int *a, fp_int *b, fp_int *c)
 941{
 942  fp_word  w = 0;
 943  fp_digit mask;
 944  int i;
 945
 946  mask = (fp_digit)0 - (a->dp[0] & 1);
 947  for (i = 0; i < b->used; i++) {
 948      fp_digit mask_a = (fp_digit)0 - (i < a->used);
 949
 950      w         += b->dp[i] & mask;
 951      w         += a->dp[i] & mask_a;
 952      c->dp[i]   = (fp_digit)w;
 953      w        >>= DIGIT_BIT;
 954  }
 955  for (i = 0; i < b->used-1; i++) {
 956      c->dp[i] = (c->dp[i] >> 1) | (c->dp[i+1] << (DIGIT_BIT - 1));
 957  }
 958  c->dp[i] = (c->dp[i] >> 1) | ((fp_digit)w << (DIGIT_BIT - 1));
 959  c->used = i + 1;
 960  c->sign = FP_ZPOS;
 961  fp_clamp(c);
 962
 963  return FP_OKAY;
 964}
 965
 966/* c = a / 2**b */
 967void fp_div_2d(fp_int *a, int b, fp_int *c, fp_int *d)
 968{
 969  int      D;
 970
 971  /* if the shift count is <= 0 then we do no work */
 972  if (b <= 0) {
 973    fp_copy (a, c);
 974    if (d != NULL) {
 975      fp_zero (d);
 976    }
 977    return;
 978  }
 979
 980  /* get the remainder before a is changed in calculating c */
 981  if (a == c && d != NULL) {
 982    fp_mod_2d (a, b, d);
 983  }
 984
 985  /* copy */
 986  fp_copy(a, c);
 987
 988  /* shift by as many digits in the bit count */
 989  if (b >= (int)DIGIT_BIT) {
 990    fp_rshd (c, b / DIGIT_BIT);
 991  }
 992
 993  /* shift any bit count < DIGIT_BIT */
 994  D = (b % DIGIT_BIT);
 995  if (D != 0) {
 996    fp_rshb(c, D);
 997  }
 998
 999  /* get the remainder if a is not changed in calculating c */
1000  if (a != c && d != NULL) {
1001    fp_mod_2d (a, b, d);
1002  }
1003
1004  fp_clamp (c);
1005}
1006
1007/* c = a mod b, 0 <= c < b  */
1008int fp_mod(fp_int *a, fp_int *b, fp_int *c)
1009{
1010   WC_DECLARE_VAR(t, fp_int, 1, 0);
1011   int    err;
1012
1013   WC_ALLOC_VAR_EX(t, fp_int, 1, NULL, DYNAMIC_TYPE_BIGINT, return FP_MEM);
1014
1015   fp_init(t);
1016   err = fp_div(a, b, NULL, t);
1017   if (err == FP_OKAY) {
1018      if (!fp_iszero(t) && (t->sign != b->sign)) {
1019         err = fp_add(t, b, c);
1020      } else {
1021         fp_copy(t, c);
1022     }
1023  }
1024
1025  WC_FREE_VAR_EX(t, NULL, DYNAMIC_TYPE_BIGINT);
1026  return err;
1027}
1028
1029/* c = a mod 2**d */
1030void fp_mod_2d(fp_int *a, int b, fp_int *c)
1031{
1032   unsigned int x;
1033   unsigned int bmax;
1034
1035   /* zero if count less than or equal to zero */
1036   if (b <= 0) {
1037      fp_zero(c);
1038      return;
1039   }
1040
1041   /* get copy of input */
1042   fp_copy(a, c);
1043
1044   /* if 2**d is larger than we just return */
1045   if (c->sign == FP_ZPOS && b >= (DIGIT_BIT * a->used)) {
1046      return;
1047   }
1048
1049   bmax = ((unsigned int)b + DIGIT_BIT - 1) / DIGIT_BIT;
1050
1051   /* If a is negative and bmax is greater than or equal to FP_SIZE, then the
1052    * result can't fit within c. Just return. */
1053   if (c->sign == FP_NEG && bmax >= FP_SIZE) {
1054      return;
1055   }
1056
1057  /* zero digits above the last digit of the modulus */
1058   for (x = bmax; x < (unsigned int)c->used; x++) {
1059    c->dp[x] = 0;
1060  }
1061
1062  if (c->sign == FP_NEG) {
1063     fp_digit carry = 0;
1064     /* negate value */
1065     for (x = 0; x < (unsigned int)c->used; x++) {
1066         fp_digit next = c->dp[x] > 0;
1067         c->dp[x] = (fp_digit)0 - c->dp[x] - carry;
1068         carry |= next;
1069     }
1070     for (; x < bmax; x++) {
1071         c->dp[x] = (fp_digit)0 - carry;
1072     }
1073     c->used = (int)bmax;
1074     c->sign = FP_ZPOS;
1075  }
1076
1077  /* clear the digit that is not completely outside/inside the modulus */
1078  x = DIGIT_BIT - (b % DIGIT_BIT);
1079  if (x != DIGIT_BIT) {
1080     c->dp[bmax - 1] &= ~((fp_digit)0) >> x;
1081  }
1082
1083  fp_clamp (c);
1084}
1085
1086static int fp_invmod_slow (fp_int * a, fp_int * b, fp_int * c)
1087{
1088#ifndef WOLFSSL_SMALL_STACK
1089  fp_int  x[1], y[1], u[1], v[1], A[1], B[1], C[1], D[1];
1090#else
1091  fp_int  *x, *y, *u, *v, *A, *B, *C, *D;
1092#endif
1093  int     err;
1094
1095  /* b cannot be negative */
1096  if (b->sign == FP_NEG || fp_iszero(b) == FP_YES) {
1097    return FP_VAL;
1098  }
1099  if (fp_iszero(a) == FP_YES) {
1100    return FP_VAL;
1101  }
1102
1103#ifdef WOLFSSL_SMALL_STACK
1104  x = (fp_int*)XMALLOC(sizeof(fp_int) * 8, NULL, DYNAMIC_TYPE_BIGINT);
1105  if (x == NULL) {
1106      return FP_MEM;
1107  }
1108  y = &x[1]; u = &x[2]; v = &x[3]; A = &x[4]; B = &x[5]; C = &x[6]; D = &x[7];
1109#endif
1110
1111  /* init temps */
1112  fp_init(x);    fp_init(y);
1113  fp_init(u);    fp_init(v);
1114  fp_init(A);    fp_init(B);
1115  fp_init(C);    fp_init(D);
1116
1117  /* x = a, y = b */
1118  if ((err = fp_mod(a, b, x)) != FP_OKAY) {
1119    WC_FREE_VAR_EX(x, NULL, DYNAMIC_TYPE_BIGINT);
1120    return err;
1121  }
1122  fp_copy(b, y);
1123
1124  if (fp_iszero(x) == FP_YES) {
1125    /* invmod doesn't exist for this a and b */
1126    WC_FREE_VAR_EX(x, NULL, DYNAMIC_TYPE_BIGINT);
1127    return FP_VAL;
1128  }
1129
1130  /* 2. [modified] if x,y are both even then return an error! */
1131  if (fp_iseven(x) == FP_YES && fp_iseven(y) == FP_YES) {
1132    WC_FREE_VAR_EX(x, NULL, DYNAMIC_TYPE_BIGINT);
1133    return FP_VAL;
1134  }
1135
1136  /* 3. u=x, v=y, A=1, B=0, C=0,D=1 */
1137  fp_copy (x, u);
1138  fp_copy (y, v);
1139  fp_set (A, 1);
1140  fp_set (D, 1);
1141
1142top:
1143  /* 4.  while u is even do */
1144  while (fp_iseven (u) == FP_YES) {
1145    /* 4.1 u = u/2 */
1146    fp_div_2 (u, u);
1147
1148    /* 4.2 if A or B is odd then */
1149    if (fp_isodd (A) == FP_YES || fp_isodd (B) == FP_YES) {
1150      /* A = (A+y)/2, B = (B-x)/2 */
1151      err = fp_add (A, y, A);
1152      if (err != FP_OKAY) {
1153        WC_FREE_VAR_EX(x, NULL, DYNAMIC_TYPE_BIGINT);
1154        return err;
1155      }
1156      err = fp_sub (B, x, B);
1157      if (err != FP_OKAY) {
1158        WC_FREE_VAR_EX(x, NULL, DYNAMIC_TYPE_BIGINT);
1159        return err;
1160      }
1161    }
1162    /* A = A/2, B = B/2 */
1163    fp_div_2 (A, A);
1164    fp_div_2 (B, B);
1165  }
1166
1167  /* 5.  while v is even do */
1168  while (fp_iseven (v) == FP_YES) {
1169    /* 5.1 v = v/2 */
1170    fp_div_2 (v, v);
1171
1172    /* 5.2 if C or D is odd then */
1173    if (fp_isodd (C) == FP_YES || fp_isodd (D) == FP_YES) {
1174      /* C = (C+y)/2, D = (D-x)/2 */
1175      err = fp_add (C, y, C);
1176      if (err != FP_OKAY) {
1177        WC_FREE_VAR_EX(x, NULL, DYNAMIC_TYPE_BIGINT);
1178        return err;
1179      }
1180      err = fp_sub (D, x, D);
1181      if (err != FP_OKAY) {
1182        WC_FREE_VAR_EX(x, NULL, DYNAMIC_TYPE_BIGINT);
1183        return err;
1184      }
1185    }
1186    /* C = C/2, D = D/2 */
1187    fp_div_2 (C, C);
1188    fp_div_2 (D, D);
1189  }
1190
1191  /* 6.  if u >= v then */
1192  if (fp_cmp (u, v) != FP_LT) {
1193    /* u = u - v, A = A - C, B = B - D */
1194    err = fp_sub (u, v, u);
1195    if (err != FP_OKAY) {
1196      WC_FREE_VAR_EX(x, NULL, DYNAMIC_TYPE_BIGINT);
1197      return err;
1198    }
1199    err = fp_sub (A, C, A);
1200    if (err != FP_OKAY) {
1201      WC_FREE_VAR_EX(x, NULL, DYNAMIC_TYPE_BIGINT);
1202      return err;
1203    }
1204    err = fp_sub (B, D, B);
1205    if (err != FP_OKAY) {
1206      WC_FREE_VAR_EX(x, NULL, DYNAMIC_TYPE_BIGINT);
1207      return err;
1208    }
1209  } else {
1210    /* v - v - u, C = C - A, D = D - B */
1211    err = fp_sub (v, u, v);
1212    if (err != FP_OKAY) {
1213      WC_FREE_VAR_EX(x, NULL, DYNAMIC_TYPE_BIGINT);
1214      return err;
1215    }
1216    err = fp_sub (C, A, C);
1217    if (err != FP_OKAY) {
1218      WC_FREE_VAR_EX(x, NULL, DYNAMIC_TYPE_BIGINT);
1219      return err;
1220    }
1221    err = fp_sub (D, B, D);
1222    if (err != FP_OKAY) {
1223      WC_FREE_VAR_EX(x, NULL, DYNAMIC_TYPE_BIGINT);
1224      return err;
1225    }
1226  }
1227
1228  /* if not zero goto step 4 */
1229  if (fp_iszero (u) == FP_NO)
1230    goto top;
1231
1232  /* now a = C, b = D, gcd == g*v */
1233
1234  /* if v != 1 then there is no inverse */
1235  if (fp_cmp_d (v, 1) != FP_EQ) {
1236    WC_FREE_VAR_EX(x, NULL, DYNAMIC_TYPE_BIGINT);
1237    return FP_VAL;
1238  }
1239
1240  /* if its too low */
1241  while (fp_cmp_d(C, 0) == FP_LT) {
1242    err = fp_add(C, b, C);
1243    if (err != FP_OKAY) {
1244      WC_FREE_VAR_EX(x, NULL, DYNAMIC_TYPE_BIGINT);
1245      return err;
1246    }
1247  }
1248
1249  /* too big */
1250  while (fp_cmp_mag(C, b) != FP_LT) {
1251    err = fp_sub(C, b, C);
1252    if (err != FP_OKAY) {
1253      WC_FREE_VAR_EX(x, NULL, DYNAMIC_TYPE_BIGINT);
1254      return err;
1255    }
1256  }
1257
1258  /* C is now the inverse */
1259  fp_copy(C, c);
1260  WC_FREE_VAR_EX(x, NULL, DYNAMIC_TYPE_BIGINT);
1261  return FP_OKAY;
1262}
1263
1264/* c = 1/a (mod b) for odd b only */
1265int fp_invmod(fp_int *a, fp_int *b, fp_int *c)
1266{
1267#ifndef WOLFSSL_SMALL_STACK
1268  fp_int  x[1], y[1], u[1], v[1], B[1], D[1];
1269#else
1270  fp_int  *x, *y, *u, *v, *B, *D;
1271#endif
1272  int     err;
1273
1274  if (b->sign == FP_NEG || fp_iszero(b) == FP_YES) {
1275    return FP_VAL;
1276  }
1277
1278  /* [modified] sanity check on "a" */
1279  if (fp_iszero(a) == FP_YES) {
1280    return FP_VAL; /* can not divide by 0 here */
1281  }
1282
1283  /* 2. [modified] b must be odd   */
1284  if (fp_iseven(b) == FP_YES) {
1285    return fp_invmod_slow(a,b,c);
1286  }
1287
1288#ifdef WOLFSSL_SMALL_STACK
1289  x = (fp_int*)XMALLOC(sizeof(fp_int) * 6, NULL, DYNAMIC_TYPE_BIGINT);
1290  if (x == NULL) {
1291      return FP_MEM;
1292  }
1293  y = &x[1]; u = &x[2]; v = &x[3]; B = &x[4]; D = &x[5];
1294#endif
1295
1296  /* init all our temps */
1297  fp_init(x);  fp_init(y);
1298  fp_init(u);  fp_init(v);
1299  fp_init(B);  fp_init(D);
1300
1301  if (fp_iszero(a) == FP_YES) {
1302    WC_FREE_VAR_EX(x, NULL, DYNAMIC_TYPE_BIGINT);
1303    return FP_VAL;
1304  }
1305
1306  /* x == modulus, y == value to invert */
1307  fp_copy(b, x);
1308
1309  /* we need y = |a| */
1310  if ((err = mp_mod(a, b, y)) != FP_OKAY) {
1311    WC_FREE_VAR_EX(x, NULL, DYNAMIC_TYPE_BIGINT);
1312    return err;
1313  }
1314
1315  if (fp_iszero(y) == FP_YES) {
1316    /* invmod doesn't exist for this a and b */
1317    WC_FREE_VAR_EX(x, NULL, DYNAMIC_TYPE_BIGINT);
1318    return FP_VAL;
1319  }
1320
1321  /* 3. u=x, v=y, A=1, B=0, C=0,D=1 */
1322  fp_copy(x, u);
1323  fp_copy(y, v);
1324  fp_set (D, 1);
1325
1326top:
1327  /* 4.  while u is even do */
1328  while (fp_iseven (u) == FP_YES) {
1329    /* 4.1 u = u/2 */
1330    fp_div_2 (u, u);
1331
1332    /* 4.2 if B is odd then */
1333    if (fp_isodd (B) == FP_YES) {
1334      err = fp_sub (B, x, B);
1335      if (err != FP_OKAY) {
1336        WC_FREE_VAR_EX(x, NULL, DYNAMIC_TYPE_BIGINT);
1337        return err;
1338      }
1339    }
1340    /* B = B/2 */
1341    fp_div_2 (B, B);
1342  }
1343
1344  /* 5.  while v is even do */
1345  while (fp_iseven (v) == FP_YES) {
1346    /* 5.1 v = v/2 */
1347    fp_div_2 (v, v);
1348
1349    /* 5.2 if D is odd then */
1350    if (fp_isodd (D) == FP_YES) {
1351      /* D = (D-x)/2 */
1352      err = fp_sub (D, x, D);
1353      if (err != FP_OKAY) {
1354        WC_FREE_VAR_EX(x, NULL, DYNAMIC_TYPE_BIGINT);
1355        return err;
1356      }
1357    }
1358    /* D = D/2 */
1359    fp_div_2 (D, D);
1360  }
1361
1362  /* 6.  if u >= v then */
1363  if (fp_cmp (u, v) != FP_LT) {
1364    /* u = u - v, B = B - D */
1365    err = fp_sub (u, v, u);
1366    if (err != FP_OKAY) {
1367      WC_FREE_VAR_EX(x, NULL, DYNAMIC_TYPE_BIGINT);
1368      return err;
1369    }
1370    err = fp_sub (B, D, B);
1371    if (err != FP_OKAY) {
1372      WC_FREE_VAR_EX(x, NULL, DYNAMIC_TYPE_BIGINT);
1373      return err;
1374    }
1375  } else {
1376    /* v - v - u, D = D - B */
1377    err = fp_sub (v, u, v);
1378    if (err != FP_OKAY) {
1379      WC_FREE_VAR_EX(x, NULL, DYNAMIC_TYPE_BIGINT);
1380      return err;
1381    }
1382    err = fp_sub (D, B, D);
1383    if (err != FP_OKAY) {
1384      WC_FREE_VAR_EX(x, NULL, DYNAMIC_TYPE_BIGINT);
1385      return err;
1386    }
1387  }
1388
1389  /* if not zero goto step 4 */
1390  if (fp_iszero (u) == FP_NO) {
1391    goto top;
1392  }
1393
1394  /* now a = C, b = D, gcd == g*v */
1395
1396  /* if v != 1 then there is no inverse */
1397  if (fp_cmp_d (v, 1) != FP_EQ) {
1398    WC_FREE_VAR_EX(x, NULL, DYNAMIC_TYPE_BIGINT);
1399    return FP_VAL;
1400  }
1401
1402  /* b is now the inverse */
1403  while (D->sign == FP_NEG) {
1404    err = fp_add (D, b, D);
1405    if (err != FP_OKAY) {
1406      WC_FREE_VAR_EX(x, NULL, DYNAMIC_TYPE_BIGINT);
1407      return FP_OKAY;
1408    }
1409  }
1410  /* too big */
1411  while (fp_cmp_mag(D, b) != FP_LT) {
1412    err = fp_sub(D, b, D);
1413    if (err != FP_OKAY) {
1414      WC_FREE_VAR_EX(x, NULL, DYNAMIC_TYPE_BIGINT);
1415      return err;
1416    }
1417  }
1418  fp_copy (D, c);
1419  WC_FREE_VAR_EX(x, NULL, DYNAMIC_TYPE_BIGINT);
1420  return FP_OKAY;
1421}
1422
1423#define CT_INV_MOD_PRE_CNT      8
1424
1425/* modulus (b) must be greater than 2 and a prime */
1426int fp_invmod_mont_ct(fp_int *a, fp_int *b, fp_int *c, fp_digit mp)
1427{
1428  int i, j, err = FP_OKAY;
1429#ifndef WOLFSSL_SMALL_STACK
1430  fp_int t[1], e[1];
1431  fp_int pre[CT_INV_MOD_PRE_CNT];
1432#else
1433  fp_int* t;
1434  fp_int* e;
1435  fp_int* pre;
1436#endif
1437
1438  if ((a->used * 2 > FP_SIZE) || (b->used * 2 > FP_SIZE)) {
1439    return FP_VAL;
1440  }
1441
1442#ifdef WOLFSSL_SMALL_STACK
1443  t = (fp_int*)XMALLOC(sizeof(fp_int) * (2 + CT_INV_MOD_PRE_CNT), NULL,
1444                                                           DYNAMIC_TYPE_BIGINT);
1445  if (t == NULL)
1446    return FP_MEM;
1447  e = t + 1;
1448  pre = t + 2;
1449#endif
1450
1451  fp_init(t);
1452  fp_init(e);
1453
1454  fp_init(&pre[0]);
1455  fp_copy(a, &pre[0]);
1456  for (i = 1; i < CT_INV_MOD_PRE_CNT; i++) {
1457    fp_init(&pre[i]);
1458    err |= fp_sqr(&pre[i-1], &pre[i]);
1459    err |= fp_montgomery_reduce(&pre[i], b, mp);
1460    err |= fp_mul(&pre[i], a, &pre[i]);
1461    err |= fp_montgomery_reduce(&pre[i], b, mp);
1462  }
1463
1464  err |= fp_sub_d(b, 2, e);
1465  /* Highest bit is always set. */
1466  j = 1;
1467  for (i = fp_count_bits(e)-2; i >= 0; i--) {
1468      if (!fp_is_bit_set(e, i) || j == CT_INV_MOD_PRE_CNT)
1469          break;
1470      j++;
1471  }
1472  fp_copy(&pre[j-1], t);
1473  j = 0;
1474  for (; i >= 0; i--) {
1475    int set = fp_is_bit_set(e, i);
1476
1477    if ((j == CT_INV_MOD_PRE_CNT) || (!set && j > 0)) {
1478      err |= fp_mul(t, &pre[j-1], t);
1479      err |= fp_montgomery_reduce(t, b, mp);
1480      j = 0;
1481    }
1482    err |= fp_sqr(t, t);
1483    err |= fp_montgomery_reduce(t, b, mp);
1484    j += set;
1485  }
1486  if (j > 0) {
1487    err |= fp_mul(t, &pre[j-1], c);
1488    err |= fp_montgomery_reduce(c, b, mp);
1489  }
1490  else
1491    fp_copy(t, c);
1492
1493  WC_FREE_VAR_EX(t, NULL, DYNAMIC_TYPE_BIGINT);
1494
1495  return err;
1496}
1497
1498/* d = a * b (mod c) */
1499int fp_mulmod(fp_int *a, fp_int *b, fp_int *c, fp_int *d)
1500{
1501  int err;
1502   WC_DECLARE_VAR(t, fp_int, 1, 0);
1503
1504   WC_ALLOC_VAR_EX(t, fp_int, 1, NULL, DYNAMIC_TYPE_BIGINT, return FP_MEM);
1505
1506  fp_init(t);
1507  err = fp_mul(a, b, t);
1508  if (err == FP_OKAY) {
1509  #if defined(ALT_ECC_SIZE) || defined(HAVE_WOLF_BIGINT)
1510    if (d->size < FP_SIZE) {
1511      err = fp_mod(t, c, t);
1512      fp_copy(t, d);
1513    } else
1514  #endif
1515    {
1516      err = fp_mod(t, c, d);
1517    }
1518  }
1519
1520  WC_FREE_VAR_EX(t, NULL, DYNAMIC_TYPE_BIGINT);
1521  return err;
1522}
1523
1524/* d = a - b (mod c) */
1525int fp_submod(fp_int *a, fp_int *b, fp_int *c, fp_int *d)
1526{
1527  int err;
1528   WC_DECLARE_VAR(t, fp_int, 1, 0);
1529
1530   WC_ALLOC_VAR_EX(t, fp_int, 1, NULL, DYNAMIC_TYPE_BIGINT, return FP_MEM);
1531
1532  fp_init(t);
1533  err = fp_sub(a, b, t);
1534  if (err == FP_OKAY) {
1535  #if defined(ALT_ECC_SIZE) || defined(HAVE_WOLF_BIGINT)
1536    if (d->size < FP_SIZE) {
1537      err = fp_mod(t, c, t);
1538      fp_copy(t, d);
1539    } else
1540  #endif
1541    {
1542      err = fp_mod(t, c, d);
1543    }
1544  }
1545
1546  WC_FREE_VAR_EX(t, NULL, DYNAMIC_TYPE_BIGINT);
1547  return err;
1548}
1549
1550/* d = a + b (mod c) */
1551int fp_addmod(fp_int *a, fp_int *b, fp_int *c, fp_int *d)
1552{
1553  int err;
1554   WC_DECLARE_VAR(t, fp_int, 1, 0);
1555
1556   WC_ALLOC_VAR_EX(t, fp_int, 1, NULL, DYNAMIC_TYPE_BIGINT, return FP_MEM);
1557
1558  fp_init(t);
1559  err = fp_add(a, b, t);
1560  if (err == FP_OKAY) {
1561  #if defined(ALT_ECC_SIZE) || defined(HAVE_WOLF_BIGINT)
1562    if (d->size < FP_SIZE) {
1563      err = fp_mod(t, c, t);
1564      fp_copy(t, d);
1565    } else
1566  #endif
1567    {
1568      err = fp_mod(t, c, d);
1569    }
1570  }
1571
1572  WC_FREE_VAR_EX(t, NULL, DYNAMIC_TYPE_BIGINT);
1573  return err;
1574}
1575
1576/* d = a - b (mod c) - constant time (a < c and b < c and all positive)
1577 * c and d must not be the same pointers.
1578 */
1579int fp_submod_ct(fp_int *a, fp_int *b, fp_int *c, fp_int *d)
1580{
1581  fp_sword w;
1582  fp_digit mask;
1583  int i;
1584
1585  if (c->used + 1 > FP_SIZE) {
1586    return FP_VAL;
1587  }
1588  if (c == d) {
1589    return FP_VAL;
1590  }
1591
1592  /* In constant time, subtract b from a putting result in d. */
1593  w = 0;
1594  for (i = 0; i < c->used; i++) {
1595    w         += a->dp[i];
1596    w         -= b->dp[i];
1597    d->dp[i]   = (fp_digit)w;
1598    w        >>= DIGIT_BIT;
1599  }
1600  w  += a->dp[i];
1601  w  -= b->dp[i];
1602  w >>= DIGIT_BIT;
1603  /* When w is negative then we need to add modulus to make result positive. */
1604  mask = (fp_digit)0 - (w < 0);
1605  /* Constant time, conditionally, add modulus to difference. */
1606  w = 0;
1607  for (i = 0; i < c->used; i++) {
1608    w         += d->dp[i];
1609    w         += c->dp[i] & mask;
1610    d->dp[i]   = (fp_digit)w;
1611    w        >>= DIGIT_BIT;
1612  }
1613  /* Result will always have digits equal to or less than those in modulus. */
1614  d->used = i;
1615  d->sign = FP_ZPOS;
1616  fp_clamp(d);
1617
1618  return FP_OKAY;
1619}
1620
1621/* d = a + b (mod c) - constant time (a < c and b < c and all positive)
1622 * c and d must not be the same pointers.
1623 */
1624int fp_addmod_ct(fp_int *a, fp_int *b, fp_int *c, fp_int *d)
1625{
1626  fp_word  w;
1627  fp_sword s;
1628  fp_digit mask;
1629  int i;
1630
1631  if (c == d) {
1632    return FP_VAL;
1633  }
1634
1635  /* Add a to b into d. Do the subtract of modulus but don't store result.
1636   * When subtract result is negative, the overflow will be negative.
1637   * Only need to subtract mod when result is positive - overflow is positive.
1638   */
1639  w = 0;
1640  s = 0;
1641  for (i = 0; i < c->used; i++) {
1642    w         += a->dp[i];
1643    w         += b->dp[i];
1644    d->dp[i]   = (fp_digit)w;
1645    s         += (fp_digit)w;
1646    s         -= c->dp[i];
1647    w        >>= DIGIT_BIT;
1648    s        >>= DIGIT_BIT;
1649  }
1650  s += (fp_digit)w;
1651  /* s will be positive when subtracting modulus is needed. */
1652  mask = (fp_digit)0 - (s >= 0);
1653
1654  /* Constant time, conditionally, subtract modulus from sum. */
1655  w = 0;
1656  for (i = 0; i < c->used; i++) {
1657    w        += c->dp[i] & mask;
1658    w         = d->dp[i] - w;
1659    d->dp[i]  = (fp_digit)w;
1660    w         = (w >> DIGIT_BIT)&1;
1661  }
1662  /* Result will always have digits equal to or less than those in modulus. */
1663  d->used = i;
1664  d->sign = FP_ZPOS;
1665  fp_clamp(d);
1666
1667  return FP_OKAY;
1668}
1669
1670#ifdef TFM_TIMING_RESISTANT
1671
1672#ifdef WC_RSA_NONBLOCK
1673
1674#ifdef WC_RSA_NONBLOCK_TIME
1675  /* User can override the check-time at build-time using the
1676   * FP_EXPTMOD_NB_CHECKTIME macro to define your own function */
1677  #ifndef FP_EXPTMOD_NB_CHECKTIME
1678    /* instruction count for each type of operation */
1679    /* array lookup is using TFM_EXPTMOD_NB_* states */
1680    static const word32 exptModNbInst[TFM_EXPTMOD_NB_COUNT] = {
1681    #ifdef TFM_PPC32
1682      #ifdef _DEBUG
1683        11098, 8701, 3971, 178394, 858093, 1040, 822, 178056, 181574, 90883, 184339, 236813
1684      #else
1685        7050,  2554, 3187, 43178,  200422, 384,  275, 43024,  43550,  30450, 46270,  61376
1686      #endif
1687    #elif defined(TFM_X86_64)
1688      #ifdef _DEBUG
1689        954, 2377, 858, 19027, 90840, 287, 407, 20140, 7874,  11385, 8005,  6151
1690      #else
1691        765, 1007, 771, 5216,  34993, 248, 193, 4975,  4201,  3947,  4275,  3811
1692      #endif
1693    #else /* software only fast math */
1694      #ifdef _DEBUG
1695        798, 2245, 802, 16657, 66920, 352, 186, 16997, 16145, 12789, 16742, 15006
1696      #else
1697        775, 1084, 783, 4692,  37510, 207, 183, 4374,  4392,  3097,  4442,  4079
1698      #endif
1699    #endif
1700    };
1701
1702    static int fp_exptmod_nb_checktime(exptModNb_t* nb)
1703    {
1704      word32 totalInst;
1705
1706      /* if no max time has been set then stop (do not block) */
1707      if (nb->maxBlockInst == 0 || nb->state >= TFM_EXPTMOD_NB_COUNT) {
1708        return TFM_EXPTMOD_NB_STOP;
1709      }
1710
1711      /* if instruction table not set then use maxBlockInst as simple counter */
1712      if (exptModNbInst[nb->state] == 0) {
1713        if (++nb->totalInst < nb->maxBlockInst)
1714          return TFM_EXPTMOD_NB_CONTINUE;
1715
1716        nb->totalInst = 0; /* reset counter */
1717        return TFM_EXPTMOD_NB_STOP;
1718      }
1719
1720      /* get total instruction count including next operation */
1721      totalInst = nb->totalInst + exptModNbInst[nb->state];
1722      /* if the next operation can completed within the maximum then continue */
1723      if (totalInst <= nb->maxBlockInst) {
1724        return TFM_EXPTMOD_NB_CONTINUE;
1725      }
1726
1727      return TFM_EXPTMOD_NB_STOP;
1728    }
1729    #define FP_EXPTMOD_NB_CHECKTIME(nb) fp_exptmod_nb_checktime((nb))
1730  #endif /* !FP_EXPTMOD_NB_CHECKTIME */
1731#endif /* WC_RSA_NONBLOCK_TIME */
1732
1733/* non-blocking version of timing resistant fp_exptmod function */
1734/* supports cache resistance */
1735int fp_exptmod_nb(exptModNb_t* nb, fp_int* G, fp_int* X, fp_int* P, fp_int* Y)
1736{
1737  int err, ret = FP_WOULDBLOCK;
1738
1739  if (nb == NULL)
1740    return FP_VAL;
1741
1742#ifdef WC_RSA_NONBLOCK_TIME
1743  nb->totalInst = 0;
1744  do {
1745    nb->totalInst += exptModNbInst[nb->state];
1746#endif
1747
1748  switch (nb->state) {
1749  case TFM_EXPTMOD_NB_INIT:
1750    /* now setup montgomery  */
1751    if ((err = fp_montgomery_setup(P, &nb->mp)) != FP_OKAY) {
1752      nb->state = TFM_EXPTMOD_NB_INIT;
1753      return err;
1754    }
1755
1756    /* init ints */
1757    fp_init(&nb->R[0]);
1758    fp_init(&nb->R[1]);
1759  #ifndef WC_NO_CACHE_RESISTANT
1760    fp_init(&nb->R[2]);
1761  #endif
1762    nb->state = TFM_EXPTMOD_NB_MONT;
1763    break;
1764
1765  case TFM_EXPTMOD_NB_MONT:
1766    /* mod m -> R[0] */
1767    err = fp_montgomery_calc_normalization(&nb->R[0], P);
1768    if (err != FP_OKAY) {
1769      nb->state = TFM_EXPTMOD_NB_INIT;
1770      return err;
1771    }
1772
1773    nb->state = TFM_EXPTMOD_NB_MONT_RED;
1774    break;
1775
1776  case TFM_EXPTMOD_NB_MONT_RED:
1777    /* reduce G -> R[1] */
1778    if (fp_cmp_mag(P, G) != FP_GT) {
1779       /* G > P so we reduce it first */
1780       err = fp_mod(G, P, &nb->R[1]);
1781       if (err != FP_OKAY) {
1782         nb->state = TFM_EXPTMOD_NB_INIT;
1783         return err;
1784       }
1785    } else {
1786       fp_copy(G, &nb->R[1]);
1787    }
1788
1789    nb->state = TFM_EXPTMOD_NB_MONT_MUL;
1790    break;
1791
1792  case TFM_EXPTMOD_NB_MONT_MUL:
1793    /* G (R[1]) * m (R[0]) */
1794    err = fp_mul(&nb->R[1], &nb->R[0], &nb->R[1]);
1795    if (err != FP_OKAY) {
1796      nb->state = TFM_EXPTMOD_NB_INIT;
1797      return err;
1798    }
1799
1800    nb->state = TFM_EXPTMOD_NB_MONT_MOD;
1801    break;
1802
1803  case TFM_EXPTMOD_NB_MONT_MOD:
1804    /* mod m */
1805    err = fp_div(&nb->R[1], P, NULL, &nb->R[1]);
1806    if (err != FP_OKAY) {
1807      nb->state = TFM_EXPTMOD_NB_INIT;
1808      return err;
1809    }
1810
1811    nb->state = TFM_EXPTMOD_NB_MONT_MODCHK;
1812    break;
1813
1814  case TFM_EXPTMOD_NB_MONT_MODCHK:
1815    /* m matches sign of (G * R mod m) */
1816    if (nb->R[1].sign != P->sign) {
1817       err = fp_add(&nb->R[1], P, &nb->R[1]);
1818       if (err != FP_OKAY) {
1819         nb->state = TFM_EXPTMOD_NB_INIT;
1820         return err;
1821       }
1822    }
1823
1824    /* set initial mode and bit cnt */
1825    nb->bitcnt = 1;
1826    nb->buf    = 0;
1827    nb->digidx = X->used - 1;
1828
1829    nb->state = TFM_EXPTMOD_NB_NEXT;
1830    break;
1831
1832  case TFM_EXPTMOD_NB_NEXT:
1833    /* grab next digit as required */
1834    if (--nb->bitcnt == 0) {
1835      /* if nb->digidx == -1 we are out of digits so break */
1836      if (nb->digidx == -1) {
1837        nb->state = TFM_EXPTMOD_NB_RED;
1838        break;
1839      }
1840      /* read next digit and reset nb->bitcnt */
1841      nb->buf    = X->dp[nb->digidx--];
1842      nb->bitcnt = (int)DIGIT_BIT;
1843    }
1844
1845    /* grab the next msb from the exponent */
1846    nb->y     = (int)(nb->buf >> (DIGIT_BIT - 1)) & 1;
1847    nb->buf <<= (fp_digit)1;
1848    nb->state = TFM_EXPTMOD_NB_MUL;
1849    FALL_THROUGH;
1850
1851  case TFM_EXPTMOD_NB_MUL:
1852    fp_mul(&nb->R[0], &nb->R[1], &nb->R[nb->y^1]);
1853    nb->state = TFM_EXPTMOD_NB_MUL_RED;
1854    break;
1855
1856  case TFM_EXPTMOD_NB_MUL_RED:
1857    err = fp_montgomery_reduce(&nb->R[nb->y^1], P, nb->mp);
1858    if (err != FP_OKAY) {
1859      nb->state = TFM_EXPTMOD_NB_INIT;
1860      return err;
1861    }
1862    nb->state = TFM_EXPTMOD_NB_SQR;
1863    break;
1864
1865  case TFM_EXPTMOD_NB_SQR:
1866  #ifdef WC_NO_CACHE_RESISTANT
1867    err = fp_sqr(&nb->R[nb->y], &nb->R[nb->y]);
1868  #else
1869    fp_copy((fp_int*) ( ((wc_ptr_t)&nb->R[0] & wc_off_on_addr[nb->y^1]) +
1870                        ((wc_ptr_t)&nb->R[1] & wc_off_on_addr[nb->y]) ),
1871            &nb->R[2]);
1872    err = fp_sqr(&nb->R[2], &nb->R[2]);
1873  #endif /* WC_NO_CACHE_RESISTANT */
1874    if (err != FP_OKAY) {
1875      nb->state = TFM_EXPTMOD_NB_INIT;
1876      return err;
1877    }
1878
1879    nb->state = TFM_EXPTMOD_NB_SQR_RED;
1880    break;
1881
1882  case TFM_EXPTMOD_NB_SQR_RED:
1883  #ifdef WC_NO_CACHE_RESISTANT
1884    err = fp_montgomery_reduce(&nb->R[nb->y], P, nb->mp);
1885  #else
1886    err = fp_montgomery_reduce(&nb->R[2], P, nb->mp);
1887    fp_copy(&nb->R[2],
1888            (fp_int*) ( ((wc_ptr_t)&nb->R[0] & wc_off_on_addr[nb->y^1]) +
1889                        ((wc_ptr_t)&nb->R[1] & wc_off_on_addr[nb->y]) ) );
1890  #endif /* WC_NO_CACHE_RESISTANT */
1891    if (err != FP_OKAY) {
1892      nb->state = TFM_EXPTMOD_NB_INIT;
1893      return err;
1894    }
1895
1896    nb->state = TFM_EXPTMOD_NB_NEXT;
1897    break;
1898
1899  case TFM_EXPTMOD_NB_RED:
1900    /* final reduce */
1901    err = fp_montgomery_reduce(&nb->R[0], P, nb->mp);
1902    if (err != FP_OKAY) {
1903      nb->state = TFM_EXPTMOD_NB_INIT;
1904      return err;
1905    }
1906    fp_copy(&nb->R[0], Y);
1907
1908    nb->state = TFM_EXPTMOD_NB_INIT;
1909    ret = FP_OKAY;
1910    break;
1911  } /* switch */
1912
1913#ifdef WC_RSA_NONBLOCK_TIME
1914  /* determine if maximum blocking time has been reached */
1915  } while (ret == FP_WOULDBLOCK &&
1916    FP_EXPTMOD_NB_CHECKTIME(nb) == TFM_EXPTMOD_NB_CONTINUE);
1917#endif
1918
1919  return ret;
1920}
1921
1922#endif /* WC_RSA_NONBLOCK */
1923
1924
1925#ifndef WC_PROTECT_ENCRYPTED_MEM
1926
1927/* timing resistant montgomery ladder based exptmod
1928   Based on work by Marc Joye, Sung-Ming Yen, "The Montgomery Powering Ladder",
1929   Cryptographic Hardware and Embedded Systems, CHES 2002
1930*/
1931static int _fp_exptmod_ct(fp_int * G, fp_int * X, int digits, fp_int * P,
1932                          fp_int * Y)
1933{
1934#ifndef WOLFSSL_SMALL_STACK
1935#ifdef WC_NO_CACHE_RESISTANT
1936  fp_int   R[2];
1937#else
1938  fp_int   R[3];   /* need a temp for cache resistance */
1939#endif
1940#else
1941   fp_int  *R;
1942#endif
1943  fp_digit buf, mp;
1944  int      err, bitcnt, digidx, y;
1945
1946  /* now setup montgomery  */
1947  if ((err = fp_montgomery_setup (P, &mp)) != FP_OKAY) {
1948     return err;
1949  }
1950
1951#ifdef WOLFSSL_SMALL_STACK
1952#ifndef WC_NO_CACHE_RESISTANT
1953   R = (fp_int*)XMALLOC(sizeof(fp_int) * 3, NULL, DYNAMIC_TYPE_BIGINT);
1954#else
1955   R = (fp_int*)XMALLOC(sizeof(fp_int) * 2, NULL, DYNAMIC_TYPE_BIGINT);
1956#endif
1957   if (R == NULL)
1958       return FP_MEM;
1959#endif
1960  fp_init(&R[0]);
1961  fp_init(&R[1]);
1962#ifndef WC_NO_CACHE_RESISTANT
1963  fp_init(&R[2]);
1964#endif
1965
1966  /* now we need R mod m */
1967  err = fp_montgomery_calc_normalization (&R[0], P);
1968  if (err != FP_OKAY) {
1969    WC_FREE_VAR_EX(R, NULL, DYNAMIC_TYPE_BIGINT);
1970    return err;
1971  }
1972
1973  /* now set R[0][1] to G * R mod m */
1974  if (fp_cmp_mag(P, G) != FP_GT) {
1975     /* G > P so we reduce it first */
1976     err = fp_mod(G, P, &R[1]);
1977     if (err != FP_OKAY) {
1978         WC_FREE_VAR_EX(R, NULL, DYNAMIC_TYPE_BIGINT);
1979         return err;
1980     }
1981  } else {
1982     fp_copy(G, &R[1]);
1983  }
1984  err = fp_mulmod (&R[1], &R[0], P, &R[1]);
1985  if (err != FP_OKAY) {
1986      WC_FREE_VAR_EX(R, NULL, DYNAMIC_TYPE_BIGINT);
1987      return err;
1988  }
1989
1990  /* for j = t-1 downto 0 do
1991        r_!k = R0*R1; r_k = r_k^2
1992  */
1993
1994  /* set initial mode and bit cnt */
1995  bitcnt = 1;
1996  buf    = 0;
1997  digidx = digits - 1;
1998
1999  for (;;) {
2000    /* grab next digit as required */
2001    if (--bitcnt == 0) {
2002      /* if digidx == -1 we are out of digits so break */
2003      if (digidx == -1) {
2004        break;
2005      }
2006      /* read next digit and reset bitcnt */
2007      buf    = X->dp[digidx--];
2008      bitcnt = (int)DIGIT_BIT;
2009    }
2010
2011    /* grab the next msb from the exponent */
2012    y     = (int)(buf >> (DIGIT_BIT - 1)) & 1;
2013    buf <<= (fp_digit)1;
2014
2015#ifdef WC_NO_CACHE_RESISTANT
2016    /* do ops */
2017    err = fp_mul(&R[0], &R[1], &R[y^1]);
2018    if (err != FP_OKAY) {
2019      WC_FREE_VAR_EX(R, NULL, DYNAMIC_TYPE_BIGINT);
2020      return err;
2021    }
2022    err = fp_montgomery_reduce(&R[y^1], P, mp);
2023    if (err != FP_OKAY) {
2024      WC_FREE_VAR_EX(R, NULL, DYNAMIC_TYPE_BIGINT);
2025      return err;
2026    }
2027
2028    err = fp_sqr(&R[y], &R[y]);
2029    if (err != FP_OKAY) {
2030      WC_FREE_VAR_EX(R, NULL, DYNAMIC_TYPE_BIGINT);
2031      return err;
2032    }
2033    err = fp_montgomery_reduce(&R[y], P, mp);
2034    if (err != FP_OKAY) {
2035      WC_FREE_VAR_EX(R, NULL, DYNAMIC_TYPE_BIGINT);
2036      return err;
2037    }
2038#else
2039    /* do ops */
2040    err = fp_mul(&R[0], &R[1], &R[2]);
2041    if (err != FP_OKAY) {
2042      WC_FREE_VAR_EX(R, NULL, DYNAMIC_TYPE_BIGINT);
2043      return err;
2044    }
2045    err = fp_montgomery_reduce(&R[2], P, mp);
2046    if (err != FP_OKAY) {
2047      WC_FREE_VAR_EX(R, NULL, DYNAMIC_TYPE_BIGINT);
2048      return err;
2049    }
2050    /* instead of using R[y^1] for mul, which leaks key bit to cache monitor,
2051     * use R[2] as temp, make sure address calc is constant, keep
2052     * &R[0] and &R[1] in cache */
2053    fp_copy(&R[2],
2054            (fp_int*) ( ((wc_ptr_t)&R[0] & wc_off_on_addr[y]) +
2055                        ((wc_ptr_t)&R[1] & wc_off_on_addr[y^1]) ) );
2056
2057    /* instead of using R[y] for sqr, which leaks key bit to cache monitor,
2058     * use R[2] as temp, make sure address calc is constant, keep
2059     * &R[0] and &R[1] in cache */
2060    fp_copy((fp_int*) ( ((wc_ptr_t)&R[0] & wc_off_on_addr[y^1]) +
2061                        ((wc_ptr_t)&R[1] & wc_off_on_addr[y]) ),
2062            &R[2]);
2063    err = fp_sqr(&R[2], &R[2]);
2064    if (err != FP_OKAY) {
2065      WC_FREE_VAR_EX(R, NULL, DYNAMIC_TYPE_BIGINT);
2066      return err;
2067    }
2068    err = fp_montgomery_reduce(&R[2], P, mp);
2069    if (err != FP_OKAY) {
2070      WC_FREE_VAR_EX(R, NULL, DYNAMIC_TYPE_BIGINT);
2071      return err;
2072    }
2073    fp_copy(&R[2],
2074            (fp_int*) ( ((wc_ptr_t)&R[0] & wc_off_on_addr[y^1]) +
2075                        ((wc_ptr_t)&R[1] & wc_off_on_addr[y]) ) );
2076#endif /* WC_NO_CACHE_RESISTANT */
2077  }
2078
2079   err = fp_montgomery_reduce(&R[0], P, mp);
2080   fp_copy(&R[0], Y);
2081   WC_FREE_VAR_EX(R, NULL, DYNAMIC_TYPE_BIGINT);
2082
2083   return err;
2084}
2085
2086#else
2087
2088/* Copy from a1 and a2 into r1 and r2 based on y in constant time.
2089 * When y is 1, r1 = a1 and r2 = a2.
2090 * When y is 0, r1 = a2 and r2 = a1.
2091 * Always copy size digits as that is the maximum size for a1 and a2.
2092 */
2093static void fp_copy_2_ct(fp_int* a1, fp_int* a2, fp_int* r1, fp_int* r2, int y,
2094    int size)
2095{
2096    int i;
2097
2098    /* Copy data - constant time. */
2099    for (i = 0; i < size; i++) {
2100        r1->dp[i] = (a1->dp[i] & ((fp_digit)wc_off_on_addr[y  ])) +
2101                    (a2->dp[i] & ((fp_digit)wc_off_on_addr[y^1]));
2102        r2->dp[i] = (a1->dp[i] & ((fp_digit)wc_off_on_addr[y^1])) +
2103                    (a2->dp[i] & ((fp_digit)wc_off_on_addr[y  ]));
2104    }
2105    /* Copy used. */
2106    r1->used = (a1->used & ((int)wc_off_on_addr[y  ])) +
2107               (a2->used & ((int)wc_off_on_addr[y^1]));
2108    r2->used = (a1->used & ((int)wc_off_on_addr[y^1])) +
2109               (a2->used & ((int)wc_off_on_addr[y  ]));
2110    /* Copy sign. */
2111    r1->sign = (a1->sign & ((int)wc_off_on_addr[y  ])) +
2112               (a2->sign & ((int)wc_off_on_addr[y^1]));
2113    r2->sign = (a1->sign & ((int)wc_off_on_addr[y^1])) +
2114               (a2->sign & ((int)wc_off_on_addr[y  ]));
2115}
2116
2117/* timing resistant montgomery ladder based exptmod
2118   Based on work by Marc Joye, Sung-Ming Yen, "The Montgomery Powering Ladder",
2119   Cryptographic Hardware and Embedded Systems, CHES 2002
2120*/
2121static int _fp_exptmod_ct(fp_int * G, fp_int * X, int digits, fp_int * P,
2122                          fp_int * Y)
2123{
2124#ifndef WOLFSSL_SMALL_STACK
2125  fp_int   R[4];   /* need a temp for cache resistance */
2126#else
2127  fp_int  *R;
2128#endif
2129  fp_digit buf, mp;
2130  int      err, bitcnt, digidx, y;
2131
2132  /* now setup montgomery  */
2133  if ((err = fp_montgomery_setup (P, &mp)) != FP_OKAY) {
2134     return err;
2135  }
2136
2137   WC_ALLOC_VAR_EX(R, fp_int, 4, NULL, DYNAMIC_TYPE_BIGINT, return FP_MEM);
2138  fp_init(&R[0]);
2139  fp_init(&R[1]);
2140  fp_init(&R[2]);
2141  fp_init(&R[3]);
2142
2143  /* now we need R mod m */
2144  err = fp_montgomery_calc_normalization (&R[0], P);
2145  if (err != FP_OKAY) {
2146    WC_FREE_VAR_EX(R, NULL, DYNAMIC_TYPE_BIGINT);
2147    return err;
2148  }
2149
2150  /* now set R[0][1] to G * R mod m */
2151  if (fp_cmp_mag(P, G) != FP_GT) {
2152     /* G > P so we reduce it first */
2153     err = fp_mod(G, P, &R[1]);
2154     if (err != FP_OKAY) {
2155         WC_FREE_VAR_EX(R, NULL, DYNAMIC_TYPE_BIGINT);
2156         return err;
2157     }
2158  } else {
2159     fp_copy(G, &R[1]);
2160  }
2161  err = fp_mulmod (&R[1], &R[0], P, &R[1]);
2162  if (err != FP_OKAY) {
2163      WC_FREE_VAR_EX(R, NULL, DYNAMIC_TYPE_BIGINT);
2164      return err;
2165  }
2166
2167  /* for j = t-1 downto 0 do
2168        r_!k = R0*R1; r_k = r_k^2
2169  */
2170
2171  /* set initial mode and bit cnt */
2172  bitcnt = 1;
2173  buf    = 0;
2174  digidx = digits - 1;
2175
2176  for (;;) {
2177    /* grab next digit as required */
2178    if (--bitcnt == 0) {
2179      /* if digidx == -1 we are out of digits so break */
2180      if (digidx == -1) {
2181        break;
2182      }
2183      /* read next digit and reset bitcnt */
2184      buf    = X->dp[digidx--];
2185      bitcnt = (int)DIGIT_BIT;
2186    }
2187
2188    /* grab the next msb from the exponent */
2189    y     = (int)(buf >> (DIGIT_BIT - 1)) & 1;
2190    buf <<= (fp_digit)1;
2191
2192    /* do ops */
2193    err = fp_mul(&R[0], &R[1], &R[2]);
2194    if (err != FP_OKAY) {
2195      WC_FREE_VAR_EX(R, NULL, DYNAMIC_TYPE_BIGINT);
2196      return err;
2197    }
2198    err = fp_montgomery_reduce(&R[2], P, mp);
2199    if (err != FP_OKAY) {
2200      WC_FREE_VAR_EX(R, NULL, DYNAMIC_TYPE_BIGINT);
2201      return err;
2202    }
2203
2204    /* instead of using R[y] for sqr, which leaks key bit to cache monitor,
2205     * use R[3] as temp, make sure address calc is constant, keep
2206     * &R[0] and &R[1] in cache */
2207    fp_copy((fp_int*) ( ((wc_ptr_t)&R[0] & wc_off_on_addr[y^1]) +
2208                        ((wc_ptr_t)&R[1] & wc_off_on_addr[y]) ),
2209            &R[3]);
2210    err = fp_sqr(&R[3], &R[3]);
2211    if (err != FP_OKAY) {
2212      WC_FREE_VAR_EX(R, NULL, DYNAMIC_TYPE_BIGINT);
2213      return err;
2214    }
2215    err = fp_montgomery_reduce(&R[3], P, mp);
2216    if (err != FP_OKAY) {
2217      WC_FREE_VAR_EX(R, NULL, DYNAMIC_TYPE_BIGINT);
2218      return err;
2219    }
2220    fp_copy_2_ct(&R[2], &R[3], &R[0], &R[1], y, P->used);
2221  }
2222
2223  err = fp_montgomery_reduce(&R[0], P, mp);
2224  fp_copy(&R[0], Y);
2225  WC_FREE_VAR_EX(R, NULL, DYNAMIC_TYPE_BIGINT);
2226  return err;
2227}
2228
2229#endif /* WC_PROTECT_ENCRYPTED_MEM */
2230
2231#endif /* TFM_TIMING_RESISTANT */
2232
2233/* y = g**x (mod b)
2234 * Some restrictions... x must be positive and < b
2235 */
2236static int _fp_exptmod_nct(fp_int * G, fp_int * X, fp_int * P, fp_int * Y)
2237{
2238  fp_int  *res;
2239  fp_digit buf, mp;
2240  int      err, bitbuf, bitcpy, bitcnt, mode, digidx, x, y, winsize;
2241#ifndef WOLFSSL_NO_MALLOC
2242  fp_int  *M;
2243#else
2244  fp_int   M[(1 << 6) + 1];
2245#endif
2246
2247  /* find window size */
2248  x = fp_count_bits (X);
2249  if (x <= 21) {
2250    winsize = 1;
2251  } else if (x <= 36) {
2252    winsize = 3;
2253  } else if (x <= 140) {
2254    winsize = 4;
2255  } else if (x <= 450) {
2256    winsize = 5;
2257  } else {
2258    winsize = 6;
2259  }
2260
2261  /* now setup montgomery  */
2262  if ((err = fp_montgomery_setup (P, &mp)) != FP_OKAY) {
2263     return err;
2264  }
2265
2266#ifndef WOLFSSL_NO_MALLOC
2267  /* only allocate space for what's needed for window plus res */
2268  M = (fp_int*)XMALLOC(sizeof(fp_int)*((1 << winsize) + 1), NULL,
2269                                                           DYNAMIC_TYPE_BIGINT);
2270  if (M == NULL) {
2271     return FP_MEM;
2272  }
2273#endif
2274  res = &M[(word32)(1 << winsize)];
2275
2276  /* init M array */
2277  for(x = 0; x < (1 << winsize); x++)
2278    fp_init(&M[x]);
2279
2280  /* setup result */
2281  fp_init(res);
2282
2283  /* create M table
2284   *
2285   * The M table contains powers of the input base, e.g. M[x] = G^x mod P
2286   *
2287   * The first half of the table is not computed though except for M[0] and M[1]
2288   */
2289
2290  /* now we need R mod m */
2291  err = fp_montgomery_calc_normalization (res, P);
2292  if (err != FP_OKAY) {
2293#ifndef WOLFSSL_NO_MALLOC
2294    XFREE(M, NULL, DYNAMIC_TYPE_BIGINT);
2295#endif
2296    return err;
2297  }
2298
2299  /* now set M[1] to G * R mod m */
2300  if (fp_cmp_mag(P, G) != FP_GT) {
2301     /* G > P so we reduce it first */
2302     err = fp_mod(G, P, &M[1]);
2303     if (err != FP_OKAY) {
2304     #ifndef WOLFSSL_NO_MALLOC
2305        XFREE(M, NULL, DYNAMIC_TYPE_BIGINT);
2306     #endif
2307        return err;
2308     }
2309  } else {
2310     fp_copy(G, &M[1]);
2311  }
2312  err = fp_mulmod (&M[1], res, P, &M[1]);
2313  if (err != FP_OKAY) {
2314  #ifndef WOLFSSL_NO_MALLOC
2315     XFREE(M, NULL, DYNAMIC_TYPE_BIGINT);
2316  #endif
2317     return err;
2318  }
2319
2320  /* compute the value at M[1<<(winsize-1)] by
2321   * squaring M[1] (winsize-1) times */
2322  fp_copy (&M[1], &M[(word32)(1 << (winsize - 1))]);
2323  for (x = 0; x < (winsize - 1); x++) {
2324    err = fp_sqr (&M[(word32)(1 << (winsize - 1))],
2325                  &M[(word32)(1 << (winsize - 1))]);
2326    if (err != FP_OKAY) {
2327#ifndef WOLFSSL_NO_MALLOC
2328      XFREE(M, NULL, DYNAMIC_TYPE_BIGINT);
2329#endif
2330      return err;
2331    }
2332    err = fp_montgomery_reduce_ex(&M[(word32)(1 << (winsize - 1))], P, mp, 0);
2333    if (err != FP_OKAY) {
2334#ifndef WOLFSSL_NO_MALLOC
2335      XFREE(M, NULL, DYNAMIC_TYPE_BIGINT);
2336#endif
2337      return err;
2338    }
2339  }
2340
2341  /* create upper table */
2342  for (x = (1 << (winsize - 1)) + 1; x < (1 << winsize); x++) {
2343    err = fp_mul(&M[x - 1], &M[1], &M[x]);
2344    if (err != FP_OKAY) {
2345#ifndef WOLFSSL_NO_MALLOC
2346      XFREE(M, NULL, DYNAMIC_TYPE_BIGINT);
2347#endif
2348      return err;
2349    }
2350    err = fp_montgomery_reduce_ex(&M[x], P, mp, 0);
2351    if (err != FP_OKAY) {
2352#ifndef WOLFSSL_NO_MALLOC
2353      XFREE(M, NULL, DYNAMIC_TYPE_BIGINT);
2354#endif
2355      return err;
2356    }
2357  }
2358
2359  /* set initial mode and bit cnt */
2360  mode   = 0;
2361  bitcnt = (x % DIGIT_BIT) + 1;
2362  buf    = 0;
2363  digidx = X->used - 1;
2364  bitcpy = 0;
2365  bitbuf = 0;
2366
2367  for (;;) {
2368    /* grab next digit as required */
2369    if (--bitcnt == 0) {
2370      /* if digidx == -1 we are out of digits so break */
2371      if (digidx == -1) {
2372        break;
2373      }
2374      /* read next digit and reset bitcnt */
2375      buf    = X->dp[digidx--];
2376      bitcnt = (int)DIGIT_BIT;
2377    }
2378
2379    /* grab the next msb from the exponent */
2380    y     = (int)(buf >> (DIGIT_BIT - 1)) & 1;
2381    buf <<= (fp_digit)1;
2382
2383    /* if the bit is zero and mode == 0 then we ignore it
2384     * These represent the leading zero bits before the first 1 bit
2385     * in the exponent.  Technically this opt is not required but it
2386     * does lower the # of trivial squaring/reductions used
2387     */
2388    if (mode == 0 && y == 0) {
2389      continue;
2390    }
2391
2392    /* if the bit is zero and mode == 1 then we square */
2393    if (mode == 1 && y == 0) {
2394      err = fp_sqr(res, res);
2395      if (err != FP_OKAY) {
2396#ifndef WOLFSSL_NO_MALLOC
2397        XFREE(M, NULL, DYNAMIC_TYPE_BIGINT);
2398#endif
2399        return err;
2400      }
2401      err = fp_montgomery_reduce_ex(res, P, mp, 0);
2402      if (err != FP_OKAY) {
2403#ifndef WOLFSSL_NO_MALLOC
2404        XFREE(M, NULL, DYNAMIC_TYPE_BIGINT);
2405#endif
2406        return err;
2407      }
2408      continue;
2409    }
2410
2411    /* else we add it to the window */
2412    bitbuf |= (y << (winsize - ++bitcpy));
2413    mode    = 2;
2414
2415    if (bitcpy == winsize) {
2416      /* ok window is filled so square as required and multiply  */
2417      /* square first */
2418      for (x = 0; x < winsize; x++) {
2419        err = fp_sqr(res, res);
2420        if (err != FP_OKAY) {
2421#ifndef WOLFSSL_NO_MALLOC
2422          XFREE(M, NULL, DYNAMIC_TYPE_BIGINT);
2423#endif
2424          return err;
2425        }
2426        err = fp_montgomery_reduce_ex(res, P, mp, 0);
2427        if (err != FP_OKAY) {
2428#ifndef WOLFSSL_NO_MALLOC
2429          XFREE(M, NULL, DYNAMIC_TYPE_BIGINT);
2430#endif
2431          return err;
2432        }
2433      }
2434
2435      /* then multiply */
2436      err = fp_mul(res, &M[bitbuf], res);
2437      if (err != FP_OKAY) {
2438#ifndef WOLFSSL_NO_MALLOC
2439        XFREE(M, NULL, DYNAMIC_TYPE_BIGINT);
2440#endif
2441        return err;
2442      }
2443      err = fp_montgomery_reduce_ex(res, P, mp, 0);
2444      if (err != FP_OKAY) {
2445#ifndef WOLFSSL_NO_MALLOC
2446        XFREE(M, NULL, DYNAMIC_TYPE_BIGINT);
2447#endif
2448        return err;
2449      }
2450
2451      /* empty window and reset */
2452      bitcpy = 0;
2453      bitbuf = 0;
2454      mode   = 1;
2455    }
2456  }
2457
2458  /* if bits remain then square/multiply */
2459  if (mode == 2 && bitcpy > 0) {
2460    /* square then multiply if the bit is set */
2461    for (x = 0; x < bitcpy; x++) {
2462      err = fp_sqr(res, res);
2463      if (err != FP_OKAY) {
2464#ifndef WOLFSSL_NO_MALLOC
2465        XFREE(M, NULL, DYNAMIC_TYPE_BIGINT);
2466#endif
2467        return err;
2468      }
2469      err = fp_montgomery_reduce_ex(res, P, mp, 0);
2470      if (err != FP_OKAY) {
2471#ifndef WOLFSSL_NO_MALLOC
2472        XFREE(M, NULL, DYNAMIC_TYPE_BIGINT);
2473#endif
2474        return err;
2475      }
2476
2477      /* get next bit of the window */
2478      bitbuf <<= 1;
2479      if ((bitbuf & (1 << winsize)) != 0) {
2480        /* then multiply */
2481        err = fp_mul(res, &M[1], res);
2482        if (err != FP_OKAY) {
2483#ifndef WOLFSSL_NO_MALLOC
2484          XFREE(M, NULL, DYNAMIC_TYPE_BIGINT);
2485#endif
2486          return err;
2487        }
2488        err = fp_montgomery_reduce_ex(res, P, mp, 0);
2489        if (err != FP_OKAY) {
2490#ifndef WOLFSSL_NO_MALLOC
2491          XFREE(M, NULL, DYNAMIC_TYPE_BIGINT);
2492#endif
2493          return err;
2494        }
2495      }
2496    }
2497  }
2498
2499  /* fixup result if Montgomery reduction is used
2500   * recall that any value in a Montgomery system is
2501   * actually multiplied by R mod n.  So we have
2502   * to reduce one more time to cancel out the factor
2503   * of R.
2504   */
2505  err = fp_montgomery_reduce_ex(res, P, mp, 0);
2506
2507  /* swap res with Y */
2508  fp_copy (res, Y);
2509
2510#ifndef WOLFSSL_NO_MALLOC
2511  XFREE(M, NULL, DYNAMIC_TYPE_BIGINT);
2512#endif
2513  return err;
2514}
2515
2516
2517#ifdef TFM_TIMING_RESISTANT
2518#if DIGIT_BIT <= 16
2519    #define WINSIZE    2
2520    #define WINMASK    0x3
2521#elif DIGIT_BIT <= 32
2522    #define WINSIZE    3
2523    #define WINMASK    0x7
2524#elif DIGIT_BIT <= 64
2525    #define WINSIZE    4
2526    #define WINMASK    0xf
2527#elif DIGIT_BIT <= 128
2528    #define WINSIZE    5
2529    #define WINMASK    0x1f
2530#endif
2531
2532/* y = 2**x (mod b)
2533 * Some restrictions... x must be positive and < b
2534 */
2535static int _fp_exptmod_base_2(fp_int * X, int digits, fp_int * P,
2536                              fp_int * Y)
2537{
2538  fp_digit buf, mp;
2539  int      err, bitbuf, bitcpy, bitcnt, digidx, x, y;
2540#ifdef WOLFSSL_SMALL_STACK
2541  fp_int  *res;
2542  fp_int  *tmp;
2543#else
2544  fp_int   res[1];
2545  fp_int   tmp[1];
2546#endif
2547
2548#ifdef WOLFSSL_SMALL_STACK
2549  res = (fp_int*)XMALLOC(2*sizeof(fp_int), NULL, DYNAMIC_TYPE_TMP_BUFFER);
2550  if (res == NULL) {
2551     return FP_MEM;
2552  }
2553  tmp = &res[1];
2554#endif
2555
2556  /* now setup montgomery  */
2557  if ((err = fp_montgomery_setup(P, &mp)) != FP_OKAY) {
2558     WC_FREE_VAR_EX(res, NULL, DYNAMIC_TYPE_TMP_BUFFER);
2559     return err;
2560  }
2561
2562  /* setup result */
2563  fp_init(res);
2564  fp_init(tmp);
2565
2566  err = fp_mul_2d(P, 1 << WINSIZE, tmp);
2567  if (err != FP_OKAY) {
2568    WC_FREE_VAR_EX(res, NULL, DYNAMIC_TYPE_TMP_BUFFER);
2569    return err;
2570  }
2571
2572  /* now we need R mod m */
2573  err = fp_montgomery_calc_normalization(res, P);
2574  if (err != FP_OKAY) {
2575    WC_FREE_VAR_EX(res, NULL, DYNAMIC_TYPE_TMP_BUFFER);
2576    return err;
2577  }
2578
2579  /* Get the top bits left over after taking WINSIZE bits starting at the
2580   * least-significant.
2581   */
2582  digidx = digits - 1;
2583  bitcpy = (digits * DIGIT_BIT) % WINSIZE;
2584  if (bitcpy > 0) {
2585      bitcnt = (int)DIGIT_BIT - bitcpy;
2586      buf    = X->dp[digidx--];
2587      bitbuf = (int)(buf >> bitcnt);
2588      /* Multiply montgomery representation of 1 by 2 ^ top */
2589      err = fp_mul_2d(res, bitbuf, res);
2590      if (err != FP_OKAY) {
2591        WC_FREE_VAR_EX(res, NULL, DYNAMIC_TYPE_TMP_BUFFER);
2592        return err;
2593      }
2594      err = fp_add(res, tmp, res);
2595      if (err != FP_OKAY) {
2596        WC_FREE_VAR_EX(res, NULL, DYNAMIC_TYPE_TMP_BUFFER);
2597        return err;
2598      }
2599      err = fp_mod(res, P, res);
2600      if (err != FP_OKAY) {
2601        WC_FREE_VAR_EX(res, NULL, DYNAMIC_TYPE_TMP_BUFFER);
2602        return err;
2603      }
2604      /* Move out bits used */
2605      buf  <<= bitcpy;
2606      bitcnt++;
2607  }
2608  else {
2609      bitcnt = 1;
2610      buf    = 0;
2611  }
2612
2613  /* empty window and reset  */
2614  bitbuf = 0;
2615  bitcpy = 0;
2616
2617  for (;;) {
2618    /* grab next digit as required */
2619    if (--bitcnt == 0) {
2620      /* if digidx == -1 we are out of digits so break */
2621      if (digidx == -1) {
2622        break;
2623      }
2624      /* read next digit and reset bitcnt */
2625      buf    = X->dp[digidx--];
2626      bitcnt = (int)DIGIT_BIT;
2627    }
2628
2629    /* grab the next msb from the exponent */
2630    y       = (int)(buf >> (DIGIT_BIT - 1)) & 1;
2631    buf   <<= (fp_digit)1;
2632    /* add bit to the window */
2633  #ifndef WC_PROTECT_ENCRYPTED_MEM
2634    bitbuf |= (y << (WINSIZE - ++bitcpy));
2635  #else
2636    /* Ensure value changes even when y is zero. */
2637    bitbuf += (WINMASK + 1) + (y << (WINSIZE - ++bitcpy));
2638  #endif
2639
2640    if (bitcpy == WINSIZE) {
2641      /* ok window is filled so square as required and multiply  */
2642      /* square first */
2643      for (x = 0; x < WINSIZE; x++) {
2644        err = fp_sqr(res, res);
2645        if (err != FP_OKAY) {
2646          WC_FREE_VAR_EX(res, NULL, DYNAMIC_TYPE_TMP_BUFFER);
2647          return err;
2648        }
2649        err = fp_montgomery_reduce(res, P, mp);
2650        if (err != FP_OKAY) {
2651          WC_FREE_VAR_EX(res, NULL, DYNAMIC_TYPE_TMP_BUFFER);
2652          return err;
2653        }
2654      }
2655
2656      /* then multiply by 2^bitbuf */
2657    #ifndef WC_PROTECT_ENCRYPTED_MEM
2658      err = fp_mul_2d(res, bitbuf, res);
2659    #else
2660      /* Get the window bits. */
2661      err = fp_mul_2d(res, bitbuf & WINMASK, res);
2662    #endif
2663      if (err != FP_OKAY) {
2664        WC_FREE_VAR_EX(res, NULL, DYNAMIC_TYPE_TMP_BUFFER);
2665        return err;
2666      }
2667      /* Add in value to make mod operation take same time */
2668      err = fp_add(res, tmp, res);
2669      if (err != FP_OKAY) {
2670        WC_FREE_VAR_EX(res, NULL, DYNAMIC_TYPE_TMP_BUFFER);
2671        return err;
2672      }
2673      err = fp_mod(res, P, res);
2674      if (err != FP_OKAY) {
2675        WC_FREE_VAR_EX(res, NULL, DYNAMIC_TYPE_TMP_BUFFER);
2676        return err;
2677      }
2678
2679      /* empty window and reset */
2680      bitcpy = 0;
2681    #ifndef WC_PROTECT_ENCRYPTED_MEM
2682      bitbuf = 0;
2683    #else
2684      /* Ensure value is new even when bottom bits are 0. */
2685      bitbuf = (WINMASK + 1) + (bitbuf & ~WINMASK);
2686    #endif
2687    }
2688  }
2689
2690  /* fixup result if Montgomery reduction is used
2691   * recall that any value in a Montgomery system is
2692   * actually multiplied by R mod n.  So we have
2693   * to reduce one more time to cancel out the factor
2694   * of R.
2695   */
2696  err = fp_montgomery_reduce(res, P, mp);
2697
2698  /* swap res with Y */
2699  fp_copy(res, Y);
2700
2701  WC_FREE_VAR_EX(res, NULL, DYNAMIC_TYPE_TMP_BUFFER);
2702  return err;
2703}
2704
2705#undef WINSIZE
2706#else
2707#if DIGIT_BIT < 16
2708    #define WINSIZE    3
2709#elif DIGIT_BIT < 32
2710    #define WINSIZE    4
2711#elif DIGIT_BIT < 64
2712    #define WINSIZE    5
2713#elif DIGIT_BIT < 128
2714    #define WINSIZE    6
2715#elif DIGIT_BIT == 128
2716    #define WINSIZE    7
2717#endif
2718
2719/* y = 2**x (mod b)
2720 * Some restrictions... x must be positive and < b
2721 */
2722static int _fp_exptmod_base_2(fp_int * X, int digits, fp_int * P,
2723                              fp_int * Y)
2724{
2725  fp_digit buf, mp;
2726  int      err, bitbuf, bitcpy, bitcnt, digidx, x, y;
2727  WC_DECLARE_VAR(res, fp_int, 1, 0);
2728
2729  /* now setup montgomery  */
2730  if ((err = fp_montgomery_setup(P, &mp)) != FP_OKAY) {
2731    return err;
2732  }
2733
2734  WC_ALLOC_VAR_EX(res, fp_int, 1, NULL, DYNAMIC_TYPE_TMP_BUFFER,
2735      return FP_MEM);
2736
2737  /* setup result */
2738  fp_init(res);
2739
2740  /* now we need R mod m */
2741  err = fp_montgomery_calc_normalization(res, P);
2742  if (err != FP_OKAY) {
2743    WC_FREE_VAR_EX(res, NULL, DYNAMIC_TYPE_TMP_BUFFER);
2744    return err;
2745  }
2746
2747  /* Get the top bits left over after taking WINSIZE bits starting at the
2748   * least-significant.
2749   */
2750  digidx = digits - 1;
2751  bitcpy = (digits * DIGIT_BIT) % WINSIZE;
2752  if (bitcpy > 0) {
2753      bitcnt = (int)DIGIT_BIT - bitcpy;
2754      buf    = X->dp[digidx--];
2755      bitbuf = (int)(buf >> bitcnt);
2756      /* Multiply montgomery representation of 1 by 2 ^ top */
2757      err = fp_mul_2d(res, bitbuf, res);
2758      if (err != FP_OKAY) {
2759        WC_FREE_VAR_EX(res, NULL, DYNAMIC_TYPE_TMP_BUFFER);
2760        return err;
2761      }
2762      err = fp_mod(res, P, res);
2763      if (err != FP_OKAY) {
2764        WC_FREE_VAR_EX(res, NULL, DYNAMIC_TYPE_TMP_BUFFER);
2765        return err;
2766      }
2767      /* Move out bits used */
2768      buf  <<= bitcpy;
2769      bitcnt++;
2770  }
2771  else {
2772      bitcnt = 1;
2773      buf    = 0;
2774  }
2775
2776  /* empty window and reset  */
2777  bitbuf = 0;
2778  bitcpy = 0;
2779
2780  for (;;) {
2781    /* grab next digit as required */
2782    if (--bitcnt == 0) {
2783      /* if digidx == -1 we are out of digits so break */
2784      if (digidx == -1) {
2785        break;
2786      }
2787      /* read next digit and reset bitcnt */
2788      buf    = X->dp[digidx--];
2789      bitcnt = (int)DIGIT_BIT;
2790    }
2791
2792    /* grab the next msb from the exponent */
2793    y       = (int)(buf >> (DIGIT_BIT - 1)) & 1;
2794    buf   <<= (fp_digit)1;
2795    /* add bit to the window */
2796    bitbuf |= (y << (WINSIZE - ++bitcpy));
2797
2798    if (bitcpy == WINSIZE) {
2799      /* ok window is filled so square as required and multiply  */
2800      /* square first */
2801      for (x = 0; x < WINSIZE; x++) {
2802        err = fp_sqr(res, res);
2803        if (err != FP_OKAY) {
2804          WC_FREE_VAR_EX(res, NULL, DYNAMIC_TYPE_TMP_BUFFER);
2805          return err;
2806        }
2807        err = fp_montgomery_reduce(res, P, mp);
2808        if (err != FP_OKAY) {
2809          WC_FREE_VAR_EX(res, NULL, DYNAMIC_TYPE_TMP_BUFFER);
2810          return err;
2811        }
2812      }
2813
2814      /* then multiply by 2^bitbuf */
2815      err = fp_mul_2d(res, bitbuf, res);
2816      if (err != FP_OKAY) {
2817        WC_FREE_VAR_EX(res, NULL, DYNAMIC_TYPE_TMP_BUFFER);
2818        return err;
2819      }
2820      err = fp_mod(res, P, res);
2821      if (err != FP_OKAY) {
2822        WC_FREE_VAR_EX(res, NULL, DYNAMIC_TYPE_TMP_BUFFER);
2823        return err;
2824      }
2825
2826      /* empty window and reset */
2827      bitcpy = 0;
2828      bitbuf = 0;
2829    }
2830  }
2831
2832  /* fixup result if Montgomery reduction is used
2833   * recall that any value in a Montgomery system is
2834   * actually multiplied by R mod n.  So we have
2835   * to reduce one more time to cancel out the factor
2836   * of R.
2837   */
2838  err = fp_montgomery_reduce(res, P, mp);
2839
2840  /* swap res with Y */
2841  fp_copy(res, Y);
2842
2843  WC_FREE_VAR_EX(res, NULL, DYNAMIC_TYPE_TMP_BUFFER);
2844  return err;
2845}
2846
2847#undef WINSIZE
2848#endif
2849
2850/* Y = (G * X) mod P */
2851int fp_exptmod(fp_int * G, fp_int * X, fp_int * P, fp_int * Y)
2852{
2853#if defined(WOLFSSL_ESP32_CRYPT_RSA_PRI_EXPTMOD)
2854    int retHW = FP_OKAY;
2855#endif
2856
2857   /* handle modulus of zero and prevent overflows */
2858   if (fp_iszero(P) || (P->used > (FP_SIZE/2))) {
2859      return FP_VAL;
2860   }
2861   if (fp_isone(P)) {
2862      fp_set(Y, 0);
2863      return FP_OKAY;
2864   }
2865   if (fp_iszero(X)) {
2866      fp_set(Y, 1);
2867      return FP_OKAY;
2868   }
2869   if (fp_iszero(G)) {
2870      fp_set(Y, 0);
2871      return FP_OKAY;
2872   }
2873
2874#if defined(WOLFSSL_ESP32_CRYPT_RSA_PRI_EXPTMOD)
2875   if (esp_hw_validation_active()) {
2876      ESP_LOGV(TAG, "Skipping call to esp_mp_exptmod "
2877                    "during active validation.");
2878   }
2879   else {
2880      /* HW accelerated exptmod  */
2881      retHW = esp_mp_exptmod(G, X, P, Y);
2882      switch (retHW) {
2883         case MP_OKAY:
2884            /* successfully computed in HW */
2885            return retHW;
2886            break;
2887
2888         case WC_NO_ERR_TRACE(WC_HW_WAIT_E): /* MP_HW_BUSY math HW busy, fall back */
2889         case MP_HW_FALLBACK:    /* forced fallback from HW to SW */
2890         case WC_NO_ERR_TRACE(MP_HW_VALIDATION_ACTIVE): /* use SW to compare to HW */
2891            /* use software calc */
2892            break;
2893
2894         default:
2895            /* Once we've failed, exit without trying to continue.
2896             * We may have mangled operands: (e.g. Z = X * Z)
2897             * Future implementation may consider saving operands,
2898             * but hard errors should never actually occur. */
2899            return retHW; /* error */
2900            break;
2901      } /* switch */
2902   } /* if validation check */
2903   /* fall through to software calcs */
2904#endif /* WOLFSSL_ESP32_CRYPT_RSA_PRI_EXPTMOD */
2905
2906   if (X->sign == FP_NEG) {
2907#ifndef POSITIVE_EXP_ONLY  /* reduce stack if assume no negatives */
2908      int    err;
2909      WC_DECLARE_VAR(tmp, fp_int, 2, 0);
2910
2911      WC_ALLOC_VAR_EX(tmp, fp_int, 2, NULL, DYNAMIC_TYPE_BIGINT,
2912          return FP_MEM);
2913
2914      /* yes, copy G and invmod it */
2915      fp_init_copy(&tmp[0], G);
2916      fp_init_copy(&tmp[1], P);
2917      tmp[1].sign = FP_ZPOS;
2918      err = fp_invmod(&tmp[0], &tmp[1], &tmp[0]);
2919      if (err == FP_OKAY) {
2920         fp_copy(X, &tmp[1]);
2921         tmp[1].sign = FP_ZPOS;
2922   #ifdef TFM_TIMING_RESISTANT
2923         err =  _fp_exptmod_ct(&tmp[0], &tmp[1], tmp[1].used, P, Y);
2924   #else
2925         err =  _fp_exptmod_nct(&tmp[0], &tmp[1], P, Y);
2926   #endif
2927         if ((err == 0) && (P->sign == FP_NEG)) {
2928            err = fp_add(Y, P, Y);
2929         }
2930      }
2931      WC_FREE_VAR_EX(tmp, NULL, DYNAMIC_TYPE_TMP_BUFFER);
2932      return err;
2933#else
2934      return FP_VAL;
2935#endif /* POSITIVE_EXP_ONLY check */
2936   }
2937   else if (G->used == 1 && G->dp[0] == 2) {
2938      return _fp_exptmod_base_2(X, X->used, P, Y);
2939   }
2940   else {
2941      /* Positive exponent so just exptmod */
2942#ifdef TFM_TIMING_RESISTANT
2943      return _fp_exptmod_ct(G, X, X->used, P, Y);
2944#else
2945      return _fp_exptmod_nct(G, X, P, Y);
2946#endif
2947   }
2948}
2949
2950int fp_exptmod_ex(fp_int * G, fp_int * X, int digits, fp_int * P, fp_int * Y)
2951{
2952#if defined(WOLFSSL_ESP32_CRYPT_RSA_PRI_EXPTMOD)
2953   int retHW = FP_OKAY;
2954#endif
2955
2956   /* handle modulus of zero and prevent overflows */
2957   if (fp_iszero(P) || (P->used > (FP_SIZE/2))) {
2958      return FP_VAL;
2959   }
2960   if (fp_isone(P)) {
2961      fp_set(Y, 0);
2962      return FP_OKAY;
2963   }
2964   if (fp_iszero(X)) {
2965      fp_set(Y, 1);
2966      return FP_OKAY;
2967   }
2968   if (fp_iszero(G)) {
2969      fp_set(Y, 0);
2970      return FP_OKAY;
2971   }
2972
2973#if defined(WOLFSSL_ESP32_CRYPT_RSA_PRI_EXPTMOD)
2974   retHW = esp_mp_exptmod(G, X, P, Y);
2975   switch (retHW) {
2976      case MP_OKAY:
2977         /* successfully computed in HW */
2978         return retHW;
2979         break;
2980
2981      case WC_NO_ERR_TRACE(WC_HW_WAIT_E): /* MP_HW_BUSY math HW busy, fall back */
2982      case MP_HW_FALLBACK:    /* forced fallback from HW to SW */
2983      case MP_HW_VALIDATION_ACTIVE: /* use SW to compare to HW */
2984         /* use software calc */
2985         break;
2986
2987      default:
2988         /* Once we've failed, exit without trying to continue.
2989          * We may have mangled operands: (e.g. Z = X * Z)
2990          * Future implementation may consider saving operands,
2991          * but hard errors should never actually occur. */
2992         return retHW;
2993         break;
2994   } /* HW result switch */
2995   /* falling through to SW: */
2996#endif /* WOLFSSL_ESP32_CRYPT_RSA_PRI_EXPTMOD */
2997
2998   if (X->sign == FP_NEG) {
2999#ifndef POSITIVE_EXP_ONLY  /* reduce stack if assume no negatives */
3000      int    err;
3001      WC_DECLARE_VAR(tmp, fp_int, 2, 0);
3002
3003      WC_ALLOC_VAR_EX(tmp, fp_int, 2, NULL, DYNAMIC_TYPE_TMP_BUFFER,
3004          return FP_MEM);
3005
3006      /* yes, copy G and invmod it */
3007      fp_init_copy(&tmp[0], G);
3008      fp_init_copy(&tmp[1], P);
3009      tmp[1].sign = FP_ZPOS;
3010      err = fp_invmod(&tmp[0], &tmp[1], &tmp[0]);
3011      if (err == FP_OKAY) {
3012         X->sign = FP_ZPOS;
3013#ifdef TFM_TIMING_RESISTANT
3014         err =  _fp_exptmod_ct(&tmp[0], X, digits, P, Y);
3015#else
3016         err =  _fp_exptmod_nct(&tmp[0], X, P, Y);
3017         (void)digits;
3018#endif
3019         if (X != Y) {
3020            X->sign = FP_NEG;
3021         }
3022         if ((err == 0) && (P->sign == FP_NEG)) {
3023            err = fp_add(Y, P, Y);
3024         }
3025      }
3026      WC_FREE_VAR_EX(tmp, NULL, DYNAMIC_TYPE_BIGINT);
3027      return err;
3028#else
3029      return FP_VAL;
3030#endif
3031   }
3032   else {
3033      /* Positive exponent so just exptmod */
3034#ifdef TFM_TIMING_RESISTANT
3035      return _fp_exptmod_ct(G, X, digits, P, Y);
3036#else
3037      return  _fp_exptmod_nct(G, X, P, Y);
3038#endif
3039   }
3040}
3041
3042int fp_exptmod_nct(fp_int * G, fp_int * X, fp_int * P, fp_int * Y)
3043{
3044#if defined(WOLFSSL_ESP32_CRYPT_RSA_PRI_EXPTMOD)
3045   int retHW = FP_OKAY;
3046#endif
3047
3048   /* handle modulus of zero and prevent overflows */
3049   if  (fp_iszero(P)) {
3050      return FP_VAL;
3051   }
3052   if (P->used > (FP_SIZE/2)) {
3053      /* FP_MAX_BITS too small is a common cert failure cause */
3054#ifdef WOLFSSL_DEBUG_CERTS
3055      WOLFSSL_MSG_CERT_EX("TFM fp_exptmod_nct failed: P.used (%d) > (FP_SIZE/2)"
3056                       "; FP_SIZE: %d; FP_MAX_SIZE: %d",
3057                       P->used, FP_SIZE, FP_MAX_BITS, FP_MAX_SIZE);
3058      WOLFSSL_MSG_CERT_EX("Consider adjusting current FP_MAX_BITS: %d",
3059                       FP_MAX_BITS);
3060#endif
3061      return FP_VAL;
3062   }
3063   if (fp_isone(P)) {
3064      fp_set(Y, 0);
3065      return FP_OKAY;
3066   }
3067   if (fp_iszero(X)) {
3068      fp_set(Y, 1);
3069      return FP_OKAY;
3070   }
3071   if (fp_iszero(G)) {
3072      fp_set(Y, 0);
3073      return FP_OKAY;
3074   }
3075
3076#if defined(WOLFSSL_ESP32_CRYPT_RSA_PRI_EXPTMOD)
3077   retHW = esp_mp_exptmod(G, X, P, Y);
3078   switch (retHW) {
3079      case MP_OKAY:
3080         /* successfully computed in HW */
3081         return retHW;
3082         break;
3083
3084      case WC_NO_ERR_TRACE(WC_HW_WAIT_E): /* MP_HW_BUSY math HW busy, fall back */
3085      case MP_HW_FALLBACK:    /* forced fallback from HW to SW */
3086      case MP_HW_VALIDATION_ACTIVE: /* use SW to compare to HW */
3087         /* use software calc */
3088         break;
3089
3090      default:
3091         /* Once we've failed, exit without trying to continue.
3092          * We may have mangled operands: (e.g. Z = X * Z)
3093          * Future implementation may consider saving operands,
3094          * but hard errors should never actually occur. */
3095         return retHW;
3096         break;
3097   }
3098   /* falling through to SW: */
3099#endif
3100
3101   if (X->sign == FP_NEG) {
3102#ifndef POSITIVE_EXP_ONLY  /* reduce stack if assume no negatives */
3103      int    err;
3104      WC_DECLARE_VAR(tmp, fp_int, 2, 0);
3105
3106      WC_ALLOC_VAR_EX(tmp, fp_int, 2, NULL, DYNAMIC_TYPE_TMP_BUFFER,
3107          return FP_MEM);
3108
3109      /* yes, copy G and invmod it */
3110      fp_init_copy(&tmp[0], G);
3111      fp_init_copy(&tmp[1], P);
3112      tmp[1].sign = FP_ZPOS;
3113      err = fp_invmod(&tmp[0], &tmp[1], &tmp[0]);
3114      if (err == FP_OKAY) {
3115         X->sign = FP_ZPOS;
3116         err =  _fp_exptmod_nct(&tmp[0], X, P, Y);
3117         if (X != Y) {
3118            X->sign = FP_NEG;
3119         }
3120         if ((err == 0) && (P->sign == FP_NEG)) {
3121            err = fp_add(Y, P, Y);
3122         }
3123      }
3124      WC_FREE_VAR_EX(tmp, NULL, DYNAMIC_TYPE_BIGINT);
3125      return err;
3126#else
3127      return FP_VAL;
3128#endif
3129   }
3130   else {
3131      /* Positive exponent so just exptmod */
3132      return  _fp_exptmod_nct(G, X, P, Y);
3133   }
3134}
3135
3136/* computes a = 2**b */
3137void fp_2expt(fp_int *a, int b)
3138{
3139   int     z;
3140
3141   /* zero a as per default */
3142   fp_zero (a);
3143
3144   if (b < 0) {
3145      return;
3146   }
3147
3148   z = b / DIGIT_BIT;
3149   if (z >= FP_SIZE) {
3150      return;
3151   }
3152
3153  /* set the used count of where the bit will go */
3154  a->used = z + 1;
3155
3156  /* put the single bit in its place */
3157  a->dp[z] = ((fp_digit)1) << (b % DIGIT_BIT);
3158}
3159
3160/* b = a*a  */
3161int fp_sqr(fp_int *A, fp_int *B)
3162{
3163    int err;
3164    int y, oldused;
3165
3166    oldused = B->used;
3167    y = A->used;
3168
3169    /* error if we're out of range */
3170    if (y + y >= FP_SIZE) {
3171       err = FP_VAL;
3172       goto clean;
3173    }
3174
3175#if defined(WOLFSSL_ESP32_CRYPT_RSA_PRI_MP_MUL)
3176    if (esp_hw_validation_active()) {
3177        ESP_LOGV(TAG, "Skipping call to esp_mp_mul "
3178                      "during active validation.");
3179    }
3180    else {
3181        err = esp_mp_mul(A, A, B); /* HW accelerated multiply  */
3182        switch (err) {
3183            case MP_OKAY:
3184                goto clean; /* success */
3185                break;
3186
3187            case WC_NO_ERR_TRACE(WC_HW_WAIT_E): /* MP_HW_BUSY math HW busy, fall back */
3188            case MP_HW_FALLBACK:    /* forced fallback from HW to SW */
3189            case MP_HW_VALIDATION_ACTIVE: /* use SW to compare to HW */
3190                /* fall back to software, below */
3191                break;
3192
3193            default:
3194                /* Once we've failed, exit without trying to continue.
3195                 * We may have mangled operands: (e.g. Z = X * Z)
3196                 * Future implementation may consider saving operands,
3197                 * but errors should never occur. */
3198                goto clean;  /* error */
3199                break;
3200        }
3201    }
3202    /* fall through to software calcs */
3203#endif /* WOLFSSL_ESP32_CRYPT_RSA_PRI_MP_MUL */
3204
3205#if defined(TFM_SQR3) && FP_SIZE >= 6
3206        if (y <= 3) {
3207           err = fp_sqr_comba3(A,B);
3208           goto clean;
3209        }
3210#endif
3211#if defined(TFM_SQR4) && FP_SIZE >= 8
3212        if (y == 4) {
3213           err = fp_sqr_comba4(A,B);
3214           goto clean;
3215        }
3216#endif
3217#if defined(TFM_SQR6) && FP_SIZE >= 12
3218        if (y <= 6) {
3219           err = fp_sqr_comba6(A,B);
3220           goto clean;
3221        }
3222#endif
3223#if defined(TFM_SQR7) && FP_SIZE >= 14
3224        if (y == 7) {
3225           err = fp_sqr_comba7(A,B);
3226           goto clean;
3227        }
3228#endif
3229#if defined(TFM_SQR8) && FP_SIZE >= 16
3230        if (y == 8) {
3231           err = fp_sqr_comba8(A,B);
3232           goto clean;
3233        }
3234#endif
3235#if defined(TFM_SQR9) && FP_SIZE >= 18
3236        if (y == 9) {
3237           err = fp_sqr_comba9(A,B);
3238           goto clean;
3239        }
3240#endif
3241#if defined(TFM_SQR12) && FP_SIZE >= 24
3242        if (y <= 12) {
3243           err = fp_sqr_comba12(A,B);
3244           goto clean;
3245        }
3246#endif
3247#if defined(TFM_SQR17) && FP_SIZE >= 34
3248        if (y <= 17) {
3249           err = fp_sqr_comba17(A,B);
3250           goto clean;
3251        }
3252#endif
3253#if defined(TFM_SMALL_SET)
3254        if (y <= 16) {
3255           err = fp_sqr_comba_small(A,B);
3256           goto clean;
3257        }
3258#endif
3259#if defined(TFM_SQR20) && FP_SIZE >= 40
3260        if (y <= 20) {
3261           err = fp_sqr_comba20(A,B);
3262           goto clean;
3263        }
3264#endif
3265#if defined(TFM_SQR24) && FP_SIZE >= 48
3266        if (y <= 24) {
3267           err = fp_sqr_comba24(A,B);
3268           goto clean;
3269        }
3270#endif
3271#if defined(TFM_SQR28) && FP_SIZE >= 56
3272        if (y <= 28) {
3273           err = fp_sqr_comba28(A,B);
3274           goto clean;
3275        }
3276#endif
3277#if defined(TFM_SQR32) && FP_SIZE >= 64
3278        if (y <= 32) {
3279           err = fp_sqr_comba32(A,B);
3280           goto clean;
3281        }
3282#endif
3283#if defined(TFM_SQR48) && FP_SIZE >= 96
3284        if (y <= 48) {
3285           err = fp_sqr_comba48(A,B);
3286           goto clean;
3287        }
3288#endif
3289#if defined(TFM_SQR64) && FP_SIZE >= 128
3290        if (y <= 64) {
3291           err = fp_sqr_comba64(A,B);
3292           goto clean;
3293        }
3294#endif
3295       err = fp_sqr_comba(A, B);
3296
3297clean:
3298  /* zero any excess digits on the destination that we didn't write to */
3299  for (y = B->used; y >= 0 && y < oldused; y++) {
3300    B->dp[y] = 0;
3301  }
3302
3303  return err;
3304}
3305
3306/* generic comba squarer */
3307int fp_sqr_comba(fp_int *A, fp_int *B)
3308{
3309  int       pa, ix, iz;
3310  fp_digit  c0, c1, c2;
3311#ifdef TFM_ISO
3312  fp_word   tt = 0;
3313#endif
3314   fp_int    *dst;
3315   WC_DECLARE_VAR(tmp, fp_int, 1, 0);
3316
3317   WC_ALLOC_VAR_EX(tmp, fp_int, 1, NULL, DYNAMIC_TYPE_BIGINT,
3318       return FP_MEM);
3319
3320  /* get size of output and trim */
3321  pa = A->used + A->used;
3322  if (pa >= FP_SIZE) {
3323     pa = FP_SIZE-1;
3324  }
3325
3326  /* number of output digits to produce */
3327  COMBA_START;
3328  COMBA_CLEAR;
3329
3330  if (A == B) {
3331     fp_init(tmp);
3332     dst = tmp;
3333  } else {
3334     fp_zero(B);
3335     dst = B;
3336  }
3337
3338  for (ix = 0; ix < pa; ix++) {
3339      int      tx, ty, iy;
3340      fp_digit *tmpy, *tmpx;
3341
3342      /* get offsets into the two bignums */
3343      ty = MIN(A->used-1, ix);
3344      tx = ix - ty;
3345
3346      /* setup temp aliases */
3347      tmpx = A->dp + tx;
3348      tmpy = A->dp + ty;
3349
3350      /* this is the number of times the loop will iterate,
3351         while (tx++ < a->used && ty-- >= 0) { ... }
3352       */
3353      iy = MIN(A->used-tx, ty+1);
3354
3355      /* now for squaring tx can never equal ty
3356       * we halve the distance since they approach
3357       * at a rate of 2x and we have to round because
3358       * odd cases need to be executed
3359       */
3360      iy = MIN(iy, (ty-tx+1)>>1);
3361
3362      /* forward carries */
3363      COMBA_FORWARD;
3364
3365      /* execute loop */
3366      for (iz = 0; iz < iy; iz++) {
3367          SQRADD2(*tmpx++, *tmpy--);
3368      }
3369
3370      /* even columns have the square term in them */
3371      if ((ix&1) == 0) {
3372          /* TAO change COMBA_ADD back to SQRADD */
3373          SQRADD(A->dp[ix>>1], A->dp[ix>>1]);
3374      }
3375
3376      /* store it */
3377      COMBA_STORE(dst->dp[ix]);
3378  }
3379
3380  COMBA_FINI;
3381
3382  /* setup dest */
3383  dst->used = pa;
3384  fp_clamp (dst);
3385  if (dst != B) {
3386     fp_copy(dst, B);
3387  }
3388
3389  /* Variables used but not seen by cppcheck. */
3390  (void)c0; (void)c1; (void)c2;
3391#ifdef TFM_ISO
3392  (void)tt;
3393#endif
3394
3395  WC_FREE_VAR_EX(tmp, NULL, DYNAMIC_TYPE_BIGINT);
3396  return FP_OKAY;
3397}
3398
3399int fp_cmp(fp_int *a, fp_int *b)
3400{
3401   if (a->sign == FP_NEG && b->sign == FP_ZPOS) {
3402      return FP_LT;
3403   } else if (a->sign == FP_ZPOS && b->sign == FP_NEG) {
3404      return FP_GT;
3405   } else {
3406      /* compare digits */
3407      if (a->sign == FP_NEG) {
3408         /* if negative compare opposite direction */
3409         return fp_cmp_mag(b, a);
3410      } else {
3411         return fp_cmp_mag(a, b);
3412      }
3413   }
3414}
3415
3416/* compare against a single digit */
3417int fp_cmp_d(fp_int *a, fp_digit b)
3418{
3419  /* special case for zero*/
3420  if (a->used == 0 && b == 0)
3421    return FP_EQ;
3422
3423  /* compare based on sign */
3424  if ((b && a->used == 0) || a->sign == FP_NEG) {
3425    return FP_LT;
3426  }
3427
3428  /* compare based on magnitude */
3429  if (a->used > 1) {
3430    return FP_GT;
3431  }
3432
3433  /* compare the only digit of a to b */
3434  if (a->dp[0] > b) {
3435    return FP_GT;
3436  } else if (a->dp[0] < b) {
3437    return FP_LT;
3438  } else {
3439    return FP_EQ;
3440  }
3441
3442}
3443
3444int fp_cmp_mag(fp_int *a, fp_int *b)
3445{
3446   int x;
3447
3448   if (a->used > b->used) {
3449      return FP_GT;
3450   } else if (a->used < b->used) {
3451      return FP_LT;
3452   } else {
3453      for (x = a->used - 1; x >= 0; x--) {
3454          if (a->dp[x] > b->dp[x]) {
3455             return FP_GT;
3456          } else if (a->dp[x] < b->dp[x]) {
3457             return FP_LT;
3458          }
3459      }
3460   }
3461   return FP_EQ;
3462}
3463
3464
3465/* sets up the montgomery reduction */
3466int fp_montgomery_setup(fp_int *a, fp_digit *rho)
3467{
3468  fp_digit x, b;
3469
3470/* fast inversion mod 2**k
3471 *
3472 * Based on the fact that
3473 *
3474 * XA = 1 (mod 2**n)  =>  (X(2-XA)) A = 1 (mod 2**2n)
3475 *                    =>  2*X*A - X*X*A*A = 1
3476 *                    =>  2*(1) - (1)     = 1
3477 */
3478  b = a->dp[0];
3479
3480  if ((b & 1) == 0) {
3481    return FP_VAL;
3482  }
3483
3484  x = (((b + 2) & 4) << 1) + b; /* here x*a==1 mod 2**4 */
3485  x *= 2 - b * x;               /* here x*a==1 mod 2**8 */
3486  x *= 2 - b * x;               /* here x*a==1 mod 2**16 */
3487  x *= 2 - b * x;               /* here x*a==1 mod 2**32 */
3488#ifdef FP_64BIT
3489  x *= 2 - b * x;               /* here x*a==1 mod 2**64 */
3490#endif
3491
3492  /* rho = -1/m mod b */
3493  *rho = (fp_digit) (((fp_word) 1 << ((fp_word) DIGIT_BIT)) - ((fp_word)x));
3494
3495  return FP_OKAY;
3496}
3497
3498/* computes a = B**n mod b without division or multiplication useful for
3499 * normalizing numbers in a Montgomery system.
3500 */
3501int fp_montgomery_calc_normalization(fp_int *a, fp_int *b)
3502{
3503  int     x, bits;
3504
3505  /* how many bits of last digit does b use */
3506  bits = fp_count_bits (b) % DIGIT_BIT;
3507  if (!bits) bits = DIGIT_BIT;
3508
3509  /* compute A = B^(n-1) * 2^(bits-1) */
3510  if (b->used > 1) {
3511     fp_2expt (a, (b->used - 1) * DIGIT_BIT + bits - 1);
3512  } else {
3513     fp_set(a, 1);
3514     bits = 1;
3515  }
3516
3517  /* now compute C = A * B mod b */
3518  for (x = bits - 1; x < (int)DIGIT_BIT; x++) {
3519    int err = fp_mul_2 (a, a);
3520    if (err != FP_OKAY) {
3521      return err;
3522    }
3523    if (fp_cmp_mag (a, b) != FP_LT) {
3524      s_fp_sub (a, b, a);
3525    }
3526  }
3527  return FP_OKAY;
3528}
3529
3530
3531#ifdef TFM_SMALL_MONT_SET
3532    #include "fp_mont_small.i"
3533#endif
3534
3535#ifdef HAVE_INTEL_MULX
3536static WC_INLINE void innermul8_mulx(fp_digit *c_mulx, fp_digit *cy_mulx, fp_digit *tmpm, fp_digit mu)
3537{
3538    fp_digit cy = *cy_mulx ;
3539    INNERMUL8_MULX ;
3540    *cy_mulx = cy ;
3541}
3542
3543/* computes x/R == x (mod N) via Montgomery Reduction */
3544static int fp_montgomery_reduce_mulx(fp_int *a, fp_int *m, fp_digit mp, int ct)
3545{
3546   WC_DECLARE_VAR(c, fp_digit, FP_SIZE+1, 0);
3547   fp_digit *_c, *tmpm, mu = 0;
3548   int      oldused, x, y, pa;
3549
3550   /* bail if too large */
3551   if (m->used > (FP_SIZE/2)) {
3552      (void)mu;                     /* shut up compiler */
3553      return FP_VAL;
3554   }
3555
3556#ifdef TFM_SMALL_MONT_SET
3557   if (m->used <= 16) {
3558      return fp_montgomery_reduce_small(a, m, mp);
3559   }
3560#endif
3561
3562   /* only allocate space for what's needed for window plus res */
3563   WC_ALLOC_VAR_EX(c, fp_digit, (FP_SIZE+1), NULL, DYNAMIC_TYPE_BIGINT,
3564       return FP_MEM);
3565
3566   /* now zero the buff */
3567   XMEMSET(c, 0, sizeof(fp_digit)*(FP_SIZE + 1));
3568   pa = m->used;
3569
3570   /* copy the input */
3571#ifdef TFM_TIMING_RESISTANT
3572   if (a->used <= m->used) {
3573      oldused = m->used;
3574   }
3575   else {
3576      oldused = m->used * 2;
3577   }
3578#else
3579   oldused = a->used;
3580#endif
3581   for (x = 0; x < oldused; x++) {
3582       c[x] = a->dp[x];
3583   }
3584   MONT_START;
3585
3586   for (x = 0; x < pa; x++) {
3587       fp_digit cy = 0;
3588       /* get Mu for this round */
3589       LOOP_START;
3590       _c   = c + x;
3591       tmpm = m->dp;
3592       y = 0;
3593        for (; y < (pa & ~7); y += 8) {
3594              innermul8_mulx(_c, &cy, tmpm, mu) ;
3595              _c   += 8;
3596              tmpm += 8;
3597           }
3598       for (; y < pa; y++) {
3599          INNERMUL;
3600          ++_c;
3601       }
3602       LOOP_END;
3603       while (cy) {
3604           PROPCARRY;
3605           ++_c;
3606       }
3607  }
3608
3609  /* now copy out */
3610  _c   = c + pa;
3611  tmpm = a->dp;
3612  for (x = 0; x < pa+1; x++) {
3613     *tmpm++ = *_c++;
3614  }
3615
3616  /* zero any excess digits on the destination that we didn't write to */
3617  for (; x < oldused; x++) {
3618     *tmpm++ = 0;
3619  }
3620
3621  MONT_FINI;
3622
3623  a->used = pa+1;
3624  fp_clamp(a);
3625
3626#ifndef WOLFSSL_MONT_RED_CT
3627  /* if A >= m then A = A - m */
3628  if (fp_cmp_mag (a, m) != FP_LT) {
3629    s_fp_sub (a, m, a);
3630  }
3631  (void)ct;
3632#else
3633  if (ct) {
3634    fp_submod_ct(a, m, m, a);
3635  }
3636  else if (fp_cmp_mag (a, m) != FP_LT) {
3637    s_fp_sub (a, m, a);
3638  }
3639#endif
3640
3641  WC_FREE_VAR_EX(c, NULL, DYNAMIC_TYPE_BIGINT);
3642  return FP_OKAY;
3643}
3644#endif
3645
3646/* computes x/R == x (mod N) via Montgomery Reduction */
3647int fp_montgomery_reduce_ex(fp_int *a, fp_int *m, fp_digit mp, int ct)
3648{
3649   WC_DECLARE_VAR(c, fp_digit, FP_SIZE+1, 0);
3650   fp_digit *_c, *tmpm, mu = 0;
3651   int      oldused, x, y, pa, err = 0;
3652
3653   IF_HAVE_INTEL_MULX(err=fp_montgomery_reduce_mulx(a, m, mp, ct), return err) ;
3654   (void)err;
3655
3656   /* bail if too large */
3657   if (m->used > (FP_SIZE/2)) {
3658      (void)mu;                     /* shut up compiler */
3659      return FP_VAL;
3660   }
3661
3662#ifdef TFM_SMALL_MONT_SET
3663   if (m->used <= 16) {
3664      return fp_montgomery_reduce_small(a, m, mp);
3665   }
3666#endif
3667
3668   /* only allocate space for what's needed for window plus res */
3669   WC_ALLOC_VAR_EX(c, fp_digit, (FP_SIZE+1), NULL, DYNAMIC_TYPE_BIGINT,
3670       return FP_MEM);
3671
3672   /* now zero the buff */
3673   XMEMSET(c, 0, sizeof(fp_digit)*(FP_SIZE + 1));
3674   pa = m->used;
3675
3676   /* copy the input */
3677#ifdef TFM_TIMING_RESISTANT
3678   if (a->used <= m->used) {
3679      oldused = m->used;
3680   }
3681   else {
3682      oldused = m->used * 2;
3683   }
3684#else
3685   oldused = a->used;
3686#endif
3687   for (x = 0; x < oldused; x++) {
3688       c[x] = a->dp[x];
3689   }
3690   MONT_START;
3691
3692   for (x = 0; x < pa; x++) {
3693       fp_digit cy = 0;
3694       /* get Mu for this round */
3695       LOOP_START;
3696       _c   = c + x;
3697       tmpm = m->dp;
3698       y = 0;
3699#if defined(INNERMUL8)
3700        for (; y < (pa & ~7); y += 8) {
3701              INNERMUL8 ;
3702              _c   += 8;
3703              tmpm += 8;
3704           }
3705#endif
3706       for (; y < pa; y++) {
3707          INNERMUL;
3708          ++_c;
3709       }
3710       LOOP_END;
3711       while (cy) { /* //NOLINT(bugprone-infinite-loop) */ /* PROPCARRY is an asm macro */
3712           PROPCARRY;
3713           ++_c;
3714       }
3715  }
3716
3717  /* now copy out */
3718  _c   = c + pa;
3719  tmpm = a->dp;
3720  for (x = 0; x < pa+1; x++) {
3721     *tmpm++ = *_c++;
3722  }
3723
3724  /* zero any excess digits on the destination that we didn't write to */
3725  for (; x < oldused; x++) {
3726     *tmpm++ = 0;
3727  }
3728
3729  MONT_FINI;
3730
3731  a->used = pa+1;
3732  fp_clamp(a);
3733
3734#ifndef WOLFSSL_MONT_RED_CT
3735  /* if A >= m then A = A - m */
3736  if (fp_cmp_mag (a, m) != FP_LT) {
3737    s_fp_sub (a, m, a);
3738  }
3739  (void)ct;
3740#else
3741  if (ct) {
3742    fp_submod_ct(a, m, m, a);
3743  }
3744  else if (fp_cmp_mag (a, m) != FP_LT) {
3745    s_fp_sub (a, m, a);
3746  }
3747#endif
3748
3749  WC_FREE_VAR_EX(c, NULL, DYNAMIC_TYPE_BIGINT);
3750  return FP_OKAY;
3751}
3752
3753int fp_montgomery_reduce(fp_int *a, fp_int *m, fp_digit mp)
3754{
3755  return fp_montgomery_reduce_ex(a, m, mp, 1);
3756}
3757
3758int fp_read_unsigned_bin(fp_int *a, const unsigned char *b, int c)
3759{
3760#if defined(ALT_ECC_SIZE) || defined(HAVE_WOLF_BIGINT)
3761  const word32 maxC = (a->size * sizeof(fp_digit));
3762#else
3763  const word32 maxC = (FP_SIZE * sizeof(fp_digit));
3764#endif
3765
3766  /* zero the int */
3767  fp_zero (a);
3768
3769  if (c < 0) {
3770      return FP_VAL;
3771  }
3772
3773  if (c == 0) {
3774      return FP_OKAY;
3775  }
3776
3777  /* if input b excess max, then truncate */
3778  if ((word32)c > maxC) {
3779     int excess = (c - maxC);
3780     c -= excess;
3781     b += excess;
3782  }
3783
3784/* Not both endian simultaneously */
3785#if defined(LITTLE_ENDIAN_ORDER) && defined(BIG_ENDIAN_ORDER)
3786#error Both LITTLE_ENDIAN_ORDER and BIG_ENDIAN_ORDER defined.
3787#endif
3788
3789#if (defined(LITTLE_ENDIAN_ORDER) || defined(BIG_ENDIAN_ORDER)) && \
3790    (defined(FP_32BIT) || defined(FP_64BIT))
3791#ifdef FP_32BIT
3792  /* If we know the endianness of this architecture, and we're using
3793     32-bit fp_digits, we can optimize this */
3794  {
3795     unsigned char *pd = (unsigned char *)a->dp;
3796
3797     a->used = (c + sizeof(fp_digit) - 1)/sizeof(fp_digit);
3798#ifdef BIG_ENDIAN_ORDER
3799     {
3800       /* Use Duff's device to unroll the loop. */
3801       int idx = (c - 1) & ~3;
3802       switch (c % 4) {
3803       case 0:    do { pd[idx+0] = *b++; FALL_THROUGH;
3804       case 3:         pd[idx+1] = *b++; FALL_THROUGH;
3805       case 2:         pd[idx+2] = *b++; FALL_THROUGH;
3806       case 1:         pd[idx+3] = *b++;
3807                     idx -= 4;
3808                 } while ((c -= 4) > 0);
3809       }
3810     }
3811#else
3812     /* read the bytes in one at a time. */
3813     for (c -= 1; c >= 0; c -= 1) {
3814       pd[c] = *b++;
3815     }
3816#endif
3817  }
3818#elif defined(FP_64BIT)
3819  /* If we know the endianness of this architecture, and we're using
3820     64-bit fp_digits, we can optimize this */
3821  {
3822     unsigned char *pd = (unsigned char *)a->dp;
3823
3824     a->used = (c + sizeof(fp_digit) - 1)/sizeof(fp_digit);
3825#ifdef BIG_ENDIAN_ORDER
3826     {
3827       /* Use Duff's device to unroll the loop. */
3828       int idx = (c - 1) & ~7;
3829       switch (c % 8) {
3830       case 0:    do { pd[idx+0] = *b++; FALL_THROUGH;
3831       case 7:         pd[idx+1] = *b++; FALL_THROUGH;
3832       case 6:         pd[idx+2] = *b++; FALL_THROUGH;
3833       case 5:         pd[idx+3] = *b++; FALL_THROUGH;
3834       case 4:         pd[idx+4] = *b++; FALL_THROUGH;
3835       case 3:         pd[idx+5] = *b++; FALL_THROUGH;
3836       case 2:         pd[idx+6] = *b++; FALL_THROUGH;
3837       case 1:         pd[idx+7] = *b++;
3838                     idx -= 8;
3839                 } while ((c -= 8) > 0);
3840       }
3841     }
3842#else
3843     /* read the bytes in one at a time. */
3844     for (c -= 1; c >= 0; c -= 1) {
3845       pd[c] = *b++;
3846     }
3847#endif
3848  }
3849#endif
3850#else
3851  /* read the bytes in one at a time - unknown number of bits in digit */
3852  for (; c > 0; c--) {
3853     int err = fp_mul_2d (a, 8, a);
3854     if (err != FP_OKAY) {
3855         return err;
3856     }
3857     a->dp[0] |= *b++;
3858
3859     if (a->used == 0) {
3860         a->used = 1;
3861     }
3862  }
3863#endif
3864  fp_clamp (a);
3865
3866  return FP_OKAY;
3867}
3868
3869int fp_to_unsigned_bin_at_pos(int x, fp_int *t, unsigned char *b)
3870{
3871#if DIGIT_BIT == 64 || DIGIT_BIT == 32
3872   int i;
3873   int j = 0;
3874   fp_digit n;
3875
3876   for (i = 0; i < t->used-1; ) {
3877       b[x++] = (unsigned char)(t->dp[i] >> j);
3878       j += 8;
3879       i += j == DIGIT_BIT;
3880       j &= DIGIT_BIT - 1;
3881   }
3882   n = t->dp[i];
3883   while (n != 0) {
3884       b[x++] = (unsigned char)n;
3885       n >>= 8;
3886   }
3887   return x;
3888#else
3889   while (fp_iszero (t) == FP_NO) {
3890      b[x++] = (unsigned char) (t->dp[0] & 255);
3891      fp_div_2d (t, 8, t, NULL);
3892  }
3893  return x;
3894#endif
3895}
3896
3897int fp_to_unsigned_bin(const fp_int *a, unsigned char *b)
3898{
3899  int     x;
3900   WC_DECLARE_VAR(t, fp_int, 1, 0);
3901
3902   WC_ALLOC_VAR_EX(t, fp_int, 1, NULL, DYNAMIC_TYPE_BIGINT, return FP_MEM);
3903
3904  fp_init_copy(t, a);
3905
3906  x = fp_to_unsigned_bin_at_pos(0, t, b);
3907  mp_reverse (b, x);
3908
3909  WC_FREE_VAR_EX(t, NULL, DYNAMIC_TYPE_BIGINT);
3910  return FP_OKAY;
3911}
3912
3913int fp_to_unsigned_bin_len_ct(fp_int *a, unsigned char *out, int outSz)
3914{
3915  int err = MP_OKAY;
3916
3917  /* Validate parameters. */
3918  if ((a == NULL) || (out == NULL) || (outSz < 0)) {
3919    err = MP_VAL;
3920  }
3921
3922#if DIGIT_BIT > 8
3923  if (err == MP_OKAY) {
3924    /* Start at the end of the buffer - least significant byte. */
3925    int j;
3926    unsigned int i;
3927    fp_digit mask = (fp_digit)-1;
3928    fp_digit d;
3929
3930    /* Put each digit in. */
3931    i = 0;
3932    for (j = outSz - 1; j >= 0; ) {
3933      unsigned int b;
3934      d = a->dp[i];
3935      /* Place each byte of a digit into the buffer. */
3936      for (b = 0; (j >= 0) && (b < (DIGIT_BIT / 8)); b++) {
3937        out[j--] = (byte)(d & mask);
3938        d >>= 8;
3939      }
3940      mask &= (fp_digit)0 - (i < (unsigned int)a->used - 1);
3941      i += (unsigned int)(1 & mask);
3942    }
3943  }
3944#else
3945  if ((err == MP_OKAY) && ((unsigned int)outSz < a->used)) {
3946    err = MP_VAL;
3947  }
3948  if (err == MP_OKAY) {
3949    unsigned int i;
3950    int j;
3951    fp_digit mask = (fp_digit)-1;
3952
3953    i = 0;
3954    for (j = outSz - 1; j >= 0; j--) {
3955      out[j] = a->dp[i] & mask;
3956      mask &= (fp_digit)0 - (i < (unsigned int)a->used - 1);
3957      i += (unsigned int)(1 & mask);
3958    }
3959  }
3960#endif
3961
3962  return err;
3963}
3964
3965int fp_to_unsigned_bin_len(fp_int *a, unsigned char *b, int c)
3966{
3967#if DIGIT_BIT == 64 || DIGIT_BIT == 32 || DIGIT_BIT == 16
3968  int i = 0;
3969  int j = 0;
3970  int x;
3971
3972  for (x=c-1; x >= 0 && i < a->used; x--) {
3973     b[x] = (unsigned char)(a->dp[i] >> j);
3974     j += 8;
3975     i += j == DIGIT_BIT;
3976     j &= DIGIT_BIT - 1;
3977  }
3978  for (; x >= 0; x--) {
3979     b[x] = 0;
3980  }
3981  if (i < a->used - 1) {
3982      return FP_VAL;
3983  }
3984  if ((i == a->used - 1) && ((a->dp[i] >> j) != 0)) {
3985      return FP_VAL;
3986  }
3987
3988  return FP_OKAY;
3989#else
3990  int     x;
3991   WC_DECLARE_VAR(t, fp_int, 1, 0);
3992
3993   WC_ALLOC_VAR_EX(t, fp_int, 1, NULL, DYNAMIC_TYPE_BIGINT, return FP_MEM);
3994
3995  fp_init_copy(t, a);
3996
3997  for (x = 0; x < c; x++) {
3998      b[x] = (unsigned char) (t->dp[0] & 255);
3999      fp_div_2d (t, 8, t, NULL);
4000  }
4001  mp_reverse (b, x);
4002
4003  WC_FREE_VAR_EX(t, NULL, DYNAMIC_TYPE_BIGINT);
4004  if (!fp_iszero(t)) {
4005      return FP_VAL;
4006  }
4007  return FP_OKAY;
4008#endif
4009}
4010
4011int fp_unsigned_bin_size(const fp_int *a)
4012{
4013  int     size = fp_count_bits (a);
4014  return (size / 8 + ((size & 7) != 0 ? 1 : 0));
4015}
4016
4017void fp_set(fp_int *a, fp_digit b)
4018{
4019   fp_zero(a);
4020   a->dp[0] = b;
4021   a->used  = a->dp[0] ? 1 : 0;
4022}
4023
4024
4025#ifndef MP_SET_CHUNK_BITS
4026    #define MP_SET_CHUNK_BITS 4
4027#endif
4028int fp_set_int(fp_int *a, unsigned long b)
4029{
4030  /* use direct fp_set if b is less than fp_digit max
4031   * If input max value of b down shift by 1 less than full range
4032   * fp_digit, then condition is always true. */
4033#if ((ULONG_MAX >> (DIGIT_BIT-1)) > 0)
4034  int x;
4035  if (b < FP_DIGIT_MAX)
4036  {
4037    fp_set (a, (fp_digit)b);
4038    return FP_OKAY;
4039  }
4040
4041  fp_zero (a);
4042
4043  /* set chunk bits at a time */
4044  for (x = 0; x < (int)(sizeof(b) * 8) / MP_SET_CHUNK_BITS; x++) {
4045    int err = fp_mul_2d (a, MP_SET_CHUNK_BITS, a);
4046    if (err != FP_OKAY)
4047        return err;
4048
4049    /* OR in the top bits of the source */
4050    a->dp[0] |= (b >> ((sizeof(b) * 8) - MP_SET_CHUNK_BITS)) &
4051                                  ((1 << MP_SET_CHUNK_BITS) - 1);
4052
4053    /* shift the source up to the next chunk bits */
4054    b <<= MP_SET_CHUNK_BITS;
4055
4056    /* ensure that digits are not clamped off */
4057    a->used += 1;
4058  }
4059
4060  /* clamp digits */
4061  fp_clamp(a);
4062#else
4063  fp_set (a, (fp_digit)b);
4064#endif
4065
4066  return FP_OKAY;
4067}
4068
4069/* check if a bit is set */
4070int fp_is_bit_set (fp_int *a, fp_digit b)
4071{
4072    fp_digit i;
4073
4074    if (b > FP_MAX_BITS)
4075        return FP_VAL;
4076
4077    i = b/DIGIT_BIT;
4078
4079    if ((fp_digit)a->used < i)
4080        return 0;
4081
4082    return (int)((a->dp[i] >> b%DIGIT_BIT) & (fp_digit)1);
4083}
4084
4085/* set the b bit of a */
4086int fp_set_bit (fp_int * a, fp_digit b)
4087{
4088    fp_digit i;
4089
4090    if (b > FP_MAX_BITS)
4091        return FP_VAL;
4092
4093    i = b/DIGIT_BIT;
4094
4095    /* set the used count of where the bit will go if required */
4096    if (a->used < (int)(i+1))
4097        a->used = (int)(i+1);
4098
4099    /* put the single bit in its place */
4100    a->dp[i] |= ((fp_digit)1) << (b % DIGIT_BIT);
4101
4102    return MP_OKAY;
4103}
4104
4105int fp_count_bits (const fp_int * a)
4106{
4107  int     r;
4108  fp_digit q;
4109
4110  /* shortcut */
4111  if (a->used == 0) {
4112    return 0;
4113  }
4114
4115  /* get number of digits and add that */
4116  r = (a->used - 1) * DIGIT_BIT;
4117
4118  /* take the last digit and count the bits in it */
4119  q = a->dp[a->used - 1];
4120  while (q > ((fp_digit) 0)) {
4121    ++r;
4122    q >>= ((fp_digit) 1);
4123  }
4124
4125  return r;
4126}
4127
4128int fp_leading_bit(fp_int *a)
4129{
4130    int bit = 0;
4131
4132    if (a->used != 0) {
4133        fp_digit q = a->dp[a->used - 1];
4134        int qSz = sizeof(fp_digit);
4135
4136        while (qSz > 0) {
4137            if ((unsigned char)q != 0)
4138                bit = (q & 0x80) != 0;
4139            q >>= 8;
4140            qSz--;
4141        }
4142    }
4143
4144    return bit;
4145}
4146
4147int fp_lshd(fp_int *a, int x)
4148{
4149    int y;
4150
4151    if (a->used + x > FP_SIZE) return FP_VAL;
4152
4153    y = a->used + x - 1;
4154
4155    /* store new size */
4156    a->used = y + 1;
4157
4158    /* move digits */
4159    for (; y >= x; y--) {
4160        a->dp[y] = a->dp[y-x];
4161    }
4162
4163    /* zero lower digits */
4164    for (; y >= 0; y--) {
4165        a->dp[y] = 0;
4166    }
4167
4168    /* clamp digits */
4169    fp_clamp(a);
4170    return FP_OKAY;
4171}
4172
4173
4174/* right shift by bit count */
4175void fp_rshb(fp_int *c, int x)
4176{
4177    fp_digit *tmpc, mask, shift;
4178    fp_digit r, rr;
4179    fp_digit D = x;
4180
4181    /* shifting by a negative number not supported, and shifting by
4182     * zero changes nothing.
4183     */
4184    if (x <= 0) return;
4185
4186    /* shift digits first if needed */
4187    if (x >= DIGIT_BIT) {
4188        fp_rshd(c, x / DIGIT_BIT);
4189        /* recalculate number of bits to shift */
4190        D = x % DIGIT_BIT;
4191        /* check if any more shifting needed */
4192        if (D == 0) return;
4193
4194    }
4195
4196    /* zero shifted is always zero */
4197    if (fp_iszero(c)) return;
4198
4199    /* mask */
4200    mask = (((fp_digit)1) << D) - 1;
4201
4202    /* shift for lsb */
4203    shift = DIGIT_BIT - D;
4204
4205    /* alias */
4206    tmpc = c->dp + (c->used - 1);
4207
4208    /* carry */
4209    r = 0;
4210    for (x = c->used - 1; x >= 0; x--) {
4211      /* get the lower  bits of this word in a temp */
4212      rr = *tmpc & mask;
4213
4214      /* shift the current word and mix in the carry bits from previous word */
4215      *tmpc = (*tmpc >> D) | (r << shift);
4216      --tmpc;
4217
4218      /* set the carry to the carry bits of the current word found above */
4219      r = rr;
4220    }
4221
4222    /* clamp digits */
4223    fp_clamp(c);
4224}
4225
4226
4227void fp_rshd(fp_int *a, int x)
4228{
4229  int y;
4230
4231  /* too many digits just zero and return */
4232  if (x >= a->used) {
4233     fp_zero(a);
4234     return;
4235  }
4236
4237   /* shift */
4238   for (y = 0; y < a->used - x; y++) {
4239      a->dp[y] = a->dp[y+x];
4240   }
4241
4242   /* zero rest */
4243   for (; y < a->used; y++) {
4244      a->dp[y] = 0;
4245   }
4246
4247   /* decrement count */
4248   a->used -= x;
4249   fp_clamp(a);
4250}
4251
4252
4253/* c = a - b */
4254int fp_sub_d(fp_int *a, fp_digit b, fp_int *c)
4255{
4256   WC_DECLARE_VAR(tmp, fp_int, 1, 0);
4257   int       err = FP_OKAY;
4258
4259   WC_ALLOC_VAR_EX(tmp, fp_int, 1, NULL, DYNAMIC_TYPE_BIGINT,
4260       return FP_MEM);
4261
4262   fp_init(tmp);
4263   fp_set(tmp, b);
4264#if defined(ALT_ECC_SIZE) || defined(HAVE_WOLF_BIGINT)
4265   if (c->size < FP_SIZE) {
4266     err = fp_sub(a, tmp, tmp);
4267     fp_copy(tmp, c);
4268   }
4269   else
4270#endif
4271   {
4272     err = fp_sub(a, tmp, c);
4273   }
4274
4275   WC_FREE_VAR_EX(tmp, NULL, DYNAMIC_TYPE_BIGINT);
4276   return err;
4277}
4278
4279
4280/* wolfSSL callers from normal lib */
4281
4282/* init a new mp_int */
4283int mp_init (mp_int * a)
4284{
4285  if (a)
4286    fp_init(a);
4287  return MP_OKAY;
4288}
4289
4290void fp_init(fp_int *a)
4291{
4292#if defined(ALT_ECC_SIZE) || defined(HAVE_WOLF_BIGINT)
4293    a->size = FP_SIZE;
4294#endif
4295#ifdef HAVE_WOLF_BIGINT
4296    wc_bigint_init(&a->raw);
4297#endif
4298    fp_zero(a);
4299}
4300
4301void fp_zero(fp_int *a)
4302{
4303    int size;
4304    a->used = 0;
4305    a->sign = FP_ZPOS;
4306#if defined(ALT_ECC_SIZE) || defined(HAVE_WOLF_BIGINT)
4307    size = a->size;
4308#else
4309    size = FP_SIZE;
4310#endif
4311    XMEMSET(a->dp, 0, size * sizeof(fp_digit));
4312}
4313
4314void fp_clear(fp_int *a)
4315{
4316#ifdef HAVE_FIPS
4317    fp_forcezero(a);
4318#else
4319    int size;
4320    a->used = 0;
4321    a->sign = FP_ZPOS;
4322#if defined(ALT_ECC_SIZE) || defined(HAVE_WOLF_BIGINT)
4323    size = a->size;
4324#else
4325    size = FP_SIZE;
4326#endif
4327    XMEMSET(a->dp, 0, size * sizeof(fp_digit));
4328    fp_free(a);
4329#endif
4330}
4331
4332void fp_forcezero (mp_int * a)
4333{
4334    int size;
4335
4336    if (a == NULL)
4337      return;
4338
4339    a->used = 0;
4340    a->sign = FP_ZPOS;
4341#if defined(ALT_ECC_SIZE) || defined(HAVE_WOLF_BIGINT)
4342    size = a->size;
4343#else
4344    size = FP_SIZE;
4345#endif
4346    ForceZero(a->dp, size * sizeof(fp_digit));
4347#ifdef HAVE_WOLF_BIGINT
4348    wc_bigint_zero(&a->raw);
4349#endif
4350    fp_free(a);
4351}
4352
4353void mp_forcezero (mp_int * a)
4354{
4355    fp_forcezero(a);
4356}
4357
4358void fp_free(fp_int* a)
4359{
4360#ifdef HAVE_WOLF_BIGINT
4361    wc_bigint_free(&a->raw);
4362#else
4363    (void)a;
4364#endif
4365}
4366
4367
4368/* clear one (frees)  */
4369void mp_clear (mp_int * a)
4370{
4371    if (a == NULL)
4372        return;
4373    fp_clear(a);
4374}
4375
4376void mp_free(mp_int* a)
4377{
4378    fp_free(a);
4379}
4380
4381/* handle up to 6 inits */
4382int mp_init_multi(mp_int* a, mp_int* b, mp_int* c, mp_int* d,
4383                  mp_int* e, mp_int* f)
4384{
4385    if (a)
4386        fp_init(a);
4387    if (b)
4388        fp_init(b);
4389    if (c)
4390        fp_init(c);
4391    if (d)
4392        fp_init(d);
4393    if (e)
4394        fp_init(e);
4395    if (f)
4396        fp_init(f);
4397
4398    return MP_OKAY;
4399}
4400
4401/* high level addition (handles signs) */
4402int mp_add (mp_int * a, mp_int * b, mp_int * c)
4403{
4404  return fp_add(a, b, c);
4405}
4406
4407/* high level subtraction (handles signs) */
4408int mp_sub (mp_int * a, mp_int * b, mp_int * c)
4409{
4410  return fp_sub(a, b, c);
4411}
4412
4413/* high level multiplication (handles sign) */
4414#if defined(FREESCALE_LTC_TFM)
4415int wolfcrypt_mp_mul(mp_int * a, mp_int * b, mp_int * c)
4416#else
4417int mp_mul (mp_int * a, mp_int * b, mp_int * c)
4418#endif
4419{
4420  return fp_mul(a, b, c);
4421}
4422
4423int mp_mul_d (mp_int * a, mp_digit b, mp_int * c)
4424{
4425  return fp_mul_d(a, b, c);
4426}
4427
4428/* d = a * b (mod c) */
4429#if defined(FREESCALE_LTC_TFM)
4430int wolfcrypt_mp_mulmod (mp_int * a, mp_int * b, mp_int * c, mp_int * d)
4431#else
4432int mp_mulmod (mp_int * a, mp_int * b, mp_int * c, mp_int * d)
4433#endif
4434{
4435   int ret = MP_OKAY;
4436#ifdef WOLFSSL_ESP32_CRYPT_RSA_PRI_MULMOD
4437   ret = esp_mp_mulmod(a, b, c, d);
4438   switch (ret) {
4439      case MP_OKAY:
4440         /* successfully computed in HW */
4441         break;
4442
4443      case WC_NO_ERR_TRACE(WC_HW_WAIT_E): /* MP_HW_BUSY math HW busy, fall back */
4444      case MP_HW_FALLBACK:    /* forced fallback from HW to SW */
4445      case MP_HW_VALIDATION_ACTIVE: /* use SW to compare to HW */
4446         /* use software calc */
4447         ret = fp_mulmod(a, b, c, d);
4448         break;
4449
4450      default:
4451         /* Once we've failed, exit without trying to continue.
4452          * We may have mangled operands: (e.g. Z = X * Z)
4453          * Future implementation may consider saving operands,
4454          * but hard errors should never actually occur. */
4455         break;
4456   }
4457#else /* no HW */
4458   ret = fp_mulmod(a, b, c, d);
4459#endif /* WOLFSSL_ESP32_CRYPT_RSA_PRI_MULMOD */
4460   return ret;
4461}
4462
4463/* d = a - b (mod c) */
4464int mp_submod(mp_int *a, mp_int *b, mp_int *c, mp_int *d)
4465{
4466  return fp_submod(a, b, c, d);
4467}
4468
4469/* d = a + b (mod c) */
4470int mp_addmod(mp_int *a, mp_int *b, mp_int *c, mp_int *d)
4471{
4472  return fp_addmod(a, b, c, d);
4473}
4474
4475/* d = a - b (mod c) - constant time (a < c and b < c) */
4476int mp_submod_ct(mp_int *a, mp_int *b, mp_int *c, mp_int *d)
4477{
4478  return fp_submod_ct(a, b, c, d);
4479}
4480
4481/* d = a + b (mod c) - constant time (a < c and b < c) */
4482int mp_addmod_ct(mp_int *a, mp_int *b, mp_int *c, mp_int *d)
4483{
4484  return fp_addmod_ct(a, b, c, d);
4485}
4486
4487/* c = a mod b, 0 <= c < b */
4488#if defined(FREESCALE_LTC_TFM)
4489int wolfcrypt_mp_mod (mp_int * a, mp_int * b, mp_int * c)
4490#else
4491int mp_mod (mp_int * a, mp_int * b, mp_int * c)
4492#endif
4493{
4494  return fp_mod (a, b, c);
4495}
4496
4497/* hac 14.61, pp608 */
4498#if defined(FREESCALE_LTC_TFM)
4499int wolfcrypt_mp_invmod (mp_int * a, mp_int * b, mp_int * c)
4500#else
4501int mp_invmod (mp_int * a, mp_int * b, mp_int * c)
4502#endif
4503{
4504  return fp_invmod(a, b, c);
4505}
4506
4507/* hac 14.61, pp608 */
4508int mp_invmod_mont_ct (mp_int * a, mp_int * b, mp_int * c, mp_digit mp)
4509{
4510  return fp_invmod_mont_ct(a, b, c, mp);
4511}
4512
4513/* this is a shell function that calls either the normal or Montgomery
4514 * exptmod functions.  Originally the call to the montgomery code was
4515 * embedded in the normal function but that wasted a lot of stack space
4516 * for nothing (since 99% of the time the Montgomery code would be called)
4517 */
4518#if defined(FREESCALE_LTC_TFM)
4519int wolfcrypt_mp_exptmod (mp_int * G, mp_int * X, mp_int * P, mp_int * Y)
4520#else
4521int mp_exptmod (mp_int * G, mp_int * X, mp_int * P, mp_int * Y)
4522#endif
4523{
4524  return fp_exptmod(G, X, P, Y);
4525}
4526
4527int mp_exptmod_ex (mp_int * G, mp_int * X, int digits, mp_int * P, mp_int * Y)
4528{
4529  return fp_exptmod_ex(G, X, digits, P, Y);
4530}
4531
4532#if defined(FREESCALE_LTC_TFM)
4533int wolfcrypt_mp_exptmod_nct (mp_int * G, mp_int * X, mp_int * P, mp_int * Y)
4534#else
4535int mp_exptmod_nct (mp_int * G, mp_int * X, mp_int * P, mp_int * Y)
4536#endif
4537{
4538  return fp_exptmod_nct(G, X, P, Y);
4539}
4540
4541
4542/* compare two ints (signed)*/
4543int mp_cmp (const mp_int * a, const mp_int * b)
4544{
4545  return fp_cmp((mp_int *)a, (mp_int *)b);
4546}
4547
4548/* compare a digit */
4549int mp_cmp_d(mp_int * a, mp_digit b)
4550{
4551  return fp_cmp_d(a, b);
4552}
4553
4554/* get the size for an unsigned equivalent */
4555int mp_unsigned_bin_size (const mp_int * a)
4556{
4557  return fp_unsigned_bin_size(a);
4558}
4559
4560int mp_to_unsigned_bin_at_pos(int x, fp_int *t, unsigned char *b)
4561{
4562  return fp_to_unsigned_bin_at_pos(x, t, b);
4563}
4564
4565/* store in unsigned [big endian] format */
4566int mp_to_unsigned_bin(const mp_int * a, unsigned char *b)
4567{
4568  return fp_to_unsigned_bin(a,b);
4569}
4570
4571int mp_to_unsigned_bin_len_ct(mp_int * a, unsigned char *b, int c)
4572{
4573  return fp_to_unsigned_bin_len_ct(a, b, c);
4574}
4575
4576int mp_to_unsigned_bin_len(mp_int * a, unsigned char *b, int c)
4577{
4578  return fp_to_unsigned_bin_len(a, b, c);
4579}
4580/* reads a unsigned char array, assumes the msb is stored first [big endian] */
4581int mp_read_unsigned_bin (mp_int * a, const unsigned char *b, int c)
4582{
4583  return fp_read_unsigned_bin(a, b, c);
4584}
4585
4586
4587int mp_sub_d(fp_int *a, fp_digit b, fp_int *c)
4588{
4589  return fp_sub_d(a, b, c);
4590}
4591
4592int mp_mul_2d(fp_int *a, int b, fp_int *c)
4593{
4594  return fp_mul_2d(a, b, c);
4595}
4596
4597int mp_2expt(fp_int* a, int b)
4598{
4599  fp_2expt(a, b);
4600  return MP_OKAY;
4601}
4602
4603int mp_div(fp_int * a, fp_int * b, fp_int * c, fp_int * d)
4604{
4605  return fp_div(a, b, c, d);
4606}
4607
4608int mp_div_2d(fp_int* a, int b, fp_int* c, fp_int* d)
4609{
4610  fp_div_2d(a, b, c, d);
4611  return MP_OKAY;
4612}
4613
4614int mp_mod_2d(fp_int* a, int b, fp_int* c)
4615{
4616  fp_mod_2d(a, b, c);
4617  return MP_OKAY;
4618}
4619
4620/* copy (src = a) to (dst = b) */
4621void fp_copy(const fp_int *a, fp_int *b)
4622{
4623    /* if source and destination are different */
4624    if (a != b) {
4625#if defined(ALT_ECC_SIZE) || defined(HAVE_WOLF_BIGINT)
4626        /* verify a will fit in b */
4627        if (b->size >= a->used) {
4628            int x, oldused;
4629            oldused = b->used;
4630            b->used = a->used;
4631            b->sign = a->sign;
4632
4633            XMEMCPY(b->dp, a->dp, a->used * sizeof(fp_digit));
4634
4635            /* zero any excess digits on the destination that we didn't write to */
4636            for (x = b->used; x >= 0 && x < oldused; x++) {
4637                b->dp[x] = 0;
4638            }
4639        }
4640        else {
4641            /* TODO: Handle error case */
4642        }
4643#else
4644        /* all dp's are same size, so do straight copy */
4645        b->used = a->used;
4646        b->sign = a->sign;
4647        XMEMCPY(b->dp, a->dp, FP_SIZE * sizeof(fp_digit));
4648#endif
4649    }
4650}
4651
4652int mp_init_copy(fp_int * a, const fp_int * b)
4653{
4654    fp_init_copy(a, b);
4655    return MP_OKAY;
4656}
4657
4658/* Copy (dst = a) from (src = b) */
4659void fp_init_copy(fp_int *a, const fp_int* b)
4660{
4661    if (a != b) {
4662        fp_init(a);
4663        /* Note reversed parameter order! */
4664        fp_copy(b, a); /* copy (src = b) to (dst = a) */
4665    }
4666}
4667
4668/* fast math wrappers */
4669int mp_copy(const fp_int* a, fp_int* b)
4670{
4671    fp_copy(a, b);
4672    return MP_OKAY;
4673}
4674
4675int mp_isodd(const mp_int* a)
4676{
4677    return fp_isodd(a);
4678}
4679
4680int mp_iszero(const mp_int* a)
4681{
4682    return fp_iszero(a);
4683}
4684
4685int mp_count_bits (const mp_int* a)
4686{
4687    return fp_count_bits(a);
4688}
4689
4690int mp_leading_bit (mp_int* a)
4691{
4692    return fp_leading_bit(a);
4693}
4694
4695void mp_rshb (mp_int* a, int x)
4696{
4697    fp_rshb(a, x);
4698}
4699
4700void mp_rshd (mp_int* a, int x)
4701{
4702    fp_rshd(a, x);
4703}
4704
4705int mp_set_int(mp_int *a, unsigned long b)
4706{
4707    return fp_set_int(a, b);
4708}
4709
4710int mp_is_bit_set (mp_int *a, mp_digit b)
4711{
4712    return fp_is_bit_set(a, b);
4713}
4714
4715int mp_set_bit(mp_int *a, mp_digit b)
4716{
4717    return fp_set_bit(a, b);
4718}
4719
4720#if defined(WOLFSSL_KEY_GEN) || defined (HAVE_ECC) || !defined(NO_DH) || \
4721    !defined(NO_DSA) || !defined(NO_RSA)
4722
4723/* c = a * a (mod b) */
4724int fp_sqrmod(fp_int *a, fp_int *b, fp_int *c)
4725{
4726  int err;
4727   WC_DECLARE_VAR(t, fp_int, 1, 0);
4728
4729   WC_ALLOC_VAR_EX(t, fp_int, 1, NULL, DYNAMIC_TYPE_BIGINT, return FP_MEM);
4730
4731  fp_init(t);
4732  err = fp_sqr(a, t);
4733  if (err == FP_OKAY) {
4734  #if defined(ALT_ECC_SIZE) || defined(HAVE_WOLF_BIGINT)
4735    if (c->size < FP_SIZE) {
4736      err = fp_mod(t, b, t);
4737      fp_copy(t, c);
4738    }
4739    else
4740  #endif
4741    {
4742      err = fp_mod(t, b, c);
4743    }
4744  }
4745
4746  WC_FREE_VAR_EX(t, NULL, DYNAMIC_TYPE_BIGINT);
4747  return err;
4748}
4749
4750/* fast math conversion */
4751int mp_sqrmod(mp_int *a, mp_int *b, mp_int *c)
4752{
4753    return fp_sqrmod(a, b, c);
4754}
4755
4756/* fast math conversion */
4757int mp_montgomery_calc_normalization(mp_int *a, mp_int *b)
4758{
4759    return fp_montgomery_calc_normalization(a, b);
4760}
4761
4762#endif /* WOLFSSL_KEY_GEN || HAVE_ECC */
4763
4764static int fp_cond_swap_ct_ex(mp_int* a, mp_int* b, int c, int m, mp_int* t)
4765{
4766    int i;
4767    mp_digit mask = (mp_digit)0 - m;
4768
4769    t->used = (a->used ^ b->used) & mask;
4770    for (i = 0; i < c; i++) {
4771        t->dp[i] = (a->dp[i] ^ b->dp[i]) & mask;
4772    }
4773    a->used ^= t->used;
4774    for (i = 0; i < c; i++) {
4775        a->dp[i] ^= t->dp[i];
4776    }
4777    b->used ^= t->used;
4778    for (i = 0; i < c; i++) {
4779        b->dp[i] ^= t->dp[i];
4780    }
4781
4782    return FP_OKAY;
4783}
4784
4785
4786static int fp_cond_swap_ct(mp_int* a, mp_int* b, int c, int m)
4787{
4788    WC_DECLARE_VAR(t, fp_int, 1, 0);
4789
4790   WC_ALLOC_VAR_EX(t, fp_int, 1, NULL, DYNAMIC_TYPE_BIGINT, return FP_MEM);
4791
4792   fp_cond_swap_ct_ex(a, b, c, m, t);
4793
4794    WC_FREE_VAR_EX(t, NULL, DYNAMIC_TYPE_BIGINT);
4795    return FP_OKAY;
4796}
4797
4798
4799#if defined(WC_MP_TO_RADIX) || !defined(NO_DH) || !defined(NO_DSA) || \
4800    !defined(NO_RSA)
4801
4802#ifdef WOLFSSL_KEY_GEN
4803/* swap the elements of two integers, for cases where you can't simply swap the
4804 * mp_int pointers around
4805 */
4806static int fp_exch (fp_int * a, fp_int * b)
4807{
4808    WC_DECLARE_VAR(t, fp_int, 1, 0);
4809
4810   WC_ALLOC_VAR_EX(t, fp_int, 1, NULL, DYNAMIC_TYPE_BIGINT, return FP_MEM);
4811
4812    *t = *a;
4813    *a = *b;
4814    *b = *t;
4815
4816    WC_FREE_VAR_EX(t, NULL, DYNAMIC_TYPE_BIGINT);
4817    return FP_OKAY;
4818}
4819#endif
4820
4821static const int lnz[16] = {
4822   4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0
4823};
4824
4825/* Counts the number of lsbs which are zero before the first zero bit */
4826int fp_cnt_lsb(fp_int *a)
4827{
4828   int x;
4829   fp_digit q, qq;
4830
4831   /* easy out */
4832   if (fp_iszero(a) == FP_YES) {
4833      return 0;
4834   }
4835
4836   /* scan lower digits until non-zero */
4837   for (x = 0; x < a->used && a->dp[x] == 0; x++) {}
4838   q = a->dp[x];
4839   x *= DIGIT_BIT;
4840
4841   /* now scan this digit until a 1 is found */
4842   if ((q & 1) == 0) {
4843      do {
4844         qq  = q & 15;
4845         x  += lnz[qq];
4846         q >>= 4;
4847      } while (qq == 0);
4848   }
4849   return x;
4850}
4851
4852
4853static int s_is_power_of_two(fp_digit b, int *p)
4854{
4855   int x;
4856
4857   /* fast return if no power of two */
4858   if ((b==0) || (b & (b-1))) {
4859      return FP_NO;
4860   }
4861
4862   for (x = 0; x < DIGIT_BIT; x++) {
4863      if (b == (((fp_digit)1)<<x)) {
4864         *p = x;
4865         return FP_YES;
4866      }
4867   }
4868   return FP_NO;
4869}
4870
4871/* a/b => cb + d == a */
4872static int fp_div_d(fp_int *a, fp_digit b, fp_int *c, fp_digit *d)
4873{
4874  WC_DECLARE_VAR(q, fp_int, 1, 0);
4875  fp_word  w;
4876  fp_digit t;
4877  int      ix;
4878
4879  /* cannot divide by zero */
4880  if (b == 0) {
4881     return FP_VAL;
4882  }
4883
4884  /* quick outs */
4885  if (b == 1 || fp_iszero(a) == FP_YES) {
4886     if (d != NULL) {
4887        *d = 0;
4888     }
4889     if (c != NULL) {
4890        fp_copy(a, c);
4891     }
4892     return FP_OKAY;
4893  }
4894
4895  /* power of two ? */
4896  if (s_is_power_of_two(b, &ix) == FP_YES) {
4897     if (d != NULL) {
4898        *d = a->dp[0] & ((((fp_digit)1)<<ix) - 1);
4899     }
4900     if (c != NULL) {
4901        fp_div_2d(a, ix, c, NULL);
4902     }
4903     return FP_OKAY;
4904  }
4905
4906  WC_ALLOC_VAR_EX(q, fp_int, 1, NULL, DYNAMIC_TYPE_BIGINT, return FP_MEM);
4907
4908  fp_init(q);
4909
4910  if (c != NULL) {
4911    q->used = a->used;
4912    q->sign = a->sign;
4913  }
4914
4915  w = 0;
4916  for (ix = a->used - 1; ix >= 0; ix--) {
4917     w = (w << ((fp_word)DIGIT_BIT)) | ((fp_word)a->dp[ix]);
4918
4919     if (w >= b) {
4920#ifdef WOLFSSL_LINUXKM
4921        t = (fp_digit)w;
4922        /* Linux kernel macro for in-place 64 bit integer division. */
4923        do_div(t, b);
4924#else
4925        t = (fp_digit)(w / b);
4926#endif
4927        w -= ((fp_word)t) * ((fp_word)b);
4928      } else {
4929        t = 0;
4930      }
4931      if (c != NULL)
4932        q->dp[ix] = (fp_digit)t;
4933  }
4934
4935  if (d != NULL) {
4936     *d = (fp_digit)w;
4937  }
4938
4939  if (c != NULL) {
4940     fp_clamp(q);
4941     fp_copy(q, c);
4942  }
4943
4944  WC_FREE_VAR_EX(q, NULL, DYNAMIC_TYPE_BIGINT);
4945  return FP_OKAY;
4946}
4947
4948
4949/* c = a mod b, 0 <= c < b  */
4950static int fp_mod_d(fp_int *a, fp_digit b, fp_digit *c)
4951{
4952   return fp_div_d(a, b, NULL, c);
4953}
4954
4955int mp_mod_d(fp_int *a, fp_digit b, fp_digit *c)
4956{
4957   return fp_mod_d(a, b, c);
4958}
4959
4960#endif /* WC_MP_TO_RADIX || !NO_DH || !NO_DSA || !NO_RSA */
4961
4962
4963#if !defined(NO_DH) || !defined(NO_DSA) || !defined(NO_RSA) || \
4964    defined(WOLFSSL_KEY_GEN)
4965
4966static int  fp_isprime_ex(fp_int *a, int t, int* result);
4967
4968#if defined(FREESCALE_LTC_TFM)
4969int wolfcrypt_mp_prime_is_prime(mp_int* a, int t, int* result)
4970#else
4971int mp_prime_is_prime(mp_int* a, int t, int* result)
4972#endif
4973{
4974    return fp_isprime_ex(a, t, result);
4975}
4976
4977/* Miller-Rabin test of "a" to the base of "b" as described in
4978 * HAC pp. 139 Algorithm 4.24
4979 *
4980 * Sets result to 0 if definitely composite or 1 if probably prime.
4981 * Randomly the chance of error is no more than 1/4 and often
4982 * very much lower.
4983 */
4984static int fp_prime_miller_rabin_ex(fp_int * a, fp_int * b, int *result,
4985  fp_int *n1, fp_int *y, fp_int *r)
4986{
4987  int s, j;
4988  int err;
4989
4990  /* default */
4991  *result = FP_NO;
4992
4993  /* ensure b > 1 */
4994  if (fp_cmp_d(b, 1) != FP_GT) {
4995     return FP_OKAY;
4996  }
4997
4998  /* get n1 = a - 1 */
4999  fp_copy(a, n1);
5000  err = fp_sub_d(n1, 1, n1);
5001  if (err != FP_OKAY) {
5002     return err;
5003  }
5004
5005  /* set 2**s * r = n1 */
5006  fp_copy(n1, r);
5007
5008  /* count the number of least significant bits
5009   * which are zero
5010   */
5011  s = fp_cnt_lsb(r);
5012
5013  /* now divide n - 1 by 2**s */
5014  fp_div_2d (r, s, r, NULL);
5015
5016  /* compute y = b**r mod a */
5017  fp_zero(y);
5018#if (defined(WOLFSSL_HAVE_SP_RSA) && !defined(WOLFSSL_RSA_PUBLIC_ONLY)) || \
5019                                                     defined(WOLFSSL_HAVE_SP_DH)
5020#ifndef WOLFSSL_SP_NO_2048
5021  if (fp_count_bits(a) == 1024 && fp_isodd(a))
5022      err = sp_ModExp_1024(b, r, a, y);
5023  else if (fp_count_bits(a) == 2048 && fp_isodd(a))
5024      err = sp_ModExp_2048(b, r, a, y);
5025  else
5026#endif
5027#ifndef WOLFSSL_SP_NO_3072
5028  if (fp_count_bits(a) == 1536 && fp_isodd(a))
5029      err = sp_ModExp_1536(b, r, a, y);
5030  else if (fp_count_bits(a) == 3072 && fp_isodd(a))
5031      err = sp_ModExp_3072(b, r, a, y);
5032  else
5033#endif
5034#ifdef WOLFSSL_SP_4096
5035  if (fp_count_bits(a) == 4096 && fp_isodd(a))
5036      err = sp_ModExp_4096(b, r, a, y);
5037  else
5038#endif
5039#endif
5040      err = fp_exptmod(b, r, a, y);
5041   if (err != FP_OKAY) {
5042       return err;
5043   }
5044
5045  /* if y != 1 and y != n1 do */
5046  if (fp_cmp_d (y, 1) != FP_EQ && fp_cmp (y, n1) != FP_EQ) {
5047    j = 1;
5048    /* while j <= s-1 and y != n1 */
5049    while ((j <= (s - 1)) && fp_cmp (y, n1) != FP_EQ) {
5050      err = fp_sqrmod (y, a, y);
5051      if (err != FP_OKAY)
5052         return err;
5053
5054      /* if y == 1 then composite */
5055      if (fp_cmp_d (y, 1) == FP_EQ) {
5056         return FP_OKAY;
5057      }
5058      ++j;
5059    }
5060
5061    /* if y != n1 then composite */
5062    if (fp_cmp (y, n1) != FP_EQ) {
5063       return FP_OKAY;
5064    }
5065  }
5066
5067  /* probably prime now */
5068  *result = FP_YES;
5069
5070  return FP_OKAY;
5071}
5072
5073static int fp_prime_miller_rabin(fp_int * a, fp_int * b, int *result)
5074{
5075  int err;
5076#ifndef WOLFSSL_SMALL_STACK
5077  fp_int  n1[1], y[1], r[1];
5078#else
5079  fp_int *n1, *y, *r;
5080#endif
5081
5082#ifdef WOLFSSL_SMALL_STACK
5083  n1 = (fp_int*)XMALLOC(sizeof(fp_int) * 3, NULL, DYNAMIC_TYPE_BIGINT);
5084  if (n1 == NULL) {
5085      return FP_MEM;
5086  }
5087  y = &n1[1]; r = &n1[2];
5088#endif
5089
5090  fp_init(n1);
5091  fp_init(y);
5092  fp_init(r);
5093
5094  err = fp_prime_miller_rabin_ex(a, b, result, n1, y, r);
5095
5096  fp_clear(n1);
5097  fp_clear(y);
5098  fp_clear(r);
5099
5100  WC_FREE_VAR_EX(n1, NULL, DYNAMIC_TYPE_BIGINT);
5101
5102  return err;
5103}
5104
5105
5106/* a few primes */
5107static const fp_digit primes[FP_PRIME_SIZE] = {
5108  0x0002, 0x0003, 0x0005, 0x0007, 0x000B, 0x000D, 0x0011, 0x0013,
5109  0x0017, 0x001D, 0x001F, 0x0025, 0x0029, 0x002B, 0x002F, 0x0035,
5110  0x003B, 0x003D, 0x0043, 0x0047, 0x0049, 0x004F, 0x0053, 0x0059,
5111  0x0061, 0x0065, 0x0067, 0x006B, 0x006D, 0x0071, 0x007F, 0x0083,
5112  0x0089, 0x008B, 0x0095, 0x0097, 0x009D, 0x00A3, 0x00A7, 0x00AD,
5113  0x00B3, 0x00B5, 0x00BF, 0x00C1, 0x00C5, 0x00C7, 0x00D3, 0x00DF,
5114  0x00E3, 0x00E5, 0x00E9, 0x00EF, 0x00F1, 0x00FB, 0x0101, 0x0107,
5115  0x010D, 0x010F, 0x0115, 0x0119, 0x011B, 0x0125, 0x0133, 0x0137,
5116
5117  0x0139, 0x013D, 0x014B, 0x0151, 0x015B, 0x015D, 0x0161, 0x0167,
5118  0x016F, 0x0175, 0x017B, 0x017F, 0x0185, 0x018D, 0x0191, 0x0199,
5119  0x01A3, 0x01A5, 0x01AF, 0x01B1, 0x01B7, 0x01BB, 0x01C1, 0x01C9,
5120  0x01CD, 0x01CF, 0x01D3, 0x01DF, 0x01E7, 0x01EB, 0x01F3, 0x01F7,
5121  0x01FD, 0x0209, 0x020B, 0x021D, 0x0223, 0x022D, 0x0233, 0x0239,
5122  0x023B, 0x0241, 0x024B, 0x0251, 0x0257, 0x0259, 0x025F, 0x0265,
5123  0x0269, 0x026B, 0x0277, 0x0281, 0x0283, 0x0287, 0x028D, 0x0293,
5124  0x0295, 0x02A1, 0x02A5, 0x02AB, 0x02B3, 0x02BD, 0x02C5, 0x02CF,
5125
5126  0x02D7, 0x02DD, 0x02E3, 0x02E7, 0x02EF, 0x02F5, 0x02F9, 0x0301,
5127  0x0305, 0x0313, 0x031D, 0x0329, 0x032B, 0x0335, 0x0337, 0x033B,
5128  0x033D, 0x0347, 0x0355, 0x0359, 0x035B, 0x035F, 0x036D, 0x0371,
5129  0x0373, 0x0377, 0x038B, 0x038F, 0x0397, 0x03A1, 0x03A9, 0x03AD,
5130  0x03B3, 0x03B9, 0x03C7, 0x03CB, 0x03D1, 0x03D7, 0x03DF, 0x03E5,
5131  0x03F1, 0x03F5, 0x03FB, 0x03FD, 0x0407, 0x0409, 0x040F, 0x0419,
5132  0x041B, 0x0425, 0x0427, 0x042D, 0x043F, 0x0443, 0x0445, 0x0449,
5133  0x044F, 0x0455, 0x045D, 0x0463, 0x0469, 0x047F, 0x0481, 0x048B,
5134
5135  0x0493, 0x049D, 0x04A3, 0x04A9, 0x04B1, 0x04BD, 0x04C1, 0x04C7,
5136  0x04CD, 0x04CF, 0x04D5, 0x04E1, 0x04EB, 0x04FD, 0x04FF, 0x0503,
5137  0x0509, 0x050B, 0x0511, 0x0515, 0x0517, 0x051B, 0x0527, 0x0529,
5138  0x052F, 0x0551, 0x0557, 0x055D, 0x0565, 0x0577, 0x0581, 0x058F,
5139  0x0593, 0x0595, 0x0599, 0x059F, 0x05A7, 0x05AB, 0x05AD, 0x05B3,
5140  0x05BF, 0x05C9, 0x05CB, 0x05CF, 0x05D1, 0x05D5, 0x05DB, 0x05E7,
5141  0x05F3, 0x05FB, 0x0607, 0x060D, 0x0611, 0x0617, 0x061F, 0x0623,
5142  0x062B, 0x062F, 0x063D, 0x0641, 0x0647, 0x0649, 0x064D, 0x0653
5143};
5144
5145int fp_isprime_ex(fp_int *a, int t, int* result)
5146{
5147   WC_DECLARE_VAR(b, fp_int, 1, 0);
5148   fp_digit d;
5149   int      r, res;
5150   int      err;
5151
5152   if (t <= 0 || t > FP_PRIME_SIZE) {
5153     *result = FP_NO;
5154     return FP_VAL;
5155   }
5156
5157   if (fp_isone(a)) {
5158       *result = FP_NO;
5159       return FP_OKAY;
5160   }
5161
5162   /* check against primes table */
5163   for (r = 0; r < FP_PRIME_SIZE; r++) {
5164       if (fp_cmp_d(a, primes[r]) == FP_EQ) {
5165           *result = FP_YES;
5166           return FP_OKAY;
5167       }
5168   }
5169
5170   /* do trial division */
5171   for (r = 0; r < FP_PRIME_SIZE; r++) {
5172       res = fp_mod_d(a, primes[r], &d);
5173       if (res != MP_OKAY || d == 0) {
5174           *result = FP_NO;
5175           return res;
5176       }
5177   }
5178
5179  WC_ALLOC_VAR_EX(b, fp_int, 1, NULL, DYNAMIC_TYPE_BIGINT, return FP_MEM);
5180   /* now do 't' miller rabins */
5181   fp_init(b);
5182   for (r = 0; r < t; r++) {
5183       fp_set(b, primes[r]);
5184       err = fp_prime_miller_rabin(a, b, &res);
5185       if ((err != FP_OKAY) || (res == FP_NO)) {
5186          *result = res;
5187          WC_FREE_VAR_EX(b, NULL, DYNAMIC_TYPE_BIGINT);
5188          return err;
5189       }
5190   }
5191   *result = FP_YES;
5192   WC_FREE_VAR_EX(b, NULL, DYNAMIC_TYPE_BIGINT);
5193   return FP_OKAY;
5194}
5195
5196
5197#if defined(FREESCALE_LTC_TFM)
5198int wolfcrypt_mp_prime_is_prime_ex(mp_int* a, int t, int* result, WC_RNG* rng)
5199#else
5200int mp_prime_is_prime_ex(mp_int* a, int t, int* result, WC_RNG* rng)
5201#endif
5202{
5203    int ret = FP_YES;
5204    fp_digit d;
5205    int i;
5206
5207    if (a == NULL || result == NULL || rng == NULL)
5208        return FP_VAL;
5209    if (a->sign == FP_NEG)
5210        return FP_VAL;
5211    if (t <= 0 || t > FP_PRIME_SIZE)
5212        return FP_VAL;
5213
5214    if (fp_isone(a)) {
5215        *result = FP_NO;
5216        return FP_OKAY;
5217    }
5218
5219    /* check against primes table */
5220    for (i = 0; i < FP_PRIME_SIZE; i++) {
5221        if (fp_cmp_d(a, primes[i]) == FP_EQ) {
5222            *result = FP_YES;
5223            return FP_OKAY;
5224        }
5225    }
5226
5227    /* do trial division */
5228    for (i = 0; i < FP_PRIME_SIZE; i++) {
5229        if (fp_mod_d(a, primes[i], &d) == MP_OKAY) {
5230            if (d == 0) {
5231                *result = FP_NO;
5232                return FP_OKAY;
5233            }
5234        }
5235        else
5236            return FP_VAL;
5237    }
5238
5239#ifndef WC_NO_RNG
5240    /* now do a miller rabin with up to t random numbers, this should
5241     * give a (1/4)^t chance of a false prime. */
5242    {
5243    #ifndef WOLFSSL_SMALL_STACK
5244        fp_int b[1], c[1], n1[1], y[1], r[1];
5245        byte   base[FP_MAX_PRIME_SIZE];
5246    #else
5247        fp_int *b, *c, *n1, *y, *r;
5248        byte*  base;
5249    #endif
5250        word32 baseSz;
5251        word32 bitSz;
5252        int    err;
5253
5254        bitSz = fp_count_bits(a);
5255        /* The base size is the number of bits / 8. One is added if the number
5256         * of bits isn't an even 8. */
5257        baseSz = (bitSz / 8) + ((bitSz % 8) ? 1 : 0);
5258        bitSz %= 8;
5259
5260    #ifndef WOLFSSL_SMALL_STACK
5261        if (baseSz > sizeof(base))
5262            return FP_MEM;
5263    #else
5264        base = (byte*)XMALLOC(baseSz, NULL, DYNAMIC_TYPE_TMP_BUFFER);
5265        if (base == NULL)
5266            return FP_MEM;
5267
5268        b = (fp_int*)XMALLOC(sizeof(fp_int) * 5, NULL, DYNAMIC_TYPE_BIGINT);
5269        if (b == NULL) {
5270            XFREE(base, NULL, DYNAMIC_TYPE_TMP_BUFFER);
5271            return FP_MEM;
5272        }
5273        c = &b[1]; n1 = &b[2]; y= &b[3]; r = &b[4];
5274    #endif
5275
5276        fp_init(b);
5277        fp_init(c);
5278        fp_init(n1);
5279        fp_init(y);
5280        fp_init(r);
5281
5282        err = fp_sub_d(a, 2, c);
5283        if (err != FP_OKAY) {
5284           WC_FREE_VAR_EX(b, NULL, DYNAMIC_TYPE_BIGINT);
5285           WC_FREE_VAR_EX(base, NULL, DYNAMIC_TYPE_TMP_BUFFER);
5286           return err;
5287        }
5288        while (t > 0) {
5289            if ((err = wc_RNG_GenerateBlock(rng, base, baseSz)) != 0) {
5290               WC_FREE_VAR_EX(b, NULL, DYNAMIC_TYPE_BIGINT);
5291               WC_FREE_VAR_EX(base, NULL, DYNAMIC_TYPE_TMP_BUFFER);
5292               return err;
5293            }
5294
5295            if (bitSz != 0)
5296                base[0] &= (1 << bitSz) - 1;
5297
5298            err = fp_read_unsigned_bin(b, base, baseSz);
5299            if (err != FP_OKAY) {
5300               WC_FREE_VAR_EX(b, NULL, DYNAMIC_TYPE_BIGINT);
5301               WC_FREE_VAR_EX(base, NULL, DYNAMIC_TYPE_TMP_BUFFER);
5302               return err;
5303            }
5304            if (fp_cmp_d(b, 2) != FP_GT || fp_cmp(b, c) != FP_LT) {
5305                continue;
5306            }
5307
5308            err = fp_prime_miller_rabin_ex(a, b, &ret, n1, y, r);
5309            if (err != FP_OKAY) {
5310               WC_FREE_VAR_EX(b, NULL, DYNAMIC_TYPE_BIGINT);
5311               WC_FREE_VAR_EX(base, NULL, DYNAMIC_TYPE_TMP_BUFFER);
5312               return err;
5313            }
5314            if (ret == FP_NO)
5315                break;
5316            fp_zero(b);
5317            t--;
5318        }
5319
5320        fp_clear(n1);
5321        fp_clear(y);
5322        fp_clear(r);
5323        fp_clear(b);
5324        fp_clear(c);
5325        WC_FREE_VAR_EX(b, NULL, DYNAMIC_TYPE_BIGINT);
5326        WC_FREE_VAR_EX(base, NULL, DYNAMIC_TYPE_TMP_BUFFER);
5327    }
5328#else
5329    (void)t;
5330#endif /* !WC_NO_RNG */
5331
5332    *result = ret;
5333    return FP_OKAY;
5334}
5335#endif /* !NO_RSA || !NO_DSA || !NO_DH || WOLFSSL_KEY_GEN */
5336
5337
5338int mp_cond_swap_ct_ex(mp_int* a, mp_int* b, int c, int m, mp_int* t)
5339{
5340    return fp_cond_swap_ct_ex(a, b, c, m, t);
5341}
5342
5343int mp_cond_swap_ct(mp_int* a, mp_int* b, int c, int m)
5344{
5345    return fp_cond_swap_ct(a, b, c, m);
5346}
5347
5348#ifdef WOLFSSL_KEY_GEN
5349
5350static int  fp_gcd(fp_int *a, fp_int *b, fp_int *c);
5351static int  fp_lcm(fp_int *a, fp_int *b, fp_int *c);
5352static int  fp_randprime(fp_int* a, int len, WC_RNG* rng, void* heap);
5353
5354int mp_gcd(fp_int *a, fp_int *b, fp_int *c)
5355{
5356    return fp_gcd(a, b, c);
5357}
5358
5359
5360int mp_lcm(fp_int *a, fp_int *b, fp_int *c)
5361{
5362    return fp_lcm(a, b, c);
5363}
5364
5365int mp_rand_prime(mp_int* a, int len, WC_RNG* rng, void* heap)
5366{
5367    int err;
5368
5369    err = fp_randprime(a, len, rng, heap);
5370    switch(err) {
5371        case WC_NO_ERR_TRACE(MP_VAL):
5372            return MP_VAL;
5373        case WC_NO_ERR_TRACE(MP_MEM):
5374            return MP_MEM;
5375        default:
5376            break;
5377    }
5378
5379    return MP_OKAY;
5380}
5381
5382int mp_exch (mp_int * a, mp_int * b)
5383{
5384    return fp_exch(a, b);
5385}
5386
5387
5388
5389int fp_randprime(fp_int* a, int len, WC_RNG* rng, void* heap)
5390{
5391    static const int USE_BBS = 1;
5392    int   err, type;
5393    int   isPrime = FP_YES;
5394        /* Assume the candidate is probably prime and then test until
5395         * it is proven composite. */
5396    byte* buf;
5397
5398    (void)heap;
5399
5400    /* get type */
5401    if (len < 0) {
5402        type = USE_BBS;
5403        len = -len;
5404    } else {
5405        type = 0;
5406    }
5407
5408    /* allow sizes between 2 and 512 bytes for a prime size */
5409    if (len < 2 || len > 512) {
5410        return FP_VAL;
5411    }
5412
5413    /* allocate buffer to work with */
5414    buf = (byte*)XMALLOC(len, heap, DYNAMIC_TYPE_TMP_BUFFER);
5415    if (buf == NULL) {
5416        return FP_MEM;
5417    }
5418    XMEMSET(buf, 0, len);
5419
5420    do {
5421#ifdef SHOW_GEN
5422        printf(".");
5423        fflush(stdout);
5424#endif
5425        /* generate value */
5426        err = wc_RNG_GenerateBlock(rng, buf, len);
5427        if (err != 0) {
5428            XFREE(buf, heap, DYNAMIC_TYPE_TMP_BUFFER);
5429            return FP_VAL;
5430        }
5431
5432        /* munge bits */
5433        buf[0]     |= 0x80 | 0x40;
5434        buf[len-1] |= 0x01 | ((type & USE_BBS) ? 0x02 : 0x00);
5435
5436        /* load value */
5437        err = fp_read_unsigned_bin(a, buf, len);
5438        if (err != 0) {
5439            XFREE(buf, heap, DYNAMIC_TYPE_TMP_BUFFER);
5440            return err;
5441        }
5442
5443        /* test */
5444        /* Running Miller-Rabin up to 3 times gives us a 2^{-80} chance
5445         * of a 1024-bit candidate being a false positive, when it is our
5446         * prime candidate. (Note 4.49 of Handbook of Applied Cryptography.)
5447         * Using 8 because we've always used 8 */
5448        mp_prime_is_prime_ex(a, 8, &isPrime, rng);
5449    } while (isPrime == FP_NO);
5450
5451    XMEMSET(buf, 0, len);
5452    XFREE(buf, heap, DYNAMIC_TYPE_TMP_BUFFER);
5453
5454    return FP_OKAY;
5455}
5456
5457/* c = [a, b] */
5458int fp_lcm(fp_int *a, fp_int *b, fp_int *c)
5459{
5460   int     err;
5461   WC_DECLARE_VAR(t, fp_int, 2, 0);
5462
5463   /* LCM of 0 and any number is undefined as 0 is not in the set of values
5464    * being used. */
5465   if (fp_iszero(a) == FP_YES || fp_iszero(b) == FP_YES) {
5466       return FP_VAL;
5467   }
5468
5469   WC_ALLOC_VAR_EX(t, fp_int, 2, NULL, DYNAMIC_TYPE_BIGINT, return FP_MEM);
5470
5471   fp_init(&t[0]);
5472   fp_init(&t[1]);
5473   err = fp_gcd(a, b, &t[0]);
5474   if (err == FP_OKAY) {
5475      if (fp_cmp_mag(a, b) == FP_GT) {
5476        err = fp_div(a, &t[0], &t[1], NULL);
5477        if (err == FP_OKAY)
5478          err = fp_mul(b, &t[1], c);
5479     } else {
5480        err = fp_div(b, &t[0], &t[1], NULL);
5481        if (err == FP_OKAY)
5482          err = fp_mul(a, &t[1], c);
5483     }
5484   }
5485
5486   WC_FREE_VAR_EX(t, NULL, DYNAMIC_TYPE_BIGINT);
5487   return err;
5488}
5489
5490
5491
5492/* c = (a, b) */
5493int fp_gcd(fp_int *a, fp_int *b, fp_int *c)
5494{
5495#ifndef WOLFSSL_SMALL_STACK
5496   fp_int u[1], v[1], r[1];
5497#else
5498   fp_int *u, *v, *r;
5499#endif
5500
5501   /* GCD of 0 and 0 is undefined as all integers divide 0. */
5502   if (fp_iszero(a) == FP_YES && fp_iszero(b) == FP_YES) {
5503       return FP_VAL;
5504   }
5505
5506   /* either zero than gcd is the largest */
5507   if (fp_iszero (a) == FP_YES && fp_iszero (b) == FP_NO) {
5508     fp_abs (b, c);
5509     return FP_OKAY;
5510   }
5511   if (fp_iszero (a) == FP_NO && fp_iszero (b) == FP_YES) {
5512     fp_abs (a, c);
5513     return FP_OKAY;
5514   }
5515
5516   /* optimized.  At this point if a == 0 then
5517    * b must equal zero too
5518    */
5519   if (fp_iszero (a) == FP_YES) {
5520     fp_zero(c);
5521     return FP_OKAY;
5522   }
5523
5524#ifdef WOLFSSL_SMALL_STACK
5525   u = (fp_int*)XMALLOC(sizeof(fp_int) * 3, NULL, DYNAMIC_TYPE_BIGINT);
5526   if (u == NULL) {
5527       return FP_MEM;
5528   }
5529   v = &u[1]; r = &u[2];
5530#endif
5531
5532   /* sort inputs */
5533   if (fp_cmp_mag(a, b) != FP_LT) {
5534      fp_init_copy(u, a);
5535      fp_init_copy(v, b);
5536   } else {
5537      fp_init_copy(u, b);
5538      fp_init_copy(v, a);
5539   }
5540
5541   u->sign = FP_ZPOS;
5542   v->sign = FP_ZPOS;
5543
5544   fp_init(r);
5545   while (fp_iszero(v) == FP_NO) {
5546      int err = fp_mod(u, v, r);
5547      if (err != MP_OKAY) {
5548          WC_FREE_VAR_EX(u, NULL, DYNAMIC_TYPE_BIGINT);
5549        return err;
5550      }
5551      fp_copy(v, u);
5552      fp_copy(r, v);
5553   }
5554   fp_copy(u, c);
5555
5556   WC_FREE_VAR_EX(u, NULL, DYNAMIC_TYPE_BIGINT);
5557   return FP_OKAY;
5558}
5559
5560#endif /* WOLFSSL_KEY_GEN */
5561
5562
5563#if defined(HAVE_ECC) || !defined(NO_PWDBASED) || defined(OPENSSL_EXTRA) || \
5564    defined(WC_RSA_BLINDING) || !defined(NO_DSA) || \
5565    (!defined(NO_RSA) && !defined(NO_RSA_BOUNDS_CHECK))
5566/* c = a + b */
5567int fp_add_d(fp_int *a, fp_digit b, fp_int *c)
5568{
5569   WC_DECLARE_VAR(tmp, fp_int, 1, 0);
5570   int     err;
5571
5572   WC_ALLOC_VAR_EX(tmp, fp_int, 1, NULL, DYNAMIC_TYPE_BIGINT,
5573       return FP_MEM);
5574
5575   fp_init(tmp);
5576   fp_set(tmp, b);
5577   err = fp_add(a, tmp, c);
5578
5579   WC_FREE_VAR_EX(tmp, NULL, DYNAMIC_TYPE_BIGINT);
5580   return err;
5581}
5582
5583/* external compatibility */
5584int mp_add_d(fp_int *a, fp_digit b, fp_int *c)
5585{
5586    return fp_add_d(a, b, c);
5587}
5588
5589#endif  /* HAVE_ECC || !NO_PWDBASED || OPENSSL_EXTRA || WC_RSA_BLINDING ||
5590  !NO_DSA || (!NO_RSA && !NO_RSA_BOUNDS_CHECK) */
5591
5592
5593#if !defined(NO_DSA) || defined(HAVE_ECC) || defined(WOLFSSL_KEY_GEN) || \
5594    defined(HAVE_COMP_KEY) || defined(WOLFSSL_DEBUG_MATH) || \
5595    defined(DEBUG_WOLFSSL) || defined(OPENSSL_EXTRA) || defined(WC_MP_TO_RADIX)
5596
5597/* chars used in radix conversions */
5598static wcchar fp_s_rmap = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"
5599                                    "abcdefghijklmnopqrstuvwxyz+/";
5600#endif
5601
5602#if defined(OPENSSL_EXTRA) || !defined(NO_DSA) || defined(HAVE_ECC)
5603#if DIGIT_BIT == 64 || DIGIT_BIT == 32
5604static int fp_read_radix_16(fp_int *a, const char *str)
5605{
5606  int     i, j, k, neg;
5607  int     ch;
5608  /* Skip whitespace at end of line */
5609  int     eol_done = 0;
5610
5611  /* if the leading digit is a
5612   * minus set the sign to negative.
5613   */
5614  if (*str == '-') {
5615    ++str;
5616    neg = FP_NEG;
5617  } else {
5618    neg = FP_ZPOS;
5619  }
5620
5621  j = 0;
5622  k = 0;
5623  for (i = (int)(XSTRLEN(str) - 1); i >= 0; i--) {
5624      ch = (int)HexCharToByte(str[i]);
5625      if (ch < 0) {
5626        if (!eol_done && CharIsWhiteSpace(str[i]))
5627          continue;
5628        return FP_VAL;
5629      }
5630      eol_done = 1;
5631
5632      k += j == DIGIT_BIT;
5633      j &= DIGIT_BIT - 1;
5634      if (k >= FP_SIZE)
5635          return FP_VAL;
5636
5637      a->dp[k] |= ((fp_digit)ch) << j;
5638      j += 4;
5639  }
5640
5641  a->used = k + 1;
5642  fp_clamp(a);
5643  /* set the sign only if a != 0 */
5644  if (fp_iszero(a) != FP_YES) {
5645     a->sign = neg;
5646  }
5647  return FP_OKAY;
5648}
5649#endif
5650
5651static int fp_read_radix(fp_int *a, const char *str, int radix)
5652{
5653  int     y, neg;
5654  char    ch;
5655
5656  /* set the integer to the default of zero */
5657  fp_zero (a);
5658
5659#if DIGIT_BIT == 64 || DIGIT_BIT == 32
5660  if (radix == 16)
5661      return fp_read_radix_16(a, str);
5662#endif
5663
5664  /* make sure the radix is ok */
5665  if (radix < 2 || radix > 64) {
5666    return FP_VAL;
5667  }
5668
5669  /* if the leading digit is a
5670   * minus set the sign to negative.
5671   */
5672  if (*str == '-') {
5673    ++str;
5674    neg = FP_NEG;
5675  } else {
5676    neg = FP_ZPOS;
5677  }
5678
5679  /* process each digit of the string */
5680  while (*str) {
5681    /* if the radix <= 36 the conversion is case insensitive
5682     * this allows numbers like 1AB and 1ab to represent the same  value
5683     * [e.g. in hex]
5684     */
5685    ch = (char)((radix <= 36) ? XTOUPPER((unsigned char)*str) : *str);
5686    for (y = 0; y < 64; y++) {
5687      if (ch == fp_s_rmap[y]) {
5688         break;
5689      }
5690    }
5691    if (y >= radix) {
5692      /* Check if whitespace at end of line */
5693      while (CharIsWhiteSpace(*str))
5694        ++str;
5695      if (*str)
5696        return FP_VAL;
5697      else
5698        break;
5699    }
5700
5701    /* if the char was found in the map
5702     * and is less than the given radix add it
5703     * to the number, otherwise exit the loop.
5704     */
5705    if (y < radix) {
5706      int ret = fp_mul_d (a, (fp_digit) radix, a);
5707      if (ret != FP_OKAY)
5708        return ret;
5709      ret = fp_add_d (a, (fp_digit) y, a);
5710      if (ret != FP_OKAY)
5711        return ret;
5712    } else {
5713      break;
5714    }
5715    ++str;
5716  }
5717
5718  /* set the sign only if a != 0 */
5719  if (fp_iszero(a) != FP_YES) {
5720     a->sign = neg;
5721  }
5722  return FP_OKAY;
5723}
5724
5725/* fast math conversion */
5726int mp_read_radix(mp_int *a, const char *str, int radix)
5727{
5728    return fp_read_radix(a, str, radix);
5729}
5730
5731#endif /* !defined(NO_DSA) || defined(HAVE_ECC) */
5732
5733#if defined(HAVE_ECC) || (!defined(NO_RSA) && defined(WC_RSA_BLINDING))
5734
5735int mp_montgomery_reduce(fp_int *a, fp_int *m, fp_digit mp)
5736{
5737    return fp_montgomery_reduce(a, m, mp);
5738}
5739
5740int mp_montgomery_reduce_ex(fp_int *a, fp_int *m, fp_digit mp, int ct)
5741{
5742    return fp_montgomery_reduce_ex(a, m, mp, ct);
5743}
5744
5745
5746/* fast math conversion */
5747int mp_montgomery_setup(fp_int *a, fp_digit *rho)
5748{
5749    return fp_montgomery_setup(a, rho);
5750}
5751
5752#endif /* HAVE_ECC || (!NO_RSA && WC_RSA_BLINDING) */
5753
5754/* fast math conversion */
5755int mp_sqr(fp_int *A, fp_int *B)
5756{
5757    return fp_sqr(A, B);
5758}
5759
5760#ifdef HAVE_ECC
5761
5762/* fast math conversion */
5763int mp_div_2(fp_int * a, fp_int * b)
5764{
5765    fp_div_2(a, b);
5766    return MP_OKAY;
5767}
5768
5769/* c = a / 2 (mod b) - constant time (a < b and positive) */
5770int mp_div_2_mod_ct(mp_int *a, mp_int *b, mp_int *c)
5771{
5772  return fp_div_2_mod_ct(a, b, c);
5773}
5774
5775#ifdef HAVE_COMP_KEY
5776
5777int mp_cnt_lsb(fp_int* a)
5778{
5779    return fp_cnt_lsb(a);
5780}
5781
5782#endif /* HAVE_COMP_KEY */
5783
5784#endif /* HAVE_ECC */
5785
5786#if defined(HAVE_ECC) || !defined(NO_RSA) || !defined(NO_DSA) || \
5787    defined(WOLFSSL_KEY_GEN)
5788/* fast math conversion */
5789int mp_set(fp_int *a, fp_digit b)
5790{
5791    fp_set(a,b);
5792    return MP_OKAY;
5793}
5794#endif
5795
5796#ifdef WC_MP_TO_RADIX
5797
5798/* returns size of ASCII representation */
5799int mp_radix_size (mp_int *a, int radix, int *size)
5800{
5801    int      res, digs;
5802    fp_digit d;
5803    WC_DECLARE_VAR(t, fp_int, 1, 0);
5804
5805    *size = 0;
5806
5807    /* special case for binary */
5808    if (radix == 2) {
5809        *size = fp_count_bits(a);
5810        if (*size == 0)
5811          *size = 1;
5812        *size += (a->sign == FP_NEG ? 1 : 0) + 1; /* "-" sign + null term */
5813        return FP_OKAY;
5814    }
5815
5816    /* make sure the radix is in range */
5817    if (radix < 2 || radix > 64) {
5818        return FP_VAL;
5819    }
5820
5821    if (fp_iszero(a) == MP_YES) {
5822#ifndef WC_DISABLE_RADIX_ZERO_PAD
5823        if (radix == 16)
5824            *size = 3;
5825        else
5826#endif
5827            *size = 2;
5828        return FP_OKAY;
5829    }
5830
5831    /* digs is the digit count */
5832    digs = 0;
5833
5834    WC_ALLOC_VAR_EX(t, fp_int, 1, NULL, DYNAMIC_TYPE_BIGINT, return FP_MEM);
5835
5836    /* Init a copy (t) of the input (a)
5837    **
5838    ** ALERT: Not calling fp_init_copy() as some compiler optimization settings
5839    ** such as -O2 will complain that (t) "may be used uninitialized"
5840    ** The fp_init() is here only to appease the compiler.  */
5841    fp_init(t);
5842    fp_copy(a, t); /* copy (src = a) to (dst = t)*/
5843
5844    /* force temp to positive */
5845    t->sign = FP_ZPOS;
5846
5847    /* fetch out all of the digits */
5848    while (fp_iszero (t) == FP_NO) {
5849        if ((res = fp_div_d (t, (mp_digit) radix, t, &d)) != FP_OKAY) {
5850            fp_zero (t);
5851            WC_FREE_VAR_EX(t, NULL, DYNAMIC_TYPE_BIGINT);
5852            return res;
5853        }
5854        ++digs;
5855    }
5856    fp_zero (t);
5857
5858#ifndef WC_DISABLE_RADIX_ZERO_PAD
5859    /* For hexadecimal output, add zero padding when number of digits is odd */
5860    if ((digs & 1) && (radix == 16)) {
5861        ++digs;
5862    }
5863#endif
5864
5865    /* if it's negative add one for the sign */
5866    if (a->sign == FP_NEG) {
5867        ++digs;
5868    }
5869
5870    /* return digs + 1, the 1 is for the NULL byte that would be required. */
5871    *size = digs + 1;
5872    WC_FREE_VAR_EX(t, NULL, DYNAMIC_TYPE_BIGINT);
5873    return FP_OKAY;
5874}
5875
5876/* stores a bignum as a ASCII string in a given radix (2..64) */
5877int mp_toradix (mp_int *a, char *str, int radix)
5878{
5879    int      res, digs;
5880    fp_digit d;
5881    char     *_s = str;
5882    WC_DECLARE_VAR(t, fp_int, 1, 0);
5883
5884    /* check range of the radix */
5885    if (radix < 2 || radix > 64) {
5886        return FP_VAL;
5887    }
5888
5889    /* quick out if its zero */
5890    if (fp_iszero(a) == FP_YES) {
5891#ifndef WC_DISABLE_RADIX_ZERO_PAD
5892        if (radix == 16)
5893            *str++ = '0';
5894#endif
5895        *str++ = '0';
5896        *str = '\0';
5897        return FP_OKAY;
5898    }
5899
5900    WC_ALLOC_VAR_EX(t, fp_int, 1, NULL, DYNAMIC_TYPE_BIGINT, return FP_MEM);
5901
5902    /* Init a copy (t) of the input (a)
5903    **
5904    ** ALERT: Not calling fp_init_copy() as some compiler optimization settings
5905    ** such as -O2 will complain that (t) "may be used uninitialized"
5906    ** The fp_init() is here only to appease the compiler.  */
5907    fp_init(t);
5908    fp_copy(a, t); /* copy (src = a) to (dst = t) */
5909
5910    /* if it is negative output a - */
5911    if (t->sign == FP_NEG) {
5912        ++_s;
5913        *str++ = '-';
5914        t->sign = FP_ZPOS;
5915    }
5916
5917    digs = 0;
5918    while (fp_iszero (t) == FP_NO) {
5919        if ((res = fp_div_d (t, (fp_digit) radix, t, &d)) != FP_OKAY) {
5920            fp_zero (t);
5921            WC_FREE_VAR_EX(t, NULL, DYNAMIC_TYPE_BIGINT);
5922            return res;
5923        }
5924        *str++ = fp_s_rmap[d];
5925        ++digs;
5926    }
5927#ifndef WC_DISABLE_RADIX_ZERO_PAD
5928    /* For hexadecimal output, add zero padding when number of digits is odd */
5929    if ((digs & 1) && (radix == 16)) {
5930        *str++ = fp_s_rmap[0];
5931        ++digs;
5932    }
5933#endif
5934    /* reverse the digits of the string.  In this case _s points
5935     * to the first digit [excluding the sign] of the number]
5936     */
5937    mp_reverse ((unsigned char *)_s, digs);
5938
5939    /* append a NULL so the string is properly terminated */
5940    *str = '\0';
5941
5942    fp_zero (t);
5943    WC_FREE_VAR_EX(t, NULL, DYNAMIC_TYPE_BIGINT);
5944    return FP_OKAY;
5945}
5946
5947#ifdef WOLFSSL_DEBUG_MATH
5948void mp_dump(const char* desc, mp_int* a, byte verbose)
5949{
5950  char buffer[FP_SIZE * sizeof(fp_digit) * 2];
5951  int size;
5952
5953#if defined(ALT_ECC_SIZE) || defined(HAVE_WOLF_BIGINT)
5954  size = a->size;
5955#else
5956  size = FP_SIZE;
5957#endif
5958
5959  printf("%s: ptr=%p, used=%d, sign=%d, size=%d, fpd=%d\n",
5960    desc, a, a->used, a->sign, size, (int)sizeof(fp_digit));
5961
5962  mp_tohex(a, buffer);
5963  printf("  %s\n  ", buffer);
5964
5965  if (verbose) {
5966    int i;
5967    for(i=0; i<size * (int)sizeof(fp_digit); i++) {
5968      printf("%x ", *(((byte*)a->dp) + i));
5969    }
5970    printf("\n");
5971  }
5972}
5973#endif /* WOLFSSL_DEBUG_MATH */
5974
5975#endif /* WC_MP_TO_RADIX */
5976
5977
5978int mp_abs(mp_int* a, mp_int* b)
5979{
5980  fp_abs(a, b);
5981  return FP_OKAY;
5982}
5983
5984
5985int mp_lshd (mp_int * a, int b)
5986{
5987  return fp_lshd(a, b);
5988}
5989
5990#ifdef WOLFSSL_CHECK_MEM_ZERO
5991void mp_memzero_add(const char* name, mp_int* a)
5992{
5993    wc_MemZero_Add(name, a->dp, sizeof(a->dp));
5994}
5995
5996void mp_memzero_check(mp_int* a)
5997{
5998    wc_MemZero_Check(a->dp, sizeof(a->dp));
5999}
6000#endif /* WOLFSSL_CHECK_MEM_ZERO */
6001
6002#endif /* USE_FAST_MATH */