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.c133
1 files changed, 65 insertions, 68 deletions
diff --git a/src/lib/libcrypto/bn/bn_exp.c b/src/lib/libcrypto/bn/bn_exp.c
index 70a33f0d93..9e1e88abe8 100644
--- a/src/lib/libcrypto/bn/bn_exp.c
+++ b/src/lib/libcrypto/bn/bn_exp.c
@@ -122,9 +122,9 @@ int BN_exp(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx)
122 int i,bits,ret=0; 122 int i,bits,ret=0;
123 BIGNUM *v,*rr; 123 BIGNUM *v,*rr;
124 124
125 if (BN_get_flags(p, BN_FLG_CONSTTIME) != 0) 125 if (BN_get_flags(p, BN_FLG_EXP_CONSTTIME) != 0)
126 { 126 {
127 /* BN_FLG_CONSTTIME only supported by BN_mod_exp_mont() */ 127 /* BN_FLG_EXP_CONSTTIME only supported by BN_mod_exp_mont() */
128 BNerr(BN_F_BN_EXP,ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED); 128 BNerr(BN_F_BN_EXP,ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
129 return -1; 129 return -1;
130 } 130 }
@@ -155,7 +155,6 @@ int BN_exp(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx)
155err: 155err:
156 if (r != rr) BN_copy(r,rr); 156 if (r != rr) BN_copy(r,rr);
157 BN_CTX_end(ctx); 157 BN_CTX_end(ctx);
158 bn_check_top(r);
159 return(ret); 158 return(ret);
160 } 159 }
161 160
@@ -213,7 +212,7 @@ int BN_mod_exp(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, const BIGNUM *m,
213 if (BN_is_odd(m)) 212 if (BN_is_odd(m))
214 { 213 {
215# ifdef MONT_EXP_WORD 214# ifdef MONT_EXP_WORD
216 if (a->top == 1 && !a->neg && (BN_get_flags(p, BN_FLG_CONSTTIME) == 0)) 215 if (a->top == 1 && !a->neg && (BN_get_flags(p, BN_FLG_EXP_CONSTTIME) == 0))
217 { 216 {
218 BN_ULONG A = a->d[0]; 217 BN_ULONG A = a->d[0];
219 ret=BN_mod_exp_mont_word(r,A,p,m,ctx,NULL); 218 ret=BN_mod_exp_mont_word(r,A,p,m,ctx,NULL);
@@ -230,7 +229,6 @@ int BN_mod_exp(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, const BIGNUM *m,
230 { ret=BN_mod_exp_simple(r,a,p,m,ctx); } 229 { ret=BN_mod_exp_simple(r,a,p,m,ctx); }
231#endif 230#endif
232 231
233 bn_check_top(r);
234 return(ret); 232 return(ret);
235 } 233 }
236 234
@@ -239,15 +237,14 @@ int BN_mod_exp_recp(BIGNUM *r, const BIGNUM *a, const BIGNUM *p,
239 const BIGNUM *m, BN_CTX *ctx) 237 const BIGNUM *m, BN_CTX *ctx)
240 { 238 {
241 int i,j,bits,ret=0,wstart,wend,window,wvalue; 239 int i,j,bits,ret=0,wstart,wend,window,wvalue;
242 int start=1; 240 int start=1,ts=0;
243 BIGNUM *aa; 241 BIGNUM *aa;
244 /* Table of variables obtained from 'ctx' */ 242 BIGNUM val[TABLE_SIZE];
245 BIGNUM *val[TABLE_SIZE];
246 BN_RECP_CTX recp; 243 BN_RECP_CTX recp;
247 244
248 if (BN_get_flags(p, BN_FLG_CONSTTIME) != 0) 245 if (BN_get_flags(p, BN_FLG_EXP_CONSTTIME) != 0)
249 { 246 {
250 /* BN_FLG_CONSTTIME only supported by BN_mod_exp_mont() */ 247 /* BN_FLG_EXP_CONSTTIME only supported by BN_mod_exp_mont() */
251 BNerr(BN_F_BN_MOD_EXP_RECP,ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED); 248 BNerr(BN_F_BN_MOD_EXP_RECP,ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
252 return -1; 249 return -1;
253 } 250 }
@@ -261,9 +258,7 @@ int BN_mod_exp_recp(BIGNUM *r, const BIGNUM *a, const BIGNUM *p,
261 } 258 }
262 259
263 BN_CTX_start(ctx); 260 BN_CTX_start(ctx);
264 aa = BN_CTX_get(ctx); 261 if ((aa = BN_CTX_get(ctx)) == NULL) goto err;
265 val[0] = BN_CTX_get(ctx);
266 if(!aa || !val[0]) goto err;
267 262
268 BN_RECP_CTX_init(&recp); 263 BN_RECP_CTX_init(&recp);
269 if (m->neg) 264 if (m->neg)
@@ -278,27 +273,29 @@ int BN_mod_exp_recp(BIGNUM *r, const BIGNUM *a, const BIGNUM *p,
278 if (BN_RECP_CTX_set(&recp,m,ctx) <= 0) goto err; 273 if (BN_RECP_CTX_set(&recp,m,ctx) <= 0) goto err;
279 } 274 }
280 275
281 if (!BN_nnmod(val[0],a,m,ctx)) goto err; /* 1 */ 276 BN_init(&(val[0]));
282 if (BN_is_zero(val[0])) 277 ts=1;
278
279 if (!BN_nnmod(&(val[0]),a,m,ctx)) goto err; /* 1 */
280 if (BN_is_zero(&(val[0])))
283 { 281 {
284 BN_zero(r); 282 ret = BN_zero(r);
285 ret = 1;
286 goto err; 283 goto err;
287 } 284 }
288 285
289 window = BN_window_bits_for_exponent_size(bits); 286 window = BN_window_bits_for_exponent_size(bits);
290 if (window > 1) 287 if (window > 1)
291 { 288 {
292 if (!BN_mod_mul_reciprocal(aa,val[0],val[0],&recp,ctx)) 289 if (!BN_mod_mul_reciprocal(aa,&(val[0]),&(val[0]),&recp,ctx))
293 goto err; /* 2 */ 290 goto err; /* 2 */
294 j=1<<(window-1); 291 j=1<<(window-1);
295 for (i=1; i<j; i++) 292 for (i=1; i<j; i++)
296 { 293 {
297 if(((val[i] = BN_CTX_get(ctx)) == NULL) || 294 BN_init(&val[i]);
298 !BN_mod_mul_reciprocal(val[i],val[i-1], 295 if (!BN_mod_mul_reciprocal(&(val[i]),&(val[i-1]),aa,&recp,ctx))
299 aa,&recp,ctx))
300 goto err; 296 goto err;
301 } 297 }
298 ts=i;
302 } 299 }
303 300
304 start=1; /* This is used to avoid multiplication etc 301 start=1; /* This is used to avoid multiplication etc
@@ -350,7 +347,7 @@ int BN_mod_exp_recp(BIGNUM *r, const BIGNUM *a, const BIGNUM *p,
350 } 347 }
351 348
352 /* wvalue will be an odd number < 2^window */ 349 /* wvalue will be an odd number < 2^window */
353 if (!BN_mod_mul_reciprocal(r,r,val[wvalue>>1],&recp,ctx)) 350 if (!BN_mod_mul_reciprocal(r,r,&(val[wvalue>>1]),&recp,ctx))
354 goto err; 351 goto err;
355 352
356 /* move the 'window' down further */ 353 /* move the 'window' down further */
@@ -362,8 +359,9 @@ int BN_mod_exp_recp(BIGNUM *r, const BIGNUM *a, const BIGNUM *p,
362 ret=1; 359 ret=1;
363err: 360err:
364 BN_CTX_end(ctx); 361 BN_CTX_end(ctx);
362 for (i=0; i<ts; i++)
363 BN_clear_free(&(val[i]));
365 BN_RECP_CTX_free(&recp); 364 BN_RECP_CTX_free(&recp);
366 bn_check_top(r);
367 return(ret); 365 return(ret);
368 } 366 }
369 367
@@ -372,14 +370,13 @@ int BN_mod_exp_mont(BIGNUM *rr, const BIGNUM *a, const BIGNUM *p,
372 const BIGNUM *m, BN_CTX *ctx, BN_MONT_CTX *in_mont) 370 const BIGNUM *m, BN_CTX *ctx, BN_MONT_CTX *in_mont)
373 { 371 {
374 int i,j,bits,ret=0,wstart,wend,window,wvalue; 372 int i,j,bits,ret=0,wstart,wend,window,wvalue;
375 int start=1; 373 int start=1,ts=0;
376 BIGNUM *d,*r; 374 BIGNUM *d,*r;
377 const BIGNUM *aa; 375 const BIGNUM *aa;
378 /* Table of variables obtained from 'ctx' */ 376 BIGNUM val[TABLE_SIZE];
379 BIGNUM *val[TABLE_SIZE];
380 BN_MONT_CTX *mont=NULL; 377 BN_MONT_CTX *mont=NULL;
381 378
382 if (BN_get_flags(p, BN_FLG_CONSTTIME) != 0) 379 if (BN_get_flags(p, BN_FLG_EXP_CONSTTIME) != 0)
383 { 380 {
384 return BN_mod_exp_mont_consttime(rr, a, p, m, ctx, in_mont); 381 return BN_mod_exp_mont_consttime(rr, a, p, m, ctx, in_mont);
385 } 382 }
@@ -388,7 +385,7 @@ int BN_mod_exp_mont(BIGNUM *rr, const BIGNUM *a, const BIGNUM *p,
388 bn_check_top(p); 385 bn_check_top(p);
389 bn_check_top(m); 386 bn_check_top(m);
390 387
391 if (!BN_is_odd(m)) 388 if (!(m->d[0] & 1))
392 { 389 {
393 BNerr(BN_F_BN_MOD_EXP_MONT,BN_R_CALLED_WITH_EVEN_MODULUS); 390 BNerr(BN_F_BN_MOD_EXP_MONT,BN_R_CALLED_WITH_EVEN_MODULUS);
394 return(0); 391 return(0);
@@ -403,8 +400,7 @@ int BN_mod_exp_mont(BIGNUM *rr, const BIGNUM *a, const BIGNUM *p,
403 BN_CTX_start(ctx); 400 BN_CTX_start(ctx);
404 d = BN_CTX_get(ctx); 401 d = BN_CTX_get(ctx);
405 r = BN_CTX_get(ctx); 402 r = BN_CTX_get(ctx);
406 val[0] = BN_CTX_get(ctx); 403 if (d == NULL || r == NULL) goto err;
407 if (!d || !r || !val[0]) goto err;
408 404
409 /* If this is not done, things will break in the montgomery 405 /* If this is not done, things will break in the montgomery
410 * part */ 406 * part */
@@ -417,34 +413,35 @@ int BN_mod_exp_mont(BIGNUM *rr, const BIGNUM *a, const BIGNUM *p,
417 if (!BN_MONT_CTX_set(mont,m,ctx)) goto err; 413 if (!BN_MONT_CTX_set(mont,m,ctx)) goto err;
418 } 414 }
419 415
416 BN_init(&val[0]);
417 ts=1;
420 if (a->neg || BN_ucmp(a,m) >= 0) 418 if (a->neg || BN_ucmp(a,m) >= 0)
421 { 419 {
422 if (!BN_nnmod(val[0],a,m,ctx)) 420 if (!BN_nnmod(&(val[0]),a,m,ctx))
423 goto err; 421 goto err;
424 aa= val[0]; 422 aa= &(val[0]);
425 } 423 }
426 else 424 else
427 aa=a; 425 aa=a;
428 if (BN_is_zero(aa)) 426 if (BN_is_zero(aa))
429 { 427 {
430 BN_zero(rr); 428 ret = BN_zero(rr);
431 ret = 1;
432 goto err; 429 goto err;
433 } 430 }
434 if (!BN_to_montgomery(val[0],aa,mont,ctx)) goto err; /* 1 */ 431 if (!BN_to_montgomery(&(val[0]),aa,mont,ctx)) goto err; /* 1 */
435 432
436 window = BN_window_bits_for_exponent_size(bits); 433 window = BN_window_bits_for_exponent_size(bits);
437 if (window > 1) 434 if (window > 1)
438 { 435 {
439 if (!BN_mod_mul_montgomery(d,val[0],val[0],mont,ctx)) goto err; /* 2 */ 436 if (!BN_mod_mul_montgomery(d,&(val[0]),&(val[0]),mont,ctx)) goto err; /* 2 */
440 j=1<<(window-1); 437 j=1<<(window-1);
441 for (i=1; i<j; i++) 438 for (i=1; i<j; i++)
442 { 439 {
443 if(((val[i] = BN_CTX_get(ctx)) == NULL) || 440 BN_init(&(val[i]));
444 !BN_mod_mul_montgomery(val[i],val[i-1], 441 if (!BN_mod_mul_montgomery(&(val[i]),&(val[i-1]),d,mont,ctx))
445 d,mont,ctx))
446 goto err; 442 goto err;
447 } 443 }
444 ts=i;
448 } 445 }
449 446
450 start=1; /* This is used to avoid multiplication etc 447 start=1; /* This is used to avoid multiplication etc
@@ -497,7 +494,7 @@ int BN_mod_exp_mont(BIGNUM *rr, const BIGNUM *a, const BIGNUM *p,
497 } 494 }
498 495
499 /* wvalue will be an odd number < 2^window */ 496 /* wvalue will be an odd number < 2^window */
500 if (!BN_mod_mul_montgomery(r,r,val[wvalue>>1],mont,ctx)) 497 if (!BN_mod_mul_montgomery(r,r,&(val[wvalue>>1]),mont,ctx))
501 goto err; 498 goto err;
502 499
503 /* move the 'window' down further */ 500 /* move the 'window' down further */
@@ -511,7 +508,8 @@ int BN_mod_exp_mont(BIGNUM *rr, const BIGNUM *a, const BIGNUM *p,
511err: 508err:
512 if ((in_mont == NULL) && (mont != NULL)) BN_MONT_CTX_free(mont); 509 if ((in_mont == NULL) && (mont != NULL)) BN_MONT_CTX_free(mont);
513 BN_CTX_end(ctx); 510 BN_CTX_end(ctx);
514 bn_check_top(rr); 511 for (i=0; i<ts; i++)
512 BN_clear_free(&(val[i]));
515 return(ret); 513 return(ret);
516 } 514 }
517 515
@@ -537,7 +535,7 @@ static int MOD_EXP_CTIME_COPY_TO_PREBUF(BIGNUM *b, int top, unsigned char *buf,
537 buf[j] = ((unsigned char*)b->d)[i]; 535 buf[j] = ((unsigned char*)b->d)[i];
538 } 536 }
539 537
540 bn_correct_top(b); 538 bn_fix_top(b);
541 return 1; 539 return 1;
542 } 540 }
543 541
@@ -554,7 +552,7 @@ static int MOD_EXP_CTIME_COPY_FROM_PREBUF(BIGNUM *b, int top, unsigned char *buf
554 } 552 }
555 553
556 b->top = top; 554 b->top = top;
557 bn_correct_top(b); 555 bn_fix_top(b);
558 return 1; 556 return 1;
559 } 557 }
560 558
@@ -745,9 +743,9 @@ int BN_mod_exp_mont_word(BIGNUM *rr, BN_ULONG a, const BIGNUM *p,
745#define BN_TO_MONTGOMERY_WORD(r, w, mont) \ 743#define BN_TO_MONTGOMERY_WORD(r, w, mont) \
746 (BN_set_word(r, (w)) && BN_to_montgomery(r, r, (mont), ctx)) 744 (BN_set_word(r, (w)) && BN_to_montgomery(r, r, (mont), ctx))
747 745
748 if (BN_get_flags(p, BN_FLG_CONSTTIME) != 0) 746 if (BN_get_flags(p, BN_FLG_EXP_CONSTTIME) != 0)
749 { 747 {
750 /* BN_FLG_CONSTTIME only supported by BN_mod_exp_mont() */ 748 /* BN_FLG_EXP_CONSTTIME only supported by BN_mod_exp_mont() */
751 BNerr(BN_F_BN_MOD_EXP_MONT_WORD,ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED); 749 BNerr(BN_F_BN_MOD_EXP_MONT_WORD,ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
752 return -1; 750 return -1;
753 } 751 }
@@ -755,7 +753,7 @@ int BN_mod_exp_mont_word(BIGNUM *rr, BN_ULONG a, const BIGNUM *p,
755 bn_check_top(p); 753 bn_check_top(p);
756 bn_check_top(m); 754 bn_check_top(m);
757 755
758 if (!BN_is_odd(m)) 756 if (m->top == 0 || !(m->d[0] & 1))
759 { 757 {
760 BNerr(BN_F_BN_MOD_EXP_MONT_WORD,BN_R_CALLED_WITH_EVEN_MODULUS); 758 BNerr(BN_F_BN_MOD_EXP_MONT_WORD,BN_R_CALLED_WITH_EVEN_MODULUS);
761 return(0); 759 return(0);
@@ -771,8 +769,7 @@ int BN_mod_exp_mont_word(BIGNUM *rr, BN_ULONG a, const BIGNUM *p,
771 } 769 }
772 if (a == 0) 770 if (a == 0)
773 { 771 {
774 BN_zero(rr); 772 ret = BN_zero(rr);
775 ret = 1;
776 return ret; 773 return ret;
777 } 774 }
778 775
@@ -866,24 +863,23 @@ int BN_mod_exp_mont_word(BIGNUM *rr, BN_ULONG a, const BIGNUM *p,
866err: 863err:
867 if ((in_mont == NULL) && (mont != NULL)) BN_MONT_CTX_free(mont); 864 if ((in_mont == NULL) && (mont != NULL)) BN_MONT_CTX_free(mont);
868 BN_CTX_end(ctx); 865 BN_CTX_end(ctx);
869 bn_check_top(rr);
870 return(ret); 866 return(ret);
871 } 867 }
872 868
873 869
874/* The old fallback, simple version :-) */ 870/* The old fallback, simple version :-) */
875int BN_mod_exp_simple(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, 871int BN_mod_exp_simple(BIGNUM *r,
876 const BIGNUM *m, BN_CTX *ctx) 872 const BIGNUM *a, const BIGNUM *p, const BIGNUM *m,
873 BN_CTX *ctx)
877 { 874 {
878 int i,j,bits,ret=0,wstart,wend,window,wvalue; 875 int i,j,bits,ret=0,wstart,wend,window,wvalue,ts=0;
879 int start=1; 876 int start=1;
880 BIGNUM *d; 877 BIGNUM *d;
881 /* Table of variables obtained from 'ctx' */ 878 BIGNUM val[TABLE_SIZE];
882 BIGNUM *val[TABLE_SIZE];
883 879
884 if (BN_get_flags(p, BN_FLG_CONSTTIME) != 0) 880 if (BN_get_flags(p, BN_FLG_EXP_CONSTTIME) != 0)
885 { 881 {
886 /* BN_FLG_CONSTTIME only supported by BN_mod_exp_mont() */ 882 /* BN_FLG_EXP_CONSTTIME only supported by BN_mod_exp_mont() */
887 BNerr(BN_F_BN_MOD_EXP_SIMPLE,ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED); 883 BNerr(BN_F_BN_MOD_EXP_SIMPLE,ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
888 return -1; 884 return -1;
889 } 885 }
@@ -897,30 +893,30 @@ int BN_mod_exp_simple(BIGNUM *r, const BIGNUM *a, const BIGNUM *p,
897 } 893 }
898 894
899 BN_CTX_start(ctx); 895 BN_CTX_start(ctx);
900 d = BN_CTX_get(ctx); 896 if ((d = BN_CTX_get(ctx)) == NULL) goto err;
901 val[0] = BN_CTX_get(ctx);
902 if(!d || !val[0]) goto err;
903 897
904 if (!BN_nnmod(val[0],a,m,ctx)) goto err; /* 1 */ 898 BN_init(&(val[0]));
905 if (BN_is_zero(val[0])) 899 ts=1;
900 if (!BN_nnmod(&(val[0]),a,m,ctx)) goto err; /* 1 */
901 if (BN_is_zero(&(val[0])))
906 { 902 {
907 BN_zero(r); 903 ret = BN_zero(r);
908 ret = 1;
909 goto err; 904 goto err;
910 } 905 }
911 906
912 window = BN_window_bits_for_exponent_size(bits); 907 window = BN_window_bits_for_exponent_size(bits);
913 if (window > 1) 908 if (window > 1)
914 { 909 {
915 if (!BN_mod_mul(d,val[0],val[0],m,ctx)) 910 if (!BN_mod_mul(d,&(val[0]),&(val[0]),m,ctx))
916 goto err; /* 2 */ 911 goto err; /* 2 */
917 j=1<<(window-1); 912 j=1<<(window-1);
918 for (i=1; i<j; i++) 913 for (i=1; i<j; i++)
919 { 914 {
920 if(((val[i] = BN_CTX_get(ctx)) == NULL) || 915 BN_init(&(val[i]));
921 !BN_mod_mul(val[i],val[i-1],d,m,ctx)) 916 if (!BN_mod_mul(&(val[i]),&(val[i-1]),d,m,ctx))
922 goto err; 917 goto err;
923 } 918 }
919 ts=i;
924 } 920 }
925 921
926 start=1; /* This is used to avoid multiplication etc 922 start=1; /* This is used to avoid multiplication etc
@@ -972,7 +968,7 @@ int BN_mod_exp_simple(BIGNUM *r, const BIGNUM *a, const BIGNUM *p,
972 } 968 }
973 969
974 /* wvalue will be an odd number < 2^window */ 970 /* wvalue will be an odd number < 2^window */
975 if (!BN_mod_mul(r,r,val[wvalue>>1],m,ctx)) 971 if (!BN_mod_mul(r,r,&(val[wvalue>>1]),m,ctx))
976 goto err; 972 goto err;
977 973
978 /* move the 'window' down further */ 974 /* move the 'window' down further */
@@ -984,7 +980,8 @@ int BN_mod_exp_simple(BIGNUM *r, const BIGNUM *a, const BIGNUM *p,
984 ret=1; 980 ret=1;
985err: 981err:
986 BN_CTX_end(ctx); 982 BN_CTX_end(ctx);
987 bn_check_top(r); 983 for (i=0; i<ts; i++)
984 BN_clear_free(&(val[i]));
988 return(ret); 985 return(ret);
989 } 986 }
990 987
generated by cgit v1.2.3-55-g6feb (git 2.39.1) at 2025-08-04 14:02:17 +0000