diff options
Diffstat (limited to 'src/lib/libcrypto/bn/bn_exp.c')
-rw-r--r-- | src/lib/libcrypto/bn/bn_exp.c | 696 |
1 files changed, 0 insertions, 696 deletions
diff --git a/src/lib/libcrypto/bn/bn_exp.c b/src/lib/libcrypto/bn/bn_exp.c deleted file mode 100644 index d2c91628ac..0000000000 --- a/src/lib/libcrypto/bn/bn_exp.c +++ /dev/null | |||
@@ -1,696 +0,0 @@ | |||
1 | /* crypto/bn/bn_exp.c */ | ||
2 | /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) | ||
3 | * All rights reserved. | ||
4 | * | ||
5 | * This package is an SSL implementation written | ||
6 | * by Eric Young (eay@cryptsoft.com). | ||
7 | * The implementation was written so as to conform with Netscapes SSL. | ||
8 | * | ||
9 | * This library is free for commercial and non-commercial use as long as | ||
10 | * the following conditions are aheared to. The following conditions | ||
11 | * apply to all code found in this distribution, be it the RC4, RSA, | ||
12 | * lhash, DES, etc., code; not just the SSL code. The SSL documentation | ||
13 | * included with this distribution is covered by the same copyright terms | ||
14 | * except that the holder is Tim Hudson (tjh@cryptsoft.com). | ||
15 | * | ||
16 | * Copyright remains Eric Young's, and as such any Copyright notices in | ||
17 | * the code are not to be removed. | ||
18 | * If this package is used in a product, Eric Young should be given attribution | ||
19 | * as the author of the parts of the library used. | ||
20 | * This can be in the form of a textual message at program startup or | ||
21 | * in documentation (online or textual) provided with the package. | ||
22 | * | ||
23 | * Redistribution and use in source and binary forms, with or without | ||
24 | * modification, are permitted provided that the following conditions | ||
25 | * are met: | ||
26 | * 1. Redistributions of source code must retain the copyright | ||
27 | * notice, this list of conditions and the following disclaimer. | ||
28 | * 2. Redistributions in binary form must reproduce the above copyright | ||
29 | * notice, this list of conditions and the following disclaimer in the | ||
30 | * documentation and/or other materials provided with the distribution. | ||
31 | * 3. All advertising materials mentioning features or use of this software | ||
32 | * must display the following acknowledgement: | ||
33 | * "This product includes cryptographic software written by | ||
34 | * Eric Young (eay@cryptsoft.com)" | ||
35 | * The word 'cryptographic' can be left out if the rouines from the library | ||
36 | * being used are not cryptographic related :-). | ||
37 | * 4. If you include any Windows specific code (or a derivative thereof) from | ||
38 | * the apps directory (application code) you must include an acknowledgement: | ||
39 | * "This product includes software written by Tim Hudson (tjh@cryptsoft.com)" | ||
40 | * | ||
41 | * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND | ||
42 | * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE | ||
43 | * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE | ||
44 | * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE | ||
45 | * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL | ||
46 | * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS | ||
47 | * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) | ||
48 | * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT | ||
49 | * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY | ||
50 | * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF | ||
51 | * SUCH DAMAGE. | ||
52 | * | ||
53 | * The licence and distribution terms for any publically available version or | ||
54 | * derivative of this code cannot be changed. i.e. this code cannot simply be | ||
55 | * copied and put under another distribution licence | ||
56 | * [including the GNU Public Licence.] | ||
57 | */ | ||
58 | /* ==================================================================== | ||
59 | * Copyright (c) 1998-2000 The OpenSSL Project. All rights reserved. | ||
60 | * | ||
61 | * Redistribution and use in source and binary forms, with or without | ||
62 | * modification, are permitted provided that the following conditions | ||
63 | * are met: | ||
64 | * | ||
65 | * 1. Redistributions of source code must retain the above copyright | ||
66 | * notice, this list of conditions and the following disclaimer. | ||
67 | * | ||
68 | * 2. Redistributions in binary form must reproduce the above copyright | ||
69 | * notice, this list of conditions and the following disclaimer in | ||
70 | * the documentation and/or other materials provided with the | ||
71 | * distribution. | ||
72 | * | ||
73 | * 3. All advertising materials mentioning features or use of this | ||
74 | * software must display the following acknowledgment: | ||
75 | * "This product includes software developed by the OpenSSL Project | ||
76 | * for use in the OpenSSL Toolkit. (http://www.openssl.org/)" | ||
77 | * | ||
78 | * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to | ||
79 | * endorse or promote products derived from this software without | ||
80 | * prior written permission. For written permission, please contact | ||
81 | * openssl-core@openssl.org. | ||
82 | * | ||
83 | * 5. Products derived from this software may not be called "OpenSSL" | ||
84 | * nor may "OpenSSL" appear in their names without prior written | ||
85 | * permission of the OpenSSL Project. | ||
86 | * | ||
87 | * 6. Redistributions of any form whatsoever must retain the following | ||
88 | * acknowledgment: | ||
89 | * "This product includes software developed by the OpenSSL Project | ||
90 | * for use in the OpenSSL Toolkit (http://www.openssl.org/)" | ||
91 | * | ||
92 | * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY | ||
93 | * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE | ||
94 | * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR | ||
95 | * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR | ||
96 | * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, | ||
97 | * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT | ||
98 | * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; | ||
99 | * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) | ||
100 | * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, | ||
101 | * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) | ||
102 | * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED | ||
103 | * OF THE POSSIBILITY OF SUCH DAMAGE. | ||
104 | * ==================================================================== | ||
105 | * | ||
106 | * This product includes cryptographic software written by Eric Young | ||
107 | * (eay@cryptsoft.com). This product includes software written by Tim | ||
108 | * Hudson (tjh@cryptsoft.com). | ||
109 | * | ||
110 | */ | ||
111 | |||
112 | |||
113 | #include <stdio.h> | ||
114 | #include "cryptlib.h" | ||
115 | #include "bn_lcl.h" | ||
116 | |||
117 | #define TABLE_SIZE 32 | ||
118 | |||
119 | /* slow but works */ | ||
120 | int BN_mod_mul(BIGNUM *ret, BIGNUM *a, BIGNUM *b, const BIGNUM *m, BN_CTX *ctx) | ||
121 | { | ||
122 | BIGNUM *t; | ||
123 | int r=0; | ||
124 | |||
125 | bn_check_top(a); | ||
126 | bn_check_top(b); | ||
127 | bn_check_top(m); | ||
128 | |||
129 | BN_CTX_start(ctx); | ||
130 | if ((t = BN_CTX_get(ctx)) == NULL) goto err; | ||
131 | if (a == b) | ||
132 | { if (!BN_sqr(t,a,ctx)) goto err; } | ||
133 | else | ||
134 | { if (!BN_mul(t,a,b,ctx)) goto err; } | ||
135 | if (!BN_mod(ret,t,m,ctx)) goto err; | ||
136 | r=1; | ||
137 | err: | ||
138 | BN_CTX_end(ctx); | ||
139 | return(r); | ||
140 | } | ||
141 | |||
142 | |||
143 | /* this one works - simple but works */ | ||
144 | int BN_exp(BIGNUM *r, BIGNUM *a, BIGNUM *p, BN_CTX *ctx) | ||
145 | { | ||
146 | int i,bits,ret=0; | ||
147 | BIGNUM *v,*rr; | ||
148 | |||
149 | BN_CTX_start(ctx); | ||
150 | if ((r == a) || (r == p)) | ||
151 | rr = BN_CTX_get(ctx); | ||
152 | else | ||
153 | rr = r; | ||
154 | if ((v = BN_CTX_get(ctx)) == NULL) goto err; | ||
155 | |||
156 | if (BN_copy(v,a) == NULL) goto err; | ||
157 | bits=BN_num_bits(p); | ||
158 | |||
159 | if (BN_is_odd(p)) | ||
160 | { if (BN_copy(rr,a) == NULL) goto err; } | ||
161 | else { if (!BN_one(rr)) goto err; } | ||
162 | |||
163 | for (i=1; i<bits; i++) | ||
164 | { | ||
165 | if (!BN_sqr(v,v,ctx)) goto err; | ||
166 | if (BN_is_bit_set(p,i)) | ||
167 | { | ||
168 | if (!BN_mul(rr,rr,v,ctx)) goto err; | ||
169 | } | ||
170 | } | ||
171 | ret=1; | ||
172 | err: | ||
173 | if (r != rr) BN_copy(r,rr); | ||
174 | BN_CTX_end(ctx); | ||
175 | return(ret); | ||
176 | } | ||
177 | |||
178 | |||
179 | int BN_mod_exp(BIGNUM *r, BIGNUM *a, const BIGNUM *p, const BIGNUM *m, | ||
180 | BN_CTX *ctx) | ||
181 | { | ||
182 | int ret; | ||
183 | |||
184 | bn_check_top(a); | ||
185 | bn_check_top(p); | ||
186 | bn_check_top(m); | ||
187 | |||
188 | #ifdef MONT_MUL_MOD | ||
189 | /* I have finally been able to take out this pre-condition of | ||
190 | * the top bit being set. It was caused by an error in BN_div | ||
191 | * with negatives. There was also another problem when for a^b%m | ||
192 | * a >= m. eay 07-May-97 */ | ||
193 | /* if ((m->d[m->top-1]&BN_TBIT) && BN_is_odd(m)) */ | ||
194 | |||
195 | if (BN_is_odd(m)) | ||
196 | { | ||
197 | if (a->top == 1) | ||
198 | { | ||
199 | BN_ULONG A = a->d[0]; | ||
200 | ret=BN_mod_exp_mont_word(r,A,p,m,ctx,NULL); | ||
201 | } | ||
202 | else | ||
203 | ret=BN_mod_exp_mont(r,a,p,m,ctx,NULL); | ||
204 | } | ||
205 | else | ||
206 | #endif | ||
207 | #ifdef RECP_MUL_MOD | ||
208 | { ret=BN_mod_exp_recp(r,a,p,m,ctx); } | ||
209 | #else | ||
210 | { ret=BN_mod_exp_simple(r,a,p,m,ctx); } | ||
211 | #endif | ||
212 | |||
213 | return(ret); | ||
214 | } | ||
215 | |||
216 | |||
217 | int BN_mod_exp_recp(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, | ||
218 | const BIGNUM *m, BN_CTX *ctx) | ||
219 | { | ||
220 | int i,j,bits,ret=0,wstart,wend,window,wvalue; | ||
221 | int start=1,ts=0; | ||
222 | BIGNUM *aa; | ||
223 | BIGNUM val[TABLE_SIZE]; | ||
224 | BN_RECP_CTX recp; | ||
225 | |||
226 | bits=BN_num_bits(p); | ||
227 | |||
228 | if (bits == 0) | ||
229 | { | ||
230 | BN_one(r); | ||
231 | return(1); | ||
232 | } | ||
233 | |||
234 | BN_CTX_start(ctx); | ||
235 | if ((aa = BN_CTX_get(ctx)) == NULL) goto err; | ||
236 | |||
237 | BN_RECP_CTX_init(&recp); | ||
238 | if (BN_RECP_CTX_set(&recp,m,ctx) <= 0) goto err; | ||
239 | |||
240 | BN_init(&(val[0])); | ||
241 | ts=1; | ||
242 | |||
243 | if (!BN_mod(&(val[0]),a,m,ctx)) goto err; /* 1 */ | ||
244 | |||
245 | window = BN_window_bits_for_exponent_size(bits); | ||
246 | if (window > 1) | ||
247 | { | ||
248 | if (!BN_mod_mul_reciprocal(aa,&(val[0]),&(val[0]),&recp,ctx)) | ||
249 | goto err; /* 2 */ | ||
250 | j=1<<(window-1); | ||
251 | for (i=1; i<j; i++) | ||
252 | { | ||
253 | BN_init(&val[i]); | ||
254 | if (!BN_mod_mul_reciprocal(&(val[i]),&(val[i-1]),aa,&recp,ctx)) | ||
255 | goto err; | ||
256 | } | ||
257 | ts=i; | ||
258 | } | ||
259 | |||
260 | start=1; /* This is used to avoid multiplication etc | ||
261 | * when there is only the value '1' in the | ||
262 | * buffer. */ | ||
263 | wvalue=0; /* The 'value' of the window */ | ||
264 | wstart=bits-1; /* The top bit of the window */ | ||
265 | wend=0; /* The bottom bit of the window */ | ||
266 | |||
267 | if (!BN_one(r)) goto err; | ||
268 | |||
269 | for (;;) | ||
270 | { | ||
271 | if (BN_is_bit_set(p,wstart) == 0) | ||
272 | { | ||
273 | if (!start) | ||
274 | if (!BN_mod_mul_reciprocal(r,r,r,&recp,ctx)) | ||
275 | goto err; | ||
276 | if (wstart == 0) break; | ||
277 | wstart--; | ||
278 | continue; | ||
279 | } | ||
280 | /* We now have wstart on a 'set' bit, we now need to work out | ||
281 | * how bit a window to do. To do this we need to scan | ||
282 | * forward until the last set bit before the end of the | ||
283 | * window */ | ||
284 | j=wstart; | ||
285 | wvalue=1; | ||
286 | wend=0; | ||
287 | for (i=1; i<window; i++) | ||
288 | { | ||
289 | if (wstart-i < 0) break; | ||
290 | if (BN_is_bit_set(p,wstart-i)) | ||
291 | { | ||
292 | wvalue<<=(i-wend); | ||
293 | wvalue|=1; | ||
294 | wend=i; | ||
295 | } | ||
296 | } | ||
297 | |||
298 | /* wend is the size of the current window */ | ||
299 | j=wend+1; | ||
300 | /* add the 'bytes above' */ | ||
301 | if (!start) | ||
302 | for (i=0; i<j; i++) | ||
303 | { | ||
304 | if (!BN_mod_mul_reciprocal(r,r,r,&recp,ctx)) | ||
305 | goto err; | ||
306 | } | ||
307 | |||
308 | /* wvalue will be an odd number < 2^window */ | ||
309 | if (!BN_mod_mul_reciprocal(r,r,&(val[wvalue>>1]),&recp,ctx)) | ||
310 | goto err; | ||
311 | |||
312 | /* move the 'window' down further */ | ||
313 | wstart-=wend+1; | ||
314 | wvalue=0; | ||
315 | start=0; | ||
316 | if (wstart < 0) break; | ||
317 | } | ||
318 | ret=1; | ||
319 | err: | ||
320 | BN_CTX_end(ctx); | ||
321 | for (i=0; i<ts; i++) | ||
322 | BN_clear_free(&(val[i])); | ||
323 | BN_RECP_CTX_free(&recp); | ||
324 | return(ret); | ||
325 | } | ||
326 | |||
327 | |||
328 | int BN_mod_exp_mont(BIGNUM *rr, BIGNUM *a, const BIGNUM *p, | ||
329 | const BIGNUM *m, BN_CTX *ctx, BN_MONT_CTX *in_mont) | ||
330 | { | ||
331 | int i,j,bits,ret=0,wstart,wend,window,wvalue; | ||
332 | int start=1,ts=0; | ||
333 | BIGNUM *d,*r; | ||
334 | BIGNUM *aa; | ||
335 | BIGNUM val[TABLE_SIZE]; | ||
336 | BN_MONT_CTX *mont=NULL; | ||
337 | |||
338 | bn_check_top(a); | ||
339 | bn_check_top(p); | ||
340 | bn_check_top(m); | ||
341 | |||
342 | if (!(m->d[0] & 1)) | ||
343 | { | ||
344 | BNerr(BN_F_BN_MOD_EXP_MONT,BN_R_CALLED_WITH_EVEN_MODULUS); | ||
345 | return(0); | ||
346 | } | ||
347 | bits=BN_num_bits(p); | ||
348 | if (bits == 0) | ||
349 | { | ||
350 | BN_one(rr); | ||
351 | return(1); | ||
352 | } | ||
353 | BN_CTX_start(ctx); | ||
354 | d = BN_CTX_get(ctx); | ||
355 | r = BN_CTX_get(ctx); | ||
356 | if (d == NULL || r == NULL) goto err; | ||
357 | |||
358 | /* If this is not done, things will break in the montgomery | ||
359 | * part */ | ||
360 | |||
361 | if (in_mont != NULL) | ||
362 | mont=in_mont; | ||
363 | else | ||
364 | { | ||
365 | if ((mont=BN_MONT_CTX_new()) == NULL) goto err; | ||
366 | if (!BN_MONT_CTX_set(mont,m,ctx)) goto err; | ||
367 | } | ||
368 | |||
369 | BN_init(&val[0]); | ||
370 | ts=1; | ||
371 | if (BN_ucmp(a,m) >= 0) | ||
372 | { | ||
373 | if (!BN_mod(&(val[0]),a,m,ctx)) | ||
374 | goto err; | ||
375 | aa= &(val[0]); | ||
376 | } | ||
377 | else | ||
378 | aa=a; | ||
379 | if (!BN_to_montgomery(&(val[0]),aa,mont,ctx)) goto err; /* 1 */ | ||
380 | |||
381 | window = BN_window_bits_for_exponent_size(bits); | ||
382 | if (window > 1) | ||
383 | { | ||
384 | if (!BN_mod_mul_montgomery(d,&(val[0]),&(val[0]),mont,ctx)) goto err; /* 2 */ | ||
385 | j=1<<(window-1); | ||
386 | for (i=1; i<j; i++) | ||
387 | { | ||
388 | BN_init(&(val[i])); | ||
389 | if (!BN_mod_mul_montgomery(&(val[i]),&(val[i-1]),d,mont,ctx)) | ||
390 | goto err; | ||
391 | } | ||
392 | ts=i; | ||
393 | } | ||
394 | |||
395 | start=1; /* This is used to avoid multiplication etc | ||
396 | * when there is only the value '1' in the | ||
397 | * buffer. */ | ||
398 | wvalue=0; /* The 'value' of the window */ | ||
399 | wstart=bits-1; /* The top bit of the window */ | ||
400 | wend=0; /* The bottom bit of the window */ | ||
401 | |||
402 | if (!BN_to_montgomery(r,BN_value_one(),mont,ctx)) goto err; | ||
403 | for (;;) | ||
404 | { | ||
405 | if (BN_is_bit_set(p,wstart) == 0) | ||
406 | { | ||
407 | if (!start) | ||
408 | { | ||
409 | if (!BN_mod_mul_montgomery(r,r,r,mont,ctx)) | ||
410 | goto err; | ||
411 | } | ||
412 | if (wstart == 0) break; | ||
413 | wstart--; | ||
414 | continue; | ||
415 | } | ||
416 | /* We now have wstart on a 'set' bit, we now need to work out | ||
417 | * how bit a window to do. To do this we need to scan | ||
418 | * forward until the last set bit before the end of the | ||
419 | * window */ | ||
420 | j=wstart; | ||
421 | wvalue=1; | ||
422 | wend=0; | ||
423 | for (i=1; i<window; i++) | ||
424 | { | ||
425 | if (wstart-i < 0) break; | ||
426 | if (BN_is_bit_set(p,wstart-i)) | ||
427 | { | ||
428 | wvalue<<=(i-wend); | ||
429 | wvalue|=1; | ||
430 | wend=i; | ||
431 | } | ||
432 | } | ||
433 | |||
434 | /* wend is the size of the current window */ | ||
435 | j=wend+1; | ||
436 | /* add the 'bytes above' */ | ||
437 | if (!start) | ||
438 | for (i=0; i<j; i++) | ||
439 | { | ||
440 | if (!BN_mod_mul_montgomery(r,r,r,mont,ctx)) | ||
441 | goto err; | ||
442 | } | ||
443 | |||
444 | /* wvalue will be an odd number < 2^window */ | ||
445 | if (!BN_mod_mul_montgomery(r,r,&(val[wvalue>>1]),mont,ctx)) | ||
446 | goto err; | ||
447 | |||
448 | /* move the 'window' down further */ | ||
449 | wstart-=wend+1; | ||
450 | wvalue=0; | ||
451 | start=0; | ||
452 | if (wstart < 0) break; | ||
453 | } | ||
454 | if (!BN_from_montgomery(rr,r,mont,ctx)) goto err; | ||
455 | ret=1; | ||
456 | err: | ||
457 | if ((in_mont == NULL) && (mont != NULL)) BN_MONT_CTX_free(mont); | ||
458 | BN_CTX_end(ctx); | ||
459 | for (i=0; i<ts; i++) | ||
460 | BN_clear_free(&(val[i])); | ||
461 | return(ret); | ||
462 | } | ||
463 | |||
464 | int BN_mod_exp_mont_word(BIGNUM *rr, BN_ULONG a, const BIGNUM *p, | ||
465 | const BIGNUM *m, BN_CTX *ctx, BN_MONT_CTX *in_mont) | ||
466 | { | ||
467 | BN_MONT_CTX *mont = NULL; | ||
468 | int b, bits, ret=0; | ||
469 | int r_is_one; | ||
470 | BN_ULONG w, next_w; | ||
471 | BIGNUM *d, *r, *t; | ||
472 | BIGNUM *swap_tmp; | ||
473 | #define BN_MOD_MUL_WORD(r, w, m) \ | ||
474 | (BN_mul_word(r, (w)) && \ | ||
475 | (/* BN_ucmp(r, (m)) < 0 ? 1 :*/ \ | ||
476 | (BN_mod(t, r, m, ctx) && (swap_tmp = r, r = t, t = swap_tmp, 1)))) | ||
477 | /* BN_MOD_MUL_WORD is only used with 'w' large, | ||
478 | * so the BN_ucmp test is probably more overhead | ||
479 | * than always using BN_mod (which uses BN_copy if | ||
480 | * a similar test returns true). */ | ||
481 | #define BN_TO_MONTGOMERY_WORD(r, w, mont) \ | ||
482 | (BN_set_word(r, (w)) && BN_to_montgomery(r, r, (mont), ctx)) | ||
483 | |||
484 | bn_check_top(p); | ||
485 | bn_check_top(m); | ||
486 | |||
487 | if (!(m->d[0] & 1)) | ||
488 | { | ||
489 | BNerr(BN_F_BN_MOD_EXP_MONT_WORD,BN_R_CALLED_WITH_EVEN_MODULUS); | ||
490 | return(0); | ||
491 | } | ||
492 | bits = BN_num_bits(p); | ||
493 | if (bits == 0) | ||
494 | { | ||
495 | BN_one(rr); | ||
496 | return(1); | ||
497 | } | ||
498 | BN_CTX_start(ctx); | ||
499 | d = BN_CTX_get(ctx); | ||
500 | r = BN_CTX_get(ctx); | ||
501 | t = BN_CTX_get(ctx); | ||
502 | if (d == NULL || r == NULL || t == NULL) goto err; | ||
503 | |||
504 | if (in_mont != NULL) | ||
505 | mont=in_mont; | ||
506 | else | ||
507 | { | ||
508 | if ((mont = BN_MONT_CTX_new()) == NULL) goto err; | ||
509 | if (!BN_MONT_CTX_set(mont, m, ctx)) goto err; | ||
510 | } | ||
511 | |||
512 | r_is_one = 1; /* except for Montgomery factor */ | ||
513 | |||
514 | /* bits-1 >= 0 */ | ||
515 | |||
516 | /* The result is accumulated in the product r*w. */ | ||
517 | w = a; /* bit 'bits-1' of 'p' is always set */ | ||
518 | for (b = bits-2; b >= 0; b--) | ||
519 | { | ||
520 | /* First, square r*w. */ | ||
521 | next_w = w*w; | ||
522 | if ((next_w/w) != w) /* overflow */ | ||
523 | { | ||
524 | if (r_is_one) | ||
525 | { | ||
526 | if (!BN_TO_MONTGOMERY_WORD(r, w, mont)) goto err; | ||
527 | r_is_one = 0; | ||
528 | } | ||
529 | else | ||
530 | { | ||
531 | if (!BN_MOD_MUL_WORD(r, w, m)) goto err; | ||
532 | } | ||
533 | next_w = 1; | ||
534 | } | ||
535 | w = next_w; | ||
536 | if (!r_is_one) | ||
537 | { | ||
538 | if (!BN_mod_mul_montgomery(r, r, r, mont, ctx)) goto err; | ||
539 | } | ||
540 | |||
541 | /* Second, multiply r*w by 'a' if exponent bit is set. */ | ||
542 | if (BN_is_bit_set(p, b)) | ||
543 | { | ||
544 | next_w = w*a; | ||
545 | if ((next_w/a) != w) /* overflow */ | ||
546 | { | ||
547 | if (r_is_one) | ||
548 | { | ||
549 | if (!BN_TO_MONTGOMERY_WORD(r, w, mont)) goto err; | ||
550 | r_is_one = 0; | ||
551 | } | ||
552 | else | ||
553 | { | ||
554 | if (!BN_MOD_MUL_WORD(r, w, m)) goto err; | ||
555 | } | ||
556 | next_w = a; | ||
557 | } | ||
558 | w = next_w; | ||
559 | } | ||
560 | } | ||
561 | |||
562 | /* Finally, set r:=r*w. */ | ||
563 | if (w != 1) | ||
564 | { | ||
565 | if (r_is_one) | ||
566 | { | ||
567 | if (!BN_TO_MONTGOMERY_WORD(r, w, mont)) goto err; | ||
568 | r_is_one = 0; | ||
569 | } | ||
570 | else | ||
571 | { | ||
572 | if (!BN_MOD_MUL_WORD(r, w, m)) goto err; | ||
573 | } | ||
574 | } | ||
575 | |||
576 | if (r_is_one) /* can happen only if a == 1*/ | ||
577 | { | ||
578 | if (!BN_one(rr)) goto err; | ||
579 | } | ||
580 | else | ||
581 | { | ||
582 | if (!BN_from_montgomery(rr, r, mont, ctx)) goto err; | ||
583 | } | ||
584 | ret = 1; | ||
585 | err: | ||
586 | if ((in_mont == NULL) && (mont != NULL)) BN_MONT_CTX_free(mont); | ||
587 | BN_CTX_end(ctx); | ||
588 | return(ret); | ||
589 | } | ||
590 | |||
591 | |||
592 | /* The old fallback, simple version :-) */ | ||
593 | int BN_mod_exp_simple(BIGNUM *r, BIGNUM *a, BIGNUM *p, BIGNUM *m, | ||
594 | BN_CTX *ctx) | ||
595 | { | ||
596 | int i,j,bits,ret=0,wstart,wend,window,wvalue,ts=0; | ||
597 | int start=1; | ||
598 | BIGNUM *d; | ||
599 | BIGNUM val[TABLE_SIZE]; | ||
600 | |||
601 | bits=BN_num_bits(p); | ||
602 | |||
603 | if (bits == 0) | ||
604 | { | ||
605 | BN_one(r); | ||
606 | return(1); | ||
607 | } | ||
608 | |||
609 | BN_CTX_start(ctx); | ||
610 | if ((d = BN_CTX_get(ctx)) == NULL) goto err; | ||
611 | |||
612 | BN_init(&(val[0])); | ||
613 | ts=1; | ||
614 | if (!BN_mod(&(val[0]),a,m,ctx)) goto err; /* 1 */ | ||
615 | |||
616 | window = BN_window_bits_for_exponent_size(bits); | ||
617 | if (window > 1) | ||
618 | { | ||
619 | if (!BN_mod_mul(d,&(val[0]),&(val[0]),m,ctx)) | ||
620 | goto err; /* 2 */ | ||
621 | j=1<<(window-1); | ||
622 | for (i=1; i<j; i++) | ||
623 | { | ||
624 | BN_init(&(val[i])); | ||
625 | if (!BN_mod_mul(&(val[i]),&(val[i-1]),d,m,ctx)) | ||
626 | goto err; | ||
627 | } | ||
628 | ts=i; | ||
629 | } | ||
630 | |||
631 | start=1; /* This is used to avoid multiplication etc | ||
632 | * when there is only the value '1' in the | ||
633 | * buffer. */ | ||
634 | wvalue=0; /* The 'value' of the window */ | ||
635 | wstart=bits-1; /* The top bit of the window */ | ||
636 | wend=0; /* The bottom bit of the window */ | ||
637 | |||
638 | if (!BN_one(r)) goto err; | ||
639 | |||
640 | for (;;) | ||
641 | { | ||
642 | if (BN_is_bit_set(p,wstart) == 0) | ||
643 | { | ||
644 | if (!start) | ||
645 | if (!BN_mod_mul(r,r,r,m,ctx)) | ||
646 | goto err; | ||
647 | if (wstart == 0) break; | ||
648 | wstart--; | ||
649 | continue; | ||
650 | } | ||
651 | /* We now have wstart on a 'set' bit, we now need to work out | ||
652 | * how bit a window to do. To do this we need to scan | ||
653 | * forward until the last set bit before the end of the | ||
654 | * window */ | ||
655 | j=wstart; | ||
656 | wvalue=1; | ||
657 | wend=0; | ||
658 | for (i=1; i<window; i++) | ||
659 | { | ||
660 | if (wstart-i < 0) break; | ||
661 | if (BN_is_bit_set(p,wstart-i)) | ||
662 | { | ||
663 | wvalue<<=(i-wend); | ||
664 | wvalue|=1; | ||
665 | wend=i; | ||
666 | } | ||
667 | } | ||
668 | |||
669 | /* wend is the size of the current window */ | ||
670 | j=wend+1; | ||
671 | /* add the 'bytes above' */ | ||
672 | if (!start) | ||
673 | for (i=0; i<j; i++) | ||
674 | { | ||
675 | if (!BN_mod_mul(r,r,r,m,ctx)) | ||
676 | goto err; | ||
677 | } | ||
678 | |||
679 | /* wvalue will be an odd number < 2^window */ | ||
680 | if (!BN_mod_mul(r,r,&(val[wvalue>>1]),m,ctx)) | ||
681 | goto err; | ||
682 | |||
683 | /* move the 'window' down further */ | ||
684 | wstart-=wend+1; | ||
685 | wvalue=0; | ||
686 | start=0; | ||
687 | if (wstart < 0) break; | ||
688 | } | ||
689 | ret=1; | ||
690 | err: | ||
691 | BN_CTX_end(ctx); | ||
692 | for (i=0; i<ts; i++) | ||
693 | BN_clear_free(&(val[i])); | ||
694 | return(ret); | ||
695 | } | ||
696 | |||