lib/hcrypto/libtommath/bn_mp_exptmod.c

   1 #include "tommath_private.h"
   2 #ifdef BN_MP_EXPTMOD_C
   3 /* LibTomMath, multiple-precision integer library -- Tom St Denis */
   4 /* SPDX-License-Identifier: Unlicense */
   5
   6 /* this is a shell function that calls either the normal or Montgomery
   7  * exptmod functions.  Originally the call to the montgomery code was
   8  * embedded in the normal function but that wasted alot of stack space
   9  * for nothing (since 99% of the time the Montgomery code would be called)
  10  */
  11 mp_err mp_exptmod(const mp_int *G, const mp_int *X, const mp_int *P, mp_int *Y)
  12 {
  13    int dr;
  14
  15    /* modulus P must be positive */
  16    if (P->sign == MP_NEG) {
  17       return MP_VAL;
  18    }
  19
  20    /* if exponent X is negative we have to recurse */
  21    if (X->sign == MP_NEG) {
  22       mp_int tmpG, tmpX;
  23       mp_err err;
  24
  25       if (!MP_HAS(MP_INVMOD)) {
  26          return MP_VAL;
  27       }
  28
  29       if ((err = mp_init_multi(&tmpG, &tmpX, NULL)) != MP_OKAY) {
  30          return err;
  31       }
  32
  33       /* first compute 1/G mod P */
  34       if ((err = mp_invmod(G, P, &tmpG)) != MP_OKAY) {
  35          goto LBL_ERR;
  36       }
  37
  38       /* now get |X| */
  39       if ((err = mp_abs(X, &tmpX)) != MP_OKAY) {
  40          goto LBL_ERR;
  41       }
  42
  43       /* and now compute (1/G)**|X| instead of G**X [X < 0] */
  44       err = mp_exptmod(&tmpG, &tmpX, P, Y);
  45 LBL_ERR:
  46       mp_clear_multi(&tmpG, &tmpX, NULL);
  47       return err;
  48    }
  49
  50    /* modified diminished radix reduction */
  51    if (MP_HAS(MP_REDUCE_IS_2K_L) && MP_HAS(MP_REDUCE_2K_L) && MP_HAS(S_MP_EXPTMOD) &&
  52        (mp_reduce_is_2k_l(P) == MP_YES)) {
  53       return s_mp_exptmod(G, X, P, Y, 1);
  54    }
  55
  56    /* is it a DR modulus? default to no */
  57    dr = (MP_HAS(MP_DR_IS_MODULUS) && (mp_dr_is_modulus(P) == MP_YES)) ? 1 : 0;
  58
  59    /* if not, is it a unrestricted DR modulus? */
  60    if (MP_HAS(MP_REDUCE_IS_2K) && (dr == 0)) {
  61       dr = (mp_reduce_is_2k(P) == MP_YES) ? 2 : 0;
  62    }
  63
  64    /* if the modulus is odd or dr != 0 use the montgomery method */
  65    if (MP_HAS(S_MP_EXPTMOD_FAST) && (MP_IS_ODD(P) || (dr != 0))) {
  66       return s_mp_exptmod_fast(G, X, P, Y, dr);
  67    } else if (MP_HAS(S_MP_EXPTMOD)) {
  68       /* otherwise use the generic Barrett reduction technique */
  69       return s_mp_exptmod(G, X, P, Y, 0);
  70    } else {
  71       /* no exptmod for evens */
  72       return MP_VAL;
  73    }
  74 }
  75
  76 #endif