]>
Commit | Line | Data |
---|---|---|
dc434bbc BM |
1 | /* crypto/bn/bn_exp2.c */ |
2 | /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) | |
3 | * All rights reserved. | |
4 | * | |
5 | * This package is an SSL implementation written | |
6 | * by Eric Young (eay@cryptsoft.com). | |
7 | * The implementation was written so as to conform with Netscapes SSL. | |
40720ce3 | 8 | * |
dc434bbc BM |
9 | * This library is free for commercial and non-commercial use as long as |
10 | * the following conditions are aheared to. The following conditions | |
11 | * apply to all code found in this distribution, be it the RC4, RSA, | |
12 | * lhash, DES, etc., code; not just the SSL code. The SSL documentation | |
13 | * included with this distribution is covered by the same copyright terms | |
14 | * except that the holder is Tim Hudson (tjh@cryptsoft.com). | |
40720ce3 | 15 | * |
dc434bbc BM |
16 | * Copyright remains Eric Young's, and as such any Copyright notices in |
17 | * the code are not to be removed. | |
18 | * If this package is used in a product, Eric Young should be given attribution | |
19 | * as the author of the parts of the library used. | |
20 | * This can be in the form of a textual message at program startup or | |
21 | * in documentation (online or textual) provided with the package. | |
40720ce3 | 22 | * |
dc434bbc BM |
23 | * Redistribution and use in source and binary forms, with or without |
24 | * modification, are permitted provided that the following conditions | |
25 | * are met: | |
26 | * 1. Redistributions of source code must retain the copyright | |
27 | * notice, this list of conditions and the following disclaimer. | |
28 | * 2. Redistributions in binary form must reproduce the above copyright | |
29 | * notice, this list of conditions and the following disclaimer in the | |
30 | * documentation and/or other materials provided with the distribution. | |
31 | * 3. All advertising materials mentioning features or use of this software | |
32 | * must display the following acknowledgement: | |
33 | * "This product includes cryptographic software written by | |
34 | * Eric Young (eay@cryptsoft.com)" | |
35 | * The word 'cryptographic' can be left out if the rouines from the library | |
36 | * being used are not cryptographic related :-). | |
40720ce3 | 37 | * 4. If you include any Windows specific code (or a derivative thereof) from |
dc434bbc BM |
38 | * the apps directory (application code) you must include an acknowledgement: |
39 | * "This product includes software written by Tim Hudson (tjh@cryptsoft.com)" | |
40720ce3 | 40 | * |
dc434bbc BM |
41 | * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND |
42 | * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE | |
43 | * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE | |
44 | * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE | |
45 | * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL | |
46 | * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS | |
47 | * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) | |
48 | * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT | |
49 | * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY | |
50 | * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF | |
51 | * SUCH DAMAGE. | |
40720ce3 | 52 | * |
dc434bbc BM |
53 | * The licence and distribution terms for any publically available version or |
54 | * derivative of this code cannot be changed. i.e. this code cannot simply be | |
55 | * copied and put under another distribution licence | |
56 | * [including the GNU Public Licence.] | |
57 | */ | |
58 | /* ==================================================================== | |
59 | * Copyright (c) 1998-2000 The OpenSSL Project. All rights reserved. | |
60 | * | |
61 | * Redistribution and use in source and binary forms, with or without | |
62 | * modification, are permitted provided that the following conditions | |
63 | * are met: | |
64 | * | |
65 | * 1. Redistributions of source code must retain the above copyright | |
40720ce3 | 66 | * notice, this list of conditions and the following disclaimer. |
dc434bbc BM |
67 | * |
68 | * 2. Redistributions in binary form must reproduce the above copyright | |
69 | * notice, this list of conditions and the following disclaimer in | |
70 | * the documentation and/or other materials provided with the | |
71 | * distribution. | |
72 | * | |
73 | * 3. All advertising materials mentioning features or use of this | |
74 | * software must display the following acknowledgment: | |
75 | * "This product includes software developed by the OpenSSL Project | |
76 | * for use in the OpenSSL Toolkit. (http://www.openssl.org/)" | |
77 | * | |
78 | * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to | |
79 | * endorse or promote products derived from this software without | |
80 | * prior written permission. For written permission, please contact | |
81 | * openssl-core@openssl.org. | |
82 | * | |
83 | * 5. Products derived from this software may not be called "OpenSSL" | |
84 | * nor may "OpenSSL" appear in their names without prior written | |
85 | * permission of the OpenSSL Project. | |
86 | * | |
87 | * 6. Redistributions of any form whatsoever must retain the following | |
88 | * acknowledgment: | |
89 | * "This product includes software developed by the OpenSSL Project | |
90 | * for use in the OpenSSL Toolkit (http://www.openssl.org/)" | |
91 | * | |
92 | * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY | |
93 | * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE | |
94 | * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR | |
95 | * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR | |
96 | * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, | |
97 | * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT | |
98 | * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; | |
99 | * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) | |
100 | * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, | |
101 | * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) | |
102 | * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED | |
103 | * OF THE POSSIBILITY OF SUCH DAMAGE. | |
104 | * ==================================================================== | |
105 | * | |
106 | * This product includes cryptographic software written by Eric Young | |
107 | * (eay@cryptsoft.com). This product includes software written by Tim | |
108 | * Hudson (tjh@cryptsoft.com). | |
109 | * | |
110 | */ | |
111 | ||
dfeab068 RE |
112 | #include <stdio.h> |
113 | #include "cryptlib.h" | |
114 | #include "bn_lcl.h" | |
115 | ||
40720ce3 | 116 | #define TABLE_SIZE 32 |
dfeab068 | 117 | |
020fc820 | 118 | int BN_mod_exp2_mont(BIGNUM *rr, const BIGNUM *a1, const BIGNUM *p1, |
40720ce3 MC |
119 | const BIGNUM *a2, const BIGNUM *p2, const BIGNUM *m, |
120 | BN_CTX *ctx, BN_MONT_CTX *in_mont) | |
121 | { | |
122 | int i, j, bits, b, bits1, bits2, ret = | |
123 | 0, wpos1, wpos2, window1, window2, wvalue1, wvalue2; | |
124 | int r_is_one = 1; | |
125 | BIGNUM *d, *r; | |
126 | const BIGNUM *a_mod_m; | |
127 | /* Tables of variables obtained from 'ctx' */ | |
128 | BIGNUM *val1[TABLE_SIZE], *val2[TABLE_SIZE]; | |
129 | BN_MONT_CTX *mont = NULL; | |
130 | ||
131 | bn_check_top(a1); | |
132 | bn_check_top(p1); | |
133 | bn_check_top(a2); | |
134 | bn_check_top(p2); | |
135 | bn_check_top(m); | |
136 | ||
137 | if (!(m->d[0] & 1)) { | |
138 | BNerr(BN_F_BN_MOD_EXP2_MONT, BN_R_CALLED_WITH_EVEN_MODULUS); | |
139 | return (0); | |
140 | } | |
141 | bits1 = BN_num_bits(p1); | |
142 | bits2 = BN_num_bits(p2); | |
143 | if ((bits1 == 0) && (bits2 == 0)) { | |
144 | ret = BN_one(rr); | |
145 | return ret; | |
146 | } | |
dfeab068 | 147 | |
40720ce3 | 148 | bits = (bits1 > bits2) ? bits1 : bits2; |
dfeab068 | 149 | |
40720ce3 MC |
150 | BN_CTX_start(ctx); |
151 | d = BN_CTX_get(ctx); | |
152 | r = BN_CTX_get(ctx); | |
153 | val1[0] = BN_CTX_get(ctx); | |
154 | val2[0] = BN_CTX_get(ctx); | |
155 | if (!d || !r || !val1[0] || !val2[0]) | |
156 | goto err; | |
9b141126 | 157 | |
40720ce3 MC |
158 | if (in_mont != NULL) |
159 | mont = in_mont; | |
160 | else { | |
161 | if ((mont = BN_MONT_CTX_new()) == NULL) | |
162 | goto err; | |
163 | if (!BN_MONT_CTX_set(mont, m, ctx)) | |
164 | goto err; | |
165 | } | |
9b141126 | 166 | |
40720ce3 MC |
167 | window1 = BN_window_bits_for_exponent_size(bits1); |
168 | window2 = BN_window_bits_for_exponent_size(bits2); | |
dfeab068 | 169 | |
40720ce3 MC |
170 | /* |
171 | * Build table for a1: val1[i] := a1^(2*i + 1) mod m for i = 0 .. 2^(window1-1) | |
172 | */ | |
173 | if (a1->neg || BN_ucmp(a1, m) >= 0) { | |
174 | if (!BN_mod(val1[0], a1, m, ctx)) | |
175 | goto err; | |
176 | a_mod_m = val1[0]; | |
177 | } else | |
178 | a_mod_m = a1; | |
179 | if (BN_is_zero(a_mod_m)) { | |
180 | BN_zero(rr); | |
181 | ret = 1; | |
182 | goto err; | |
183 | } | |
dc434bbc | 184 | |
40720ce3 MC |
185 | if (!BN_to_montgomery(val1[0], a_mod_m, mont, ctx)) |
186 | goto err; | |
187 | if (window1 > 1) { | |
188 | if (!BN_mod_mul_montgomery(d, val1[0], val1[0], mont, ctx)) | |
189 | goto err; | |
73c2522c | 190 | |
40720ce3 MC |
191 | j = 1 << (window1 - 1); |
192 | for (i = 1; i < j; i++) { | |
193 | if (((val1[i] = BN_CTX_get(ctx)) == NULL) || | |
194 | !BN_mod_mul_montgomery(val1[i], val1[i - 1], d, mont, ctx)) | |
195 | goto err; | |
196 | } | |
197 | } | |
dc434bbc | 198 | |
40720ce3 MC |
199 | /* |
200 | * Build table for a2: val2[i] := a2^(2*i + 1) mod m for i = 0 .. 2^(window2-1) | |
201 | */ | |
202 | if (a2->neg || BN_ucmp(a2, m) >= 0) { | |
203 | if (!BN_mod(val2[0], a2, m, ctx)) | |
204 | goto err; | |
205 | a_mod_m = val2[0]; | |
206 | } else | |
207 | a_mod_m = a2; | |
208 | if (BN_is_zero(a_mod_m)) { | |
209 | BN_zero(rr); | |
210 | ret = 1; | |
211 | goto err; | |
212 | } | |
213 | if (!BN_to_montgomery(val2[0], a_mod_m, mont, ctx)) | |
214 | goto err; | |
215 | if (window2 > 1) { | |
216 | if (!BN_mod_mul_montgomery(d, val2[0], val2[0], mont, ctx)) | |
217 | goto err; | |
dc434bbc | 218 | |
40720ce3 MC |
219 | j = 1 << (window2 - 1); |
220 | for (i = 1; i < j; i++) { | |
221 | if (((val2[i] = BN_CTX_get(ctx)) == NULL) || | |
222 | !BN_mod_mul_montgomery(val2[i], val2[i - 1], d, mont, ctx)) | |
223 | goto err; | |
224 | } | |
225 | } | |
dc434bbc | 226 | |
40720ce3 MC |
227 | /* Now compute the power product, using independent windows. */ |
228 | r_is_one = 1; | |
229 | wvalue1 = 0; /* The 'value' of the first window */ | |
230 | wvalue2 = 0; /* The 'value' of the second window */ | |
231 | wpos1 = 0; /* If wvalue1 > 0, the bottom bit of the | |
232 | * first window */ | |
233 | wpos2 = 0; /* If wvalue2 > 0, the bottom bit of the | |
234 | * second window */ | |
dc434bbc | 235 | |
40720ce3 MC |
236 | if (!BN_to_montgomery(r, BN_value_one(), mont, ctx)) |
237 | goto err; | |
238 | for (b = bits - 1; b >= 0; b--) { | |
239 | if (!r_is_one) { | |
240 | if (!BN_mod_mul_montgomery(r, r, r, mont, ctx)) | |
241 | goto err; | |
242 | } | |
dc434bbc | 243 | |
40720ce3 MC |
244 | if (!wvalue1) |
245 | if (BN_is_bit_set(p1, b)) { | |
246 | /* | |
247 | * consider bits b-window1+1 .. b for this window | |
248 | */ | |
249 | i = b - window1 + 1; | |
250 | while (!BN_is_bit_set(p1, i)) /* works for i<0 */ | |
251 | i++; | |
252 | wpos1 = i; | |
253 | wvalue1 = 1; | |
254 | for (i = b - 1; i >= wpos1; i--) { | |
255 | wvalue1 <<= 1; | |
256 | if (BN_is_bit_set(p1, i)) | |
257 | wvalue1++; | |
258 | } | |
259 | } | |
dc434bbc | 260 | |
40720ce3 MC |
261 | if (!wvalue2) |
262 | if (BN_is_bit_set(p2, b)) { | |
263 | /* | |
264 | * consider bits b-window2+1 .. b for this window | |
265 | */ | |
266 | i = b - window2 + 1; | |
267 | while (!BN_is_bit_set(p2, i)) | |
268 | i++; | |
269 | wpos2 = i; | |
270 | wvalue2 = 1; | |
271 | for (i = b - 1; i >= wpos2; i--) { | |
272 | wvalue2 <<= 1; | |
273 | if (BN_is_bit_set(p2, i)) | |
274 | wvalue2++; | |
275 | } | |
276 | } | |
dc434bbc | 277 | |
40720ce3 MC |
278 | if (wvalue1 && b == wpos1) { |
279 | /* wvalue1 is odd and < 2^window1 */ | |
280 | if (!BN_mod_mul_montgomery(r, r, val1[wvalue1 >> 1], mont, ctx)) | |
281 | goto err; | |
282 | wvalue1 = 0; | |
283 | r_is_one = 0; | |
284 | } | |
dc434bbc | 285 | |
40720ce3 MC |
286 | if (wvalue2 && b == wpos2) { |
287 | /* wvalue2 is odd and < 2^window2 */ | |
288 | if (!BN_mod_mul_montgomery(r, r, val2[wvalue2 >> 1], mont, ctx)) | |
289 | goto err; | |
290 | wvalue2 = 0; | |
291 | r_is_one = 0; | |
292 | } | |
293 | } | |
294 | if (!BN_from_montgomery(rr, r, mont, ctx)) | |
295 | goto err; | |
296 | ret = 1; | |
297 | err: | |
298 | if ((in_mont == NULL) && (mont != NULL)) | |
299 | BN_MONT_CTX_free(mont); | |
300 | BN_CTX_end(ctx); | |
301 | bn_check_top(rr); | |
302 | return (ret); | |
303 | } |