Speed up DH with small generator.

diff --git a/CHANGES b/CHANGES
index 9f6560b882429aa0d3d7ea4b6b67579c928ef871..f1cfe73a80c17235980e5dffcd1cb4d731bb98d4 100644 (file)
--- a/CHANGES
+++ b/CHANGES
@@ -4,6 +4,11 @@
 
  Changes between 0.9.5a and 0.9.6  [xx XXX 2000]
 
+  *) New function BN_mod_exp_mont_word for small bases (roughly 20%
+     faster than BN_mod_exp_mont even though it does not use
+     windowing).
+     [Bodo Moeller]
+
   *) CygWin32 support.
      [John Jarvie <jjarvie@newsguy.com>]
 

diff --git a/crypto/bn/bn.h b/crypto/bn/bn.h
index 9fa995c64f0db0bffd6618652c97d4c8732807fa..000ff48155f076fcee92da9e6e8a20cfc90e1b84 100644 (file)
--- a/crypto/bn/bn.h
+++ b/crypto/bn/bn.h
@@ -364,6 +364,8 @@ int BN_mod_exp(BIGNUM *r, BIGNUM *a, const BIGNUM *p,
                   const BIGNUM *m,BN_CTX *ctx);
 int    BN_mod_exp_mont(BIGNUM *r, BIGNUM *a, const BIGNUM *p,
                        const BIGNUM *m, BN_CTX *ctx, BN_MONT_CTX *m_ctx);
+int    BN_mod_exp_mont_word(BIGNUM *r, BN_ULONG a, const BIGNUM *p,
+                       const BIGNUM *m, BN_CTX *ctx, BN_MONT_CTX *m_ctx);
 int    BN_mod_exp2_mont(BIGNUM *r, BIGNUM *a1, BIGNUM *p1,BIGNUM *a2,
                BIGNUM *p2,BIGNUM *m,BN_CTX *ctx,BN_MONT_CTX *m_ctx);
 int    BN_mod_exp_simple(BIGNUM *r, BIGNUM *a, BIGNUM *p,
@@ -484,6 +486,7 @@ BN_ULONG bn_sub_words(BN_ULONG *rp, BN_ULONG *ap, BN_ULONG *bp,int num);
 #define BN_F_BN_DIV                                     107
 #define BN_F_BN_EXPAND2                                         108
 #define BN_F_BN_MOD_EXP_MONT                            109
+#define BN_F_BN_MOD_EXP_MONT_WORD                       117
 #define BN_F_BN_MOD_INVERSE                             110
 #define BN_F_BN_MOD_MUL_RECIPROCAL                      111
 #define BN_F_BN_MPI2BN                                  112

diff --git a/crypto/bn/bn_err.c b/crypto/bn/bn_err.c
index 988270bcf4f7ca2d353f933b4266f5ffb6aea204..e0cbd70b7dbec5e0ceade5a33ec414358cc2dc7f 100644 (file)
--- a/crypto/bn/bn_err.c
+++ b/crypto/bn/bn_err.c
@@ -77,6 +77,7 @@ static ERR_STRING_DATA BN_str_functs[]=
 {ERR_PACK(0,BN_F_BN_DIV,0),    "BN_div"},
 {ERR_PACK(0,BN_F_BN_EXPAND2,0),        "bn_expand2"},
 {ERR_PACK(0,BN_F_BN_MOD_EXP_MONT,0),   "BN_mod_exp_mont"},
+{ERR_PACK(0,BN_F_BN_MOD_EXP_MONT_WORD,0),      "BN_MOD_EXP_MONT_WORD"},
 {ERR_PACK(0,BN_F_BN_MOD_INVERSE,0),    "BN_mod_inverse"},
 {ERR_PACK(0,BN_F_BN_MOD_MUL_RECIPROCAL,0),     "BN_mod_mul_reciprocal"},
 {ERR_PACK(0,BN_F_BN_MPI2BN,0), "BN_mpi2bn"},

diff --git a/crypto/bn/bn_exp.c b/crypto/bn/bn_exp.c
index 0c11601675493bef66c3f88a6bf1c7c88f642b5c..96f34fa529b7cfc699571f97c0cb63a9df9ac296 100644 (file)
--- a/crypto/bn/bn_exp.c
+++ b/crypto/bn/bn_exp.c
@@ -66,6 +66,7 @@
 # include <dlfcn.h>
 #endif
 
+
 #define TABLE_SIZE     16
 
 /* slow but works */
@@ -91,42 +92,6 @@ err:
        return(r);
        }
 
-#if 0
-/* this one works - simple but works */
-int BN_mod_exp(BIGNUM *r, BIGNUM *a, BIGNUM *p, BIGNUM *m, BN_CTX *ctx)
-       {
-       int i,bits,ret=0;
-       BIGNUM *v,*tmp;
-
-       BN_CTX_start(ctx);
-       v = BN_CTX_get(ctx);
-       tmp = BN_CTX_get(ctx);
-       if (v == NULL || tmp == NULL) goto err;
-
-       if (BN_copy(v,a) == NULL) goto err;
-       bits=BN_num_bits(p);
-
-       if (BN_is_odd(p))
-               { if (BN_copy(r,a) == NULL) goto err; }
-       else    { if (!BN_one(r)) goto err; }
-
-       for (i=1; i<bits; i++)
-               {
-               if (!BN_sqr(tmp,v,ctx)) goto err;
-               if (!BN_mod(v,tmp,m,ctx)) goto err;
-               if (BN_is_bit_set(p,i))
-                       {
-                       if (!BN_mul(tmp,r,v,ctx)) goto err;
-                       if (!BN_mod(r,tmp,m,ctx)) goto err;
-                       }
-               }
-       ret=1;
-err:
-       BN_CTX_end(ctx);
-       return(ret);
-       }
-
-#endif
 
 /* this one works - simple but works */
 int BN_exp(BIGNUM *r, BIGNUM *a, BIGNUM *p, BN_CTX *ctx)
@@ -163,6 +128,7 @@ err:
        return(ret);
        }
 
+
 #ifdef ATALLA
 
 /*
@@ -330,6 +296,7 @@ int BN_mod_exp_atalla(BIGNUM *r, BIGNUM *a, const BIGNUM *p, const BIGNUM *m)
         }
 #endif /* def ATALLA */
 
+
 int BN_mod_exp(BIGNUM *r, BIGNUM *a, const BIGNUM *p, const BIGNUM *m,
               BN_CTX *ctx)
        {
@@ -354,7 +321,15 @@ int BN_mod_exp(BIGNUM *r, BIGNUM *a, const BIGNUM *p, const BIGNUM *m,
 /*     if ((m->d[m->top-1]&BN_TBIT) && BN_is_odd(m)) */
 
        if (BN_is_odd(m))
-               { ret=BN_mod_exp_mont(r,a,p,m,ctx,NULL); }
+               {
+               if (a->top == 1)
+                       {
+                       BN_ULONG A = a->d[0];
+                       ret=BN_mod_exp_mont_word(r,A,p,m,ctx,NULL);
+                       }
+               else
+                       ret=BN_mod_exp_mont(r,a,p,m,ctx,NULL);
+               }
        else
 #endif
 #ifdef RECP_MUL_MOD
@@ -370,7 +345,7 @@ int BN_mod_exp(BIGNUM *r, BIGNUM *a, const BIGNUM *p, const BIGNUM *m,
        return(ret);
        }
 
-/* #ifdef RECP_MUL_MOD */
+
 int BN_mod_exp_recp(BIGNUM *r, const BIGNUM *a, const BIGNUM *p,
                    const BIGNUM *m, BN_CTX *ctx)
        {
@@ -485,9 +460,8 @@ err:
        BN_RECP_CTX_free(&recp);
        return(ret);
        }
-/* #endif */
 
-/* #ifdef MONT_MUL_MOD */
+
 int BN_mod_exp_mont(BIGNUM *rr, BIGNUM *a, const BIGNUM *p,
                    const BIGNUM *m, BN_CTX *ctx, BN_MONT_CTX *in_mont)
        {
@@ -527,11 +501,9 @@ int BN_mod_exp_mont(BIGNUM *rr, BIGNUM *a, const BIGNUM *p,
        /* If this is not done, things will break in the montgomery
         * part */
 
-#if 1
        if (in_mont != NULL)
                mont=in_mont;
        else
-#endif
                {
                if ((mont=BN_MONT_CTX_new()) == NULL) goto err;
                if (!BN_MONT_CTX_set(mont,m,ctx)) goto err;
@@ -541,7 +513,8 @@ int BN_mod_exp_mont(BIGNUM *rr, BIGNUM *a, const BIGNUM *p,
        ts=1;
        if (BN_ucmp(a,m) >= 0)
                {
-               BN_mod(&(val[0]),a,m,ctx);
+               if (!BN_mod(&(val[0]),a,m,ctx))
+                       goto err;
                aa= &(val[0]);
                }
        else
@@ -574,7 +547,7 @@ int BN_mod_exp_mont(BIGNUM *rr, BIGNUM *a, const BIGNUM *p,
        wstart=bits-1;  /* The top bit of the window */
        wend=0;         /* The bottom bit of the window */
 
-        if (!BN_to_montgomery(r,BN_value_one(),mont,ctx)) goto err;
+       if (!BN_to_montgomery(r,BN_value_one(),mont,ctx)) goto err;
        for (;;)
                {
                if (BN_is_bit_set(p,wstart) == 0)
@@ -635,7 +608,82 @@ err:
                BN_clear_free(&(val[i]));
        return(ret);
        }
-/* #endif */
+
+int BN_mod_exp_mont_word(BIGNUM *rr, BN_ULONG a, const BIGNUM *p,
+                         const BIGNUM *m, BN_CTX *ctx, BN_MONT_CTX *in_mont)
+/* if we had BN_mod_exp_mont_2, we could even use windowing in it */
+       {
+       int b, bits, ret=0;
+       BIGNUM *d, *r, *t;
+       BN_MONT_CTX *mont = NULL;
+
+       bn_check_top(p);
+       bn_check_top(m);
+
+       if (!(m->d[0] & 1))
+               {
+               BNerr(BN_F_BN_MOD_EXP_MONT_WORD,BN_R_CALLED_WITH_EVEN_MODULUS);
+               return(0);
+               }
+       bits = BN_num_bits(p);
+       if (bits == 0)
+               {
+               BN_one(rr);
+               return(1);
+               }
+       BN_CTX_start(ctx);
+       d = BN_CTX_get(ctx);
+       r = BN_CTX_get(ctx);
+       t = BN_CTX_get(ctx);
+       if (d == NULL || r == NULL || t == NULL) goto err;
+
+#ifdef ATALLA
+       if (!tried_atalla)
+               {
+               BN_set_word(t, a);
+               if (BN_mod_exp_word_atalla(rr, t, p, m))
+                       return 1;
+               }
+/* If it fails, try the other methods */
+#endif
+
+       if (in_mont != NULL)
+               mont=in_mont;
+       else
+               {
+               if ((mont = BN_MONT_CTX_new()) == NULL) goto err;
+               if (!BN_MONT_CTX_set(mont, m, ctx)) goto err;
+               }
+
+       if (!BN_to_montgomery(r, BN_value_one(), mont, ctx)) goto err;
+       for (b = bits-1; b >= 0; b--)
+               {
+               if (BN_is_bit_set(p, b))
+                       {
+                       if (!BN_mul_word(r, a))
+                               goto err;
+                       if (BN_ucmp(r, m) >= 0)
+                               {
+                               if (!BN_mod(t, r, m, ctx))
+                                       goto err;
+                               { BIGNUM *swap_tmp = r; r = t; t = swap_tmp; }
+                               }
+                       }
+               
+               if (b > 0)
+                       {
+                       if (!BN_mod_mul_montgomery(r, r, r, mont, ctx))
+                               goto err;
+                       }
+               }
+       BN_from_montgomery(rr, r, mont, ctx);
+       ret = 1;
+err:
+       if ((in_mont == NULL) && (mont != NULL)) BN_MONT_CTX_free(mont);
+       BN_CTX_end(ctx);
+       return(ret);
+       }
+
 
 /* The old fallback, simple version :-) */
 int BN_mod_exp_simple(BIGNUM *r, BIGNUM *a, BIGNUM *p, BIGNUM *m,

diff --git a/crypto/dh/dh_key.c b/crypto/dh/dh_key.c
index 0c7eeaf260b359e8a017cf7249f53bab239f80f0..6f9426dd6fc276129100eba63f9d1abdcadb322d 100644 (file)
--- a/crypto/dh/dh_key.c
+++ b/crypto/dh/dh_key.c
@@ -193,19 +193,26 @@ err:
 static int dh_bn_mod_exp(DH *dh, BIGNUM *r, BIGNUM *a, const BIGNUM *p,
                        const BIGNUM *m, BN_CTX *ctx,
                        BN_MONT_CTX *m_ctx)
-{
-       return BN_mod_exp_mont(r, a, p, m, ctx, m_ctx);
-}
+       {
+       if (a->top == 1)
+               {
+               BN_ULONG A = a->d[0];
+               return BN_mod_exp_mont_word(r,A,p,m,ctx,m_ctx);
+               }
+       else
+               return BN_mod_exp_mont(r,a,p,m,ctx,m_ctx);
+       }
+
 
 static int dh_init(DH *dh)
-{
+       {
        dh->flags |= DH_FLAG_CACHE_MONT_P;
        return(1);
-}
+       }
 
 static int dh_finish(DH *dh)
-{
+       {
        if(dh->method_mont_p)
                BN_MONT_CTX_free((BN_MONT_CTX *)dh->method_mont_p);
        return(1);
-}
+       }