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(rr,a1,p1,a2,p2,m,ctx,in_mont)
28 int i,j,k,bits,bits1,bits2,ret=0,wstart,wend,window,xvalue,yvalue;
30 BIGNUM *d,*aa1,*aa2,*r;
31 BIGNUM val[EXP2_TABLE_SIZE][EXP2_TABLE_SIZE];
32 BN_MONT_CTX *mont=NULL;
42 BNerr(BN_F_BN_MOD_EXP_MONT,BN_R_CALLED_WITH_EVEN_MODULUS);
45 d= &(ctx->bn[ctx->tos++]);
46 r= &(ctx->bn[ctx->tos++]);
47 bits1=BN_num_bits(p1);
48 bits2=BN_num_bits(p2);
49 if ((bits1 == 0) && (bits2 == 0))
54 bits=(bits1 > bits2)?bits1:bits2;
56 /* If this is not done, things will break in the montgomery
63 if ((mont=BN_MONT_CTX_new()) == NULL) goto err;
64 if (!BN_MONT_CTX_set(mont,m,ctx)) goto err;
67 BN_init(&(val[0][0]));
68 BN_init(&(val[1][1]));
69 BN_init(&(val[0][1]));
70 BN_init(&(val[1][0]));
72 if (BN_ucmp(a1,m) >= 0)
74 BN_mod(&(val[1][0]),a1,m,ctx);
79 if (BN_ucmp(a2,m) >= 0)
81 BN_mod(&(val[0][1]),a2,m,ctx);
86 if (!BN_to_montgomery(&(val[1][0]),aa1,mont,ctx)) goto err;
87 if (!BN_to_montgomery(&(val[0][1]),aa2,mont,ctx)) goto err;
88 if (!BN_mod_mul_montgomery(&(val[1][1]),
89 &(val[1][0]),&(val[0][1]),mont,ctx))
93 if (bits <= 20) /* This is probably 3 or 0x10001, so just do singles */
96 window=5; /* max size of window */
102 window=EXP2_TABLE_BITS;
110 BN_init(&(val[x][0]));
111 BN_init(&(val[x][1]));
112 if (!BN_mod_mul_montgomery(&(val[x][0]),
113 &(val[1][0]),&(val[x-1][0]),mont,ctx)) goto err;
114 if (!BN_mod_mul_montgomery(&(val[x][1]),
115 &(val[1][0]),&(val[x-1][1]),mont,ctx)) goto err;
119 BN_init(&(val[x][y]));
120 if (!BN_mod_mul_montgomery(&(val[x][y]),
121 &(val[x][y-1]),&(val[0][1]),mont,ctx))
127 start=1; /* This is used to avoid multiplication etc
128 * when there is only the value '1' in the
130 xvalue=0; /* The 'x value' of the window */
131 yvalue=0; /* The 'y value' of the window */
132 wstart=bits-1; /* The top bit of the window */
133 wend=0; /* The bottom bit of the window */
135 if (!BN_to_montgomery(r,BN_value_one(),mont,ctx)) goto err;
138 xvalue=BN_is_bit_set(p1,wstart);
139 yvalue=BN_is_bit_set(p2,wstart);
140 if (!(xvalue || yvalue))
144 if (!BN_mod_mul_montgomery(r,r,r,mont,ctx))
148 if (wstart < 0) break;
151 /* We now have wstart on a 'set' bit, we now need to work out
152 * how bit a window to do. To do this we need to scan
153 * forward until the last set bit before the end of the
156 /* xvalue=BN_is_bit_set(p1,wstart); already set */
157 /* yvalue=BN_is_bit_set(p1,wstart); already set */
159 for (i=1; i<window; i++)
161 if (wstart-i < 0) break;
163 xvalue|=BN_is_bit_set(p1,wstart-i);
165 yvalue|=BN_is_bit_set(p2,wstart-i);
168 /* i is the size of the current window */
169 /* add the 'bytes above' */
173 if (!BN_mod_mul_montgomery(r,r,r,mont,ctx))
177 /* wvalue will be an odd number < 2^window */
178 if (xvalue || yvalue)
180 if (!BN_mod_mul_montgomery(r,r,&(val[xvalue][yvalue]),
184 /* move the 'window' down further */
187 if (wstart < 0) break;
189 BN_from_montgomery(rr,r,mont,ctx);
192 if ((in_mont == NULL) && (mont != NULL)) BN_MONT_CTX_free(mont);
198 BN_clear_free(&(val[i][j]));