summaryrefslogtreecommitdiff
path: root/src/lib/libcrypto/bn/bn_exp.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/lib/libcrypto/bn/bn_exp.c')
-rw-r--r--src/lib/libcrypto/bn/bn_exp.c521
1 files changed, 234 insertions, 287 deletions
diff --git a/src/lib/libcrypto/bn/bn_exp.c b/src/lib/libcrypto/bn/bn_exp.c
index 0c11601675..d2c91628ac 100644
--- a/src/lib/libcrypto/bn/bn_exp.c
+++ b/src/lib/libcrypto/bn/bn_exp.c
@@ -55,18 +55,66 @@
55 * copied and put under another distribution licence 55 * copied and put under another distribution licence
56 * [including the GNU Public Licence.] 56 * [including the GNU Public Licence.]
57 */ 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
58 112
59#include <stdio.h> 113#include <stdio.h>
60#include "cryptlib.h" 114#include "cryptlib.h"
61#include "bn_lcl.h" 115#include "bn_lcl.h"
62#ifdef ATALLA
63# include <alloca.h>
64# include <atasi.h>
65# include <assert.h>
66# include <dlfcn.h>
67#endif
68 116
69#define TABLE_SIZE 16 117#define TABLE_SIZE 32
70 118
71/* slow but works */ 119/* slow but works */
72int BN_mod_mul(BIGNUM *ret, BIGNUM *a, BIGNUM *b, const BIGNUM *m, BN_CTX *ctx) 120int BN_mod_mul(BIGNUM *ret, BIGNUM *a, BIGNUM *b, const BIGNUM *m, BN_CTX *ctx)
@@ -91,42 +139,6 @@ err:
91 return(r); 139 return(r);
92 } 140 }
93 141
94#if 0
95/* this one works - simple but works */
96int BN_mod_exp(BIGNUM *r, BIGNUM *a, BIGNUM *p, BIGNUM *m, BN_CTX *ctx)
97 {
98 int i,bits,ret=0;
99 BIGNUM *v,*tmp;
100
101 BN_CTX_start(ctx);
102 v = BN_CTX_get(ctx);
103 tmp = BN_CTX_get(ctx);
104 if (v == NULL || tmp == NULL) goto err;
105
106 if (BN_copy(v,a) == NULL) goto err;
107 bits=BN_num_bits(p);
108
109 if (BN_is_odd(p))
110 { if (BN_copy(r,a) == NULL) goto err; }
111 else { if (!BN_one(r)) goto err; }
112
113 for (i=1; i<bits; i++)
114 {
115 if (!BN_sqr(tmp,v,ctx)) goto err;
116 if (!BN_mod(v,tmp,m,ctx)) goto err;
117 if (BN_is_bit_set(p,i))
118 {
119 if (!BN_mul(tmp,r,v,ctx)) goto err;
120 if (!BN_mod(r,tmp,m,ctx)) goto err;
121 }
122 }
123 ret=1;
124err:
125 BN_CTX_end(ctx);
126 return(ret);
127 }
128
129#endif
130 142
131/* this one works - simple but works */ 143/* this one works - simple but works */
132int BN_exp(BIGNUM *r, BIGNUM *a, BIGNUM *p, BN_CTX *ctx) 144int BN_exp(BIGNUM *r, BIGNUM *a, BIGNUM *p, BN_CTX *ctx)
@@ -163,172 +175,6 @@ err:
163 return(ret); 175 return(ret);
164 } 176 }
165 177
166#ifdef ATALLA
167
168/*
169 * This routine will dynamically check for the existance of an Atalla AXL-200
170 * SSL accelerator module. If one is found, the variable
171 * asi_accelerator_present is set to 1 and the function pointers
172 * ptr_ASI_xxxxxx above will be initialized to corresponding ASI API calls.
173 */
174typedef int tfnASI_GetPerformanceStatistics(int reset_flag,
175 unsigned int *ret_buf);
176typedef int tfnASI_GetHardwareConfig(long card_num, unsigned int *ret_buf);
177typedef int tfnASI_RSAPrivateKeyOpFn(RSAPrivateKey * rsaKey,
178 unsigned char *output,
179 unsigned char *input,
180 unsigned int modulus_len);
181
182static tfnASI_GetHardwareConfig *ptr_ASI_GetHardwareConfig;
183static tfnASI_RSAPrivateKeyOpFn *ptr_ASI_RSAPrivateKeyOpFn;
184static tfnASI_GetPerformanceStatistics *ptr_ASI_GetPerformanceStatistics;
185static int asi_accelerator_present;
186static int tried_atalla;
187
188void atalla_initialize_accelerator_handle(void)
189 {
190 void *dl_handle;
191 int status;
192 unsigned int config_buf[1024];
193 static int tested;
194
195 if(tested)
196 return;
197
198 tested=1;
199
200 bzero((void *)config_buf, 1024);
201
202 /*
203 * Check to see if the library is present on the system
204 */
205 dl_handle = dlopen("atasi.so", RTLD_NOW);
206 if (dl_handle == (void *) NULL)
207 {
208/* printf("atasi.so library is not present on the system\n");
209 printf("No HW acceleration available\n");*/
210 return;
211 }
212
213 /*
214 * The library is present. Now we'll check to insure that the
215 * LDM is up and running. First we'll get the address of the
216 * function in the atasi library that we need to see if the
217 * LDM is operating.
218 */
219
220 ptr_ASI_GetHardwareConfig =
221 (tfnASI_GetHardwareConfig *)dlsym(dl_handle,"ASI_GetHardwareConfig");
222
223 if (ptr_ASI_GetHardwareConfig)
224 {
225 /*
226 * We found the call, now we'll get our config
227 * status. If we get a non 0 result, the LDM is not
228 * running and we cannot use the Atalla ASI *
229 * library.
230 */
231 status = (*ptr_ASI_GetHardwareConfig)(0L, config_buf);
232 if (status != 0)
233 {
234 printf("atasi.so library is present but not initialized\n");
235 printf("No HW acceleration available\n");
236 return;
237 }
238 }
239 else
240 {
241/* printf("We found the library, but not the function. Very Strange!\n");*/
242 return ;
243 }
244
245 /*
246 * It looks like we have acceleration capabilities. Load up the
247 * pointers to our ASI API calls.
248 */
249 ptr_ASI_RSAPrivateKeyOpFn=
250 (tfnASI_RSAPrivateKeyOpFn *)dlsym(dl_handle, "ASI_RSAPrivateKeyOpFn");
251 if (ptr_ASI_RSAPrivateKeyOpFn == NULL)
252 {
253/* printf("We found the library, but no RSA function. Very Strange!\n");*/
254 return;
255 }
256
257 ptr_ASI_GetPerformanceStatistics =
258 (tfnASI_GetPerformanceStatistics *)dlsym(dl_handle, "ASI_GetPerformanceStatistics");
259 if (ptr_ASI_GetPerformanceStatistics == NULL)
260 {
261/* printf("We found the library, but no stat function. Very Strange!\n");*/
262 return;
263 }
264
265 /*
266 * Indicate that acceleration is available
267 */
268 asi_accelerator_present = 1;
269
270/* printf("This system has acceleration!\n");*/
271
272 return;
273 }
274
275/* make sure this only gets called once when bn_mod_exp calls bn_mod_exp_mont */
276int BN_mod_exp_atalla(BIGNUM *r, BIGNUM *a, const BIGNUM *p, const BIGNUM *m)
277 {
278 unsigned char *abin;
279 unsigned char *pbin;
280 unsigned char *mbin;
281 unsigned char *rbin;
282 int an,pn,mn,ret;
283 RSAPrivateKey keydata;
284
285 atalla_initialize_accelerator_handle();
286 if(!asi_accelerator_present)
287 return 0;
288
289
290/* We should be able to run without size testing */
291# define ASIZE 128
292 an=BN_num_bytes(a);
293 pn=BN_num_bytes(p);
294 mn=BN_num_bytes(m);
295
296 if(an <= ASIZE && pn <= ASIZE && mn <= ASIZE)
297 {
298 int size=mn;
299
300 assert(an <= mn);
301 abin=alloca(size);
302 memset(abin,'\0',mn);
303 BN_bn2bin(a,abin+size-an);
304
305 pbin=alloca(pn);
306 BN_bn2bin(p,pbin);
307
308 mbin=alloca(size);
309 memset(mbin,'\0',mn);
310 BN_bn2bin(m,mbin+size-mn);
311
312 rbin=alloca(size);
313
314 memset(&keydata,'\0',sizeof keydata);
315 keydata.privateExponent.data=pbin;
316 keydata.privateExponent.len=pn;
317 keydata.modulus.data=mbin;
318 keydata.modulus.len=size;
319
320 ret=(*ptr_ASI_RSAPrivateKeyOpFn)(&keydata,rbin,abin,keydata.modulus.len);
321/*fprintf(stderr,"!%s\n",BN_bn2hex(a));*/
322 if(!ret)
323 {
324 BN_bin2bn(rbin,keydata.modulus.len,r);
325/*fprintf(stderr,"?%s\n",BN_bn2hex(r));*/
326 return 1;
327 }
328 }
329 return 0;
330 }
331#endif /* def ATALLA */
332 178
333int BN_mod_exp(BIGNUM *r, BIGNUM *a, const BIGNUM *p, const BIGNUM *m, 179int BN_mod_exp(BIGNUM *r, BIGNUM *a, const BIGNUM *p, const BIGNUM *m,
334 BN_CTX *ctx) 180 BN_CTX *ctx)
@@ -339,13 +185,6 @@ int BN_mod_exp(BIGNUM *r, BIGNUM *a, const BIGNUM *p, const BIGNUM *m,
339 bn_check_top(p); 185 bn_check_top(p);
340 bn_check_top(m); 186 bn_check_top(m);
341 187
342#ifdef ATALLA
343 if(BN_mod_exp_atalla(r,a,p,m))
344 return 1;
345/* If it fails, try the other methods (but don't try atalla again) */
346 tried_atalla=1;
347#endif
348
349#ifdef MONT_MUL_MOD 188#ifdef MONT_MUL_MOD
350 /* I have finally been able to take out this pre-condition of 189 /* I have finally been able to take out this pre-condition of
351 * the top bit being set. It was caused by an error in BN_div 190 * the top bit being set. It was caused by an error in BN_div
@@ -354,7 +193,15 @@ int BN_mod_exp(BIGNUM *r, BIGNUM *a, const BIGNUM *p, const BIGNUM *m,
354/* if ((m->d[m->top-1]&BN_TBIT) && BN_is_odd(m)) */ 193/* if ((m->d[m->top-1]&BN_TBIT) && BN_is_odd(m)) */
355 194
356 if (BN_is_odd(m)) 195 if (BN_is_odd(m))
357 { ret=BN_mod_exp_mont(r,a,p,m,ctx,NULL); } 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 }
358 else 205 else
359#endif 206#endif
360#ifdef RECP_MUL_MOD 207#ifdef RECP_MUL_MOD
@@ -363,14 +210,10 @@ int BN_mod_exp(BIGNUM *r, BIGNUM *a, const BIGNUM *p, const BIGNUM *m,
363 { ret=BN_mod_exp_simple(r,a,p,m,ctx); } 210 { ret=BN_mod_exp_simple(r,a,p,m,ctx); }
364#endif 211#endif
365 212
366#ifdef ATALLA
367 tried_atalla=0;
368#endif
369
370 return(ret); 213 return(ret);
371 } 214 }
372 215
373/* #ifdef RECP_MUL_MOD */ 216
374int BN_mod_exp_recp(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, 217int BN_mod_exp_recp(BIGNUM *r, const BIGNUM *a, const BIGNUM *p,
375 const BIGNUM *m, BN_CTX *ctx) 218 const BIGNUM *m, BN_CTX *ctx)
376 { 219 {
@@ -398,27 +241,22 @@ int BN_mod_exp_recp(BIGNUM *r, const BIGNUM *a, const BIGNUM *p,
398 ts=1; 241 ts=1;
399 242
400 if (!BN_mod(&(val[0]),a,m,ctx)) goto err; /* 1 */ 243 if (!BN_mod(&(val[0]),a,m,ctx)) goto err; /* 1 */
401 if (!BN_mod_mul_reciprocal(aa,&(val[0]),&(val[0]),&recp,ctx))
402 goto err; /* 2 */
403
404 if (bits <= 17) /* This is probably 3 or 0x10001, so just do singles */
405 window=1;
406 else if (bits >= 256)
407 window=5; /* max size of window */
408 else if (bits >= 128)
409 window=4;
410 else
411 window=3;
412 244
413 j=1<<(window-1); 245 window = BN_window_bits_for_exponent_size(bits);
414 for (i=1; i<j; i++) 246 if (window > 1)
415 { 247 {
416 BN_init(&val[i]); 248 if (!BN_mod_mul_reciprocal(aa,&(val[0]),&(val[0]),&recp,ctx))
417 if (!BN_mod_mul_reciprocal(&(val[i]),&(val[i-1]),aa,&recp,ctx)) 249 goto err; /* 2 */
418 goto err; 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;
419 } 258 }
420 ts=i; 259
421
422 start=1; /* This is used to avoid multiplication etc 260 start=1; /* This is used to avoid multiplication etc
423 * when there is only the value '1' in the 261 * when there is only the value '1' in the
424 * buffer. */ 262 * buffer. */
@@ -485,9 +323,8 @@ err:
485 BN_RECP_CTX_free(&recp); 323 BN_RECP_CTX_free(&recp);
486 return(ret); 324 return(ret);
487 } 325 }
488/* #endif */
489 326
490/* #ifdef MONT_MUL_MOD */ 327
491int BN_mod_exp_mont(BIGNUM *rr, BIGNUM *a, const BIGNUM *p, 328int BN_mod_exp_mont(BIGNUM *rr, BIGNUM *a, const BIGNUM *p,
492 const BIGNUM *m, BN_CTX *ctx, BN_MONT_CTX *in_mont) 329 const BIGNUM *m, BN_CTX *ctx, BN_MONT_CTX *in_mont)
493 { 330 {
@@ -502,12 +339,6 @@ int BN_mod_exp_mont(BIGNUM *rr, BIGNUM *a, const BIGNUM *p,
502 bn_check_top(p); 339 bn_check_top(p);
503 bn_check_top(m); 340 bn_check_top(m);
504 341
505#ifdef ATALLA
506 if(!tried_atalla && BN_mod_exp_atalla(rr,a,p,m))
507 return 1;
508/* If it fails, try the other methods */
509#endif
510
511 if (!(m->d[0] & 1)) 342 if (!(m->d[0] & 1))
512 { 343 {
513 BNerr(BN_F_BN_MOD_EXP_MONT,BN_R_CALLED_WITH_EVEN_MODULUS); 344 BNerr(BN_F_BN_MOD_EXP_MONT,BN_R_CALLED_WITH_EVEN_MODULUS);
@@ -527,11 +358,9 @@ int BN_mod_exp_mont(BIGNUM *rr, BIGNUM *a, const BIGNUM *p,
527 /* If this is not done, things will break in the montgomery 358 /* If this is not done, things will break in the montgomery
528 * part */ 359 * part */
529 360
530#if 1
531 if (in_mont != NULL) 361 if (in_mont != NULL)
532 mont=in_mont; 362 mont=in_mont;
533 else 363 else
534#endif
535 { 364 {
536 if ((mont=BN_MONT_CTX_new()) == NULL) goto err; 365 if ((mont=BN_MONT_CTX_new()) == NULL) goto err;
537 if (!BN_MONT_CTX_set(mont,m,ctx)) goto err; 366 if (!BN_MONT_CTX_set(mont,m,ctx)) goto err;
@@ -541,31 +370,27 @@ int BN_mod_exp_mont(BIGNUM *rr, BIGNUM *a, const BIGNUM *p,
541 ts=1; 370 ts=1;
542 if (BN_ucmp(a,m) >= 0) 371 if (BN_ucmp(a,m) >= 0)
543 { 372 {
544 BN_mod(&(val[0]),a,m,ctx); 373 if (!BN_mod(&(val[0]),a,m,ctx))
374 goto err;
545 aa= &(val[0]); 375 aa= &(val[0]);
546 } 376 }
547 else 377 else
548 aa=a; 378 aa=a;
549 if (!BN_to_montgomery(&(val[0]),aa,mont,ctx)) goto err; /* 1 */ 379 if (!BN_to_montgomery(&(val[0]),aa,mont,ctx)) goto err; /* 1 */
550 if (!BN_mod_mul_montgomery(d,&(val[0]),&(val[0]),mont,ctx)) goto err; /* 2 */
551
552 if (bits <= 20) /* This is probably 3 or 0x10001, so just do singles */
553 window=1;
554 else if (bits >= 256)
555 window=5; /* max size of window */
556 else if (bits >= 128)
557 window=4;
558 else
559 window=3;
560 380
561 j=1<<(window-1); 381 window = BN_window_bits_for_exponent_size(bits);
562 for (i=1; i<j; i++) 382 if (window > 1)
563 { 383 {
564 BN_init(&(val[i])); 384 if (!BN_mod_mul_montgomery(d,&(val[0]),&(val[0]),mont,ctx)) goto err; /* 2 */
565 if (!BN_mod_mul_montgomery(&(val[i]),&(val[i-1]),d,mont,ctx)) 385 j=1<<(window-1);
566 goto err; 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;
567 } 393 }
568 ts=i;
569 394
570 start=1; /* This is used to avoid multiplication etc 395 start=1; /* This is used to avoid multiplication etc
571 * when there is only the value '1' in the 396 * when there is only the value '1' in the
@@ -574,7 +399,7 @@ int BN_mod_exp_mont(BIGNUM *rr, BIGNUM *a, const BIGNUM *p,
574 wstart=bits-1; /* The top bit of the window */ 399 wstart=bits-1; /* The top bit of the window */
575 wend=0; /* The bottom bit of the window */ 400 wend=0; /* The bottom bit of the window */
576 401
577 if (!BN_to_montgomery(r,BN_value_one(),mont,ctx)) goto err; 402 if (!BN_to_montgomery(r,BN_value_one(),mont,ctx)) goto err;
578 for (;;) 403 for (;;)
579 { 404 {
580 if (BN_is_bit_set(p,wstart) == 0) 405 if (BN_is_bit_set(p,wstart) == 0)
@@ -626,7 +451,7 @@ int BN_mod_exp_mont(BIGNUM *rr, BIGNUM *a, const BIGNUM *p,
626 start=0; 451 start=0;
627 if (wstart < 0) break; 452 if (wstart < 0) break;
628 } 453 }
629 BN_from_montgomery(rr,r,mont,ctx); 454 if (!BN_from_montgomery(rr,r,mont,ctx)) goto err;
630 ret=1; 455 ret=1;
631err: 456err:
632 if ((in_mont == NULL) && (mont != NULL)) BN_MONT_CTX_free(mont); 457 if ((in_mont == NULL) && (mont != NULL)) BN_MONT_CTX_free(mont);
@@ -635,7 +460,134 @@ err:
635 BN_clear_free(&(val[i])); 460 BN_clear_free(&(val[i]));
636 return(ret); 461 return(ret);
637 } 462 }
638/* #endif */ 463
464int 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;
585err:
586 if ((in_mont == NULL) && (mont != NULL)) BN_MONT_CTX_free(mont);
587 BN_CTX_end(ctx);
588 return(ret);
589 }
590
639 591
640/* The old fallback, simple version :-) */ 592/* The old fallback, simple version :-) */
641int BN_mod_exp_simple(BIGNUM *r, BIGNUM *a, BIGNUM *p, BIGNUM *m, 593int BN_mod_exp_simple(BIGNUM *r, BIGNUM *a, BIGNUM *p, BIGNUM *m,
@@ -660,26 +612,21 @@ int BN_mod_exp_simple(BIGNUM *r, BIGNUM *a, BIGNUM *p, BIGNUM *m,
660 BN_init(&(val[0])); 612 BN_init(&(val[0]));
661 ts=1; 613 ts=1;
662 if (!BN_mod(&(val[0]),a,m,ctx)) goto err; /* 1 */ 614 if (!BN_mod(&(val[0]),a,m,ctx)) goto err; /* 1 */
663 if (!BN_mod_mul(d,&(val[0]),&(val[0]),m,ctx))
664 goto err; /* 2 */
665
666 if (bits <= 17) /* This is probably 3 or 0x10001, so just do singles */
667 window=1;
668 else if (bits >= 256)
669 window=5; /* max size of window */
670 else if (bits >= 128)
671 window=4;
672 else
673 window=3;
674 615
675 j=1<<(window-1); 616 window = BN_window_bits_for_exponent_size(bits);
676 for (i=1; i<j; i++) 617 if (window > 1)
677 { 618 {
678 BN_init(&(val[i])); 619 if (!BN_mod_mul(d,&(val[0]),&(val[0]),m,ctx))
679 if (!BN_mod_mul(&(val[i]),&(val[i-1]),d,m,ctx)) 620 goto err; /* 2 */
680 goto err; 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;
681 } 629 }
682 ts=i;
683 630
684 start=1; /* This is used to avoid multiplication etc 631 start=1; /* This is used to avoid multiplication etc
685 * when there is only the value '1' in the 632 * when there is only the value '1' in the
generated by cgit v1.2.3-55-g6feb (git 2.39.1) at 2025-11-23 17:41:36 +0000