crypto/external/bsd/heimdal/dist/lib/hcrypto/libtommath/bn_mp_exptmod.c

   1 /*      $NetBSD: bn_mp_exptmod.c,v 1.1.1.2 2014/04/24 12:45:31 pettai Exp $     */
   2
   3 #include <tommath.h>
   4 #ifdef BN_MP_EXPTMOD_C
   5 /* LibTomMath, multiple-precision integer library -- Tom St Denis
   6  *
   7  * LibTomMath is a library that provides multiple-precision
   8  * integer arithmetic as well as number theoretic functionality.
   9  *
  10  * The library was designed directly after the MPI library by
  11  * Michael Fromberger but has been written from scratch with
  12  * additional optimizations in place.
  13  *
  14  * The library is free for all purposes without any express
  15  * guarantee it works.
  16  *
  17  * Tom St Denis, tomstdenis@gmail.com, http://libtom.org
  18  */
  19
  20
  21 /* this is a shell function that calls either the normal or Montgomery
  22  * exptmod functions.  Originally the call to the montgomery code was
  23  * embedded in the normal function but that wasted alot of stack space
  24  * for nothing (since 99% of the time the Montgomery code would be called)
  25  */
  26 int mp_exptmod (mp_int * G, mp_int * X, mp_int * P, mp_int * Y)
  27 {
  28   int dr;
  29
  30   /* modulus P must be positive */
  31   if (P->sign == MP_NEG) {
  32      return MP_VAL;
  33   }
  34
  35   /* if exponent X is negative we have to recurse */
  36   if (X->sign == MP_NEG) {
  37 #ifdef BN_MP_INVMOD_C
  38      mp_int tmpG, tmpX;
  39      int err;
  40
  41      /* first compute 1/G mod P */
  42      if ((err = mp_init(&tmpG)) != MP_OKAY) {
  43         return err;
  44      }
  45      if ((err = mp_invmod(G, P, &tmpG)) != MP_OKAY) {
  46         mp_clear(&tmpG);
  47         return err;
  48      }
  49
  50      /* now get |X| */
  51      if ((err = mp_init(&tmpX)) != MP_OKAY) {
  52         mp_clear(&tmpG);
  53         return err;
  54      }
  55      if ((err = mp_abs(X, &tmpX)) != MP_OKAY) {
  56         mp_clear_multi(&tmpG, &tmpX, NULL);
  57         return err;
  58      }
  59
  60      /* and now compute (1/G)**|X| instead of G**X [X < 0] */
  61      err = mp_exptmod(&tmpG, &tmpX, P, Y);
  62      mp_clear_multi(&tmpG, &tmpX, NULL);
  63      return err;
  64 #else
  65      /* no invmod */
  66      return MP_VAL;
  67 #endif
  68   }
  69
  70 /* modified diminished radix reduction */
  71 #if defined(BN_MP_REDUCE_IS_2K_L_C) && defined(BN_MP_REDUCE_2K_L_C) && defined(BN_S_MP_EXPTMOD_C)
  72   if (mp_reduce_is_2k_l(P) == MP_YES) {
  73      return s_mp_exptmod(G, X, P, Y, 1);
  74   }
  75 #endif
  76
  77 #ifdef BN_MP_DR_IS_MODULUS_C
  78   /* is it a DR modulus? */
  79   dr = mp_dr_is_modulus(P);
  80 #else
  81   /* default to no */
  82   dr = 0;
  83 #endif
  84
  85 #ifdef BN_MP_REDUCE_IS_2K_C
  86   /* if not, is it a unrestricted DR modulus? */
  87   if (dr == 0) {
  88      dr = mp_reduce_is_2k(P) << 1;
  89   }
  90 #endif
  91
  92   /* if the modulus is odd or dr != 0 use the montgomery method */
  93 #ifdef BN_MP_EXPTMOD_FAST_C
  94   if (mp_isodd (P) == 1 || dr !=  0) {
  95     return mp_exptmod_fast (G, X, P, Y, dr);
  96   } else {
  97 #endif
  98 #ifdef BN_S_MP_EXPTMOD_C
  99     /* otherwise use the generic Barrett reduction technique */
 100     return s_mp_exptmod (G, X, P, Y, 0);
 101 #else
 102     /* no exptmod for evens */
 103     return MP_VAL;
 104 #endif
 105 #ifdef BN_MP_EXPTMOD_FAST_C
 106   }
 107 #endif
 108 }
 109
 110 #endif
 111
 112 /* Source: /cvs/libtom/libtommath/bn_mp_exptmod.c,v  */
 113 /* Revision: 1.5  */
 114 /* Date: 2006/12/28 01:25:13  */