summaryrefslogtreecommitdiff
path: root/src/lib/libcrypto/bn
diff options
context:
space:
mode:
authordjm <>2006-06-27 05:05:42 +0000
committerdjm <>2006-06-27 05:05:42 +0000
commitf6198d4d0ab97685dc56be2d48715ed39fcc74b9 (patch)
tree6e28360095ed5ba5ef1760a419c43eef4ef6946b /src/lib/libcrypto/bn
parent0ff0f9d99c40072de315264b0f602bd639e7f662 (diff)
downloadopenbsd-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.pl23
-rw-r--r--src/lib/libcrypto/bn/asm/sparcv8plus.S16
-rw-r--r--src/lib/libcrypto/bn/bn.h34
-rw-r--r--src/lib/libcrypto/bn/bn_asm.c2
-rw-r--r--src/lib/libcrypto/bn/bn_err.c92
-rw-r--r--src/lib/libcrypto/bn/bn_exp.c244
-rw-r--r--src/lib/libcrypto/bn/bn_lcl.h39
-rw-r--r--src/lib/libcrypto/bn/bn_mont.c20
-rw-r--r--src/lib/libcrypto/bn/bn_x931p.c282
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
1711Lppcasm_div1: 1713Lppcasm_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.
1724Lppcasm_div2: 1721Lppcasm_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 */
164bn_mul_add_words: 164bn_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 */
262bn_mul_words: 266bn_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 */
346bn_sqr_words: 354bn_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 */
447bn_add_words: 459bn_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 */
525bn_sub_words: 537bn_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
232typedef struct bignum_st 245typedef 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);
379int BN_mod_exp_mont(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, 392int 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);
394int 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);
381int BN_mod_exp_mont_word(BIGNUM *r, BN_ULONG a, const BIGNUM *p, 396int 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);
383int BN_mod_exp2_mont(BIGNUM *r, const BIGNUM *a1, const BIGNUM *p1, 398int 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
442int 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);
446int BN_X931_generate_Xpq(BIGNUM *Xp, BIGNUM *Xq, int nbits, BN_CTX *ctx);
447int 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
426BN_MONT_CTX *BN_MONT_CTX_new(void ); 454BN_MONT_CTX *BN_MONT_CTX_new(void );
427void BN_MONT_CTX_init(BN_MONT_CTX *ctx); 455void BN_MONT_CTX_init(BN_MONT_CTX *ctx);
428int BN_mod_mul_montgomery(BIGNUM *r,const BIGNUM *a,const BIGNUM *b, 456int 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,
434void BN_MONT_CTX_free(BN_MONT_CTX *mont); 462void BN_MONT_CTX_free(BN_MONT_CTX *mont);
435int BN_MONT_CTX_set(BN_MONT_CTX *mont,const BIGNUM *mod,BN_CTX *ctx); 463int BN_MONT_CTX_set(BN_MONT_CTX *mont,const BIGNUM *mod,BN_CTX *ctx);
436BN_MONT_CTX *BN_MONT_CTX_copy(BN_MONT_CTX *to,BN_MONT_CTX *from); 464BN_MONT_CTX *BN_MONT_CTX_copy(BN_MONT_CTX *to,BN_MONT_CTX *from);
465BN_MONT_CTX *BN_MONT_CTX_set_locked(BN_MONT_CTX **pmont, int lock,
466 const BIGNUM *mod, BN_CTX *ctx);
437 467
438BN_BLINDING *BN_BLINDING_new(BIGNUM *A,BIGNUM *Ai,BIGNUM *mod); 468BN_BLINDING *BN_BLINDING_new(BIGNUM *A,BIGNUM *Ai,BIGNUM *mod);
439void BN_BLINDING_free(BN_BLINDING *b); 469void 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
67static ERR_STRING_DATA BN_str_functs[]= 71static 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
95static ERR_STRING_DATA BN_str_reasons[]= 103static 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
522static 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
542static 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 */
569int 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;
709err:
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
496int BN_mod_exp_mont_word(BIGNUM *rr, BN_ULONG a, const BIGNUM *p, 722int 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
350BN_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
72static 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
101int 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
204int 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
251int 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