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
]));