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