Mercurial > dropbear
annotate bn_s_mp_exptmod.c @ 203:e109027b9edf libtommath LTM_DB_0.46 LTM_DB_0.47
Don't remove ~ files on make clean (and find -type was wrong anyway)
| author | Matt Johnston <matt@ucc.asn.au> |
|---|---|
| date | Wed, 11 May 2005 16:27:28 +0000 |
| parents | d8254fc979e9 |
| children |
| rev | line source |
|---|---|
| 142 | 1 #include <tommath.h> |
| 2 #ifdef BN_S_MP_EXPTMOD_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 #ifdef MP_LOW_MEM | |
| 19 #define TAB_SIZE 32 | |
| 20 #else | |
| 21 #define TAB_SIZE 256 | |
| 22 #endif | |
| 23 | |
|
190
d8254fc979e9
Initial import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
142
diff
changeset
|
24 int s_mp_exptmod (mp_int * G, mp_int * X, mp_int * P, mp_int * Y, int redmode) |
| 2 | 25 { |
| 26 mp_int M[TAB_SIZE], res, mu; | |
| 27 mp_digit buf; | |
| 28 int err, bitbuf, bitcpy, bitcnt, mode, digidx, x, y, winsize; | |
|
190
d8254fc979e9
Initial import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
142
diff
changeset
|
29 int (*redux)(mp_int*,mp_int*,mp_int*); |
| 2 | 30 |
| 31 /* find window size */ | |
| 32 x = mp_count_bits (X); | |
| 33 if (x <= 7) { | |
| 34 winsize = 2; | |
| 35 } else if (x <= 36) { | |
| 36 winsize = 3; | |
| 37 } else if (x <= 140) { | |
| 38 winsize = 4; | |
| 39 } else if (x <= 450) { | |
| 40 winsize = 5; | |
| 41 } else if (x <= 1303) { | |
| 42 winsize = 6; | |
| 43 } else if (x <= 3529) { | |
| 44 winsize = 7; | |
| 45 } else { | |
| 46 winsize = 8; | |
| 47 } | |
| 48 | |
| 49 #ifdef MP_LOW_MEM | |
| 50 if (winsize > 5) { | |
| 51 winsize = 5; | |
| 52 } | |
| 53 #endif | |
| 54 | |
| 55 /* init M array */ | |
| 56 /* init first cell */ | |
| 57 if ((err = mp_init(&M[1])) != MP_OKAY) { | |
| 58 return err; | |
| 59 } | |
| 60 | |
| 61 /* now init the second half of the array */ | |
| 62 for (x = 1<<(winsize-1); x < (1 << winsize); x++) { | |
| 63 if ((err = mp_init(&M[x])) != MP_OKAY) { | |
| 64 for (y = 1<<(winsize-1); y < x; y++) { | |
| 65 mp_clear (&M[y]); | |
| 66 } | |
| 67 mp_clear(&M[1]); | |
| 68 return err; | |
| 69 } | |
| 70 } | |
| 71 | |
| 72 /* create mu, used for Barrett reduction */ | |
| 73 if ((err = mp_init (&mu)) != MP_OKAY) { | |
|
190
d8254fc979e9
Initial import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
142
diff
changeset
|
74 goto LBL_M; |
| 2 | 75 } |
|
190
d8254fc979e9
Initial import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
142
diff
changeset
|
76 |
|
d8254fc979e9
Initial import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
142
diff
changeset
|
77 if (redmode == 0) { |
|
d8254fc979e9
Initial import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
142
diff
changeset
|
78 if ((err = mp_reduce_setup (&mu, P)) != MP_OKAY) { |
|
d8254fc979e9
Initial import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
142
diff
changeset
|
79 goto LBL_MU; |
|
d8254fc979e9
Initial import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
142
diff
changeset
|
80 } |
|
d8254fc979e9
Initial import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
142
diff
changeset
|
81 redux = mp_reduce; |
|
d8254fc979e9
Initial import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
142
diff
changeset
|
82 } else { |
|
d8254fc979e9
Initial import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
142
diff
changeset
|
83 if ((err = mp_reduce_2k_setup_l (P, &mu)) != MP_OKAY) { |
|
d8254fc979e9
Initial import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
142
diff
changeset
|
84 goto LBL_MU; |
|
d8254fc979e9
Initial import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
142
diff
changeset
|
85 } |
|
d8254fc979e9
Initial import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
142
diff
changeset
|
86 redux = mp_reduce_2k_l; |
|
d8254fc979e9
Initial import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
142
diff
changeset
|
87 } |
| 2 | 88 |
| 89 /* create M table | |
| 90 * | |
| 91 * The M table contains powers of the base, | |
| 92 * e.g. M[x] = G**x mod P | |
| 93 * | |
| 94 * The first half of the table is not | |
| 95 * computed though accept for M[0] and M[1] | |
| 96 */ | |
| 97 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
|
98 goto LBL_MU; |
| 2 | 99 } |
| 100 | |
| 101 /* compute the value at M[1<<(winsize-1)] by squaring | |
| 102 * M[1] (winsize-1) times | |
| 103 */ | |
| 104 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
|
105 goto LBL_MU; |
| 2 | 106 } |
| 107 | |
| 108 for (x = 0; x < (winsize - 1); x++) { | |
|
190
d8254fc979e9
Initial import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
142
diff
changeset
|
109 /* square it */ |
| 2 | 110 if ((err = mp_sqr (&M[1 << (winsize - 1)], |
| 111 &M[1 << (winsize - 1)])) != MP_OKAY) { | |
|
190
d8254fc979e9
Initial import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
142
diff
changeset
|
112 goto LBL_MU; |
| 2 | 113 } |
|
190
d8254fc979e9
Initial import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
142
diff
changeset
|
114 |
|
d8254fc979e9
Initial import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
142
diff
changeset
|
115 /* reduce modulo P */ |
|
d8254fc979e9
Initial import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
142
diff
changeset
|
116 if ((err = redux (&M[1 << (winsize - 1)], P, &mu)) != MP_OKAY) { |
|
d8254fc979e9
Initial import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
142
diff
changeset
|
117 goto LBL_MU; |
| 2 | 118 } |
| 119 } | |
| 120 | |
| 121 /* create upper table, that is M[x] = M[x-1] * M[1] (mod P) | |
| 122 * for x = (2**(winsize - 1) + 1) to (2**winsize - 1) | |
| 123 */ | |
| 124 for (x = (1 << (winsize - 1)) + 1; x < (1 << winsize); x++) { | |
| 125 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
|
126 goto LBL_MU; |
| 2 | 127 } |
|
190
d8254fc979e9
Initial import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
142
diff
changeset
|
128 if ((err = redux (&M[x], P, &mu)) != MP_OKAY) { |
|
d8254fc979e9
Initial import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
142
diff
changeset
|
129 goto LBL_MU; |
| 2 | 130 } |
| 131 } | |
| 132 | |
| 133 /* setup result */ | |
| 134 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
|
135 goto LBL_MU; |
| 2 | 136 } |
| 137 mp_set (&res, 1); | |
| 138 | |
| 139 /* set initial mode and bit cnt */ | |
| 140 mode = 0; | |
| 141 bitcnt = 1; | |
| 142 buf = 0; | |
| 143 digidx = X->used - 1; | |
| 144 bitcpy = 0; | |
| 145 bitbuf = 0; | |
| 146 | |
| 147 for (;;) { | |
| 148 /* grab next digit as required */ | |
| 149 if (--bitcnt == 0) { | |
| 150 /* if digidx == -1 we are out of digits */ | |
| 151 if (digidx == -1) { | |
| 152 break; | |
| 153 } | |
| 154 /* read next digit and reset the bitcnt */ | |
| 155 buf = X->dp[digidx--]; | |
| 156 bitcnt = (int) DIGIT_BIT; | |
| 157 } | |
| 158 | |
| 159 /* grab the next msb from the exponent */ | |
| 160 y = (buf >> (mp_digit)(DIGIT_BIT - 1)) & 1; | |
| 161 buf <<= (mp_digit)1; | |
| 162 | |
| 163 /* if the bit is zero and mode == 0 then we ignore it | |
| 164 * These represent the leading zero bits before the first 1 bit | |
| 165 * in the exponent. Technically this opt is not required but it | |
| 166 * does lower the # of trivial squaring/reductions used | |
| 167 */ | |
| 168 if (mode == 0 && y == 0) { | |
| 169 continue; | |
| 170 } | |
| 171 | |
| 172 /* if the bit is zero and mode == 1 then we square */ | |
| 173 if (mode == 1 && y == 0) { | |
| 174 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
|
175 goto LBL_RES; |
| 2 | 176 } |
|
190
d8254fc979e9
Initial import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
142
diff
changeset
|
177 if ((err = redux (&res, P, &mu)) != MP_OKAY) { |
|
d8254fc979e9
Initial import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
142
diff
changeset
|
178 goto LBL_RES; |
| 2 | 179 } |
| 180 continue; | |
| 181 } | |
| 182 | |
| 183 /* else we add it to the window */ | |
| 184 bitbuf |= (y << (winsize - ++bitcpy)); | |
| 185 mode = 2; | |
| 186 | |
| 187 if (bitcpy == winsize) { | |
| 188 /* ok window is filled so square as required and multiply */ | |
| 189 /* square first */ | |
| 190 for (x = 0; x < winsize; x++) { | |
| 191 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
|
192 goto LBL_RES; |
| 2 | 193 } |
|
190
d8254fc979e9
Initial import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
142
diff
changeset
|
194 if ((err = redux (&res, P, &mu)) != MP_OKAY) { |
|
d8254fc979e9
Initial import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
142
diff
changeset
|
195 goto LBL_RES; |
| 2 | 196 } |
| 197 } | |
| 198 | |
| 199 /* then multiply */ | |
| 200 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
|
201 goto LBL_RES; |
| 2 | 202 } |
|
190
d8254fc979e9
Initial import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
142
diff
changeset
|
203 if ((err = redux (&res, P, &mu)) != MP_OKAY) { |
|
d8254fc979e9
Initial import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
142
diff
changeset
|
204 goto LBL_RES; |
| 2 | 205 } |
| 206 | |
| 207 /* empty window and reset */ | |
| 208 bitcpy = 0; | |
| 209 bitbuf = 0; | |
| 210 mode = 1; | |
| 211 } | |
| 212 } | |
| 213 | |
| 214 /* if bits remain then square/multiply */ | |
| 215 if (mode == 2 && bitcpy > 0) { | |
| 216 /* square then multiply if the bit is set */ | |
| 217 for (x = 0; x < bitcpy; x++) { | |
| 218 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
|
219 goto LBL_RES; |
| 2 | 220 } |
|
190
d8254fc979e9
Initial import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
142
diff
changeset
|
221 if ((err = redux (&res, P, &mu)) != MP_OKAY) { |
|
d8254fc979e9
Initial import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
142
diff
changeset
|
222 goto LBL_RES; |
| 2 | 223 } |
| 224 | |
| 225 bitbuf <<= 1; | |
| 226 if ((bitbuf & (1 << winsize)) != 0) { | |
| 227 /* then multiply */ | |
| 228 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
|
229 goto LBL_RES; |
| 2 | 230 } |
|
190
d8254fc979e9
Initial import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
142
diff
changeset
|
231 if ((err = redux (&res, P, &mu)) != MP_OKAY) { |
|
d8254fc979e9
Initial import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
142
diff
changeset
|
232 goto LBL_RES; |
| 2 | 233 } |
| 234 } | |
| 235 } | |
| 236 } | |
| 237 | |
| 238 mp_exch (&res, Y); | |
| 239 err = MP_OKAY; | |
|
190
d8254fc979e9
Initial import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
142
diff
changeset
|
240 LBL_RES:mp_clear (&res); |
|
d8254fc979e9
Initial import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
142
diff
changeset
|
241 LBL_MU:mp_clear (&mu); |
|
d8254fc979e9
Initial import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
142
diff
changeset
|
242 LBL_M: |
| 2 | 243 mp_clear(&M[1]); |
| 244 for (x = 1<<(winsize-1); x < (1 << winsize); x++) { | |
| 245 mp_clear (&M[x]); | |
| 246 } | |
| 247 return err; | |
| 248 } | |
| 142 | 249 #endif |