userapps/opensource/sshd/libtommath/bn_mp_montgomery_calc_normalization.c

   1 /* LibTomMath, multiple-precision integer library -- Tom St Denis
   2  *
   3  * LibTomMath is library that provides for multiple-precision
   4  * integer arithmetic as well as number theoretic functionality.
   5  *
   6  * The library is designed directly after the MPI library by
   7  * Michael Fromberger but has been written from scratch with
   8  * additional optimizations in place.
   9  *
  10  * The library is free for all purposes without any express
  11  * guarantee it works.
  12  *
  13  * Tom St Denis, tomstdenis@iahu.ca, http://math.libtomcrypt.org
  14  */
  15 #include <tommath.h>
  16
  17 /* calculates a = B^n mod b for Montgomery reduction
  18  * Where B is the base [e.g. 2^DIGIT_BIT].
  19  * B^n mod b is computed by first computing
  20  * A = B^(n-1) which doesn't require a reduction but a simple OR.
  21  * then C = A * B = B^n is computed by performing upto DIGIT_BIT
  22  * shifts with subtractions when the result is greater than b.
  23  *
  24  * The method is slightly modified to shift B unconditionally upto just under
  25  * the leading bit of b.  This saves alot of multiple precision shifting.
  26  */
  27 int
  28 mp_montgomery_calc_normalization (mp_int * a, mp_int * b)
  29 {
  30   int     x, bits, res;
  31
  32   /* how many bits of last digit does b use */
  33   bits = mp_count_bits (b) % DIGIT_BIT;
  34
  35   /* compute A = B^(n-1) * 2^(bits-1) */
  36   if ((res = mp_2expt (a, (b->used - 1) * DIGIT_BIT + bits - 1)) != MP_OKAY) {
  37     return res;
  38   }
  39
  40   /* now compute C = A * B mod b */
  41   for (x = bits - 1; x < (int)DIGIT_BIT; x++) {
  42     if ((res = mp_mul_2 (a, a)) != MP_OKAY) {
  43       return res;
  44     }
  45     if (mp_cmp_mag (a, b) != MP_LT) {
  46       if ((res = s_mp_sub (a, b, a)) != MP_OKAY) {
  47         return res;
  48       }
  49     }
  50   }
  51
  52   return MP_OKAY;
  53 }