Mercurial > dropbear

comparison bn_mp_exptmod_fast.c @ 190:d8254fc979e9 libtommath-orig LTM_0.35

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Initial import of libtommath 0.35
author Matt Johnston <matt@ucc.asn.au>
date Fri, 06 May 2005 08:59:30 +0000
parents d29b64170cf0
children
comparison
equal deleted inserted replaced
142:d29b64170cf0 190:d8254fc979e9
27 #define TAB_SIZE 32 27 #define TAB_SIZE 32
28 #else 28 #else
29 #define TAB_SIZE 256 29 #define TAB_SIZE 256
30 #endif 30 #endif
31 31
32 int 32 int mp_exptmod_fast (mp_int * G, mp_int * X, mp_int * P, mp_int * Y, int redmode)
33 mp_exptmod_fast (mp_int * G, mp_int * X, mp_int * P, mp_int * Y, int redmode)
34 { 33 {
35 mp_int M[TAB_SIZE], res; 34 mp_int M[TAB_SIZE], res;
36 mp_digit buf, mp; 35 mp_digit buf, mp;
37 int err, bitbuf, bitcpy, bitcnt, mode, digidx, x, y, winsize; 36 int err, bitbuf, bitcpy, bitcnt, mode, digidx, x, y, winsize;
38 37
86 /* determine and setup reduction code */ 85 /* determine and setup reduction code */
87 if (redmode == 0) { 86 if (redmode == 0) {
88 #ifdef BN_MP_MONTGOMERY_SETUP_C 87 #ifdef BN_MP_MONTGOMERY_SETUP_C
89 /* now setup montgomery */ 88 /* now setup montgomery */
90 if ((err = mp_montgomery_setup (P, &mp)) != MP_OKAY) { 89 if ((err = mp_montgomery_setup (P, &mp)) != MP_OKAY) {
91 goto __M; 90 goto LBL_M;
92 } 91 }
93 #else 92 #else
94 err = MP_VAL; 93 err = MP_VAL;
95 goto __M; 94 goto LBL_M;
96 #endif 95 #endif
97 96
98 /* automatically pick the comba one if available (saves quite a few calls/ifs) */ 97 /* automatically pick the comba one if available (saves quite a few calls/ifs) */
99 #ifdef BN_FAST_MP_MONTGOMERY_REDUCE_C 98 #ifdef BN_FAST_MP_MONTGOMERY_REDUCE_C
100 if (((P->used * 2 + 1) < MP_WARRAY) && 99 if (((P->used * 2 + 1) < MP_WARRAY) &&
106 #ifdef BN_MP_MONTGOMERY_REDUCE_C 105 #ifdef BN_MP_MONTGOMERY_REDUCE_C
107 /* use slower baseline Montgomery method */ 106 /* use slower baseline Montgomery method */
108 redux = mp_montgomery_reduce; 107 redux = mp_montgomery_reduce;
109 #else 108 #else
110 err = MP_VAL; 109 err = MP_VAL;
111 goto __M; 110 goto LBL_M;
112 #endif 111 #endif
113 } 112 }
114 } else if (redmode == 1) { 113 } else if (redmode == 1) {
115 #if defined(BN_MP_DR_SETUP_C) && defined(BN_MP_DR_REDUCE_C) 114 #if defined(BN_MP_DR_SETUP_C) && defined(BN_MP_DR_REDUCE_C)
116 /* setup DR reduction for moduli of the form B**k - b */ 115 /* setup DR reduction for moduli of the form B**k - b */
117 mp_dr_setup(P, &mp); 116 mp_dr_setup(P, &mp);
118 redux = mp_dr_reduce; 117 redux = mp_dr_reduce;
119 #else 118 #else
120 err = MP_VAL; 119 err = MP_VAL;
121 goto __M; 120 goto LBL_M;
122 #endif 121 #endif
123 } else { 122 } else {
124 #if defined(BN_MP_REDUCE_2K_SETUP_C) && defined(BN_MP_REDUCE_2K_C) 123 #if defined(BN_MP_REDUCE_2K_SETUP_C) && defined(BN_MP_REDUCE_2K_C)
125 /* setup DR reduction for moduli of the form 2**k - b */ 124 /* setup DR reduction for moduli of the form 2**k - b */
126 if ((err = mp_reduce_2k_setup(P, &mp)) != MP_OKAY) { 125 if ((err = mp_reduce_2k_setup(P, &mp)) != MP_OKAY) {
127 goto __M; 126 goto LBL_M;
128 } 127 }
129 redux = mp_reduce_2k; 128 redux = mp_reduce_2k;
130 #else 129 #else
131 err = MP_VAL; 130 err = MP_VAL;
132 goto __M; 131 goto LBL_M;
133 #endif 132 #endif
134 } 133 }
135 134
136 /* setup result */ 135 /* setup result */
137 if ((err = mp_init (&res)) != MP_OKAY) { 136 if ((err = mp_init (&res)) != MP_OKAY) {
138 goto __M; 137 goto LBL_M;
139 } 138 }
140 139
141 /* create M table 140 /* create M table
142 * 141 *
143 142
147 146
148 if (redmode == 0) { 147 if (redmode == 0) {
149 #ifdef BN_MP_MONTGOMERY_CALC_NORMALIZATION_C 148 #ifdef BN_MP_MONTGOMERY_CALC_NORMALIZATION_C
150 /* now we need R mod m */ 149 /* now we need R mod m */
151 if ((err = mp_montgomery_calc_normalization (&res, P)) != MP_OKAY) { 150 if ((err = mp_montgomery_calc_normalization (&res, P)) != MP_OKAY) {
152 goto __RES; 151 goto LBL_RES;
153 } 152 }
154 #else 153 #else
155 err = MP_VAL; 154 err = MP_VAL;
156 goto __RES; 155 goto LBL_RES;
157 #endif 156 #endif
158 157
159 /* now set M[1] to G * R mod m */ 158 /* now set M[1] to G * R mod m */
160 if ((err = mp_mulmod (G, &res, P, &M[1])) != MP_OKAY) { 159 if ((err = mp_mulmod (G, &res, P, &M[1])) != MP_OKAY) {
161 goto __RES; 160 goto LBL_RES;
162 } 161 }
163 } else { 162 } else {
164 mp_set(&res, 1); 163 mp_set(&res, 1);
165 if ((err = mp_mod(G, P, &M[1])) != MP_OKAY) { 164 if ((err = mp_mod(G, P, &M[1])) != MP_OKAY) {
166 goto __RES; 165 goto LBL_RES;
167 } 166 }
168 } 167 }
169 168
170 /* compute the value at M[1<<(winsize-1)] by squaring M[1] (winsize-1) times */ 169 /* compute the value at M[1<<(winsize-1)] by squaring M[1] (winsize-1) times */
171 if ((err = mp_copy (&M[1], &M[1 << (winsize - 1)])) != MP_OKAY) { 170 if ((err = mp_copy (&M[1], &M[1 << (winsize - 1)])) != MP_OKAY) {
172 goto __RES; 171 goto LBL_RES;
173 } 172 }
174 173
175 for (x = 0; x < (winsize - 1); x++) { 174 for (x = 0; x < (winsize - 1); x++) {
176 if ((err = mp_sqr (&M[1 << (winsize - 1)], &M[1 << (winsize - 1)])) != MP_OKAY) { 175 if ((err = mp_sqr (&M[1 << (winsize - 1)], &M[1 << (winsize - 1)])) != MP_OKAY) {
177 goto __RES; 176 goto LBL_RES;
178 } 177 }
179 if ((err = redux (&M[1 << (winsize - 1)], P, mp)) != MP_OKAY) { 178 if ((err = redux (&M[1 << (winsize - 1)], P, mp)) != MP_OKAY) {
180 goto __RES; 179 goto LBL_RES;
181 } 180 }
182 } 181 }
183 182
184 /* create upper table */ 183 /* create upper table */
185 for (x = (1 << (winsize - 1)) + 1; x < (1 << winsize); x++) { 184 for (x = (1 << (winsize - 1)) + 1; x < (1 << winsize); x++) {
186 if ((err = mp_mul (&M[x - 1], &M[1], &M[x])) != MP_OKAY) { 185 if ((err = mp_mul (&M[x - 1], &M[1], &M[x])) != MP_OKAY) {
187 goto __RES; 186 goto LBL_RES;
188 } 187 }
189 if ((err = redux (&M[x], P, mp)) != MP_OKAY) { 188 if ((err = redux (&M[x], P, mp)) != MP_OKAY) {
190 goto __RES; 189 goto LBL_RES;
191 } 190 }
192 } 191 }
193 192
194 /* set initial mode and bit cnt */ 193 /* set initial mode and bit cnt */
195 mode = 0; 194 mode = 0;
225 } 224 }
226 225
227 /* if the bit is zero and mode == 1 then we square */ 226 /* if the bit is zero and mode == 1 then we square */
228 if (mode == 1 && y == 0) { 227 if (mode == 1 && y == 0) {
229 if ((err = mp_sqr (&res, &res)) != MP_OKAY) { 228 if ((err = mp_sqr (&res, &res)) != MP_OKAY) {
230 goto __RES; 229 goto LBL_RES;
231 } 230 }
232 if ((err = redux (&res, P, mp)) != MP_OKAY) { 231 if ((err = redux (&res, P, mp)) != MP_OKAY) {
233 goto __RES; 232 goto LBL_RES;
234 } 233 }
235 continue; 234 continue;
236 } 235 }
237 236
238 /* else we add it to the window */ 237 /* else we add it to the window */
242 if (bitcpy == winsize) { 241 if (bitcpy == winsize) {
243 /* ok window is filled so square as required and multiply */ 242 /* ok window is filled so square as required and multiply */
244 /* square first */ 243 /* square first */
245 for (x = 0; x < winsize; x++) { 244 for (x = 0; x < winsize; x++) {
246 if ((err = mp_sqr (&res, &res)) != MP_OKAY) { 245 if ((err = mp_sqr (&res, &res)) != MP_OKAY) {
247 goto __RES; 246 goto LBL_RES;
248 } 247 }
249 if ((err = redux (&res, P, mp)) != MP_OKAY) { 248 if ((err = redux (&res, P, mp)) != MP_OKAY) {
250 goto __RES; 249 goto LBL_RES;
251 } 250 }
252 } 251 }
253 252
254 /* then multiply */ 253 /* then multiply */
255 if ((err = mp_mul (&res, &M[bitbuf], &res)) != MP_OKAY) { 254 if ((err = mp_mul (&res, &M[bitbuf], &res)) != MP_OKAY) {
256 goto __RES; 255 goto LBL_RES;
257 } 256 }
258 if ((err = redux (&res, P, mp)) != MP_OKAY) { 257 if ((err = redux (&res, P, mp)) != MP_OKAY) {
259 goto __RES; 258 goto LBL_RES;
260 } 259 }
261 260
262 /* empty window and reset */ 261 /* empty window and reset */
263 bitcpy = 0; 262 bitcpy = 0;
264 bitbuf = 0; 263 bitbuf = 0;
269 /* if bits remain then square/multiply */ 268 /* if bits remain then square/multiply */
270 if (mode == 2 && bitcpy > 0) { 269 if (mode == 2 && bitcpy > 0) {
271 /* square then multiply if the bit is set */ 270 /* square then multiply if the bit is set */
272 for (x = 0; x < bitcpy; x++) { 271 for (x = 0; x < bitcpy; x++) {
273 if ((err = mp_sqr (&res, &res)) != MP_OKAY) { 272 if ((err = mp_sqr (&res, &res)) != MP_OKAY) {
274 goto __RES; 273 goto LBL_RES;
275 } 274 }
276 if ((err = redux (&res, P, mp)) != MP_OKAY) { 275 if ((err = redux (&res, P, mp)) != MP_OKAY) {
277 goto __RES; 276 goto LBL_RES;
278 } 277 }
279 278
280 /* get next bit of the window */ 279 /* get next bit of the window */
281 bitbuf <<= 1; 280 bitbuf <<= 1;
282 if ((bitbuf & (1 << winsize)) != 0) { 281 if ((bitbuf & (1 << winsize)) != 0) {
283 /* then multiply */ 282 /* then multiply */
284 if ((err = mp_mul (&res, &M[1], &res)) != MP_OKAY) { 283 if ((err = mp_mul (&res, &M[1], &res)) != MP_OKAY) {
285 goto __RES; 284 goto LBL_RES;
286 } 285 }
287 if ((err = redux (&res, P, mp)) != MP_OKAY) { 286 if ((err = redux (&res, P, mp)) != MP_OKAY) {
288 goto __RES; 287 goto LBL_RES;
289 } 288 }
290 } 289 }
291 } 290 }
292 } 291 }
293 292
297 * actually multiplied by R mod n. So we have 296 * actually multiplied by R mod n. So we have
298 * to reduce one more time to cancel out the factor 297 * to reduce one more time to cancel out the factor
299 * of R. 298 * of R.
300 */ 299 */
301 if ((err = redux(&res, P, mp)) != MP_OKAY) { 300 if ((err = redux(&res, P, mp)) != MP_OKAY) {
302 goto __RES; 301 goto LBL_RES;
303 } 302 }
304 } 303 }
305 304
306 /* swap res with Y */ 305 /* swap res with Y */
307 mp_exch (&res, Y); 306 mp_exch (&res, Y);
308 err = MP_OKAY; 307 err = MP_OKAY;
309 __RES:mp_clear (&res); 308 LBL_RES:mp_clear (&res);
310 __M: 309 LBL_M:
311 mp_clear(&M[1]); 310 mp_clear(&M[1]);
312 for (x = 1<<(winsize-1); x < (1 << winsize); x++) { 311 for (x = 1<<(winsize-1); x < (1 << winsize); x++) {
313 mp_clear (&M[x]); 312 mp_clear (&M[x]);
314 } 313 }
315 return err; 314 return err;