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