err:
if (r != rr) BN_copy(r,rr);
BN_CTX_end(ctx);
+ bn_check_top(r);
return(ret);
}
*/
#define MONT_MUL_MOD
+#define MONT_EXP_WORD
#define RECP_MUL_MOD
#ifdef MONT_MUL_MOD
if (BN_is_odd(m))
{
+# ifdef MONT_EXP_WORD
if (a->top == 1 && !a->neg)
{
BN_ULONG A = a->d[0];
ret=BN_mod_exp_mont_word(r,A,p,m,ctx,NULL);
}
else
+# endif
ret=BN_mod_exp_mont(r,a,p,m,ctx,NULL);
}
else
{ ret=BN_mod_exp_simple(r,a,p,m,ctx); }
#endif
+ bn_check_top(r);
return(ret);
}
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;
bits=BN_num_bits(p);
if (bits == 0)
{
- BN_one(r);
- return(1);
+ ret = BN_one(r);
+ return ret;
}
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 (BN_RECP_CTX_set(&recp,m,ctx) <= 0) goto err;
-
- BN_init(&(val[0]));
- ts=1;
+ if (m->neg)
+ {
+ /* ignore sign of 'm' */
+ if (!BN_copy(aa, m)) goto err;
+ aa->neg = 0;
+ if (BN_RECP_CTX_set(&recp,aa,ctx) <= 0) goto err;
+ }
+ else
+ {
+ if (BN_RECP_CTX_set(&recp,m,ctx) <= 0) goto err;
+ }
- if (!BN_nnmod(&(val[0]),a,m,ctx)) goto err; /* 1 */
+ if (!BN_nnmod(val[0],a,m,ctx)) goto err; /* 1 */
+ if (BN_is_zero(val[0]))
+ {
+ 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<j; i++)
{
- BN_init(&val[i]);
- if (!BN_mod_mul_reciprocal(&(val[i]),&(val[i-1]),aa,&recp,ctx))
+ if(((val[i] = BN_CTX_get(ctx)) == NULL) ||
+ !BN_mod_mul_reciprocal(val[i],val[i-1],
+ aa,&recp,ctx))
goto err;
}
- ts=i;
}
start=1; /* This is used to avoid multiplication etc
}
/* wvalue will be an odd number < 2^window */
- if (!BN_mod_mul_reciprocal(r,r,&(val[wvalue>>1]),&recp,ctx))
+ if (!BN_mod_mul_reciprocal(r,r,val[wvalue>>1],&recp,ctx))
goto err;
/* move the 'window' down further */
ret=1;
err:
BN_CTX_end(ctx);
- for (i=0; i<ts; i++)
- BN_clear_free(&(val[i]));
BN_RECP_CTX_free(&recp);
+ bn_check_top(r);
return(ret);
}
const BIGNUM *m, BN_CTX *ctx, BN_MONT_CTX *in_mont)
{
int i,j,bits,ret=0,wstart,wend,window,wvalue;
- int start=1,ts=0;
+ int start=1;
BIGNUM *d,*r;
const BIGNUM *aa;
- BIGNUM val[TABLE_SIZE];
+ /* Table of variables obtained from 'ctx' */
+ BIGNUM *val[TABLE_SIZE];
BN_MONT_CTX *mont=NULL;
bn_check_top(a);
bn_check_top(p);
bn_check_top(m);
- if (!(m->d[0] & 1))
+ if (!BN_is_odd(m))
{
BNerr(BN_F_BN_MOD_EXP_MONT,BN_R_CALLED_WITH_EVEN_MODULUS);
return(0);
bits=BN_num_bits(p);
if (bits == 0)
{
- BN_one(rr);
- return(1);
+ ret = BN_one(rr);
+ return ret;
}
+
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 */
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_to_montgomery(&(val[0]),aa,mont,ctx)) goto err; /* 1 */
+ if (BN_is_zero(aa))
+ {
+ BN_zero(rr);
+ ret = 1;
+ goto err;
+ }
+ 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<j; i++)
{
- BN_init(&(val[i]));
- if (!BN_mod_mul_montgomery(&(val[i]),&(val[i-1]),d,mont,ctx))
+ if(((val[i] = BN_CTX_get(ctx)) == NULL) ||
+ !BN_mod_mul_montgomery(val[i],val[i-1],
+ d,mont,ctx))
goto err;
}
- ts=i;
}
start=1; /* This is used to avoid multiplication etc
}
/* wvalue will be an odd number < 2^window */
- if (!BN_mod_mul_montgomery(r,r,&(val[wvalue>>1]),mont,ctx))
+ if (!BN_mod_mul_montgomery(r,r,val[wvalue>>1],mont,ctx))
goto err;
/* move the 'window' down further */
err:
if ((in_mont == NULL) && (mont != NULL)) BN_MONT_CTX_free(mont);
BN_CTX_end(ctx);
- for (i=0; i<ts; i++)
- BN_clear_free(&(val[i]));
+ bn_check_top(rr);
return(ret);
}
(/* BN_ucmp(r, (m)) < 0 ? 1 :*/ \
(BN_mod(t, r, m, ctx) && (swap_tmp = r, r = t, t = swap_tmp, 1))))
/* BN_MOD_MUL_WORD is only used with 'w' large,
- * so the BN_ucmp test is probably more overhead
- * than always using BN_mod (which uses BN_copy if
- * a similar test returns true). */
+ * so the BN_ucmp test is probably more overhead
+ * than always using BN_mod (which uses BN_copy if
+ * a similar test returns true). */
+ /* We can use BN_mod and do not need BN_nnmod because our
+ * accumulator is never negative (the result of BN_mod does
+ * not depend on the sign of the modulus).
+ */
#define BN_TO_MONTGOMERY_WORD(r, w, mont) \
(BN_set_word(r, (w)) && BN_to_montgomery(r, r, (mont), ctx))
bn_check_top(p);
bn_check_top(m);
- if (!(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);
}
+ if (m->top == 1)
+ a %= m->d[0]; /* make sure that 'a' is reduced */
+
bits = BN_num_bits(p);
if (bits == 0)
{
- BN_one(rr);
- return(1);
+ ret = BN_one(rr);
+ return ret;
+ }
+ if (a == 0)
+ {
+ BN_zero(rr);
+ ret = 1;
+ return ret;
}
+
BN_CTX_start(ctx);
d = BN_CTX_get(ctx);
r = BN_CTX_get(ctx);
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];
bits=BN_num_bits(p);
if (bits == 0)
{
- BN_one(r);
- return(1);
+ ret = BN_one(r);
+ return ret;
}
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_nnmod(val[0],a,m,ctx)) goto err; /* 1 */
+ if (BN_is_zero(val[0]))
+ {
+ 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<j; i++)
{
- BN_init(&(val[i]));
- if (!BN_mod_mul(&(val[i]),&(val[i-1]),d,m,ctx))
+ if(((val[i] = BN_CTX_get(ctx)) == NULL) ||
+ !BN_mod_mul(val[i],val[i-1],d,m,ctx))
goto err;
}
- ts=i;
}
start=1; /* This is used to avoid multiplication etc
}
/* wvalue will be an odd number < 2^window */
- if (!BN_mod_mul(r,r,&(val[wvalue>>1]),m,ctx))
+ if (!BN_mod_mul(r,r,val[wvalue>>1],m,ctx))
goto err;
/* move the 'window' down further */
ret=1;
err:
BN_CTX_end(ctx);
- for (i=0; i<ts; i++)
- BN_clear_free(&(val[i]));
+ bn_check_top(r);
return(ret);
}