diff options
author | djm <> | 2006-06-27 05:05:42 +0000 |
---|---|---|
committer | djm <> | 2006-06-27 05:05:42 +0000 |
commit | f6198d4d0ab97685dc56be2d48715ed39fcc74b9 (patch) | |
tree | 6e28360095ed5ba5ef1760a419c43eef4ef6946b /src/lib/libcrypto/bn | |
parent | 0ff0f9d99c40072de315264b0f602bd639e7f662 (diff) | |
download | openbsd-f6198d4d0ab97685dc56be2d48715ed39fcc74b9.tar.gz openbsd-f6198d4d0ab97685dc56be2d48715ed39fcc74b9.tar.bz2 openbsd-f6198d4d0ab97685dc56be2d48715ed39fcc74b9.zip |
import of openssl-0.9.7j
Diffstat (limited to 'src/lib/libcrypto/bn')
-rw-r--r-- | src/lib/libcrypto/bn/asm/ppc.pl | 23 | ||||
-rw-r--r-- | src/lib/libcrypto/bn/asm/sparcv8plus.S | 16 | ||||
-rw-r--r-- | src/lib/libcrypto/bn/bn.h | 34 | ||||
-rw-r--r-- | src/lib/libcrypto/bn/bn_asm.c | 2 | ||||
-rw-r--r-- | src/lib/libcrypto/bn/bn_err.c | 92 | ||||
-rw-r--r-- | src/lib/libcrypto/bn/bn_exp.c | 244 | ||||
-rw-r--r-- | src/lib/libcrypto/bn/bn_lcl.h | 39 | ||||
-rw-r--r-- | src/lib/libcrypto/bn/bn_mont.c | 20 | ||||
-rw-r--r-- | src/lib/libcrypto/bn/bn_x931p.c | 282 |
9 files changed, 692 insertions, 60 deletions
diff --git a/src/lib/libcrypto/bn/asm/ppc.pl b/src/lib/libcrypto/bn/asm/ppc.pl index 307c7ccb35..08e0053473 100644 --- a/src/lib/libcrypto/bn/asm/ppc.pl +++ b/src/lib/libcrypto/bn/asm/ppc.pl | |||
@@ -116,7 +116,7 @@ if ($opf =~ /32\.s/) { | |||
116 | $UDIV= "divwu"; # unsigned divide | 116 | $UDIV= "divwu"; # unsigned divide |
117 | $UCMPI= "cmplwi"; # unsigned compare with immediate | 117 | $UCMPI= "cmplwi"; # unsigned compare with immediate |
118 | $UCMP= "cmplw"; # unsigned compare | 118 | $UCMP= "cmplw"; # unsigned compare |
119 | $COUNTZ="cntlzw"; # count leading zeros | 119 | $CNTLZ= "cntlzw"; # count leading zeros |
120 | $SHL= "slw"; # shift left | 120 | $SHL= "slw"; # shift left |
121 | $SHR= "srw"; # unsigned shift right | 121 | $SHR= "srw"; # unsigned shift right |
122 | $SHRI= "srwi"; # unsigned shift right by immediate | 122 | $SHRI= "srwi"; # unsigned shift right by immediate |
@@ -124,6 +124,7 @@ if ($opf =~ /32\.s/) { | |||
124 | $CLRU= "clrlwi"; # clear upper bits | 124 | $CLRU= "clrlwi"; # clear upper bits |
125 | $INSR= "insrwi"; # insert right | 125 | $INSR= "insrwi"; # insert right |
126 | $ROTL= "rotlwi"; # rotate left by immediate | 126 | $ROTL= "rotlwi"; # rotate left by immediate |
127 | $TR= "tw"; # conditional trap | ||
127 | } elsif ($opf =~ /64\.s/) { | 128 | } elsif ($opf =~ /64\.s/) { |
128 | $BITS= 64; | 129 | $BITS= 64; |
129 | $BNSZ= $BITS/8; | 130 | $BNSZ= $BITS/8; |
@@ -139,7 +140,7 @@ if ($opf =~ /32\.s/) { | |||
139 | $UDIV= "divdu"; # unsigned divide | 140 | $UDIV= "divdu"; # unsigned divide |
140 | $UCMPI= "cmpldi"; # unsigned compare with immediate | 141 | $UCMPI= "cmpldi"; # unsigned compare with immediate |
141 | $UCMP= "cmpld"; # unsigned compare | 142 | $UCMP= "cmpld"; # unsigned compare |
142 | $COUNTZ="cntlzd"; # count leading zeros | 143 | $CNTLZ= "cntlzd"; # count leading zeros |
143 | $SHL= "sld"; # shift left | 144 | $SHL= "sld"; # shift left |
144 | $SHR= "srd"; # unsigned shift right | 145 | $SHR= "srd"; # unsigned shift right |
145 | $SHRI= "srdi"; # unsigned shift right by immediate | 146 | $SHRI= "srdi"; # unsigned shift right by immediate |
@@ -147,6 +148,7 @@ if ($opf =~ /32\.s/) { | |||
147 | $CLRU= "clrldi"; # clear upper bits | 148 | $CLRU= "clrldi"; # clear upper bits |
148 | $INSR= "insrdi"; # insert right | 149 | $INSR= "insrdi"; # insert right |
149 | $ROTL= "rotldi"; # rotate left by immediate | 150 | $ROTL= "rotldi"; # rotate left by immediate |
151 | $TR= "td"; # conditional trap | ||
150 | } else { die "nonsense $opf"; } | 152 | } else { die "nonsense $opf"; } |
151 | 153 | ||
152 | ( defined shift || open STDOUT,">$opf" ) || die "can't open $opf: $!"; | 154 | ( defined shift || open STDOUT,">$opf" ) || die "can't open $opf: $!"; |
@@ -1710,17 +1712,12 @@ Lppcasm_add_adios: | |||
1710 | bclr BO_ALWAYS,CR0_LT | 1712 | bclr BO_ALWAYS,CR0_LT |
1711 | Lppcasm_div1: | 1713 | Lppcasm_div1: |
1712 | xor r0,r0,r0 #r0=0 | 1714 | xor r0,r0,r0 #r0=0 |
1713 | $COUNTZ r7,r5 #r7 = num leading 0s in d. | 1715 | li r8,$BITS |
1714 | subfic r8,r7,$BITS #r8 = BN_num_bits_word(d) | 1716 | $CNTLZ. r7,r5 #r7 = num leading 0s in d. |
1715 | cmpi 0,0,r8,$BITS # | 1717 | bc BO_IF,CR0_EQ,Lppcasm_div2 #proceed if no leading zeros |
1716 | bc BO_IF,CR0_EQ,Lppcasm_div2 #proceed if (r8==$BITS) | 1718 | subf r8,r7,r8 #r8 = BN_num_bits_word(d) |
1717 | li r9,1 # r9=1 | 1719 | $SHR. r9,r3,r8 #are there any bits above r8'th? |
1718 | $SHL r10,r9,r8 # r9<<=r8 | 1720 | $TR 16,r9,r0 #if there're, signal to dump core... |
1719 | $UCMP 0,r3,r10 # | ||
1720 | bc BO_IF,CR0_GT,Lppcasm_div2 #or if (h > (1<<r8)) | ||
1721 | $UDIV r3,r3,r0 #if not assert(0) divide by 0! | ||
1722 | #that's how we signal overflow | ||
1723 | bclr BO_ALWAYS,CR0_LT #return. NEVER REACHED. | ||
1724 | Lppcasm_div2: | 1721 | Lppcasm_div2: |
1725 | $UCMP 0,r3,r5 #h>=d? | 1722 | $UCMP 0,r3,r5 #h>=d? |
1726 | bc BO_IF,CR0_LT,Lppcasm_div3 #goto Lppcasm_div3 if not | 1723 | bc BO_IF,CR0_LT,Lppcasm_div3 #goto Lppcasm_div3 if not |
diff --git a/src/lib/libcrypto/bn/asm/sparcv8plus.S b/src/lib/libcrypto/bn/asm/sparcv8plus.S index 0074dfdb75..8c56e2e7e7 100644 --- a/src/lib/libcrypto/bn/asm/sparcv8plus.S +++ b/src/lib/libcrypto/bn/asm/sparcv8plus.S | |||
@@ -162,10 +162,14 @@ | |||
162 | * BN_ULONG w; | 162 | * BN_ULONG w; |
163 | */ | 163 | */ |
164 | bn_mul_add_words: | 164 | bn_mul_add_words: |
165 | sra %o2,%g0,%o2 ! signx %o2 | ||
165 | brgz,a %o2,.L_bn_mul_add_words_proceed | 166 | brgz,a %o2,.L_bn_mul_add_words_proceed |
166 | lduw [%o1],%g2 | 167 | lduw [%o1],%g2 |
167 | retl | 168 | retl |
168 | clr %o0 | 169 | clr %o0 |
170 | nop | ||
171 | nop | ||
172 | nop | ||
169 | 173 | ||
170 | .L_bn_mul_add_words_proceed: | 174 | .L_bn_mul_add_words_proceed: |
171 | srl %o3,%g0,%o3 ! clruw %o3 | 175 | srl %o3,%g0,%o3 ! clruw %o3 |
@@ -260,10 +264,14 @@ bn_mul_add_words: | |||
260 | * BN_ULONG w; | 264 | * BN_ULONG w; |
261 | */ | 265 | */ |
262 | bn_mul_words: | 266 | bn_mul_words: |
267 | sra %o2,%g0,%o2 ! signx %o2 | ||
263 | brgz,a %o2,.L_bn_mul_words_proceeed | 268 | brgz,a %o2,.L_bn_mul_words_proceeed |
264 | lduw [%o1],%g2 | 269 | lduw [%o1],%g2 |
265 | retl | 270 | retl |
266 | clr %o0 | 271 | clr %o0 |
272 | nop | ||
273 | nop | ||
274 | nop | ||
267 | 275 | ||
268 | .L_bn_mul_words_proceeed: | 276 | .L_bn_mul_words_proceeed: |
269 | srl %o3,%g0,%o3 ! clruw %o3 | 277 | srl %o3,%g0,%o3 ! clruw %o3 |
@@ -344,10 +352,14 @@ bn_mul_words: | |||
344 | * int n; | 352 | * int n; |
345 | */ | 353 | */ |
346 | bn_sqr_words: | 354 | bn_sqr_words: |
355 | sra %o2,%g0,%o2 ! signx %o2 | ||
347 | brgz,a %o2,.L_bn_sqr_words_proceeed | 356 | brgz,a %o2,.L_bn_sqr_words_proceeed |
348 | lduw [%o1],%g2 | 357 | lduw [%o1],%g2 |
349 | retl | 358 | retl |
350 | clr %o0 | 359 | clr %o0 |
360 | nop | ||
361 | nop | ||
362 | nop | ||
351 | 363 | ||
352 | .L_bn_sqr_words_proceeed: | 364 | .L_bn_sqr_words_proceeed: |
353 | andcc %o2,-4,%g0 | 365 | andcc %o2,-4,%g0 |
@@ -445,6 +457,7 @@ bn_div_words: | |||
445 | * int n; | 457 | * int n; |
446 | */ | 458 | */ |
447 | bn_add_words: | 459 | bn_add_words: |
460 | sra %o3,%g0,%o3 ! signx %o3 | ||
448 | brgz,a %o3,.L_bn_add_words_proceed | 461 | brgz,a %o3,.L_bn_add_words_proceed |
449 | lduw [%o1],%o4 | 462 | lduw [%o1],%o4 |
450 | retl | 463 | retl |
@@ -454,7 +467,6 @@ bn_add_words: | |||
454 | andcc %o3,-4,%g0 | 467 | andcc %o3,-4,%g0 |
455 | bz,pn %icc,.L_bn_add_words_tail | 468 | bz,pn %icc,.L_bn_add_words_tail |
456 | addcc %g0,0,%g0 ! clear carry flag | 469 | addcc %g0,0,%g0 ! clear carry flag |
457 | nop | ||
458 | 470 | ||
459 | .L_bn_add_words_loop: ! wow! 32 aligned! | 471 | .L_bn_add_words_loop: ! wow! 32 aligned! |
460 | dec 4,%o3 | 472 | dec 4,%o3 |
@@ -523,6 +535,7 @@ bn_add_words: | |||
523 | * int n; | 535 | * int n; |
524 | */ | 536 | */ |
525 | bn_sub_words: | 537 | bn_sub_words: |
538 | sra %o3,%g0,%o3 ! signx %o3 | ||
526 | brgz,a %o3,.L_bn_sub_words_proceed | 539 | brgz,a %o3,.L_bn_sub_words_proceed |
527 | lduw [%o1],%o4 | 540 | lduw [%o1],%o4 |
528 | retl | 541 | retl |
@@ -532,7 +545,6 @@ bn_sub_words: | |||
532 | andcc %o3,-4,%g0 | 545 | andcc %o3,-4,%g0 |
533 | bz,pn %icc,.L_bn_sub_words_tail | 546 | bz,pn %icc,.L_bn_sub_words_tail |
534 | addcc %g0,0,%g0 ! clear carry flag | 547 | addcc %g0,0,%g0 ! clear carry flag |
535 | nop | ||
536 | 548 | ||
537 | .L_bn_sub_words_loop: ! wow! 32 aligned! | 549 | .L_bn_sub_words_loop: ! wow! 32 aligned! |
538 | dec 4,%o3 | 550 | dec 4,%o3 |
diff --git a/src/lib/libcrypto/bn/bn.h b/src/lib/libcrypto/bn/bn.h index 3da6d8ced9..1251521c54 100644 --- a/src/lib/libcrypto/bn/bn.h +++ b/src/lib/libcrypto/bn/bn.h | |||
@@ -225,10 +225,23 @@ extern "C" { | |||
225 | 225 | ||
226 | #define BN_FLG_MALLOCED 0x01 | 226 | #define BN_FLG_MALLOCED 0x01 |
227 | #define BN_FLG_STATIC_DATA 0x02 | 227 | #define BN_FLG_STATIC_DATA 0x02 |
228 | #define BN_FLG_EXP_CONSTTIME 0x04 /* avoid leaking exponent information through timings | ||
229 | * (BN_mod_exp_mont() will call BN_mod_exp_mont_consttime) */ | ||
228 | #define BN_FLG_FREE 0x8000 /* used for debuging */ | 230 | #define BN_FLG_FREE 0x8000 /* used for debuging */ |
229 | #define BN_set_flags(b,n) ((b)->flags|=(n)) | 231 | #define BN_set_flags(b,n) ((b)->flags|=(n)) |
230 | #define BN_get_flags(b,n) ((b)->flags&(n)) | 232 | #define BN_get_flags(b,n) ((b)->flags&(n)) |
231 | 233 | ||
234 | /* get a clone of a BIGNUM with changed flags, for *temporary* use only | ||
235 | * (the two BIGNUMs cannot not be used in parallel!) */ | ||
236 | #define BN_with_flags(dest,b,n) ((dest)->d=(b)->d, \ | ||
237 | (dest)->top=(b)->top, \ | ||
238 | (dest)->dmax=(b)->dmax, \ | ||
239 | (dest)->neg=(b)->neg, \ | ||
240 | (dest)->flags=(((dest)->flags & BN_FLG_MALLOCED) \ | ||
241 | | ((b)->flags & ~BN_FLG_MALLOCED) \ | ||
242 | | BN_FLG_STATIC_DATA \ | ||
243 | | (n))) | ||
244 | |||
232 | typedef struct bignum_st | 245 | typedef struct bignum_st |
233 | { | 246 | { |
234 | BN_ULONG *d; /* Pointer to an array of 'BN_BITS2' bit chunks. */ | 247 | BN_ULONG *d; /* Pointer to an array of 'BN_BITS2' bit chunks. */ |
@@ -378,6 +391,8 @@ int BN_mod_exp(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, | |||
378 | const BIGNUM *m,BN_CTX *ctx); | 391 | const BIGNUM *m,BN_CTX *ctx); |
379 | int BN_mod_exp_mont(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, | 392 | int BN_mod_exp_mont(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, |
380 | const BIGNUM *m, BN_CTX *ctx, BN_MONT_CTX *m_ctx); | 393 | const BIGNUM *m, BN_CTX *ctx, BN_MONT_CTX *m_ctx); |
394 | int BN_mod_exp_mont_consttime(BIGNUM *rr, const BIGNUM *a, const BIGNUM *p, | ||
395 | const BIGNUM *m, BN_CTX *ctx, BN_MONT_CTX *in_mont); | ||
381 | int BN_mod_exp_mont_word(BIGNUM *r, BN_ULONG a, const BIGNUM *p, | 396 | int BN_mod_exp_mont_word(BIGNUM *r, BN_ULONG a, const BIGNUM *p, |
382 | const BIGNUM *m, BN_CTX *ctx, BN_MONT_CTX *m_ctx); | 397 | const BIGNUM *m, BN_CTX *ctx, BN_MONT_CTX *m_ctx); |
383 | int BN_mod_exp2_mont(BIGNUM *r, const BIGNUM *a1, const BIGNUM *p1, | 398 | int BN_mod_exp2_mont(BIGNUM *r, const BIGNUM *a1, const BIGNUM *p1, |
@@ -423,6 +438,19 @@ int BN_is_prime_fasttest(const BIGNUM *p,int nchecks, | |||
423 | void (*callback)(int,int,void *),BN_CTX *ctx,void *cb_arg, | 438 | void (*callback)(int,int,void *),BN_CTX *ctx,void *cb_arg, |
424 | int do_trial_division); | 439 | int do_trial_division); |
425 | 440 | ||
441 | #ifdef OPENSSL_FIPS | ||
442 | int BN_X931_derive_prime(BIGNUM *p, BIGNUM *p1, BIGNUM *p2, | ||
443 | void (*cb)(int, int, void *), void *cb_arg, | ||
444 | const BIGNUM *Xp, const BIGNUM *Xp1, const BIGNUM *Xp2, | ||
445 | const BIGNUM *e, BN_CTX *ctx); | ||
446 | int BN_X931_generate_Xpq(BIGNUM *Xp, BIGNUM *Xq, int nbits, BN_CTX *ctx); | ||
447 | int BN_X931_generate_prime(BIGNUM *p, BIGNUM *p1, BIGNUM *p2, | ||
448 | BIGNUM *Xp1, BIGNUM *Xp2, | ||
449 | const BIGNUM *Xp, | ||
450 | const BIGNUM *e, BN_CTX *ctx, | ||
451 | void (*cb)(int, int, void *), void *cb_arg); | ||
452 | #endif | ||
453 | |||
426 | BN_MONT_CTX *BN_MONT_CTX_new(void ); | 454 | BN_MONT_CTX *BN_MONT_CTX_new(void ); |
427 | void BN_MONT_CTX_init(BN_MONT_CTX *ctx); | 455 | void BN_MONT_CTX_init(BN_MONT_CTX *ctx); |
428 | int BN_mod_mul_montgomery(BIGNUM *r,const BIGNUM *a,const BIGNUM *b, | 456 | int BN_mod_mul_montgomery(BIGNUM *r,const BIGNUM *a,const BIGNUM *b, |
@@ -434,6 +462,8 @@ int BN_from_montgomery(BIGNUM *r,const BIGNUM *a, | |||
434 | void BN_MONT_CTX_free(BN_MONT_CTX *mont); | 462 | void BN_MONT_CTX_free(BN_MONT_CTX *mont); |
435 | int BN_MONT_CTX_set(BN_MONT_CTX *mont,const BIGNUM *mod,BN_CTX *ctx); | 463 | int BN_MONT_CTX_set(BN_MONT_CTX *mont,const BIGNUM *mod,BN_CTX *ctx); |
436 | BN_MONT_CTX *BN_MONT_CTX_copy(BN_MONT_CTX *to,BN_MONT_CTX *from); | 464 | BN_MONT_CTX *BN_MONT_CTX_copy(BN_MONT_CTX *to,BN_MONT_CTX *from); |
465 | BN_MONT_CTX *BN_MONT_CTX_set_locked(BN_MONT_CTX **pmont, int lock, | ||
466 | const BIGNUM *mod, BN_CTX *ctx); | ||
437 | 467 | ||
438 | BN_BLINDING *BN_BLINDING_new(BIGNUM *A,BIGNUM *Ai,BIGNUM *mod); | 468 | BN_BLINDING *BN_BLINDING_new(BIGNUM *A,BIGNUM *Ai,BIGNUM *mod); |
439 | void BN_BLINDING_free(BN_BLINDING *b); | 469 | void BN_BLINDING_free(BN_BLINDING *b); |
@@ -510,11 +540,15 @@ void ERR_load_BN_strings(void); | |||
510 | #define BN_F_BN_CTX_GET 116 | 540 | #define BN_F_BN_CTX_GET 116 |
511 | #define BN_F_BN_CTX_NEW 106 | 541 | #define BN_F_BN_CTX_NEW 106 |
512 | #define BN_F_BN_DIV 107 | 542 | #define BN_F_BN_DIV 107 |
543 | #define BN_F_BN_EXP 123 | ||
513 | #define BN_F_BN_EXPAND2 108 | 544 | #define BN_F_BN_EXPAND2 108 |
514 | #define BN_F_BN_EXPAND_INTERNAL 120 | 545 | #define BN_F_BN_EXPAND_INTERNAL 120 |
515 | #define BN_F_BN_MOD_EXP2_MONT 118 | 546 | #define BN_F_BN_MOD_EXP2_MONT 118 |
516 | #define BN_F_BN_MOD_EXP_MONT 109 | 547 | #define BN_F_BN_MOD_EXP_MONT 109 |
548 | #define BN_F_BN_MOD_EXP_MONT_CONSTTIME 124 | ||
517 | #define BN_F_BN_MOD_EXP_MONT_WORD 117 | 549 | #define BN_F_BN_MOD_EXP_MONT_WORD 117 |
550 | #define BN_F_BN_MOD_EXP_RECP 125 | ||
551 | #define BN_F_BN_MOD_EXP_SIMPLE 126 | ||
518 | #define BN_F_BN_MOD_INVERSE 110 | 552 | #define BN_F_BN_MOD_INVERSE 110 |
519 | #define BN_F_BN_MOD_LSHIFT_QUICK 119 | 553 | #define BN_F_BN_MOD_LSHIFT_QUICK 119 |
520 | #define BN_F_BN_MOD_MUL_RECIPROCAL 111 | 554 | #define BN_F_BN_MOD_MUL_RECIPROCAL 111 |
diff --git a/src/lib/libcrypto/bn/bn_asm.c b/src/lib/libcrypto/bn/bn_asm.c index be8aa3ffc5..19978085b2 100644 --- a/src/lib/libcrypto/bn/bn_asm.c +++ b/src/lib/libcrypto/bn/bn_asm.c | |||
@@ -237,7 +237,7 @@ BN_ULONG bn_div_words(BN_ULONG h, BN_ULONG l, BN_ULONG d) | |||
237 | if (d == 0) return(BN_MASK2); | 237 | if (d == 0) return(BN_MASK2); |
238 | 238 | ||
239 | i=BN_num_bits_word(d); | 239 | i=BN_num_bits_word(d); |
240 | assert((i == BN_BITS2) || (h > (BN_ULONG)1<<i)); | 240 | assert((i == BN_BITS2) || (h <= (BN_ULONG)1<<i)); |
241 | 241 | ||
242 | i=BN_BITS2-i; | 242 | i=BN_BITS2-i; |
243 | if (h >= d) h-=d; | 243 | if (h >= d) h-=d; |
diff --git a/src/lib/libcrypto/bn/bn_err.c b/src/lib/libcrypto/bn/bn_err.c index fb84ee96d8..5dfac00c88 100644 --- a/src/lib/libcrypto/bn/bn_err.c +++ b/src/lib/libcrypto/bn/bn_err.c | |||
@@ -1,6 +1,6 @@ | |||
1 | /* crypto/bn/bn_err.c */ | 1 | /* crypto/bn/bn_err.c */ |
2 | /* ==================================================================== | 2 | /* ==================================================================== |
3 | * Copyright (c) 1999 The OpenSSL Project. All rights reserved. | 3 | * Copyright (c) 1999-2005 The OpenSSL Project. All rights reserved. |
4 | * | 4 | * |
5 | * Redistribution and use in source and binary forms, with or without | 5 | * Redistribution and use in source and binary forms, with or without |
6 | * modification, are permitted provided that the following conditions | 6 | * modification, are permitted provided that the following conditions |
@@ -64,52 +64,60 @@ | |||
64 | 64 | ||
65 | /* BEGIN ERROR CODES */ | 65 | /* BEGIN ERROR CODES */ |
66 | #ifndef OPENSSL_NO_ERR | 66 | #ifndef OPENSSL_NO_ERR |
67 | |||
68 | #define ERR_FUNC(func) ERR_PACK(ERR_LIB_BN,func,0) | ||
69 | #define ERR_REASON(reason) ERR_PACK(ERR_LIB_BN,0,reason) | ||
70 | |||
67 | static ERR_STRING_DATA BN_str_functs[]= | 71 | static ERR_STRING_DATA BN_str_functs[]= |
68 | { | 72 | { |
69 | {ERR_PACK(0,BN_F_BN_BLINDING_CONVERT,0), "BN_BLINDING_convert"}, | 73 | {ERR_FUNC(BN_F_BN_BLINDING_CONVERT), "BN_BLINDING_convert"}, |
70 | {ERR_PACK(0,BN_F_BN_BLINDING_INVERT,0), "BN_BLINDING_invert"}, | 74 | {ERR_FUNC(BN_F_BN_BLINDING_INVERT), "BN_BLINDING_invert"}, |
71 | {ERR_PACK(0,BN_F_BN_BLINDING_NEW,0), "BN_BLINDING_new"}, | 75 | {ERR_FUNC(BN_F_BN_BLINDING_NEW), "BN_BLINDING_new"}, |
72 | {ERR_PACK(0,BN_F_BN_BLINDING_UPDATE,0), "BN_BLINDING_update"}, | 76 | {ERR_FUNC(BN_F_BN_BLINDING_UPDATE), "BN_BLINDING_update"}, |
73 | {ERR_PACK(0,BN_F_BN_BN2DEC,0), "BN_bn2dec"}, | 77 | {ERR_FUNC(BN_F_BN_BN2DEC), "BN_bn2dec"}, |
74 | {ERR_PACK(0,BN_F_BN_BN2HEX,0), "BN_bn2hex"}, | 78 | {ERR_FUNC(BN_F_BN_BN2HEX), "BN_bn2hex"}, |
75 | {ERR_PACK(0,BN_F_BN_CTX_GET,0), "BN_CTX_get"}, | 79 | {ERR_FUNC(BN_F_BN_CTX_GET), "BN_CTX_get"}, |
76 | {ERR_PACK(0,BN_F_BN_CTX_NEW,0), "BN_CTX_new"}, | 80 | {ERR_FUNC(BN_F_BN_CTX_NEW), "BN_CTX_new"}, |
77 | {ERR_PACK(0,BN_F_BN_DIV,0), "BN_div"}, | 81 | {ERR_FUNC(BN_F_BN_DIV), "BN_div"}, |
78 | {ERR_PACK(0,BN_F_BN_EXPAND2,0), "bn_expand2"}, | 82 | {ERR_FUNC(BN_F_BN_EXP), "BN_exp"}, |
79 | {ERR_PACK(0,BN_F_BN_EXPAND_INTERNAL,0), "BN_EXPAND_INTERNAL"}, | 83 | {ERR_FUNC(BN_F_BN_EXPAND2), "bn_expand2"}, |
80 | {ERR_PACK(0,BN_F_BN_MOD_EXP2_MONT,0), "BN_mod_exp2_mont"}, | 84 | {ERR_FUNC(BN_F_BN_EXPAND_INTERNAL), "BN_EXPAND_INTERNAL"}, |
81 | {ERR_PACK(0,BN_F_BN_MOD_EXP_MONT,0), "BN_mod_exp_mont"}, | 85 | {ERR_FUNC(BN_F_BN_MOD_EXP2_MONT), "BN_mod_exp2_mont"}, |
82 | {ERR_PACK(0,BN_F_BN_MOD_EXP_MONT_WORD,0), "BN_mod_exp_mont_word"}, | 86 | {ERR_FUNC(BN_F_BN_MOD_EXP_MONT), "BN_mod_exp_mont"}, |
83 | {ERR_PACK(0,BN_F_BN_MOD_INVERSE,0), "BN_mod_inverse"}, | 87 | {ERR_FUNC(BN_F_BN_MOD_EXP_MONT_CONSTTIME), "BN_mod_exp_mont_consttime"}, |
84 | {ERR_PACK(0,BN_F_BN_MOD_LSHIFT_QUICK,0), "BN_mod_lshift_quick"}, | 88 | {ERR_FUNC(BN_F_BN_MOD_EXP_MONT_WORD), "BN_mod_exp_mont_word"}, |
85 | {ERR_PACK(0,BN_F_BN_MOD_MUL_RECIPROCAL,0), "BN_mod_mul_reciprocal"}, | 89 | {ERR_FUNC(BN_F_BN_MOD_EXP_RECP), "BN_mod_exp_recp"}, |
86 | {ERR_PACK(0,BN_F_BN_MOD_SQRT,0), "BN_mod_sqrt"}, | 90 | {ERR_FUNC(BN_F_BN_MOD_EXP_SIMPLE), "BN_mod_exp_simple"}, |
87 | {ERR_PACK(0,BN_F_BN_MPI2BN,0), "BN_mpi2bn"}, | 91 | {ERR_FUNC(BN_F_BN_MOD_INVERSE), "BN_mod_inverse"}, |
88 | {ERR_PACK(0,BN_F_BN_NEW,0), "BN_new"}, | 92 | {ERR_FUNC(BN_F_BN_MOD_LSHIFT_QUICK), "BN_mod_lshift_quick"}, |
89 | {ERR_PACK(0,BN_F_BN_RAND,0), "BN_rand"}, | 93 | {ERR_FUNC(BN_F_BN_MOD_MUL_RECIPROCAL), "BN_mod_mul_reciprocal"}, |
90 | {ERR_PACK(0,BN_F_BN_RAND_RANGE,0), "BN_rand_range"}, | 94 | {ERR_FUNC(BN_F_BN_MOD_SQRT), "BN_mod_sqrt"}, |
91 | {ERR_PACK(0,BN_F_BN_USUB,0), "BN_usub"}, | 95 | {ERR_FUNC(BN_F_BN_MPI2BN), "BN_mpi2bn"}, |
96 | {ERR_FUNC(BN_F_BN_NEW), "BN_new"}, | ||
97 | {ERR_FUNC(BN_F_BN_RAND), "BN_rand"}, | ||
98 | {ERR_FUNC(BN_F_BN_RAND_RANGE), "BN_rand_range"}, | ||
99 | {ERR_FUNC(BN_F_BN_USUB), "BN_usub"}, | ||
92 | {0,NULL} | 100 | {0,NULL} |
93 | }; | 101 | }; |
94 | 102 | ||
95 | static ERR_STRING_DATA BN_str_reasons[]= | 103 | static ERR_STRING_DATA BN_str_reasons[]= |
96 | { | 104 | { |
97 | {BN_R_ARG2_LT_ARG3 ,"arg2 lt arg3"}, | 105 | {ERR_REASON(BN_R_ARG2_LT_ARG3) ,"arg2 lt arg3"}, |
98 | {BN_R_BAD_RECIPROCAL ,"bad reciprocal"}, | 106 | {ERR_REASON(BN_R_BAD_RECIPROCAL) ,"bad reciprocal"}, |
99 | {BN_R_BIGNUM_TOO_LONG ,"bignum too long"}, | 107 | {ERR_REASON(BN_R_BIGNUM_TOO_LONG) ,"bignum too long"}, |
100 | {BN_R_CALLED_WITH_EVEN_MODULUS ,"called with even modulus"}, | 108 | {ERR_REASON(BN_R_CALLED_WITH_EVEN_MODULUS),"called with even modulus"}, |
101 | {BN_R_DIV_BY_ZERO ,"div by zero"}, | 109 | {ERR_REASON(BN_R_DIV_BY_ZERO) ,"div by zero"}, |
102 | {BN_R_ENCODING_ERROR ,"encoding error"}, | 110 | {ERR_REASON(BN_R_ENCODING_ERROR) ,"encoding error"}, |
103 | {BN_R_EXPAND_ON_STATIC_BIGNUM_DATA ,"expand on static bignum data"}, | 111 | {ERR_REASON(BN_R_EXPAND_ON_STATIC_BIGNUM_DATA),"expand on static bignum data"}, |
104 | {BN_R_INPUT_NOT_REDUCED ,"input not reduced"}, | 112 | {ERR_REASON(BN_R_INPUT_NOT_REDUCED) ,"input not reduced"}, |
105 | {BN_R_INVALID_LENGTH ,"invalid length"}, | 113 | {ERR_REASON(BN_R_INVALID_LENGTH) ,"invalid length"}, |
106 | {BN_R_INVALID_RANGE ,"invalid range"}, | 114 | {ERR_REASON(BN_R_INVALID_RANGE) ,"invalid range"}, |
107 | {BN_R_NOT_A_SQUARE ,"not a square"}, | 115 | {ERR_REASON(BN_R_NOT_A_SQUARE) ,"not a square"}, |
108 | {BN_R_NOT_INITIALIZED ,"not initialized"}, | 116 | {ERR_REASON(BN_R_NOT_INITIALIZED) ,"not initialized"}, |
109 | {BN_R_NO_INVERSE ,"no inverse"}, | 117 | {ERR_REASON(BN_R_NO_INVERSE) ,"no inverse"}, |
110 | {BN_R_P_IS_NOT_PRIME ,"p is not prime"}, | 118 | {ERR_REASON(BN_R_P_IS_NOT_PRIME) ,"p is not prime"}, |
111 | {BN_R_TOO_MANY_ITERATIONS ,"too many iterations"}, | 119 | {ERR_REASON(BN_R_TOO_MANY_ITERATIONS) ,"too many iterations"}, |
112 | {BN_R_TOO_MANY_TEMPORARY_VARIABLES ,"too many temporary variables"}, | 120 | {ERR_REASON(BN_R_TOO_MANY_TEMPORARY_VARIABLES),"too many temporary variables"}, |
113 | {0,NULL} | 121 | {0,NULL} |
114 | }; | 122 | }; |
115 | 123 | ||
@@ -123,8 +131,8 @@ void ERR_load_BN_strings(void) | |||
123 | { | 131 | { |
124 | init=0; | 132 | init=0; |
125 | #ifndef OPENSSL_NO_ERR | 133 | #ifndef OPENSSL_NO_ERR |
126 | ERR_load_strings(ERR_LIB_BN,BN_str_functs); | 134 | ERR_load_strings(0,BN_str_functs); |
127 | ERR_load_strings(ERR_LIB_BN,BN_str_reasons); | 135 | ERR_load_strings(0,BN_str_reasons); |
128 | #endif | 136 | #endif |
129 | 137 | ||
130 | } | 138 | } |
diff --git a/src/lib/libcrypto/bn/bn_exp.c b/src/lib/libcrypto/bn/bn_exp.c index afdfd580fb..9e1e88abe8 100644 --- a/src/lib/libcrypto/bn/bn_exp.c +++ b/src/lib/libcrypto/bn/bn_exp.c | |||
@@ -56,7 +56,7 @@ | |||
56 | * [including the GNU Public Licence.] | 56 | * [including the GNU Public Licence.] |
57 | */ | 57 | */ |
58 | /* ==================================================================== | 58 | /* ==================================================================== |
59 | * Copyright (c) 1998-2000 The OpenSSL Project. All rights reserved. | 59 | * Copyright (c) 1998-2005 The OpenSSL Project. All rights reserved. |
60 | * | 60 | * |
61 | * Redistribution and use in source and binary forms, with or without | 61 | * Redistribution and use in source and binary forms, with or without |
62 | * modification, are permitted provided that the following conditions | 62 | * modification, are permitted provided that the following conditions |
@@ -113,6 +113,7 @@ | |||
113 | #include "cryptlib.h" | 113 | #include "cryptlib.h" |
114 | #include "bn_lcl.h" | 114 | #include "bn_lcl.h" |
115 | 115 | ||
116 | /* maximum precomputation table size for *variable* sliding windows */ | ||
116 | #define TABLE_SIZE 32 | 117 | #define TABLE_SIZE 32 |
117 | 118 | ||
118 | /* this one works - simple but works */ | 119 | /* this one works - simple but works */ |
@@ -121,6 +122,13 @@ int BN_exp(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx) | |||
121 | int i,bits,ret=0; | 122 | int i,bits,ret=0; |
122 | BIGNUM *v,*rr; | 123 | BIGNUM *v,*rr; |
123 | 124 | ||
125 | if (BN_get_flags(p, BN_FLG_EXP_CONSTTIME) != 0) | ||
126 | { | ||
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); | ||
129 | return -1; | ||
130 | } | ||
131 | |||
124 | BN_CTX_start(ctx); | 132 | BN_CTX_start(ctx); |
125 | if ((r == a) || (r == p)) | 133 | if ((r == a) || (r == p)) |
126 | rr = BN_CTX_get(ctx); | 134 | rr = BN_CTX_get(ctx); |
@@ -204,7 +212,7 @@ int BN_mod_exp(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, const BIGNUM *m, | |||
204 | if (BN_is_odd(m)) | 212 | if (BN_is_odd(m)) |
205 | { | 213 | { |
206 | # ifdef MONT_EXP_WORD | 214 | # ifdef MONT_EXP_WORD |
207 | if (a->top == 1 && !a->neg) | 215 | if (a->top == 1 && !a->neg && (BN_get_flags(p, BN_FLG_EXP_CONSTTIME) == 0)) |
208 | { | 216 | { |
209 | BN_ULONG A = a->d[0]; | 217 | BN_ULONG A = a->d[0]; |
210 | 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); |
@@ -234,6 +242,13 @@ int BN_mod_exp_recp(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, | |||
234 | BIGNUM val[TABLE_SIZE]; | 242 | BIGNUM val[TABLE_SIZE]; |
235 | BN_RECP_CTX recp; | 243 | BN_RECP_CTX recp; |
236 | 244 | ||
245 | if (BN_get_flags(p, BN_FLG_EXP_CONSTTIME) != 0) | ||
246 | { | ||
247 | /* BN_FLG_EXP_CONSTTIME only supported by BN_mod_exp_mont() */ | ||
248 | BNerr(BN_F_BN_MOD_EXP_RECP,ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED); | ||
249 | return -1; | ||
250 | } | ||
251 | |||
237 | bits=BN_num_bits(p); | 252 | bits=BN_num_bits(p); |
238 | 253 | ||
239 | if (bits == 0) | 254 | if (bits == 0) |
@@ -361,6 +376,11 @@ int BN_mod_exp_mont(BIGNUM *rr, const BIGNUM *a, const BIGNUM *p, | |||
361 | BIGNUM val[TABLE_SIZE]; | 376 | BIGNUM val[TABLE_SIZE]; |
362 | BN_MONT_CTX *mont=NULL; | 377 | BN_MONT_CTX *mont=NULL; |
363 | 378 | ||
379 | if (BN_get_flags(p, BN_FLG_EXP_CONSTTIME) != 0) | ||
380 | { | ||
381 | return BN_mod_exp_mont_consttime(rr, a, p, m, ctx, in_mont); | ||
382 | } | ||
383 | |||
364 | bn_check_top(a); | 384 | bn_check_top(a); |
365 | bn_check_top(p); | 385 | bn_check_top(p); |
366 | bn_check_top(m); | 386 | bn_check_top(m); |
@@ -493,6 +513,212 @@ err: | |||
493 | return(ret); | 513 | return(ret); |
494 | } | 514 | } |
495 | 515 | ||
516 | |||
517 | /* BN_mod_exp_mont_consttime() stores the precomputed powers in a specific layout | ||
518 | * so that accessing any of these table values shows the same access pattern as far | ||
519 | * as cache lines are concerned. The following functions are used to transfer a BIGNUM | ||
520 | * from/to that table. */ | ||
521 | |||
522 | static int MOD_EXP_CTIME_COPY_TO_PREBUF(BIGNUM *b, int top, unsigned char *buf, int idx, int width) | ||
523 | { | ||
524 | size_t i, j; | ||
525 | |||
526 | if (bn_wexpand(b, top) == NULL) | ||
527 | return 0; | ||
528 | while (b->top < top) | ||
529 | { | ||
530 | b->d[b->top++] = 0; | ||
531 | } | ||
532 | |||
533 | for (i = 0, j=idx; i < top * sizeof b->d[0]; i++, j+=width) | ||
534 | { | ||
535 | buf[j] = ((unsigned char*)b->d)[i]; | ||
536 | } | ||
537 | |||
538 | bn_fix_top(b); | ||
539 | return 1; | ||
540 | } | ||
541 | |||
542 | static int MOD_EXP_CTIME_COPY_FROM_PREBUF(BIGNUM *b, int top, unsigned char *buf, int idx, int width) | ||
543 | { | ||
544 | size_t i, j; | ||
545 | |||
546 | if (bn_wexpand(b, top) == NULL) | ||
547 | return 0; | ||
548 | |||
549 | for (i=0, j=idx; i < top * sizeof b->d[0]; i++, j+=width) | ||
550 | { | ||
551 | ((unsigned char*)b->d)[i] = buf[j]; | ||
552 | } | ||
553 | |||
554 | b->top = top; | ||
555 | bn_fix_top(b); | ||
556 | return 1; | ||
557 | } | ||
558 | |||
559 | /* Given a pointer value, compute the next address that is a cache line multiple. */ | ||
560 | #define MOD_EXP_CTIME_ALIGN(x_) \ | ||
561 | ((unsigned char*)(x_) + (MOD_EXP_CTIME_MIN_CACHE_LINE_WIDTH - (((BN_ULONG)(x_)) & (MOD_EXP_CTIME_MIN_CACHE_LINE_MASK)))) | ||
562 | |||
563 | /* This variant of BN_mod_exp_mont() uses fixed windows and the special | ||
564 | * precomputation memory layout to limit data-dependency to a minimum | ||
565 | * to protect secret exponents (cf. the hyper-threading timing attacks | ||
566 | * pointed out by Colin Percival, | ||
567 | * http://www.daemonology.net/hyperthreading-considered-harmful/) | ||
568 | */ | ||
569 | int BN_mod_exp_mont_consttime(BIGNUM *rr, const BIGNUM *a, const BIGNUM *p, | ||
570 | const BIGNUM *m, BN_CTX *ctx, BN_MONT_CTX *in_mont) | ||
571 | { | ||
572 | int i,bits,ret=0,idx,window,wvalue; | ||
573 | int top; | ||
574 | BIGNUM *r; | ||
575 | const BIGNUM *aa; | ||
576 | BN_MONT_CTX *mont=NULL; | ||
577 | |||
578 | int numPowers; | ||
579 | unsigned char *powerbufFree=NULL; | ||
580 | int powerbufLen = 0; | ||
581 | unsigned char *powerbuf=NULL; | ||
582 | BIGNUM *computeTemp=NULL, *am=NULL; | ||
583 | |||
584 | bn_check_top(a); | ||
585 | bn_check_top(p); | ||
586 | bn_check_top(m); | ||
587 | |||
588 | top = m->top; | ||
589 | |||
590 | if (!(m->d[0] & 1)) | ||
591 | { | ||
592 | BNerr(BN_F_BN_MOD_EXP_MONT_CONSTTIME,BN_R_CALLED_WITH_EVEN_MODULUS); | ||
593 | return(0); | ||
594 | } | ||
595 | bits=BN_num_bits(p); | ||
596 | if (bits == 0) | ||
597 | { | ||
598 | ret = BN_one(rr); | ||
599 | return ret; | ||
600 | } | ||
601 | |||
602 | /* Initialize BIGNUM context and allocate intermediate result */ | ||
603 | BN_CTX_start(ctx); | ||
604 | r = BN_CTX_get(ctx); | ||
605 | if (r == NULL) goto err; | ||
606 | |||
607 | /* Allocate a montgomery context if it was not supplied by the caller. | ||
608 | * If this is not done, things will break in the montgomery part. | ||
609 | */ | ||
610 | if (in_mont != NULL) | ||
611 | mont=in_mont; | ||
612 | else | ||
613 | { | ||
614 | if ((mont=BN_MONT_CTX_new()) == NULL) goto err; | ||
615 | if (!BN_MONT_CTX_set(mont,m,ctx)) goto err; | ||
616 | } | ||
617 | |||
618 | /* Get the window size to use with size of p. */ | ||
619 | window = BN_window_bits_for_ctime_exponent_size(bits); | ||
620 | |||
621 | /* Allocate a buffer large enough to hold all of the pre-computed | ||
622 | * powers of a. | ||
623 | */ | ||
624 | numPowers = 1 << window; | ||
625 | powerbufLen = sizeof(m->d[0])*top*numPowers; | ||
626 | if ((powerbufFree=(unsigned char*)OPENSSL_malloc(powerbufLen+MOD_EXP_CTIME_MIN_CACHE_LINE_WIDTH)) == NULL) | ||
627 | goto err; | ||
628 | |||
629 | powerbuf = MOD_EXP_CTIME_ALIGN(powerbufFree); | ||
630 | memset(powerbuf, 0, powerbufLen); | ||
631 | |||
632 | /* Initialize the intermediate result. Do this early to save double conversion, | ||
633 | * once each for a^0 and intermediate result. | ||
634 | */ | ||
635 | if (!BN_to_montgomery(r,BN_value_one(),mont,ctx)) goto err; | ||
636 | if (!MOD_EXP_CTIME_COPY_TO_PREBUF(r, top, powerbuf, 0, numPowers)) goto err; | ||
637 | |||
638 | /* Initialize computeTemp as a^1 with montgomery precalcs */ | ||
639 | computeTemp = BN_CTX_get(ctx); | ||
640 | am = BN_CTX_get(ctx); | ||
641 | if (computeTemp==NULL || am==NULL) goto err; | ||
642 | |||
643 | if (a->neg || BN_ucmp(a,m) >= 0) | ||
644 | { | ||
645 | if (!BN_mod(am,a,m,ctx)) | ||
646 | goto err; | ||
647 | aa= am; | ||
648 | } | ||
649 | else | ||
650 | aa=a; | ||
651 | if (!BN_to_montgomery(am,aa,mont,ctx)) goto err; | ||
652 | if (!BN_copy(computeTemp, am)) goto err; | ||
653 | if (!MOD_EXP_CTIME_COPY_TO_PREBUF(am, top, powerbuf, 1, numPowers)) goto err; | ||
654 | |||
655 | /* If the window size is greater than 1, then calculate | ||
656 | * val[i=2..2^winsize-1]. Powers are computed as a*a^(i-1) | ||
657 | * (even powers could instead be computed as (a^(i/2))^2 | ||
658 | * to use the slight performance advantage of sqr over mul). | ||
659 | */ | ||
660 | if (window > 1) | ||
661 | { | ||
662 | for (i=2; i<numPowers; i++) | ||
663 | { | ||
664 | /* Calculate a^i = a^(i-1) * a */ | ||
665 | if (!BN_mod_mul_montgomery(computeTemp,am,computeTemp,mont,ctx)) | ||
666 | goto err; | ||
667 | if (!MOD_EXP_CTIME_COPY_TO_PREBUF(computeTemp, top, powerbuf, i, numPowers)) goto err; | ||
668 | } | ||
669 | } | ||
670 | |||
671 | /* Adjust the number of bits up to a multiple of the window size. | ||
672 | * If the exponent length is not a multiple of the window size, then | ||
673 | * this pads the most significant bits with zeros to normalize the | ||
674 | * scanning loop to there's no special cases. | ||
675 | * | ||
676 | * * NOTE: Making the window size a power of two less than the native | ||
677 | * * word size ensures that the padded bits won't go past the last | ||
678 | * * word in the internal BIGNUM structure. Going past the end will | ||
679 | * * still produce the correct result, but causes a different branch | ||
680 | * * to be taken in the BN_is_bit_set function. | ||
681 | */ | ||
682 | bits = ((bits+window-1)/window)*window; | ||
683 | idx=bits-1; /* The top bit of the window */ | ||
684 | |||
685 | /* Scan the exponent one window at a time starting from the most | ||
686 | * significant bits. | ||
687 | */ | ||
688 | while (idx >= 0) | ||
689 | { | ||
690 | wvalue=0; /* The 'value' of the window */ | ||
691 | |||
692 | /* Scan the window, squaring the result as we go */ | ||
693 | for (i=0; i<window; i++,idx--) | ||
694 | { | ||
695 | if (!BN_mod_mul_montgomery(r,r,r,mont,ctx)) goto err; | ||
696 | wvalue = (wvalue<<1)+BN_is_bit_set(p,idx); | ||
697 | } | ||
698 | |||
699 | /* Fetch the appropriate pre-computed value from the pre-buf */ | ||
700 | if (!MOD_EXP_CTIME_COPY_FROM_PREBUF(computeTemp, top, powerbuf, wvalue, numPowers)) goto err; | ||
701 | |||
702 | /* Multiply the result into the intermediate result */ | ||
703 | if (!BN_mod_mul_montgomery(r,r,computeTemp,mont,ctx)) goto err; | ||
704 | } | ||
705 | |||
706 | /* Convert the final result from montgomery to standard format */ | ||
707 | if (!BN_from_montgomery(rr,r,mont,ctx)) goto err; | ||
708 | ret=1; | ||
709 | err: | ||
710 | if ((in_mont == NULL) && (mont != NULL)) BN_MONT_CTX_free(mont); | ||
711 | if (powerbuf!=NULL) | ||
712 | { | ||
713 | OPENSSL_cleanse(powerbuf,powerbufLen); | ||
714 | OPENSSL_free(powerbufFree); | ||
715 | } | ||
716 | if (am!=NULL) BN_clear(am); | ||
717 | if (computeTemp!=NULL) BN_clear(computeTemp); | ||
718 | BN_CTX_end(ctx); | ||
719 | return(ret); | ||
720 | } | ||
721 | |||
496 | int BN_mod_exp_mont_word(BIGNUM *rr, BN_ULONG a, const BIGNUM *p, | 722 | int BN_mod_exp_mont_word(BIGNUM *rr, BN_ULONG a, const BIGNUM *p, |
497 | const BIGNUM *m, BN_CTX *ctx, BN_MONT_CTX *in_mont) | 723 | const BIGNUM *m, BN_CTX *ctx, BN_MONT_CTX *in_mont) |
498 | { | 724 | { |
@@ -517,6 +743,13 @@ int BN_mod_exp_mont_word(BIGNUM *rr, BN_ULONG a, const BIGNUM *p, | |||
517 | #define BN_TO_MONTGOMERY_WORD(r, w, mont) \ | 743 | #define BN_TO_MONTGOMERY_WORD(r, w, mont) \ |
518 | (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)) |
519 | 745 | ||
746 | if (BN_get_flags(p, BN_FLG_EXP_CONSTTIME) != 0) | ||
747 | { | ||
748 | /* BN_FLG_EXP_CONSTTIME only supported by BN_mod_exp_mont() */ | ||
749 | BNerr(BN_F_BN_MOD_EXP_MONT_WORD,ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED); | ||
750 | return -1; | ||
751 | } | ||
752 | |||
520 | bn_check_top(p); | 753 | bn_check_top(p); |
521 | bn_check_top(m); | 754 | bn_check_top(m); |
522 | 755 | ||
@@ -644,6 +877,13 @@ int BN_mod_exp_simple(BIGNUM *r, | |||
644 | BIGNUM *d; | 877 | BIGNUM *d; |
645 | BIGNUM val[TABLE_SIZE]; | 878 | BIGNUM val[TABLE_SIZE]; |
646 | 879 | ||
880 | if (BN_get_flags(p, BN_FLG_EXP_CONSTTIME) != 0) | ||
881 | { | ||
882 | /* BN_FLG_EXP_CONSTTIME only supported by BN_mod_exp_mont() */ | ||
883 | BNerr(BN_F_BN_MOD_EXP_SIMPLE,ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED); | ||
884 | return -1; | ||
885 | } | ||
886 | |||
647 | bits=BN_num_bits(p); | 887 | bits=BN_num_bits(p); |
648 | 888 | ||
649 | if (bits == 0) | 889 | if (bits == 0) |
diff --git a/src/lib/libcrypto/bn/bn_lcl.h b/src/lib/libcrypto/bn/bn_lcl.h index 253e195e23..a84998f2bd 100644 --- a/src/lib/libcrypto/bn/bn_lcl.h +++ b/src/lib/libcrypto/bn/bn_lcl.h | |||
@@ -177,6 +177,45 @@ struct bignum_ctx | |||
177 | 177 | ||
178 | 178 | ||
179 | 179 | ||
180 | /* BN_mod_exp_mont_conttime is based on the assumption that the | ||
181 | * L1 data cache line width of the target processor is at least | ||
182 | * the following value. | ||
183 | */ | ||
184 | #define MOD_EXP_CTIME_MIN_CACHE_LINE_WIDTH ( 64 ) | ||
185 | #define MOD_EXP_CTIME_MIN_CACHE_LINE_MASK (MOD_EXP_CTIME_MIN_CACHE_LINE_WIDTH - 1) | ||
186 | |||
187 | /* Window sizes optimized for fixed window size modular exponentiation | ||
188 | * algorithm (BN_mod_exp_mont_consttime). | ||
189 | * | ||
190 | * To achieve the security goals of BN_mode_exp_mont_consttime, the | ||
191 | * maximum size of the window must not exceed | ||
192 | * log_2(MOD_EXP_CTIME_MIN_CACHE_LINE_WIDTH). | ||
193 | * | ||
194 | * Window size thresholds are defined for cache line sizes of 32 and 64, | ||
195 | * cache line sizes where log_2(32)=5 and log_2(64)=6 respectively. A | ||
196 | * window size of 7 should only be used on processors that have a 128 | ||
197 | * byte or greater cache line size. | ||
198 | */ | ||
199 | #if MOD_EXP_CTIME_MIN_CACHE_LINE_WIDTH == 64 | ||
200 | |||
201 | # define BN_window_bits_for_ctime_exponent_size(b) \ | ||
202 | ((b) > 937 ? 6 : \ | ||
203 | (b) > 306 ? 5 : \ | ||
204 | (b) > 89 ? 4 : \ | ||
205 | (b) > 22 ? 3 : 1) | ||
206 | # define BN_MAX_WINDOW_BITS_FOR_CTIME_EXPONENT_SIZE (6) | ||
207 | |||
208 | #elif MOD_EXP_CTIME_MIN_CACHE_LINE_WIDTH == 32 | ||
209 | |||
210 | # define BN_window_bits_for_ctime_exponent_size(b) \ | ||
211 | ((b) > 306 ? 5 : \ | ||
212 | (b) > 89 ? 4 : \ | ||
213 | (b) > 22 ? 3 : 1) | ||
214 | # define BN_MAX_WINDOW_BITS_FOR_CTIME_EXPONENT_SIZE (5) | ||
215 | |||
216 | #endif | ||
217 | |||
218 | |||
180 | /* Pentium pro 16,16,16,32,64 */ | 219 | /* Pentium pro 16,16,16,32,64 */ |
181 | /* Alpha 16,16,16,16.64 */ | 220 | /* Alpha 16,16,16,16.64 */ |
182 | #define BN_MULL_SIZE_NORMAL (16) /* 32 */ | 221 | #define BN_MULL_SIZE_NORMAL (16) /* 32 */ |
diff --git a/src/lib/libcrypto/bn/bn_mont.c b/src/lib/libcrypto/bn/bn_mont.c index b79b1b60da..3572e5a690 100644 --- a/src/lib/libcrypto/bn/bn_mont.c +++ b/src/lib/libcrypto/bn/bn_mont.c | |||
@@ -347,3 +347,23 @@ BN_MONT_CTX *BN_MONT_CTX_copy(BN_MONT_CTX *to, BN_MONT_CTX *from) | |||
347 | return(to); | 347 | return(to); |
348 | } | 348 | } |
349 | 349 | ||
350 | BN_MONT_CTX *BN_MONT_CTX_set_locked(BN_MONT_CTX **pmont, int lock, | ||
351 | const BIGNUM *mod, BN_CTX *ctx) | ||
352 | { | ||
353 | if (*pmont) | ||
354 | return *pmont; | ||
355 | CRYPTO_w_lock(lock); | ||
356 | if (!*pmont) | ||
357 | { | ||
358 | *pmont = BN_MONT_CTX_new(); | ||
359 | if (*pmont && !BN_MONT_CTX_set(*pmont, mod, ctx)) | ||
360 | { | ||
361 | BN_MONT_CTX_free(*pmont); | ||
362 | *pmont = NULL; | ||
363 | } | ||
364 | } | ||
365 | CRYPTO_w_unlock(lock); | ||
366 | return *pmont; | ||
367 | } | ||
368 | |||
369 | |||
diff --git a/src/lib/libcrypto/bn/bn_x931p.c b/src/lib/libcrypto/bn/bn_x931p.c new file mode 100644 index 0000000000..c64410dd3a --- /dev/null +++ b/src/lib/libcrypto/bn/bn_x931p.c | |||
@@ -0,0 +1,282 @@ | |||
1 | /* bn_x931p.c */ | ||
2 | /* Written by Dr Stephen N Henson (shenson@bigfoot.com) for the OpenSSL | ||
3 | * project 2005. | ||
4 | */ | ||
5 | /* ==================================================================== | ||
6 | * Copyright (c) 2005 The OpenSSL Project. All rights reserved. | ||
7 | * | ||
8 | * Redistribution and use in source and binary forms, with or without | ||
9 | * modification, are permitted provided that the following conditions | ||
10 | * are met: | ||
11 | * | ||
12 | * 1. Redistributions of source code must retain the above copyright | ||
13 | * notice, this list of conditions and the following disclaimer. | ||
14 | * | ||
15 | * 2. Redistributions in binary form must reproduce the above copyright | ||
16 | * notice, this list of conditions and the following disclaimer in | ||
17 | * the documentation and/or other materials provided with the | ||
18 | * distribution. | ||
19 | * | ||
20 | * 3. All advertising materials mentioning features or use of this | ||
21 | * software must display the following acknowledgment: | ||
22 | * "This product includes software developed by the OpenSSL Project | ||
23 | * for use in the OpenSSL Toolkit. (http://www.OpenSSL.org/)" | ||
24 | * | ||
25 | * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to | ||
26 | * endorse or promote products derived from this software without | ||
27 | * prior written permission. For written permission, please contact | ||
28 | * licensing@OpenSSL.org. | ||
29 | * | ||
30 | * 5. Products derived from this software may not be called "OpenSSL" | ||
31 | * nor may "OpenSSL" appear in their names without prior written | ||
32 | * permission of the OpenSSL Project. | ||
33 | * | ||
34 | * 6. Redistributions of any form whatsoever must retain the following | ||
35 | * acknowledgment: | ||
36 | * "This product includes software developed by the OpenSSL Project | ||
37 | * for use in the OpenSSL Toolkit (http://www.OpenSSL.org/)" | ||
38 | * | ||
39 | * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY | ||
40 | * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE | ||
41 | * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR | ||
42 | * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR | ||
43 | * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, | ||
44 | * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT | ||
45 | * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; | ||
46 | * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) | ||
47 | * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, | ||
48 | * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) | ||
49 | * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED | ||
50 | * OF THE POSSIBILITY OF SUCH DAMAGE. | ||
51 | * ==================================================================== | ||
52 | * | ||
53 | * This product includes cryptographic software written by Eric Young | ||
54 | * (eay@cryptsoft.com). This product includes software written by Tim | ||
55 | * Hudson (tjh@cryptsoft.com). | ||
56 | * | ||
57 | */ | ||
58 | |||
59 | #include <stdio.h> | ||
60 | #include <openssl/bn.h> | ||
61 | |||
62 | #ifdef OPENSSL_FIPS | ||
63 | |||
64 | /* X9.31 routines for prime derivation */ | ||
65 | |||
66 | |||
67 | /* X9.31 prime derivation. This is used to generate the primes pi | ||
68 | * (p1, p2, q1, q2) from a parameter Xpi by checking successive odd | ||
69 | * integers. | ||
70 | */ | ||
71 | |||
72 | static int bn_x931_derive_pi(BIGNUM *pi, const BIGNUM *Xpi, BN_CTX *ctx, | ||
73 | void (*cb)(int, int, void *), void *cb_arg) | ||
74 | { | ||
75 | int i = 0; | ||
76 | if (!BN_copy(pi, Xpi)) | ||
77 | return 0; | ||
78 | if (!BN_is_odd(pi) && !BN_add_word(pi, 1)) | ||
79 | return 0; | ||
80 | for(;;) | ||
81 | { | ||
82 | i++; | ||
83 | if (cb) | ||
84 | cb(0, i, cb_arg); | ||
85 | /* NB 27 MR is specificed in X9.31 */ | ||
86 | if (BN_is_prime_fasttest(pi, 27, cb, ctx, cb_arg, 1)) | ||
87 | break; | ||
88 | if (!BN_add_word(pi, 2)) | ||
89 | return 0; | ||
90 | } | ||
91 | if (cb) | ||
92 | cb(2, i, cb_arg); | ||
93 | return 1; | ||
94 | } | ||
95 | |||
96 | /* This is the main X9.31 prime derivation function. From parameters | ||
97 | * Xp1, Xp2 and Xp derive the prime p. If the parameters p1 or p2 are | ||
98 | * not NULL they will be returned too: this is needed for testing. | ||
99 | */ | ||
100 | |||
101 | int BN_X931_derive_prime(BIGNUM *p, BIGNUM *p1, BIGNUM *p2, | ||
102 | void (*cb)(int, int, void *), void *cb_arg, | ||
103 | const BIGNUM *Xp, const BIGNUM *Xp1, const BIGNUM *Xp2, | ||
104 | const BIGNUM *e, BN_CTX *ctx) | ||
105 | { | ||
106 | int ret = 0; | ||
107 | |||
108 | BIGNUM *t, *p1p2, *pm1; | ||
109 | |||
110 | /* Only even e supported */ | ||
111 | if (!BN_is_odd(e)) | ||
112 | return 0; | ||
113 | |||
114 | BN_CTX_start(ctx); | ||
115 | if (!p1) | ||
116 | p1 = BN_CTX_get(ctx); | ||
117 | |||
118 | if (!p2) | ||
119 | p2 = BN_CTX_get(ctx); | ||
120 | |||
121 | t = BN_CTX_get(ctx); | ||
122 | |||
123 | p1p2 = BN_CTX_get(ctx); | ||
124 | |||
125 | pm1 = BN_CTX_get(ctx); | ||
126 | |||
127 | if (!bn_x931_derive_pi(p1, Xp1, ctx, cb, cb_arg)) | ||
128 | goto err; | ||
129 | |||
130 | if (!bn_x931_derive_pi(p2, Xp2, ctx, cb, cb_arg)) | ||
131 | goto err; | ||
132 | |||
133 | if (!BN_mul(p1p2, p1, p2, ctx)) | ||
134 | goto err; | ||
135 | |||
136 | /* First set p to value of Rp */ | ||
137 | |||
138 | if (!BN_mod_inverse(p, p2, p1, ctx)) | ||
139 | goto err; | ||
140 | |||
141 | if (!BN_mul(p, p, p2, ctx)) | ||
142 | goto err; | ||
143 | |||
144 | if (!BN_mod_inverse(t, p1, p2, ctx)) | ||
145 | goto err; | ||
146 | |||
147 | if (!BN_mul(t, t, p1, ctx)) | ||
148 | goto err; | ||
149 | |||
150 | if (!BN_sub(p, p, t)) | ||
151 | goto err; | ||
152 | |||
153 | if (p->neg && !BN_add(p, p, p1p2)) | ||
154 | goto err; | ||
155 | |||
156 | /* p now equals Rp */ | ||
157 | |||
158 | if (!BN_mod_sub(p, p, Xp, p1p2, ctx)) | ||
159 | goto err; | ||
160 | |||
161 | if (!BN_add(p, p, Xp)) | ||
162 | goto err; | ||
163 | |||
164 | /* p now equals Yp0 */ | ||
165 | |||
166 | for (;;) | ||
167 | { | ||
168 | int i = 1; | ||
169 | if (cb) | ||
170 | cb(0, i++, cb_arg); | ||
171 | if (!BN_copy(pm1, p)) | ||
172 | goto err; | ||
173 | if (!BN_sub_word(pm1, 1)) | ||
174 | goto err; | ||
175 | if (!BN_gcd(t, pm1, e, ctx)) | ||
176 | goto err; | ||
177 | if (BN_is_one(t) | ||
178 | /* X9.31 specifies 8 MR and 1 Lucas test or any prime test | ||
179 | * offering similar or better guarantees 50 MR is considerably | ||
180 | * better. | ||
181 | */ | ||
182 | && BN_is_prime_fasttest(p, 50, cb, ctx, cb_arg, 1)) | ||
183 | break; | ||
184 | if (!BN_add(p, p, p1p2)) | ||
185 | goto err; | ||
186 | } | ||
187 | |||
188 | if (cb) | ||
189 | cb(3, 0, cb_arg); | ||
190 | |||
191 | ret = 1; | ||
192 | |||
193 | err: | ||
194 | |||
195 | BN_CTX_end(ctx); | ||
196 | |||
197 | return ret; | ||
198 | } | ||
199 | |||
200 | /* Generate pair of paramters Xp, Xq for X9.31 prime generation. | ||
201 | * Note: nbits paramter is sum of number of bits in both. | ||
202 | */ | ||
203 | |||
204 | int BN_X931_generate_Xpq(BIGNUM *Xp, BIGNUM *Xq, int nbits, BN_CTX *ctx) | ||
205 | { | ||
206 | BIGNUM *t; | ||
207 | int i; | ||
208 | /* Number of bits for each prime is of the form | ||
209 | * 512+128s for s = 0, 1, ... | ||
210 | */ | ||
211 | if ((nbits < 1024) || (nbits & 0xff)) | ||
212 | return 0; | ||
213 | nbits >>= 1; | ||
214 | /* The random value Xp must be between sqrt(2) * 2^(nbits-1) and | ||
215 | * 2^nbits - 1. By setting the top two bits we ensure that the lower | ||
216 | * bound is exceeded. | ||
217 | */ | ||
218 | if (!BN_rand(Xp, nbits, 1, 0)) | ||
219 | return 0; | ||
220 | |||
221 | BN_CTX_start(ctx); | ||
222 | t = BN_CTX_get(ctx); | ||
223 | |||
224 | for (i = 0; i < 1000; i++) | ||
225 | { | ||
226 | if (!BN_rand(Xq, nbits, 1, 0)) | ||
227 | return 0; | ||
228 | /* Check that |Xp - Xq| > 2^(nbits - 100) */ | ||
229 | BN_sub(t, Xp, Xq); | ||
230 | if (BN_num_bits(t) > (nbits - 100)) | ||
231 | break; | ||
232 | } | ||
233 | |||
234 | BN_CTX_end(ctx); | ||
235 | |||
236 | if (i < 1000) | ||
237 | return 1; | ||
238 | |||
239 | return 0; | ||
240 | |||
241 | } | ||
242 | |||
243 | /* Generate primes using X9.31 algorithm. Of the values p, p1, p2, Xp1 | ||
244 | * and Xp2 only 'p' needs to be non-NULL. If any of the others are not NULL | ||
245 | * the relevant parameter will be stored in it. | ||
246 | * | ||
247 | * Due to the fact that |Xp - Xq| > 2^(nbits - 100) must be satisfied Xp and Xq | ||
248 | * are generated using the previous function and supplied as input. | ||
249 | */ | ||
250 | |||
251 | int BN_X931_generate_prime(BIGNUM *p, BIGNUM *p1, BIGNUM *p2, | ||
252 | BIGNUM *Xp1, BIGNUM *Xp2, | ||
253 | const BIGNUM *Xp, | ||
254 | const BIGNUM *e, BN_CTX *ctx, | ||
255 | void (*cb)(int, int, void *), void *cb_arg) | ||
256 | { | ||
257 | int ret = 0; | ||
258 | |||
259 | BN_CTX_start(ctx); | ||
260 | if (!Xp1) | ||
261 | Xp1 = BN_CTX_get(ctx); | ||
262 | if (!Xp2) | ||
263 | Xp2 = BN_CTX_get(ctx); | ||
264 | |||
265 | if (!BN_rand(Xp1, 101, 0, 0)) | ||
266 | goto error; | ||
267 | if (!BN_rand(Xp2, 101, 0, 0)) | ||
268 | goto error; | ||
269 | if (!BN_X931_derive_prime(p, p1, p2, cb, cb_arg, | ||
270 | Xp, Xp1, Xp2, e, ctx)) | ||
271 | goto error; | ||
272 | |||
273 | ret = 1; | ||
274 | |||
275 | error: | ||
276 | BN_CTX_end(ctx); | ||
277 | |||
278 | return ret; | ||
279 | |||
280 | } | ||
281 | |||
282 | #endif | ||