modular arithmetics
authorBodo Möller <bodo@openssl.org>
Sun, 26 Nov 2000 16:42:38 +0000 (16:42 +0000)
committerBodo Möller <bodo@openssl.org>
Sun, 26 Nov 2000 16:42:38 +0000 (16:42 +0000)
"make update"

18 files changed:
CHANGES
TABLE
crypto/bn/Makefile.ssl
crypto/bn/bn.h
crypto/bn/bn_div.c
crypto/bn/bn_exp.c
crypto/bn/bn_lib.c
crypto/bn/bn_modfs.c
crypto/bn/bn_modfs.h
crypto/bn/bn_recp.c
crypto/bn/bn_sqr.c
crypto/bn/expspeed.c
doc/crypto/BN_add.pod
doc/crypto/BN_mod_mul_montgomery.pod
doc/crypto/bn.pod
ssl/ssl.h
ssl/ssl_err.c
util/libeay.num

diff --git a/CHANGES b/CHANGES
index c54ab99..e37d299 100644 (file)
--- 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 <fibikova@exp-math.uni-essen.de>, 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 7a397ae..9b07db9 100644 (file)
--- 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
index ad36267..89bd67b 100644 (file)
@@ -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
index 857ade3..0a665c2 100644 (file)
@@ -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
-
index 999bba7..2e600c7 100644 (file)
@@ -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
-       }
-
index 74b1f0e..e6b3a5f 100644 (file)
  */
 
 
-#include <stdio.h>
 #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)
index 130a9e2..0e161d1 100644 (file)
@@ -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)
index c6986fb..c7d5a73 100644 (file)
 
 #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;
 
        }
 
index c596ca3..f03e4de 100644 (file)
@@ -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
+/*\r
+ *\r
+ *     bn_modfs.h\r
+ *\r
+ *     Some Modular Arithmetic Functions.\r
+ *\r
+ *     Copyright (C) Lenka Fibikova 2000\r
+ *\r
+ *\r
+ */\r
+\r
+#ifndef HEADER_BN_MODFS_H\r
+#define HEADER_BN_MODFS_H\r
+\r
+\r
+#include "bn.h"\r
+\r
+\r
+int BN_legendre(BIGNUM *a, BIGNUM *p, BN_CTX *ctx);\r
+int BN_mod_sqrt(BIGNUM *x, BIGNUM *a, BIGNUM *p, BN_CTX *ctx);\r
+\r
+#endif\r
index a175e1c..0700a0f 100644 (file)
@@ -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;
index eb52c4e..b75e619 100644 (file)
@@ -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;
index 2044ab9..e9c1fee 100644 (file)
@@ -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<NUM_SIZES; i++)
@@ -200,11 +197,9 @@ void do_mul_exp(BIGNUM *r, BIGNUM *a, BIGNUM *b, BIGNUM *c, BN_CTX *ctx)
                BN_mod(a,a,c,ctx);
                BN_mod(b,b,c,ctx);
 
-               BN_MONT_CTX_set(&m,c,ctx);
-
                Time_F(START);
                for (k=0; k<num; k++)
-                       BN_mod_exp_mont(r,a,b,c,ctx,&m);
+                       BN_mod_exp(r,a,b,c,ctx);
                tm=Time_F(STOP);
                printf("mul %4d ^ %4d %% %d -> %8.3fms %5.1f\n",sizes[i],sizes[i],sizes[i],tm*1000.0/num,tm*mul_c[i]/num);
                num/=7;
index 0541d45..4c8db25 100644 (file)
@@ -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<a> and B<b> and places the result in B<r> (C<r=a+b>).
-B<r> may be the same B<BIGNUM> as B<a> or B<b>.
+BN_add() adds I<a> and I<b> and places the result in I<r> (C<r=a+b>).
+I<r> may be the same B<BIGNUM> as I<a> or I<b>.
 
-BN_sub() subtracts B<b> from B<a> and places the result in B<r> (C<r=a-b>).
+BN_sub() subtracts I<b> from I<a> and places the result in I<r> (C<r=a-b>).
 
-BN_mul() multiplies B<a> and B<b> and places the result in B<r> (C<r=a*b>).
-B<r> may be the same B<BIGNUM> as B<a> or B<b>.
+BN_mul() multiplies I<a> and I<b> and places the result in I<r> (C<r=a*b>).
+I<r> may be the same B<BIGNUM> as I<a> or I<b>.
 For multiplication by powers of 2, use L<BN_lshift(3)|BN_lshift(3)>.
 
-BN_div() divides B<a> by B<d> and places the result in B<dv> and the
-remainder in B<rem> (C<dv=a/d, rem=a%d>). Either of B<dv> and B<rem> may
-be NULL, in which case the respective value is not returned.
+BN_sqr() takes the square of I<a> and places the result in I<r>
+(C<r=a^2>). I<r> and I<a> may be the same B<BIGNUM>.
+This function is faster than BN_mul(r,a,a).
+
+BN_div() divides I<a> by I<d> and places the result in I<dv> and the
+remainder in I<rem> (C<dv=a/d, rem=a%d>). Either of I<dv> and I<rem> may
+be B<NULL>, in which case the respective value is not returned.
+The result is rounded towards zero; thus if I<a> 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<a> and places the result in B<r>
-(C<r=a^2>). B<r> and B<a> may be the same B<BIGNUM>.
-This function is faster than BN_mul(r,a,a).
+BN_mod() corresponds to BN_div() with I<dv> set to B<NULL>.
+
+BN_nnmod() finds the non-negative remainder of I<a> divided by I<m>.
+
+BN_mod_add() adds I<a> to I<b> modulo I<m> and places the non-negative
+result in I<r>.
+
+BN_mod_sub() substracts I<b> from I<a> modulo I<m> and places the
+non-negative result in I<r>.
 
-BN_mod() find the remainder of B<a> divided by B<m> and places it in
-B<rem> (C<rem=a%m>).
+BN_mod_mul() multiplies I<a> by I<b> and finds the non-negative
+remainder respective to modulus I<m> (C<r=(a*b) mod m>). I<r> may be
+the same B<BIGNUM> as I<a> or I<b>. For more efficient algorithms for
+repeated computations using the same modulus, see
+L<BN_mod_mul_montgomery(3)|BN_mod_mul_montgomery(3)> and
+L<BN_mod_mul_reciprocal(3)|BN_mod_mul_reciprocal(3)>.
 
-BN_mod_mul() multiplies B<a> by B<b> and finds the remainder when
-divided by B<m> (C<r=(a*b)%m>). B<r> may be the same B<BIGNUM> as B<a>
-or B<b>. For a more efficient algorithm, see
-L<BN_mod_mul_montgomery(3)|BN_mod_mul_montgomery(3)>; for repeated
-computations using the same modulus, see L<BN_mod_mul_reciprocal(3)|BN_mod_mul_reciprocal(3)>.
+BN_mod_sqr() takes the square of I<a> modulo B<m> and places the
+result in I<r>.
 
-BN_exp() raises B<a> to the B<p>-th power and places the result in B<r>
+BN_exp() raises I<a> to the I<p>-th power and places the result in I<r>
 (C<r=a^p>). This function is faster than repeated applications of
 BN_mul().
 
-BN_mod_exp() computes B<a> to the B<p>-th power modulo B<m> (C<r=a^p %
+BN_mod_exp() computes I<a> to the I<p>-th power modulo I<m> (C<r=a^p %
 m>). This function uses less time and space than BN_exp().
 
-BN_gcd() computes the greatest common divisor of B<a> and B<b> and
-places the result in B<r>. B<r> may be the same B<BIGNUM> as B<a> or
-B<b>.
+BN_gcd() computes the greatest common divisor of I<a> and I<b> and
+places the result in I<r>. I<r> may be the same B<BIGNUM> as I<a> or
+I<b>.
 
-For all functions, B<ctx> is a previously allocated B<BN_CTX> used for
+For all functions, I<ctx> is a previously allocated B<BN_CTX> used for
 temporary variables; see L<BN_CTX_new(3)|BN_CTX_new(3)>.
 
 Unless noted otherwise, the result B<BIGNUM> must be different from
@@ -91,9 +115,11 @@ L<BN_add_word(3)|BN_add_word(3)>, L<BN_set_bit(3)|BN_set_bit(3)>
 
 =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<ctx> argument to BN_mul() was added in SSLeay
+OpenSSL. The I<ctx> 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
index 0b8ab51..6452470 100644 (file)
@@ -36,22 +36,23 @@ using the same modulus.
 BN_MONT_CTX_new() allocates and initializes a B<BN_MONT_CTX> structure.
 BN_MONT_CTX_init() initializes an existing uninitialized B<BN_MONT_CTX>.
 
-BN_MONT_CTX_set() sets up the B<mont> structure from the modulus B<m>
+BN_MONT_CTX_set() sets up the I<mont> structure from the modulus I<m>
 by precomputing its inverse and a value R.
 
-BN_MONT_CTX_copy() copies the B<BN_MONT_CTX> B<from> to B<to>.
+BN_MONT_CTX_copy() copies the B<BN_MONT_CTX> I<from> to I<to>.
 
 BN_MONT_CTX_free() frees the components of the B<BN_MONT_CTX>, and, if
 it was created by BN_MONT_CTX_new(), also the structure itself.
 
-BN_mod_mul_montgomery() computes Mont(B<a>,B<b>):=B<a>*B<b>*R^-1 and places
-the result in B<r>.
+BN_mod_mul_montgomery() computes Mont(I<a>,I<b>):=I<a>*I<b>*R^-1 and places
+the result in I<r>.
 
-BN_from_montgomery() performs the Montgomery reduction B<r> = B<a>*R^-1.
+BN_from_montgomery() performs the Montgomery reduction I<r> = I<a>*R^-1.
 
-BN_to_montgomery() computes Mont(B<a>,R^2), i.e. B<a>*R.
+BN_to_montgomery() computes Mont(I<a>,R^2), i.e. I<a>*R.
+Note that I<a> must be non-negative and smaller than the modulus.
 
-For all functions, B<ctx> is a previously allocated B<BN_CTX> used for
+For all functions, I<ctx> is a previously allocated B<BN_CTX> used for
 temporary variables.
 
 The B<BN_MONT_CTX> structure is defined as follows:
index 1504a1c..224dfe1 100644 (file)
@@ -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 B<BIGNUM>s to external formats is described in L<BN_bn2bin(3)|BN_bn2bin(3)>.
 L<bn_internal(3)|bn_internal(3)>,
 L<dh(3)|dh(3)>, L<err(3)|err(3)>, L<rand(3)|rand(3)>, L<rsa(3)|rsa(3)>,
 L<BN_new(3)|BN_new(3)>, L<BN_CTX_new(3)|BN_CTX_new(3)>,
-L<BN_copy(3)|BN_copy(3)>, L<BN_num_bytes(3)|BN_num_bytes(3)>,
+L<BN_copy(3)|BN_copy(3)>, L<BN_swap(3)|BN_swap(3)>, L<BN_num_bytes(3)|BN_num_bytes(3)>,
 L<BN_add(3)|BN_add(3)>, L<BN_add_word(3)|BN_add_word(3)>,
 L<BN_cmp(3)|BN_cmp(3)>, L<BN_zero(3)|BN_zero(3)>, L<BN_rand(3)|BN_rand(3)>,
 L<BN_generate_prime(3)|BN_generate_prime(3)>, L<BN_set_bit(3)|BN_set_bit(3)>,
index 2bc994a..297f8e8 100644 (file)
--- 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
index 17b4caf..f3edd5a 100644 (file)
@@ -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"},
index 4e2ab52..7a86fc6 100755 (executable)
@@ -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: