summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--CHANGES5
-rw-r--r--crypto/bn/bn.h3
-rw-r--r--crypto/bn/bn_err.c1
-rw-r--r--crypto/bn/bn_exp.c138
-rw-r--r--crypto/dh/dh_key.c21
5 files changed, 116 insertions, 52 deletions
diff --git a/CHANGES b/CHANGES
index 9f6560b882..f1cfe73a80 100644
--- 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 9fa995c64f..000ff48155 100644
--- 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 988270bcf4..e0cbd70b7d 100644
--- 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 0c11601675..96f34fa529 100644
--- 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 0c7eeaf260..6f9426dd6f 100644
--- 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);
-}
+ }
generated by cgit v1.2.3 (git 2.25.1) at 2024-08-26 18:25:58 +0000