5 /* I've done some timing with different table sizes.
6 * The main hassle is that even with bits set at 3, this requires
7 * 63 BIGNUMs to store the pre-calculated values.
12 * The lack of speed improvment is also a function of the pre-calculation
13 * which could be removed.
15 #define EXP2_TABLE_BITS 2 /* 1 2 3 4 5 */
16 #define EXP2_TABLE_SIZE 4 /* 2 4 8 16 32 */
18 int BN_mod_exp2_mont(BIGNUM *rr, BIGNUM *a1, BIGNUM *p1, BIGNUM *a2,
19 BIGNUM *p2, BIGNUM *m, BN_CTX *ctx, BN_MONT_CTX *in_mont)
21 int i,j,k,bits,bits1,bits2,ret=0,wstart,wend,window,xvalue,yvalue;
23 BIGNUM *d,*aa1,*aa2,*r;
24 BIGNUM val[EXP2_TABLE_SIZE][EXP2_TABLE_SIZE];
25 BN_MONT_CTX *mont=NULL;
35 BNerr(BN_F_BN_MOD_EXP_MONT,BN_R_CALLED_WITH_EVEN_MODULUS);
38 d= &(ctx->bn[ctx->tos++]);
39 r= &(ctx->bn[ctx->tos++]);
40 bits1=BN_num_bits(p1);
41 bits2=BN_num_bits(p2);
42 if ((bits1 == 0) && (bits2 == 0))
47 bits=(bits1 > bits2)?bits1:bits2;
49 /* If this is not done, things will break in the montgomery
56 if ((mont=BN_MONT_CTX_new()) == NULL) goto err;
57 if (!BN_MONT_CTX_set(mont,m,ctx)) goto err;
60 BN_init(&(val[0][0]));
61 BN_init(&(val[1][1]));
62 BN_init(&(val[0][1]));
63 BN_init(&(val[1][0]));
65 if (BN_ucmp(a1,m) >= 0)
67 BN_mod(&(val[1][0]),a1,m,ctx);
72 if (BN_ucmp(a2,m) >= 0)
74 BN_mod(&(val[0][1]),a2,m,ctx);
79 if (!BN_to_montgomery(&(val[1][0]),aa1,mont,ctx)) goto err;
80 if (!BN_to_montgomery(&(val[0][1]),aa2,mont,ctx)) goto err;
81 if (!BN_mod_mul_montgomery(&(val[1][1]),
82 &(val[1][0]),&(val[0][1]),mont,ctx))
86 if (bits <= 20) /* This is probably 3 or 0x10001, so just do singles */
89 window=5; /* max size of window */
95 window=EXP2_TABLE_BITS;
103 BN_init(&(val[x][0]));
104 BN_init(&(val[x][1]));
105 if (!BN_mod_mul_montgomery(&(val[x][0]),
106 &(val[1][0]),&(val[x-1][0]),mont,ctx)) goto err;
107 if (!BN_mod_mul_montgomery(&(val[x][1]),
108 &(val[1][0]),&(val[x-1][1]),mont,ctx)) goto err;
112 BN_init(&(val[x][y]));
113 if (!BN_mod_mul_montgomery(&(val[x][y]),
114 &(val[x][y-1]),&(val[0][1]),mont,ctx))
120 start=1; /* This is used to avoid multiplication etc
121 * when there is only the value '1' in the
123 xvalue=0; /* The 'x value' of the window */
124 yvalue=0; /* The 'y value' of the window */
125 wstart=bits-1; /* The top bit of the window */
126 wend=0; /* The bottom bit of the window */
128 if (!BN_to_montgomery(r,BN_value_one(),mont,ctx)) goto err;
131 xvalue=BN_is_bit_set(p1,wstart);
132 yvalue=BN_is_bit_set(p2,wstart);
133 if (!(xvalue || yvalue))
137 if (!BN_mod_mul_montgomery(r,r,r,mont,ctx))
141 if (wstart < 0) break;
144 /* We now have wstart on a 'set' bit, we now need to work out
145 * how bit a window to do. To do this we need to scan
146 * forward until the last set bit before the end of the
149 /* xvalue=BN_is_bit_set(p1,wstart); already set */
150 /* yvalue=BN_is_bit_set(p1,wstart); already set */
152 for (i=1; i<window; i++)
154 if (wstart-i < 0) break;
156 xvalue|=BN_is_bit_set(p1,wstart-i);
158 yvalue|=BN_is_bit_set(p2,wstart-i);
161 /* i is the size of the current window */
162 /* add the 'bytes above' */
166 if (!BN_mod_mul_montgomery(r,r,r,mont,ctx))
170 /* wvalue will be an odd number < 2^window */
171 if (xvalue || yvalue)
173 if (!BN_mod_mul_montgomery(r,r,&(val[xvalue][yvalue]),
177 /* move the 'window' down further */
180 if (wstart < 0) break;
182 BN_from_montgomery(rr,r,mont,ctx);
185 if ((in_mont == NULL) && (mont != NULL)) BN_MONT_CTX_free(mont);
191 BN_clear_free(&(val[i][j]));