X-Git-Url: http://git.rot13.org/?p=bcm963xx.git;a=blobdiff_plain;f=userapps%2Fopensource%2Fsshd%2Flibtommath%2Fbn_mp_exptmod_fast.c;h=82be9acd37b06b2a3bd3c83ea94a77bc8121cf93;hp=54de53d1e4219af0c6f9ff5bc2bcff9c9ff6db90;hb=57a096f051259ceaefd5977f30d269884e1dd248;hpb=9887430fc6b7c0f8eb8e81de2bfe3bba12d8d4a1 diff --git a/userapps/opensource/sshd/libtommath/bn_mp_exptmod_fast.c b/userapps/opensource/sshd/libtommath/bn_mp_exptmod_fast.c index 54de53d1..82be9acd 100755 --- a/userapps/opensource/sshd/libtommath/bn_mp_exptmod_fast.c +++ b/userapps/opensource/sshd/libtommath/bn_mp_exptmod_fast.c @@ -1,9 +1,11 @@ +#include +#ifdef BN_MP_EXPTMOD_FAST_C /* LibTomMath, multiple-precision integer library -- Tom St Denis * - * LibTomMath is library that provides for multiple-precision + * LibTomMath is a library that provides multiple-precision * integer arithmetic as well as number theoretic functionality. * - * The library is designed directly after the MPI library by + * The library was designed directly after the MPI library by * Michael Fromberger but has been written from scratch with * additional optimizations in place. * @@ -12,25 +14,30 @@ * * Tom St Denis, tomstdenis@iahu.ca, http://math.libtomcrypt.org */ -#include -/* computes Y == G^X mod P, HAC pp.616, Algorithm 14.85 +/* computes Y == G**X mod P, HAC pp.616, Algorithm 14.85 * * Uses a left-to-right k-ary sliding window to compute the modular exponentiation. * The value of k changes based on the size of the exponent. * * Uses Montgomery or Diminished Radix reduction [whichever appropriate] */ -int -mp_exptmod_fast (mp_int * G, mp_int * X, mp_int * P, mp_int * Y, int redmode) + +#ifdef MP_LOW_MEM + #define TAB_SIZE 32 +#else + #define TAB_SIZE 256 +#endif + +int mp_exptmod_fast (mp_int * G, mp_int * X, mp_int * P, mp_int * Y, int redmode) { - mp_int M[256], res; + mp_int M[TAB_SIZE], res; mp_digit buf, mp; int err, bitbuf, bitcpy, bitcnt, mode, digidx, x, y, winsize; - + /* use a pointer to the reduction algorithm. This allows us to use * one of many reduction algorithms without modding the guts of - * the code with if statements everywhere. + * the code with if statements everywhere. */ int (*redux)(mp_int*,mp_int*,mp_digit); @@ -58,94 +65,128 @@ mp_exptmod_fast (mp_int * G, mp_int * X, mp_int * P, mp_int * Y, int redmode) } #endif + /* init M array */ + /* init first cell */ + if ((err = mp_init(&M[1])) != MP_OKAY) { + return err; + } - /* init G array */ - for (x = 0; x < (1 << winsize); x++) { - if ((err = mp_init (&M[x])) != MP_OKAY) { - for (y = 0; y < x; y++) { + /* now init the second half of the array */ + for (x = 1<<(winsize-1); x < (1 << winsize); x++) { + if ((err = mp_init(&M[x])) != MP_OKAY) { + for (y = 1<<(winsize-1); y < x; y++) { mp_clear (&M[y]); } + mp_clear(&M[1]); return err; } } /* determine and setup reduction code */ if (redmode == 0) { +#ifdef BN_MP_MONTGOMERY_SETUP_C /* now setup montgomery */ if ((err = mp_montgomery_setup (P, &mp)) != MP_OKAY) { - goto __M; + goto LBL_M; } - +#else + err = MP_VAL; + goto LBL_M; +#endif + /* automatically pick the comba one if available (saves quite a few calls/ifs) */ +#ifdef BN_FAST_MP_MONTGOMERY_REDUCE_C if (((P->used * 2 + 1) < MP_WARRAY) && P->used < (1 << ((CHAR_BIT * sizeof (mp_word)) - (2 * DIGIT_BIT)))) { redux = fast_mp_montgomery_reduce; - } else { - /* use slower baselien method */ + } else +#endif + { +#ifdef BN_MP_MONTGOMERY_REDUCE_C + /* use slower baseline Montgomery method */ redux = mp_montgomery_reduce; +#else + err = MP_VAL; + goto LBL_M; +#endif } } else if (redmode == 1) { - /* setup DR reduction */ +#if defined(BN_MP_DR_SETUP_C) && defined(BN_MP_DR_REDUCE_C) + /* setup DR reduction for moduli of the form B**k - b */ mp_dr_setup(P, &mp); redux = mp_dr_reduce; +#else + err = MP_VAL; + goto LBL_M; +#endif } else { - /* setup 2k reduction */ +#if defined(BN_MP_REDUCE_2K_SETUP_C) && defined(BN_MP_REDUCE_2K_C) + /* setup DR reduction for moduli of the form 2**k - b */ if ((err = mp_reduce_2k_setup(P, &mp)) != MP_OKAY) { - goto __M; + goto LBL_M; } redux = mp_reduce_2k; +#else + err = MP_VAL; + goto LBL_M; +#endif } /* setup result */ if ((err = mp_init (&res)) != MP_OKAY) { - goto __RES; + goto LBL_M; } /* create M table * - * The M table contains powers of the input base, e.g. M[x] = G^x mod P + * * The first half of the table is not computed though accept for M[0] and M[1] */ if (redmode == 0) { +#ifdef BN_MP_MONTGOMERY_CALC_NORMALIZATION_C /* now we need R mod m */ if ((err = mp_montgomery_calc_normalization (&res, P)) != MP_OKAY) { - goto __RES; + goto LBL_RES; } +#else + err = MP_VAL; + goto LBL_RES; +#endif /* now set M[1] to G * R mod m */ if ((err = mp_mulmod (G, &res, P, &M[1])) != MP_OKAY) { - goto __RES; + goto LBL_RES; } } else { mp_set(&res, 1); if ((err = mp_mod(G, P, &M[1])) != MP_OKAY) { - goto __RES; + goto LBL_RES; } } /* compute the value at M[1<<(winsize-1)] by squaring M[1] (winsize-1) times */ if ((err = mp_copy (&M[1], &M[1 << (winsize - 1)])) != MP_OKAY) { - goto __RES; + goto LBL_RES; } for (x = 0; x < (winsize - 1); x++) { if ((err = mp_sqr (&M[1 << (winsize - 1)], &M[1 << (winsize - 1)])) != MP_OKAY) { - goto __RES; + goto LBL_RES; } if ((err = redux (&M[1 << (winsize - 1)], P, mp)) != MP_OKAY) { - goto __RES; + goto LBL_RES; } } /* create upper table */ for (x = (1 << (winsize - 1)) + 1; x < (1 << winsize); x++) { if ((err = mp_mul (&M[x - 1], &M[1], &M[x])) != MP_OKAY) { - goto __RES; + goto LBL_RES; } if ((err = redux (&M[x], P, mp)) != MP_OKAY) { - goto __RES; + goto LBL_RES; } } @@ -160,15 +201,17 @@ mp_exptmod_fast (mp_int * G, mp_int * X, mp_int * P, mp_int * Y, int redmode) for (;;) { /* grab next digit as required */ if (--bitcnt == 0) { + /* if digidx == -1 we are out of digits so break */ if (digidx == -1) { break; } - buf = X->dp[digidx--]; - bitcnt = (int) DIGIT_BIT; + /* read next digit and reset bitcnt */ + buf = X->dp[digidx--]; + bitcnt = (int)DIGIT_BIT; } /* grab the next msb from the exponent */ - y = (mp_digit)(buf >> (DIGIT_BIT - 1)) & 1; + y = (mp_digit)(buf >> (DIGIT_BIT - 1)) & 1; buf <<= (mp_digit)1; /* if the bit is zero and mode == 0 then we ignore it @@ -183,42 +226,42 @@ mp_exptmod_fast (mp_int * G, mp_int * X, mp_int * P, mp_int * Y, int redmode) /* if the bit is zero and mode == 1 then we square */ if (mode == 1 && y == 0) { if ((err = mp_sqr (&res, &res)) != MP_OKAY) { - goto __RES; + goto LBL_RES; } if ((err = redux (&res, P, mp)) != MP_OKAY) { - goto __RES; + goto LBL_RES; } continue; } /* else we add it to the window */ bitbuf |= (y << (winsize - ++bitcpy)); - mode = 2; + mode = 2; if (bitcpy == winsize) { /* ok window is filled so square as required and multiply */ /* square first */ for (x = 0; x < winsize; x++) { if ((err = mp_sqr (&res, &res)) != MP_OKAY) { - goto __RES; + goto LBL_RES; } if ((err = redux (&res, P, mp)) != MP_OKAY) { - goto __RES; + goto LBL_RES; } } /* then multiply */ if ((err = mp_mul (&res, &M[bitbuf], &res)) != MP_OKAY) { - goto __RES; + goto LBL_RES; } if ((err = redux (&res, P, mp)) != MP_OKAY) { - goto __RES; + goto LBL_RES; } /* empty window and reset */ bitcpy = 0; bitbuf = 0; - mode = 1; + mode = 1; } } @@ -227,38 +270,48 @@ mp_exptmod_fast (mp_int * G, mp_int * X, mp_int * P, mp_int * Y, int redmode) /* square then multiply if the bit is set */ for (x = 0; x < bitcpy; x++) { if ((err = mp_sqr (&res, &res)) != MP_OKAY) { - goto __RES; + goto LBL_RES; } if ((err = redux (&res, P, mp)) != MP_OKAY) { - goto __RES; + goto LBL_RES; } + /* get next bit of the window */ bitbuf <<= 1; if ((bitbuf & (1 << winsize)) != 0) { /* then multiply */ if ((err = mp_mul (&res, &M[1], &res)) != MP_OKAY) { - goto __RES; + goto LBL_RES; } if ((err = redux (&res, P, mp)) != MP_OKAY) { - goto __RES; + goto LBL_RES; } } } } if (redmode == 0) { - /* fixup result if Montgomery reduction is used */ - if ((err = mp_montgomery_reduce (&res, P, mp)) != MP_OKAY) { - goto __RES; + /* fixup result if Montgomery reduction is used + * recall that any value in a Montgomery system is + * actually multiplied by R mod n. So we have + * to reduce one more time to cancel out the factor + * of R. + */ + if ((err = redux(&res, P, mp)) != MP_OKAY) { + goto LBL_RES; } } + /* swap res with Y */ mp_exch (&res, Y); err = MP_OKAY; -__RES:mp_clear (&res); -__M: - for (x = 0; x < (1 << winsize); x++) { +LBL_RES:mp_clear (&res); +LBL_M: + mp_clear(&M[1]); + for (x = 1<<(winsize-1); x < (1 << winsize); x++) { mp_clear (&M[x]); } return err; } +#endif +