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 improvement 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 bits1=BN_num_bits(p1);
39 bits2=BN_num_bits(p2);
40 if ((bits1 == 0) && (bits2 == 0))
49 if (d == NULL || r == NULL) goto err;
51 bits=(bits1 > bits2)?bits1:bits2;
53 /* If this is not done, things will break in the montgomery
60 if ((mont=BN_MONT_CTX_new()) == NULL) goto err;
61 if (!BN_MONT_CTX_set(mont,m,ctx)) goto err;
64 BN_init(&(val[0][0]));
65 BN_init(&(val[1][1]));
66 BN_init(&(val[0][1]));
67 BN_init(&(val[1][0]));
69 if (BN_ucmp(a1,m) >= 0)
71 BN_mod(&(val[1][0]),a1,m,ctx);
76 if (BN_ucmp(a2,m) >= 0)
78 BN_mod(&(val[0][1]),a2,m,ctx);
83 if (!BN_to_montgomery(&(val[1][0]),aa1,mont,ctx)) goto err;
84 if (!BN_to_montgomery(&(val[0][1]),aa2,mont,ctx)) goto err;
85 if (!BN_mod_mul_montgomery(&(val[1][1]),
86 &(val[1][0]),&(val[0][1]),mont,ctx))
90 if (bits <= 20) /* This is probably 3 or 0x10001, so just do singles */
93 window=5; /* max size of window */
99 window=EXP2_TABLE_BITS;
107 BN_init(&(val[x][0]));
108 BN_init(&(val[x][1]));
109 if (!BN_mod_mul_montgomery(&(val[x][0]),
110 &(val[1][0]),&(val[x-1][0]),mont,ctx)) goto err;
111 if (!BN_mod_mul_montgomery(&(val[x][1]),
112 &(val[1][0]),&(val[x-1][1]),mont,ctx)) goto err;
116 BN_init(&(val[x][y]));
117 if (!BN_mod_mul_montgomery(&(val[x][y]),
118 &(val[x][y-1]),&(val[0][1]),mont,ctx))
124 start=1; /* This is used to avoid multiplication etc
125 * when there is only the value '1' in the
127 xvalue=0; /* The 'x value' of the window */
128 yvalue=0; /* The 'y value' of the window */
129 wstart=bits-1; /* The top bit of the window */
130 wend=0; /* The bottom bit of the window */
132 if (!BN_to_montgomery(r,BN_value_one(),mont,ctx)) goto err;
135 xvalue=BN_is_bit_set(p1,wstart);
136 yvalue=BN_is_bit_set(p2,wstart);
137 if (!(xvalue || yvalue))
141 if (!BN_mod_mul_montgomery(r,r,r,mont,ctx))
145 if (wstart < 0) break;
148 /* We now have wstart on a 'set' bit, we now need to work out
149 * how bit a window to do. To do this we need to scan
150 * forward until the last set bit before the end of the
153 /* xvalue=BN_is_bit_set(p1,wstart); already set */
154 /* yvalue=BN_is_bit_set(p1,wstart); already set */
156 for (i=1; i<window; i++)
158 if (wstart-i < 0) break;
160 xvalue|=BN_is_bit_set(p1,wstart-i);
162 yvalue|=BN_is_bit_set(p2,wstart-i);
165 /* i is the size of the current window */
166 /* add the 'bytes above' */
170 if (!BN_mod_mul_montgomery(r,r,r,mont,ctx))
174 /* wvalue will be an odd number < 2^window */
175 if (xvalue || yvalue)
177 if (!BN_mod_mul_montgomery(r,r,&(val[xvalue][yvalue]),
181 /* move the 'window' down further */
184 if (wstart < 0) break;
186 BN_from_montgomery(rr,r,mont,ctx);
189 if ((in_mont == NULL) && (mont != NULL)) BN_MONT_CTX_free(mont);
195 BN_clear_free(&(val[i][j]));