Mercurial > dropbear
annotate bn_mp_exptmod_fast.c @ 202:d7f5a681fa23 libtommath
Update Makefile.in for dropbear
| author | Matt Johnston <matt@ucc.asn.au> |
|---|---|
| date | Wed, 11 May 2005 16:25:34 +0000 |
| parents | d8254fc979e9 |
| children |
| rev | line source |
|---|---|
| 142 | 1 #include <tommath.h> |
| 2 #ifdef BN_MP_EXPTMOD_FAST_C | |
| 2 | 3 /* LibTomMath, multiple-precision integer library -- Tom St Denis |
| 4 * | |
| 5 * LibTomMath is a library that provides multiple-precision | |
| 6 * integer arithmetic as well as number theoretic functionality. | |
| 7 * | |
| 8 * The library was designed directly after the MPI library by | |
| 9 * Michael Fromberger but has been written from scratch with | |
| 10 * additional optimizations in place. | |
| 11 * | |
| 12 * The library is free for all purposes without any express | |
| 13 * guarantee it works. | |
| 14 * | |
| 15 * Tom St Denis, [email protected], http://math.libtomcrypt.org | |
| 16 */ | |
| 17 | |
| 18 /* computes Y == G**X mod P, HAC pp.616, Algorithm 14.85 | |
| 19 * | |
| 20 * Uses a left-to-right k-ary sliding window to compute the modular exponentiation. | |
| 21 * The value of k changes based on the size of the exponent. | |
| 22 * | |
| 23 * Uses Montgomery or Diminished Radix reduction [whichever appropriate] | |
| 24 */ | |
| 25 | |
| 26 #ifdef MP_LOW_MEM | |
| 27 #define TAB_SIZE 32 | |
| 28 #else | |
| 29 #define TAB_SIZE 256 | |
| 30 #endif | |
| 31 | |
|
190
d8254fc979e9
Initial import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
142
diff
changeset
|
32 int mp_exptmod_fast (mp_int * G, mp_int * X, mp_int * P, mp_int * Y, int redmode) |
| 2 | 33 { |
| 34 mp_int M[TAB_SIZE], res; | |
| 35 mp_digit buf, mp; | |
| 36 int err, bitbuf, bitcpy, bitcnt, mode, digidx, x, y, winsize; | |
| 37 | |
| 38 /* use a pointer to the reduction algorithm. This allows us to use | |
| 39 * one of many reduction algorithms without modding the guts of | |
| 40 * the code with if statements everywhere. | |
| 41 */ | |
| 42 int (*redux)(mp_int*,mp_int*,mp_digit); | |
| 43 | |
| 44 /* find window size */ | |
| 45 x = mp_count_bits (X); | |
| 46 if (x <= 7) { | |
| 47 winsize = 2; | |
| 48 } else if (x <= 36) { | |
| 49 winsize = 3; | |
| 50 } else if (x <= 140) { | |
| 51 winsize = 4; | |
| 52 } else if (x <= 450) { | |
| 53 winsize = 5; | |
| 54 } else if (x <= 1303) { | |
| 55 winsize = 6; | |
| 56 } else if (x <= 3529) { | |
| 57 winsize = 7; | |
| 58 } else { | |
| 59 winsize = 8; | |
| 60 } | |
| 61 | |
| 62 #ifdef MP_LOW_MEM | |
| 63 if (winsize > 5) { | |
| 64 winsize = 5; | |
| 65 } | |
| 66 #endif | |
| 67 | |
| 68 /* init M array */ | |
| 69 /* init first cell */ | |
| 70 if ((err = mp_init(&M[1])) != MP_OKAY) { | |
| 71 return err; | |
| 72 } | |
| 73 | |
| 74 /* now init the second half of the array */ | |
| 75 for (x = 1<<(winsize-1); x < (1 << winsize); x++) { | |
| 76 if ((err = mp_init(&M[x])) != MP_OKAY) { | |
| 77 for (y = 1<<(winsize-1); y < x; y++) { | |
| 78 mp_clear (&M[y]); | |
| 79 } | |
| 80 mp_clear(&M[1]); | |
| 81 return err; | |
| 82 } | |
| 83 } | |
| 84 | |
| 85 /* determine and setup reduction code */ | |
| 86 if (redmode == 0) { | |
| 142 | 87 #ifdef BN_MP_MONTGOMERY_SETUP_C |
| 2 | 88 /* now setup montgomery */ |
| 89 if ((err = mp_montgomery_setup (P, &mp)) != MP_OKAY) { | |
|
190
d8254fc979e9
Initial import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
142
diff
changeset
|
90 goto LBL_M; |
| 2 | 91 } |
| 142 | 92 #else |
| 93 err = MP_VAL; | |
|
190
d8254fc979e9
Initial import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
142
diff
changeset
|
94 goto LBL_M; |
| 142 | 95 #endif |
| 2 | 96 |
| 97 /* automatically pick the comba one if available (saves quite a few calls/ifs) */ | |
| 142 | 98 #ifdef BN_FAST_MP_MONTGOMERY_REDUCE_C |
| 2 | 99 if (((P->used * 2 + 1) < MP_WARRAY) && |
| 100 P->used < (1 << ((CHAR_BIT * sizeof (mp_word)) - (2 * DIGIT_BIT)))) { | |
| 101 redux = fast_mp_montgomery_reduce; | |
| 142 | 102 } else |
| 103 #endif | |
| 104 { | |
| 105 #ifdef BN_MP_MONTGOMERY_REDUCE_C | |
| 2 | 106 /* use slower baseline Montgomery method */ |
| 107 redux = mp_montgomery_reduce; | |
| 142 | 108 #else |
| 109 err = MP_VAL; | |
|
190
d8254fc979e9
Initial import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
142
diff
changeset
|
110 goto LBL_M; |
| 142 | 111 #endif |
| 2 | 112 } |
| 113 } else if (redmode == 1) { | |
| 142 | 114 #if defined(BN_MP_DR_SETUP_C) && defined(BN_MP_DR_REDUCE_C) |
| 2 | 115 /* setup DR reduction for moduli of the form B**k - b */ |
| 116 mp_dr_setup(P, &mp); | |
| 117 redux = mp_dr_reduce; | |
| 142 | 118 #else |
| 119 err = MP_VAL; | |
|
190
d8254fc979e9
Initial import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
142
diff
changeset
|
120 goto LBL_M; |
| 142 | 121 #endif |
| 2 | 122 } else { |
| 142 | 123 #if defined(BN_MP_REDUCE_2K_SETUP_C) && defined(BN_MP_REDUCE_2K_C) |
| 2 | 124 /* setup DR reduction for moduli of the form 2**k - b */ |
| 125 if ((err = mp_reduce_2k_setup(P, &mp)) != MP_OKAY) { | |
|
190
d8254fc979e9
Initial import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
142
diff
changeset
|
126 goto LBL_M; |
| 2 | 127 } |
| 128 redux = mp_reduce_2k; | |
| 142 | 129 #else |
| 130 err = MP_VAL; | |
|
190
d8254fc979e9
Initial import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
142
diff
changeset
|
131 goto LBL_M; |
| 142 | 132 #endif |
| 2 | 133 } |
| 134 | |
| 135 /* setup result */ | |
| 136 if ((err = mp_init (&res)) != MP_OKAY) { | |
|
190
d8254fc979e9
Initial import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
142
diff
changeset
|
137 goto LBL_M; |
| 2 | 138 } |
| 139 | |
| 140 /* create M table | |
| 141 * | |
| 142 | 142 |
| 2 | 143 * |
| 144 * The first half of the table is not computed though accept for M[0] and M[1] | |
| 145 */ | |
| 146 | |
| 147 if (redmode == 0) { | |
| 142 | 148 #ifdef BN_MP_MONTGOMERY_CALC_NORMALIZATION_C |
| 2 | 149 /* now we need R mod m */ |
| 150 if ((err = mp_montgomery_calc_normalization (&res, P)) != MP_OKAY) { | |
|
190
d8254fc979e9
Initial import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
142
diff
changeset
|
151 goto LBL_RES; |
| 2 | 152 } |
| 142 | 153 #else |
| 154 err = MP_VAL; | |
|
190
d8254fc979e9
Initial import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
142
diff
changeset
|
155 goto LBL_RES; |
| 142 | 156 #endif |
| 2 | 157 |
| 158 /* now set M[1] to G * R mod m */ | |
| 159 if ((err = mp_mulmod (G, &res, P, &M[1])) != MP_OKAY) { | |
|
190
d8254fc979e9
Initial import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
142
diff
changeset
|
160 goto LBL_RES; |
| 2 | 161 } |
| 162 } else { | |
| 163 mp_set(&res, 1); | |
| 164 if ((err = mp_mod(G, P, &M[1])) != MP_OKAY) { | |
|
190
d8254fc979e9
Initial import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
142
diff
changeset
|
165 goto LBL_RES; |
| 2 | 166 } |
| 167 } | |
| 168 | |
| 169 /* compute the value at M[1<<(winsize-1)] by squaring M[1] (winsize-1) times */ | |
| 170 if ((err = mp_copy (&M[1], &M[1 << (winsize - 1)])) != MP_OKAY) { | |
|
190
d8254fc979e9
Initial import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
142
diff
changeset
|
171 goto LBL_RES; |
| 2 | 172 } |
| 173 | |
| 174 for (x = 0; x < (winsize - 1); x++) { | |
| 175 if ((err = mp_sqr (&M[1 << (winsize - 1)], &M[1 << (winsize - 1)])) != MP_OKAY) { | |
|
190
d8254fc979e9
Initial import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
142
diff
changeset
|
176 goto LBL_RES; |
| 2 | 177 } |
| 178 if ((err = redux (&M[1 << (winsize - 1)], P, mp)) != MP_OKAY) { | |
|
190
d8254fc979e9
Initial import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
142
diff
changeset
|
179 goto LBL_RES; |
| 2 | 180 } |
| 181 } | |
| 182 | |
| 183 /* create upper table */ | |
| 184 for (x = (1 << (winsize - 1)) + 1; x < (1 << winsize); x++) { | |
| 185 if ((err = mp_mul (&M[x - 1], &M[1], &M[x])) != MP_OKAY) { | |
|
190
d8254fc979e9
Initial import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
142
diff
changeset
|
186 goto LBL_RES; |
| 2 | 187 } |
| 188 if ((err = redux (&M[x], P, mp)) != MP_OKAY) { | |
|
190
d8254fc979e9
Initial import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
142
diff
changeset
|
189 goto LBL_RES; |
| 2 | 190 } |
| 191 } | |
| 192 | |
| 193 /* set initial mode and bit cnt */ | |
| 194 mode = 0; | |
| 195 bitcnt = 1; | |
| 196 buf = 0; | |
| 197 digidx = X->used - 1; | |
| 198 bitcpy = 0; | |
| 199 bitbuf = 0; | |
| 200 | |
| 201 for (;;) { | |
| 202 /* grab next digit as required */ | |
| 203 if (--bitcnt == 0) { | |
| 204 /* if digidx == -1 we are out of digits so break */ | |
| 205 if (digidx == -1) { | |
| 206 break; | |
| 207 } | |
| 208 /* read next digit and reset bitcnt */ | |
| 209 buf = X->dp[digidx--]; | |
| 210 bitcnt = (int)DIGIT_BIT; | |
| 211 } | |
| 212 | |
| 213 /* grab the next msb from the exponent */ | |
| 214 y = (mp_digit)(buf >> (DIGIT_BIT - 1)) & 1; | |
| 215 buf <<= (mp_digit)1; | |
| 216 | |
| 217 /* if the bit is zero and mode == 0 then we ignore it | |
| 218 * These represent the leading zero bits before the first 1 bit | |
| 219 * in the exponent. Technically this opt is not required but it | |
| 220 * does lower the # of trivial squaring/reductions used | |
| 221 */ | |
| 222 if (mode == 0 && y == 0) { | |
| 223 continue; | |
| 224 } | |
| 225 | |
| 226 /* if the bit is zero and mode == 1 then we square */ | |
| 227 if (mode == 1 && y == 0) { | |
| 228 if ((err = mp_sqr (&res, &res)) != MP_OKAY) { | |
|
190
d8254fc979e9
Initial import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
142
diff
changeset
|
229 goto LBL_RES; |
| 2 | 230 } |
| 231 if ((err = redux (&res, P, mp)) != MP_OKAY) { | |
|
190
d8254fc979e9
Initial import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
142
diff
changeset
|
232 goto LBL_RES; |
| 2 | 233 } |
| 234 continue; | |
| 235 } | |
| 236 | |
| 237 /* else we add it to the window */ | |
| 238 bitbuf |= (y << (winsize - ++bitcpy)); | |
| 239 mode = 2; | |
| 240 | |
| 241 if (bitcpy == winsize) { | |
| 242 /* ok window is filled so square as required and multiply */ | |
| 243 /* square first */ | |
| 244 for (x = 0; x < winsize; x++) { | |
| 245 if ((err = mp_sqr (&res, &res)) != MP_OKAY) { | |
|
190
d8254fc979e9
Initial import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
142
diff
changeset
|
246 goto LBL_RES; |
| 2 | 247 } |
| 248 if ((err = redux (&res, P, mp)) != MP_OKAY) { | |
|
190
d8254fc979e9
Initial import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
142
diff
changeset
|
249 goto LBL_RES; |
| 2 | 250 } |
| 251 } | |
| 252 | |
| 253 /* then multiply */ | |
| 254 if ((err = mp_mul (&res, &M[bitbuf], &res)) != MP_OKAY) { | |
|
190
d8254fc979e9
Initial import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
142
diff
changeset
|
255 goto LBL_RES; |
| 2 | 256 } |
| 257 if ((err = redux (&res, P, mp)) != MP_OKAY) { | |
|
190
d8254fc979e9
Initial import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
142
diff
changeset
|
258 goto LBL_RES; |
| 2 | 259 } |
| 260 | |
| 261 /* empty window and reset */ | |
| 262 bitcpy = 0; | |
| 263 bitbuf = 0; | |
| 264 mode = 1; | |
| 265 } | |
| 266 } | |
| 267 | |
| 268 /* if bits remain then square/multiply */ | |
| 269 if (mode == 2 && bitcpy > 0) { | |
| 270 /* square then multiply if the bit is set */ | |
| 271 for (x = 0; x < bitcpy; x++) { | |
| 272 if ((err = mp_sqr (&res, &res)) != MP_OKAY) { | |
|
190
d8254fc979e9
Initial import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
142
diff
changeset
|
273 goto LBL_RES; |
| 2 | 274 } |
| 275 if ((err = redux (&res, P, mp)) != MP_OKAY) { | |
|
190
d8254fc979e9
Initial import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
142
diff
changeset
|
276 goto LBL_RES; |
| 2 | 277 } |
| 278 | |
| 279 /* get next bit of the window */ | |
| 280 bitbuf <<= 1; | |
| 281 if ((bitbuf & (1 << winsize)) != 0) { | |
| 282 /* then multiply */ | |
| 283 if ((err = mp_mul (&res, &M[1], &res)) != MP_OKAY) { | |
|
190
d8254fc979e9
Initial import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
142
diff
changeset
|
284 goto LBL_RES; |
| 2 | 285 } |
| 286 if ((err = redux (&res, P, mp)) != MP_OKAY) { | |
|
190
d8254fc979e9
Initial import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
142
diff
changeset
|
287 goto LBL_RES; |
| 2 | 288 } |
| 289 } | |
| 290 } | |
| 291 } | |
| 292 | |
| 293 if (redmode == 0) { | |
| 294 /* fixup result if Montgomery reduction is used | |
| 295 * recall that any value in a Montgomery system is | |
| 296 * actually multiplied by R mod n. So we have | |
| 297 * to reduce one more time to cancel out the factor | |
| 298 * of R. | |
| 299 */ | |
| 142 | 300 if ((err = redux(&res, P, mp)) != MP_OKAY) { |
|
190
d8254fc979e9
Initial import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
142
diff
changeset
|
301 goto LBL_RES; |
| 2 | 302 } |
| 303 } | |
| 304 | |
| 305 /* swap res with Y */ | |
| 306 mp_exch (&res, Y); | |
| 307 err = MP_OKAY; | |
|
190
d8254fc979e9
Initial import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
142
diff
changeset
|
308 LBL_RES:mp_clear (&res); |
|
d8254fc979e9
Initial import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
142
diff
changeset
|
309 LBL_M: |
| 2 | 310 mp_clear(&M[1]); |
| 311 for (x = 1<<(winsize-1); x < (1 << winsize); x++) { | |
| 312 mp_clear (&M[x]); | |
| 313 } | |
| 314 return err; | |
| 315 } | |
| 142 | 316 #endif |
| 317 |