From 6b62d1fdd8a4fd35acfcc0c4bb1bf8b757fa8cda Mon Sep 17 00:00:00 2001 From: djm <> Date: Sat, 6 Sep 2008 12:17:54 +0000 Subject: resolve conflicts --- src/lib/libcrypto/bn/asm/bn-586.pl | 86 +++- src/lib/libcrypto/bn/asm/ia64.S | 35 +- src/lib/libcrypto/bn/bn.h | 399 +++++++++++++++---- src/lib/libcrypto/bn/bn_add.c | 96 ++--- src/lib/libcrypto/bn/bn_asm.c | 28 ++ src/lib/libcrypto/bn/bn_blind.c | 249 +++++++++++- src/lib/libcrypto/bn/bn_ctx.c | 417 +++++++++++++++++--- src/lib/libcrypto/bn/bn_div.c | 299 ++++++++++++-- src/lib/libcrypto/bn/bn_err.c | 29 +- src/lib/libcrypto/bn/bn_exp.c | 133 +++---- src/lib/libcrypto/bn/bn_exp2.c | 56 ++- src/lib/libcrypto/bn/bn_gcd.c | 164 ++++++++ src/lib/libcrypto/bn/bn_kron.c | 8 +- src/lib/libcrypto/bn/bn_lcl.h | 114 +++--- src/lib/libcrypto/bn/bn_lib.c | 225 ++++++----- src/lib/libcrypto/bn/bn_mod.c | 7 +- src/lib/libcrypto/bn/bn_mont.c | 377 ++++++++++++++++-- src/lib/libcrypto/bn/bn_mpi.c | 1 + src/lib/libcrypto/bn/bn_mul.c | 539 ++++++++++++++++++++++---- src/lib/libcrypto/bn/bn_prime.c | 114 +++--- src/lib/libcrypto/bn/bn_prime.h | 4 +- src/lib/libcrypto/bn/bn_prime.pl | 6 +- src/lib/libcrypto/bn/bn_print.c | 41 +- src/lib/libcrypto/bn/bn_rand.c | 24 +- src/lib/libcrypto/bn/bn_recp.c | 22 +- src/lib/libcrypto/bn/bn_shift.c | 27 +- src/lib/libcrypto/bn/bn_sqr.c | 18 +- src/lib/libcrypto/bn/bn_sqrt.c | 76 ++-- src/lib/libcrypto/bn/bn_word.c | 67 +++- src/lib/libcrypto/bn/bntest.c | 775 +++++++++++++++++++++++++++++++++++-- src/lib/libcrypto/bn/exptest.c | 3 + 31 files changed, 3649 insertions(+), 790 deletions(-) (limited to 'src/lib/libcrypto/bn') diff --git a/src/lib/libcrypto/bn/asm/bn-586.pl b/src/lib/libcrypto/bn/asm/bn-586.pl index c4de4a2bee..26c2685a72 100644 --- a/src/lib/libcrypto/bn/asm/bn-586.pl +++ b/src/lib/libcrypto/bn/asm/bn-586.pl @@ -5,13 +5,18 @@ require "x86asm.pl"; &asm_init($ARGV[0],$0); +$sse2=0; +for (@ARGV) { $sse2=1 if (/-DOPENSSL_IA32_SSE2/); } + +&external_label("OPENSSL_ia32cap_P") if ($sse2); + &bn_mul_add_words("bn_mul_add_words"); &bn_mul_words("bn_mul_words"); &bn_sqr_words("bn_sqr_words"); &bn_div_words("bn_div_words"); &bn_add_words("bn_add_words"); &bn_sub_words("bn_sub_words"); -#&bn_sub_part_words("bn_sub_part_words"); +&bn_sub_part_words("bn_sub_part_words"); &asm_finish(); @@ -19,7 +24,7 @@ sub bn_mul_add_words { local($name)=@_; - &function_begin($name,""); + &function_begin($name,$sse2?"EXTRN\t_OPENSSL_ia32cap_P:DWORD":""); &comment(""); $Low="eax"; @@ -42,6 +47,83 @@ sub bn_mul_add_words &jz(&label("maw_finish")); + if ($sse2) { + &picmeup("eax","OPENSSL_ia32cap_P"); + &bt(&DWP(0,"eax"),26); + &jnc(&label("maw_loop")); + + &movd("mm0",$w); # mm0 = w + &pxor("mm1","mm1"); # mm1 = carry_in + + &set_label("maw_sse2_loop",0); + &movd("mm3",&DWP(0,$r,"",0)); # mm3 = r[0] + &paddq("mm1","mm3"); # mm1 = carry_in + r[0] + &movd("mm2",&DWP(0,$a,"",0)); # mm2 = a[0] + &pmuludq("mm2","mm0"); # mm2 = w*a[0] + &movd("mm4",&DWP(4,$a,"",0)); # mm4 = a[1] + &pmuludq("mm4","mm0"); # mm4 = w*a[1] + &movd("mm6",&DWP(8,$a,"",0)); # mm6 = a[2] + &pmuludq("mm6","mm0"); # mm6 = w*a[2] + &movd("mm7",&DWP(12,$a,"",0)); # mm7 = a[3] + &pmuludq("mm7","mm0"); # mm7 = w*a[3] + &paddq("mm1","mm2"); # mm1 = carry_in + r[0] + w*a[0] + &movd("mm3",&DWP(4,$r,"",0)); # mm3 = r[1] + &paddq("mm3","mm4"); # mm3 = r[1] + w*a[1] + &movd("mm5",&DWP(8,$r,"",0)); # mm5 = r[2] + &paddq("mm5","mm6"); # mm5 = r[2] + w*a[2] + &movd("mm4",&DWP(12,$r,"",0)); # mm4 = r[3] + &paddq("mm7","mm4"); # mm7 = r[3] + w*a[3] + &movd(&DWP(0,$r,"",0),"mm1"); + &movd("mm2",&DWP(16,$a,"",0)); # mm2 = a[4] + &pmuludq("mm2","mm0"); # mm2 = w*a[4] + &psrlq("mm1",32); # mm1 = carry0 + &movd("mm4",&DWP(20,$a,"",0)); # mm4 = a[5] + &pmuludq("mm4","mm0"); # mm4 = w*a[5] + &paddq("mm1","mm3"); # mm1 = carry0 + r[1] + w*a[1] + &movd("mm6",&DWP(24,$a,"",0)); # mm6 = a[6] + &pmuludq("mm6","mm0"); # mm6 = w*a[6] + &movd(&DWP(4,$r,"",0),"mm1"); + &psrlq("mm1",32); # mm1 = carry1 + &movd("mm3",&DWP(28,$a,"",0)); # mm3 = a[7] + &add($a,32); + &pmuludq("mm3","mm0"); # mm3 = w*a[7] + &paddq("mm1","mm5"); # mm1 = carry1 + r[2] + w*a[2] + &movd("mm5",&DWP(16,$r,"",0)); # mm5 = r[4] + &paddq("mm2","mm5"); # mm2 = r[4] + w*a[4] + &movd(&DWP(8,$r,"",0),"mm1"); + &psrlq("mm1",32); # mm1 = carry2 + &paddq("mm1","mm7"); # mm1 = carry2 + r[3] + w*a[3] + &movd("mm5",&DWP(20,$r,"",0)); # mm5 = r[5] + &paddq("mm4","mm5"); # mm4 = r[5] + w*a[5] + &movd(&DWP(12,$r,"",0),"mm1"); + &psrlq("mm1",32); # mm1 = carry3 + &paddq("mm1","mm2"); # mm1 = carry3 + r[4] + w*a[4] + &movd("mm5",&DWP(24,$r,"",0)); # mm5 = r[6] + &paddq("mm6","mm5"); # mm6 = r[6] + w*a[6] + &movd(&DWP(16,$r,"",0),"mm1"); + &psrlq("mm1",32); # mm1 = carry4 + &paddq("mm1","mm4"); # mm1 = carry4 + r[5] + w*a[5] + &movd("mm5",&DWP(28,$r,"",0)); # mm5 = r[7] + &paddq("mm3","mm5"); # mm3 = r[7] + w*a[7] + &movd(&DWP(20,$r,"",0),"mm1"); + &psrlq("mm1",32); # mm1 = carry5 + &paddq("mm1","mm6"); # mm1 = carry5 + r[6] + w*a[6] + &movd(&DWP(24,$r,"",0),"mm1"); + &psrlq("mm1",32); # mm1 = carry6 + &paddq("mm1","mm3"); # mm1 = carry6 + r[7] + w*a[7] + &movd(&DWP(28,$r,"",0),"mm1"); + &add($r,32); + &psrlq("mm1",32); # mm1 = carry_out + + &sub("ecx",8); + &jnz(&label("maw_sse2_loop")); + + &movd($c,"mm1"); # c = carry_out + &emms(); + + &jmp(&label("maw_finish")); + } + &set_label("maw_loop",0); &mov(&swtmp(0),"ecx"); # diff --git a/src/lib/libcrypto/bn/asm/ia64.S b/src/lib/libcrypto/bn/asm/ia64.S index 7b82b820e6..951abc53ea 100644 --- a/src/lib/libcrypto/bn/asm/ia64.S +++ b/src/lib/libcrypto/bn/asm/ia64.S @@ -171,21 +171,21 @@ .skip 32 // makes the loop body aligned at 64-byte boundary bn_add_words: .prologue - .fframe 0 .save ar.pfs,r2 { .mii; alloc r2=ar.pfs,4,12,0,16 cmp4.le p6,p0=r35,r0 };; { .mfb; mov r8=r0 // return value (p6) br.ret.spnt.many b0 };; - .save ar.lc,r3 { .mib; sub r10=r35,r0,1 + .save ar.lc,r3 mov r3=ar.lc brp.loop.imp .L_bn_add_words_ctop,.L_bn_add_words_cend-16 } - .body { .mib; ADDP r14=0,r32 // rp + .save pr,r9 mov r9=pr };; + .body { .mii; ADDP r15=0,r33 // ap mov ar.lc=r10 mov ar.ec=6 } @@ -224,21 +224,21 @@ bn_add_words: .skip 32 // makes the loop body aligned at 64-byte boundary bn_sub_words: .prologue - .fframe 0 .save ar.pfs,r2 { .mii; alloc r2=ar.pfs,4,12,0,16 cmp4.le p6,p0=r35,r0 };; { .mfb; mov r8=r0 // return value (p6) br.ret.spnt.many b0 };; - .save ar.lc,r3 { .mib; sub r10=r35,r0,1 + .save ar.lc,r3 mov r3=ar.lc brp.loop.imp .L_bn_sub_words_ctop,.L_bn_sub_words_cend-16 } - .body { .mib; ADDP r14=0,r32 // rp + .save pr,r9 mov r9=pr };; + .body { .mii; ADDP r15=0,r33 // ap mov ar.lc=r10 mov ar.ec=6 } @@ -283,7 +283,6 @@ bn_sub_words: .skip 32 // makes the loop body aligned at 64-byte boundary bn_mul_words: .prologue - .fframe 0 .save ar.pfs,r2 #ifdef XMA_TEMPTATION { .mfi; alloc r2=ar.pfs,4,0,0,0 };; @@ -294,9 +293,10 @@ bn_mul_words: cmp4.le p6,p0=r34,r0 (p6) br.ret.spnt.many b0 };; - .save ar.lc,r3 { .mii; sub r10=r34,r0,1 + .save ar.lc,r3 mov r3=ar.lc + .save pr,r9 mov r9=pr };; .body @@ -397,22 +397,21 @@ bn_mul_words: .skip 48 // makes the loop body aligned at 64-byte boundary bn_mul_add_words: .prologue - .fframe 0 .save ar.pfs,r2 - .save ar.lc,r3 - .save pr,r9 { .mmi; alloc r2=ar.pfs,4,4,0,8 cmp4.le p6,p0=r34,r0 + .save ar.lc,r3 mov r3=ar.lc };; { .mib; mov r8=r0 // return value sub r10=r34,r0,1 (p6) br.ret.spnt.many b0 };; - .body { .mib; setf.sig f8=r35 // w + .save pr,r9 mov r9=pr brp.loop.imp .L_bn_mul_add_words_ctop,.L_bn_mul_add_words_cend-16 } + .body { .mmi; ADDP r14=0,r32 // rp ADDP r15=0,r33 // ap mov ar.lc=r10 } @@ -466,7 +465,6 @@ bn_mul_add_words: .skip 32 // makes the loop body aligned at 64-byte boundary bn_sqr_words: .prologue - .fframe 0 .save ar.pfs,r2 { .mii; alloc r2=ar.pfs,3,0,0,0 sxt4 r34=r34 };; @@ -476,9 +474,10 @@ bn_sqr_words: nop.f 0x0 (p6) br.ret.spnt.many b0 };; - .save ar.lc,r3 { .mii; sub r10=r34,r0,1 + .save ar.lc,r3 mov r3=ar.lc + .save pr,r9 mov r9=pr };; .body @@ -545,7 +544,6 @@ bn_sqr_words: .align 64 bn_sqr_comba8: .prologue - .fframe 0 .save ar.pfs,r2 #if defined(_HPUX_SOURCE) && !defined(_LP64) { .mii; alloc r2=ar.pfs,2,1,0,0 @@ -617,7 +615,6 @@ bn_sqr_comba8: .align 64 bn_mul_comba8: .prologue - .fframe 0 .save ar.pfs,r2 #if defined(_HPUX_SOURCE) && !defined(_LP64) { .mii; alloc r2=ar.pfs,3,0,0,0 @@ -1175,7 +1172,6 @@ bn_mul_comba8: .align 64 bn_sqr_comba4: .prologue - .fframe 0 .save ar.pfs,r2 #if defined(_HPUX_SOURCE) && !defined(_LP64) { .mii; alloc r2=ar.pfs,2,1,0,0 @@ -1208,7 +1204,6 @@ bn_sqr_comba4: .align 64 bn_mul_comba4: .prologue - .fframe 0 .save ar.pfs,r2 #if defined(_HPUX_SOURCE) && !defined(_LP64) { .mii; alloc r2=ar.pfs,3,0,0,0 @@ -1411,11 +1406,11 @@ equ=p24 .align 64 bn_div_words: .prologue - .fframe 0 .save ar.pfs,r2 - .save b0,r3 { .mii; alloc r2=ar.pfs,3,5,0,8 + .save b0,r3 mov r3=b0 + .save pr,r10 mov r10=pr };; { .mmb; cmp.eq p6,p0=r34,r0 mov r8=-1 diff --git a/src/lib/libcrypto/bn/bn.h b/src/lib/libcrypto/bn/bn.h index 1251521c54..6d754d5547 100644 --- a/src/lib/libcrypto/bn/bn.h +++ b/src/lib/libcrypto/bn/bn.h @@ -55,6 +55,19 @@ * copied and put under another distribution licence * [including the GNU Public Licence.] */ +/* ==================================================================== + * Copyright 2002 Sun Microsystems, Inc. ALL RIGHTS RESERVED. + * + * Portions of the attached software ("Contribution") are developed by + * SUN MICROSYSTEMS, INC., and are contributed to the OpenSSL project. + * + * The Contribution is licensed pursuant to the Eric Young open source + * license provided above. + * + * The binary polynomial arithmetic software is originally written by + * Sheueling Chang Shantz and Douglas Stebila of Sun Microsystems Laboratories. + * + */ #ifndef HEADER_BN_H #define HEADER_BN_H @@ -63,14 +76,23 @@ #ifndef OPENSSL_NO_FP_API #include /* FILE */ #endif +#include #ifdef __cplusplus extern "C" { #endif -#ifdef OPENSSL_SYS_VMS -#undef BN_LLONG /* experimental, so far... */ -#endif +/* These preprocessor symbols control various aspects of the bignum headers and + * library code. They're not defined by any "normal" configuration, as they are + * intended for development and testing purposes. NB: defining all three can be + * useful for debugging application code as well as openssl itself. + * + * BN_DEBUG - turn on various debugging alterations to the bignum code + * BN_DEBUG_RAND - uses random poisoning of unused words to trip up + * mismanagement of bignum internals. You must also define BN_DEBUG. + */ +/* #define BN_DEBUG */ +/* #define BN_DEBUG_RAND */ #define BN_MUL_COMBA #define BN_SQR_COMBA @@ -143,10 +165,12 @@ extern "C" { #endif #ifdef THIRTY_TWO_BIT -#if defined(OPENSSL_SYS_WIN32) && !defined(__GNUC__) -#define BN_ULLONG unsigned _int64 -#else -#define BN_ULLONG unsigned long long +#ifdef BN_LLONG +# if defined(OPENSSL_SYS_WIN32) && !defined(__GNUC__) +# define BN_ULLONG unsigned __int64 +# else +# define BN_ULLONG unsigned long long +# endif #endif #define BN_ULONG unsigned long #define BN_LONG long @@ -219,15 +243,23 @@ extern "C" { #define BN_DEFAULT_BITS 1280 -#ifdef BIGNUM -#undef BIGNUM -#endif - #define BN_FLG_MALLOCED 0x01 #define BN_FLG_STATIC_DATA 0x02 -#define BN_FLG_EXP_CONSTTIME 0x04 /* avoid leaking exponent information through timings - * (BN_mod_exp_mont() will call BN_mod_exp_mont_consttime) */ +#define BN_FLG_CONSTTIME 0x04 /* avoid leaking exponent information through timing, + * BN_mod_exp_mont() will call BN_mod_exp_mont_consttime, + * BN_div() will call BN_div_no_branch, + * BN_mod_inverse() will call BN_mod_inverse_no_branch. + */ + +#ifndef OPENSSL_NO_DEPRECATED +#define BN_FLG_EXP_CONSTTIME BN_FLG_CONSTTIME /* deprecated name for the flag */ + /* avoid leaking exponent information through timings + * (BN_mod_exp_mont() will call BN_mod_exp_mont_consttime) */ +#endif + +#ifndef OPENSSL_NO_DEPRECATED #define BN_FLG_FREE 0x8000 /* used for debuging */ +#endif #define BN_set_flags(b,n) ((b)->flags|=(n)) #define BN_get_flags(b,n) ((b)->flags&(n)) @@ -242,7 +274,18 @@ extern "C" { | BN_FLG_STATIC_DATA \ | (n))) -typedef struct bignum_st +/* Already declared in ossl_typ.h */ +#if 0 +typedef struct bignum_st BIGNUM; +/* Used for temp variables (declaration hidden in bn_lcl.h) */ +typedef struct bignum_ctx BN_CTX; +typedef struct bn_blinding_st BN_BLINDING; +typedef struct bn_mont_ctx_st BN_MONT_CTX; +typedef struct bn_recp_ctx_st BN_RECP_CTX; +typedef struct bn_gencb_st BN_GENCB; +#endif + +struct bignum_st { BN_ULONG *d; /* Pointer to an array of 'BN_BITS2' bit chunks. */ int top; /* Index of last used d +1. */ @@ -250,44 +293,64 @@ typedef struct bignum_st int dmax; /* Size of the d array. */ int neg; /* one if the number is negative */ int flags; - } BIGNUM; - -/* Used for temp variables (declaration hidden in bn_lcl.h) */ -typedef struct bignum_ctx BN_CTX; - -typedef struct bn_blinding_st - { - int init; - BIGNUM *A; - BIGNUM *Ai; - BIGNUM *mod; /* just a reference */ - unsigned long thread_id; /* added in OpenSSL 0.9.6j and 0.9.7b; - * used only by crypto/rsa/rsa_eay.c, rsa_lib.c */ - } BN_BLINDING; + }; /* Used for montgomery multiplication */ -typedef struct bn_mont_ctx_st +struct bn_mont_ctx_st { int ri; /* number of bits in R */ BIGNUM RR; /* used to convert to montgomery form */ BIGNUM N; /* The modulus */ BIGNUM Ni; /* R*(1/R mod N) - N*Ni = 1 * (Ni is only stored for bignum algorithm) */ +#if 0 + /* OpenSSL 0.9.9 preview: */ + BN_ULONG n0[2];/* least significant word(s) of Ni */ +#else BN_ULONG n0; /* least significant word of Ni */ +#endif int flags; - } BN_MONT_CTX; + }; /* Used for reciprocal division/mod functions * It cannot be shared between threads */ -typedef struct bn_recp_ctx_st +struct bn_recp_ctx_st { BIGNUM N; /* the divisor */ BIGNUM Nr; /* the reciprocal */ int num_bits; int shift; int flags; - } BN_RECP_CTX; + }; + +/* Used for slow "generation" functions. */ +struct bn_gencb_st + { + unsigned int ver; /* To handle binary (in)compatibility */ + void *arg; /* callback-specific data */ + union + { + /* if(ver==1) - handles old style callbacks */ + void (*cb_1)(int, int, void *); + /* if(ver==2) - new callback style */ + int (*cb_2)(int, int, BN_GENCB *); + } cb; + }; +/* Wrapper function to make using BN_GENCB easier, */ +int BN_GENCB_call(BN_GENCB *cb, int a, int b); +/* Macro to populate a BN_GENCB structure with an "old"-style callback */ +#define BN_GENCB_set_old(gencb, callback, cb_arg) { \ + BN_GENCB *tmp_gencb = (gencb); \ + tmp_gencb->ver = 1; \ + tmp_gencb->arg = (cb_arg); \ + tmp_gencb->cb.cb_1 = (callback); } +/* Macro to populate a BN_GENCB structure with a "new"-style callback */ +#define BN_GENCB_set(gencb, callback, cb_arg) { \ + BN_GENCB *tmp_gencb = (gencb); \ + tmp_gencb->ver = 2; \ + tmp_gencb->arg = (cb_arg); \ + tmp_gencb->cb.cb_2 = (callback); } #define BN_prime_checks 0 /* default: select number of iterations based on the size of the number */ @@ -312,24 +375,33 @@ typedef struct bn_recp_ctx_st #define BN_num_bytes(a) ((BN_num_bits(a)+7)/8) -/* Note that BN_abs_is_word does not work reliably for w == 0 */ -#define BN_abs_is_word(a,w) (((a)->top == 1) && ((a)->d[0] == (BN_ULONG)(w))) -#define BN_is_zero(a) (((a)->top == 0) || BN_abs_is_word(a,0)) +/* Note that BN_abs_is_word didn't work reliably for w == 0 until 0.9.8 */ +#define BN_abs_is_word(a,w) ((((a)->top == 1) && ((a)->d[0] == (BN_ULONG)(w))) || \ + (((w) == 0) && ((a)->top == 0))) +#define BN_is_zero(a) ((a)->top == 0) #define BN_is_one(a) (BN_abs_is_word((a),1) && !(a)->neg) -#define BN_is_word(a,w) ((w) ? BN_abs_is_word((a),(w)) && !(a)->neg : \ - BN_is_zero((a))) +#define BN_is_word(a,w) (BN_abs_is_word((a),(w)) && (!(w) || !(a)->neg)) #define BN_is_odd(a) (((a)->top > 0) && ((a)->d[0] & 1)) #define BN_one(a) (BN_set_word((a),1)) +#define BN_zero_ex(a) \ + do { \ + BIGNUM *_tmp_bn = (a); \ + _tmp_bn->top = 0; \ + _tmp_bn->neg = 0; \ + } while(0) +#ifdef OPENSSL_NO_DEPRECATED +#define BN_zero(a) BN_zero_ex(a) +#else #define BN_zero(a) (BN_set_word((a),0)) - -/*#define BN_ascii2bn(a) BN_hex2bn(a) */ -/*#define BN_bn2ascii(a) BN_bn2hex(a) */ +#endif const BIGNUM *BN_value_one(void); char * BN_options(void); BN_CTX *BN_CTX_new(void); +#ifndef OPENSSL_NO_DEPRECATED void BN_CTX_init(BN_CTX *c); +#endif void BN_CTX_free(BN_CTX *c); void BN_CTX_start(BN_CTX *ctx); BIGNUM *BN_CTX_get(BN_CTX *ctx); @@ -355,6 +427,16 @@ int BN_uadd(BIGNUM *r, const BIGNUM *a, const BIGNUM *b); int BN_add(BIGNUM *r, const BIGNUM *a, const BIGNUM *b); int BN_mul(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx); int BN_sqr(BIGNUM *r, const BIGNUM *a,BN_CTX *ctx); +/** BN_set_negative sets sign of a BIGNUM + * \param b pointer to the BIGNUM object + * \param n 0 if the BIGNUM b should be positive and a value != 0 otherwise + */ +void BN_set_negative(BIGNUM *b, int n); +/** BN_is_negative returns 1 if the BIGNUM is negative + * \param a pointer to the BIGNUM object + * \return 1 if a < 0 and 0 otherwise + */ +#define BN_is_negative(a) ((a)->neg != 0) int BN_div(BIGNUM *dv, BIGNUM *rem, const BIGNUM *m, const BIGNUM *d, BN_CTX *ctx); @@ -428,6 +510,9 @@ BIGNUM *BN_mod_inverse(BIGNUM *ret, const BIGNUM *a, const BIGNUM *n,BN_CTX *ctx); BIGNUM *BN_mod_sqrt(BIGNUM *ret, const BIGNUM *a, const BIGNUM *n,BN_CTX *ctx); + +/* Deprecated versions */ +#ifndef OPENSSL_NO_DEPRECATED BIGNUM *BN_generate_prime(BIGNUM *ret,int bits,int safe, const BIGNUM *add, const BIGNUM *rem, void (*callback)(int,int,void *),void *cb_arg); @@ -437,19 +522,14 @@ int BN_is_prime(const BIGNUM *p,int nchecks, int BN_is_prime_fasttest(const BIGNUM *p,int nchecks, void (*callback)(int,int,void *),BN_CTX *ctx,void *cb_arg, int do_trial_division); +#endif /* !defined(OPENSSL_NO_DEPRECATED) */ -#ifdef OPENSSL_FIPS -int BN_X931_derive_prime(BIGNUM *p, BIGNUM *p1, BIGNUM *p2, - void (*cb)(int, int, void *), void *cb_arg, - const BIGNUM *Xp, const BIGNUM *Xp1, const BIGNUM *Xp2, - const BIGNUM *e, BN_CTX *ctx); -int BN_X931_generate_Xpq(BIGNUM *Xp, BIGNUM *Xq, int nbits, BN_CTX *ctx); -int BN_X931_generate_prime(BIGNUM *p, BIGNUM *p1, BIGNUM *p2, - BIGNUM *Xp1, BIGNUM *Xp2, - const BIGNUM *Xp, - const BIGNUM *e, BN_CTX *ctx, - void (*cb)(int, int, void *), void *cb_arg); -#endif +/* Newer versions */ +int BN_generate_prime_ex(BIGNUM *ret,int bits,int safe, const BIGNUM *add, + const BIGNUM *rem, BN_GENCB *cb); +int BN_is_prime_ex(const BIGNUM *p,int nchecks, BN_CTX *ctx, BN_GENCB *cb); +int BN_is_prime_fasttest_ex(const BIGNUM *p,int nchecks, BN_CTX *ctx, + int do_trial_division, BN_GENCB *cb); BN_MONT_CTX *BN_MONT_CTX_new(void ); void BN_MONT_CTX_init(BN_MONT_CTX *ctx); @@ -465,14 +545,31 @@ BN_MONT_CTX *BN_MONT_CTX_copy(BN_MONT_CTX *to,BN_MONT_CTX *from); BN_MONT_CTX *BN_MONT_CTX_set_locked(BN_MONT_CTX **pmont, int lock, const BIGNUM *mod, BN_CTX *ctx); -BN_BLINDING *BN_BLINDING_new(BIGNUM *A,BIGNUM *Ai,BIGNUM *mod); +/* BN_BLINDING flags */ +#define BN_BLINDING_NO_UPDATE 0x00000001 +#define BN_BLINDING_NO_RECREATE 0x00000002 + +BN_BLINDING *BN_BLINDING_new(const BIGNUM *A, const BIGNUM *Ai, /* const */ BIGNUM *mod); void BN_BLINDING_free(BN_BLINDING *b); int BN_BLINDING_update(BN_BLINDING *b,BN_CTX *ctx); -int BN_BLINDING_convert(BIGNUM *n, BN_BLINDING *r, BN_CTX *ctx); +int BN_BLINDING_convert(BIGNUM *n, BN_BLINDING *b, BN_CTX *ctx); int BN_BLINDING_invert(BIGNUM *n, BN_BLINDING *b, BN_CTX *ctx); - +int BN_BLINDING_convert_ex(BIGNUM *n, BIGNUM *r, BN_BLINDING *b, BN_CTX *); +int BN_BLINDING_invert_ex(BIGNUM *n, const BIGNUM *r, BN_BLINDING *b, BN_CTX *); +unsigned long BN_BLINDING_get_thread_id(const BN_BLINDING *); +void BN_BLINDING_set_thread_id(BN_BLINDING *, unsigned long); +unsigned long BN_BLINDING_get_flags(const BN_BLINDING *); +void BN_BLINDING_set_flags(BN_BLINDING *, unsigned long); +BN_BLINDING *BN_BLINDING_create_param(BN_BLINDING *b, + const BIGNUM *e, /* const */ BIGNUM *m, BN_CTX *ctx, + int (*bn_mod_exp)(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, + const BIGNUM *m, BN_CTX *ctx, BN_MONT_CTX *m_ctx), + BN_MONT_CTX *m_ctx); + +#ifndef OPENSSL_NO_DEPRECATED void BN_set_params(int mul,int high,int low,int mont); int BN_get_params(int which); /* 0, mul, 1 high, 2 low, 3 mont */ +#endif void BN_RECP_CTX_init(BN_RECP_CTX *recp); BN_RECP_CTX *BN_RECP_CTX_new(void); @@ -485,15 +582,162 @@ int BN_mod_exp_recp(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, int BN_div_recp(BIGNUM *dv, BIGNUM *rem, const BIGNUM *m, BN_RECP_CTX *recp, BN_CTX *ctx); +/* Functions for arithmetic over binary polynomials represented by BIGNUMs. + * + * The BIGNUM::neg property of BIGNUMs representing binary polynomials is + * ignored. + * + * Note that input arguments are not const so that their bit arrays can + * be expanded to the appropriate size if needed. + */ + +int BN_GF2m_add(BIGNUM *r, const BIGNUM *a, const BIGNUM *b); /*r = a + b*/ +#define BN_GF2m_sub(r, a, b) BN_GF2m_add(r, a, b) +int BN_GF2m_mod(BIGNUM *r, const BIGNUM *a, const BIGNUM *p); /*r=a mod p*/ +int BN_GF2m_mod_mul(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, + const BIGNUM *p, BN_CTX *ctx); /* r = (a * b) mod p */ +int BN_GF2m_mod_sqr(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, + BN_CTX *ctx); /* r = (a * a) mod p */ +int BN_GF2m_mod_inv(BIGNUM *r, const BIGNUM *b, const BIGNUM *p, + BN_CTX *ctx); /* r = (1 / b) mod p */ +int BN_GF2m_mod_div(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, + const BIGNUM *p, BN_CTX *ctx); /* r = (a / b) mod p */ +int BN_GF2m_mod_exp(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, + const BIGNUM *p, BN_CTX *ctx); /* r = (a ^ b) mod p */ +int BN_GF2m_mod_sqrt(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, + BN_CTX *ctx); /* r = sqrt(a) mod p */ +int BN_GF2m_mod_solve_quad(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, + BN_CTX *ctx); /* r^2 + r = a mod p */ +#define BN_GF2m_cmp(a, b) BN_ucmp((a), (b)) +/* Some functions allow for representation of the irreducible polynomials + * as an unsigned int[], say p. The irreducible f(t) is then of the form: + * t^p[0] + t^p[1] + ... + t^p[k] + * where m = p[0] > p[1] > ... > p[k] = 0. + */ +int BN_GF2m_mod_arr(BIGNUM *r, const BIGNUM *a, const unsigned int p[]); + /* r = a mod p */ +int BN_GF2m_mod_mul_arr(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, + const unsigned int p[], BN_CTX *ctx); /* r = (a * b) mod p */ +int BN_GF2m_mod_sqr_arr(BIGNUM *r, const BIGNUM *a, const unsigned int p[], + BN_CTX *ctx); /* r = (a * a) mod p */ +int BN_GF2m_mod_inv_arr(BIGNUM *r, const BIGNUM *b, const unsigned int p[], + BN_CTX *ctx); /* r = (1 / b) mod p */ +int BN_GF2m_mod_div_arr(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, + const unsigned int p[], BN_CTX *ctx); /* r = (a / b) mod p */ +int BN_GF2m_mod_exp_arr(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, + const unsigned int p[], BN_CTX *ctx); /* r = (a ^ b) mod p */ +int BN_GF2m_mod_sqrt_arr(BIGNUM *r, const BIGNUM *a, + const unsigned int p[], BN_CTX *ctx); /* r = sqrt(a) mod p */ +int BN_GF2m_mod_solve_quad_arr(BIGNUM *r, const BIGNUM *a, + const unsigned int p[], BN_CTX *ctx); /* r^2 + r = a mod p */ +int BN_GF2m_poly2arr(const BIGNUM *a, unsigned int p[], int max); +int BN_GF2m_arr2poly(const unsigned int p[], BIGNUM *a); + +/* faster mod functions for the 'NIST primes' + * 0 <= a < p^2 */ +int BN_nist_mod_192(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx); +int BN_nist_mod_224(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx); +int BN_nist_mod_256(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx); +int BN_nist_mod_384(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx); +int BN_nist_mod_521(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx); + +const BIGNUM *BN_get0_nist_prime_192(void); +const BIGNUM *BN_get0_nist_prime_224(void); +const BIGNUM *BN_get0_nist_prime_256(void); +const BIGNUM *BN_get0_nist_prime_384(void); +const BIGNUM *BN_get0_nist_prime_521(void); + /* library internal functions */ #define bn_expand(a,bits) ((((((bits+BN_BITS2-1))/BN_BITS2)) <= (a)->dmax)?\ - (a):bn_expand2((a),(bits)/BN_BITS2+1)) + (a):bn_expand2((a),(bits+BN_BITS2-1)/BN_BITS2)) #define bn_wexpand(a,words) (((words) <= (a)->dmax)?(a):bn_expand2((a),(words))) BIGNUM *bn_expand2(BIGNUM *a, int words); -BIGNUM *bn_dup_expand(const BIGNUM *a, int words); +#ifndef OPENSSL_NO_DEPRECATED +BIGNUM *bn_dup_expand(const BIGNUM *a, int words); /* unused */ +#endif + +/* Bignum consistency macros + * There is one "API" macro, bn_fix_top(), for stripping leading zeroes from + * bignum data after direct manipulations on the data. There is also an + * "internal" macro, bn_check_top(), for verifying that there are no leading + * zeroes. Unfortunately, some auditing is required due to the fact that + * bn_fix_top() has become an overabused duct-tape because bignum data is + * occasionally passed around in an inconsistent state. So the following + * changes have been made to sort this out; + * - bn_fix_top()s implementation has been moved to bn_correct_top() + * - if BN_DEBUG isn't defined, bn_fix_top() maps to bn_correct_top(), and + * bn_check_top() is as before. + * - if BN_DEBUG *is* defined; + * - bn_check_top() tries to pollute unused words even if the bignum 'top' is + * consistent. (ed: only if BN_DEBUG_RAND is defined) + * - bn_fix_top() maps to bn_check_top() rather than "fixing" anything. + * The idea is to have debug builds flag up inconsistent bignums when they + * occur. If that occurs in a bn_fix_top(), we examine the code in question; if + * the use of bn_fix_top() was appropriate (ie. it follows directly after code + * that manipulates the bignum) it is converted to bn_correct_top(), and if it + * was not appropriate, we convert it permanently to bn_check_top() and track + * down the cause of the bug. Eventually, no internal code should be using the + * bn_fix_top() macro. External applications and libraries should try this with + * their own code too, both in terms of building against the openssl headers + * with BN_DEBUG defined *and* linking with a version of OpenSSL built with it + * defined. This not only improves external code, it provides more test + * coverage for openssl's own code. + */ + +#ifdef BN_DEBUG -#define bn_fix_top(a) \ +/* We only need assert() when debugging */ +#include + +#ifdef BN_DEBUG_RAND +/* To avoid "make update" cvs wars due to BN_DEBUG, use some tricks */ +#ifndef RAND_pseudo_bytes +int RAND_pseudo_bytes(unsigned char *buf,int num); +#define BN_DEBUG_TRIX +#endif +#define bn_pollute(a) \ + do { \ + const BIGNUM *_bnum1 = (a); \ + if(_bnum1->top < _bnum1->dmax) { \ + unsigned char _tmp_char; \ + /* We cast away const without the compiler knowing, any \ + * *genuinely* constant variables that aren't mutable \ + * wouldn't be constructed with top!=dmax. */ \ + BN_ULONG *_not_const; \ + memcpy(&_not_const, &_bnum1->d, sizeof(BN_ULONG*)); \ + RAND_pseudo_bytes(&_tmp_char, 1); \ + memset((unsigned char *)(_not_const + _bnum1->top), _tmp_char, \ + (_bnum1->dmax - _bnum1->top) * sizeof(BN_ULONG)); \ + } \ + } while(0) +#ifdef BN_DEBUG_TRIX +#undef RAND_pseudo_bytes +#endif +#else +#define bn_pollute(a) +#endif +#define bn_check_top(a) \ + do { \ + const BIGNUM *_bnum2 = (a); \ + if (_bnum2 != NULL) { \ + assert((_bnum2->top == 0) || \ + (_bnum2->d[_bnum2->top - 1] != 0)); \ + bn_pollute(_bnum2); \ + } \ + } while(0) + +#define bn_fix_top(a) bn_check_top(a) + +#else /* !BN_DEBUG */ + +#define bn_pollute(a) +#define bn_check_top(a) +#define bn_fix_top(a) bn_correct_top(a) + +#endif + +#define bn_correct_top(a) \ { \ BN_ULONG *ftl; \ if ((a)->top > 0) \ @@ -501,6 +745,7 @@ BIGNUM *bn_dup_expand(const BIGNUM *a, int words); for (ftl= &((a)->d[(a)->top-1]); (a)->top > 0; (a)->top--) \ if (*(ftl--)) break; \ } \ + bn_pollute(a); \ } BN_ULONG bn_mul_add_words(BN_ULONG *rp, const BN_ULONG *ap, int num, BN_ULONG w); @@ -510,15 +755,17 @@ BN_ULONG bn_div_words(BN_ULONG h, BN_ULONG l, BN_ULONG d); BN_ULONG bn_add_words(BN_ULONG *rp, const BN_ULONG *ap, const BN_ULONG *bp,int num); BN_ULONG bn_sub_words(BN_ULONG *rp, const BN_ULONG *ap, const BN_ULONG *bp,int num); -#ifdef BN_DEBUG -void bn_dump1(FILE *o, const char *a, const BN_ULONG *b,int n); -# define bn_print(a) {fprintf(stderr, #a "="); BN_print_fp(stderr,a); \ - fprintf(stderr,"\n");} -# define bn_dump(a,n) bn_dump1(stderr,#a,a,n); -#else -# define bn_print(a) -# define bn_dump(a,b) -#endif +/* Primes from RFC 2409 */ +BIGNUM *get_rfc2409_prime_768(BIGNUM *bn); +BIGNUM *get_rfc2409_prime_1024(BIGNUM *bn); + +/* Primes from RFC 3526 */ +BIGNUM *get_rfc3526_prime_1536(BIGNUM *bn); +BIGNUM *get_rfc3526_prime_2048(BIGNUM *bn); +BIGNUM *get_rfc3526_prime_3072(BIGNUM *bn); +BIGNUM *get_rfc3526_prime_4096(BIGNUM *bn); +BIGNUM *get_rfc3526_prime_6144(BIGNUM *bn); +BIGNUM *get_rfc3526_prime_8192(BIGNUM *bn); int BN_bntest_rand(BIGNUM *rnd, int bits, int top,int bottom); @@ -531,18 +778,30 @@ void ERR_load_BN_strings(void); /* Error codes for the BN functions. */ /* Function codes. */ -#define BN_F_BN_BLINDING_CONVERT 100 -#define BN_F_BN_BLINDING_INVERT 101 +#define BN_F_BNRAND 127 +#define BN_F_BN_BLINDING_CONVERT_EX 100 +#define BN_F_BN_BLINDING_CREATE_PARAM 128 +#define BN_F_BN_BLINDING_INVERT_EX 101 #define BN_F_BN_BLINDING_NEW 102 #define BN_F_BN_BLINDING_UPDATE 103 #define BN_F_BN_BN2DEC 104 #define BN_F_BN_BN2HEX 105 #define BN_F_BN_CTX_GET 116 #define BN_F_BN_CTX_NEW 106 +#define BN_F_BN_CTX_START 129 #define BN_F_BN_DIV 107 +#define BN_F_BN_DIV_NO_BRANCH 138 +#define BN_F_BN_DIV_RECP 130 #define BN_F_BN_EXP 123 #define BN_F_BN_EXPAND2 108 #define BN_F_BN_EXPAND_INTERNAL 120 +#define BN_F_BN_GF2M_MOD 131 +#define BN_F_BN_GF2M_MOD_EXP 132 +#define BN_F_BN_GF2M_MOD_MUL 133 +#define BN_F_BN_GF2M_MOD_SOLVE_QUAD 134 +#define BN_F_BN_GF2M_MOD_SOLVE_QUAD_ARR 135 +#define BN_F_BN_GF2M_MOD_SQR 136 +#define BN_F_BN_GF2M_MOD_SQRT 137 #define BN_F_BN_MOD_EXP2_MONT 118 #define BN_F_BN_MOD_EXP_MONT 109 #define BN_F_BN_MOD_EXP_MONT_CONSTTIME 124 @@ -550,6 +809,7 @@ void ERR_load_BN_strings(void); #define BN_F_BN_MOD_EXP_RECP 125 #define BN_F_BN_MOD_EXP_SIMPLE 126 #define BN_F_BN_MOD_INVERSE 110 +#define BN_F_BN_MOD_INVERSE_NO_BRANCH 139 #define BN_F_BN_MOD_LSHIFT_QUICK 119 #define BN_F_BN_MOD_MUL_RECIPROCAL 111 #define BN_F_BN_MOD_SQRT 121 @@ -573,6 +833,7 @@ void ERR_load_BN_strings(void); #define BN_R_NOT_A_SQUARE 111 #define BN_R_NOT_INITIALIZED 107 #define BN_R_NO_INVERSE 108 +#define BN_R_NO_SOLUTION 116 #define BN_R_P_IS_NOT_PRIME 112 #define BN_R_TOO_MANY_ITERATIONS 113 #define BN_R_TOO_MANY_TEMPORARY_VARIABLES 109 diff --git a/src/lib/libcrypto/bn/bn_add.c b/src/lib/libcrypto/bn/bn_add.c index 6cba07e9f6..9405163706 100644 --- a/src/lib/libcrypto/bn/bn_add.c +++ b/src/lib/libcrypto/bn/bn_add.c @@ -64,7 +64,7 @@ int BN_add(BIGNUM *r, const BIGNUM *a, const BIGNUM *b) { const BIGNUM *tmp; - int a_neg = a->neg; + int a_neg = a->neg, ret; bn_check_top(a); bn_check_top(b); @@ -95,20 +95,17 @@ int BN_add(BIGNUM *r, const BIGNUM *a, const BIGNUM *b) return(1); } - if (!BN_uadd(r,a,b)) return(0); - if (a_neg) /* both are neg */ - r->neg=1; - else - r->neg=0; - return(1); + ret = BN_uadd(r,a,b); + r->neg = a_neg; + bn_check_top(r); + return ret; } -/* unsigned add of b to a, r must be large enough */ +/* unsigned add of b to a */ int BN_uadd(BIGNUM *r, const BIGNUM *a, const BIGNUM *b) { - register int i; - int max,min; - BN_ULONG *ap,*bp,*rp,carry,t1; + int max,min,dif; + BN_ULONG *ap,*bp,*rp,carry,t1,t2; const BIGNUM *tmp; bn_check_top(a); @@ -116,11 +113,12 @@ int BN_uadd(BIGNUM *r, const BIGNUM *a, const BIGNUM *b) if (a->top < b->top) { tmp=a; a=b; b=tmp; } - max=a->top; - min=b->top; + max = a->top; + min = b->top; + dif = max - min; if (bn_wexpand(r,max+1) == NULL) - return(0); + return 0; r->top=max; @@ -128,46 +126,46 @@ int BN_uadd(BIGNUM *r, const BIGNUM *a, const BIGNUM *b) ap=a->d; bp=b->d; rp=r->d; - carry=0; carry=bn_add_words(rp,ap,bp,min); rp+=min; ap+=min; bp+=min; - i=min; if (carry) { - while (i < max) + while (dif) { - i++; - t1= *(ap++); - if ((*(rp++)=(t1+1)&BN_MASK2) >= t1) + dif--; + t1 = *(ap++); + t2 = (t1+1) & BN_MASK2; + *(rp++) = t2; + if (t2) { carry=0; break; } } - if ((i >= max) && carry) + if (carry) { - *(rp++)=1; + /* carry != 0 => dif == 0 */ + *rp = 1; r->top++; } } - if (rp != ap) - { - for (; ineg = 0; - return(1); + bn_check_top(r); + return 1; } /* unsigned subtraction of b from a, a must be larger than b. */ int BN_usub(BIGNUM *r, const BIGNUM *a, const BIGNUM *b) { - int max,min; + int max,min,dif; register BN_ULONG t1,t2,*ap,*bp,*rp; int i,carry; #if defined(IRIX_CC_BUG) && !defined(LINT) @@ -177,14 +175,16 @@ int BN_usub(BIGNUM *r, const BIGNUM *a, const BIGNUM *b) bn_check_top(a); bn_check_top(b); - if (a->top < b->top) /* hmm... should not be happening */ + max = a->top; + min = b->top; + dif = max - min; + + if (dif < 0) /* hmm... should not be happening */ { BNerr(BN_F_BN_USUB,BN_R_ARG2_LT_ARG3); return(0); } - max=a->top; - min=b->top; if (bn_wexpand(r,max) == NULL) return(0); ap=a->d; @@ -193,7 +193,7 @@ int BN_usub(BIGNUM *r, const BIGNUM *a, const BIGNUM *b) #if 1 carry=0; - for (i=0; i t2) break; + dif--; + t1 = *(ap++); + t2 = (t1-1)&BN_MASK2; + *(rp++) = t2; + if (t1) + break; } } #if 0 @@ -237,13 +240,13 @@ int BN_usub(BIGNUM *r, const BIGNUM *a, const BIGNUM *b) { for (;;) { - if (i++ >= max) break; + if (!dif--) break; rp[0]=ap[0]; - if (i++ >= max) break; + if (!dif--) break; rp[1]=ap[1]; - if (i++ >= max) break; + if (!dif--) break; rp[2]=ap[2]; - if (i++ >= max) break; + if (!dif--) break; rp[3]=ap[3]; rp+=4; ap+=4; @@ -253,7 +256,7 @@ int BN_usub(BIGNUM *r, const BIGNUM *a, const BIGNUM *b) r->top=max; r->neg=0; - bn_fix_top(r); + bn_correct_top(r); return(1); } @@ -304,6 +307,7 @@ int BN_sub(BIGNUM *r, const BIGNUM *a, const BIGNUM *b) if (!BN_usub(r,a,b)) return(0); r->neg=0; } + bn_check_top(r); return(1); } diff --git a/src/lib/libcrypto/bn/bn_asm.c b/src/lib/libcrypto/bn/bn_asm.c index 19978085b2..99bc2de491 100644 --- a/src/lib/libcrypto/bn/bn_asm.c +++ b/src/lib/libcrypto/bn/bn_asm.c @@ -459,6 +459,34 @@ BN_ULONG bn_sub_words(BN_ULONG *r, const BN_ULONG *a, const BN_ULONG *b, int n) #define sqr_add_c2(a,i,j,c0,c1,c2) \ mul_add_c2((a)[i],(a)[j],c0,c1,c2) +#elif defined(BN_UMULT_LOHI) + +#define mul_add_c(a,b,c0,c1,c2) { \ + BN_ULONG ta=(a),tb=(b); \ + BN_UMULT_LOHI(t1,t2,ta,tb); \ + c0 += t1; t2 += (c0A=BN_new()) == NULL) goto err; - if ((ret->Ai=BN_new()) == NULL) goto err; - if (!BN_copy(ret->A,A)) goto err; - if (!BN_copy(ret->Ai,Ai)) goto err; - ret->mod=mod; + if (A != NULL) + { + if ((ret->A = BN_dup(A)) == NULL) goto err; + } + if (Ai != NULL) + { + if ((ret->Ai = BN_dup(Ai)) == NULL) goto err; + } + + /* save a copy of mod in the BN_BLINDING structure */ + if ((ret->mod = BN_dup(mod)) == NULL) goto err; + if (BN_get_flags(mod, BN_FLG_CONSTTIME) != 0) + BN_set_flags(ret->mod, BN_FLG_CONSTTIME); + + ret->counter = BN_BLINDING_COUNTER; return(ret); err: if (ret != NULL) BN_BLINDING_free(ret); @@ -91,6 +171,8 @@ void BN_BLINDING_free(BN_BLINDING *r) if (r->A != NULL) BN_free(r->A ); if (r->Ai != NULL) BN_free(r->Ai); + if (r->e != NULL) BN_free(r->e ); + if (r->mod != NULL) BN_free(r->mod); OPENSSL_free(r); } @@ -103,42 +185,181 @@ int BN_BLINDING_update(BN_BLINDING *b, BN_CTX *ctx) BNerr(BN_F_BN_BLINDING_UPDATE,BN_R_NOT_INITIALIZED); goto err; } - - if (!BN_mod_mul(b->A,b->A,b->A,b->mod,ctx)) goto err; - if (!BN_mod_mul(b->Ai,b->Ai,b->Ai,b->mod,ctx)) goto err; + + if (--(b->counter) == 0 && b->e != NULL && + !(b->flags & BN_BLINDING_NO_RECREATE)) + { + /* re-create blinding parameters */ + if (!BN_BLINDING_create_param(b, NULL, NULL, ctx, NULL, NULL)) + goto err; + } + else if (!(b->flags & BN_BLINDING_NO_UPDATE)) + { + if (!BN_mod_mul(b->A,b->A,b->A,b->mod,ctx)) goto err; + if (!BN_mod_mul(b->Ai,b->Ai,b->Ai,b->mod,ctx)) goto err; + } ret=1; err: + if (b->counter == 0) + b->counter = BN_BLINDING_COUNTER; return(ret); } int BN_BLINDING_convert(BIGNUM *n, BN_BLINDING *b, BN_CTX *ctx) { + return BN_BLINDING_convert_ex(n, NULL, b, ctx); + } + +int BN_BLINDING_convert_ex(BIGNUM *n, BIGNUM *r, BN_BLINDING *b, BN_CTX *ctx) + { + int ret = 1; + bn_check_top(n); if ((b->A == NULL) || (b->Ai == NULL)) { - BNerr(BN_F_BN_BLINDING_CONVERT,BN_R_NOT_INITIALIZED); + BNerr(BN_F_BN_BLINDING_CONVERT_EX,BN_R_NOT_INITIALIZED); return(0); } - return(BN_mod_mul(n,n,b->A,b->mod,ctx)); + + if (r != NULL) + { + if (!BN_copy(r, b->Ai)) ret=0; + } + + if (!BN_mod_mul(n,n,b->A,b->mod,ctx)) ret=0; + + return ret; } int BN_BLINDING_invert(BIGNUM *n, BN_BLINDING *b, BN_CTX *ctx) + { + return BN_BLINDING_invert_ex(n, NULL, b, ctx); + } + +int BN_BLINDING_invert_ex(BIGNUM *n, const BIGNUM *r, BN_BLINDING *b, BN_CTX *ctx) { int ret; bn_check_top(n); if ((b->A == NULL) || (b->Ai == NULL)) { - BNerr(BN_F_BN_BLINDING_INVERT,BN_R_NOT_INITIALIZED); + BNerr(BN_F_BN_BLINDING_INVERT_EX,BN_R_NOT_INITIALIZED); return(0); } - if ((ret=BN_mod_mul(n,n,b->Ai,b->mod,ctx)) >= 0) + + if (r != NULL) + ret = BN_mod_mul(n, n, r, b->mod, ctx); + else + ret = BN_mod_mul(n, n, b->Ai, b->mod, ctx); + + if (ret >= 0) { if (!BN_BLINDING_update(b,ctx)) return(0); } + bn_check_top(n); return(ret); } +unsigned long BN_BLINDING_get_thread_id(const BN_BLINDING *b) + { + return b->thread_id; + } + +void BN_BLINDING_set_thread_id(BN_BLINDING *b, unsigned long n) + { + b->thread_id = n; + } + +unsigned long BN_BLINDING_get_flags(const BN_BLINDING *b) + { + return b->flags; + } + +void BN_BLINDING_set_flags(BN_BLINDING *b, unsigned long flags) + { + b->flags = flags; + } + +BN_BLINDING *BN_BLINDING_create_param(BN_BLINDING *b, + const BIGNUM *e, /* const */ BIGNUM *m, BN_CTX *ctx, + int (*bn_mod_exp)(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, + const BIGNUM *m, BN_CTX *ctx, BN_MONT_CTX *m_ctx), + BN_MONT_CTX *m_ctx) +{ + int retry_counter = 32; + BN_BLINDING *ret = NULL; + + if (b == NULL) + ret = BN_BLINDING_new(NULL, NULL, m); + else + ret = b; + + if (ret == NULL) + goto err; + + if (ret->A == NULL && (ret->A = BN_new()) == NULL) + goto err; + if (ret->Ai == NULL && (ret->Ai = BN_new()) == NULL) + goto err; + + if (e != NULL) + { + if (ret->e != NULL) + BN_free(ret->e); + ret->e = BN_dup(e); + } + if (ret->e == NULL) + goto err; + + if (bn_mod_exp != NULL) + ret->bn_mod_exp = bn_mod_exp; + if (m_ctx != NULL) + ret->m_ctx = m_ctx; + + do { + if (!BN_rand_range(ret->A, ret->mod)) goto err; + if (BN_mod_inverse(ret->Ai, ret->A, ret->mod, ctx) == NULL) + { + /* this should almost never happen for good RSA keys */ + unsigned long error = ERR_peek_last_error(); + if (ERR_GET_REASON(error) == BN_R_NO_INVERSE) + { + if (retry_counter-- == 0) + { + BNerr(BN_F_BN_BLINDING_CREATE_PARAM, + BN_R_TOO_MANY_ITERATIONS); + goto err; + } + ERR_clear_error(); + } + else + goto err; + } + else + break; + } while (1); + + if (ret->bn_mod_exp != NULL && ret->m_ctx != NULL) + { + if (!ret->bn_mod_exp(ret->A, ret->A, ret->e, ret->mod, ctx, ret->m_ctx)) + goto err; + } + else + { + if (!BN_mod_exp(ret->A, ret->A, ret->e, ret->mod, ctx)) + goto err; + } + + return ret; +err: + if (b == NULL && ret != NULL) + { + BN_BLINDING_free(ret); + ret = NULL; + } + + return ret; +} diff --git a/src/lib/libcrypto/bn/bn_ctx.c b/src/lib/libcrypto/bn/bn_ctx.c index 7daf19eb84..b3452f1a91 100644 --- a/src/lib/libcrypto/bn/bn_ctx.c +++ b/src/lib/libcrypto/bn/bn_ctx.c @@ -1,7 +1,7 @@ /* crypto/bn/bn_ctx.c */ /* Written by Ulf Moeller for the OpenSSL project. */ /* ==================================================================== - * Copyright (c) 1998-2000 The OpenSSL Project. All rights reserved. + * Copyright (c) 1998-2004 The OpenSSL Project. All rights reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions @@ -54,9 +54,10 @@ * */ -#ifndef BN_CTX_DEBUG -# undef NDEBUG /* avoid conflicting definitions */ -# define NDEBUG +#if !defined(BN_CTX_DEBUG) && !defined(BN_DEBUG) +#ifndef NDEBUG +#define NDEBUG +#endif #endif #include @@ -65,91 +66,389 @@ #include "cryptlib.h" #include "bn_lcl.h" +/* TODO list + * + * 1. Check a bunch of "(words+1)" type hacks in various bignum functions and + * check they can be safely removed. + * - Check +1 and other ugliness in BN_from_montgomery() + * + * 2. Consider allowing a BN_new_ex() that, at least, lets you specify an + * appropriate 'block' size that will be honoured by bn_expand_internal() to + * prevent piddly little reallocations. OTOH, profiling bignum expansions in + * BN_CTX doesn't show this to be a big issue. + */ + +/* How many bignums are in each "pool item"; */ +#define BN_CTX_POOL_SIZE 16 +/* The stack frame info is resizing, set a first-time expansion size; */ +#define BN_CTX_START_FRAMES 32 -BN_CTX *BN_CTX_new(void) +/***********/ +/* BN_POOL */ +/***********/ + +/* A bundle of bignums that can be linked with other bundles */ +typedef struct bignum_pool_item + { + /* The bignum values */ + BIGNUM vals[BN_CTX_POOL_SIZE]; + /* Linked-list admin */ + struct bignum_pool_item *prev, *next; + } BN_POOL_ITEM; +/* A linked-list of bignums grouped in bundles */ +typedef struct bignum_pool + { + /* Linked-list admin */ + BN_POOL_ITEM *head, *current, *tail; + /* Stack depth and allocation size */ + unsigned used, size; + } BN_POOL; +static void BN_POOL_init(BN_POOL *); +static void BN_POOL_finish(BN_POOL *); +#ifndef OPENSSL_NO_DEPRECATED +static void BN_POOL_reset(BN_POOL *); +#endif +static BIGNUM * BN_POOL_get(BN_POOL *); +static void BN_POOL_release(BN_POOL *, unsigned int); + +/************/ +/* BN_STACK */ +/************/ + +/* A wrapper to manage the "stack frames" */ +typedef struct bignum_ctx_stack { - BN_CTX *ret; + /* Array of indexes into the bignum stack */ + unsigned int *indexes; + /* Number of stack frames, and the size of the allocated array */ + unsigned int depth, size; + } BN_STACK; +static void BN_STACK_init(BN_STACK *); +static void BN_STACK_finish(BN_STACK *); +#ifndef OPENSSL_NO_DEPRECATED +static void BN_STACK_reset(BN_STACK *); +#endif +static int BN_STACK_push(BN_STACK *, unsigned int); +static unsigned int BN_STACK_pop(BN_STACK *); + +/**********/ +/* BN_CTX */ +/**********/ + +/* The opaque BN_CTX type */ +struct bignum_ctx + { + /* The bignum bundles */ + BN_POOL pool; + /* The "stack frames", if you will */ + BN_STACK stack; + /* The number of bignums currently assigned */ + unsigned int used; + /* Depth of stack overflow */ + int err_stack; + /* Block "gets" until an "end" (compatibility behaviour) */ + int too_many; + }; - ret=(BN_CTX *)OPENSSL_malloc(sizeof(BN_CTX)); - if (ret == NULL) +/* Enable this to find BN_CTX bugs */ +#ifdef BN_CTX_DEBUG +static const char *ctxdbg_cur = NULL; +static void ctxdbg(BN_CTX *ctx) + { + unsigned int bnidx = 0, fpidx = 0; + BN_POOL_ITEM *item = ctx->pool.head; + BN_STACK *stack = &ctx->stack; + fprintf(stderr,"(%08x): ", (unsigned int)ctx); + while(bnidx < ctx->used) { - BNerr(BN_F_BN_CTX_NEW,ERR_R_MALLOC_FAILURE); - return(NULL); + fprintf(stderr,"%02x ", item->vals[bnidx++ % BN_CTX_POOL_SIZE].dmax); + if(!(bnidx % BN_CTX_POOL_SIZE)) + item = item->next; } - - BN_CTX_init(ret); - ret->flags=BN_FLG_MALLOCED; - return(ret); + fprintf(stderr,"\n"); + bnidx = 0; + fprintf(stderr," : "); + while(fpidx < stack->depth) + { + while(bnidx++ < stack->indexes[fpidx]) + fprintf(stderr," "); + fprintf(stderr,"^^ "); + bnidx++; + fpidx++; + } + fprintf(stderr,"\n"); } +#define CTXDBG_ENTRY(str, ctx) do { \ + ctxdbg_cur = (str); \ + fprintf(stderr,"Starting %s\n", ctxdbg_cur); \ + ctxdbg(ctx); \ + } while(0) +#define CTXDBG_EXIT(ctx) do { \ + fprintf(stderr,"Ending %s\n", ctxdbg_cur); \ + ctxdbg(ctx); \ + } while(0) +#define CTXDBG_RET(ctx,ret) +#else +#define CTXDBG_ENTRY(str, ctx) +#define CTXDBG_EXIT(ctx) +#define CTXDBG_RET(ctx,ret) +#endif +/* This function is an evil legacy and should not be used. This implementation + * is WYSIWYG, though I've done my best. */ +#ifndef OPENSSL_NO_DEPRECATED void BN_CTX_init(BN_CTX *ctx) { -#if 0 /* explicit version */ - int i; - ctx->tos = 0; - ctx->flags = 0; - ctx->depth = 0; + /* Assume the caller obtained the context via BN_CTX_new() and so is + * trying to reset it for use. Nothing else makes sense, least of all + * binary compatibility from a time when they could declare a static + * variable. */ + BN_POOL_reset(&ctx->pool); + BN_STACK_reset(&ctx->stack); + ctx->used = 0; + ctx->err_stack = 0; ctx->too_many = 0; - for (i = 0; i < BN_CTX_NUM; i++) - BN_init(&(ctx->bn[i])); -#else - memset(ctx, 0, sizeof *ctx); + } #endif + +BN_CTX *BN_CTX_new(void) + { + BN_CTX *ret = OPENSSL_malloc(sizeof(BN_CTX)); + if(!ret) + { + BNerr(BN_F_BN_CTX_NEW,ERR_R_MALLOC_FAILURE); + return NULL; + } + /* Initialise the structure */ + BN_POOL_init(&ret->pool); + BN_STACK_init(&ret->stack); + ret->used = 0; + ret->err_stack = 0; + ret->too_many = 0; + return ret; } void BN_CTX_free(BN_CTX *ctx) { - int i; - - if (ctx == NULL) return; - assert(ctx->depth == 0); - - for (i=0; i < BN_CTX_NUM; i++) - BN_clear_free(&(ctx->bn[i])); - if (ctx->flags & BN_FLG_MALLOCED) - OPENSSL_free(ctx); + if (ctx == NULL) + return; +#ifdef BN_CTX_DEBUG + { + BN_POOL_ITEM *pool = ctx->pool.head; + fprintf(stderr,"BN_CTX_free, stack-size=%d, pool-bignums=%d\n", + ctx->stack.size, ctx->pool.size); + fprintf(stderr,"dmaxs: "); + while(pool) { + unsigned loop = 0; + while(loop < BN_CTX_POOL_SIZE) + fprintf(stderr,"%02x ", pool->vals[loop++].dmax); + pool = pool->next; + } + fprintf(stderr,"\n"); + } +#endif + BN_STACK_finish(&ctx->stack); + BN_POOL_finish(&ctx->pool); + OPENSSL_free(ctx); } void BN_CTX_start(BN_CTX *ctx) { - if (ctx->depth < BN_CTX_NUM_POS) - ctx->pos[ctx->depth] = ctx->tos; - ctx->depth++; + CTXDBG_ENTRY("BN_CTX_start", ctx); + /* If we're already overflowing ... */ + if(ctx->err_stack || ctx->too_many) + ctx->err_stack++; + /* (Try to) get a new frame pointer */ + else if(!BN_STACK_push(&ctx->stack, ctx->used)) + { + BNerr(BN_F_BN_CTX_START,BN_R_TOO_MANY_TEMPORARY_VARIABLES); + ctx->err_stack++; + } + CTXDBG_EXIT(ctx); } +void BN_CTX_end(BN_CTX *ctx) + { + CTXDBG_ENTRY("BN_CTX_end", ctx); + if(ctx->err_stack) + ctx->err_stack--; + else + { + unsigned int fp = BN_STACK_pop(&ctx->stack); + /* Does this stack frame have anything to release? */ + if(fp < ctx->used) + BN_POOL_release(&ctx->pool, ctx->used - fp); + ctx->used = fp; + /* Unjam "too_many" in case "get" had failed */ + ctx->too_many = 0; + } + CTXDBG_EXIT(ctx); + } BIGNUM *BN_CTX_get(BN_CTX *ctx) { - /* Note: If BN_CTX_get is ever changed to allocate BIGNUMs dynamically, - * make sure that if BN_CTX_get fails once it will return NULL again - * until BN_CTX_end is called. (This is so that callers have to check - * only the last return value.) - */ - if (ctx->depth > BN_CTX_NUM_POS || ctx->tos >= BN_CTX_NUM) + BIGNUM *ret; + CTXDBG_ENTRY("BN_CTX_get", ctx); + if(ctx->err_stack || ctx->too_many) return NULL; + if((ret = BN_POOL_get(&ctx->pool)) == NULL) + { + /* Setting too_many prevents repeated "get" attempts from + * cluttering the error stack. */ + ctx->too_many = 1; + BNerr(BN_F_BN_CTX_GET,BN_R_TOO_MANY_TEMPORARY_VARIABLES); + return NULL; + } + /* OK, make sure the returned bignum is "zero" */ + BN_zero(ret); + ctx->used++; + CTXDBG_RET(ctx, ret); + return ret; + } + +/************/ +/* BN_STACK */ +/************/ + +static void BN_STACK_init(BN_STACK *st) + { + st->indexes = NULL; + st->depth = st->size = 0; + } + +static void BN_STACK_finish(BN_STACK *st) + { + if(st->size) OPENSSL_free(st->indexes); + } + +#ifndef OPENSSL_NO_DEPRECATED +static void BN_STACK_reset(BN_STACK *st) + { + st->depth = 0; + } +#endif + +static int BN_STACK_push(BN_STACK *st, unsigned int idx) + { + if(st->depth == st->size) + /* Need to expand */ + { + unsigned int newsize = (st->size ? + (st->size * 3 / 2) : BN_CTX_START_FRAMES); + unsigned int *newitems = OPENSSL_malloc(newsize * + sizeof(unsigned int)); + if(!newitems) return 0; + if(st->depth) + memcpy(newitems, st->indexes, st->depth * + sizeof(unsigned int)); + if(st->size) OPENSSL_free(st->indexes); + st->indexes = newitems; + st->size = newsize; + } + st->indexes[(st->depth)++] = idx; + return 1; + } + +static unsigned int BN_STACK_pop(BN_STACK *st) + { + return st->indexes[--(st->depth)]; + } + +/***********/ +/* BN_POOL */ +/***********/ + +static void BN_POOL_init(BN_POOL *p) + { + p->head = p->current = p->tail = NULL; + p->used = p->size = 0; + } + +static void BN_POOL_finish(BN_POOL *p) + { + while(p->head) { - if (!ctx->too_many) + unsigned int loop = 0; + BIGNUM *bn = p->head->vals; + while(loop++ < BN_CTX_POOL_SIZE) { - BNerr(BN_F_BN_CTX_GET,BN_R_TOO_MANY_TEMPORARY_VARIABLES); - /* disable error code until BN_CTX_end is called: */ - ctx->too_many = 1; + if(bn->d) BN_clear_free(bn); + bn++; } - return NULL; + p->current = p->head->next; + OPENSSL_free(p->head); + p->head = p->current; } - return (&(ctx->bn[ctx->tos++])); } -void BN_CTX_end(BN_CTX *ctx) +#ifndef OPENSSL_NO_DEPRECATED +static void BN_POOL_reset(BN_POOL *p) { - if (ctx == NULL) return; - assert(ctx->depth > 0); - if (ctx->depth == 0) - /* should never happen, but we can tolerate it if not in - * debug mode (could be a 'goto err' in the calling function - * before BN_CTX_start was reached) */ - BN_CTX_start(ctx); + BN_POOL_ITEM *item = p->head; + while(item) + { + unsigned int loop = 0; + BIGNUM *bn = item->vals; + while(loop++ < BN_CTX_POOL_SIZE) + { + if(bn->d) BN_clear(bn); + bn++; + } + item = item->next; + } + p->current = p->head; + p->used = 0; + } +#endif - ctx->too_many = 0; - ctx->depth--; - if (ctx->depth < BN_CTX_NUM_POS) - ctx->tos = ctx->pos[ctx->depth]; +static BIGNUM *BN_POOL_get(BN_POOL *p) + { + if(p->used == p->size) + { + BIGNUM *bn; + unsigned int loop = 0; + BN_POOL_ITEM *item = OPENSSL_malloc(sizeof(BN_POOL_ITEM)); + if(!item) return NULL; + /* Initialise the structure */ + bn = item->vals; + while(loop++ < BN_CTX_POOL_SIZE) + BN_init(bn++); + item->prev = p->tail; + item->next = NULL; + /* Link it in */ + if(!p->head) + p->head = p->current = p->tail = item; + else + { + p->tail->next = item; + p->tail = item; + p->current = item; + } + p->size += BN_CTX_POOL_SIZE; + p->used++; + /* Return the first bignum from the new pool */ + return item->vals; + } + if(!p->used) + p->current = p->head; + else if((p->used % BN_CTX_POOL_SIZE) == 0) + p->current = p->current->next; + return p->current->vals + ((p->used++) % BN_CTX_POOL_SIZE); + } + +static void BN_POOL_release(BN_POOL *p, unsigned int num) + { + unsigned int offset = (p->used - 1) % BN_CTX_POOL_SIZE; + p->used -= num; + while(num--) + { + bn_check_top(p->current->vals + offset); + if(!offset) + { + offset = BN_CTX_POOL_SIZE - 1; + p->current = p->current->prev; + } + else + offset--; + } } + diff --git a/src/lib/libcrypto/bn/bn_div.c b/src/lib/libcrypto/bn/bn_div.c index 580d1201bc..8655eb118e 100644 --- a/src/lib/libcrypto/bn/bn_div.c +++ b/src/lib/libcrypto/bn/bn_div.c @@ -169,22 +169,31 @@ int BN_div(BIGNUM *dv, BIGNUM *rem, const BIGNUM *m, const BIGNUM *d, #endif /* OPENSSL_NO_ASM */ -/* BN_div computes dv := num / divisor, rounding towards zero, and sets up - * rm such that dv*divisor + rm = num holds. +/* BN_div[_no_branch] computes dv := num / divisor, rounding towards + * zero, and sets up rm such that dv*divisor + rm = num holds. * Thus: * dv->neg == num->neg ^ divisor->neg (unless the result is zero) * rm->neg == num->neg (unless the remainder is zero) * If 'dv' or 'rm' is NULL, the respective value is not returned. */ +static int BN_div_no_branch(BIGNUM *dv, BIGNUM *rm, const BIGNUM *num, + const BIGNUM *divisor, BN_CTX *ctx); int BN_div(BIGNUM *dv, BIGNUM *rm, const BIGNUM *num, const BIGNUM *divisor, BN_CTX *ctx) { - int norm_shift,i,j,loop; + int norm_shift,i,loop; BIGNUM *tmp,wnum,*snum,*sdiv,*res; BN_ULONG *resp,*wnump; BN_ULONG d0,d1; int num_n,div_n; + if ((BN_get_flags(num, BN_FLG_CONSTTIME) != 0) || (BN_get_flags(divisor, BN_FLG_CONSTTIME) != 0)) + { + return BN_div_no_branch(dv, rm, num, divisor, ctx); + } + + bn_check_top(dv); + bn_check_top(rm); bn_check_top(num); bn_check_top(divisor); @@ -210,7 +219,6 @@ int BN_div(BIGNUM *dv, BIGNUM *rm, const BIGNUM *num, const BIGNUM *divisor, res=BN_CTX_get(ctx); else res=dv; if (sdiv == NULL || res == NULL) goto err; - tmp->neg=0; /* First we normalise the numbers */ norm_shift=BN_BITS2-((BN_num_bits(divisor))%BN_BITS2); @@ -222,17 +230,17 @@ int BN_div(BIGNUM *dv, BIGNUM *rm, const BIGNUM *num, const BIGNUM *divisor, div_n=sdiv->top; num_n=snum->top; loop=num_n-div_n; - /* Lets setup a 'window' into snum * This is the part that corresponds to the current * 'area' being divided */ - BN_init(&wnum); - wnum.d= &(snum->d[loop]); - wnum.top= div_n; - wnum.dmax= snum->dmax+1; /* a bit of a lie */ + wnum.neg = 0; + wnum.d = &(snum->d[loop]); + wnum.top = div_n; + /* only needed when BN_ucmp messes up the values between top and max */ + wnum.dmax = snum->dmax - loop; /* so we don't step out of bounds */ /* Get the top 2 words of sdiv */ - /* i=sdiv->top; */ + /* div_n=sdiv->top; */ d0=sdiv->d[div_n-1]; d1=(div_n == 1)?0:sdiv->d[div_n-2]; @@ -250,19 +258,28 @@ int BN_div(BIGNUM *dv, BIGNUM *rm, const BIGNUM *num, const BIGNUM *divisor, if (BN_ucmp(&wnum,sdiv) >= 0) { - if (!BN_usub(&wnum,&wnum,sdiv)) goto err; + /* If BN_DEBUG_RAND is defined BN_ucmp changes (via + * bn_pollute) the const bignum arguments => + * clean the values between top and max again */ + bn_clear_top2max(&wnum); + bn_sub_words(wnum.d, wnum.d, sdiv->d, div_n); *resp=1; - res->d[res->top-1]=1; } else res->top--; + /* if res->top == 0 then clear the neg value otherwise decrease + * the resp pointer */ if (res->top == 0) res->neg = 0; - resp--; + else + resp--; - for (i=0; i 0x%08X\n", #endif /* !BN_DIV3W */ l0=bn_mul_words(tmp->d,sdiv->d,div_n,q); - wnum.d--; wnum.top++; tmp->d[div_n]=l0; - for (j=div_n+1; j>0; j--) - if (tmp->d[j-1]) break; - tmp->top=j; + wnum.d--; + /* ingore top values of the bignums just sub the two + * BN_ULONG arrays with bn_sub_words */ + if (bn_sub_words(wnum.d, wnum.d, tmp->d, div_n+1)) + { + /* Note: As we have considered only the leading + * two BN_ULONGs in the calculation of q, sdiv * q + * might be greater than wnum (but then (q-1) * sdiv + * is less or equal than wnum) + */ + q--; + if (bn_add_words(wnum.d, wnum.d, sdiv->d, div_n)) + /* we can't have an overflow here (assuming + * that q != 0, but if q == 0 then tmp is + * zero anyway) */ + (*wnump)++; + } + /* store part of the result */ + *resp = q; + } + bn_correct_top(snum); + if (rm != NULL) + { + /* Keep a copy of the neg flag in num because if rm==num + * BN_rshift() will overwrite it. + */ + int neg = num->neg; + BN_rshift(rm,snum,norm_shift); + if (!BN_is_zero(rm)) + rm->neg = neg; + bn_check_top(rm); + } + BN_CTX_end(ctx); + return(1); +err: + bn_check_top(rm); + BN_CTX_end(ctx); + return(0); + } + + +/* BN_div_no_branch is a special version of BN_div. It does not contain + * branches that may leak sensitive information. + */ +static int BN_div_no_branch(BIGNUM *dv, BIGNUM *rm, const BIGNUM *num, + const BIGNUM *divisor, BN_CTX *ctx) + { + int norm_shift,i,loop; + BIGNUM *tmp,wnum,*snum,*sdiv,*res; + BN_ULONG *resp,*wnump; + BN_ULONG d0,d1; + int num_n,div_n; + + bn_check_top(dv); + bn_check_top(rm); + bn_check_top(num); + bn_check_top(divisor); + + if (BN_is_zero(divisor)) + { + BNerr(BN_F_BN_DIV_NO_BRANCH,BN_R_DIV_BY_ZERO); + return(0); + } + + BN_CTX_start(ctx); + tmp=BN_CTX_get(ctx); + snum=BN_CTX_get(ctx); + sdiv=BN_CTX_get(ctx); + if (dv == NULL) + res=BN_CTX_get(ctx); + else res=dv; + if (sdiv == NULL || res == NULL) goto err; + + /* First we normalise the numbers */ + norm_shift=BN_BITS2-((BN_num_bits(divisor))%BN_BITS2); + if (!(BN_lshift(sdiv,divisor,norm_shift))) goto err; + sdiv->neg=0; + norm_shift+=BN_BITS2; + if (!(BN_lshift(snum,num,norm_shift))) goto err; + snum->neg=0; + + /* Since we don't know whether snum is larger than sdiv, + * we pad snum with enough zeroes without changing its + * value. + */ + if (snum->top <= sdiv->top+1) + { + if (bn_wexpand(snum, sdiv->top + 2) == NULL) goto err; + for (i = snum->top; i < sdiv->top + 2; i++) snum->d[i] = 0; + snum->top = sdiv->top + 2; + } + else + { + if (bn_wexpand(snum, snum->top + 1) == NULL) goto err; + snum->d[snum->top] = 0; + snum->top ++; + } + + div_n=sdiv->top; + num_n=snum->top; + loop=num_n-div_n; + /* Lets setup a 'window' into snum + * This is the part that corresponds to the current + * 'area' being divided */ + wnum.neg = 0; + wnum.d = &(snum->d[loop]); + wnum.top = div_n; + /* only needed when BN_ucmp messes up the values between top and max */ + wnum.dmax = snum->dmax - loop; /* so we don't step out of bounds */ + + /* Get the top 2 words of sdiv */ + /* div_n=sdiv->top; */ + d0=sdiv->d[div_n-1]; + d1=(div_n == 1)?0:sdiv->d[div_n-2]; + + /* pointer to the 'top' of snum */ + wnump= &(snum->d[num_n-1]); + + /* Setup to 'res' */ + res->neg= (num->neg^divisor->neg); + if (!bn_wexpand(res,(loop+1))) goto err; + res->top=loop-1; + resp= &(res->d[loop-1]); + + /* space for temp */ + if (!bn_wexpand(tmp,(div_n+1))) goto err; + + /* if res->top == 0 then clear the neg value otherwise decrease + * the resp pointer */ + if (res->top == 0) + res->neg = 0; + else + resp--; + + for (i=0; i 0x%08X\n", + n0, n1, d0, q); +#endif +#endif + +#ifndef REMAINDER_IS_ALREADY_CALCULATED + /* + * rem doesn't have to be BN_ULLONG. The least we + * know it's less that d0, isn't it? + */ + rem=(n1-q*d0)&BN_MASK2; +#endif + t2=(BN_ULLONG)d1*q; + + for (;;) + { + if (t2 <= ((((BN_ULLONG)rem)< 0x%08X\n", + n0, n1, d0, q); +#endif +#ifndef REMAINDER_IS_ALREADY_CALCULATED + rem=(n1-q*d0)&BN_MASK2; +#endif - j=wnum.top; - if (!BN_sub(&wnum,&wnum,tmp)) goto err; +#if defined(BN_UMULT_LOHI) + BN_UMULT_LOHI(t2l,t2h,d1,q); +#elif defined(BN_UMULT_HIGH) + t2l = d1 * q; + t2h = BN_UMULT_HIGH(d1,q); +#else + t2l=LBITS(d1); t2h=HBITS(d1); + ql =LBITS(q); qh =HBITS(q); + mul64(t2l,t2h,ql,qh); /* t2=(BN_ULLONG)d1*q; */ +#endif - snum->top=snum->top+wnum.top-j; + for (;;) + { + if ((t2h < rem) || + ((t2h == rem) && (t2l <= wnump[-2]))) + break; + q--; + rem += d0; + if (rem < d0) break; /* don't let rem overflow */ + if (t2l < d1) t2h--; t2l -= d1; + } +#endif /* !BN_LLONG */ + } +#endif /* !BN_DIV3W */ - if (wnum.neg) + l0=bn_mul_words(tmp->d,sdiv->d,div_n,q); + tmp->d[div_n]=l0; + wnum.d--; + /* ingore top values of the bignums just sub the two + * BN_ULONG arrays with bn_sub_words */ + if (bn_sub_words(wnum.d, wnum.d, tmp->d, div_n+1)) { + /* Note: As we have considered only the leading + * two BN_ULONGs in the calculation of q, sdiv * q + * might be greater than wnum (but then (q-1) * sdiv + * is less or equal than wnum) + */ q--; - j=wnum.top; - if (!BN_add(&wnum,&wnum,sdiv)) goto err; - snum->top+=wnum.top-j; + if (bn_add_words(wnum.d, wnum.d, sdiv->d, div_n)) + /* we can't have an overflow here (assuming + * that q != 0, but if q == 0 then tmp is + * zero anyway) */ + (*wnump)++; } - *(resp--)=q; - wnump--; + /* store part of the result */ + *resp = q; } + bn_correct_top(snum); if (rm != NULL) { /* Keep a copy of the neg flag in num because if rm==num @@ -376,10 +618,13 @@ X) -> 0x%08X\n", BN_rshift(rm,snum,norm_shift); if (!BN_is_zero(rm)) rm->neg = neg; + bn_check_top(rm); } + bn_correct_top(res); BN_CTX_end(ctx); return(1); err: + bn_check_top(rm); BN_CTX_end(ctx); return(0); } diff --git a/src/lib/libcrypto/bn/bn_err.c b/src/lib/libcrypto/bn/bn_err.c index 5dfac00c88..cfe2eb94a0 100644 --- a/src/lib/libcrypto/bn/bn_err.c +++ b/src/lib/libcrypto/bn/bn_err.c @@ -1,6 +1,6 @@ /* crypto/bn/bn_err.c */ /* ==================================================================== - * Copyright (c) 1999-2005 The OpenSSL Project. All rights reserved. + * Copyright (c) 1999-2007 The OpenSSL Project. All rights reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions @@ -70,18 +70,30 @@ static ERR_STRING_DATA BN_str_functs[]= { -{ERR_FUNC(BN_F_BN_BLINDING_CONVERT), "BN_BLINDING_convert"}, -{ERR_FUNC(BN_F_BN_BLINDING_INVERT), "BN_BLINDING_invert"}, +{ERR_FUNC(BN_F_BNRAND), "BNRAND"}, +{ERR_FUNC(BN_F_BN_BLINDING_CONVERT_EX), "BN_BLINDING_convert_ex"}, +{ERR_FUNC(BN_F_BN_BLINDING_CREATE_PARAM), "BN_BLINDING_create_param"}, +{ERR_FUNC(BN_F_BN_BLINDING_INVERT_EX), "BN_BLINDING_invert_ex"}, {ERR_FUNC(BN_F_BN_BLINDING_NEW), "BN_BLINDING_new"}, {ERR_FUNC(BN_F_BN_BLINDING_UPDATE), "BN_BLINDING_update"}, {ERR_FUNC(BN_F_BN_BN2DEC), "BN_bn2dec"}, {ERR_FUNC(BN_F_BN_BN2HEX), "BN_bn2hex"}, {ERR_FUNC(BN_F_BN_CTX_GET), "BN_CTX_get"}, {ERR_FUNC(BN_F_BN_CTX_NEW), "BN_CTX_new"}, +{ERR_FUNC(BN_F_BN_CTX_START), "BN_CTX_start"}, {ERR_FUNC(BN_F_BN_DIV), "BN_div"}, +{ERR_FUNC(BN_F_BN_DIV_NO_BRANCH), "BN_div_no_branch"}, +{ERR_FUNC(BN_F_BN_DIV_RECP), "BN_div_recp"}, {ERR_FUNC(BN_F_BN_EXP), "BN_exp"}, {ERR_FUNC(BN_F_BN_EXPAND2), "bn_expand2"}, {ERR_FUNC(BN_F_BN_EXPAND_INTERNAL), "BN_EXPAND_INTERNAL"}, +{ERR_FUNC(BN_F_BN_GF2M_MOD), "BN_GF2m_mod"}, +{ERR_FUNC(BN_F_BN_GF2M_MOD_EXP), "BN_GF2m_mod_exp"}, +{ERR_FUNC(BN_F_BN_GF2M_MOD_MUL), "BN_GF2m_mod_mul"}, +{ERR_FUNC(BN_F_BN_GF2M_MOD_SOLVE_QUAD), "BN_GF2m_mod_solve_quad"}, +{ERR_FUNC(BN_F_BN_GF2M_MOD_SOLVE_QUAD_ARR), "BN_GF2m_mod_solve_quad_arr"}, +{ERR_FUNC(BN_F_BN_GF2M_MOD_SQR), "BN_GF2m_mod_sqr"}, +{ERR_FUNC(BN_F_BN_GF2M_MOD_SQRT), "BN_GF2m_mod_sqrt"}, {ERR_FUNC(BN_F_BN_MOD_EXP2_MONT), "BN_mod_exp2_mont"}, {ERR_FUNC(BN_F_BN_MOD_EXP_MONT), "BN_mod_exp_mont"}, {ERR_FUNC(BN_F_BN_MOD_EXP_MONT_CONSTTIME), "BN_mod_exp_mont_consttime"}, @@ -89,6 +101,7 @@ static ERR_STRING_DATA BN_str_functs[]= {ERR_FUNC(BN_F_BN_MOD_EXP_RECP), "BN_mod_exp_recp"}, {ERR_FUNC(BN_F_BN_MOD_EXP_SIMPLE), "BN_mod_exp_simple"}, {ERR_FUNC(BN_F_BN_MOD_INVERSE), "BN_mod_inverse"}, +{ERR_FUNC(BN_F_BN_MOD_INVERSE_NO_BRANCH), "BN_mod_inverse_no_branch"}, {ERR_FUNC(BN_F_BN_MOD_LSHIFT_QUICK), "BN_mod_lshift_quick"}, {ERR_FUNC(BN_F_BN_MOD_MUL_RECIPROCAL), "BN_mod_mul_reciprocal"}, {ERR_FUNC(BN_F_BN_MOD_SQRT), "BN_mod_sqrt"}, @@ -115,6 +128,7 @@ static ERR_STRING_DATA BN_str_reasons[]= {ERR_REASON(BN_R_NOT_A_SQUARE) ,"not a square"}, {ERR_REASON(BN_R_NOT_INITIALIZED) ,"not initialized"}, {ERR_REASON(BN_R_NO_INVERSE) ,"no inverse"}, +{ERR_REASON(BN_R_NO_SOLUTION) ,"no solution"}, {ERR_REASON(BN_R_P_IS_NOT_PRIME) ,"p is not prime"}, {ERR_REASON(BN_R_TOO_MANY_ITERATIONS) ,"too many iterations"}, {ERR_REASON(BN_R_TOO_MANY_TEMPORARY_VARIABLES),"too many temporary variables"}, @@ -125,15 +139,12 @@ static ERR_STRING_DATA BN_str_reasons[]= void ERR_load_BN_strings(void) { - static int init=1; +#ifndef OPENSSL_NO_ERR - if (init) + if (ERR_func_error_string(BN_str_functs[0].error) == NULL) { - init=0; -#ifndef OPENSSL_NO_ERR ERR_load_strings(0,BN_str_functs); ERR_load_strings(0,BN_str_reasons); -#endif - } +#endif } 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) int i,bits,ret=0; BIGNUM *v,*rr; - if (BN_get_flags(p, BN_FLG_EXP_CONSTTIME) != 0) + if (BN_get_flags(p, BN_FLG_CONSTTIME) != 0) { - /* BN_FLG_EXP_CONSTTIME only supported by BN_mod_exp_mont() */ + /* BN_FLG_CONSTTIME only supported by BN_mod_exp_mont() */ BNerr(BN_F_BN_EXP,ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED); return -1; } @@ -155,6 +155,7 @@ int BN_exp(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx) err: if (r != rr) BN_copy(r,rr); BN_CTX_end(ctx); + bn_check_top(r); return(ret); } @@ -212,7 +213,7 @@ int BN_mod_exp(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, const BIGNUM *m, if (BN_is_odd(m)) { # ifdef MONT_EXP_WORD - if (a->top == 1 && !a->neg && (BN_get_flags(p, BN_FLG_EXP_CONSTTIME) == 0)) + if (a->top == 1 && !a->neg && (BN_get_flags(p, BN_FLG_CONSTTIME) == 0)) { BN_ULONG A = a->d[0]; 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, { ret=BN_mod_exp_simple(r,a,p,m,ctx); } #endif + bn_check_top(r); return(ret); } @@ -237,14 +239,15 @@ int BN_mod_exp_recp(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, const BIGNUM *m, BN_CTX *ctx) { int i,j,bits,ret=0,wstart,wend,window,wvalue; - int start=1,ts=0; + int start=1; BIGNUM *aa; - BIGNUM val[TABLE_SIZE]; + /* Table of variables obtained from 'ctx' */ + BIGNUM *val[TABLE_SIZE]; BN_RECP_CTX recp; - if (BN_get_flags(p, BN_FLG_EXP_CONSTTIME) != 0) + if (BN_get_flags(p, BN_FLG_CONSTTIME) != 0) { - /* BN_FLG_EXP_CONSTTIME only supported by BN_mod_exp_mont() */ + /* BN_FLG_CONSTTIME only supported by BN_mod_exp_mont() */ BNerr(BN_F_BN_MOD_EXP_RECP,ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED); return -1; } @@ -258,7 +261,9 @@ int BN_mod_exp_recp(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, } BN_CTX_start(ctx); - if ((aa = BN_CTX_get(ctx)) == NULL) goto err; + aa = BN_CTX_get(ctx); + val[0] = BN_CTX_get(ctx); + if(!aa || !val[0]) goto err; BN_RECP_CTX_init(&recp); if (m->neg) @@ -273,29 +278,27 @@ int BN_mod_exp_recp(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, if (BN_RECP_CTX_set(&recp,m,ctx) <= 0) goto err; } - BN_init(&(val[0])); - ts=1; - - if (!BN_nnmod(&(val[0]),a,m,ctx)) goto err; /* 1 */ - if (BN_is_zero(&(val[0]))) + if (!BN_nnmod(val[0],a,m,ctx)) goto err; /* 1 */ + if (BN_is_zero(val[0])) { - ret = BN_zero(r); + BN_zero(r); + ret = 1; goto err; } window = BN_window_bits_for_exponent_size(bits); if (window > 1) { - if (!BN_mod_mul_reciprocal(aa,&(val[0]),&(val[0]),&recp,ctx)) + if (!BN_mod_mul_reciprocal(aa,val[0],val[0],&recp,ctx)) goto err; /* 2 */ j=1<<(window-1); for (i=1; i>1]),&recp,ctx)) + if (!BN_mod_mul_reciprocal(r,r,val[wvalue>>1],&recp,ctx)) goto err; /* move the 'window' down further */ @@ -359,9 +362,8 @@ int BN_mod_exp_recp(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, ret=1; err: BN_CTX_end(ctx); - for (i=0; id[0] & 1)) + if (!BN_is_odd(m)) { BNerr(BN_F_BN_MOD_EXP_MONT,BN_R_CALLED_WITH_EVEN_MODULUS); return(0); @@ -400,7 +403,8 @@ int BN_mod_exp_mont(BIGNUM *rr, const BIGNUM *a, const BIGNUM *p, BN_CTX_start(ctx); d = BN_CTX_get(ctx); r = BN_CTX_get(ctx); - if (d == NULL || r == NULL) goto err; + val[0] = BN_CTX_get(ctx); + if (!d || !r || !val[0]) goto err; /* If this is not done, things will break in the montgomery * part */ @@ -413,35 +417,34 @@ int BN_mod_exp_mont(BIGNUM *rr, const BIGNUM *a, const BIGNUM *p, if (!BN_MONT_CTX_set(mont,m,ctx)) goto err; } - BN_init(&val[0]); - ts=1; if (a->neg || BN_ucmp(a,m) >= 0) { - if (!BN_nnmod(&(val[0]),a,m,ctx)) + if (!BN_nnmod(val[0],a,m,ctx)) goto err; - aa= &(val[0]); + aa= val[0]; } else aa=a; if (BN_is_zero(aa)) { - ret = BN_zero(rr); + BN_zero(rr); + ret = 1; goto err; } - if (!BN_to_montgomery(&(val[0]),aa,mont,ctx)) goto err; /* 1 */ + if (!BN_to_montgomery(val[0],aa,mont,ctx)) goto err; /* 1 */ window = BN_window_bits_for_exponent_size(bits); if (window > 1) { - if (!BN_mod_mul_montgomery(d,&(val[0]),&(val[0]),mont,ctx)) goto err; /* 2 */ + if (!BN_mod_mul_montgomery(d,val[0],val[0],mont,ctx)) goto err; /* 2 */ j=1<<(window-1); for (i=1; i>1]),mont,ctx)) + if (!BN_mod_mul_montgomery(r,r,val[wvalue>>1],mont,ctx)) goto err; /* move the 'window' down further */ @@ -508,8 +511,7 @@ int BN_mod_exp_mont(BIGNUM *rr, const BIGNUM *a, const BIGNUM *p, err: if ((in_mont == NULL) && (mont != NULL)) BN_MONT_CTX_free(mont); BN_CTX_end(ctx); - for (i=0; id)[i]; } - bn_fix_top(b); + bn_correct_top(b); return 1; } @@ -552,7 +554,7 @@ static int MOD_EXP_CTIME_COPY_FROM_PREBUF(BIGNUM *b, int top, unsigned char *buf } b->top = top; - bn_fix_top(b); + bn_correct_top(b); return 1; } @@ -743,9 +745,9 @@ int BN_mod_exp_mont_word(BIGNUM *rr, BN_ULONG a, const BIGNUM *p, #define BN_TO_MONTGOMERY_WORD(r, w, mont) \ (BN_set_word(r, (w)) && BN_to_montgomery(r, r, (mont), ctx)) - if (BN_get_flags(p, BN_FLG_EXP_CONSTTIME) != 0) + if (BN_get_flags(p, BN_FLG_CONSTTIME) != 0) { - /* BN_FLG_EXP_CONSTTIME only supported by BN_mod_exp_mont() */ + /* BN_FLG_CONSTTIME only supported by BN_mod_exp_mont() */ BNerr(BN_F_BN_MOD_EXP_MONT_WORD,ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED); return -1; } @@ -753,7 +755,7 @@ int BN_mod_exp_mont_word(BIGNUM *rr, BN_ULONG a, const BIGNUM *p, bn_check_top(p); bn_check_top(m); - if (m->top == 0 || !(m->d[0] & 1)) + if (!BN_is_odd(m)) { BNerr(BN_F_BN_MOD_EXP_MONT_WORD,BN_R_CALLED_WITH_EVEN_MODULUS); return(0); @@ -769,7 +771,8 @@ int BN_mod_exp_mont_word(BIGNUM *rr, BN_ULONG a, const BIGNUM *p, } if (a == 0) { - ret = BN_zero(rr); + BN_zero(rr); + ret = 1; return ret; } @@ -863,23 +866,24 @@ int BN_mod_exp_mont_word(BIGNUM *rr, BN_ULONG a, const BIGNUM *p, err: if ((in_mont == NULL) && (mont != NULL)) BN_MONT_CTX_free(mont); BN_CTX_end(ctx); + bn_check_top(rr); return(ret); } /* The old fallback, simple version :-) */ -int BN_mod_exp_simple(BIGNUM *r, - const BIGNUM *a, const BIGNUM *p, const BIGNUM *m, - BN_CTX *ctx) +int BN_mod_exp_simple(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, + const BIGNUM *m, BN_CTX *ctx) { - int i,j,bits,ret=0,wstart,wend,window,wvalue,ts=0; + int i,j,bits,ret=0,wstart,wend,window,wvalue; int start=1; BIGNUM *d; - BIGNUM val[TABLE_SIZE]; + /* Table of variables obtained from 'ctx' */ + BIGNUM *val[TABLE_SIZE]; - if (BN_get_flags(p, BN_FLG_EXP_CONSTTIME) != 0) + if (BN_get_flags(p, BN_FLG_CONSTTIME) != 0) { - /* BN_FLG_EXP_CONSTTIME only supported by BN_mod_exp_mont() */ + /* BN_FLG_CONSTTIME only supported by BN_mod_exp_mont() */ BNerr(BN_F_BN_MOD_EXP_SIMPLE,ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED); return -1; } @@ -893,30 +897,30 @@ int BN_mod_exp_simple(BIGNUM *r, } BN_CTX_start(ctx); - if ((d = BN_CTX_get(ctx)) == NULL) goto err; + d = BN_CTX_get(ctx); + val[0] = BN_CTX_get(ctx); + if(!d || !val[0]) goto err; - BN_init(&(val[0])); - ts=1; - if (!BN_nnmod(&(val[0]),a,m,ctx)) goto err; /* 1 */ - if (BN_is_zero(&(val[0]))) + if (!BN_nnmod(val[0],a,m,ctx)) goto err; /* 1 */ + if (BN_is_zero(val[0])) { - ret = BN_zero(r); + BN_zero(r); + ret = 1; goto err; } window = BN_window_bits_for_exponent_size(bits); if (window > 1) { - if (!BN_mod_mul(d,&(val[0]),&(val[0]),m,ctx)) + if (!BN_mod_mul(d,val[0],val[0],m,ctx)) goto err; /* 2 */ j=1<<(window-1); for (i=1; i>1]),m,ctx)) + if (!BN_mod_mul(r,r,val[wvalue>>1],m,ctx)) goto err; /* move the 'window' down further */ @@ -980,8 +984,7 @@ int BN_mod_exp_simple(BIGNUM *r, ret=1; err: BN_CTX_end(ctx); - for (i=0; ineg || BN_ucmp(a1,m) >= 0) { - if (!BN_mod(&(val1[0]),a1,m,ctx)) + if (!BN_mod(val1[0],a1,m,ctx)) goto err; - a_mod_m = &(val1[0]); + a_mod_m = val1[0]; } else a_mod_m = a1; if (BN_is_zero(a_mod_m)) { - ret = BN_zero(rr); + BN_zero(rr); + ret = 1; goto err; } - if (!BN_to_montgomery(&(val1[0]),a_mod_m,mont,ctx)) goto err; + if (!BN_to_montgomery(val1[0],a_mod_m,mont,ctx)) goto err; if (window1 > 1) { - if (!BN_mod_mul_montgomery(d,&(val1[0]),&(val1[0]),mont,ctx)) goto err; + if (!BN_mod_mul_montgomery(d,val1[0],val1[0],mont,ctx)) goto err; j=1<<(window1-1); for (i=1; ineg || BN_ucmp(a2,m) >= 0) { - if (!BN_mod(&(val2[0]),a2,m,ctx)) + if (!BN_mod(val2[0],a2,m,ctx)) goto err; - a_mod_m = &(val2[0]); + a_mod_m = val2[0]; } else a_mod_m = a2; if (BN_is_zero(a_mod_m)) { - ret = BN_zero(rr); + BN_zero(rr); + ret = 1; goto err; } - if (!BN_to_montgomery(&(val2[0]),a_mod_m,mont,ctx)) goto err; + if (!BN_to_montgomery(val2[0],a_mod_m,mont,ctx)) goto err; if (window2 > 1) { - if (!BN_mod_mul_montgomery(d,&(val2[0]),&(val2[0]),mont,ctx)) goto err; + if (!BN_mod_mul_montgomery(d,val2[0],val2[0],mont,ctx)) goto err; j=1<<(window2-1); for (i=1; i>1]),mont,ctx)) + if (!BN_mod_mul_montgomery(r,r,val1[wvalue1>>1],mont,ctx)) goto err; wvalue1 = 0; r_is_one = 0; @@ -294,7 +295,7 @@ int BN_mod_exp2_mont(BIGNUM *rr, const BIGNUM *a1, const BIGNUM *p1, if (wvalue2 && b == wpos2) { /* wvalue2 is odd and < 2^window2 */ - if (!BN_mod_mul_montgomery(r,r,&(val2[wvalue2>>1]),mont,ctx)) + if (!BN_mod_mul_montgomery(r,r,val2[wvalue2>>1],mont,ctx)) goto err; wvalue2 = 0; r_is_one = 0; @@ -305,9 +306,6 @@ int BN_mod_exp2_mont(BIGNUM *rr, const BIGNUM *a1, const BIGNUM *p1, err: if ((in_mont == NULL) && (mont != NULL)) BN_MONT_CTX_free(mont); BN_CTX_end(ctx); - for (i=0; ineg = 0; + + if (B->neg || (BN_ucmp(B, A) >= 0)) + { + /* Turn BN_FLG_CONSTTIME flag on, so that when BN_div is invoked, + * BN_div_no_branch will be called eventually. + */ + pB = &local_B; + BN_with_flags(pB, B, BN_FLG_CONSTTIME); + if (!BN_nnmod(B, pB, A, ctx)) goto err; + } + sign = -1; + /* From B = a mod |n|, A = |n| it follows that + * + * 0 <= B < A, + * -sign*X*a == B (mod |n|), + * sign*Y*a == A (mod |n|). + */ + + while (!BN_is_zero(B)) + { + BIGNUM *tmp; + + /* + * 0 < B < A, + * (*) -sign*X*a == B (mod |n|), + * sign*Y*a == A (mod |n|) + */ + + /* Turn BN_FLG_CONSTTIME flag on, so that when BN_div is invoked, + * BN_div_no_branch will be called eventually. + */ + pA = &local_A; + BN_with_flags(pA, A, BN_FLG_CONSTTIME); + + /* (D, M) := (A/B, A%B) ... */ + if (!BN_div(D,M,pA,B,ctx)) goto err; + + /* Now + * A = D*B + M; + * thus we have + * (**) sign*Y*a == D*B + M (mod |n|). + */ + + tmp=A; /* keep the BIGNUM object, the value does not matter */ + + /* (A, B) := (B, A mod B) ... */ + A=B; + B=M; + /* ... so we have 0 <= B < A again */ + + /* Since the former M is now B and the former B is now A, + * (**) translates into + * sign*Y*a == D*A + B (mod |n|), + * i.e. + * sign*Y*a - D*A == B (mod |n|). + * Similarly, (*) translates into + * -sign*X*a == A (mod |n|). + * + * Thus, + * sign*Y*a + D*sign*X*a == B (mod |n|), + * i.e. + * sign*(Y + D*X)*a == B (mod |n|). + * + * So if we set (X, Y, sign) := (Y + D*X, X, -sign), we arrive back at + * -sign*X*a == B (mod |n|), + * sign*Y*a == A (mod |n|). + * Note that X and Y stay non-negative all the time. + */ + + if (!BN_mul(tmp,D,X,ctx)) goto err; + if (!BN_add(tmp,tmp,Y)) goto err; + + M=Y; /* keep the BIGNUM object, the value does not matter */ + Y=X; + X=tmp; + sign = -sign; + } + + /* + * The while loop (Euclid's algorithm) ends when + * A == gcd(a,n); + * we have + * sign*Y*a == A (mod |n|), + * where Y is non-negative. + */ + + if (sign < 0) + { + if (!BN_sub(Y,n,Y)) goto err; + } + /* Now Y*a == A (mod |n|). */ + + if (BN_is_one(A)) + { + /* Y*a == 1 (mod |n|) */ + if (!Y->neg && BN_ucmp(Y,n) < 0) + { + if (!BN_copy(R,Y)) goto err; + } + else + { + if (!BN_nnmod(R,Y,n,ctx)) goto err; + } + } + else + { + BNerr(BN_F_BN_MOD_INVERSE_NO_BRANCH,BN_R_NO_INVERSE); + goto err; + } + ret=R; +err: + if ((ret == NULL) && (in == NULL)) BN_free(R); + BN_CTX_end(ctx); + bn_check_top(ret); return(ret); } diff --git a/src/lib/libcrypto/bn/bn_kron.c b/src/lib/libcrypto/bn/bn_kron.c index 49f75594ae..740359b752 100644 --- a/src/lib/libcrypto/bn/bn_kron.c +++ b/src/lib/libcrypto/bn/bn_kron.c @@ -53,9 +53,9 @@ * */ +#include "cryptlib.h" #include "bn_lcl.h" - /* least significant word */ #define BN_lsw(n) (((n)->top == 0) ? (BN_ULONG) 0 : (n)->d[0]) @@ -74,6 +74,9 @@ int BN_kronecker(const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx) */ static const int tab[8] = {0, 1, 0, -1, 0, -1, 0, 1}; + bn_check_top(a); + bn_check_top(b); + BN_CTX_start(ctx); A = BN_CTX_get(ctx); B = BN_CTX_get(ctx); @@ -172,8 +175,7 @@ int BN_kronecker(const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx) tmp = A; A = B; B = tmp; tmp->neg = 0; } - - end: +end: BN_CTX_end(ctx); if (err) return -2; diff --git a/src/lib/libcrypto/bn/bn_lcl.h b/src/lib/libcrypto/bn/bn_lcl.h index a84998f2bd..27ac4397a1 100644 --- a/src/lib/libcrypto/bn/bn_lcl.h +++ b/src/lib/libcrypto/bn/bn_lcl.h @@ -119,20 +119,6 @@ extern "C" { #endif -/* Used for temp variables */ -#define BN_CTX_NUM 32 -#define BN_CTX_NUM_POS 12 -struct bignum_ctx - { - int tos; - BIGNUM bn[BN_CTX_NUM]; - int flags; - int depth; - int pos[BN_CTX_NUM_POS]; - int too_many; - } /* BN_CTX */; - - /* * BN_window_bits_for_exponent_size -- macro for sliding window mod_exp functions * @@ -284,6 +270,15 @@ struct bignum_ctx : "a"(a),"g"(b) \ : "cc"); # endif +# elif (defined(_M_AMD64) || defined(_M_X64)) && defined(SIXTY_FOUR_BIT) +# if defined(_MSC_VER) && _MSC_VER>=1400 + unsigned __int64 __umulh (unsigned __int64 a,unsigned __int64 b); + unsigned __int64 _umul128 (unsigned __int64 a,unsigned __int64 b, + unsigned __int64 *h); +# pragma intrinsic(__umulh,_umul128) +# define BN_UMULT_HIGH(a,b) __umulh((a),(b)) +# define BN_UMULT_LOHI(low,high,a,b) ((low)=_umul128((a),(b),&(high))) +# endif # endif /* cpu */ #endif /* OPENSSL_NO_ASM */ @@ -293,44 +288,17 @@ struct bignum_ctx #define Lw(t) (((BN_ULONG)(t))&BN_MASK2) #define Hw(t) (((BN_ULONG)((t)>>BN_BITS2))&BN_MASK2) -/* This is used for internal error checking and is not normally used */ -#ifdef BN_DEBUG -# include -# define bn_check_top(a) assert ((a)->top >= 0 && (a)->top <= (a)->dmax); -#else -# define bn_check_top(a) -#endif - -/* This macro is to add extra stuff for development checking */ -#ifdef BN_DEBUG -#define bn_set_max(r) ((r)->max=(r)->top,BN_set_flags((r),BN_FLG_STATIC_DATA)) -#else -#define bn_set_max(r) -#endif - -/* These macros are used to 'take' a section of a bignum for read only use */ -#define bn_set_low(r,a,n) \ - { \ - (r)->top=((a)->top > (n))?(n):(a)->top; \ - (r)->d=(a)->d; \ - (r)->neg=(a)->neg; \ - (r)->flags|=BN_FLG_STATIC_DATA; \ - bn_set_max(r); \ - } - -#define bn_set_high(r,a,n) \ +#ifdef BN_DEBUG_RAND +#define bn_clear_top2max(a) \ { \ - if ((a)->top > (n)) \ - { \ - (r)->top=(a)->top-n; \ - (r)->d= &((a)->d[n]); \ - } \ - else \ - (r)->top=0; \ - (r)->neg=(a)->neg; \ - (r)->flags|=BN_FLG_STATIC_DATA; \ - bn_set_max(r); \ + int ind = (a)->dmax - (a)->top; \ + BN_ULONG *ftl = &(a)->d[(a)->top-1]; \ + for (; ind != 0; ind--) \ + *(++ftl) = 0x0; \ } +#else +#define bn_clear_top2max(a) +#endif #ifdef BN_LLONG #define mul_add(r,a,w,c) { \ @@ -354,6 +322,33 @@ struct bignum_ctx (r1)=Hw(t); \ } +#elif defined(BN_UMULT_LOHI) +#define mul_add(r,a,w,c) { \ + BN_ULONG high,low,ret,tmp=(a); \ + ret = (r); \ + BN_UMULT_LOHI(low,high,w,tmp); \ + ret += (c); \ + (c) = (ret<(c))?1:0; \ + (c) += high; \ + ret += low; \ + (c) += (ret= 0) { - if (mult > (sizeof(int)*8)-1) + if (mult > (int)(sizeof(int)*8)-1) mult=sizeof(int)*8-1; bn_limit_bits=mult; bn_limit_num=1<= 0) { - if (high > (sizeof(int)*8)-1) + if (high > (int)(sizeof(int)*8)-1) high=sizeof(int)*8-1; bn_limit_bits_high=high; bn_limit_num_high=1<= 0) { - if (low > (sizeof(int)*8)-1) + if (low > (int)(sizeof(int)*8)-1) low=sizeof(int)*8-1; bn_limit_bits_low=low; bn_limit_num_low=1<= 0) { - if (mont > (sizeof(int)*8)-1) + if (mont > (int)(sizeof(int)*8)-1) mont=sizeof(int)*8-1; bn_limit_bits_mont=mont; bn_limit_num_mont=1<top - 1; bn_check_top(a); - if (a->top == 0) return(0); - l=a->d[a->top-1]; - assert(l != 0); - i=(a->top-1)*BN_BITS2; - return(i+BN_num_bits_word(l)); + if (BN_is_zero(a)) return 0; + return ((i*BN_BITS2) + BN_num_bits_word(a->d[i])); } void BN_clear_free(BIGNUM *a) @@ -261,6 +259,7 @@ void BN_clear_free(BIGNUM *a) int i; if (a == NULL) return; + bn_check_top(a); if (a->d != NULL) { OPENSSL_cleanse(a->d,a->dmax*sizeof(a->d[0])); @@ -276,16 +275,24 @@ void BN_clear_free(BIGNUM *a) void BN_free(BIGNUM *a) { if (a == NULL) return; + bn_check_top(a); if ((a->d != NULL) && !(BN_get_flags(a,BN_FLG_STATIC_DATA))) OPENSSL_free(a->d); - a->flags|=BN_FLG_FREE; /* REMOVE? */ if (a->flags & BN_FLG_MALLOCED) OPENSSL_free(a); + else + { +#ifndef OPENSSL_NO_DEPRECATED + a->flags|=BN_FLG_FREE; +#endif + a->d = NULL; + } } void BN_init(BIGNUM *a) { memset(a,0,sizeof(BIGNUM)); + bn_check_top(a); } BIGNUM *BN_new(void) @@ -302,6 +309,7 @@ BIGNUM *BN_new(void) ret->neg=0; ret->dmax=0; ret->d=NULL; + bn_check_top(ret); return(ret); } @@ -313,19 +321,19 @@ static BN_ULONG *bn_expand_internal(const BIGNUM *b, int words) const BN_ULONG *B; int i; + bn_check_top(b); + if (words > (INT_MAX/(4*BN_BITS2))) { BNerr(BN_F_BN_EXPAND_INTERNAL,BN_R_BIGNUM_TOO_LONG); return NULL; } - - bn_check_top(b); if (BN_get_flags(b,BN_FLG_STATIC_DATA)) { BNerr(BN_F_BN_EXPAND_INTERNAL,BN_R_EXPAND_ON_STATIC_BIGNUM_DATA); return(NULL); } - a=A=(BN_ULONG *)OPENSSL_malloc(sizeof(BN_ULONG)*(words+1)); + a=A=(BN_ULONG *)OPENSSL_malloc(sizeof(BN_ULONG)*words); if (A == NULL) { BNerr(BN_F_BN_EXPAND_INTERNAL,ERR_R_MALLOC_FAILURE); @@ -363,19 +371,8 @@ static BN_ULONG *bn_expand_internal(const BIGNUM *b, int words) } } - /* Now need to zero any data between b->top and b->max */ - /* XXX Why? */ - - A= &(a[b->top]); - for (i=(words - b->top)>>3; i>0; i--,A+=8) - { - A[0]=0; A[1]=0; A[2]=0; A[3]=0; - A[4]=0; A[5]=0; A[6]=0; A[7]=0; - } - for (i=(words - b->top)&7; i>0; i--,A++) - A[0]=0; #else - memset(A,0,sizeof(BN_ULONG)*(words+1)); + memset(A,0,sizeof(BN_ULONG)*words); memcpy(A,b->d,sizeof(b->d[0])*b->top); #endif @@ -393,16 +390,19 @@ static BN_ULONG *bn_expand_internal(const BIGNUM *b, int words) * while bn_dup_expand() makes sure allocation is made only once. */ +#ifndef OPENSSL_NO_DEPRECATED BIGNUM *bn_dup_expand(const BIGNUM *b, int words) { BIGNUM *r = NULL; + bn_check_top(b); + /* This function does not work if * words <= b->dmax && top < words * because BN_dup() does not preserve 'dmax'! * (But bn_dup_expand() is not used anywhere yet.) */ - + if (words > b->dmax) { BN_ULONG *a = bn_expand_internal(b, words); @@ -431,48 +431,67 @@ BIGNUM *bn_dup_expand(const BIGNUM *b, int words) r = BN_dup(b); } + bn_check_top(r); return r; } +#endif /* This is an internal function that should not be used in applications. - * It ensures that 'b' has enough room for a 'words' word number number. + * It ensures that 'b' has enough room for a 'words' word number + * and initialises any unused part of b->d with leading zeros. * It is mostly used by the various BIGNUM routines. If there is an error, * NULL is returned. If not, 'b' is returned. */ BIGNUM *bn_expand2(BIGNUM *b, int words) { + bn_check_top(b); + if (words > b->dmax) { BN_ULONG *a = bn_expand_internal(b, words); + if(!a) return NULL; + if(b->d) OPENSSL_free(b->d); + b->d=a; + b->dmax=words; + } - if (a) +/* None of this should be necessary because of what b->top means! */ +#if 0 + /* NB: bn_wexpand() calls this only if the BIGNUM really has to grow */ + if (b->top < b->dmax) + { + int i; + BN_ULONG *A = &(b->d[b->top]); + for (i=(b->dmax - b->top)>>3; i>0; i--,A+=8) { - if (b->d) - OPENSSL_free(b->d); - b->d=a; - b->dmax=words; + A[0]=0; A[1]=0; A[2]=0; A[3]=0; + A[4]=0; A[5]=0; A[6]=0; A[7]=0; } - else - b = NULL; + for (i=(b->dmax - b->top)&7; i>0; i--,A++) + A[0]=0; + assert(A == &(b->d[b->dmax])); } +#endif + bn_check_top(b); return b; } BIGNUM *BN_dup(const BIGNUM *a) { - BIGNUM *r, *t; + BIGNUM *t; if (a == NULL) return NULL; - bn_check_top(a); t = BN_new(); - if (t == NULL) return(NULL); - r = BN_copy(t, a); - /* now r == t || r == NULL */ - if (r == NULL) + if (t == NULL) return NULL; + if(!BN_copy(t, a)) + { BN_free(t); - return r; + return NULL; + } + bn_check_top(t); + return t; } BIGNUM *BN_copy(BIGNUM *a, const BIGNUM *b) @@ -506,11 +525,9 @@ BIGNUM *BN_copy(BIGNUM *a, const BIGNUM *b) memcpy(a->d,b->d,sizeof(b->d[0])*b->top); #endif -/* memset(&(a->d[b->top]),0,sizeof(a->d[0])*(a->max-b->top));*/ a->top=b->top; - if ((a->top == 0) && (a->d != NULL)) - a->d[0]=0; a->neg=b->neg; + bn_check_top(a); return(a); } @@ -520,6 +537,9 @@ void BN_swap(BIGNUM *a, BIGNUM *b) BN_ULONG *tmp_d; int tmp_top, tmp_dmax, tmp_neg; + bn_check_top(a); + bn_check_top(b); + flags_old_a = a->flags; flags_old_b = b->flags; @@ -540,11 +560,13 @@ void BN_swap(BIGNUM *a, BIGNUM *b) a->flags = (flags_old_a & BN_FLG_MALLOCED) | (flags_old_b & BN_FLG_STATIC_DATA); b->flags = (flags_old_b & BN_FLG_MALLOCED) | (flags_old_a & BN_FLG_STATIC_DATA); + bn_check_top(a); + bn_check_top(b); } - void BN_clear(BIGNUM *a) { + bn_check_top(a); if (a->d != NULL) memset(a->d,0,a->dmax*sizeof(a->d[0])); a->top=0; @@ -553,49 +575,22 @@ void BN_clear(BIGNUM *a) BN_ULONG BN_get_word(const BIGNUM *a) { - int i,n; - BN_ULONG ret=0; - - n=BN_num_bytes(a); - if (n > sizeof(BN_ULONG)) - return(BN_MASK2); - for (i=a->top-1; i>=0; i--) - { -#ifndef SIXTY_FOUR_BIT /* the data item > unsigned long */ - ret<<=BN_BITS4; /* stops the compiler complaining */ - ret<<=BN_BITS4; -#else - ret=0; -#endif - ret|=a->d[i]; - } - return(ret); + if (a->top > 1) + return BN_MASK2; + else if (a->top == 1) + return a->d[0]; + /* a->top == 0 */ + return 0; } int BN_set_word(BIGNUM *a, BN_ULONG w) { - int i,n; - if (bn_expand(a,sizeof(BN_ULONG)*8) == NULL) return(0); - - n=sizeof(BN_ULONG)/BN_BYTES; - a->neg=0; - a->top=0; - a->d[0]=(BN_ULONG)w&BN_MASK2; - if (a->d[0] != 0) a->top=1; - for (i=1; i>=BN_BITS2 so compilers don't complain - * on builds where sizeof(long) == BN_TYPES */ -#ifndef SIXTY_FOUR_BIT /* the data item > unsigned long */ - w>>=BN_BITS4; - w>>=BN_BITS4; -#else - w=0; -#endif - a->d[i]=(BN_ULONG)w&BN_MASK2; - if (a->d[i] != 0) a->top=i+1; - } + bn_check_top(a); + if (bn_expand(a,(int)sizeof(BN_ULONG)*8) == NULL) return(0); + a->neg = 0; + a->d[0] = w; + a->top = (w ? 1 : 0); + bn_check_top(a); return(1); } @@ -604,9 +599,12 @@ BIGNUM *BN_bin2bn(const unsigned char *s, int len, BIGNUM *ret) unsigned int i,m; unsigned int n; BN_ULONG l; + BIGNUM *bn = NULL; - if (ret == NULL) ret=BN_new(); + if (ret == NULL) + ret = bn = BN_new(); if (ret == NULL) return(NULL); + bn_check_top(ret); l=0; n=len; if (n == 0) @@ -614,13 +612,16 @@ BIGNUM *BN_bin2bn(const unsigned char *s, int len, BIGNUM *ret) ret->top=0; return(ret); } - if (bn_expand(ret,(int)(n+2)*8) == NULL) - return(NULL); i=((n-1)/BN_BYTES)+1; m=((n-1)%(BN_BYTES)); + if (bn_wexpand(ret, (int)i) == NULL) + { + if (bn) BN_free(bn); + return NULL; + } ret->top=i; ret->neg=0; - while (n-- > 0) + while (n--) { l=(l<<8L)| *(s++); if (m-- == 0) @@ -632,7 +633,7 @@ BIGNUM *BN_bin2bn(const unsigned char *s, int len, BIGNUM *ret) } /* need to call this due to clear byte at top if avoiding * having the top bit set (-ve number) */ - bn_fix_top(ret); + bn_correct_top(ret); return(ret); } @@ -642,8 +643,9 @@ int BN_bn2bin(const BIGNUM *a, unsigned char *to) int n,i; BN_ULONG l; + bn_check_top(a); n=i=BN_num_bytes(a); - while (i-- > 0) + while (i--) { l=a->d[i/BN_BYTES]; *(to++)=(unsigned char)(l>>(8*(i%BN_BYTES)))&0xff; @@ -668,7 +670,7 @@ int BN_ucmp(const BIGNUM *a, const BIGNUM *b) t1= ap[i]; t2= bp[i]; if (t1 != t2) - return(t1 > t2?1:-1); + return((t1 > t2) ? 1 : -1); } return(0); } @@ -718,6 +720,9 @@ int BN_set_bit(BIGNUM *a, int n) { int i,j,k; + if (n < 0) + return 0; + i=n/BN_BITS2; j=n%BN_BITS2; if (a->top <= i) @@ -729,6 +734,7 @@ int BN_set_bit(BIGNUM *a, int n) } a->d[i]|=(((BN_ULONG)1)<top <= i) return(0); a->d[i]&=(~(((BN_ULONG)1)<top <= i) return(0); - return((a->d[i]&(((BN_ULONG)1)<top <= i) return 0; + return(((a->d[i])>>j)&((BN_ULONG)1)); } int BN_mask_bits(BIGNUM *a, int n) { int b,w; + bn_check_top(a); + if (n < 0) return 0; + w=n/BN_BITS2; b=n%BN_BITS2; - if (w >= a->top) return(0); + if (w >= a->top) return 0; if (b == 0) a->top=w; else @@ -770,10 +783,18 @@ int BN_mask_bits(BIGNUM *a, int n) a->top=w+1; a->d[w]&= ~(BN_MASK2<neg = 1; + else + a->neg = 0; + } + int bn_cmp_words(const BN_ULONG *a, const BN_ULONG *b, int n) { int i; diff --git a/src/lib/libcrypto/bn/bn_mod.c b/src/lib/libcrypto/bn/bn_mod.c index 5cf82480d7..77d6ddb91a 100644 --- a/src/lib/libcrypto/bn/bn_mod.c +++ b/src/lib/libcrypto/bn/bn_mod.c @@ -149,7 +149,7 @@ int BN_mod_add(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m, BN_ * and less than m */ int BN_mod_add_quick(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m) { - if (!BN_add(r, a, b)) return 0; + if (!BN_uadd(r, a, b)) return 0; if (BN_ucmp(r, m) >= 0) return BN_usub(r, r, m); return 1; @@ -192,6 +192,7 @@ int BN_mod_mul(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m, else { if (!BN_mul(t,a,b,ctx)) goto err; } if (!BN_nnmod(r,t,m,ctx)) goto err; + bn_check_top(r); ret=1; err: BN_CTX_end(ctx); @@ -210,6 +211,7 @@ int BN_mod_sqr(BIGNUM *r, const BIGNUM *a, const BIGNUM *m, BN_CTX *ctx) int BN_mod_lshift1(BIGNUM *r, const BIGNUM *a, const BIGNUM *m, BN_CTX *ctx) { if (!BN_lshift1(r, a)) return 0; + bn_check_top(r); return BN_nnmod(r, r, m, ctx); } @@ -219,6 +221,7 @@ int BN_mod_lshift1(BIGNUM *r, const BIGNUM *a, const BIGNUM *m, BN_CTX *ctx) int BN_mod_lshift1_quick(BIGNUM *r, const BIGNUM *a, const BIGNUM *m) { if (!BN_lshift1(r, a)) return 0; + bn_check_top(r); if (BN_cmp(r, m) >= 0) return BN_sub(r, r, m); return 1; @@ -240,6 +243,7 @@ int BN_mod_lshift(BIGNUM *r, const BIGNUM *a, int n, const BIGNUM *m, BN_CTX *ct } ret = BN_mod_lshift_quick(r, r, n, (abs_m ? abs_m : m)); + bn_check_top(r); if (abs_m) BN_free(abs_m); @@ -291,6 +295,7 @@ int BN_mod_lshift_quick(BIGNUM *r, const BIGNUM *a, int n, const BIGNUM *m) if (!BN_sub(r, r, m)) return 0; } } + bn_check_top(r); return 1; } diff --git a/src/lib/libcrypto/bn/bn_mont.c b/src/lib/libcrypto/bn/bn_mont.c index 726d5f2b1b..4799b152dd 100644 --- a/src/lib/libcrypto/bn/bn_mont.c +++ b/src/lib/libcrypto/bn/bn_mont.c @@ -55,6 +55,59 @@ * copied and put under another distribution licence * [including the GNU Public Licence.] */ +/* ==================================================================== + * Copyright (c) 1998-2006 The OpenSSL Project. All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in + * the documentation and/or other materials provided with the + * distribution. + * + * 3. All advertising materials mentioning features or use of this + * software must display the following acknowledgment: + * "This product includes software developed by the OpenSSL Project + * for use in the OpenSSL Toolkit. (http://www.openssl.org/)" + * + * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to + * endorse or promote products derived from this software without + * prior written permission. For written permission, please contact + * openssl-core@openssl.org. + * + * 5. Products derived from this software may not be called "OpenSSL" + * nor may "OpenSSL" appear in their names without prior written + * permission of the OpenSSL Project. + * + * 6. Redistributions of any form whatsoever must retain the following + * acknowledgment: + * "This product includes software developed by the OpenSSL Project + * for use in the OpenSSL Toolkit (http://www.openssl.org/)" + * + * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY + * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR + * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR + * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; + * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, + * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED + * OF THE POSSIBILITY OF SUCH DAMAGE. + * ==================================================================== + * + * This product includes cryptographic software written by Eric Young + * (eay@cryptsoft.com). This product includes software written by Tim + * Hudson (tjh@cryptsoft.com). + * + */ /* * Details about Montgomery multiplication algorithms can be found at @@ -69,11 +122,50 @@ #define MONT_WORD /* use the faster word-based algorithm */ +#if defined(MONT_WORD) && defined(OPENSSL_BN_ASM_MONT) && (BN_BITS2<=32) +/* This condition means we have a specific non-default build: + * In the 0.9.8 branch, OPENSSL_BN_ASM_MONT is normally not set for any + * BN_BITS2<=32 platform; an explicit "enable-montasm" is required. + * I.e., if we are here, the user intentionally deviates from the + * normal stable build to get better Montgomery performance from + * the 0.9.9-dev backport. + * + * In this case only, we also enable BN_from_montgomery_word() + * (another non-stable feature from 0.9.9-dev). + */ +#define MONT_FROM_WORD___NON_DEFAULT_0_9_8_BUILD +#endif + +#ifdef MONT_FROM_WORD___NON_DEFAULT_0_9_8_BUILD +static int BN_from_montgomery_word(BIGNUM *ret, BIGNUM *r, BN_MONT_CTX *mont); +#endif + + + int BN_mod_mul_montgomery(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, BN_MONT_CTX *mont, BN_CTX *ctx) { BIGNUM *tmp; int ret=0; +#if defined(OPENSSL_BN_ASM_MONT) && defined(MONT_WORD) + int num = mont->N.top; + + if (num>1 && a->top==num && b->top==num) + { + if (bn_wexpand(r,num) == NULL) return(0); +#if 0 /* for OpenSSL 0.9.9 mont->n0 */ + if (bn_mul_mont(r->d,a->d,b->d,mont->N.d,mont->n0,num)) +#else + if (bn_mul_mont(r->d,a->d,b->d,mont->N.d,&mont->n0,num)) +#endif + { + r->neg = a->neg^b->neg; + r->top = num; + bn_correct_top(r); + return(1); + } + } +#endif BN_CTX_start(ctx); tmp = BN_CTX_get(ctx); @@ -89,13 +181,162 @@ int BN_mod_mul_montgomery(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, if (!BN_mul(tmp,a,b,ctx)) goto err; } /* reduce from aRR to aR */ +#ifdef MONT_FROM_WORD___NON_DEFAULT_0_9_8_BUILD + if (!BN_from_montgomery_word(r,tmp,mont)) goto err; +#else if (!BN_from_montgomery(r,tmp,mont,ctx)) goto err; +#endif + bn_check_top(r); ret=1; err: BN_CTX_end(ctx); return(ret); } +#ifdef MONT_FROM_WORD___NON_DEFAULT_0_9_8_BUILD +static int BN_from_montgomery_word(BIGNUM *ret, BIGNUM *r, BN_MONT_CTX *mont) + { + BIGNUM *n; + BN_ULONG *ap,*np,*rp,n0,v,*nrp; + int al,nl,max,i,x,ri; + + n= &(mont->N); + /* mont->ri is the size of mont->N in bits (rounded up + to the word size) */ + al=ri=mont->ri/BN_BITS2; + + nl=n->top; + if ((al == 0) || (nl == 0)) { ret->top=0; return(1); } + + max=(nl+al+1); /* allow for overflow (no?) XXX */ + if (bn_wexpand(r,max) == NULL) return(0); + + r->neg^=n->neg; + np=n->d; + rp=r->d; + nrp= &(r->d[nl]); + + /* clear the top words of T */ + for (i=r->top; id[i]=0; + + r->top=max; +#if 0 /* for OpenSSL 0.9.9 mont->n0 */ + n0=mont->n0[0]; +#else + n0=mont->n0; +#endif + +#ifdef BN_COUNT + fprintf(stderr,"word BN_from_montgomery_word %d * %d\n",nl,nl); +#endif + for (i=0; i= v) + continue; + else + { + if (((++nrp[0])&BN_MASK2) != 0) continue; + if (((++nrp[1])&BN_MASK2) != 0) continue; + for (x=2; (((++nrp[x])&BN_MASK2) == 0); x++) ; + } + } + bn_correct_top(r); + + /* mont->ri will be a multiple of the word size and below code + * is kind of BN_rshift(ret,r,mont->ri) equivalent */ + if (r->top <= ri) + { + ret->top=0; + return(1); + } + al=r->top-ri; + + if (bn_wexpand(ret,ri) == NULL) return(0); + x=0-(((al-ri)>>(sizeof(al)*8-1))&1); + ret->top=x=(ri&~x)|(al&x); /* min(ri,al) */ + ret->neg=r->neg; + + rp=ret->d; + ap=&(r->d[ri]); + + { + size_t m1,m2; + + v=bn_sub_words(rp,ap,np,ri); + /* this ----------------^^ works even in alri) nrp=rp; else nrp=ap; */ + /* in other words if subtraction result is real, then + * trick unconditional memcpy below to perform in-place + * "refresh" instead of actual copy. */ + m1=0-(size_t)(((al-ri)>>(sizeof(al)*8-1))&1); /* al>(sizeof(al)*8-1))&1); /* al>ri */ + m1|=m2; /* (al!=ri) */ + m1|=(0-(size_t)v); /* (al!=ri || v) */ + m1&=~m2; /* (al!=ri || v) && !al>ri */ + nrp=(BN_ULONG *)(((size_t)rp&~m1)|((size_t)ap&m1)); + } + + /* 'iri will be a multiple of the word size and below code * is kind of BN_rshift(ret,r,mont->ri) equivalent */ @@ -230,6 +471,8 @@ int BN_from_montgomery(BIGNUM *ret, const BIGNUM *a, BN_MONT_CTX *mont, } for (ri+=4; itop=al; @@ -281,10 +524,12 @@ int BN_from_montgomery(BIGNUM *ret, const BIGNUM *a, BN_MONT_CTX *mont, } #endif retn=1; + bn_check_top(ret); err: BN_CTX_end(ctx); return(retn); } +#endif /* MONT_FROM_WORD___NON_DEFAULT_0_9_8_BUILD */ BN_MONT_CTX *BN_MONT_CTX_new(void) { @@ -304,6 +549,11 @@ void BN_MONT_CTX_init(BN_MONT_CTX *ctx) BN_init(&(ctx->RR)); BN_init(&(ctx->N)); BN_init(&(ctx->Ni)); +#if 0 /* for OpenSSL 0.9.9 mont->n0 */ + ctx->n0[0] = ctx->n0[1] = 0; +#else + ctx->n0 = 0; +#endif ctx->flags=0; } @@ -321,9 +571,11 @@ void BN_MONT_CTX_free(BN_MONT_CTX *mont) int BN_MONT_CTX_set(BN_MONT_CTX *mont, const BIGNUM *mod, BN_CTX *ctx) { - BIGNUM Ri,*R; + int ret = 0; + BIGNUM *Ri,*R; - BN_init(&Ri); + BN_CTX_start(ctx); + if((Ri = BN_CTX_get(ctx)) == NULL) goto err; R= &(mont->RR); /* grab RR as a temp */ if (!BN_copy(&(mont->N),mod)) goto err; /* Set N */ mont->N.neg = 0; @@ -334,57 +586,99 @@ int BN_MONT_CTX_set(BN_MONT_CTX *mont, const BIGNUM *mod, BN_CTX *ctx) BN_ULONG buf[2]; mont->ri=(BN_num_bits(mod)+(BN_BITS2-1))/BN_BITS2*BN_BITS2; - if (!(BN_zero(R))) goto err; + BN_zero(R); +#if 0 /* for OpenSSL 0.9.9 mont->n0, would be "#if defined(OPENSSL_BN_ASM_MONT) && (BN_BITS2<=32)", + only certain BN_BITS2<=32 platforms actually need this */ + if (!(BN_set_bit(R,2*BN_BITS2))) goto err; /* R */ +#else if (!(BN_set_bit(R,BN_BITS2))) goto err; /* R */ +#endif buf[0]=mod->d[0]; /* tmod = N mod word size */ buf[1]=0; + + BN_init(&tmod); tmod.d=buf; - tmod.top=1; + tmod.top = buf[0] != 0 ? 1 : 0; tmod.dmax=2; tmod.neg=0; + +#if 0 /* for OpenSSL 0.9.9 mont->n0, would be "#if defined(OPENSSL_BN_ASM_MONT) && (BN_BITS2<=32)"; + only certain BN_BITS2<=32 platforms actually need this */ + tmod.top=0; + if ((buf[0] = mod->d[0])) tmod.top=1; + if ((buf[1] = mod->top>1 ? mod->d[1] : 0)) tmod.top=2; + + if ((BN_mod_inverse(Ri,R,&tmod,ctx)) == NULL) + goto err; + if (!BN_lshift(Ri,Ri,2*BN_BITS2)) goto err; /* R*Ri */ + if (!BN_is_zero(Ri)) + { + if (!BN_sub_word(Ri,1)) goto err; + } + else /* if N mod word size == 1 */ + { + if (bn_expand(Ri,(int)sizeof(BN_ULONG)*2) == NULL) + goto err; + /* Ri-- (mod double word size) */ + Ri->neg=0; + Ri->d[0]=BN_MASK2; + Ri->d[1]=BN_MASK2; + Ri->top=2; + } + if (!BN_div(Ri,NULL,Ri,&tmod,ctx)) goto err; + /* Ni = (R*Ri-1)/N, + * keep only couple of least significant words: */ + mont->n0[0] = (Ri->top > 0) ? Ri->d[0] : 0; + mont->n0[1] = (Ri->top > 1) ? Ri->d[1] : 0; +#else /* Ri = R^-1 mod N*/ - if ((BN_mod_inverse(&Ri,R,&tmod,ctx)) == NULL) + if ((BN_mod_inverse(Ri,R,&tmod,ctx)) == NULL) goto err; - if (!BN_lshift(&Ri,&Ri,BN_BITS2)) goto err; /* R*Ri */ - if (!BN_is_zero(&Ri)) + if (!BN_lshift(Ri,Ri,BN_BITS2)) goto err; /* R*Ri */ + if (!BN_is_zero(Ri)) { - if (!BN_sub_word(&Ri,1)) goto err; + if (!BN_sub_word(Ri,1)) goto err; } else /* if N mod word size == 1 */ { - if (!BN_set_word(&Ri,BN_MASK2)) goto err; /* Ri-- (mod word size) */ + if (!BN_set_word(Ri,BN_MASK2)) goto err; /* Ri-- (mod word size) */ } - if (!BN_div(&Ri,NULL,&Ri,&tmod,ctx)) goto err; + if (!BN_div(Ri,NULL,Ri,&tmod,ctx)) goto err; /* Ni = (R*Ri-1)/N, * keep only least significant word: */ - mont->n0 = (Ri.top > 0) ? Ri.d[0] : 0; - BN_free(&Ri); +# if 0 /* for OpenSSL 0.9.9 mont->n0 */ + mont->n0[0] = (Ri->top > 0) ? Ri->d[0] : 0; + mont->n0[1] = 0; +# else + mont->n0 = (Ri->top > 0) ? Ri->d[0] : 0; +# endif +#endif } #else /* !MONT_WORD */ { /* bignum version */ mont->ri=BN_num_bits(&mont->N); - if (!BN_zero(R)) goto err; + BN_zero(R); if (!BN_set_bit(R,mont->ri)) goto err; /* R = 2^ri */ /* Ri = R^-1 mod N*/ - if ((BN_mod_inverse(&Ri,R,&mont->N,ctx)) == NULL) + if ((BN_mod_inverse(Ri,R,&mont->N,ctx)) == NULL) goto err; - if (!BN_lshift(&Ri,&Ri,mont->ri)) goto err; /* R*Ri */ - if (!BN_sub_word(&Ri,1)) goto err; + if (!BN_lshift(Ri,Ri,mont->ri)) goto err; /* R*Ri */ + if (!BN_sub_word(Ri,1)) goto err; /* Ni = (R*Ri-1) / N */ - if (!BN_div(&(mont->Ni),NULL,&Ri,&mont->N,ctx)) goto err; - BN_free(&Ri); + if (!BN_div(&(mont->Ni),NULL,Ri,&mont->N,ctx)) goto err; } #endif /* setup RR for conversions */ - if (!BN_zero(&(mont->RR))) goto err; + BN_zero(&(mont->RR)); if (!BN_set_bit(&(mont->RR),mont->ri*2)) goto err; if (!BN_mod(&(mont->RR),&(mont->RR),&(mont->N),ctx)) goto err; - return(1); + ret = 1; err: - return(0); + BN_CTX_end(ctx); + return ret; } BN_MONT_CTX *BN_MONT_CTX_copy(BN_MONT_CTX *to, BN_MONT_CTX *from) @@ -395,27 +689,44 @@ BN_MONT_CTX *BN_MONT_CTX_copy(BN_MONT_CTX *to, BN_MONT_CTX *from) if (!BN_copy(&(to->N),&(from->N))) return NULL; if (!BN_copy(&(to->Ni),&(from->Ni))) return NULL; to->ri=from->ri; +#if 0 /* for OpenSSL 0.9.9 mont->n0 */ + to->n0[0]=from->n0[0]; + to->n0[1]=from->n0[1]; +#else to->n0=from->n0; +#endif return(to); } BN_MONT_CTX *BN_MONT_CTX_set_locked(BN_MONT_CTX **pmont, int lock, const BIGNUM *mod, BN_CTX *ctx) { - if (*pmont) - return *pmont; - CRYPTO_w_lock(lock); + int got_write_lock = 0; + BN_MONT_CTX *ret; + + CRYPTO_r_lock(lock); if (!*pmont) { - *pmont = BN_MONT_CTX_new(); - if (*pmont && !BN_MONT_CTX_set(*pmont, mod, ctx)) + CRYPTO_r_unlock(lock); + CRYPTO_w_lock(lock); + got_write_lock = 1; + + if (!*pmont) { - BN_MONT_CTX_free(*pmont); - *pmont = NULL; + ret = BN_MONT_CTX_new(); + if (ret && !BN_MONT_CTX_set(ret, mod, ctx)) + BN_MONT_CTX_free(ret); + else + *pmont = ret; } } - CRYPTO_w_unlock(lock); - return *pmont; - } + + ret = *pmont; + + if (got_write_lock) + CRYPTO_w_unlock(lock); + else + CRYPTO_r_unlock(lock); - + return ret; + } diff --git a/src/lib/libcrypto/bn/bn_mpi.c b/src/lib/libcrypto/bn/bn_mpi.c index 05fa9d1e9a..a054d21aed 100644 --- a/src/lib/libcrypto/bn/bn_mpi.c +++ b/src/lib/libcrypto/bn/bn_mpi.c @@ -124,6 +124,7 @@ BIGNUM *BN_mpi2bn(const unsigned char *d, int n, BIGNUM *a) { BN_clear_bit(a,BN_num_bits(a)-1); } + bn_check_top(a); return(a); } diff --git a/src/lib/libcrypto/bn/bn_mul.c b/src/lib/libcrypto/bn/bn_mul.c index 3ae3822bc2..b848c8cc60 100644 --- a/src/lib/libcrypto/bn/bn_mul.c +++ b/src/lib/libcrypto/bn/bn_mul.c @@ -56,10 +56,325 @@ * [including the GNU Public Licence.] */ +#ifndef BN_DEBUG +# undef NDEBUG /* avoid conflicting definitions */ +# define NDEBUG +#endif + #include +#include #include "cryptlib.h" #include "bn_lcl.h" +#if defined(OPENSSL_NO_ASM) || !defined(OPENSSL_BN_ASM_PART_WORDS) +/* Here follows specialised variants of bn_add_words() and + bn_sub_words(). They have the property performing operations on + arrays of different sizes. The sizes of those arrays is expressed through + cl, which is the common length ( basicall, min(len(a),len(b)) ), and dl, + which is the delta between the two lengths, calculated as len(a)-len(b). + All lengths are the number of BN_ULONGs... For the operations that require + a result array as parameter, it must have the length cl+abs(dl). + These functions should probably end up in bn_asm.c as soon as there are + assembler counterparts for the systems that use assembler files. */ + +BN_ULONG bn_sub_part_words(BN_ULONG *r, + const BN_ULONG *a, const BN_ULONG *b, + int cl, int dl) + { + BN_ULONG c, t; + + assert(cl >= 0); + c = bn_sub_words(r, a, b, cl); + + if (dl == 0) + return c; + + r += cl; + a += cl; + b += cl; + + if (dl < 0) + { +#ifdef BN_COUNT + fprintf(stderr, " bn_sub_part_words %d + %d (dl < 0, c = %d)\n", cl, dl, c); +#endif + for (;;) + { + t = b[0]; + r[0] = (0-t-c)&BN_MASK2; + if (t != 0) c=1; + if (++dl >= 0) break; + + t = b[1]; + r[1] = (0-t-c)&BN_MASK2; + if (t != 0) c=1; + if (++dl >= 0) break; + + t = b[2]; + r[2] = (0-t-c)&BN_MASK2; + if (t != 0) c=1; + if (++dl >= 0) break; + + t = b[3]; + r[3] = (0-t-c)&BN_MASK2; + if (t != 0) c=1; + if (++dl >= 0) break; + + b += 4; + r += 4; + } + } + else + { + int save_dl = dl; +#ifdef BN_COUNT + fprintf(stderr, " bn_sub_part_words %d + %d (dl > 0, c = %d)\n", cl, dl, c); +#endif + while(c) + { + t = a[0]; + r[0] = (t-c)&BN_MASK2; + if (t != 0) c=0; + if (--dl <= 0) break; + + t = a[1]; + r[1] = (t-c)&BN_MASK2; + if (t != 0) c=0; + if (--dl <= 0) break; + + t = a[2]; + r[2] = (t-c)&BN_MASK2; + if (t != 0) c=0; + if (--dl <= 0) break; + + t = a[3]; + r[3] = (t-c)&BN_MASK2; + if (t != 0) c=0; + if (--dl <= 0) break; + + save_dl = dl; + a += 4; + r += 4; + } + if (dl > 0) + { +#ifdef BN_COUNT + fprintf(stderr, " bn_sub_part_words %d + %d (dl > 0, c == 0)\n", cl, dl); +#endif + if (save_dl > dl) + { + switch (save_dl - dl) + { + case 1: + r[1] = a[1]; + if (--dl <= 0) break; + case 2: + r[2] = a[2]; + if (--dl <= 0) break; + case 3: + r[3] = a[3]; + if (--dl <= 0) break; + } + a += 4; + r += 4; + } + } + if (dl > 0) + { +#ifdef BN_COUNT + fprintf(stderr, " bn_sub_part_words %d + %d (dl > 0, copy)\n", cl, dl); +#endif + for(;;) + { + r[0] = a[0]; + if (--dl <= 0) break; + r[1] = a[1]; + if (--dl <= 0) break; + r[2] = a[2]; + if (--dl <= 0) break; + r[3] = a[3]; + if (--dl <= 0) break; + + a += 4; + r += 4; + } + } + } + return c; + } +#endif + +BN_ULONG bn_add_part_words(BN_ULONG *r, + const BN_ULONG *a, const BN_ULONG *b, + int cl, int dl) + { + BN_ULONG c, l, t; + + assert(cl >= 0); + c = bn_add_words(r, a, b, cl); + + if (dl == 0) + return c; + + r += cl; + a += cl; + b += cl; + + if (dl < 0) + { + int save_dl = dl; +#ifdef BN_COUNT + fprintf(stderr, " bn_add_part_words %d + %d (dl < 0, c = %d)\n", cl, dl, c); +#endif + while (c) + { + l=(c+b[0])&BN_MASK2; + c=(l < c); + r[0]=l; + if (++dl >= 0) break; + + l=(c+b[1])&BN_MASK2; + c=(l < c); + r[1]=l; + if (++dl >= 0) break; + + l=(c+b[2])&BN_MASK2; + c=(l < c); + r[2]=l; + if (++dl >= 0) break; + + l=(c+b[3])&BN_MASK2; + c=(l < c); + r[3]=l; + if (++dl >= 0) break; + + save_dl = dl; + b+=4; + r+=4; + } + if (dl < 0) + { +#ifdef BN_COUNT + fprintf(stderr, " bn_add_part_words %d + %d (dl < 0, c == 0)\n", cl, dl); +#endif + if (save_dl < dl) + { + switch (dl - save_dl) + { + case 1: + r[1] = b[1]; + if (++dl >= 0) break; + case 2: + r[2] = b[2]; + if (++dl >= 0) break; + case 3: + r[3] = b[3]; + if (++dl >= 0) break; + } + b += 4; + r += 4; + } + } + if (dl < 0) + { +#ifdef BN_COUNT + fprintf(stderr, " bn_add_part_words %d + %d (dl < 0, copy)\n", cl, dl); +#endif + for(;;) + { + r[0] = b[0]; + if (++dl >= 0) break; + r[1] = b[1]; + if (++dl >= 0) break; + r[2] = b[2]; + if (++dl >= 0) break; + r[3] = b[3]; + if (++dl >= 0) break; + + b += 4; + r += 4; + } + } + } + else + { + int save_dl = dl; +#ifdef BN_COUNT + fprintf(stderr, " bn_add_part_words %d + %d (dl > 0)\n", cl, dl); +#endif + while (c) + { + t=(a[0]+c)&BN_MASK2; + c=(t < c); + r[0]=t; + if (--dl <= 0) break; + + t=(a[1]+c)&BN_MASK2; + c=(t < c); + r[1]=t; + if (--dl <= 0) break; + + t=(a[2]+c)&BN_MASK2; + c=(t < c); + r[2]=t; + if (--dl <= 0) break; + + t=(a[3]+c)&BN_MASK2; + c=(t < c); + r[3]=t; + if (--dl <= 0) break; + + save_dl = dl; + a+=4; + r+=4; + } +#ifdef BN_COUNT + fprintf(stderr, " bn_add_part_words %d + %d (dl > 0, c == 0)\n", cl, dl); +#endif + if (dl > 0) + { + if (save_dl > dl) + { + switch (save_dl - dl) + { + case 1: + r[1] = a[1]; + if (--dl <= 0) break; + case 2: + r[2] = a[2]; + if (--dl <= 0) break; + case 3: + r[3] = a[3]; + if (--dl <= 0) break; + } + a += 4; + r += 4; + } + } + if (dl > 0) + { +#ifdef BN_COUNT + fprintf(stderr, " bn_add_part_words %d + %d (dl > 0, copy)\n", cl, dl); +#endif + for(;;) + { + r[0] = a[0]; + if (--dl <= 0) break; + r[1] = a[1]; + if (--dl <= 0) break; + r[2] = a[2]; + if (--dl <= 0) break; + r[3] = a[3]; + if (--dl <= 0) break; + + a += 4; + r += 4; + } + } + } + return c; + } + #ifdef BN_RECURSION /* Karatsuba recursive multiplication algorithm * (cf. Knuth, The Art of Computer Programming, Vol. 2) */ @@ -74,15 +389,17 @@ * a[0]*b[0]+a[1]*b[1]+(a[0]-a[1])*(b[1]-b[0]) * a[1]*b[1] */ +/* dnX may not be positive, but n2/2+dnX has to be */ void bn_mul_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n2, - BN_ULONG *t) + int dna, int dnb, BN_ULONG *t) { int n=n2/2,c1,c2; + int tna=n+dna, tnb=n+dnb; unsigned int neg,zero; BN_ULONG ln,lo,*p; # ifdef BN_COUNT - printf(" bn_mul_recursive %d * %d\n",n2,n2); + fprintf(stderr," bn_mul_recursive %d%+d * %d%+d\n",n2,dna,n2,dnb); # endif # ifdef BN_MUL_COMBA # if 0 @@ -92,34 +409,40 @@ void bn_mul_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n2, return; } # endif - if (n2 == 8) + /* Only call bn_mul_comba 8 if n2 == 8 and the + * two arrays are complete [steve] + */ + if (n2 == 8 && dna == 0 && dnb == 0) { bn_mul_comba8(r,a,b); return; } # endif /* BN_MUL_COMBA */ + /* Else do normal multiply */ if (n2 < BN_MUL_RECURSIVE_SIZE_NORMAL) { - /* This should not happen */ - bn_mul_normal(r,a,n2,b,n2); + bn_mul_normal(r,a,n2+dna,b,n2+dnb); + if ((dna + dnb) < 0) + memset(&r[2*n2 + dna + dnb], 0, + sizeof(BN_ULONG) * -(dna + dnb)); return; } /* r=(a[0]-a[1])*(b[1]-b[0]) */ - c1=bn_cmp_words(a,&(a[n]),n); - c2=bn_cmp_words(&(b[n]),b,n); + c1=bn_cmp_part_words(a,&(a[n]),tna,n-tna); + c2=bn_cmp_part_words(&(b[n]),b,tnb,tnb-n); zero=neg=0; switch (c1*3+c2) { case -4: - bn_sub_words(t, &(a[n]),a, n); /* - */ - bn_sub_words(&(t[n]),b, &(b[n]),n); /* - */ + bn_sub_part_words(t, &(a[n]),a, tna,tna-n); /* - */ + bn_sub_part_words(&(t[n]),b, &(b[n]),tnb,n-tnb); /* - */ break; case -3: zero=1; break; case -2: - bn_sub_words(t, &(a[n]),a, n); /* - */ - bn_sub_words(&(t[n]),&(b[n]),b, n); /* + */ + bn_sub_part_words(t, &(a[n]),a, tna,tna-n); /* - */ + bn_sub_part_words(&(t[n]),&(b[n]),b, tnb,tnb-n); /* + */ neg=1; break; case -1: @@ -128,21 +451,22 @@ void bn_mul_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n2, zero=1; break; case 2: - bn_sub_words(t, a, &(a[n]),n); /* + */ - bn_sub_words(&(t[n]),b, &(b[n]),n); /* - */ + bn_sub_part_words(t, a, &(a[n]),tna,n-tna); /* + */ + bn_sub_part_words(&(t[n]),b, &(b[n]),tnb,n-tnb); /* - */ neg=1; break; case 3: zero=1; break; case 4: - bn_sub_words(t, a, &(a[n]),n); - bn_sub_words(&(t[n]),&(b[n]),b, n); + bn_sub_part_words(t, a, &(a[n]),tna,n-tna); + bn_sub_part_words(&(t[n]),&(b[n]),b, tnb,tnb-n); break; } # ifdef BN_MUL_COMBA - if (n == 4) + if (n == 4 && dna == 0 && dnb == 0) /* XXX: bn_mul_comba4 could take + extra args to do this well */ { if (!zero) bn_mul_comba4(&(t[n2]),t,&(t[n])); @@ -152,7 +476,9 @@ void bn_mul_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n2, bn_mul_comba4(r,a,b); bn_mul_comba4(&(r[n2]),&(a[n]),&(b[n])); } - else if (n == 8) + else if (n == 8 && dna == 0 && dnb == 0) /* XXX: bn_mul_comba8 could + take extra args to do this + well */ { if (!zero) bn_mul_comba8(&(t[n2]),t,&(t[n])); @@ -167,11 +493,11 @@ void bn_mul_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n2, { p= &(t[n2*2]); if (!zero) - bn_mul_recursive(&(t[n2]),t,&(t[n]),n,p); + bn_mul_recursive(&(t[n2]),t,&(t[n]),n,0,0,p); else memset(&(t[n2]),0,n2*sizeof(BN_ULONG)); - bn_mul_recursive(r,a,b,n,p); - bn_mul_recursive(&(r[n2]),&(a[n]),&(b[n]),n,p); + bn_mul_recursive(r,a,b,n,0,0,p); + bn_mul_recursive(&(r[n2]),&(a[n]),&(b[n]),n,dna,dnb,p); } /* t[32] holds (a[0]-a[1])*(b[1]-b[0]), c1 is the sign @@ -220,39 +546,40 @@ void bn_mul_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n2, /* n+tn is the word length * t needs to be n*4 is size, as does r */ -void bn_mul_part_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int tn, - int n, BN_ULONG *t) +/* tnX may not be negative but less than n */ +void bn_mul_part_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n, + int tna, int tnb, BN_ULONG *t) { int i,j,n2=n*2; int c1,c2,neg,zero; BN_ULONG ln,lo,*p; # ifdef BN_COUNT - printf(" bn_mul_part_recursive %d * %d\n",tn+n,tn+n); + fprintf(stderr," bn_mul_part_recursive (%d%+d) * (%d%+d)\n", + n, tna, n, tnb); # endif if (n < 8) { - i=tn+n; - bn_mul_normal(r,a,i,b,i); + bn_mul_normal(r,a,n+tna,b,n+tnb); return; } /* r=(a[0]-a[1])*(b[1]-b[0]) */ - c1=bn_cmp_words(a,&(a[n]),n); - c2=bn_cmp_words(&(b[n]),b,n); + c1=bn_cmp_part_words(a,&(a[n]),tna,n-tna); + c2=bn_cmp_part_words(&(b[n]),b,tnb,tnb-n); zero=neg=0; switch (c1*3+c2) { case -4: - bn_sub_words(t, &(a[n]),a, n); /* - */ - bn_sub_words(&(t[n]),b, &(b[n]),n); /* - */ + bn_sub_part_words(t, &(a[n]),a, tna,tna-n); /* - */ + bn_sub_part_words(&(t[n]),b, &(b[n]),tnb,n-tnb); /* - */ break; case -3: zero=1; /* break; */ case -2: - bn_sub_words(t, &(a[n]),a, n); /* - */ - bn_sub_words(&(t[n]),&(b[n]),b, n); /* + */ + bn_sub_part_words(t, &(a[n]),a, tna,tna-n); /* - */ + bn_sub_part_words(&(t[n]),&(b[n]),b, tnb,tnb-n); /* + */ neg=1; break; case -1: @@ -261,16 +588,16 @@ void bn_mul_part_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int tn, zero=1; /* break; */ case 2: - bn_sub_words(t, a, &(a[n]),n); /* + */ - bn_sub_words(&(t[n]),b, &(b[n]),n); /* - */ + bn_sub_part_words(t, a, &(a[n]),tna,n-tna); /* + */ + bn_sub_part_words(&(t[n]),b, &(b[n]),tnb,n-tnb); /* - */ neg=1; break; case 3: zero=1; /* break; */ case 4: - bn_sub_words(t, a, &(a[n]),n); - bn_sub_words(&(t[n]),&(b[n]),b, n); + bn_sub_part_words(t, a, &(a[n]),tna,n-tna); + bn_sub_part_words(&(t[n]),&(b[n]),b, tnb,tnb-n); break; } /* The zero case isn't yet implemented here. The speedup @@ -289,54 +616,62 @@ void bn_mul_part_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int tn, { bn_mul_comba8(&(t[n2]),t,&(t[n])); bn_mul_comba8(r,a,b); - bn_mul_normal(&(r[n2]),&(a[n]),tn,&(b[n]),tn); - memset(&(r[n2+tn*2]),0,sizeof(BN_ULONG)*(n2-tn*2)); + bn_mul_normal(&(r[n2]),&(a[n]),tna,&(b[n]),tnb); + memset(&(r[n2+tna+tnb]),0,sizeof(BN_ULONG)*(n2-tna-tnb)); } else { p= &(t[n2*2]); - bn_mul_recursive(&(t[n2]),t,&(t[n]),n,p); - bn_mul_recursive(r,a,b,n,p); + bn_mul_recursive(&(t[n2]),t,&(t[n]),n,0,0,p); + bn_mul_recursive(r,a,b,n,0,0,p); i=n/2; /* If there is only a bottom half to the number, * just do it */ - j=tn-i; + if (tna > tnb) + j = tna - i; + else + j = tnb - i; if (j == 0) { - bn_mul_recursive(&(r[n2]),&(a[n]),&(b[n]),i,p); + bn_mul_recursive(&(r[n2]),&(a[n]),&(b[n]), + i,tna-i,tnb-i,p); memset(&(r[n2+i*2]),0,sizeof(BN_ULONG)*(n2-i*2)); } else if (j > 0) /* eg, n == 16, i == 8 and tn == 11 */ { bn_mul_part_recursive(&(r[n2]),&(a[n]),&(b[n]), - j,i,p); - memset(&(r[n2+tn*2]),0, - sizeof(BN_ULONG)*(n2-tn*2)); + i,tna-i,tnb-i,p); + memset(&(r[n2+tna+tnb]),0, + sizeof(BN_ULONG)*(n2-tna-tnb)); } else /* (j < 0) eg, n == 16, i == 8 and tn == 5 */ { memset(&(r[n2]),0,sizeof(BN_ULONG)*n2); - if (tn < BN_MUL_RECURSIVE_SIZE_NORMAL) + if (tna < BN_MUL_RECURSIVE_SIZE_NORMAL + && tnb < BN_MUL_RECURSIVE_SIZE_NORMAL) { - bn_mul_normal(&(r[n2]),&(a[n]),tn,&(b[n]),tn); + bn_mul_normal(&(r[n2]),&(a[n]),tna,&(b[n]),tnb); } else { for (;;) { i/=2; - if (i < tn) + /* these simplified conditions work + * exclusively because difference + * between tna and tnb is 1 or 0 */ + if (i < tna || i < tnb) { bn_mul_part_recursive(&(r[n2]), &(a[n]),&(b[n]), - tn-i,i,p); + i,tna-i,tnb-i,p); break; } - else if (i == tn) + else if (i == tna || i == tnb) { bn_mul_recursive(&(r[n2]), &(a[n]),&(b[n]), - i,p); + i,tna-i,tnb-i,p); break; } } @@ -397,10 +732,10 @@ void bn_mul_low_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n2, int n=n2/2; # ifdef BN_COUNT - printf(" bn_mul_low_recursive %d * %d\n",n2,n2); + fprintf(stderr," bn_mul_low_recursive %d * %d\n",n2,n2); # endif - bn_mul_recursive(r,a,b,n,&(t[0])); + bn_mul_recursive(r,a,b,n,0,0,&(t[0])); if (n >= BN_MUL_LOW_RECURSIVE_SIZE_NORMAL) { bn_mul_low_recursive(&(t[0]),&(a[0]),&(b[n]),n,&(t[n2])); @@ -431,7 +766,7 @@ void bn_mul_high(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, BN_ULONG *l, int n2, BN_ULONG ll,lc,*lp,*mp; # ifdef BN_COUNT - printf(" bn_mul_high %d * %d\n",n2,n2); + fprintf(stderr," bn_mul_high %d * %d\n",n2,n2); # endif n=n2/2; @@ -484,8 +819,8 @@ void bn_mul_high(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, BN_ULONG *l, int n2, else # endif { - bn_mul_recursive(&(t[0]),&(r[0]),&(r[n]),n,&(t[n2])); - bn_mul_recursive(r,&(a[n]),&(b[n]),n,&(t[n2])); + bn_mul_recursive(&(t[0]),&(r[0]),&(r[n]),n,0,0,&(t[n2])); + bn_mul_recursive(r,&(a[n]),&(b[n]),n,0,0,&(t[n2])); } /* s0 == low(al*bl) @@ -610,19 +945,19 @@ void bn_mul_high(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, BN_ULONG *l, int n2, int BN_mul(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx) { + int ret=0; int top,al,bl; BIGNUM *rr; - int ret = 0; #if defined(BN_MUL_COMBA) || defined(BN_RECURSION) int i; #endif #ifdef BN_RECURSION - BIGNUM *t; - int j,k; + BIGNUM *t=NULL; + int j=0,k; #endif #ifdef BN_COUNT - printf("BN_mul %d * %d\n",a->top,b->top); + fprintf(stderr,"BN_mul %d * %d\n",a->top,b->top); #endif bn_check_top(a); @@ -634,7 +969,7 @@ int BN_mul(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx) if ((al == 0) || (bl == 0)) { - if (!BN_zero(r)) goto err; + BN_zero(r); return(1); } top=al+bl; @@ -675,21 +1010,55 @@ int BN_mul(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx) #ifdef BN_RECURSION if ((al >= BN_MULL_SIZE_NORMAL) && (bl >= BN_MULL_SIZE_NORMAL)) { - if (i == 1 && !BN_get_flags(b,BN_FLG_STATIC_DATA) && bldmax) + if (i >= -1 && i <= 1) { -#if 0 /* tribute to const-ification, bldmax above covers for this */ - if (bn_wexpand(b,al) == NULL) goto err; -#endif - b->d[bl]=0; + int sav_j =0; + /* Find out the power of two lower or equal + to the longest of the two numbers */ + if (i >= 0) + { + j = BN_num_bits_word((BN_ULONG)al); + } + if (i == -1) + { + j = BN_num_bits_word((BN_ULONG)bl); + } + sav_j = j; + j = 1<<(j-1); + assert(j <= al || j <= bl); + k = j+j; + t = BN_CTX_get(ctx); + if (al > j || bl > j) + { + bn_wexpand(t,k*4); + bn_wexpand(rr,k*4); + bn_mul_part_recursive(rr->d,a->d,b->d, + j,al-j,bl-j,t->d); + } + else /* al <= j || bl <= j */ + { + bn_wexpand(t,k*2); + bn_wexpand(rr,k*2); + bn_mul_recursive(rr->d,a->d,b->d, + j,al-j,bl-j,t->d); + } + rr->top=top; + goto end; + } +#if 0 + if (i == 1 && !BN_get_flags(b,BN_FLG_STATIC_DATA)) + { + BIGNUM *tmp_bn = (BIGNUM *)b; + if (bn_wexpand(tmp_bn,al) == NULL) goto err; + tmp_bn->d[bl]=0; bl++; i--; } - else if (i == -1 && !BN_get_flags(a,BN_FLG_STATIC_DATA) && aldmax) + else if (i == -1 && !BN_get_flags(a,BN_FLG_STATIC_DATA)) { -#if 0 /* tribute to const-ification, aldmax above covers for this */ - if (bn_wexpand(a,bl) == NULL) goto err; -#endif - a->d[al]=0; + BIGNUM *tmp_bn = (BIGNUM *)a; + if (bn_wexpand(tmp_bn,bl) == NULL) goto err; + tmp_bn->d[al]=0; al++; i++; } @@ -706,26 +1075,17 @@ int BN_mul(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx) if (bn_wexpand(t,k*2) == NULL) goto err; if (bn_wexpand(rr,k*2) == NULL) goto err; bn_mul_recursive(rr->d,a->d,b->d,al,t->d); - rr->top=top; - goto end; } -#if 0 /* tribute to const-ification, rsa/dsa performance is not affected */ else { - if (bn_wexpand(a,k) == NULL ) goto err; - if (bn_wexpand(b,k) == NULL ) goto err; - if (bn_wexpand(t,k*4) == NULL ) goto err; - if (bn_wexpand(rr,k*4) == NULL ) goto err; - for (i=a->top; id[i]=0; - for (i=b->top; id[i]=0; + if (bn_wexpand(t,k*4) == NULL) goto err; + if (bn_wexpand(rr,k*4) == NULL) goto err; bn_mul_part_recursive(rr->d,a->d,b->d,al-j,j,t->d); } rr->top=top; goto end; -#endif } +#endif } #endif /* BN_RECURSION */ if (bn_wexpand(rr,top) == NULL) goto err; @@ -735,10 +1095,11 @@ int BN_mul(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx) #if defined(BN_MUL_COMBA) || defined(BN_RECURSION) end: #endif - bn_fix_top(rr); + bn_correct_top(rr); if (r != rr) BN_copy(r,rr); ret=1; err: + bn_check_top(r); BN_CTX_end(ctx); return(ret); } @@ -748,7 +1109,7 @@ void bn_mul_normal(BN_ULONG *r, BN_ULONG *a, int na, BN_ULONG *b, int nb) BN_ULONG *rr; #ifdef BN_COUNT - printf(" bn_mul_normal %d * %d\n",na,nb); + fprintf(stderr," bn_mul_normal %d * %d\n",na,nb); #endif if (na < nb) @@ -761,7 +1122,13 @@ void bn_mul_normal(BN_ULONG *r, BN_ULONG *a, int na, BN_ULONG *b, int nb) } rr= &(r[na]); - rr[0]=bn_mul_words(r,a,na,b[0]); + if (nb <= 0) + { + (void)bn_mul_words(r,a,na,0); + return; + } + else + rr[0]=bn_mul_words(r,a,na,b[0]); for (;;) { @@ -782,7 +1149,7 @@ void bn_mul_normal(BN_ULONG *r, BN_ULONG *a, int na, BN_ULONG *b, int nb) void bn_mul_low_normal(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n) { #ifdef BN_COUNT - printf(" bn_mul_low_normal %d * %d\n",n,n); + fprintf(stderr," bn_mul_low_normal %d * %d\n",n,n); #endif bn_mul_words(r,a,n,b[0]); diff --git a/src/lib/libcrypto/bn/bn_prime.c b/src/lib/libcrypto/bn/bn_prime.c index f422172f16..7b25979dd1 100644 --- a/src/lib/libcrypto/bn/bn_prime.c +++ b/src/lib/libcrypto/bn/bn_prime.c @@ -115,6 +115,11 @@ #include "bn_lcl.h" #include +/* NB: these functions have been "upgraded", the deprecated versions (which are + * compatibility wrappers using these functions) are in bn_depr.c. + * - Geoff + */ + /* The quick sieve algorithm approach to weeding out primes is * Philip Zimmermann's, as implemented in PGP. I have had a read of * his comments and implemented my own version. @@ -129,51 +134,69 @@ static int probable_prime_dh(BIGNUM *rnd, int bits, static int probable_prime_dh_safe(BIGNUM *rnd, int bits, const BIGNUM *add, const BIGNUM *rem, BN_CTX *ctx); -BIGNUM *BN_generate_prime(BIGNUM *ret, int bits, int safe, - const BIGNUM *add, const BIGNUM *rem, - void (*callback)(int,int,void *), void *cb_arg) +int BN_GENCB_call(BN_GENCB *cb, int a, int b) + { + /* No callback means continue */ + if(!cb) return 1; + switch(cb->ver) + { + case 1: + /* Deprecated-style callbacks */ + if(!cb->cb.cb_1) + return 1; + cb->cb.cb_1(a, b, cb->arg); + return 1; + case 2: + /* New-style callbacks */ + return cb->cb.cb_2(a, b, cb); + default: + break; + } + /* Unrecognised callback type */ + return 0; + } + +int BN_generate_prime_ex(BIGNUM *ret, int bits, int safe, + const BIGNUM *add, const BIGNUM *rem, BN_GENCB *cb) { - BIGNUM *rnd=NULL; - BIGNUM t; + BIGNUM *t; int found=0; int i,j,c1=0; BN_CTX *ctx; int checks = BN_prime_checks_for_size(bits); - BN_init(&t); ctx=BN_CTX_new(); if (ctx == NULL) goto err; - if (ret == NULL) - { - if ((rnd=BN_new()) == NULL) goto err; - } - else - rnd=ret; + BN_CTX_start(ctx); + t = BN_CTX_get(ctx); + if(!t) goto err; loop: /* make a random number and set the top and bottom bits */ if (add == NULL) { - if (!probable_prime(rnd,bits)) goto err; + if (!probable_prime(ret,bits)) goto err; } else { if (safe) { - if (!probable_prime_dh_safe(rnd,bits,add,rem,ctx)) + if (!probable_prime_dh_safe(ret,bits,add,rem,ctx)) goto err; } else { - if (!probable_prime_dh(rnd,bits,add,rem,ctx)) + if (!probable_prime_dh(ret,bits,add,rem,ctx)) goto err; } } - /* if (BN_mod_word(rnd,(BN_ULONG)3) == 1) goto loop; */ - if (callback != NULL) callback(0,c1++,cb_arg); + /* if (BN_mod_word(ret,(BN_ULONG)3) == 1) goto loop; */ + if(!BN_GENCB_call(cb, 0, c1++)) + /* aborted */ + goto err; if (!safe) { - i=BN_is_prime_fasttest(rnd,checks,callback,ctx,cb_arg,0); + i=BN_is_prime_fasttest_ex(ret,checks,ctx,0,cb); if (i == -1) goto err; if (i == 0) goto loop; } @@ -183,41 +206,42 @@ loop: * check that (p-1)/2 is prime. * Since a prime is odd, We just * need to divide by 2 */ - if (!BN_rshift1(&t,rnd)) goto err; + if (!BN_rshift1(t,ret)) goto err; for (i=0; i a is prime if and only if a == 2 */ return BN_is_word(a, 2); - if (do_trial_division) { for (i = 1; i < NUMPRIMES; i++) if (BN_mod_word(a, primes[i]) == 0) return 0; - if (callback != NULL) callback(1, -1, cb_arg); + if(!BN_GENCB_call(cb, 1, -1)) + goto err; } if (ctx_passed != NULL) @@ -308,7 +332,8 @@ int BN_is_prime_fasttest(const BIGNUM *a, int checks, ret=0; goto err; } - if (callback != NULL) callback(1,i,cb_arg); + if(!BN_GENCB_call(cb, 1, i)) + goto err; } ret=1; err: @@ -345,20 +370,22 @@ static int witness(BIGNUM *w, const BIGNUM *a, const BIGNUM *a1, } /* If we get here, 'w' is the (a-1)/2-th power of the original 'w', * and it is neither -1 nor +1 -- so 'a' cannot be prime */ + bn_check_top(w); return 1; } static int probable_prime(BIGNUM *rnd, int bits) { int i; - BN_ULONG mods[NUMPRIMES]; - BN_ULONG delta,d; + prime_t mods[NUMPRIMES]; + BN_ULONG delta,maxdelta; again: if (!BN_rand(rnd,bits,1,1)) return(0); /* we now have a random number 'rand' to test. */ for (i=1; i maxdelta) goto again; goto loop; } } if (!BN_add_word(rnd,delta)) return(0); + bn_check_top(rnd); return(1); } @@ -413,6 +437,7 @@ static int probable_prime_dh(BIGNUM *rnd, int bits, ret=1; err: BN_CTX_end(ctx); + bn_check_top(rnd); return(ret); } @@ -464,5 +489,6 @@ static int probable_prime_dh_safe(BIGNUM *p, int bits, const BIGNUM *padd, ret=1; err: BN_CTX_end(ctx); + bn_check_top(p); return(ret); } diff --git a/src/lib/libcrypto/bn/bn_prime.h b/src/lib/libcrypto/bn/bn_prime.h index b7cf9a9bfe..51d2194feb 100644 --- a/src/lib/libcrypto/bn/bn_prime.h +++ b/src/lib/libcrypto/bn/bn_prime.h @@ -58,10 +58,12 @@ #ifndef EIGHT_BIT #define NUMPRIMES 2048 +typedef unsigned short prime_t; #else #define NUMPRIMES 54 +typedef unsigned char prime_t; #endif -static const unsigned int primes[NUMPRIMES]= +static const prime_t primes[NUMPRIMES]= { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, diff --git a/src/lib/libcrypto/bn/bn_prime.pl b/src/lib/libcrypto/bn/bn_prime.pl index 9fc3765486..3fafb6f3e9 100644 --- a/src/lib/libcrypto/bn/bn_prime.pl +++ b/src/lib/libcrypto/bn/bn_prime.pl @@ -11,7 +11,7 @@ loop: while ($#primes < $num-1) $p+=2; $s=int(sqrt($p)); - for ($i=0; $primes[$i]<=$s; $i++) + for ($i=0; defined($primes[$i]) && $primes[$i]<=$s; $i++) { next loop if (($p%$primes[$i]) == 0); } @@ -101,10 +101,12 @@ for ($i=0; $i <= $#primes; $i++) printf "#ifndef EIGHT_BIT\n"; printf "#define NUMPRIMES %d\n",$num; +printf "typedef unsigned short prime_t;\n"; printf "#else\n"; printf "#define NUMPRIMES %d\n",$eight; +printf "typedef unsigned char prime_t;\n"; printf "#endif\n"; -print "static const unsigned int primes[NUMPRIMES]=\n\t{\n\t"; +print "static const prime_t primes[NUMPRIMES]=\n\t{\n\t"; $init=0; for ($i=0; $i <= $#primes; $i++) { diff --git a/src/lib/libcrypto/bn/bn_print.c b/src/lib/libcrypto/bn/bn_print.c index acba7ed7ee..810dde34e1 100644 --- a/src/lib/libcrypto/bn/bn_print.c +++ b/src/lib/libcrypto/bn/bn_print.c @@ -62,7 +62,7 @@ #include #include "bn_lcl.h" -static const char *Hex="0123456789ABCDEF"; +static const char Hex[]="0123456789ABCDEF"; /* Must 'OPENSSL_free' the returned data */ char *BN_bn2hex(const BIGNUM *a) @@ -102,14 +102,19 @@ err: /* Must 'OPENSSL_free' the returned data */ char *BN_bn2dec(const BIGNUM *a) { - int i=0,num; + int i=0,num, ok = 0; char *buf=NULL; char *p; BIGNUM *t=NULL; BN_ULONG *bn_data=NULL,*lp; + /* get an upper bound for the length of the decimal integer + * num <= (BN_num_bits(a) + 1) * log(2) + * <= 3 * BN_num_bits(a) * 0.1001 + log(2) + 1 (rounding error) + * <= BN_num_bits(a)/10 + BN_num_bits/1000 + 1 + 1 + */ i=BN_num_bits(a)*3; - num=(i/10+i/1000+3)+1; + num=(i/10+i/1000+1)+1; bn_data=(BN_ULONG *)OPENSSL_malloc((num/BN_DEC_NUM+1)*sizeof(BN_ULONG)); buf=(char *)OPENSSL_malloc(num+3); if ((buf == NULL) || (bn_data == NULL)) @@ -122,7 +127,6 @@ char *BN_bn2dec(const BIGNUM *a) #define BUF_REMAIN (num+3 - (size_t)(p - buf)) p=buf; lp=bn_data; - if (t->neg) *(p++)='-'; if (BN_is_zero(t)) { *(p++)='0'; @@ -130,6 +134,9 @@ char *BN_bn2dec(const BIGNUM *a) } else { + if (BN_is_negative(t)) + *p++ = '-'; + i=0; while (!BN_is_zero(t)) { @@ -149,9 +156,16 @@ char *BN_bn2dec(const BIGNUM *a) while (*p) p++; } } + ok = 1; err: if (bn_data != NULL) OPENSSL_free(bn_data); if (t != NULL) BN_free(t); + if (!ok && buf) + { + OPENSSL_free(buf); + buf = NULL; + } + return(buf); } @@ -211,10 +225,11 @@ int BN_hex2bn(BIGNUM **bn, const char *a) j-=(BN_BYTES*2); } ret->top=h; - bn_fix_top(ret); + bn_correct_top(ret); ret->neg=neg; *bn=ret; + bn_check_top(ret); return(num); err: if (*bn == NULL) BN_free(ret); @@ -270,8 +285,9 @@ int BN_dec2bn(BIGNUM **bn, const char *a) } ret->neg=neg; - bn_fix_top(ret); + bn_correct_top(ret); *bn=ret; + bn_check_top(ret); return(num); err: if (*bn == NULL) BN_free(ret); @@ -300,7 +316,7 @@ int BN_print(BIO *bp, const BIGNUM *a) int ret=0; if ((a->neg) && (BIO_write(bp,"-",1) != 1)) goto end; - if ((BN_is_zero(a)) && (BIO_write(bp,"0",1) != 1)) goto end; + if (BN_is_zero(a) && (BIO_write(bp,"0",1) != 1)) goto end; for (i=a->top-1; i >=0; i--) { for (j=BN_BITS2-4; j >= 0; j-=4) @@ -320,14 +336,3 @@ end: return(ret); } #endif - -#ifdef BN_DEBUG -void bn_dump1(FILE *o, const char *a, const BN_ULONG *b,int n) - { - int i; - fprintf(o, "%s=", a); - for (i=n-1;i>=0;i--) - fprintf(o, "%08lX", b[i]); /* assumes 32-bit BN_ULONG */ - fprintf(o, "\n"); - } -#endif diff --git a/src/lib/libcrypto/bn/bn_rand.c b/src/lib/libcrypto/bn/bn_rand.c index 893c9d2af9..f51830b12b 100644 --- a/src/lib/libcrypto/bn/bn_rand.c +++ b/src/lib/libcrypto/bn/bn_rand.c @@ -134,13 +134,13 @@ static int bnrand(int pseudorand, BIGNUM *rnd, int bits, int top, int bottom) buf=(unsigned char *)OPENSSL_malloc(bytes); if (buf == NULL) { - BNerr(BN_F_BN_RAND,ERR_R_MALLOC_FAILURE); + BNerr(BN_F_BNRAND,ERR_R_MALLOC_FAILURE); goto err; } /* make a random number and set the top and bottom bits */ time(&tim); - RAND_add(&tim,sizeof(tim),0); + RAND_add(&tim,sizeof(tim),0.0); if (pseudorand) { @@ -204,6 +204,7 @@ err: OPENSSL_cleanse(buf,bytes); OPENSSL_free(buf); } + bn_check_top(rnd); return(ret); } @@ -230,6 +231,7 @@ static int bn_rand_range(int pseudo, BIGNUM *r, BIGNUM *range) { int (*bn_rand)(BIGNUM *, int, int, int) = pseudo ? BN_pseudo_rand : BN_rand; int n; + int count = 100; if (range->neg || BN_is_zero(range)) { @@ -242,9 +244,7 @@ static int bn_rand_range(int pseudo, BIGNUM *r, BIGNUM *range) /* BN_is_bit_set(range, n - 1) always holds */ if (n == 1) - { - if (!BN_zero(r)) return 0; - } + BN_zero(r); else if (!BN_is_bit_set(range, n - 2) && !BN_is_bit_set(range, n - 3)) { /* range = 100..._2, @@ -263,6 +263,13 @@ static int bn_rand_range(int pseudo, BIGNUM *r, BIGNUM *range) if (BN_cmp(r, range) >= 0) if (!BN_sub(r, r, range)) return 0; } + + if (!--count) + { + BNerr(BN_F_BN_RAND_RANGE, BN_R_TOO_MANY_ITERATIONS); + return 0; + } + } while (BN_cmp(r, range) >= 0); } @@ -272,10 +279,17 @@ static int bn_rand_range(int pseudo, BIGNUM *r, BIGNUM *range) { /* range = 11..._2 or range = 101..._2 */ if (!bn_rand(r, n, -1, 0)) return 0; + + if (!--count) + { + BNerr(BN_F_BN_RAND_RANGE, BN_R_TOO_MANY_ITERATIONS); + return 0; + } } while (BN_cmp(r, range) >= 0); } + bn_check_top(r); return 1; } diff --git a/src/lib/libcrypto/bn/bn_recp.c b/src/lib/libcrypto/bn/bn_recp.c index ef5fdd4708..2e8efb8dae 100644 --- a/src/lib/libcrypto/bn/bn_recp.c +++ b/src/lib/libcrypto/bn/bn_recp.c @@ -94,7 +94,7 @@ void BN_RECP_CTX_free(BN_RECP_CTX *recp) int BN_RECP_CTX_set(BN_RECP_CTX *recp, const BIGNUM *d, BN_CTX *ctx) { if (!BN_copy(&(recp->N),d)) return 0; - if (!BN_zero(&(recp->Nr))) return 0; + BN_zero(&(recp->Nr)); recp->num_bits=BN_num_bits(d); recp->shift=0; return(1); @@ -123,6 +123,7 @@ int BN_mod_mul_reciprocal(BIGNUM *r, const BIGNUM *x, const BIGNUM *y, ret = BN_div_recp(NULL,r,ca,recp,ctx); err: BN_CTX_end(ctx); + bn_check_top(r); return(ret); } @@ -147,7 +148,7 @@ int BN_div_recp(BIGNUM *dv, BIGNUM *rem, const BIGNUM *m, if (BN_ucmp(m,&(recp->N)) < 0) { - if (!BN_zero(d)) return 0; + BN_zero(d); if (!BN_copy(r,m)) return 0; BN_CTX_end(ctx); return(1); @@ -190,7 +191,7 @@ int BN_div_recp(BIGNUM *dv, BIGNUM *rem, const BIGNUM *m, { if (j++ > 2) { - BNerr(BN_F_BN_MOD_MUL_RECIPROCAL,BN_R_BAD_RECIPROCAL); + BNerr(BN_F_BN_DIV_RECP,BN_R_BAD_RECIPROCAL); goto err; } if (!BN_usub(r,r,&(recp->N))) goto err; @@ -203,6 +204,8 @@ int BN_div_recp(BIGNUM *dv, BIGNUM *rem, const BIGNUM *m, ret=1; err: BN_CTX_end(ctx); + bn_check_top(dv); + bn_check_top(rem); return(ret); } @@ -214,17 +217,18 @@ err: int BN_reciprocal(BIGNUM *r, const BIGNUM *m, int len, BN_CTX *ctx) { int ret= -1; - BIGNUM t; + BIGNUM *t; - BN_init(&t); + BN_CTX_start(ctx); + if((t = BN_CTX_get(ctx)) == NULL) goto err; - if (!BN_zero(&t)) goto err; - if (!BN_set_bit(&t,len)) goto err; + if (!BN_set_bit(t,len)) goto err; - if (!BN_div(r,NULL,&t,m,ctx)) goto err; + if (!BN_div(r,NULL,t,m,ctx)) goto err; ret=len; err: - BN_free(&t); + bn_check_top(r); + BN_CTX_end(ctx); return(ret); } diff --git a/src/lib/libcrypto/bn/bn_shift.c b/src/lib/libcrypto/bn/bn_shift.c index 70f785ea18..de9312dce2 100644 --- a/src/lib/libcrypto/bn/bn_shift.c +++ b/src/lib/libcrypto/bn/bn_shift.c @@ -65,6 +65,9 @@ int BN_lshift1(BIGNUM *r, const BIGNUM *a) register BN_ULONG *ap,*rp,t,c; int i; + bn_check_top(r); + bn_check_top(a); + if (r != a) { r->neg=a->neg; @@ -89,6 +92,7 @@ int BN_lshift1(BIGNUM *r, const BIGNUM *a) *rp=1; r->top++; } + bn_check_top(r); return(1); } @@ -97,6 +101,9 @@ int BN_rshift1(BIGNUM *r, const BIGNUM *a) BN_ULONG *ap,*rp,t,c; int i; + bn_check_top(r); + bn_check_top(a); + if (BN_is_zero(a)) { BN_zero(r); @@ -117,7 +124,8 @@ int BN_rshift1(BIGNUM *r, const BIGNUM *a) rp[i]=((t>>1)&BN_MASK2)|c; c=(t&1)?BN_TBIT:0; } - bn_fix_top(r); + bn_correct_top(r); + bn_check_top(r); return(1); } @@ -127,6 +135,9 @@ int BN_lshift(BIGNUM *r, const BIGNUM *a, int n) BN_ULONG *t,*f; BN_ULONG l; + bn_check_top(r); + bn_check_top(a); + r->neg=a->neg; nw=n/BN_BITS2; if (bn_wexpand(r,a->top+nw+1) == NULL) return(0); @@ -149,7 +160,8 @@ int BN_lshift(BIGNUM *r, const BIGNUM *a, int n) /* for (i=0; itop=a->top+nw+1; - bn_fix_top(r); + bn_correct_top(r); + bn_check_top(r); return(1); } @@ -159,6 +171,9 @@ int BN_rshift(BIGNUM *r, const BIGNUM *a, int n) BN_ULONG *t,*f; BN_ULONG l,tmp; + bn_check_top(r); + bn_check_top(a); + nw=n/BN_BITS2; rb=n%BN_BITS2; lb=BN_BITS2-rb; @@ -185,13 +200,13 @@ int BN_rshift(BIGNUM *r, const BIGNUM *a, int n) if (rb == 0) { - for (i=j+1; i > 0; i--) + for (i=j; i != 0; i--) *(t++)= *(f++); } else { l= *(f++); - for (i=1; i>rb)&BN_MASK2; l= *(f++); @@ -199,7 +214,7 @@ int BN_rshift(BIGNUM *r, const BIGNUM *a, int n) } *(t++) =(l>>rb)&BN_MASK2; } - *t=0; - bn_fix_top(r); + bn_correct_top(r); + bn_check_top(r); return(1); } diff --git a/src/lib/libcrypto/bn/bn_sqr.c b/src/lib/libcrypto/bn/bn_sqr.c index c1d0cca438..270d0cd348 100644 --- a/src/lib/libcrypto/bn/bn_sqr.c +++ b/src/lib/libcrypto/bn/bn_sqr.c @@ -77,16 +77,16 @@ int BN_sqr(BIGNUM *r, const BIGNUM *a, BN_CTX *ctx) if (al <= 0) { r->top=0; - return(1); + return 1; } BN_CTX_start(ctx); rr=(a != r) ? r : BN_CTX_get(ctx); tmp=BN_CTX_get(ctx); - if (tmp == NULL) goto err; + if (!rr || !tmp) goto err; - max=(al+al); - if (bn_wexpand(rr,max+1) == NULL) goto err; + max = 2 * al; /* Non-zero (from above) */ + if (bn_wexpand(rr,max) == NULL) goto err; if (al == 4) { @@ -138,12 +138,18 @@ int BN_sqr(BIGNUM *r, const BIGNUM *a, BN_CTX *ctx) #endif } - rr->top=max; rr->neg=0; - if ((max > 0) && (rr->d[max-1] == 0)) rr->top--; + /* If the most-significant half of the top word of 'a' is zero, then + * the square of 'a' will max-1 words. */ + if(a->d[al - 1] == (a->d[al - 1] & BN_MASK2l)) + rr->top = max - 1; + else + rr->top = max; if (rr != r) BN_copy(r,rr); ret = 1; err: + bn_check_top(rr); + bn_check_top(tmp); BN_CTX_end(ctx); return(ret); } diff --git a/src/lib/libcrypto/bn/bn_sqrt.c b/src/lib/libcrypto/bn/bn_sqrt.c index e2a1105dc8..6beaf9e5e5 100644 --- a/src/lib/libcrypto/bn/bn_sqrt.c +++ b/src/lib/libcrypto/bn/bn_sqrt.c @@ -1,4 +1,4 @@ -/* crypto/bn/bn_mod.c */ +/* crypto/bn/bn_sqrt.c */ /* Written by Lenka Fibikova * and Bodo Moeller for the OpenSSL project. */ /* ==================================================================== @@ -65,14 +65,12 @@ BIGNUM *BN_mod_sqrt(BIGNUM *in, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx) * using the Tonelli/Shanks algorithm (cf. Henri Cohen, "A Course * in Algebraic Computational Number Theory", algorithm 1.5.1). * 'p' must be prime! - * If 'a' is not a square, this is not necessarily detected by - * the algorithms; a bogus result must be expected in this case. */ { BIGNUM *ret = in; int err = 1; int r; - BIGNUM *b, *q, *t, *x, *y; + BIGNUM *A, *b, *q, *t, *x, *y; int e, i, j; if (!BN_is_odd(p) || BN_abs_is_word(p, 1)) @@ -85,9 +83,11 @@ BIGNUM *BN_mod_sqrt(BIGNUM *in, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx) goto end; if (!BN_set_word(ret, BN_is_bit_set(a, 0))) { - BN_free(ret); + if (ret != in) + BN_free(ret); return NULL; } + bn_check_top(ret); return ret; } @@ -103,23 +103,16 @@ BIGNUM *BN_mod_sqrt(BIGNUM *in, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx) goto end; if (!BN_set_word(ret, BN_is_one(a))) { - BN_free(ret); + if (ret != in) + BN_free(ret); return NULL; } + bn_check_top(ret); return ret; } -#if 0 /* if BN_mod_sqrt is used with correct input, this just wastes time */ - r = BN_kronecker(a, p, ctx); - if (r < -1) return NULL; - if (r == -1) - { - BNerr(BN_F_BN_MOD_SQRT, BN_R_NOT_A_SQUARE); - return(NULL); - } -#endif - BN_CTX_start(ctx); + A = BN_CTX_get(ctx); b = BN_CTX_get(ctx); q = BN_CTX_get(ctx); t = BN_CTX_get(ctx); @@ -131,6 +124,9 @@ BIGNUM *BN_mod_sqrt(BIGNUM *in, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx) ret = BN_new(); if (ret == NULL) goto end; + /* A = a mod p */ + if (!BN_nnmod(A, a, p, ctx)) goto end; + /* now write |p| - 1 as 2^e*q where q is odd */ e = 1; while (!BN_is_bit_set(p, e)) @@ -149,9 +145,9 @@ BIGNUM *BN_mod_sqrt(BIGNUM *in, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx) if (!BN_rshift(q, p, 2)) goto end; q->neg = 0; if (!BN_add_word(q, 1)) goto end; - if (!BN_mod_exp(ret, a, q, p, ctx)) goto end; + if (!BN_mod_exp(ret, A, q, p, ctx)) goto end; err = 0; - goto end; + goto vrfy; } if (e == 2) @@ -182,15 +178,8 @@ BIGNUM *BN_mod_sqrt(BIGNUM *in, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx) * November 1992.) */ - /* make sure that a is reduced modulo p */ - if (a->neg || BN_ucmp(a, p) >= 0) - { - if (!BN_nnmod(x, a, p, ctx)) goto end; - a = x; /* use x as temporary variable */ - } - /* t := 2*a */ - if (!BN_mod_lshift1_quick(t, a, p)) goto end; + if (!BN_mod_lshift1_quick(t, A, p)) goto end; /* b := (2*a)^((|p|-5)/8) */ if (!BN_rshift(q, p, 3)) goto end; @@ -205,12 +194,12 @@ BIGNUM *BN_mod_sqrt(BIGNUM *in, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx) if (!BN_sub_word(t, 1)) goto end; /* x = a*b*t */ - if (!BN_mod_mul(x, a, b, p, ctx)) goto end; + if (!BN_mod_mul(x, A, b, p, ctx)) goto end; if (!BN_mod_mul(x, x, t, p, ctx)) goto end; if (!BN_copy(ret, x)) goto end; err = 0; - goto end; + goto vrfy; } /* e > 2, so we really have to use the Tonelli/Shanks algorithm. @@ -297,11 +286,11 @@ BIGNUM *BN_mod_sqrt(BIGNUM *in, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx) /* x := a^((q-1)/2) */ if (BN_is_zero(t)) /* special case: p = 2^e + 1 */ { - if (!BN_nnmod(t, a, p, ctx)) goto end; + if (!BN_nnmod(t, A, p, ctx)) goto end; if (BN_is_zero(t)) { /* special case: a == 0 (mod p) */ - if (!BN_zero(ret)) goto end; + BN_zero(ret); err = 0; goto end; } @@ -310,11 +299,11 @@ BIGNUM *BN_mod_sqrt(BIGNUM *in, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx) } else { - if (!BN_mod_exp(x, a, t, p, ctx)) goto end; + if (!BN_mod_exp(x, A, t, p, ctx)) goto end; if (BN_is_zero(x)) { /* special case: a == 0 (mod p) */ - if (!BN_zero(ret)) goto end; + BN_zero(ret); err = 0; goto end; } @@ -322,10 +311,10 @@ BIGNUM *BN_mod_sqrt(BIGNUM *in, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx) /* b := a*x^2 (= a^q) */ if (!BN_mod_sqr(b, x, p, ctx)) goto end; - if (!BN_mod_mul(b, b, a, p, ctx)) goto end; + if (!BN_mod_mul(b, b, A, p, ctx)) goto end; /* x := a*x (= a^((q+1)/2)) */ - if (!BN_mod_mul(x, x, a, p, ctx)) goto end; + if (!BN_mod_mul(x, x, A, p, ctx)) goto end; while (1) { @@ -342,7 +331,7 @@ BIGNUM *BN_mod_sqrt(BIGNUM *in, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx) { if (!BN_copy(ret, x)) goto end; err = 0; - goto end; + goto vrfy; } @@ -373,6 +362,22 @@ BIGNUM *BN_mod_sqrt(BIGNUM *in, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx) e = i; } + vrfy: + if (!err) + { + /* verify the result -- the input might have been not a square + * (test added in 0.9.8) */ + + if (!BN_mod_sqr(x, ret, p, ctx)) + err = 1; + + if (!err && 0 != BN_cmp(x, A)) + { + BNerr(BN_F_BN_MOD_SQRT, BN_R_NOT_A_SQUARE); + err = 1; + } + } + end: if (err) { @@ -383,5 +388,6 @@ BIGNUM *BN_mod_sqrt(BIGNUM *in, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx) ret = NULL; } BN_CTX_end(ctx); + bn_check_top(ret); return ret; } diff --git a/src/lib/libcrypto/bn/bn_word.c b/src/lib/libcrypto/bn/bn_word.c index de610ce54c..ee7b87c45c 100644 --- a/src/lib/libcrypto/bn/bn_word.c +++ b/src/lib/libcrypto/bn/bn_word.c @@ -69,6 +69,10 @@ BN_ULONG BN_mod_word(const BIGNUM *a, BN_ULONG w) #endif int i; + if (w == 0) + return (BN_ULONG)-1; + + bn_check_top(a); w&=BN_MASK2; for (i=a->top-1; i>=0; i--) { @@ -85,12 +89,24 @@ BN_ULONG BN_mod_word(const BIGNUM *a, BN_ULONG w) BN_ULONG BN_div_word(BIGNUM *a, BN_ULONG w) { - BN_ULONG ret; - int i; + BN_ULONG ret = 0; + int i, j; + + bn_check_top(a); + w &= BN_MASK2; + + if (!w) + /* actually this an error (division by zero) */ + return (BN_ULONG)-1; + if (a->top == 0) + return 0; + + /* normalize input (so bn_div_words doesn't complain) */ + j = BN_BITS2 - BN_num_bits_word(w); + w <<= j; + if (!BN_lshift(a, a, j)) + return (BN_ULONG)-1; - if (a->top == 0) return(0); - ret=0; - w&=BN_MASK2; for (i=a->top-1; i>=0; i--) { BN_ULONG l,d; @@ -102,6 +118,8 @@ BN_ULONG BN_div_word(BIGNUM *a, BN_ULONG w) } if ((a->top > 0) && (a->d[a->top-1] == 0)) a->top--; + ret >>= j; + bn_check_top(a); return(ret); } @@ -110,9 +128,14 @@ int BN_add_word(BIGNUM *a, BN_ULONG w) BN_ULONG l; int i; - if ((w & BN_MASK2) == 0) - return(1); + bn_check_top(a); + w &= BN_MASK2; + /* degenerate case: w is zero */ + if (!w) return 1; + /* degenerate case: a is zero */ + if(BN_is_zero(a)) return BN_set_word(a, w); + /* handle 'a' when negative */ if (a->neg) { a->neg=0; @@ -121,15 +144,17 @@ int BN_add_word(BIGNUM *a, BN_ULONG w) a->neg=!(a->neg); return(i); } - w&=BN_MASK2; - if (bn_wexpand(a,a->top+1) == NULL) return(0); + /* Only expand (and risk failing) if it's possibly necessary */ + if (((BN_ULONG)(a->d[a->top - 1] + 1) == 0) && + (bn_wexpand(a,a->top+1) == NULL)) + return(0); i=0; for (;;) { if (i >= a->top) l=w; else - l=(a->d[i]+(BN_ULONG)w)&BN_MASK2; + l=(a->d[i]+w)&BN_MASK2; a->d[i]=l; if (w > l) w=1; @@ -139,6 +164,7 @@ int BN_add_word(BIGNUM *a, BN_ULONG w) } if (i >= a->top) a->top++; + bn_check_top(a); return(1); } @@ -146,10 +172,21 @@ int BN_sub_word(BIGNUM *a, BN_ULONG w) { int i; - if ((w & BN_MASK2) == 0) - return(1); + bn_check_top(a); + w &= BN_MASK2; - if (BN_is_zero(a) || a->neg) + /* degenerate case: w is zero */ + if (!w) return 1; + /* degenerate case: a is zero */ + if(BN_is_zero(a)) + { + i = BN_set_word(a,w); + if (i != 0) + BN_set_negative(a, 1); + return i; + } + /* handle 'a' when negative */ + if (a->neg) { a->neg=0; i=BN_add_word(a,w); @@ -157,7 +194,6 @@ int BN_sub_word(BIGNUM *a, BN_ULONG w) return(i); } - w&=BN_MASK2; if ((a->top == 1) && (a->d[0] < w)) { a->d[0]=w-a->d[0]; @@ -181,6 +217,7 @@ int BN_sub_word(BIGNUM *a, BN_ULONG w) } if ((a->d[i] == 0) && (i == (a->top-1))) a->top--; + bn_check_top(a); return(1); } @@ -188,6 +225,7 @@ int BN_mul_word(BIGNUM *a, BN_ULONG w) { BN_ULONG ll; + bn_check_top(a); w&=BN_MASK2; if (a->top) { @@ -203,6 +241,7 @@ int BN_mul_word(BIGNUM *a, BN_ULONG w) } } } + bn_check_top(a); return(1); } diff --git a/src/lib/libcrypto/bn/bntest.c b/src/lib/libcrypto/bn/bntest.c index 792a75ff4f..cf190380f5 100644 --- a/src/lib/libcrypto/bn/bntest.c +++ b/src/lib/libcrypto/bn/bntest.c @@ -55,6 +55,25 @@ * copied and put under another distribution licence * [including the GNU Public Licence.] */ +/* ==================================================================== + * Copyright 2002 Sun Microsystems, Inc. ALL RIGHTS RESERVED. + * + * Portions of the attached software ("Contribution") are developed by + * SUN MICROSYSTEMS, INC., and are contributed to the OpenSSL project. + * + * The Contribution is licensed pursuant to the Eric Young open source + * license provided above. + * + * The binary polynomial arithmetic software is originally written by + * Sheueling Chang Shantz and Douglas Stebila of Sun Microsystems Laboratories. + * + */ + +/* Until the key-gen callbacks are modified to use newer prototypes, we allow + * deprecated functions for openssl-internal code */ +#ifdef OPENSSL_NO_DEPRECATED +#undef OPENSSL_NO_DEPRECATED +#endif #include #include @@ -79,6 +98,7 @@ int test_lshift(BIO *bp,BN_CTX *ctx,BIGNUM *a_); int test_rshift1(BIO *bp); int test_rshift(BIO *bp,BN_CTX *ctx); int test_div(BIO *bp,BN_CTX *ctx); +int test_div_word(BIO *bp); int test_div_recp(BIO *bp,BN_CTX *ctx); int test_mul(BIO *bp); int test_sqr(BIO *bp,BN_CTX *ctx); @@ -88,6 +108,15 @@ int test_mod_mul(BIO *bp,BN_CTX *ctx); int test_mod_exp(BIO *bp,BN_CTX *ctx); int test_mod_exp_mont_consttime(BIO *bp,BN_CTX *ctx); int test_exp(BIO *bp,BN_CTX *ctx); +int test_gf2m_add(BIO *bp); +int test_gf2m_mod(BIO *bp); +int test_gf2m_mod_mul(BIO *bp,BN_CTX *ctx); +int test_gf2m_mod_sqr(BIO *bp,BN_CTX *ctx); +int test_gf2m_mod_inv(BIO *bp,BN_CTX *ctx); +int test_gf2m_mod_div(BIO *bp,BN_CTX *ctx); +int test_gf2m_mod_exp(BIO *bp,BN_CTX *ctx); +int test_gf2m_mod_sqrt(BIO *bp,BN_CTX *ctx); +int test_gf2m_mod_solve_quad(BIO *bp,BN_CTX *ctx); int test_kron(BIO *bp,BN_CTX *ctx); int test_sqrt(BIO *bp,BN_CTX *ctx); int rand_neg(void); @@ -155,80 +184,120 @@ int main(int argc, char *argv[]) message(out,"BN_add"); if (!test_add(out)) goto err; - BIO_flush(out); + (void)BIO_flush(out); message(out,"BN_sub"); if (!test_sub(out)) goto err; - BIO_flush(out); + (void)BIO_flush(out); message(out,"BN_lshift1"); if (!test_lshift1(out)) goto err; - BIO_flush(out); + (void)BIO_flush(out); message(out,"BN_lshift (fixed)"); if (!test_lshift(out,ctx,BN_bin2bn(lst,sizeof(lst)-1,NULL))) goto err; - BIO_flush(out); + (void)BIO_flush(out); message(out,"BN_lshift"); if (!test_lshift(out,ctx,NULL)) goto err; - BIO_flush(out); + (void)BIO_flush(out); message(out,"BN_rshift1"); if (!test_rshift1(out)) goto err; - BIO_flush(out); + (void)BIO_flush(out); message(out,"BN_rshift"); if (!test_rshift(out,ctx)) goto err; - BIO_flush(out); + (void)BIO_flush(out); message(out,"BN_sqr"); if (!test_sqr(out,ctx)) goto err; - BIO_flush(out); + (void)BIO_flush(out); message(out,"BN_mul"); if (!test_mul(out)) goto err; - BIO_flush(out); + (void)BIO_flush(out); message(out,"BN_div"); if (!test_div(out,ctx)) goto err; - BIO_flush(out); + (void)BIO_flush(out); + + message(out,"BN_div_word"); + if (!test_div_word(out)) goto err; + (void)BIO_flush(out); message(out,"BN_div_recp"); if (!test_div_recp(out,ctx)) goto err; - BIO_flush(out); + (void)BIO_flush(out); message(out,"BN_mod"); if (!test_mod(out,ctx)) goto err; - BIO_flush(out); + (void)BIO_flush(out); message(out,"BN_mod_mul"); if (!test_mod_mul(out,ctx)) goto err; - BIO_flush(out); + (void)BIO_flush(out); message(out,"BN_mont"); if (!test_mont(out,ctx)) goto err; - BIO_flush(out); + (void)BIO_flush(out); message(out,"BN_mod_exp"); if (!test_mod_exp(out,ctx)) goto err; - BIO_flush(out); + (void)BIO_flush(out); message(out,"BN_mod_exp_mont_consttime"); if (!test_mod_exp_mont_consttime(out,ctx)) goto err; - BIO_flush(out); + (void)BIO_flush(out); message(out,"BN_exp"); if (!test_exp(out,ctx)) goto err; - BIO_flush(out); + (void)BIO_flush(out); message(out,"BN_kronecker"); if (!test_kron(out,ctx)) goto err; - BIO_flush(out); + (void)BIO_flush(out); message(out,"BN_mod_sqrt"); if (!test_sqrt(out,ctx)) goto err; - BIO_flush(out); + (void)BIO_flush(out); + + message(out,"BN_GF2m_add"); + if (!test_gf2m_add(out)) goto err; + (void)BIO_flush(out); + + message(out,"BN_GF2m_mod"); + if (!test_gf2m_mod(out)) goto err; + (void)BIO_flush(out); + + message(out,"BN_GF2m_mod_mul"); + if (!test_gf2m_mod_mul(out,ctx)) goto err; + (void)BIO_flush(out); + + message(out,"BN_GF2m_mod_sqr"); + if (!test_gf2m_mod_sqr(out,ctx)) goto err; + (void)BIO_flush(out); + + message(out,"BN_GF2m_mod_inv"); + if (!test_gf2m_mod_inv(out,ctx)) goto err; + (void)BIO_flush(out); + + message(out,"BN_GF2m_mod_div"); + if (!test_gf2m_mod_div(out,ctx)) goto err; + (void)BIO_flush(out); + + message(out,"BN_GF2m_mod_exp"); + if (!test_gf2m_mod_exp(out,ctx)) goto err; + (void)BIO_flush(out); + + message(out,"BN_GF2m_mod_sqrt"); + if (!test_gf2m_mod_sqrt(out,ctx)) goto err; + (void)BIO_flush(out); + + message(out,"BN_GF2m_mod_solve_quad"); + if (!test_gf2m_mod_solve_quad(out,ctx)) goto err; + (void)BIO_flush(out); BN_CTX_free(ctx); BIO_free(out); @@ -237,8 +306,8 @@ int main(int argc, char *argv[]) EXIT(0); err: BIO_puts(out,"1\n"); /* make sure the Perl script fed by bc notices - * the failure, see test_bn in test/Makefile */ - BIO_flush(out); + * the failure, see test_bn in test/Makefile.ssl*/ + (void)BIO_flush(out); ERR_load_crypto_strings(); ERR_print_errors_fp(stderr); EXIT(1); @@ -404,6 +473,78 @@ int test_div(BIO *bp, BN_CTX *ctx) return(1); } +static void print_word(BIO *bp,BN_ULONG w) + { +#ifdef SIXTY_FOUR_BIT + if (sizeof(w) > sizeof(unsigned long)) + { + unsigned long h=(unsigned long)(w>>32), + l=(unsigned long)(w); + + if (h) BIO_printf(bp,"%lX%08lX",h,l); + else BIO_printf(bp,"%lX",l); + return; + } +#endif + BIO_printf(bp,"%lX",w); + } + +int test_div_word(BIO *bp) + { + BIGNUM a,b; + BN_ULONG r,s; + int i; + + BN_init(&a); + BN_init(&b); + + for (i=0; ineg = rand_neg(); putc('\n', stderr); @@ -1023,6 +1741,7 @@ int test_kron(BIO *bp, BN_CTX *ctx) int test_sqrt(BIO *bp, BN_CTX *ctx) { + BN_GENCB cb; BIGNUM *a,*p,*r; int i, j; int ret = 0; @@ -1031,7 +1750,9 @@ int test_sqrt(BIO *bp, BN_CTX *ctx) p = BN_new(); r = BN_new(); if (a == NULL || p == NULL || r == NULL) goto err; - + + BN_GENCB_set(&cb, genprime_cb, NULL); + for (i = 0; i < 16; i++) { if (i < 8) @@ -1045,7 +1766,7 @@ int test_sqrt(BIO *bp, BN_CTX *ctx) if (!BN_set_word(a, 32)) goto err; if (!BN_set_word(r, 2*i + 1)) goto err; - if (!BN_generate_prime(p, 256, 0, a, r, genprime_cb, NULL)) goto err; + if (!BN_generate_prime_ex(p, 256, 0, a, r, &cb)) goto err; putc('\n', stderr); } p->neg = rand_neg(); diff --git a/src/lib/libcrypto/bn/exptest.c b/src/lib/libcrypto/bn/exptest.c index 28aaac2ac1..f598a07cf5 100644 --- a/src/lib/libcrypto/bn/exptest.c +++ b/src/lib/libcrypto/bn/exptest.c @@ -195,6 +195,9 @@ int main(int argc, char *argv[]) err: ERR_load_crypto_strings(); ERR_print_errors(out); +#ifdef OPENSSL_SYS_NETWARE + printf("ERROR\n"); +#endif EXIT(1); return(1); } -- cgit v1.2.3-55-g6feb