Back to index

lightning-sunbird  0.9+nobinonly
Defines | Functions | Variables
mpmontg.c File Reference
#include <string.h>
#include "mpi-priv.h"
#include "mplogic.h"
#include "mpprime.h"
#include <stddef.h>

Go to the source code of this file.

Defines

#define MP_USING_CACHE_SAFE_MOD_EXP   1
#define STATIC
#define MAX_ODD_INTS   32 /* 2 ** (WINDOW_BITS - 1) */
#define ABORT   abort()
#define SQR(a, b)
#define MUL(x, a, b)   MP_CHECKOK( s_mp_mul_mont(a, oddPowers + (x), b, mmm) )
#define SWAPPA   ptmp = pa1; pa1 = pa2; pa2 = ptmp
#define WEAVE_WORD_SIZE   4
#define SQR(a, b)
#define MUL_NOWEAVE(x, a, b)   MP_CHECKOK( s_mp_mul_mont(a, x, b, mmm) )
#define MUL(x, a, b)
#define SWAPPA   ptmp = pa1; pa1 = pa2; pa2 = ptmp
#define MP_ALIGN(x, y)   ((((ptrdiff_t)(x))+((y)-1))&(((ptrdiff_t)0)-(y)))

Functions

mp_err s_mp_redc (mp_int *T, mp_mont_modulus *mmm)
mp_err s_mp_mul_mont (const mp_int *a, const mp_int *b, mp_int *c, mp_mont_modulus *mmm)
STATIC mp_err s_mp_to_mont (const mp_int *x, mp_mont_modulus *mmm, mp_int *xMont)
mp_err mp_exptmod_i (const mp_int *montBase, const mp_int *exponent, const mp_int *modulus, mp_int *result, mp_mont_modulus *mmm, int nLen, mp_size bits_in_exponent, mp_size window_bits, mp_size odd_ints)
mp_err mp_set_safe_modexp (int value)
mp_err mpi_to_weave (const mp_int *bignums, unsigned char *weaved, mp_size nDigits, mp_size nBignums)
mp_err weave_to_mpi (mp_int *a, const unsigned char *pSrc, mp_size nDigits, mp_size nBignums)
mp_err mp_exptmod_safe_i (const mp_int *montBase, const mp_int *exponent, const mp_int *modulus, mp_int *result, mp_mont_modulus *mmm, int nLen, mp_size bits_in_exponent, mp_size window_bits, mp_size num_powers)
mp_err mp_exptmod (const mp_int *inBase, const mp_int *exponent, const mp_int *modulus, mp_int *result)

Variables

unsigned int mp_using_cache_safe_exp = 1

Define Documentation

#define ABORT   abort()

Definition at line 76 of file mpmontg.c.

#define MAX_ODD_INTS   32 /* 2 ** (WINDOW_BITS - 1) */

Definition at line 71 of file mpmontg.c.

#define MP_ALIGN (   x,
  y 
)    ((((ptrdiff_t)(x))+((y)-1))&(((ptrdiff_t)0)-(y)))

Definition at line 899 of file mpmontg.c.

Definition at line 50 of file mpmontg.c.

#define MUL (   x,
  a,
  b 
)    MP_CHECKOK( s_mp_mul_mont(a, oddPowers + (x), b, mmm) )

Definition at line 894 of file mpmontg.c.

#define MUL (   x,
  a,
  b 
)
Value:
MP_CHECKOK( weave_to_mpi(&tmp, powers + (x), nLen, num_powers) ); \
  MUL_NOWEAVE(&tmp,a,b)

Definition at line 894 of file mpmontg.c.

#define MUL_NOWEAVE (   x,
  a,
  b 
)    MP_CHECKOK( s_mp_mul_mont(a, x, b, mmm) )

Definition at line 890 of file mpmontg.c.

#define SQR (   a,
  b 
)
Value:
MP_CHECKOK( mp_sqr(a, b) );\
  MP_CHECKOK( s_mp_redc(b, mmm) )

Definition at line 881 of file mpmontg.c.

#define SQR (   a,
  b 
)
Value:
MP_CHECKOK( mp_sqr(a, b) );\
  MP_CHECKOK( s_mp_redc(b, mmm) )

Definition at line 881 of file mpmontg.c.

Definition at line 69 of file mpmontg.c.

#define SWAPPA   ptmp = pa1; pa1 = pa2; pa2 = ptmp

Definition at line 898 of file mpmontg.c.

#define SWAPPA   ptmp = pa1; pa1 = pa2; pa2 = ptmp

Definition at line 898 of file mpmontg.c.

Definition at line 540 of file mpmontg.c.


Function Documentation

mp_err mp_exptmod ( const mp_int inBase,
const mp_int exponent,
const mp_int modulus,
mp_int result 
)

Definition at line 1080 of file mpmontg.c.

{
  const mp_int *base;
  mp_size bits_in_exponent, i, window_bits, odd_ints;
  mp_err  res;
  int     nLen;
  mp_int  montBase, goodBase;
  mp_mont_modulus mmm;
#ifdef MP_USING_CACHE_SAFE_MOD_EXP
  static unsigned int max_window_bits;
#endif

  /* function for computing n0prime only works if n0 is odd */
  if (!mp_isodd(modulus))
    return s_mp_exptmod(inBase, exponent, modulus, result);

  MP_DIGITS(&montBase) = 0;
  MP_DIGITS(&goodBase) = 0;

  if (mp_cmp(inBase, modulus) < 0) {
    base = inBase;
  } else {
    MP_CHECKOK( mp_init(&goodBase) );
    base = &goodBase;
    MP_CHECKOK( mp_mod(inBase, modulus, &goodBase) );
  }

  nLen  = MP_USED(modulus);
  MP_CHECKOK( mp_init_size(&montBase, 2 * nLen + 2) );

  mmm.N = *modulus;                /* a copy of the mp_int struct */
  i = mpl_significant_bits(modulus);
  i += MP_DIGIT_BIT - 1;
  mmm.b = i - i % MP_DIGIT_BIT;

  /* compute n0', given n0, n0' = -(n0 ** -1) mod MP_RADIX
  **          where n0 = least significant mp_digit of N, the modulus.
  */
  mmm.n0prime = 0 - s_mp_invmod_radix( MP_DIGIT(modulus, 0) );

  MP_CHECKOK( s_mp_to_mont(base, &mmm, &montBase) );

  bits_in_exponent = mpl_significant_bits(exponent);
#ifdef MP_USING_CACHE_SAFE_MOD_EXP
  if (mp_using_cache_safe_exp) {
    if (bits_in_exponent > 780)
       window_bits = 6;
    else if (bits_in_exponent > 256)
       window_bits = 5;
    else if (bits_in_exponent > 20)
       window_bits = 4;
       /* RSA public key exponents are typically under 20 bits (common values 
        * are: 3, 17, 65537) and a 4-bit window is inefficient
        */
    else 
       window_bits = 1;
  } else
#endif
  if (bits_in_exponent > 480)
    window_bits = 6;
  else if (bits_in_exponent > 160)
    window_bits = 5;
  else if (bits_in_exponent > 20)
    window_bits = 4;
  /* RSA public key exponents are typically under 20 bits (common values 
   * are: 3, 17, 65537) and a 4-bit window is inefficient
   */
  else 
    window_bits = 1;

#ifdef MP_USING_CACHE_SAFE_MOD_EXP
  /*
   * clamp the window size based on
   * the cache line size.
   */
  if (!max_window_bits) {
    unsigned long cache_size = s_mpi_getProcessorLineSize();
    /* processor has no cache, use 'fast' code always */
    if (cache_size == 0) {
      mp_using_cache_safe_exp = 0;
    } 
    if ((cache_size == 0) || (cache_size >= 64)) {
      max_window_bits = 6;
    } else if (cache_size >= 32) {
      max_window_bits = 5;
    } else if (cache_size >= 16) {
      max_window_bits = 4;
    } else max_window_bits = 1; /* should this be an assert? */
  }

  /* clamp the window size down before we caclulate bits_in_exponent */
  if (mp_using_cache_safe_exp) {
    if (window_bits > max_window_bits) {
      window_bits = max_window_bits;
    }
  }
#endif

  odd_ints = 1 << (window_bits - 1);
  i = bits_in_exponent % window_bits;
  if (i != 0) {
    bits_in_exponent += window_bits - i;
  } 

#ifdef MP_USING_MONT_MULF
  if (mp_using_mont_mulf) {
    MP_CHECKOK( s_mp_pad(&montBase, nLen) );
    res = mp_exptmod_f(&montBase, exponent, modulus, result, &mmm, nLen, 
                   bits_in_exponent, window_bits, odd_ints);
  } else
#endif
#ifdef MP_USING_CACHE_SAFE_MOD_EXP
  if (mp_using_cache_safe_exp) {
    res = mp_exptmod_safe_i(&montBase, exponent, modulus, result, &mmm, nLen, 
                   bits_in_exponent, window_bits, 1 << window_bits);
  } else
#endif
  res = mp_exptmod_i(&montBase, exponent, modulus, result, &mmm, nLen, 
                   bits_in_exponent, window_bits, odd_ints);

CLEANUP:
  mp_clear(&montBase);
  mp_clear(&goodBase);
  /* Don't mp_clear mmm.N because it is merely a copy of modulus.
  ** Just zap it.
  */
  memset(&mmm, 0, sizeof mmm);
  return res;
}

Here is the call graph for this function:

Here is the caller graph for this function:

mp_err mp_exptmod_i ( const mp_int montBase,
const mp_int exponent,
const mp_int modulus,
mp_int result,
mp_mont_modulus mmm,
int  nLen,
mp_size  bits_in_exponent,
mp_size  window_bits,
mp_size  odd_ints 
)

Definition at line 376 of file mpmontg.c.

{
  mp_int *pa1, *pa2, *ptmp;
  mp_size i;
  mp_err  res;
  int     expOff;
  mp_int  accum1, accum2, power2, oddPowers[MAX_ODD_INTS];

  /* power2 = base ** 2; oddPowers[i] = base ** (2*i + 1); */
  /* oddPowers[i] = base ** (2*i + 1); */

  MP_DIGITS(&accum1) = 0;
  MP_DIGITS(&accum2) = 0;
  MP_DIGITS(&power2) = 0;
  for (i = 0; i < MAX_ODD_INTS; ++i) {
    MP_DIGITS(oddPowers + i) = 0;
  }

  MP_CHECKOK( mp_init_size(&accum1, 3 * nLen + 2) );
  MP_CHECKOK( mp_init_size(&accum2, 3 * nLen + 2) );

  MP_CHECKOK( mp_init_copy(&oddPowers[0], montBase) );

  mp_init_size(&power2, nLen + 2 * MP_USED(montBase) + 2);
  MP_CHECKOK( mp_sqr(montBase, &power2) );       /* power2 = montBase ** 2 */
  MP_CHECKOK( s_mp_redc(&power2, mmm) );

  for (i = 1; i < odd_ints; ++i) {
    mp_init_size(oddPowers + i, nLen + 2 * MP_USED(&power2) + 2);
    MP_CHECKOK( mp_mul(oddPowers + (i - 1), &power2, oddPowers + i) );
    MP_CHECKOK( s_mp_redc(oddPowers + i, mmm) );
  }

  /* set accumulator to montgomery residue of 1 */
  mp_set(&accum1, 1);
  MP_CHECKOK( s_mp_to_mont(&accum1, mmm, &accum1) );
  pa1 = &accum1;
  pa2 = &accum2;

  for (expOff = bits_in_exponent - window_bits; expOff >= 0; expOff -= window_bits) {
    mp_size smallExp;
    MP_CHECKOK( mpl_get_bits(exponent, expOff, window_bits) );
    smallExp = (mp_size)res;

    if (window_bits == 1) {
      if (!smallExp) {
       SQR(pa1,pa2); SWAPPA;
      } else if (smallExp & 1) {
       SQR(pa1,pa2); MUL(0,pa2,pa1);
      } else {
       ABORT;
      }
    } else if (window_bits == 4) {
      if (!smallExp) {
       SQR(pa1,pa2); SQR(pa2,pa1); SQR(pa1,pa2); SQR(pa2,pa1);
      } else if (smallExp & 1) {
       SQR(pa1,pa2); SQR(pa2,pa1); SQR(pa1,pa2); SQR(pa2,pa1); 
       MUL(smallExp/2, pa1,pa2); SWAPPA;
      } else if (smallExp & 2) {
       SQR(pa1,pa2); SQR(pa2,pa1); SQR(pa1,pa2); 
       MUL(smallExp/4,pa2,pa1); SQR(pa1,pa2); SWAPPA;
      } else if (smallExp & 4) {
       SQR(pa1,pa2); SQR(pa2,pa1); MUL(smallExp/8,pa1,pa2); 
       SQR(pa2,pa1); SQR(pa1,pa2); SWAPPA;
      } else if (smallExp & 8) {
       SQR(pa1,pa2); MUL(smallExp/16,pa2,pa1); SQR(pa1,pa2); 
       SQR(pa2,pa1); SQR(pa1,pa2); SWAPPA;
      } else {
       ABORT;
      }
    } else if (window_bits == 5) {
      if (!smallExp) {
       SQR(pa1,pa2); SQR(pa2,pa1); SQR(pa1,pa2); SQR(pa2,pa1); 
       SQR(pa1,pa2); SWAPPA;
      } else if (smallExp & 1) {
       SQR(pa1,pa2); SQR(pa2,pa1); SQR(pa1,pa2); SQR(pa2,pa1); 
       SQR(pa1,pa2); MUL(smallExp/2,pa2,pa1);
      } else if (smallExp & 2) {
       SQR(pa1,pa2); SQR(pa2,pa1); SQR(pa1,pa2); SQR(pa2,pa1); 
       MUL(smallExp/4,pa1,pa2); SQR(pa2,pa1);
      } else if (smallExp & 4) {
       SQR(pa1,pa2); SQR(pa2,pa1); SQR(pa1,pa2); 
       MUL(smallExp/8,pa2,pa1); SQR(pa1,pa2); SQR(pa2,pa1);
      } else if (smallExp & 8) {
       SQR(pa1,pa2); SQR(pa2,pa1); MUL(smallExp/16,pa1,pa2); 
       SQR(pa2,pa1); SQR(pa1,pa2); SQR(pa2,pa1);
      } else if (smallExp & 0x10) {
       SQR(pa1,pa2); MUL(smallExp/32,pa2,pa1); SQR(pa1,pa2); 
       SQR(pa2,pa1); SQR(pa1,pa2); SQR(pa2,pa1);
      } else {
       ABORT;
      }
    } else if (window_bits == 6) {
      if (!smallExp) {
       SQR(pa1,pa2); SQR(pa2,pa1); SQR(pa1,pa2); SQR(pa2,pa1); 
       SQR(pa1,pa2); SQR(pa2,pa1);
      } else if (smallExp & 1) {
       SQR(pa1,pa2); SQR(pa2,pa1); SQR(pa1,pa2); SQR(pa2,pa1); 
       SQR(pa1,pa2); SQR(pa2,pa1); MUL(smallExp/2,pa1,pa2); SWAPPA;
      } else if (smallExp & 2) {
       SQR(pa1,pa2); SQR(pa2,pa1); SQR(pa1,pa2); SQR(pa2,pa1); 
       SQR(pa1,pa2); MUL(smallExp/4,pa2,pa1); SQR(pa1,pa2); SWAPPA;
      } else if (smallExp & 4) {
       SQR(pa1,pa2); SQR(pa2,pa1); SQR(pa1,pa2); SQR(pa2,pa1); 
       MUL(smallExp/8,pa1,pa2); SQR(pa2,pa1); SQR(pa1,pa2); SWAPPA;
      } else if (smallExp & 8) {
       SQR(pa1,pa2); SQR(pa2,pa1); SQR(pa1,pa2); 
       MUL(smallExp/16,pa2,pa1); SQR(pa1,pa2); SQR(pa2,pa1); 
       SQR(pa1,pa2); SWAPPA;
      } else if (smallExp & 0x10) {
       SQR(pa1,pa2); SQR(pa2,pa1); MUL(smallExp/32,pa1,pa2); 
       SQR(pa2,pa1); SQR(pa1,pa2); SQR(pa2,pa1); SQR(pa1,pa2); SWAPPA;
      } else if (smallExp & 0x20) {
       SQR(pa1,pa2); MUL(smallExp/64,pa2,pa1); SQR(pa1,pa2); 
       SQR(pa2,pa1); SQR(pa1,pa2); SQR(pa2,pa1); SQR(pa1,pa2); SWAPPA;
      } else {
       ABORT;
      }
    } else {
      ABORT;
    }
  }

  res = s_mp_redc(pa1, mmm);
  mp_exch(pa1, result);

CLEANUP:
  mp_clear(&accum1);
  mp_clear(&accum2);
  mp_clear(&power2);
  for (i = 0; i < odd_ints; ++i) {
    mp_clear(oddPowers + i);
  }
  return res;
}

Here is the call graph for this function:

mp_err mp_exptmod_safe_i ( const mp_int montBase,
const mp_int exponent,
const mp_int modulus,
mp_int result,
mp_mont_modulus mmm,
int  nLen,
mp_size  bits_in_exponent,
mp_size  window_bits,
mp_size  num_powers 
)

Definition at line 902 of file mpmontg.c.

{
  mp_int *pa1, *pa2, *ptmp;
  mp_size i;
  mp_size first_window;
  mp_err  res;
  int     expOff;
  mp_int  accum1, accum2, accum[WEAVE_WORD_SIZE];
  mp_int  tmp;
  unsigned char *powersArray;
  unsigned char *powers;

  MP_DIGITS(&accum1) = 0;
  MP_DIGITS(&accum2) = 0;
  MP_DIGITS(&accum[0]) = 0;
  MP_DIGITS(&accum[1]) = 0;
  MP_DIGITS(&accum[2]) = 0;
  MP_DIGITS(&accum[3]) = 0;
  MP_DIGITS(&tmp) = 0;

  powersArray = (unsigned char *)malloc(num_powers*(nLen*sizeof(mp_digit)+1));
  if (powersArray == NULL) {
    res = MP_MEM;
    goto CLEANUP;
  }

  /* powers[i] = base ** (i); */
  powers = (unsigned char *)MP_ALIGN(powersArray,num_powers);

  /* grab the first window value. This allows us to preload accumulator1
   * and save a conversion, some squares and a multiple*/
  MP_CHECKOK( mpl_get_bits(exponent, 
                            bits_in_exponent-window_bits, window_bits) );
  first_window = (mp_size)res;

  MP_CHECKOK( mp_init_size(&accum1, 3 * nLen + 2) );
  MP_CHECKOK( mp_init_size(&accum2, 3 * nLen + 2) );
  MP_CHECKOK( mp_init_size(&tmp, 3 * nLen + 2) );

  /* build the first WEAVE_WORD powers inline */
  /* if WEAVE_WORD_SIZE is not 4, this code will have to change */
  if (num_powers > 2) {
    MP_CHECKOK( mp_init_size(&accum[0], 3 * nLen + 2) );
    MP_CHECKOK( mp_init_size(&accum[1], 3 * nLen + 2) );
    MP_CHECKOK( mp_init_size(&accum[2], 3 * nLen + 2) );
    MP_CHECKOK( mp_init_size(&accum[3], 3 * nLen + 2) );
    mp_set(&accum[0], 1);
    MP_CHECKOK( s_mp_to_mont(&accum[0], mmm, &accum[0]) );
    MP_CHECKOK( mp_copy(montBase, &accum[1]) );
    SQR(montBase, &accum[2]);
    MUL_NOWEAVE(montBase, &accum[2], &accum[3]);
    MP_CHECKOK( mpi_to_weave(accum, powers, nLen, num_powers) );
    if (first_window < 4) {
      MP_CHECKOK( mp_copy(&accum[first_window], &accum1) );
      first_window = num_powers;
    }
  } else {
      if (first_window == 0) {
        mp_set(&accum1, 1);
        MP_CHECKOK( s_mp_to_mont(&accum1, mmm, &accum1) );
      } else {
        /* assert first_window == 1? */
        MP_CHECKOK( mp_copy(montBase, &accum1) );
      }
  }

  /*
   * calculate all the powers in the powers array.
   * this adds 2**(k-1)-2 square operations over just calculating the
   * odd powers where k is the window size in the two other mp_modexpt
   * implementations in this file. We will get some of that
   * back by not needing the first 'k' squares and one multiply for the 
   * first window */ 
  for (i = WEAVE_WORD_SIZE; i < num_powers; i++) {
    int acc_index = i & (WEAVE_WORD_SIZE-1); /* i % WEAVE_WORD_SIZE */
    if ( i & 1 ) {
      MUL_NOWEAVE(montBase, &accum[acc_index-1] , &accum[acc_index]);
      /* we've filled the array do our 'per array' processing */
      if (acc_index == (WEAVE_WORD_SIZE-1)) {
        MP_CHECKOK( mpi_to_weave(accum, powers + i - (WEAVE_WORD_SIZE-1),
                                                  nLen, num_powers) );

        if (first_window <= i) {
          MP_CHECKOK( mp_copy(&accum[first_window & (WEAVE_WORD_SIZE-1)], 
                                                        &accum1) );
          first_window = num_powers;
        }
      }
    } else {
      /* up to 8 we can find 2^i-1 in the accum array, but at 8 we our source
       * and target are the same so we need to copy.. After that, the
       * value is overwritten, so we need to fetch it from the stored
       * weave array */
      if (i > 2* WEAVE_WORD_SIZE) {
        MP_CHECKOK(weave_to_mpi(&accum2, powers+i/2, nLen, num_powers));
        SQR(&accum2, &accum[acc_index]);
      } else {
       int half_power_index = (i/2) & (WEAVE_WORD_SIZE-1);
       if (half_power_index == acc_index) {
          /* copy is cheaper than weave_to_mpi */
          MP_CHECKOK(mp_copy(&accum[half_power_index], &accum2));
          SQR(&accum2,&accum[acc_index]);
       } else {
          SQR(&accum[half_power_index],&accum[acc_index]);
       }
      }
    }
  }
  /* if the accum1 isn't set, Then there is something wrong with our logic 
   * above and is an internal programming error. 
   */
#if MP_ARGCHK == 2
  assert(MP_USED(&accum1) != 0);
#endif

  /* set accumulator to montgomery residue of 1 */
  pa1 = &accum1;
  pa2 = &accum2;

  for (expOff = bits_in_exponent - window_bits*2; expOff >= 0; expOff -= window_bits) {
    mp_size smallExp;
    MP_CHECKOK( mpl_get_bits(exponent, expOff, window_bits) );
    smallExp = (mp_size)res;

    /* handle unroll the loops */
    switch (window_bits) {
    case 1:
       if (!smallExp) {
           SQR(pa1,pa2); SWAPPA;
       } else if (smallExp & 1) {
           SQR(pa1,pa2); MUL_NOWEAVE(montBase,pa2,pa1);
       } else {
           ABORT;
       }
       break;
    case 6:
       SQR(pa1,pa2); SQR(pa2,pa1); 
       /* fall through */
    case 4:
       SQR(pa1,pa2); SQR(pa2,pa1); SQR(pa1,pa2); SQR(pa2,pa1);
       MUL(smallExp, pa1,pa2); SWAPPA;
       break;
    case 5:
       SQR(pa1,pa2); SQR(pa2,pa1); SQR(pa1,pa2); SQR(pa2,pa1); 
       SQR(pa1,pa2); MUL(smallExp,pa2,pa1);
       break;
    default:
       ABORT; /* could do a loop? */
    }
  }

  res = s_mp_redc(pa1, mmm);
  mp_exch(pa1, result);

CLEANUP:
  mp_clear(&accum1);
  mp_clear(&accum2);
  mp_clear(&accum[0]);
  mp_clear(&accum[1]);
  mp_clear(&accum[2]);
  mp_clear(&accum[3]);
  mp_clear(&tmp);
  /* PORT_Memset(powers,0,num_powers*nLen*sizeof(mp_digit)); */
  free(powersArray);
  return res;
}

Here is the call graph for this function:

Definition at line 526 of file mpmontg.c.

{
#ifdef MP_USING_CACHE_SAFE_MOD_EXP
 mp_using_cache_safe_exp = value;
 return MP_OKAY;
#else
 if (value == 0) {
   return MP_OKAY;
 }
 return MP_BADARG;
#endif
}
mp_err mpi_to_weave ( const mp_int bignums,
unsigned char *  weaved,
mp_size  nDigits,
mp_size  nBignums 
)

Definition at line 589 of file mpmontg.c.

{
  mp_size i;
  unsigned char * endDest = weaved + (nDigits * nBignums * sizeof(mp_digit));

  for (i=0; i < WEAVE_WORD_SIZE; i++) {
    mp_size used = MP_USED(&bignums[i]);
    unsigned char *pSrc   = (unsigned char *)MP_DIGITS(&bignums[i]);
    unsigned char *endSrc = pSrc + (used * sizeof(mp_digit));
    unsigned char *pDest  = weaved + i;

    ARGCHK(MP_SIGN(&bignums[i]) == MP_ZPOS, MP_BADARG);
    ARGCHK(used <= nDigits, MP_BADARG);

    for (; pSrc < endSrc; pSrc++) {
      *pDest = *pSrc;
      pDest += nBignums;
    }
    while (pDest < endDest) {
      *pDest = 0;
      pDest += nBignums;
    }
  }

  return MP_OKAY;
}
mp_err s_mp_mul_mont ( const mp_int a,
const mp_int b,
mp_int c,
mp_mont_modulus mmm 
)

Definition at line 113 of file mpmontg.c.

{
  mp_digit *pb;
  mp_digit m_i;
  mp_err   res;
  mp_size  ib;
  mp_size  useda, usedb;

  ARGCHK(a != NULL && b != NULL && c != NULL, MP_BADARG);

  if (MP_USED(a) < MP_USED(b)) {
    const mp_int *xch = b;  /* switch a and b, to do fewer outer loops */
    b = a;
    a = xch;
  }

  MP_USED(c) = 1; MP_DIGIT(c, 0) = 0;
  ib = MP_USED(a) + MP_MAX(MP_USED(b), MP_USED(&mmm->N)) + 2;
  if((res = s_mp_pad(c, ib)) != MP_OKAY)
    goto CLEANUP;

  useda = MP_USED(a);
  pb = MP_DIGITS(b);
  s_mpv_mul_d(MP_DIGITS(a), useda, *pb++, MP_DIGITS(c));
  s_mp_setz(MP_DIGITS(c) + useda + 1, ib - (useda + 1));
  m_i = MP_DIGIT(c, 0) * mmm->n0prime;
  s_mp_mul_d_add_offset(&mmm->N, m_i, c, 0);

  /* Outer loop:  Digits of b */
  usedb = MP_USED(b);
  for (ib = 1; ib < usedb; ib++) {
    mp_digit b_i    = *pb++;

    /* Inner product:  Digits of a */
    if (b_i)
      s_mpv_mul_d_add_prop(MP_DIGITS(a), useda, b_i, MP_DIGITS(c) + ib);
    m_i = MP_DIGIT(c, ib) * mmm->n0prime;
    s_mp_mul_d_add_offset(&mmm->N, m_i, c, ib);
  }
  if (usedb < MP_USED(&mmm->N)) {
    for (usedb = MP_USED(&mmm->N); ib < usedb; ++ib ) {
      m_i = MP_DIGIT(c, ib) * mmm->n0prime;
      s_mp_mul_d_add_offset(&mmm->N, m_i, c, ib);
    }
  }
  s_mp_clamp(c);
  s_mp_div_2d(c, mmm->b); 
  if (s_mp_cmp(c, &mmm->N) >= 0) {
    MP_CHECKOK( s_mp_sub(c, &mmm->N) );
  }
  res = MP_OKAY;

CLEANUP:
  return res;
}

Here is the call graph for this function:

Here is the caller graph for this function:

mp_err s_mp_redc ( mp_int T,
mp_mont_modulus mmm 
)

Definition at line 80 of file mpmontg.c.

{
  mp_err res;
  mp_size i;

  i = MP_USED(T) + MP_USED(&mmm->N) + 2;
  MP_CHECKOK( s_mp_pad(T, i) );
  for (i = 0; i < MP_USED(&mmm->N); ++i ) {
    mp_digit m_i = MP_DIGIT(T, i) * mmm->n0prime;
    /* T += N * m_i * (MP_RADIX ** i); */
    MP_CHECKOK( s_mp_mul_d_add_offset(&mmm->N, m_i, T, i) );
  }
  s_mp_clamp(T);

  /* T /= R */
  s_mp_div_2d(T, mmm->b); 

  if ((res = s_mp_cmp(T, &mmm->N)) >= 0) {
    /* T = T - N */
    MP_CHECKOK( s_mp_sub(T, &mmm->N) );
#ifdef DEBUG
    if ((res = mp_cmp(T, &mmm->N)) >= 0) {
      res = MP_UNDEF;
      goto CLEANUP;
    }
#endif
  }
  res = MP_OKAY;
CLEANUP:
  return res;
}

Here is the call graph for this function:

Here is the caller graph for this function:

STATIC mp_err s_mp_to_mont ( const mp_int x,
mp_mont_modulus mmm,
mp_int xMont 
)

Definition at line 172 of file mpmontg.c.

{
  mp_err res;

  /* xMont = x * R mod N   where  N is modulus */
  MP_CHECKOK( mpl_lsh(x, xMont, mmm->b) );              /* xMont = x << b */
  MP_CHECKOK( mp_div(xMont, &mmm->N, 0, xMont) );       /*         mod N */
CLEANUP:
  return res;
}

Here is the call graph for this function:

mp_err weave_to_mpi ( mp_int a,
const unsigned char *  pSrc,
mp_size  nDigits,
mp_size  nBignums 
)

Definition at line 624 of file mpmontg.c.

{
  unsigned char *pDest   = (unsigned char *)MP_DIGITS(a);
  unsigned char *endDest = pDest + (nDigits * sizeof(mp_digit));

  MP_SIGN(a) = MP_ZPOS;
  MP_USED(a) = nDigits;

  for (; pDest < endDest; pSrc += nBignums, pDest++) {
    *pDest = *pSrc;
  }
  s_mp_clamp(a);
  return MP_OKAY;
}

Here is the call graph for this function:


Variable Documentation

Definition at line 523 of file mpmontg.c.