1f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project#include <tommath.h> 2f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project#ifdef BN_S_MP_EXPTMOD_C 3f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project/* LibTomMath, multiple-precision integer library -- Tom St Denis 4f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * 5f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * LibTomMath is a library that provides multiple-precision 6f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * integer arithmetic as well as number theoretic functionality. 7f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * 8f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * The library was designed directly after the MPI library by 9f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * Michael Fromberger but has been written from scratch with 10f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * additional optimizations in place. 11f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * 12f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * The library is free for all purposes without any express 13f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * guarantee it works. 14f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * 15f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * Tom St Denis, tomstdenis@gmail.com, http://math.libtomcrypt.com 16f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project */ 17f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project#ifdef MP_LOW_MEM 18f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project #define TAB_SIZE 32 19f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project#else 20f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project #define TAB_SIZE 256 21f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project#endif 22f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 23f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectint s_mp_exptmod (mp_int * G, mp_int * X, mp_int * P, mp_int * Y, int redmode) 24f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project{ 25f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_int M[TAB_SIZE], res, mu; 26f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_digit buf; 27f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project int err, bitbuf, bitcpy, bitcnt, mode, digidx, x, y, winsize; 28f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project int (*redux)(mp_int*,mp_int*,mp_int*); 29f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 30f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* find window size */ 31f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project x = mp_count_bits (X); 32f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if (x <= 7) { 33f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project winsize = 2; 34f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } else if (x <= 36) { 35f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project winsize = 3; 36f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } else if (x <= 140) { 37f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project winsize = 4; 38f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } else if (x <= 450) { 39f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project winsize = 5; 40f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } else if (x <= 1303) { 41f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project winsize = 6; 42f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } else if (x <= 3529) { 43f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project winsize = 7; 44f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } else { 45f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project winsize = 8; 46f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 47f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 48f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project#ifdef MP_LOW_MEM 49f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if (winsize > 5) { 50f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project winsize = 5; 51f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 52f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project#endif 53f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 54f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* init M array */ 55f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* init first cell */ 56f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((err = mp_init(&M[1])) != MP_OKAY) { 57f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project return err; 58f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 59f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 60f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* now init the second half of the array */ 61f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project for (x = 1<<(winsize-1); x < (1 << winsize); x++) { 62f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((err = mp_init(&M[x])) != MP_OKAY) { 63f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project for (y = 1<<(winsize-1); y < x; y++) { 64f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_clear (&M[y]); 65f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 66f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_clear(&M[1]); 67f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project return err; 68f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 69f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 70f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 71f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* create mu, used for Barrett reduction */ 72f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((err = mp_init (&mu)) != MP_OKAY) { 73f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project goto LBL_M; 74f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 75f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 76f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if (redmode == 0) { 77f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((err = mp_reduce_setup (&mu, P)) != MP_OKAY) { 78f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project goto LBL_MU; 79f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 80f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project redux = mp_reduce; 81f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } else { 82f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((err = mp_reduce_2k_setup_l (P, &mu)) != MP_OKAY) { 83f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project goto LBL_MU; 84f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 85f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project redux = mp_reduce_2k_l; 86f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 87f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 88f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* create M table 89f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * 90f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * The M table contains powers of the base, 91f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * e.g. M[x] = G**x mod P 92f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * 93f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * The first half of the table is not 94f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * computed though accept for M[0] and M[1] 95f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project */ 96f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((err = mp_mod (G, P, &M[1])) != MP_OKAY) { 97f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project goto LBL_MU; 98f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 99f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 100f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* compute the value at M[1<<(winsize-1)] by squaring 101f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * M[1] (winsize-1) times 102f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project */ 103f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((err = mp_copy (&M[1], &M[1 << (winsize - 1)])) != MP_OKAY) { 104f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project goto LBL_MU; 105f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 106f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 107f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project for (x = 0; x < (winsize - 1); x++) { 108f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* square it */ 109f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((err = mp_sqr (&M[1 << (winsize - 1)], 110f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project &M[1 << (winsize - 1)])) != MP_OKAY) { 111f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project goto LBL_MU; 112f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 113f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 114f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* reduce modulo P */ 115f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((err = redux (&M[1 << (winsize - 1)], P, &mu)) != MP_OKAY) { 116f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project goto LBL_MU; 117f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 118f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 119f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 120f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* create upper table, that is M[x] = M[x-1] * M[1] (mod P) 121f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * for x = (2**(winsize - 1) + 1) to (2**winsize - 1) 122f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project */ 123f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project for (x = (1 << (winsize - 1)) + 1; x < (1 << winsize); x++) { 124f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((err = mp_mul (&M[x - 1], &M[1], &M[x])) != MP_OKAY) { 125f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project goto LBL_MU; 126f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 127f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((err = redux (&M[x], P, &mu)) != MP_OKAY) { 128f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project goto LBL_MU; 129f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 130f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 131f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 132f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* setup result */ 133f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((err = mp_init (&res)) != MP_OKAY) { 134f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project goto LBL_MU; 135f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 136f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_set (&res, 1); 137f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 138f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* set initial mode and bit cnt */ 139f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mode = 0; 140f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project bitcnt = 1; 141f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project buf = 0; 142f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project digidx = X->used - 1; 143f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project bitcpy = 0; 144f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project bitbuf = 0; 145f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 146f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project for (;;) { 147f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* grab next digit as required */ 148f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if (--bitcnt == 0) { 149f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* if digidx == -1 we are out of digits */ 150f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if (digidx == -1) { 151f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project break; 152f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 153f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* read next digit and reset the bitcnt */ 154f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project buf = X->dp[digidx--]; 155f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project bitcnt = (int) DIGIT_BIT; 156f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 157f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 158f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* grab the next msb from the exponent */ 159f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project y = (buf >> (mp_digit)(DIGIT_BIT - 1)) & 1; 160f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project buf <<= (mp_digit)1; 161f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 162f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* if the bit is zero and mode == 0 then we ignore it 163f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * These represent the leading zero bits before the first 1 bit 164f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * in the exponent. Technically this opt is not required but it 165f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * does lower the # of trivial squaring/reductions used 166f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project */ 167f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if (mode == 0 && y == 0) { 168f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project continue; 169f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 170f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 171f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* if the bit is zero and mode == 1 then we square */ 172f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if (mode == 1 && y == 0) { 173f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((err = mp_sqr (&res, &res)) != MP_OKAY) { 174f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project goto LBL_RES; 175f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 176f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((err = redux (&res, P, &mu)) != MP_OKAY) { 177f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project goto LBL_RES; 178f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 179f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project continue; 180f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 181f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 182f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* else we add it to the window */ 183f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project bitbuf |= (y << (winsize - ++bitcpy)); 184f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mode = 2; 185f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 186f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if (bitcpy == winsize) { 187f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* ok window is filled so square as required and multiply */ 188f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* square first */ 189f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project for (x = 0; x < winsize; x++) { 190f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((err = mp_sqr (&res, &res)) != MP_OKAY) { 191f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project goto LBL_RES; 192f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 193f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((err = redux (&res, P, &mu)) != MP_OKAY) { 194f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project goto LBL_RES; 195f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 196f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 197f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 198f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* then multiply */ 199f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((err = mp_mul (&res, &M[bitbuf], &res)) != MP_OKAY) { 200f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project goto LBL_RES; 201f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 202f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((err = redux (&res, P, &mu)) != MP_OKAY) { 203f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project goto LBL_RES; 204f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 205f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 206f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* empty window and reset */ 207f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project bitcpy = 0; 208f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project bitbuf = 0; 209f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mode = 1; 210f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 211f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 212f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 213f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* if bits remain then square/multiply */ 214f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if (mode == 2 && bitcpy > 0) { 215f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* square then multiply if the bit is set */ 216f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project for (x = 0; x < bitcpy; x++) { 217f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((err = mp_sqr (&res, &res)) != MP_OKAY) { 218f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project goto LBL_RES; 219f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 220f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((err = redux (&res, P, &mu)) != MP_OKAY) { 221f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project goto LBL_RES; 222f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 223f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 224f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project bitbuf <<= 1; 225f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((bitbuf & (1 << winsize)) != 0) { 226f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* then multiply */ 227f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((err = mp_mul (&res, &M[1], &res)) != MP_OKAY) { 228f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project goto LBL_RES; 229f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 230f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((err = redux (&res, P, &mu)) != MP_OKAY) { 231f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project goto LBL_RES; 232f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 233f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 234f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 235f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 236f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 237f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_exch (&res, Y); 238f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project err = MP_OKAY; 239f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectLBL_RES:mp_clear (&res); 240f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectLBL_MU:mp_clear (&mu); 241f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectLBL_M: 242f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_clear(&M[1]); 243f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project for (x = 1<<(winsize-1); x < (1 << winsize); x++) { 244f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_clear (&M[x]); 245f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 246f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project return err; 247f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project} 248f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project#endif 249f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 250f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project/* $Source: /cvs/libtom/libtommath/bn_s_mp_exptmod.c,v $ */ 251f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project/* $Revision: 1.4 $ */ 252f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project/* $Date: 2006/03/31 14:18:44 $ */ 253