diff options
Diffstat (limited to 'crypto/bn/bn_exp2.c')
| -rw-r--r-- | crypto/bn/bn_exp2.c | 202 |
1 files changed, 202 insertions, 0 deletions
diff --git a/crypto/bn/bn_exp2.c b/crypto/bn/bn_exp2.c new file mode 100644 index 0000000000..eface739b3 --- /dev/null +++ b/crypto/bn/bn_exp2.c @@ -0,0 +1,202 @@ +#include <stdio.h> +#include "cryptlib.h" +#include "bn_lcl.h" + +/* I've done some timing with different table sizes. + * The main hassle is that even with bits set at 3, this requires + * 63 BIGNUMs to store the pre-calculated values. + * 512 1024 + * bits=1 75.4% 79.4% + * bits=2 61.2% 62.4% + * bits=3 61.3% 59.3% + * The lack of speed improvment is also a function of the pre-calculation + * which could be removed. + */ +#define EXP2_TABLE_BITS 2 /* 1 2 3 4 5 */ +#define EXP2_TABLE_SIZE 4 /* 2 4 8 16 32 */ + +int BN_mod_exp2_mont(rr,a1,p1,a2,p2,m,ctx,in_mont) +BIGNUM *rr; +BIGNUM *a1; +BIGNUM *p1; +BIGNUM *a2; +BIGNUM *p2; +BIGNUM *m; +BN_CTX *ctx; +BN_MONT_CTX *in_mont; + { + int i,j,k,bits,bits1,bits2,ret=0,wstart,wend,window,xvalue,yvalue; + int start=1,ts=0,x,y; + BIGNUM *d,*aa1,*aa2,*r; + BIGNUM val[EXP2_TABLE_SIZE][EXP2_TABLE_SIZE]; + BN_MONT_CTX *mont=NULL; + + bn_check_top(a1); + bn_check_top(p1); + bn_check_top(a2); + bn_check_top(p2); + bn_check_top(m); + + if (!(m->d[0] & 1)) + { + BNerr(BN_F_BN_MOD_EXP_MONT,BN_R_CALLED_WITH_EVEN_MODULUS); + return(0); + } + d= &(ctx->bn[ctx->tos++]); + r= &(ctx->bn[ctx->tos++]); + bits1=BN_num_bits(p1); + bits2=BN_num_bits(p2); + if ((bits1 == 0) && (bits2 == 0)) + { + BN_one(r); + return(1); + } + bits=(bits1 > bits2)?bits1:bits2; + + /* If this is not done, things will break in the montgomery + * part */ + + 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; + } + + BN_init(&(val[0][0])); + BN_init(&(val[1][1])); + BN_init(&(val[0][1])); + BN_init(&(val[1][0])); + ts=1; + if (BN_ucmp(a1,m) >= 0) + { + BN_mod(&(val[1][0]),a1,m,ctx); + aa1= &(val[1][0]); + } + else + aa1=a1; + if (BN_ucmp(a2,m) >= 0) + { + BN_mod(&(val[0][1]),a2,m,ctx); + aa2= &(val[0][1]); + } + else + aa2=a2; + if (!BN_to_montgomery(&(val[1][0]),aa1,mont,ctx)) goto err; + if (!BN_to_montgomery(&(val[0][1]),aa2,mont,ctx)) goto err; + if (!BN_mod_mul_montgomery(&(val[1][1]), + &(val[1][0]),&(val[0][1]),mont,ctx)) + goto err; + +#if 0 + if (bits <= 20) /* This is probably 3 or 0x10001, so just do singles */ + window=1; + else if (bits > 250) + window=5; /* max size of window */ + else if (bits >= 120) + window=4; + else + window=3; +#else + window=EXP2_TABLE_BITS; +#endif + + k=1<<window; + for (x=0; x<k; x++) + { + if (x >= 2) + { + BN_init(&(val[x][0])); + BN_init(&(val[x][1])); + if (!BN_mod_mul_montgomery(&(val[x][0]), + &(val[1][0]),&(val[x-1][0]),mont,ctx)) goto err; + if (!BN_mod_mul_montgomery(&(val[x][1]), + &(val[1][0]),&(val[x-1][1]),mont,ctx)) goto err; + } + for (y=2; y<k; y++) + { + BN_init(&(val[x][y])); + if (!BN_mod_mul_montgomery(&(val[x][y]), + &(val[x][y-1]),&(val[0][1]),mont,ctx)) + goto err; + } + } + ts=k; + + start=1; /* This is used to avoid multiplication etc + * when there is only the value '1' in the + * buffer. */ + xvalue=0; /* The 'x value' of the window */ + yvalue=0; /* The 'y value' of the window */ + 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; + for (;;) + { + xvalue=BN_is_bit_set(p1,wstart); + yvalue=BN_is_bit_set(p2,wstart); + if (!(xvalue || yvalue)) + { + if (!start) + { + if (!BN_mod_mul_montgomery(r,r,r,mont,ctx)) + goto err; + } + wstart--; + if (wstart < 0) break; + continue; + } + /* We now have wstart on a 'set' bit, we now need to work out + * how bit a window to do. To do this we need to scan + * forward until the last set bit before the end of the + * window */ + j=wstart; + /* xvalue=BN_is_bit_set(p1,wstart); already set */ + /* yvalue=BN_is_bit_set(p1,wstart); already set */ + wend=0; + for (i=1; i<window; i++) + { + if (wstart-i < 0) break; + xvalue+=xvalue; + xvalue|=BN_is_bit_set(p1,wstart-i); + yvalue+=yvalue; + yvalue|=BN_is_bit_set(p2,wstart-i); + } + + /* i is the size of the current window */ + /* add the 'bytes above' */ + if (!start) + for (j=0; j<i; j++) + { + if (!BN_mod_mul_montgomery(r,r,r,mont,ctx)) + goto err; + } + + /* wvalue will be an odd number < 2^window */ + if (xvalue || yvalue) + { + if (!BN_mod_mul_montgomery(r,r,&(val[xvalue][yvalue]), + mont,ctx)) goto err; + } + + /* move the 'window' down further */ + wstart-=i; + start=0; + if (wstart < 0) break; + } + BN_from_montgomery(rr,r,mont,ctx); + ret=1; +err: + if ((in_mont == NULL) && (mont != NULL)) BN_MONT_CTX_free(mont); + ctx->tos-=2; + for (i=0; i<ts; i++) + { + for (j=0; j<ts; j++) + { + BN_clear_free(&(val[i][j])); + } + } + return(ret); + } |