From 78a0c1f18d5a1f0e51b7467ef7b153b8c29fbb03 Mon Sep 17 00:00:00 2001 From: =?utf8?q?Bodo=20M=C3=B6ller?= Date: Sun, 26 Nov 2000 16:42:38 +0000 Subject: [PATCH] modular arithmetics "make update" --- CHANGES | 27 ++++++++- TABLE | 26 ++++---- crypto/bn/Makefile.ssl | 11 +++- crypto/bn/bn.h | 20 +++---- crypto/bn/bn_div.c | 49 ++++------------ crypto/bn/bn_exp.c | 56 ++++++++---------- crypto/bn/bn_lib.c | 29 +++++++++ crypto/bn/bn_modfs.c | 70 +--------------------- crypto/bn/bn_modfs.h | 54 +++++++---------- crypto/bn/bn_recp.c | 4 +- crypto/bn/bn_sqr.c | 2 +- crypto/bn/expspeed.c | 7 +-- doc/crypto/BN_add.pod | 88 ++++++++++++++++++---------- doc/crypto/BN_mod_mul_montgomery.pod | 15 ++--- doc/crypto/bn.pod | 14 ++++- ssl/ssl.h | 7 +++ ssl/ssl_err.c | 7 +++ util/libeay.num | 4 ++ 18 files changed, 245 insertions(+), 245 deletions(-) diff --git a/CHANGES b/CHANGES index c54ab994f5..e37d299dee 100644 --- a/CHANGES +++ b/CHANGES @@ -1,9 +1,34 @@ - OpenSSL CHANGES _______________ Changes between 0.9.6 and 0.9.7 [xx XXX 2000] + *) New function BN_swap. + [Bodo Moeller] + + *) Use BN_nnmod instead of BN_mod in crypto/bn/bn_exp.c so that + the exponentiation functions are more likely to produce reasonable + results on negative inputs. + [Bodo Moeller] + + *) Change BN_mod_mul so that the result is always non-negative. + Previously, it could be negative if one of the factors was negative; + I don't think anyone really wanted that behaviour. + [Bodo Moeller] + + *) Move BN_mod_... functions into new file crypto/bn/bn_mod.c + (except for exponentation, which stays in crypto/bn/bn_exp.c, + and BN_mod_mul_reciprocal, which stays in crypto/bn/bn_recp.c) + and add new functions: + BN_nnmod + BN_mod_sqr + BN_mod_add + BN_mod_sub + These functions always generate non-negative results. + BN_nnmod otherwise is like BN_mod (if BN_mod computes a remainder r + such that |m| < r < 0, BN_nnmod will output rem + |m| instead). + [Lenka Fibikova , Bodo Moeller] + *) Remove a few calls to bn_wexpand() in BN_sqr() (the one in there was actually never needed) and in BN_mul(). The removal in BN_mul() required a small change in bn_mul_part_recursive() and the addition diff --git a/TABLE b/TABLE index 7a397aecc8..9b07db96a7 100644 --- a/TABLE +++ b/TABLE @@ -846,20 +846,20 @@ $cflags = -DLEVITTE_DEBUG -DREF_CHECK -DCONF_DEBUG -DBN_CTX_DEBUG -DCRYPTO $unistd = $thread_cflag = -D_REENTRANT $lflags = -ldl -$bn_ops = -$bn_obj = -$des_obj = -$bf_obj = -$md5_obj = -$sha1_obj = -$cast_obj = -$rc4_obj = -$rmd160_obj = -$rc5_obj = +$bn_ops = BN_LLONG DES_PTR DES_RISC1 DES_UNROLL RC4_INDEX MD2_INT +$bn_obj = asm/bn86-elf.o asm/co86-elf.o +$des_obj = asm/dx86-elf.o asm/yx86-elf.o +$bf_obj = asm/bx86-elf.o +$md5_obj = asm/mx86-elf.o +$sha1_obj = asm/sx86-elf.o +$cast_obj = asm/cx86-elf.o +$rc4_obj = asm/rx86-elf.o +$rmd160_obj = asm/rm86-elf.o +$rc5_obj = asm/r586-elf.o $dso_scheme = dlfcn -$shared_target= -$shared_cflag = -$shared_extension = +$shared_target= linux-shared +$shared_cflag = -fPIC +$shared_extension = .so.$(SHLIB_MAJOR).$(SHLIB_MINOR) *** debug-linux-elf $cc = gcc diff --git a/crypto/bn/Makefile.ssl b/crypto/bn/Makefile.ssl index ad36267e26..89bd67bce1 100644 --- a/crypto/bn/Makefile.ssl +++ b/crypto/bn/Makefile.ssl @@ -35,12 +35,12 @@ TEST=bntest.c exptest.c APPS= LIB=$(TOP)/libcrypto.a -LIBSRC= bn_add.c bn_div.c bn_exp.c bn_lib.c bn_ctx.c bn_mul.c \ +LIBSRC= bn_add.c bn_div.c bn_exp.c bn_lib.c bn_ctx.c bn_mul.c bn_mod.c \ bn_print.c bn_rand.c bn_shift.c bn_word.c bn_blind.c \ bn_gcd.c bn_prime.c bn_err.c bn_sqr.c bn_asm.c bn_recp.c bn_mont.c \ bn_mpi.c bn_exp2.c -LIBOBJ= bn_add.o bn_div.o bn_exp.o bn_lib.o bn_ctx.o bn_mul.o \ +LIBOBJ= bn_add.o bn_div.o bn_exp.o bn_lib.o bn_ctx.o bn_mul.o bn_mod.o \ bn_print.o bn_rand.o bn_shift.o bn_word.o bn_blind.o \ bn_gcd.o bn_prime.o bn_err.o bn_sqr.o $(BN_ASM) bn_recp.o bn_mont.o \ bn_mpi.o bn_exp2.o @@ -237,6 +237,13 @@ bn_lib.o: ../../include/openssl/err.h ../../include/openssl/lhash.h bn_lib.o: ../../include/openssl/opensslconf.h ../../include/openssl/opensslv.h bn_lib.o: ../../include/openssl/safestack.h ../../include/openssl/stack.h bn_lib.o: ../../include/openssl/symhacks.h ../cryptlib.h bn_lcl.h +bn_mod.o: ../../include/openssl/bio.h ../../include/openssl/bn.h +bn_mod.o: ../../include/openssl/buffer.h ../../include/openssl/crypto.h +bn_mod.o: ../../include/openssl/e_os.h ../../include/openssl/e_os2.h +bn_mod.o: ../../include/openssl/err.h ../../include/openssl/lhash.h +bn_mod.o: ../../include/openssl/opensslconf.h ../../include/openssl/opensslv.h +bn_mod.o: ../../include/openssl/safestack.h ../../include/openssl/stack.h +bn_mod.o: ../../include/openssl/symhacks.h ../cryptlib.h bn_lcl.h bn_mont.o: ../../include/openssl/bio.h ../../include/openssl/bn.h bn_mont.o: ../../include/openssl/buffer.h ../../include/openssl/crypto.h bn_mont.o: ../../include/openssl/e_os.h ../../include/openssl/e_os2.h diff --git a/crypto/bn/bn.h b/crypto/bn/bn.h index 857ade3fbd..0a665c2538 100644 --- a/crypto/bn/bn.h +++ b/crypto/bn/bn.h @@ -75,8 +75,6 @@ extern "C" { #define BN_MUL_COMBA #define BN_SQR_COMBA #define BN_RECURSION -#define RECP_MUL_MOD -#define MONT_MUL_MOD /* This next option uses the C libraries (2 word)/(1 word) function. * If it is not defined, I use my C version (which is slower). @@ -284,9 +282,6 @@ typedef struct bn_recp_ctx_st int flags; } BN_RECP_CTX; -#define BN_to_montgomery(r,a,mont,ctx) BN_mod_mul_montgomery(\ - r,a,&((mont)->RR),(mont),ctx) - #define BN_prime_checks 0 /* default: select number of iterations based on the size of the number */ @@ -335,6 +330,7 @@ BIGNUM *BN_new(void); void BN_init(BIGNUM *); void BN_clear_free(BIGNUM *a); BIGNUM *BN_copy(BIGNUM *a, const BIGNUM *b); +void BN_swap(BIGNUM *a, BIGNUM *b); BIGNUM *BN_bin2bn(const unsigned char *s,int len,BIGNUM *ret); int BN_bn2bin(const BIGNUM *a, unsigned char *to); BIGNUM *BN_mpi2bn(const unsigned char *s,int len,BIGNUM *ret); @@ -343,11 +339,14 @@ int BN_sub(BIGNUM *r, const BIGNUM *a, const BIGNUM *b); int BN_usub(BIGNUM *r, const BIGNUM *a, const BIGNUM *b); int BN_uadd(BIGNUM *r, const BIGNUM *a, const BIGNUM *b); int BN_add(BIGNUM *r, const BIGNUM *a, const BIGNUM *b); -int BN_mod(BIGNUM *rem, const BIGNUM *m, const BIGNUM *d, BN_CTX *ctx); -int BN_div(BIGNUM *dv, BIGNUM *rem, const BIGNUM *m, const BIGNUM *d, - BN_CTX *ctx); 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); +int BN_div(BIGNUM *dv, BIGNUM *rem, const BIGNUM *m, const BIGNUM *d, + BN_CTX *ctx); +#define BN_mod(rem,m,d,ctx) BN_div(NULL,(rem),(m),(d),(ctx)) +int BN_nnmod(BIGNUM *rem, const BIGNUM *m, const BIGNUM *d, BN_CTX *ctx); +int BN_mod_mul(BIGNUM *ret, const BIGNUM *a, const BIGNUM *b, + const BIGNUM *m, BN_CTX *ctx); BN_ULONG BN_mod_word(const BIGNUM *a, BN_ULONG w); BN_ULONG BN_div_word(BIGNUM *a, BN_ULONG w); int BN_mul_word(BIGNUM *a, BN_ULONG w); @@ -373,8 +372,6 @@ int BN_mod_exp2_mont(BIGNUM *r, const BIGNUM *a1, const BIGNUM *p1, int BN_mod_exp_simple(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, const BIGNUM *m,BN_CTX *ctx); int BN_mask_bits(BIGNUM *a,int n); -int BN_mod_mul(BIGNUM *ret, const BIGNUM *a, const BIGNUM *b, - const BIGNUM *m, BN_CTX *ctx); #ifndef NO_FP_API int BN_print_fp(FILE *fp, const BIGNUM *a); #endif @@ -413,6 +410,8 @@ BN_MONT_CTX *BN_MONT_CTX_new(void ); void BN_MONT_CTX_init(BN_MONT_CTX *ctx); int BN_mod_mul_montgomery(BIGNUM *r,const BIGNUM *a,const BIGNUM *b, BN_MONT_CTX *mont, BN_CTX *ctx); +#define BN_to_montgomery(r,a,mont,ctx) BN_mod_mul_montgomery(\ + (r),(a),&((mont)->RR),(mont),(ctx)) int BN_from_montgomery(BIGNUM *r,const BIGNUM *a, BN_MONT_CTX *mont, BN_CTX *ctx); void BN_MONT_CTX_free(BN_MONT_CTX *mont); @@ -518,4 +517,3 @@ void bn_dump1(FILE *o, const char *a, const BN_ULONG *b,int n); } #endif #endif - diff --git a/crypto/bn/bn_div.c b/crypto/bn/bn_div.c index 999bba756c..2e600c7c54 100644 --- a/crypto/bn/bn_div.c +++ b/crypto/bn/bn_div.c @@ -61,6 +61,7 @@ #include "cryptlib.h" #include "bn_lcl.h" + /* The old slow way */ #if 0 int BN_div(BIGNUM *dv, BIGNUM *rem, const BIGNUM *m, const BIGNUM *d, @@ -152,6 +153,14 @@ int BN_div(BIGNUM *dv, BIGNUM *rem, const BIGNUM *m, const BIGNUM *d, # endif /* __GNUC__ */ #endif /* NO_ASM */ + +/* BN_div 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. + */ int BN_div(BIGNUM *dv, BIGNUM *rm, const BIGNUM *num, const BIGNUM *divisor, BN_CTX *ctx) { @@ -331,7 +340,8 @@ int BN_div(BIGNUM *dv, BIGNUM *rm, const BIGNUM *num, const BIGNUM *divisor, if (rm != NULL) { BN_rshift(rm,snum,norm_shift); - rm->neg=num->neg; + if (!BN_is_zero(rm)) + rm->neg = num->neg; } BN_CTX_end(ctx); return(1); @@ -341,40 +351,3 @@ err: } #endif - -/* rem != m */ -int BN_mod(BIGNUM *rem, const BIGNUM *m, const BIGNUM *d, BN_CTX *ctx) - { -#if 0 /* The old slow way */ - int i,nm,nd; - BIGNUM *dv; - - if (BN_ucmp(m,d) < 0) - return((BN_copy(rem,m) == NULL)?0:1); - - BN_CTX_start(ctx); - dv=BN_CTX_get(ctx); - - if (!BN_copy(rem,m)) goto err; - - nm=BN_num_bits(rem); - nd=BN_num_bits(d); - if (!BN_lshift(dv,d,nm-nd)) goto err; - for (i=nm-nd; i>=0; i--) - { - if (BN_cmp(rem,dv) >= 0) - { - if (!BN_sub(rem,rem,dv)) goto err; - } - if (!BN_rshift1(dv,dv)) goto err; - } - BN_CTX_end(ctx); - return(1); - err: - BN_CTX_end(ctx); - return(0); -#else - return(BN_div(NULL,rem,m,d,ctx)); -#endif - } - diff --git a/crypto/bn/bn_exp.c b/crypto/bn/bn_exp.c index 74b1f0e89e..e6b3a5f5f9 100644 --- a/crypto/bn/bn_exp.c +++ b/crypto/bn/bn_exp.c @@ -110,37 +110,11 @@ */ -#include #include "cryptlib.h" #include "bn_lcl.h" #define TABLE_SIZE 32 -/* slow but works */ -int BN_mod_mul(BIGNUM *ret, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m, - BN_CTX *ctx) - { - BIGNUM *t; - int r=0; - - bn_check_top(a); - bn_check_top(b); - bn_check_top(m); - - BN_CTX_start(ctx); - if ((t = BN_CTX_get(ctx)) == NULL) goto err; - if (a == b) - { if (!BN_sqr(t,a,ctx)) goto err; } - else - { if (!BN_mul(t,a,b,ctx)) goto err; } - if (!BN_mod(ret,t,m,ctx)) goto err; - r=1; -err: - BN_CTX_end(ctx); - return(r); - } - - /* this one works - simple but works */ int BN_exp(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx) { @@ -186,6 +160,26 @@ int BN_mod_exp(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, const BIGNUM *m, bn_check_top(p); bn_check_top(m); + /* For even modulus m = 2^k*m_odd, it might make sense to compute + * a^p mod m_odd and a^p mod 2^k separately (with Montgomery + * exponentiation for the odd part), using appropriate exponent + * reductions, and combine the results using the CRT. + * + * For now, we use Montgomery only if the modulus is odd; otherwise, + * exponentiation using the reciprocal-based quick remaindering + * algorithm is used. + * + * (For computations a^p mod m where a, p, m are of the same + * length, BN_mod_exp_recp takes roughly 50 .. 70 % the time + * required by the standard algorithm, and BN_mod_exp takes + * about 33 .. 40 % of it. + * [Timings obtained with expspeed.c on a AMD K6-2 platform under Linux, + * with various OpenSSL debugging macros defined. YMMV.]) + */ + +#define MONT_MUL_MOD +#define RECP_MUL_MOD + #ifdef MONT_MUL_MOD /* I have finally been able to take out this pre-condition of * the top bit being set. It was caused by an error in BN_div @@ -195,7 +189,7 @@ int BN_mod_exp(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, const BIGNUM *m, if (BN_is_odd(m)) { - if (a->top == 1) + if (a->top == 1 && !a->neg) { BN_ULONG A = a->d[0]; ret=BN_mod_exp_mont_word(r,A,p,m,ctx,NULL); @@ -241,7 +235,7 @@ int BN_mod_exp_recp(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, BN_init(&(val[0])); ts=1; - if (!BN_mod(&(val[0]),a,m,ctx)) goto err; /* 1 */ + if (!BN_nnmod(&(val[0]),a,m,ctx)) goto err; /* 1 */ window = BN_window_bits_for_exponent_size(bits); if (window > 1) @@ -369,9 +363,9 @@ int BN_mod_exp_mont(BIGNUM *rr, const BIGNUM *a, const BIGNUM *p, BN_init(&val[0]); ts=1; - if (BN_ucmp(a,m) >= 0) + if (!a->neg && BN_ucmp(a,m) >= 0) { - if (!BN_mod(&(val[0]),a,m,ctx)) + if (!BN_nnmod(&(val[0]),a,m,ctx)) goto err; aa= &(val[0]); } @@ -613,7 +607,7 @@ int BN_mod_exp_simple(BIGNUM *r, BN_init(&(val[0])); ts=1; - if (!BN_mod(&(val[0]),a,m,ctx)) goto err; /* 1 */ + if (!BN_nnmod(&(val[0]),a,m,ctx)) goto err; /* 1 */ window = BN_window_bits_for_exponent_size(bits); if (window > 1) diff --git a/crypto/bn/bn_lib.c b/crypto/bn/bn_lib.c index 130a9e2db4..0e161d173e 100644 --- a/crypto/bn/bn_lib.c +++ b/crypto/bn/bn_lib.c @@ -561,6 +561,35 @@ BIGNUM *BN_copy(BIGNUM *a, const BIGNUM *b) return(a); } +void BN_swap(BIGNUM *a, BIGNUM *b) + { + int flags_old_a, flags_old_b; + BN_ULONG *tmp_d; + int tmp_top, tmp_dmax, tmp_neg; + + flags_old_a = a->flags; + flags_old_b = b->flags; + + tmp_d = a->d; + tmp_top = a->top; + tmp_dmax = a->dmax; + tmp_neg = a->neg; + + a->d = b->d; + a->top = b->top; + a->dmax = b->dmax; + a->neg = b->neg; + + b->d = tmp_d; + b->top = tmp_top; + b->dmax = tmp_dmax; + b->neg = tmp_neg; + + 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); + } + + void BN_clear(BIGNUM *a) { if (a->d != NULL) diff --git a/crypto/bn/bn_modfs.c b/crypto/bn/bn_modfs.c index c6986fb2e7..c7d5a73781 100644 --- a/crypto/bn/bn_modfs.c +++ b/crypto/bn/bn_modfs.c @@ -18,72 +18,6 @@ #define MAX_ROUNDS 10 -int BN_smod(BIGNUM *rem, BIGNUM *m, BIGNUM *d, BN_CTX *ctx) -{ - int r_sign; - - assert(rem != NULL && m != NULL && d != NULL && ctx != NULL); - - if (d->neg) return 0; - r_sign = m->neg; - - if (r_sign) m->neg = 0; - if (!(BN_div(NULL,rem,m,d,ctx))) return 0; - if (r_sign) - { - m->neg = r_sign; - if (!BN_is_zero(rem)) - { - rem->neg = r_sign; - BN_add(rem, rem, d); - } - } - return 1; -} - -int BN_mod_sub(BIGNUM *r, BIGNUM *a, BIGNUM *b, BIGNUM *m, BN_CTX *ctx) -{ - assert(r != NULL && a != NULL && b != NULL && m != NULL && ctx != NULL); - - if (!BN_sub(r, a, b)) return 0; - return BN_smod(r, r, m, ctx); - -} - -int BN_mod_add(BIGNUM *r, BIGNUM *a, BIGNUM *b, BIGNUM *m, BN_CTX *ctx) -{ - assert(r != NULL && a != NULL && b != NULL && m != NULL && ctx != NULL); - - if (!BN_add(r, a, b)) return 0; - return BN_smod(r, r, m, ctx); - -} - -int BN_mod_sqr(BIGNUM *r, BIGNUM *a, BIGNUM *p, BN_CTX *ctx) -{ - assert(r != NULL && a != NULL && p != NULL && ctx != NULL); - - if (!BN_sqr(r, a, ctx)) return 0; - return BN_div(NULL, r, r, p, ctx); -} - -int BN_swap(BIGNUM *x, BIGNUM *y) -{ - BIGNUM *c; - - assert(x != NULL && y != NULL); - - if ((c = BN_dup(x)) == NULL) goto err; - if ((BN_copy(x, y)) == NULL) goto err; - if ((BN_copy(y, c)) == NULL) goto err; - BN_clear_free(c); - return 1; - -err: - if (c != NULL) BN_clear_free(c); - return 0; -} - int BN_legendre(BIGNUM *a, BIGNUM *p, BN_CTX *ctx) { @@ -99,7 +33,7 @@ int BN_legendre(BIGNUM *a, BIGNUM *p, BN_CTX *ctx) ctx->tos += 3; - if (!BN_smod(x, a, p, ctx)) goto err; + if (!BN_nnmod(x, a, p, ctx)) goto err; if (BN_is_zero(x)) { @@ -136,7 +70,7 @@ int BN_legendre(BIGNUM *a, BIGNUM *p, BN_CTX *ctx) if (BN_mod_word(x, 4) == 3 && BN_mod_word(y, 4) == 3) L = -L; if (!BN_swap(x, y)) goto err; - if (!BN_smod(x, x, y, ctx)) goto err; + if (!BN_nnmod(x, x, y, ctx)) goto err; } diff --git a/crypto/bn/bn_modfs.h b/crypto/bn/bn_modfs.h index c596ca3973..f03e4de8dc 100644 --- a/crypto/bn/bn_modfs.h +++ b/crypto/bn/bn_modfs.h @@ -1,32 +1,22 @@ -/* - * - * bn_modfs.h - * - * Some Modular Arithmetic Functions. - * - * Copyright (C) Lenka Fibikova 2000 - * - * - */ - -#ifndef HEADER_BN_MODFS_H -#define HEADER_BN_MODFS_H - - -#include "bn.h" - -#ifdef BN_is_zero -#undef BN_is_zero -#define BN_is_zero(a) (((a)->top == 0) || (((a)->top == 1) && ((a)->d[0] == (BN_ULONG)0))) -#endif /*BN_is_zero(a)*/ - - -int BN_smod(BIGNUM *rem, BIGNUM *m, BIGNUM *d, BN_CTX *ctx); -int BN_mod_sub(BIGNUM *r, BIGNUM *a, BIGNUM *b, BIGNUM *m, BN_CTX *ctx); -int BN_mod_add(BIGNUM *r, BIGNUM *a, BIGNUM *b, BIGNUM *m, BN_CTX *ctx); -int BN_mod_sqr(BIGNUM *r, BIGNUM *a, BIGNUM *p, BN_CTX *ctx); -int BN_swap(BIGNUM *x, BIGNUM *y); -int BN_legendre(BIGNUM *a, BIGNUM *p, BN_CTX *ctx); -int BN_mod_sqrt(BIGNUM *x, BIGNUM *a, BIGNUM *p, BN_CTX *ctx); - -#endif \ No newline at end of file +/* + * + * bn_modfs.h + * + * Some Modular Arithmetic Functions. + * + * Copyright (C) Lenka Fibikova 2000 + * + * + */ + +#ifndef HEADER_BN_MODFS_H +#define HEADER_BN_MODFS_H + + +#include "bn.h" + + +int BN_legendre(BIGNUM *a, BIGNUM *p, BN_CTX *ctx); +int BN_mod_sqrt(BIGNUM *x, BIGNUM *a, BIGNUM *p, BN_CTX *ctx); + +#endif diff --git a/crypto/bn/bn_recp.c b/crypto/bn/bn_recp.c index a175e1c5f2..0700a0f063 100644 --- a/crypto/bn/bn_recp.c +++ b/crypto/bn/bn_recp.c @@ -167,7 +167,8 @@ int BN_div_recp(BIGNUM *dv, BIGNUM *rem, const BIGNUM *m, if (i != recp->shift) recp->shift=BN_reciprocal(&(recp->Nr),&(recp->N), - i,ctx); + i,ctx); /* BN_reciprocal returns i, or -1 for an error */ + if (recp->shift == -1) goto err; if (!BN_rshift(a,m,j)) goto err; if (!BN_mul(b,a,&(recp->Nr),ctx)) goto err; @@ -203,6 +204,7 @@ err: * We actually calculate with an extra word of precision, so * we can do faster division if the remainder is not required. */ +/* r := 2^len / m */ int BN_reciprocal(BIGNUM *r, const BIGNUM *m, int len, BN_CTX *ctx) { int ret= -1; diff --git a/crypto/bn/bn_sqr.c b/crypto/bn/bn_sqr.c index eb52c4e828..b75e6194d0 100644 --- a/crypto/bn/bn_sqr.c +++ b/crypto/bn/bn_sqr.c @@ -88,7 +88,6 @@ int BN_sqr(BIGNUM *r, const BIGNUM *a, BN_CTX *ctx) max=(al+al); if (bn_wexpand(rr,max+1) == NULL) goto err; - r->neg=0; if (al == 4) { #ifndef BN_SQR_COMBA @@ -140,6 +139,7 @@ int BN_sqr(BIGNUM *r, const BIGNUM *a, BN_CTX *ctx) } rr->top=max; + rr->neg=0; if ((max > 0) && (rr->d[max-1] == 0)) rr->top--; if (rr != r) BN_copy(r,rr); ret = 1; diff --git a/crypto/bn/expspeed.c b/crypto/bn/expspeed.c index 2044ab9bff..e9c1fee7ab 100644 --- a/crypto/bn/expspeed.c +++ b/crypto/bn/expspeed.c @@ -187,9 +187,6 @@ void do_mul_exp(BIGNUM *r, BIGNUM *a, BIGNUM *b, BIGNUM *c, BN_CTX *ctx) int i,k; double tm; long num; - BN_MONT_CTX m; - - memset(&m,0,sizeof(m)); num=BASENUM; for (i=0; i %8.3fms %5.1f\n",sizes[i],sizes[i],sizes[i],tm*1000.0/num,tm*mul_c[i]/num); num/=7; diff --git a/doc/crypto/BN_add.pod b/doc/crypto/BN_add.pod index 0541d45643..4c8db25f70 100644 --- a/doc/crypto/BN_add.pod +++ b/doc/crypto/BN_add.pod @@ -2,8 +2,9 @@ =head1 NAME -BN_add, BN_sub, BN_mul, BN_div, BN_sqr, BN_mod, BN_mod_mul, BN_exp, -BN_mod_exp, BN_gcd - arithmetic operations on BIGNUMs +BN_add, BN_sub, BN_mul, BN_sqr, BN_div, BN_mod, BN_nnmod, BN_mod_add, +BN_mod_sub, BN_mod_mul, BN_mod_sqr, BN_exp, BN_mod_exp, BN_gcd - +arithmetic operations on BIGNUMs =head1 SYNOPSIS @@ -15,16 +16,26 @@ BN_mod_exp, BN_gcd - arithmetic operations on BIGNUMs int BN_mul(BIGNUM *r, BIGNUM *a, BIGNUM *b, BN_CTX *ctx); + int BN_sqr(BIGNUM *r, BIGNUM *a, BN_CTX *ctx); + int BN_div(BIGNUM *dv, BIGNUM *rem, const BIGNUM *a, const BIGNUM *d, BN_CTX *ctx); - int BN_sqr(BIGNUM *r, BIGNUM *a, BN_CTX *ctx); - int BN_mod(BIGNUM *rem, const BIGNUM *a, const BIGNUM *m, BN_CTX *ctx); - int BN_mod_mul(BIGNUM *ret, BIGNUM *a, BIGNUM *b, const BIGNUM *m, + int BN_nnmod(BIGNUM *rem, const BIGNUM *a, const BIGNUM *m, BN_CTX *ctx); + + int BN_mod_add(BIGNUM *r, BIGNUM *a, BIGNUM *b, const BIGNUM *m, + BN_CTX *ctx); + + int BN_mod_sub(BIGNUM *r, BIGNUM *a, BIGNUM *b, const BIGNUM *m, + BN_CTX *ctx); + + int BN_mod_mul(BIGNUM *r, BIGNUM *a, BIGNUM *b, const BIGNUM *m, BN_CTX *ctx); + int BN_mod_sqr(BIGNUM *r, BIGNUM *a, const BIGNUM *m, BN_CTX *ctx); + int BN_exp(BIGNUM *r, BIGNUM *a, BIGNUM *p, BN_CTX *ctx); int BN_mod_exp(BIGNUM *r, BIGNUM *a, const BIGNUM *p, @@ -34,45 +45,58 @@ BN_mod_exp, BN_gcd - arithmetic operations on BIGNUMs =head1 DESCRIPTION -BN_add() adds B and B and places the result in B (C). -B may be the same B as B or B. +BN_add() adds I and I and places the result in I (C). +I may be the same B as I or I. -BN_sub() subtracts B from B and places the result in B (C). +BN_sub() subtracts I from I and places the result in I (C). -BN_mul() multiplies B and B and places the result in B (C). -B may be the same B as B or B. +BN_mul() multiplies I and I and places the result in I (C). +I may be the same B as I or I. For multiplication by powers of 2, use L. -BN_div() divides B by B and places the result in B and the -remainder in B (C). Either of B and B may -be NULL, in which case the respective value is not returned. +BN_sqr() takes the square of I and places the result in I +(C). I and I may be the same B. +This function is faster than BN_mul(r,a,a). + +BN_div() divides I by I and places the result in I and the +remainder in I (C). Either of I and I may +be B, in which case the respective value is not returned. +The result is rounded towards zero; thus if I is negative, the +remainder will be zero or negative. For division by powers of 2, use BN_rshift(3). -BN_sqr() takes the square of B and places the result in B -(C). B and B may be the same B. -This function is faster than BN_mul(r,a,a). +BN_mod() corresponds to BN_div() with I set to B. + +BN_nnmod() finds the non-negative remainder of I divided by I. + +BN_mod_add() adds I to I modulo I and places the non-negative +result in I. + +BN_mod_sub() substracts I from I modulo I and places the +non-negative result in I. -BN_mod() find the remainder of B divided by B and places it in -B (C). +BN_mod_mul() multiplies I by I and finds the non-negative +remainder respective to modulus I (C). I may be +the same B as I or I. For more efficient algorithms for +repeated computations using the same modulus, see +L and +L. -BN_mod_mul() multiplies B by B and finds the remainder when -divided by B (C). B may be the same B as B -or B. For a more efficient algorithm, see -L; for repeated -computations using the same modulus, see L. +BN_mod_sqr() takes the square of I modulo B and places the +result in I. -BN_exp() raises B to the B

-th power and places the result in B +BN_exp() raises I to the I

-th power and places the result in I (C). This function is faster than repeated applications of BN_mul(). -BN_mod_exp() computes B to the B

-th power modulo B (C to the I

-th power modulo I (C). This function uses less time and space than BN_exp(). -BN_gcd() computes the greatest common divisor of B and B and -places the result in B. B may be the same B as B or -B. +BN_gcd() computes the greatest common divisor of I and I and +places the result in I. I may be the same B as I or +I. -For all functions, B is a previously allocated B used for +For all functions, I is a previously allocated B used for temporary variables; see L. Unless noted otherwise, the result B must be different from @@ -91,9 +115,11 @@ L, L =head1 HISTORY -BN_add(), BN_sub(), BN_div(), BN_sqr(), BN_mod(), BN_mod_mul(), +BN_add(), BN_sub(), BN_sqr(), BN_div(), BN_mod(), BN_mod_mul(), BN_mod_exp() and BN_gcd() are available in all versions of SSLeay and -OpenSSL. The B argument to BN_mul() was added in SSLeay +OpenSSL. The I argument to BN_mul() was added in SSLeay 0.9.1b. BN_exp() appeared in SSLeay 0.9.0. +BN_nnmod(), BN_mod_add(), BN_mod_sub(), and BN_mod_sqr() were added in +OpenSSL 0.9.7. =cut diff --git a/doc/crypto/BN_mod_mul_montgomery.pod b/doc/crypto/BN_mod_mul_montgomery.pod index 0b8ab512df..6452470076 100644 --- a/doc/crypto/BN_mod_mul_montgomery.pod +++ b/doc/crypto/BN_mod_mul_montgomery.pod @@ -36,22 +36,23 @@ using the same modulus. BN_MONT_CTX_new() allocates and initializes a B structure. BN_MONT_CTX_init() initializes an existing uninitialized B. -BN_MONT_CTX_set() sets up the B structure from the modulus B +BN_MONT_CTX_set() sets up the I structure from the modulus I by precomputing its inverse and a value R. -BN_MONT_CTX_copy() copies the B B to B. +BN_MONT_CTX_copy() copies the B I to I. BN_MONT_CTX_free() frees the components of the B, and, if it was created by BN_MONT_CTX_new(), also the structure itself. -BN_mod_mul_montgomery() computes Mont(B,B):=B*B*R^-1 and places -the result in B. +BN_mod_mul_montgomery() computes Mont(I,I):=I*I*R^-1 and places +the result in I. -BN_from_montgomery() performs the Montgomery reduction B = B*R^-1. +BN_from_montgomery() performs the Montgomery reduction I = I*R^-1. -BN_to_montgomery() computes Mont(B,R^2), i.e. B*R. +BN_to_montgomery() computes Mont(I,R^2), i.e. I*R. +Note that I must be non-negative and smaller than the modulus. -For all functions, B is a previously allocated B used for +For all functions, I is a previously allocated B used for temporary variables. The B structure is defined as follows: diff --git a/doc/crypto/bn.pod b/doc/crypto/bn.pod index 1504a1c92d..224dfe166a 100644 --- a/doc/crypto/bn.pod +++ b/doc/crypto/bn.pod @@ -21,19 +21,27 @@ bn - multiprecision integer arithmetics BIGNUM *BN_copy(BIGNUM *a, const BIGNUM *b); BIGNUM *BN_dup(const BIGNUM *a); + BIGNUM *BN_swap(BIGNUM *a, BIGNUM *b); + int BN_num_bytes(const BIGNUM *a); int BN_num_bits(const BIGNUM *a); int BN_num_bits_word(BN_ULONG w); - int BN_add(BIGNUM *r, BIGNUM *a, BIGNUM *b); + int BN_add(BIGNUM *r, const BIGNUM *a, const BIGNUM *b); int BN_sub(BIGNUM *r, const BIGNUM *a, const BIGNUM *b); int BN_mul(BIGNUM *r, BIGNUM *a, BIGNUM *b, BN_CTX *ctx); + int BN_sqr(BIGNUM *r, BIGNUM *a, BN_CTX *ctx); int BN_div(BIGNUM *dv, BIGNUM *rem, const BIGNUM *a, const BIGNUM *d, BN_CTX *ctx); - int BN_sqr(BIGNUM *r, BIGNUM *a, BN_CTX *ctx); int BN_mod(BIGNUM *rem, const BIGNUM *a, const BIGNUM *m, BN_CTX *ctx); + int BN_nnmod(BIGNUM *rem, const BIGNUM *a, const BIGNUM *m, BN_CTX *ctx); + int BN_mod_add(BIGNUM *ret, BIGNUM *a, BIGNUM *b, const BIGNUM *m, + BN_CTX *ctx); + int BN_mod_sub(BIGNUM *ret, BIGNUM *a, BIGNUM *b, const BIGNUM *m, + BN_CTX *ctx); int BN_mod_mul(BIGNUM *ret, BIGNUM *a, BIGNUM *b, const BIGNUM *m, BN_CTX *ctx); + int BN_mod_sqr(BIGNUM *ret, BIGNUM *a, const BIGNUM *m, BN_CTX *ctx); int BN_exp(BIGNUM *r, BIGNUM *a, BIGNUM *p, BN_CTX *ctx); int BN_mod_exp(BIGNUM *r, BIGNUM *a, const BIGNUM *p, const BIGNUM *m, BN_CTX *ctx); @@ -137,7 +145,7 @@ of Bs to external formats is described in L. L, L, L, L, L, L, L, -L, L, +L, L, L, L, L, L, L, L, L, L, diff --git a/ssl/ssl.h b/ssl/ssl.h index 2bc994a0f4..297f8e8ec8 100644 --- a/ssl/ssl.h +++ b/ssl/ssl.h @@ -1414,6 +1414,13 @@ int SSL_COMP_add_compression_method(int id,char *cm); #define SSL_R_INVALID_COMMAND 280 #define SSL_R_INVALID_PURPOSE 278 #define SSL_R_INVALID_TRUST 279 +#define SSL_R_KRB5_C_CC_PRINC 1094 +#define SSL_R_KRB5_C_GET_CRED 1095 +#define SSL_R_KRB5_C_INIT 1096 +#define SSL_R_KRB5_C_MK_REQ 1097 +#define SSL_R_KRB5_S_BAD_TICKET 1098 +#define SSL_R_KRB5_S_INIT 1099 +#define SSL_R_KRB5_S_RD_REQ 1100 #define SSL_R_LENGTH_MISMATCH 159 #define SSL_R_LENGTH_TOO_SHORT 160 #define SSL_R_LIBRARY_BUG 274 diff --git a/ssl/ssl_err.c b/ssl/ssl_err.c index 17b4caf528..f3edd5aed1 100644 --- a/ssl/ssl_err.c +++ b/ssl/ssl_err.c @@ -269,6 +269,13 @@ static ERR_STRING_DATA SSL_str_reasons[]= {SSL_R_INVALID_COMMAND ,"invalid command"}, {SSL_R_INVALID_PURPOSE ,"invalid purpose"}, {SSL_R_INVALID_TRUST ,"invalid trust"}, +{SSL_R_KRB5_C_CC_PRINC ,"krb5 c cc princ"}, +{SSL_R_KRB5_C_GET_CRED ,"krb5 c get cred"}, +{SSL_R_KRB5_C_INIT ,"krb5 c init"}, +{SSL_R_KRB5_C_MK_REQ ,"krb5 c mk req"}, +{SSL_R_KRB5_S_BAD_TICKET ,"krb5 s bad ticket"}, +{SSL_R_KRB5_S_INIT ,"krb5 s init"}, +{SSL_R_KRB5_S_RD_REQ ,"krb5 s rd req"}, {SSL_R_LENGTH_MISMATCH ,"length mismatch"}, {SSL_R_LENGTH_TOO_SHORT ,"length too short"}, {SSL_R_LIBRARY_BUG ,"library bug"}, diff --git a/util/libeay.num b/util/libeay.num index 4e2ab52e6b..7a86fc69b4 100755 --- a/util/libeay.num +++ b/util/libeay.num @@ -2056,3 +2056,7 @@ rijndaelKeyEncToDec 2644 EXIST::FUNCTION: rijndaelDecryptRound 2645 EXIST::FUNCTION: rijndaelEncrypt 2646 EXIST::FUNCTION: rijndaelKeySched 2647 EXIST::FUNCTION: +OBJ_NAME_do_all_sorted 2648 EXIST::FUNCTION: +OBJ_NAME_do_all 2649 EXIST::FUNCTION: +BN_nnmod 2650 EXIST::FUNCTION: +BN_swap 2651 EXIST::FUNCTION: -- 2.25.1