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 "bn_lcl.h" |
115 |
#ifdef ATALLA |
116 |
# include <alloca.h> |
117 |
# include <atasi.h> |
118 |
# include <assert.h> |
119 |
# include <dlfcn.h> |
120 |
#endif |
121 |
|
122 |
|
123 |
#define TABLE_SIZE 32 |
124 |
|
125 |
/* slow but works */ |
126 |
int BN_mod_mul(BIGNUM *ret, BIGNUM *a, BIGNUM *b, const BIGNUM *m, BN_CTX *ctx) |
127 |
{ |
128 |
BIGNUM *t; |
129 |
int r=0; |
130 |
|
131 |
bn_check_top(a); |
132 |
bn_check_top(b); |
133 |
bn_check_top(m); |
134 |
|
135 |
BN_CTX_start(ctx); |
136 |
if ((t = BN_CTX_get(ctx)) == NULL) goto err; |
137 |
if (a == b) |
138 |
{ if (!BN_sqr(t,a,ctx)) goto err; } |
139 |
else |
140 |
{ if (!BN_mul(t,a,b,ctx)) goto err; } |
141 |
if (!BN_mod(ret,t,m,ctx)) goto err; |
142 |
r=1; |
143 |
err: |
144 |
BN_CTX_end(ctx); |
145 |
return(r); |
146 |
} |
147 |
|
148 |
#if 0 |
149 |
/* this one works - simple but works */ |
150 |
int BN_exp(BIGNUM *r, BIGNUM *a, BIGNUM *p, BN_CTX *ctx) |
151 |
{ |
152 |
int i,bits,ret=0; |
153 |
BIGNUM *v,*rr; |
154 |
|
155 |
BN_CTX_start(ctx); |
156 |
if ((r == a) || (r == p)) |
157 |
rr = BN_CTX_get(ctx); |
158 |
else |
159 |
rr = r; |
160 |
if ((v = BN_CTX_get(ctx)) == NULL) goto err; |
161 |
|
162 |
if (BN_copy(v,a) == NULL) goto err; |
163 |
bits=BN_num_bits(p); |
164 |
|
165 |
if (BN_is_odd(p)) |
166 |
{ if (BN_copy(rr,a) == NULL) goto err; } |
167 |
else { if (!BN_one(rr)) goto err; } |
168 |
|
169 |
for (i=1; i<bits; i++) |
170 |
{ |
171 |
if (!BN_sqr(v,v,ctx)) goto err; |
172 |
if (BN_is_bit_set(p,i)) |
173 |
{ |
174 |
if (!BN_mul(rr,rr,v,ctx)) goto err; |
175 |
} |
176 |
} |
177 |
ret=1; |
178 |
err: |
179 |
if (r != rr) BN_copy(r,rr); |
180 |
BN_CTX_end(ctx); |
181 |
return(ret); |
182 |
} |
183 |
#endif |
184 |
|
185 |
#ifdef ATALLA |
186 |
|
187 |
/* |
188 |
* This routine will dynamically check for the existance of an Atalla AXL-200 |
189 |
* SSL accelerator module. If one is found, the variable |
190 |
* asi_accelerator_present is set to 1 and the function pointers |
191 |
* ptr_ASI_xxxxxx above will be initialized to corresponding ASI API calls. |
192 |
*/ |
193 |
typedef int tfnASI_GetPerformanceStatistics(int reset_flag, |
194 |
unsigned int *ret_buf); |
195 |
typedef int tfnASI_GetHardwareConfig(long card_num, unsigned int *ret_buf); |
196 |
typedef int tfnASI_RSAPrivateKeyOpFn(RSAPrivateKey * rsaKey, |
197 |
unsigned char *output, |
198 |
unsigned char *input, |
199 |
unsigned int modulus_len); |
200 |
|
201 |
static tfnASI_GetHardwareConfig *ptr_ASI_GetHardwareConfig; |
202 |
static tfnASI_RSAPrivateKeyOpFn *ptr_ASI_RSAPrivateKeyOpFn; |
203 |
static tfnASI_GetPerformanceStatistics *ptr_ASI_GetPerformanceStatistics; |
204 |
static int asi_accelerator_present; |
205 |
static int tried_atalla; |
206 |
|
207 |
void atalla_initialize_accelerator_handle(void) |
208 |
{ |
209 |
void *dl_handle; |
210 |
int status; |
211 |
unsigned int config_buf[1024]; |
212 |
static int tested; |
213 |
|
214 |
if(tested) |
215 |
return; |
216 |
|
217 |
tested=1; |
218 |
|
219 |
bzero((void *)config_buf, 1024); |
220 |
|
221 |
/* |
222 |
* Check to see if the library is present on the system |
223 |
*/ |
224 |
dl_handle = dlopen("atasi.so", RTLD_NOW); |
225 |
if (dl_handle == (void *) NULL) |
226 |
{ |
227 |
/* printf("atasi.so library is not present on the system\n"); |
228 |
printf("No HW acceleration available\n");*/ |
229 |
return; |
230 |
} |
231 |
|
232 |
/* |
233 |
* The library is present. Now we'll check to insure that the |
234 |
* LDM is up and running. First we'll get the address of the |
235 |
* function in the atasi library that we need to see if the |
236 |
* LDM is operating. |
237 |
*/ |
238 |
|
239 |
ptr_ASI_GetHardwareConfig = |
240 |
(tfnASI_GetHardwareConfig *)dlsym(dl_handle,"ASI_GetHardwareConfig"); |
241 |
|
242 |
if (ptr_ASI_GetHardwareConfig) |
243 |
{ |
244 |
/* |
245 |
* We found the call, now we'll get our config |
246 |
* status. If we get a non 0 result, the LDM is not |
247 |
* running and we cannot use the Atalla ASI * |
248 |
* library. |
249 |
*/ |
250 |
status = (*ptr_ASI_GetHardwareConfig)(0L, config_buf); |
251 |
if (status != 0) |
252 |
{ |
253 |
printf("atasi.so library is present but not initialized\n"); |
254 |
printf("No HW acceleration available\n"); |
255 |
return; |
256 |
} |
257 |
} |
258 |
else |
259 |
{ |
260 |
/* printf("We found the library, but not the function. Very Strange!\n");*/ |
261 |
return ; |
262 |
} |
263 |
|
264 |
/* |
265 |
* It looks like we have acceleration capabilities. Load up the |
266 |
* pointers to our ASI API calls. |
267 |
*/ |
268 |
ptr_ASI_RSAPrivateKeyOpFn= |
269 |
(tfnASI_RSAPrivateKeyOpFn *)dlsym(dl_handle, "ASI_RSAPrivateKeyOpFn"); |
270 |
if (ptr_ASI_RSAPrivateKeyOpFn == NULL) |
271 |
{ |
272 |
/* printf("We found the library, but no RSA function. Very Strange!\n");*/ |
273 |
return; |
274 |
} |
275 |
|
276 |
ptr_ASI_GetPerformanceStatistics = |
277 |
(tfnASI_GetPerformanceStatistics *)dlsym(dl_handle, "ASI_GetPerformanceStatistics"); |
278 |
if (ptr_ASI_GetPerformanceStatistics == NULL) |
279 |
{ |
280 |
/* printf("We found the library, but no stat function. Very Strange!\n");*/ |
281 |
return; |
282 |
} |
283 |
|
284 |
/* |
285 |
* Indicate that acceleration is available |
286 |
*/ |
287 |
asi_accelerator_present = 1; |
288 |
|
289 |
/* printf("This system has acceleration!\n");*/ |
290 |
|
291 |
return; |
292 |
} |
293 |
|
294 |
/* make sure this only gets called once when bn_mod_exp calls bn_mod_exp_mont */ |
295 |
int BN_mod_exp_atalla(BIGNUM *r, BIGNUM *a, const BIGNUM *p, const BIGNUM *m) |
296 |
{ |
297 |
unsigned char *abin; |
298 |
unsigned char *pbin; |
299 |
unsigned char *mbin; |
300 |
unsigned char *rbin; |
301 |
int an,pn,mn,ret; |
302 |
RSAPrivateKey keydata; |
303 |
|
304 |
atalla_initialize_accelerator_handle(); |
305 |
if(!asi_accelerator_present) |
306 |
return 0; |
307 |
|
308 |
|
309 |
/* We should be able to run without size testing */ |
310 |
# define ASIZE 128 |
311 |
an=BN_num_bytes(a); |
312 |
pn=BN_num_bytes(p); |
313 |
mn=BN_num_bytes(m); |
314 |
|
315 |
if(an <= ASIZE && pn <= ASIZE && mn <= ASIZE) |
316 |
{ |
317 |
int size=mn; |
318 |
|
319 |
assert(an <= mn); |
320 |
abin=alloca(size); |
321 |
memset(abin,'\0',mn); |
322 |
BN_bn2bin(a,abin+size-an); |
323 |
|
324 |
pbin=alloca(pn); |
325 |
BN_bn2bin(p,pbin); |
326 |
|
327 |
mbin=alloca(size); |
328 |
memset(mbin,'\0',mn); |
329 |
BN_bn2bin(m,mbin+size-mn); |
330 |
|
331 |
rbin=alloca(size); |
332 |
|
333 |
memset(&keydata,'\0',sizeof keydata); |
334 |
keydata.privateExponent.data=pbin; |
335 |
keydata.privateExponent.len=pn; |
336 |
keydata.modulus.data=mbin; |
337 |
keydata.modulus.len=size; |
338 |
|
339 |
ret=(*ptr_ASI_RSAPrivateKeyOpFn)(&keydata,rbin,abin,keydata.modulus.len); |
340 |
/*fprintf(stderr,"!%s\n",BN_bn2hex(a));*/ |
341 |
if(!ret) |
342 |
{ |
343 |
BN_bin2bn(rbin,keydata.modulus.len,r); |
344 |
/*fprintf(stderr,"?%s\n",BN_bn2hex(r));*/ |
345 |
return 1; |
346 |
} |
347 |
} |
348 |
return 0; |
349 |
} |
350 |
#endif /* def ATALLA */ |
351 |
|
352 |
|
353 |
int BN_mod_exp(BIGNUM *r, BIGNUM *a, const BIGNUM *p, const BIGNUM *m, |
354 |
BN_CTX *ctx) |
355 |
{ |
356 |
int ret; |
357 |
|
358 |
bn_check_top(a); |
359 |
bn_check_top(p); |
360 |
bn_check_top(m); |
361 |
|
362 |
#ifdef ATALLA |
363 |
if(BN_mod_exp_atalla(r,a,p,m)) |
364 |
return 1; |
365 |
/* If it fails, try the other methods (but don't try atalla again) */ |
366 |
tried_atalla=1; |
367 |
#endif |
368 |
|
369 |
#ifdef MONT_MUL_MOD |
370 |
/* I have finally been able to take out this pre-condition of |
371 |
* the top bit being set. It was caused by an error in BN_div |
372 |
* with negatives. There was also another problem when for a^b%m |
373 |
* a >= m. eay 07-May-97 */ |
374 |
/* if ((m->d[m->top-1]&BN_TBIT) && BN_is_odd(m)) */ |
375 |
|
376 |
if (BN_is_odd(m)) |
377 |
{ |
378 |
if (a->top == 1) |
379 |
{ |
380 |
BN_ULONG A = a->d[0]; |
381 |
ret=BN_mod_exp_mont_word(r,A,p,m,ctx,NULL); |
382 |
} |
383 |
else |
384 |
ret=BN_mod_exp_mont(r,a,p,m,ctx,NULL); |
385 |
} |
386 |
else |
387 |
#endif |
388 |
#ifdef RECP_MUL_MOD |
389 |
{ ret=BN_mod_exp_recp(r,a,p,m,ctx); } |
390 |
#else |
391 |
{ ret=BN_mod_exp_simple(r,a,p,m,ctx); } |
392 |
#endif |
393 |
|
394 |
#ifdef ATALLA |
395 |
tried_atalla=0; |
396 |
#endif |
397 |
|
398 |
return(ret); |
399 |
} |
400 |
|
401 |
#ifdef RECP_MUL_MOD |
402 |
int BN_mod_exp_recp(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, |
403 |
const BIGNUM *m, BN_CTX *ctx) |
404 |
{ |
405 |
int i,j,bits,ret=0,wstart,wend,window,wvalue; |
406 |
int start=1,ts=0; |
407 |
BIGNUM *aa; |
408 |
BIGNUM val[TABLE_SIZE]; |
409 |
BN_RECP_CTX recp; |
410 |
|
411 |
bits=BN_num_bits(p); |
412 |
|
413 |
if (bits == 0) |
414 |
{ |
415 |
BN_one(r); |
416 |
return(1); |
417 |
} |
418 |
|
419 |
BN_CTX_start(ctx); |
420 |
if ((aa = BN_CTX_get(ctx)) == NULL) goto err; |
421 |
|
422 |
BN_RECP_CTX_init(&recp); |
423 |
if (BN_RECP_CTX_set(&recp,m,ctx) <= 0) goto err; |
424 |
|
425 |
BN_init(&(val[0])); |
426 |
ts=1; |
427 |
|
428 |
if (!BN_mod(&(val[0]),a,m,ctx)) goto err; /* 1 */ |
429 |
|
430 |
window = BN_window_bits_for_exponent_size(bits); |
431 |
if (window > 1) |
432 |
{ |
433 |
if (!BN_mod_mul_reciprocal(aa,&(val[0]),&(val[0]),&recp,ctx)) |
434 |
goto err; /* 2 */ |
435 |
j=1<<(window-1); |
436 |
for (i=1; i<j; i++) |
437 |
{ |
438 |
BN_init(&val[i]); |
439 |
if (!BN_mod_mul_reciprocal(&(val[i]),&(val[i-1]),aa,&recp,ctx)) |
440 |
goto err; |
441 |
} |
442 |
ts=i; |
443 |
} |
444 |
|
445 |
start=1; /* This is used to avoid multiplication etc |
446 |
* when there is only the value '1' in the |
447 |
* buffer. */ |
448 |
wvalue=0; /* The 'value' of the window */ |
449 |
wstart=bits-1; /* The top bit of the window */ |
450 |
wend=0; /* The bottom bit of the window */ |
451 |
|
452 |
if (!BN_one(r)) goto err; |
453 |
|
454 |
for (;;) |
455 |
{ |
456 |
if (BN_is_bit_set(p,wstart) == 0) |
457 |
{ |
458 |
if (!start) |
459 |
if (!BN_mod_mul_reciprocal(r,r,r,&recp,ctx)) |
460 |
goto err; |
461 |
if (wstart == 0) break; |
462 |
wstart--; |
463 |
continue; |
464 |
} |
465 |
/* We now have wstart on a 'set' bit, we now need to work out |
466 |
* how bit a window to do. To do this we need to scan |
467 |
* forward until the last set bit before the end of the |
468 |
* window */ |
469 |
j=wstart; |
470 |
wvalue=1; |
471 |
wend=0; |
472 |
for (i=1; i<window; i++) |
473 |
{ |
474 |
if (wstart-i < 0) break; |
475 |
if (BN_is_bit_set(p,wstart-i)) |
476 |
{ |
477 |
wvalue<<=(i-wend); |
478 |
wvalue|=1; |
479 |
wend=i; |
480 |
} |
481 |
} |
482 |
|
483 |
/* wend is the size of the current window */ |
484 |
j=wend+1; |
485 |
/* add the 'bytes above' */ |
486 |
if (!start) |
487 |
for (i=0; i<j; i++) |
488 |
{ |
489 |
if (!BN_mod_mul_reciprocal(r,r,r,&recp,ctx)) |
490 |
goto err; |
491 |
} |
492 |
|
493 |
/* wvalue will be an odd number < 2^window */ |
494 |
if (!BN_mod_mul_reciprocal(r,r,&(val[wvalue>>1]),&recp,ctx)) |
495 |
goto err; |
496 |
|
497 |
/* move the 'window' down further */ |
498 |
wstart-=wend+1; |
499 |
wvalue=0; |
500 |
start=0; |
501 |
if (wstart < 0) break; |
502 |
} |
503 |
ret=1; |
504 |
err: |
505 |
BN_CTX_end(ctx); |
506 |
for (i=0; i<ts; i++) |
507 |
BN_clear_free(&(val[i])); |
508 |
BN_RECP_CTX_free(&recp); |
509 |
return(ret); |
510 |
} |
511 |
#endif |
512 |
|
513 |
#ifdef MONT_MUL_MOD |
514 |
int BN_mod_exp_mont(BIGNUM *rr, BIGNUM *a, const BIGNUM *p, |
515 |
const BIGNUM *m, BN_CTX *ctx, BN_MONT_CTX *in_mont) |
516 |
{ |
517 |
int i,j,bits,ret=0,wstart,wend,window,wvalue; |
518 |
int start=1,ts=0; |
519 |
BIGNUM *d,*r; |
520 |
BIGNUM *aa; |
521 |
BIGNUM val[TABLE_SIZE]; |
522 |
BN_MONT_CTX *mont=NULL; |
523 |
|
524 |
bn_check_top(a); |
525 |
bn_check_top(p); |
526 |
bn_check_top(m); |
527 |
|
528 |
#ifdef ATALLA |
529 |
if(!tried_atalla && BN_mod_exp_atalla(rr,a,p,m)) |
530 |
return 1; |
531 |
/* If it fails, try the other methods */ |
532 |
#endif |
533 |
|
534 |
if (!(m->d[0] & 1)) |
535 |
{ |
536 |
BNerr(BN_F_BN_MOD_EXP_MONT,BN_R_CALLED_WITH_EVEN_MODULUS); |
537 |
return(0); |
538 |
} |
539 |
bits=BN_num_bits(p); |
540 |
if (bits == 0) |
541 |
{ |
542 |
BN_one(rr); |
543 |
return(1); |
544 |
} |
545 |
BN_CTX_start(ctx); |
546 |
d = BN_CTX_get(ctx); |
547 |
r = BN_CTX_get(ctx); |
548 |
if (d == NULL || r == NULL) goto err; |
549 |
|
550 |
/* If this is not done, things will break in the montgomery |
551 |
* part */ |
552 |
|
553 |
if (in_mont != NULL) |
554 |
mont=in_mont; |
555 |
else |
556 |
{ |
557 |
if ((mont=BN_MONT_CTX_new()) == NULL) goto err; |
558 |
if (!BN_MONT_CTX_set(mont,m,ctx)) goto err; |
559 |
} |
560 |
|
561 |
BN_init(&val[0]); |
562 |
ts=1; |
563 |
if (BN_ucmp(a,m) >= 0) |
564 |
{ |
565 |
if (!BN_mod(&(val[0]),a,m,ctx)) |
566 |
goto err; |
567 |
aa= &(val[0]); |
568 |
} |
569 |
else |
570 |
aa=a; |
571 |
if (!BN_to_montgomery(&(val[0]),aa,mont,ctx)) goto err; /* 1 */ |
572 |
|
573 |
window = BN_window_bits_for_exponent_size(bits); |
574 |
if (window > 1) |
575 |
{ |
576 |
if (!BN_mod_mul_montgomery(d,&(val[0]),&(val[0]),mont,ctx)) goto err; /* 2 */ |
577 |
j=1<<(window-1); |
578 |
for (i=1; i<j; i++) |
579 |
{ |
580 |
BN_init(&(val[i])); |
581 |
if (!BN_mod_mul_montgomery(&(val[i]),&(val[i-1]),d,mont,ctx)) |
582 |
goto err; |
583 |
} |
584 |
ts=i; |
585 |
} |
586 |
|
587 |
start=1; /* This is used to avoid multiplication etc |
588 |
* when there is only the value '1' in the |
589 |
* buffer. */ |
590 |
wvalue=0; /* The 'value' of the window */ |
591 |
wstart=bits-1; /* The top bit of the window */ |
592 |
wend=0; /* The bottom bit of the window */ |
593 |
|
594 |
if (!BN_to_montgomery(r,BN_value_one(),mont,ctx)) goto err; |
595 |
for (;;) |
596 |
{ |
597 |
if (BN_is_bit_set(p,wstart) == 0) |
598 |
{ |
599 |
if (!start) |
600 |
{ |
601 |
if (!BN_mod_mul_montgomery(r,r,r,mont,ctx)) |
602 |
goto err; |
603 |
} |
604 |
if (wstart == 0) break; |
605 |
wstart--; |
606 |
continue; |
607 |
} |
608 |
/* We now have wstart on a 'set' bit, we now need to work out |
609 |
* how bit a window to do. To do this we need to scan |
610 |
* forward until the last set bit before the end of the |
611 |
* window */ |
612 |
j=wstart; |
613 |
wvalue=1; |
614 |
wend=0; |
615 |
for (i=1; i<window; i++) |
616 |
{ |
617 |
if (wstart-i < 0) break; |
618 |
if (BN_is_bit_set(p,wstart-i)) |
619 |
{ |
620 |
wvalue<<=(i-wend); |
621 |
wvalue|=1; |
622 |
wend=i; |
623 |
} |
624 |
} |
625 |
|
626 |
/* wend is the size of the current window */ |
627 |
j=wend+1; |
628 |
/* add the 'bytes above' */ |
629 |
if (!start) |
630 |
for (i=0; i<j; i++) |
631 |
{ |
632 |
if (!BN_mod_mul_montgomery(r,r,r,mont,ctx)) |
633 |
goto err; |
634 |
} |
635 |
|
636 |
/* wvalue will be an odd number < 2^window */ |
637 |
if (!BN_mod_mul_montgomery(r,r,&(val[wvalue>>1]),mont,ctx)) |
638 |
goto err; |
639 |
|
640 |
/* move the 'window' down further */ |
641 |
wstart-=wend+1; |
642 |
wvalue=0; |
643 |
start=0; |
644 |
if (wstart < 0) break; |
645 |
} |
646 |
if (!BN_from_montgomery(rr,r,mont,ctx)) goto err; |
647 |
ret=1; |
648 |
err: |
649 |
if ((in_mont == NULL) && (mont != NULL)) BN_MONT_CTX_free(mont); |
650 |
BN_CTX_end(ctx); |
651 |
for (i=0; i<ts; i++) |
652 |
BN_clear_free(&(val[i])); |
653 |
return(ret); |
654 |
} |
655 |
|
656 |
int BN_mod_exp_mont_word(BIGNUM *rr, BN_ULONG a, const BIGNUM *p, |
657 |
const BIGNUM *m, BN_CTX *ctx, BN_MONT_CTX *in_mont) |
658 |
{ |
659 |
BN_MONT_CTX *mont = NULL; |
660 |
int b, bits, ret=0; |
661 |
int r_is_one; |
662 |
BN_ULONG w, next_w; |
663 |
BIGNUM *d, *r, *t; |
664 |
BIGNUM *swap_tmp; |
665 |
#define BN_MOD_MUL_WORD(r, w, m) \ |
666 |
(BN_mul_word(r, (w)) && \ |
667 |
(/* BN_ucmp(r, (m)) < 0 ? 1 :*/ \ |
668 |
(BN_mod(t, r, m, ctx) && (swap_tmp = r, r = t, t = swap_tmp, 1)))) |
669 |
/* BN_MOD_MUL_WORD is only used with 'w' large, |
670 |
* so the BN_ucmp test is probably more overhead |
671 |
* than always using BN_mod (which uses BN_copy if |
672 |
* a similar test returns true). */ |
673 |
#define BN_TO_MONTGOMERY_WORD(r, w, mont) \ |
674 |
(BN_set_word(r, (w)) && BN_to_montgomery(r, r, (mont), ctx)) |
675 |
|
676 |
bn_check_top(p); |
677 |
bn_check_top(m); |
678 |
|
679 |
if (!(m->d[0] & 1)) |
680 |
{ |
681 |
BNerr(BN_F_BN_MOD_EXP_MONT_WORD,BN_R_CALLED_WITH_EVEN_MODULUS); |
682 |
return(0); |
683 |
} |
684 |
bits = BN_num_bits(p); |
685 |
if (bits == 0) |
686 |
{ |
687 |
BN_one(rr); |
688 |
return(1); |
689 |
} |
690 |
BN_CTX_start(ctx); |
691 |
d = BN_CTX_get(ctx); |
692 |
r = BN_CTX_get(ctx); |
693 |
t = BN_CTX_get(ctx); |
694 |
if (d == NULL || r == NULL || t == NULL) goto err; |
695 |
|
696 |
#ifdef ATALLA |
697 |
if (!tried_atalla) |
698 |
{ |
699 |
BN_set_word(t, a); |
700 |
if (BN_mod_exp_atalla(rr, t, p, m)) |
701 |
{ |
702 |
BN_CTX_end(ctx); |
703 |
return 1; |
704 |
} |
705 |
} |
706 |
/* If it fails, try the other methods */ |
707 |
#endif |
708 |
|
709 |
if (in_mont != NULL) |
710 |
mont=in_mont; |
711 |
else |
712 |
{ |
713 |
if ((mont = BN_MONT_CTX_new()) == NULL) goto err; |
714 |
if (!BN_MONT_CTX_set(mont, m, ctx)) goto err; |
715 |
} |
716 |
|
717 |
r_is_one = 1; /* except for Montgomery factor */ |
718 |
|
719 |
/* bits-1 >= 0 */ |
720 |
|
721 |
/* The result is accumulated in the product r*w. */ |
722 |
w = a; /* bit 'bits-1' of 'p' is always set */ |
723 |
for (b = bits-2; b >= 0; b--) |
724 |
{ |
725 |
/* First, square r*w. */ |
726 |
next_w = w*w; |
727 |
if ((next_w/w) != w) /* overflow */ |
728 |
{ |
729 |
if (r_is_one) |
730 |
{ |
731 |
if (!BN_TO_MONTGOMERY_WORD(r, w, mont)) goto err; |
732 |
r_is_one = 0; |
733 |
} |
734 |
else |
735 |
{ |
736 |
if (!BN_MOD_MUL_WORD(r, w, m)) goto err; |
737 |
} |
738 |
next_w = 1; |
739 |
} |
740 |
w = next_w; |
741 |
if (!r_is_one) |
742 |
{ |
743 |
if (!BN_mod_mul_montgomery(r, r, r, mont, ctx)) goto err; |
744 |
} |
745 |
|
746 |
/* Second, multiply r*w by 'a' if exponent bit is set. */ |
747 |
if (BN_is_bit_set(p, b)) |
748 |
{ |
749 |
next_w = w*a; |
750 |
if ((next_w/a) != w) /* overflow */ |
751 |
{ |
752 |
if (r_is_one) |
753 |
{ |
754 |
if (!BN_TO_MONTGOMERY_WORD(r, w, mont)) goto err; |
755 |
r_is_one = 0; |
756 |
} |
757 |
else |
758 |
{ |
759 |
if (!BN_MOD_MUL_WORD(r, w, m)) goto err; |
760 |
} |
761 |
next_w = a; |
762 |
} |
763 |
w = next_w; |
764 |
} |
765 |
} |
766 |
|
767 |
/* Finally, set r:=r*w. */ |
768 |
if (w != 1) |
769 |
{ |
770 |
if (r_is_one) |
771 |
{ |
772 |
if (!BN_TO_MONTGOMERY_WORD(r, w, mont)) goto err; |
773 |
r_is_one = 0; |
774 |
} |
775 |
else |
776 |
{ |
777 |
if (!BN_MOD_MUL_WORD(r, w, m)) goto err; |
778 |
} |
779 |
} |
780 |
|
781 |
if (r_is_one) /* can happen only if a == 1*/ |
782 |
{ |
783 |
if (!BN_one(rr)) goto err; |
784 |
} |
785 |
else |
786 |
{ |
787 |
if (!BN_from_montgomery(rr, r, mont, ctx)) goto err; |
788 |
} |
789 |
ret = 1; |
790 |
err: |
791 |
if ((in_mont == NULL) && (mont != NULL)) BN_MONT_CTX_free(mont); |
792 |
BN_CTX_end(ctx); |
793 |
return(ret); |
794 |
} |
795 |
#endif |
796 |
|
797 |
/* The old fallback, simple version :-) */ |
798 |
int BN_mod_exp_simple(BIGNUM *r, BIGNUM *a, const BIGNUM *p, const BIGNUM *m, |
799 |
BN_CTX *ctx) |
800 |
{ |
801 |
int i,j,bits,ret=0,wstart,wend,window,wvalue,ts=0; |
802 |
int start=1; |
803 |
BIGNUM *d; |
804 |
BIGNUM val[TABLE_SIZE]; |
805 |
|
806 |
bits=BN_num_bits(p); |
807 |
|
808 |
if (bits == 0) |
809 |
{ |
810 |
BN_one(r); |
811 |
return(1); |
812 |
} |
813 |
|
814 |
BN_CTX_start(ctx); |
815 |
if ((d = BN_CTX_get(ctx)) == NULL) goto err; |
816 |
|
817 |
BN_init(&(val[0])); |
818 |
ts=1; |
819 |
if (!BN_mod(&(val[0]),a,m,ctx)) goto err; /* 1 */ |
820 |
|
821 |
window = BN_window_bits_for_exponent_size(bits); |
822 |
if (window > 1) |
823 |
{ |
824 |
if (!BN_mod_mul(d,&(val[0]),&(val[0]),m,ctx)) |
825 |
goto err; /* 2 */ |
826 |
j=1<<(window-1); |
827 |
for (i=1; i<j; i++) |
828 |
{ |
829 |
BN_init(&(val[i])); |
830 |
if (!BN_mod_mul(&(val[i]),&(val[i-1]),d,m,ctx)) |
831 |
goto err; |
832 |
} |
833 |
ts=i; |
834 |
} |
835 |
|
836 |
start=1; /* This is used to avoid multiplication etc |
837 |
* when there is only the value '1' in the |
838 |
* buffer. */ |
839 |
wvalue=0; /* The 'value' of the window */ |
840 |
wstart=bits-1; /* The top bit of the window */ |
841 |
wend=0; /* The bottom bit of the window */ |
842 |
|
843 |
if (!BN_one(r)) goto err; |
844 |
|
845 |
for (;;) |
846 |
{ |
847 |
if (BN_is_bit_set(p,wstart) == 0) |
848 |
{ |
849 |
if (!start) |
850 |
if (!BN_mod_mul(r,r,r,m,ctx)) |
851 |
goto err; |
852 |
if (wstart == 0) break; |
853 |
wstart--; |
854 |
continue; |
855 |
} |
856 |
/* We now have wstart on a 'set' bit, we now need to work out |
857 |
* how bit a window to do. To do this we need to scan |
858 |
* forward until the last set bit before the end of the |
859 |
* window */ |
860 |
j=wstart; |
861 |
wvalue=1; |
862 |
wend=0; |
863 |
for (i=1; i<window; i++) |
864 |
{ |
865 |
if (wstart-i < 0) break; |
866 |
if (BN_is_bit_set(p,wstart-i)) |
867 |
{ |
868 |
wvalue<<=(i-wend); |
869 |
wvalue|=1; |
870 |
wend=i; |
871 |
} |
872 |
} |
873 |
|
874 |
/* wend is the size of the current window */ |
875 |
j=wend+1; |
876 |
/* add the 'bytes above' */ |
877 |
if (!start) |
878 |
for (i=0; i<j; i++) |
879 |
{ |
880 |
if (!BN_mod_mul(r,r,r,m,ctx)) |
881 |
goto err; |
882 |
} |
883 |
|
884 |
/* wvalue will be an odd number < 2^window */ |
885 |
if (!BN_mod_mul(r,r,&(val[wvalue>>1]),m,ctx)) |
886 |
goto err; |
887 |
|
888 |
/* move the 'window' down further */ |
889 |
wstart-=wend+1; |
890 |
wvalue=0; |
891 |
start=0; |
892 |
if (wstart < 0) break; |
893 |
} |
894 |
ret=1; |
895 |
err: |
896 |
BN_CTX_end(ctx); |
897 |
for (i=0; i<ts; i++) |
898 |
BN_clear_free(&(val[i])); |
899 |
return(ret); |
900 |
} |
901 |
|