Line data    Source code

       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         922 : mp_err mp_exptmod(const mp_int *G, const mp_int *X, const mp_int *P, mp_int *Y)
      12             : {
      13          32 :    int dr;
      14             : 
      15             :    /* modulus P must be positive */
      16         922 :    if (P->sign == MP_NEG) {
      17           0 :       return MP_VAL;
      18             :    }
      19             : 
      20             :    /* if exponent X is negative we have to recurse */
      21         922 :    if (X->sign == MP_NEG) {
      22           0 :       mp_int tmpG, tmpX;
      23           0 :       mp_err err;
      24             : 
      25           0 :       if (!MP_HAS(MP_INVMOD)) {
      26             :          return MP_VAL;
      27             :       }
      28             : 
      29           0 :       if ((err = mp_init_multi(&tmpG, &tmpX, NULL)) != MP_OKAY) {
      30           0 :          return err;
      31             :       }
      32             : 
      33             :       /* first compute 1/G mod P */
      34           0 :       if ((err = mp_invmod(G, P, &tmpG)) != MP_OKAY) {
      35           0 :          goto LBL_ERR;
      36             :       }
      37             : 
      38             :       /* now get |X| */
      39           0 :       if ((err = mp_abs(X, &tmpX)) != MP_OKAY) {
      40           0 :          goto LBL_ERR;
      41             :       }
      42             : 
      43             :       /* and now compute (1/G)**|X| instead of G**X [X < 0] */
      44           0 :       err = mp_exptmod(&tmpG, &tmpX, P, Y);
      45           0 : LBL_ERR:
      46           0 :       mp_clear_multi(&tmpG, &tmpX, NULL);
      47           0 :       return err;
      48             :    }
      49             : 
      50             :    /* modified diminished radix reduction */
      51         922 :    if (MP_HAS(MP_REDUCE_IS_2K_L) && MP_HAS(MP_REDUCE_2K_L) && MP_HAS(S_MP_EXPTMOD) &&
      52         922 :        (mp_reduce_is_2k_l(P) == MP_YES)) {
      53           0 :       return s_mp_exptmod(G, X, P, Y, 1);
      54             :    }
      55             : 
      56             :    /* is it a DR modulus? default to no */
      57         922 :    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         922 :    if (MP_HAS(MP_REDUCE_IS_2K) && (dr == 0)) {
      61         922 :       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         922 :    if (MP_HAS(S_MP_EXPTMOD_FAST) && (MP_IS_ODD(P) || (dr != 0))) {
      66         922 :       return s_mp_exptmod_fast(G, X, P, Y, dr);
      67           0 :    } else if (MP_HAS(S_MP_EXPTMOD)) {
      68             :       /* otherwise use the generic Barrett reduction technique */
      69           0 :       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