]>
Commit | Line | Data |
---|---|---|
d02b48c6 | 1 | /* crypto/bn/bn_exp.c */ |
58964a49 | 2 | /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) |
d02b48c6 RE |
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. | |
8 | * | |
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). | |
15 | * | |
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. | |
22 | * | |
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 :-). | |
37 | * 4. If you include any Windows specific code (or a derivative thereof) from | |
38 | * the apps directory (application code) you must include an acknowledgement: | |
39 | * "This product includes software written by Tim Hudson (tjh@cryptsoft.com)" | |
40 | * | |
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. | |
52 | * | |
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 | */ | |
f8989a21 | 58 | /* ==================================================================== |
46a64376 | 59 | * Copyright (c) 1998-2005 The OpenSSL Project. All rights reserved. |
f8989a21 BM |
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 | |
66 | * notice, this list of conditions and the following disclaimer. | |
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 | ||
d02b48c6 | 112 | |
d02b48c6 RE |
113 | #include "cryptlib.h" |
114 | #include "bn_lcl.h" | |
6dad7bd6 | 115 | |
7cc684f4 DSH |
116 | #define OPENSSL_FIPSAPI |
117 | #ifdef OPENSSL_FIPS | |
118 | #include <openssl/fips.h> | |
119 | #endif | |
120 | ||
46a64376 | 121 | /* maximum precomputation table size for *variable* sliding windows */ |
dc434bbc | 122 | #define TABLE_SIZE 32 |
dfeab068 | 123 | |
58964a49 | 124 | /* this one works - simple but works */ |
020fc820 | 125 | int BN_exp(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx) |
58964a49 | 126 | { |
9b141126 | 127 | int i,bits,ret=0; |
a0a54079 | 128 | BIGNUM *v,*rr; |
58964a49 | 129 | |
bd31fb21 | 130 | if (BN_get_flags(p, BN_FLG_CONSTTIME) != 0) |
46a64376 | 131 | { |
bd31fb21 | 132 | /* BN_FLG_CONSTTIME only supported by BN_mod_exp_mont() */ |
46a64376 BM |
133 | BNerr(BN_F_BN_EXP,ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED); |
134 | return -1; | |
135 | } | |
136 | ||
9b141126 | 137 | BN_CTX_start(ctx); |
a0a54079 | 138 | if ((r == a) || (r == p)) |
9b141126 | 139 | rr = BN_CTX_get(ctx); |
a0a54079 | 140 | else |
9b141126 | 141 | rr = r; |
d70323f1 DSH |
142 | v = BN_CTX_get(ctx); |
143 | if (rr == NULL || v == NULL) goto err; | |
58964a49 RE |
144 | |
145 | if (BN_copy(v,a) == NULL) goto err; | |
146 | bits=BN_num_bits(p); | |
147 | ||
148 | if (BN_is_odd(p)) | |
a0a54079 MC |
149 | { if (BN_copy(rr,a) == NULL) goto err; } |
150 | else { if (!BN_one(rr)) goto err; } | |
58964a49 RE |
151 | |
152 | for (i=1; i<bits; i++) | |
153 | { | |
a0a54079 | 154 | if (!BN_sqr(v,v,ctx)) goto err; |
58964a49 RE |
155 | if (BN_is_bit_set(p,i)) |
156 | { | |
a0a54079 | 157 | if (!BN_mul(rr,rr,v,ctx)) goto err; |
58964a49 RE |
158 | } |
159 | } | |
160 | ret=1; | |
161 | err: | |
a0a54079 | 162 | if (r != rr) BN_copy(r,rr); |
9b141126 | 163 | BN_CTX_end(ctx); |
d870740c | 164 | bn_check_top(r); |
58964a49 RE |
165 | return(ret); |
166 | } | |
167 | ||
6dad7bd6 | 168 | |
020fc820 | 169 | int BN_mod_exp(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, const BIGNUM *m, |
84c15db5 | 170 | BN_CTX *ctx) |
d02b48c6 RE |
171 | { |
172 | int ret; | |
173 | ||
dfeab068 RE |
174 | bn_check_top(a); |
175 | bn_check_top(p); | |
176 | bn_check_top(m); | |
177 | ||
78a0c1f1 BM |
178 | /* For even modulus m = 2^k*m_odd, it might make sense to compute |
179 | * a^p mod m_odd and a^p mod 2^k separately (with Montgomery | |
180 | * exponentiation for the odd part), using appropriate exponent | |
181 | * reductions, and combine the results using the CRT. | |
182 | * | |
183 | * For now, we use Montgomery only if the modulus is odd; otherwise, | |
184 | * exponentiation using the reciprocal-based quick remaindering | |
185 | * algorithm is used. | |
186 | * | |
c94b6de0 BM |
187 | * (Timing obtained with expspeed.c [computations a^p mod m |
188 | * where a, p, m are of the same length: 256, 512, 1024, 2048, | |
189 | * 4096, 8192 bits], compared to the running time of the | |
190 | * standard algorithm: | |
191 | * | |
192 | * BN_mod_exp_mont 33 .. 40 % [AMD K6-2, Linux, debug configuration] | |
193 | * 55 .. 77 % [UltraSparc processor, but | |
194 | * debug-solaris-sparcv8-gcc conf.] | |
195 | * | |
196 | * BN_mod_exp_recp 50 .. 70 % [AMD K6-2, Linux, debug configuration] | |
197 | * 62 .. 118 % [UltraSparc, debug-solaris-sparcv8-gcc] | |
198 | * | |
199 | * On the Sparc, BN_mod_exp_recp was faster than BN_mod_exp_mont | |
200 | * at 2048 and more bits, but at 512 and 1024 bits, it was | |
201 | * slower even than the standard algorithm! | |
202 | * | |
203 | * "Real" timings [linux-elf, solaris-sparcv9-gcc configurations] | |
204 | * should be obtained when the new Montgomery reduction code | |
205 | * has been integrated into OpenSSL.) | |
78a0c1f1 BM |
206 | */ |
207 | ||
208 | #define MONT_MUL_MOD | |
25439b76 | 209 | #define MONT_EXP_WORD |
78a0c1f1 BM |
210 | #define RECP_MUL_MOD |
211 | ||
d02b48c6 RE |
212 | #ifdef MONT_MUL_MOD |
213 | /* I have finally been able to take out this pre-condition of | |
214 | * the top bit being set. It was caused by an error in BN_div | |
215 | * with negatives. There was also another problem when for a^b%m | |
216 | * a >= m. eay 07-May-97 */ | |
217 | /* if ((m->d[m->top-1]&BN_TBIT) && BN_is_odd(m)) */ | |
218 | ||
219 | if (BN_is_odd(m)) | |
6dad7bd6 | 220 | { |
25439b76 | 221 | # ifdef MONT_EXP_WORD |
bd31fb21 | 222 | if (a->top == 1 && !a->neg && (BN_get_flags(p, BN_FLG_CONSTTIME) == 0)) |
6dad7bd6 BM |
223 | { |
224 | BN_ULONG A = a->d[0]; | |
225 | ret=BN_mod_exp_mont_word(r,A,p,m,ctx,NULL); | |
226 | } | |
227 | else | |
25439b76 | 228 | # endif |
6dad7bd6 BM |
229 | ret=BN_mod_exp_mont(r,a,p,m,ctx,NULL); |
230 | } | |
d02b48c6 RE |
231 | else |
232 | #endif | |
233 | #ifdef RECP_MUL_MOD | |
234 | { ret=BN_mod_exp_recp(r,a,p,m,ctx); } | |
235 | #else | |
236 | { ret=BN_mod_exp_simple(r,a,p,m,ctx); } | |
237 | #endif | |
238 | ||
d870740c | 239 | bn_check_top(r); |
d02b48c6 RE |
240 | return(ret); |
241 | } | |
242 | ||
6dad7bd6 | 243 | |
84c15db5 BL |
244 | int BN_mod_exp_recp(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, |
245 | const BIGNUM *m, BN_CTX *ctx) | |
d02b48c6 | 246 | { |
dfeab068 | 247 | int i,j,bits,ret=0,wstart,wend,window,wvalue; |
c86f2054 | 248 | int start=1; |
dfeab068 | 249 | BIGNUM *aa; |
c86f2054 GT |
250 | /* Table of variables obtained from 'ctx' */ |
251 | BIGNUM *val[TABLE_SIZE]; | |
dfeab068 | 252 | BN_RECP_CTX recp; |
d02b48c6 | 253 | |
bd31fb21 | 254 | if (BN_get_flags(p, BN_FLG_CONSTTIME) != 0) |
46a64376 | 255 | { |
bd31fb21 | 256 | /* BN_FLG_CONSTTIME only supported by BN_mod_exp_mont() */ |
46a64376 BM |
257 | BNerr(BN_F_BN_MOD_EXP_RECP,ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED); |
258 | return -1; | |
259 | } | |
260 | ||
d02b48c6 RE |
261 | bits=BN_num_bits(p); |
262 | ||
263 | if (bits == 0) | |
264 | { | |
cd2eebfd BM |
265 | ret = BN_one(r); |
266 | return ret; | |
267 | } | |
9b141126 UM |
268 | |
269 | BN_CTX_start(ctx); | |
c86f2054 GT |
270 | aa = BN_CTX_get(ctx); |
271 | val[0] = BN_CTX_get(ctx); | |
272 | if(!aa || !val[0]) goto err; | |
9b141126 | 273 | |
dfeab068 | 274 | BN_RECP_CTX_init(&recp); |
8dea52fa BM |
275 | if (m->neg) |
276 | { | |
277 | /* ignore sign of 'm' */ | |
278 | if (!BN_copy(aa, m)) goto err; | |
279 | aa->neg = 0; | |
280 | if (BN_RECP_CTX_set(&recp,aa,ctx) <= 0) goto err; | |
281 | } | |
282 | else | |
283 | { | |
284 | if (BN_RECP_CTX_set(&recp,m,ctx) <= 0) goto err; | |
285 | } | |
dfeab068 | 286 | |
c86f2054 GT |
287 | if (!BN_nnmod(val[0],a,m,ctx)) goto err; /* 1 */ |
288 | if (BN_is_zero(val[0])) | |
73c2522c | 289 | { |
b6358c89 GT |
290 | BN_zero(r); |
291 | ret = 1; | |
73c2522c BM |
292 | goto err; |
293 | } | |
d02b48c6 | 294 | |
dc434bbc BM |
295 | window = BN_window_bits_for_exponent_size(bits); |
296 | if (window > 1) | |
d02b48c6 | 297 | { |
c86f2054 | 298 | if (!BN_mod_mul_reciprocal(aa,val[0],val[0],&recp,ctx)) |
dc434bbc BM |
299 | goto err; /* 2 */ |
300 | j=1<<(window-1); | |
301 | for (i=1; i<j; i++) | |
302 | { | |
c86f2054 GT |
303 | if(((val[i] = BN_CTX_get(ctx)) == NULL) || |
304 | !BN_mod_mul_reciprocal(val[i],val[i-1], | |
305 | aa,&recp,ctx)) | |
dc434bbc BM |
306 | goto err; |
307 | } | |
d02b48c6 | 308 | } |
dc434bbc | 309 | |
d02b48c6 RE |
310 | start=1; /* This is used to avoid multiplication etc |
311 | * when there is only the value '1' in the | |
312 | * buffer. */ | |
313 | wvalue=0; /* The 'value' of the window */ | |
314 | wstart=bits-1; /* The top bit of the window */ | |
315 | wend=0; /* The bottom bit of the window */ | |
316 | ||
317 | if (!BN_one(r)) goto err; | |
318 | ||
319 | for (;;) | |
320 | { | |
321 | if (BN_is_bit_set(p,wstart) == 0) | |
322 | { | |
323 | if (!start) | |
dfeab068 | 324 | if (!BN_mod_mul_reciprocal(r,r,r,&recp,ctx)) |
d02b48c6 RE |
325 | goto err; |
326 | if (wstart == 0) break; | |
327 | wstart--; | |
328 | continue; | |
329 | } | |
330 | /* We now have wstart on a 'set' bit, we now need to work out | |
331 | * how bit a window to do. To do this we need to scan | |
332 | * forward until the last set bit before the end of the | |
333 | * window */ | |
334 | j=wstart; | |
335 | wvalue=1; | |
336 | wend=0; | |
337 | for (i=1; i<window; i++) | |
338 | { | |
339 | if (wstart-i < 0) break; | |
340 | if (BN_is_bit_set(p,wstart-i)) | |
341 | { | |
342 | wvalue<<=(i-wend); | |
343 | wvalue|=1; | |
344 | wend=i; | |
345 | } | |
346 | } | |
347 | ||
348 | /* wend is the size of the current window */ | |
349 | j=wend+1; | |
350 | /* add the 'bytes above' */ | |
351 | if (!start) | |
352 | for (i=0; i<j; i++) | |
353 | { | |
dfeab068 | 354 | if (!BN_mod_mul_reciprocal(r,r,r,&recp,ctx)) |
d02b48c6 RE |
355 | goto err; |
356 | } | |
357 | ||
358 | /* wvalue will be an odd number < 2^window */ | |
c86f2054 | 359 | if (!BN_mod_mul_reciprocal(r,r,val[wvalue>>1],&recp,ctx)) |
d02b48c6 RE |
360 | goto err; |
361 | ||
362 | /* move the 'window' down further */ | |
363 | wstart-=wend+1; | |
364 | wvalue=0; | |
365 | start=0; | |
366 | if (wstart < 0) break; | |
367 | } | |
368 | ret=1; | |
369 | err: | |
9b141126 | 370 | BN_CTX_end(ctx); |
dfeab068 | 371 | BN_RECP_CTX_free(&recp); |
d870740c | 372 | bn_check_top(r); |
d02b48c6 RE |
373 | return(ret); |
374 | } | |
d02b48c6 | 375 | |
6dad7bd6 | 376 | |
020fc820 | 377 | int BN_mod_exp_mont(BIGNUM *rr, const BIGNUM *a, const BIGNUM *p, |
84c15db5 | 378 | const BIGNUM *m, BN_CTX *ctx, BN_MONT_CTX *in_mont) |
d02b48c6 RE |
379 | { |
380 | int i,j,bits,ret=0,wstart,wend,window,wvalue; | |
c86f2054 | 381 | int start=1; |
84c15db5 | 382 | BIGNUM *d,*r; |
020fc820 | 383 | const BIGNUM *aa; |
c86f2054 GT |
384 | /* Table of variables obtained from 'ctx' */ |
385 | BIGNUM *val[TABLE_SIZE]; | |
d02b48c6 RE |
386 | BN_MONT_CTX *mont=NULL; |
387 | ||
bd31fb21 | 388 | if (BN_get_flags(p, BN_FLG_CONSTTIME) != 0) |
46a64376 BM |
389 | { |
390 | return BN_mod_exp_mont_consttime(rr, a, p, m, ctx, in_mont); | |
391 | } | |
392 | ||
dfeab068 RE |
393 | bn_check_top(a); |
394 | bn_check_top(p); | |
395 | bn_check_top(m); | |
396 | ||
82b2f57e | 397 | if (!BN_is_odd(m)) |
d02b48c6 RE |
398 | { |
399 | BNerr(BN_F_BN_MOD_EXP_MONT,BN_R_CALLED_WITH_EVEN_MODULUS); | |
400 | return(0); | |
401 | } | |
d02b48c6 RE |
402 | bits=BN_num_bits(p); |
403 | if (bits == 0) | |
404 | { | |
cd2eebfd BM |
405 | ret = BN_one(rr); |
406 | return ret; | |
407 | } | |
73c2522c | 408 | |
9b141126 UM |
409 | BN_CTX_start(ctx); |
410 | d = BN_CTX_get(ctx); | |
411 | r = BN_CTX_get(ctx); | |
c86f2054 GT |
412 | val[0] = BN_CTX_get(ctx); |
413 | if (!d || !r || !val[0]) goto err; | |
d02b48c6 RE |
414 | |
415 | /* If this is not done, things will break in the montgomery | |
416 | * part */ | |
417 | ||
58964a49 RE |
418 | if (in_mont != NULL) |
419 | mont=in_mont; | |
420 | else | |
58964a49 RE |
421 | { |
422 | if ((mont=BN_MONT_CTX_new()) == NULL) goto err; | |
423 | if (!BN_MONT_CTX_set(mont,m,ctx)) goto err; | |
424 | } | |
d02b48c6 | 425 | |
499e167f | 426 | if (a->neg || BN_ucmp(a,m) >= 0) |
d02b48c6 | 427 | { |
c86f2054 | 428 | if (!BN_nnmod(val[0],a,m,ctx)) |
6dad7bd6 | 429 | goto err; |
c86f2054 | 430 | aa= val[0]; |
d02b48c6 RE |
431 | } |
432 | else | |
433 | aa=a; | |
73c2522c BM |
434 | if (BN_is_zero(aa)) |
435 | { | |
b6358c89 GT |
436 | BN_zero(rr); |
437 | ret = 1; | |
73c2522c BM |
438 | goto err; |
439 | } | |
c86f2054 | 440 | if (!BN_to_montgomery(val[0],aa,mont,ctx)) goto err; /* 1 */ |
d02b48c6 | 441 | |
dc434bbc BM |
442 | window = BN_window_bits_for_exponent_size(bits); |
443 | if (window > 1) | |
d02b48c6 | 444 | { |
c86f2054 | 445 | if (!BN_mod_mul_montgomery(d,val[0],val[0],mont,ctx)) goto err; /* 2 */ |
dc434bbc BM |
446 | j=1<<(window-1); |
447 | for (i=1; i<j; i++) | |
448 | { | |
c86f2054 GT |
449 | if(((val[i] = BN_CTX_get(ctx)) == NULL) || |
450 | !BN_mod_mul_montgomery(val[i],val[i-1], | |
451 | d,mont,ctx)) | |
dc434bbc BM |
452 | goto err; |
453 | } | |
d02b48c6 | 454 | } |
d02b48c6 RE |
455 | |
456 | start=1; /* This is used to avoid multiplication etc | |
457 | * when there is only the value '1' in the | |
458 | * buffer. */ | |
459 | wvalue=0; /* The 'value' of the window */ | |
460 | wstart=bits-1; /* The top bit of the window */ | |
461 | wend=0; /* The bottom bit of the window */ | |
462 | ||
6dad7bd6 | 463 | if (!BN_to_montgomery(r,BN_value_one(),mont,ctx)) goto err; |
d02b48c6 RE |
464 | for (;;) |
465 | { | |
466 | if (BN_is_bit_set(p,wstart) == 0) | |
467 | { | |
468 | if (!start) | |
58964a49 | 469 | { |
d02b48c6 RE |
470 | if (!BN_mod_mul_montgomery(r,r,r,mont,ctx)) |
471 | goto err; | |
58964a49 | 472 | } |
d02b48c6 RE |
473 | if (wstart == 0) break; |
474 | wstart--; | |
475 | continue; | |
476 | } | |
477 | /* We now have wstart on a 'set' bit, we now need to work out | |
478 | * how bit a window to do. To do this we need to scan | |
479 | * forward until the last set bit before the end of the | |
480 | * window */ | |
481 | j=wstart; | |
482 | wvalue=1; | |
483 | wend=0; | |
484 | for (i=1; i<window; i++) | |
485 | { | |
486 | if (wstart-i < 0) break; | |
487 | if (BN_is_bit_set(p,wstart-i)) | |
488 | { | |
489 | wvalue<<=(i-wend); | |
490 | wvalue|=1; | |
491 | wend=i; | |
492 | } | |
493 | } | |
494 | ||
495 | /* wend is the size of the current window */ | |
496 | j=wend+1; | |
497 | /* add the 'bytes above' */ | |
498 | if (!start) | |
499 | for (i=0; i<j; i++) | |
500 | { | |
501 | if (!BN_mod_mul_montgomery(r,r,r,mont,ctx)) | |
502 | goto err; | |
503 | } | |
504 | ||
505 | /* wvalue will be an odd number < 2^window */ | |
c86f2054 | 506 | if (!BN_mod_mul_montgomery(r,r,val[wvalue>>1],mont,ctx)) |
d02b48c6 RE |
507 | goto err; |
508 | ||
509 | /* move the 'window' down further */ | |
510 | wstart-=wend+1; | |
511 | wvalue=0; | |
512 | start=0; | |
513 | if (wstart < 0) break; | |
514 | } | |
e958c5af | 515 | if (!BN_from_montgomery(rr,r,mont,ctx)) goto err; |
d02b48c6 RE |
516 | ret=1; |
517 | err: | |
58964a49 | 518 | if ((in_mont == NULL) && (mont != NULL)) BN_MONT_CTX_free(mont); |
9b141126 | 519 | BN_CTX_end(ctx); |
d870740c | 520 | bn_check_top(rr); |
d02b48c6 RE |
521 | return(ret); |
522 | } | |
6dad7bd6 | 523 | |
46a64376 BM |
524 | |
525 | /* BN_mod_exp_mont_consttime() stores the precomputed powers in a specific layout | |
526 | * so that accessing any of these table values shows the same access pattern as far | |
527 | * as cache lines are concerned. The following functions are used to transfer a BIGNUM | |
528 | * from/to that table. */ | |
529 | ||
6343829a | 530 | static int MOD_EXP_CTIME_COPY_TO_PREBUF(BIGNUM *b, int top, unsigned char *buf, int idx, int width) |
46a64376 BM |
531 | { |
532 | size_t i, j; | |
533 | ||
534 | if (bn_wexpand(b, top) == NULL) | |
535 | return 0; | |
536 | while (b->top < top) | |
537 | { | |
538 | b->d[b->top++] = 0; | |
539 | } | |
540 | ||
541 | for (i = 0, j=idx; i < top * sizeof b->d[0]; i++, j+=width) | |
542 | { | |
543 | buf[j] = ((unsigned char*)b->d)[i]; | |
544 | } | |
545 | ||
546 | bn_correct_top(b); | |
547 | return 1; | |
548 | } | |
549 | ||
6343829a | 550 | static int MOD_EXP_CTIME_COPY_FROM_PREBUF(BIGNUM *b, int top, unsigned char *buf, int idx, int width) |
46a64376 BM |
551 | { |
552 | size_t i, j; | |
553 | ||
554 | if (bn_wexpand(b, top) == NULL) | |
555 | return 0; | |
556 | ||
557 | for (i=0, j=idx; i < top * sizeof b->d[0]; i++, j+=width) | |
558 | { | |
559 | ((unsigned char*)b->d)[i] = buf[j]; | |
560 | } | |
561 | ||
562 | b->top = top; | |
563 | bn_correct_top(b); | |
564 | return 1; | |
565 | } | |
566 | ||
567 | /* Given a pointer value, compute the next address that is a cache line multiple. */ | |
568 | #define MOD_EXP_CTIME_ALIGN(x_) \ | |
569 | ((unsigned char*)(x_) + (MOD_EXP_CTIME_MIN_CACHE_LINE_WIDTH - (((BN_ULONG)(x_)) & (MOD_EXP_CTIME_MIN_CACHE_LINE_MASK)))) | |
570 | ||
571 | /* This variant of BN_mod_exp_mont() uses fixed windows and the special | |
572 | * precomputation memory layout to limit data-dependency to a minimum | |
573 | * to protect secret exponents (cf. the hyper-threading timing attacks | |
574 | * pointed out by Colin Percival, | |
575 | * http://www.daemonology.net/hyperthreading-considered-harmful/) | |
576 | */ | |
577 | int BN_mod_exp_mont_consttime(BIGNUM *rr, const BIGNUM *a, const BIGNUM *p, | |
578 | const BIGNUM *m, BN_CTX *ctx, BN_MONT_CTX *in_mont) | |
579 | { | |
580 | int i,bits,ret=0,idx,window,wvalue; | |
6343829a | 581 | int top; |
46a64376 BM |
582 | BIGNUM *r; |
583 | const BIGNUM *aa; | |
584 | BN_MONT_CTX *mont=NULL; | |
585 | ||
586 | int numPowers; | |
587 | unsigned char *powerbufFree=NULL; | |
6343829a | 588 | int powerbufLen = 0; |
46a64376 BM |
589 | unsigned char *powerbuf=NULL; |
590 | BIGNUM *computeTemp=NULL, *am=NULL; | |
591 | ||
592 | bn_check_top(a); | |
593 | bn_check_top(p); | |
594 | bn_check_top(m); | |
595 | ||
596 | top = m->top; | |
597 | ||
598 | if (!(m->d[0] & 1)) | |
599 | { | |
600 | BNerr(BN_F_BN_MOD_EXP_MONT_CONSTTIME,BN_R_CALLED_WITH_EVEN_MODULUS); | |
601 | return(0); | |
602 | } | |
603 | bits=BN_num_bits(p); | |
604 | if (bits == 0) | |
605 | { | |
606 | ret = BN_one(rr); | |
607 | return ret; | |
608 | } | |
609 | ||
610 | /* Initialize BIGNUM context and allocate intermediate result */ | |
611 | BN_CTX_start(ctx); | |
612 | r = BN_CTX_get(ctx); | |
613 | if (r == NULL) goto err; | |
614 | ||
615 | /* Allocate a montgomery context if it was not supplied by the caller. | |
616 | * If this is not done, things will break in the montgomery part. | |
617 | */ | |
618 | if (in_mont != NULL) | |
619 | mont=in_mont; | |
620 | else | |
621 | { | |
622 | if ((mont=BN_MONT_CTX_new()) == NULL) goto err; | |
623 | if (!BN_MONT_CTX_set(mont,m,ctx)) goto err; | |
624 | } | |
625 | ||
626 | /* Get the window size to use with size of p. */ | |
627 | window = BN_window_bits_for_ctime_exponent_size(bits); | |
628 | ||
629 | /* Allocate a buffer large enough to hold all of the pre-computed | |
630 | * powers of a. | |
631 | */ | |
632 | numPowers = 1 << window; | |
633 | powerbufLen = sizeof(m->d[0])*top*numPowers; | |
6343829a | 634 | if ((powerbufFree=(unsigned char*)OPENSSL_malloc(powerbufLen+MOD_EXP_CTIME_MIN_CACHE_LINE_WIDTH)) == NULL) |
46a64376 BM |
635 | goto err; |
636 | ||
637 | powerbuf = MOD_EXP_CTIME_ALIGN(powerbufFree); | |
638 | memset(powerbuf, 0, powerbufLen); | |
639 | ||
640 | /* Initialize the intermediate result. Do this early to save double conversion, | |
641 | * once each for a^0 and intermediate result. | |
642 | */ | |
643 | if (!BN_to_montgomery(r,BN_value_one(),mont,ctx)) goto err; | |
644 | if (!MOD_EXP_CTIME_COPY_TO_PREBUF(r, top, powerbuf, 0, numPowers)) goto err; | |
645 | ||
646 | /* Initialize computeTemp as a^1 with montgomery precalcs */ | |
647 | computeTemp = BN_CTX_get(ctx); | |
648 | am = BN_CTX_get(ctx); | |
649 | if (computeTemp==NULL || am==NULL) goto err; | |
650 | ||
651 | if (a->neg || BN_ucmp(a,m) >= 0) | |
652 | { | |
653 | if (!BN_mod(am,a,m,ctx)) | |
654 | goto err; | |
655 | aa= am; | |
656 | } | |
657 | else | |
658 | aa=a; | |
659 | if (!BN_to_montgomery(am,aa,mont,ctx)) goto err; | |
660 | if (!BN_copy(computeTemp, am)) goto err; | |
661 | if (!MOD_EXP_CTIME_COPY_TO_PREBUF(am, top, powerbuf, 1, numPowers)) goto err; | |
662 | ||
663 | /* If the window size is greater than 1, then calculate | |
664 | * val[i=2..2^winsize-1]. Powers are computed as a*a^(i-1) | |
665 | * (even powers could instead be computed as (a^(i/2))^2 | |
666 | * to use the slight performance advantage of sqr over mul). | |
667 | */ | |
668 | if (window > 1) | |
669 | { | |
670 | for (i=2; i<numPowers; i++) | |
671 | { | |
672 | /* Calculate a^i = a^(i-1) * a */ | |
673 | if (!BN_mod_mul_montgomery(computeTemp,am,computeTemp,mont,ctx)) | |
674 | goto err; | |
675 | if (!MOD_EXP_CTIME_COPY_TO_PREBUF(computeTemp, top, powerbuf, i, numPowers)) goto err; | |
676 | } | |
677 | } | |
678 | ||
679 | /* Adjust the number of bits up to a multiple of the window size. | |
680 | * If the exponent length is not a multiple of the window size, then | |
681 | * this pads the most significant bits with zeros to normalize the | |
682 | * scanning loop to there's no special cases. | |
683 | * | |
684 | * * NOTE: Making the window size a power of two less than the native | |
685 | * * word size ensures that the padded bits won't go past the last | |
686 | * * word in the internal BIGNUM structure. Going past the end will | |
687 | * * still produce the correct result, but causes a different branch | |
688 | * * to be taken in the BN_is_bit_set function. | |
689 | */ | |
690 | bits = ((bits+window-1)/window)*window; | |
691 | idx=bits-1; /* The top bit of the window */ | |
692 | ||
693 | /* Scan the exponent one window at a time starting from the most | |
694 | * significant bits. | |
695 | */ | |
696 | while (idx >= 0) | |
697 | { | |
698 | wvalue=0; /* The 'value' of the window */ | |
699 | ||
700 | /* Scan the window, squaring the result as we go */ | |
701 | for (i=0; i<window; i++,idx--) | |
702 | { | |
703 | if (!BN_mod_mul_montgomery(r,r,r,mont,ctx)) goto err; | |
704 | wvalue = (wvalue<<1)+BN_is_bit_set(p,idx); | |
705 | } | |
706 | ||
707 | /* Fetch the appropriate pre-computed value from the pre-buf */ | |
708 | if (!MOD_EXP_CTIME_COPY_FROM_PREBUF(computeTemp, top, powerbuf, wvalue, numPowers)) goto err; | |
709 | ||
710 | /* Multiply the result into the intermediate result */ | |
711 | if (!BN_mod_mul_montgomery(r,r,computeTemp,mont,ctx)) goto err; | |
712 | } | |
713 | ||
714 | /* Convert the final result from montgomery to standard format */ | |
715 | if (!BN_from_montgomery(rr,r,mont,ctx)) goto err; | |
716 | ret=1; | |
717 | err: | |
718 | if ((in_mont == NULL) && (mont != NULL)) BN_MONT_CTX_free(mont); | |
719 | if (powerbuf!=NULL) | |
720 | { | |
721 | OPENSSL_cleanse(powerbuf,powerbufLen); | |
722 | OPENSSL_free(powerbufFree); | |
723 | } | |
724 | if (am!=NULL) BN_clear(am); | |
725 | if (computeTemp!=NULL) BN_clear(computeTemp); | |
726 | BN_CTX_end(ctx); | |
727 | return(ret); | |
728 | } | |
729 | ||
6dad7bd6 BM |
730 | int BN_mod_exp_mont_word(BIGNUM *rr, BN_ULONG a, const BIGNUM *p, |
731 | const BIGNUM *m, BN_CTX *ctx, BN_MONT_CTX *in_mont) | |
6dad7bd6 | 732 | { |
f8989a21 | 733 | BN_MONT_CTX *mont = NULL; |
6dad7bd6 | 734 | int b, bits, ret=0; |
e958c5af | 735 | int r_is_one; |
f8989a21 | 736 | BN_ULONG w, next_w; |
6dad7bd6 | 737 | BIGNUM *d, *r, *t; |
f8989a21 BM |
738 | BIGNUM *swap_tmp; |
739 | #define BN_MOD_MUL_WORD(r, w, m) \ | |
740 | (BN_mul_word(r, (w)) && \ | |
fc57ebc0 | 741 | (/* BN_ucmp(r, (m)) < 0 ? 1 :*/ \ |
e958c5af BM |
742 | (BN_mod(t, r, m, ctx) && (swap_tmp = r, r = t, t = swap_tmp, 1)))) |
743 | /* BN_MOD_MUL_WORD is only used with 'w' large, | |
8dea52fa BM |
744 | * so the BN_ucmp test is probably more overhead |
745 | * than always using BN_mod (which uses BN_copy if | |
746 | * a similar test returns true). */ | |
747 | /* We can use BN_mod and do not need BN_nnmod because our | |
748 | * accumulator is never negative (the result of BN_mod does | |
749 | * not depend on the sign of the modulus). | |
750 | */ | |
e958c5af BM |
751 | #define BN_TO_MONTGOMERY_WORD(r, w, mont) \ |
752 | (BN_set_word(r, (w)) && BN_to_montgomery(r, r, (mont), ctx)) | |
6dad7bd6 | 753 | |
bd31fb21 | 754 | if (BN_get_flags(p, BN_FLG_CONSTTIME) != 0) |
46a64376 | 755 | { |
bd31fb21 | 756 | /* BN_FLG_CONSTTIME only supported by BN_mod_exp_mont() */ |
46a64376 BM |
757 | BNerr(BN_F_BN_MOD_EXP_MONT_WORD,ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED); |
758 | return -1; | |
759 | } | |
760 | ||
6dad7bd6 BM |
761 | bn_check_top(p); |
762 | bn_check_top(m); | |
763 | ||
82b2f57e | 764 | if (!BN_is_odd(m)) |
6dad7bd6 BM |
765 | { |
766 | BNerr(BN_F_BN_MOD_EXP_MONT_WORD,BN_R_CALLED_WITH_EVEN_MODULUS); | |
767 | return(0); | |
768 | } | |
25439b76 BM |
769 | if (m->top == 1) |
770 | a %= m->d[0]; /* make sure that 'a' is reduced */ | |
771 | ||
6dad7bd6 BM |
772 | bits = BN_num_bits(p); |
773 | if (bits == 0) | |
774 | { | |
cd2eebfd BM |
775 | ret = BN_one(rr); |
776 | return ret; | |
6dad7bd6 | 777 | } |
cd2eebfd BM |
778 | if (a == 0) |
779 | { | |
b6358c89 GT |
780 | BN_zero(rr); |
781 | ret = 1; | |
cd2eebfd BM |
782 | return ret; |
783 | } | |
784 | ||
6dad7bd6 BM |
785 | BN_CTX_start(ctx); |
786 | d = BN_CTX_get(ctx); | |
787 | r = BN_CTX_get(ctx); | |
788 | t = BN_CTX_get(ctx); | |
789 | if (d == NULL || r == NULL || t == NULL) goto err; | |
790 | ||
6dad7bd6 BM |
791 | if (in_mont != NULL) |
792 | mont=in_mont; | |
793 | else | |
794 | { | |
795 | if ((mont = BN_MONT_CTX_new()) == NULL) goto err; | |
796 | if (!BN_MONT_CTX_set(mont, m, ctx)) goto err; | |
797 | } | |
798 | ||
e958c5af | 799 | r_is_one = 1; /* except for Montgomery factor */ |
f8989a21 BM |
800 | |
801 | /* bits-1 >= 0 */ | |
802 | ||
803 | /* The result is accumulated in the product r*w. */ | |
804 | w = a; /* bit 'bits-1' of 'p' is always set */ | |
805 | for (b = bits-2; b >= 0; b--) | |
6dad7bd6 | 806 | { |
f8989a21 BM |
807 | /* First, square r*w. */ |
808 | next_w = w*w; | |
809 | if ((next_w/w) != w) /* overflow */ | |
6dad7bd6 | 810 | { |
e958c5af BM |
811 | if (r_is_one) |
812 | { | |
813 | if (!BN_TO_MONTGOMERY_WORD(r, w, mont)) goto err; | |
814 | r_is_one = 0; | |
815 | } | |
816 | else | |
817 | { | |
818 | if (!BN_MOD_MUL_WORD(r, w, m)) goto err; | |
819 | } | |
f8989a21 BM |
820 | next_w = 1; |
821 | } | |
822 | w = next_w; | |
e958c5af BM |
823 | if (!r_is_one) |
824 | { | |
825 | if (!BN_mod_mul_montgomery(r, r, r, mont, ctx)) goto err; | |
826 | } | |
f8989a21 BM |
827 | |
828 | /* Second, multiply r*w by 'a' if exponent bit is set. */ | |
829 | if (BN_is_bit_set(p, b)) | |
830 | { | |
831 | next_w = w*a; | |
832 | if ((next_w/a) != w) /* overflow */ | |
6dad7bd6 | 833 | { |
e958c5af BM |
834 | if (r_is_one) |
835 | { | |
836 | if (!BN_TO_MONTGOMERY_WORD(r, w, mont)) goto err; | |
837 | r_is_one = 0; | |
838 | } | |
839 | else | |
840 | { | |
841 | if (!BN_MOD_MUL_WORD(r, w, m)) goto err; | |
842 | } | |
f8989a21 | 843 | next_w = a; |
6dad7bd6 | 844 | } |
f8989a21 | 845 | w = next_w; |
6dad7bd6 BM |
846 | } |
847 | } | |
e958c5af | 848 | |
f8989a21 BM |
849 | /* Finally, set r:=r*w. */ |
850 | if (w != 1) | |
851 | { | |
e958c5af BM |
852 | if (r_is_one) |
853 | { | |
854 | if (!BN_TO_MONTGOMERY_WORD(r, w, mont)) goto err; | |
855 | r_is_one = 0; | |
856 | } | |
857 | else | |
858 | { | |
859 | if (!BN_MOD_MUL_WORD(r, w, m)) goto err; | |
860 | } | |
f8989a21 BM |
861 | } |
862 | ||
e958c5af BM |
863 | if (r_is_one) /* can happen only if a == 1*/ |
864 | { | |
865 | if (!BN_one(rr)) goto err; | |
866 | } | |
867 | else | |
868 | { | |
869 | if (!BN_from_montgomery(rr, r, mont, ctx)) goto err; | |
870 | } | |
6dad7bd6 BM |
871 | ret = 1; |
872 | err: | |
873 | if ((in_mont == NULL) && (mont != NULL)) BN_MONT_CTX_free(mont); | |
874 | BN_CTX_end(ctx); | |
d870740c | 875 | bn_check_top(rr); |
6dad7bd6 BM |
876 | return(ret); |
877 | } | |
878 | ||
d02b48c6 RE |
879 | |
880 | /* The old fallback, simple version :-) */ | |
82b2f57e GT |
881 | int BN_mod_exp_simple(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, |
882 | const BIGNUM *m, BN_CTX *ctx) | |
d02b48c6 | 883 | { |
c86f2054 | 884 | int i,j,bits,ret=0,wstart,wend,window,wvalue; |
d02b48c6 RE |
885 | int start=1; |
886 | BIGNUM *d; | |
c86f2054 GT |
887 | /* Table of variables obtained from 'ctx' */ |
888 | BIGNUM *val[TABLE_SIZE]; | |
d02b48c6 | 889 | |
bd31fb21 | 890 | if (BN_get_flags(p, BN_FLG_CONSTTIME) != 0) |
46a64376 | 891 | { |
bd31fb21 | 892 | /* BN_FLG_CONSTTIME only supported by BN_mod_exp_mont() */ |
46a64376 BM |
893 | BNerr(BN_F_BN_MOD_EXP_SIMPLE,ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED); |
894 | return -1; | |
895 | } | |
896 | ||
d02b48c6 RE |
897 | bits=BN_num_bits(p); |
898 | ||
899 | if (bits == 0) | |
900 | { | |
cd2eebfd BM |
901 | ret = BN_one(r); |
902 | return ret; | |
903 | } | |
d02b48c6 | 904 | |
9b141126 | 905 | BN_CTX_start(ctx); |
c86f2054 GT |
906 | d = BN_CTX_get(ctx); |
907 | val[0] = BN_CTX_get(ctx); | |
908 | if(!d || !val[0]) goto err; | |
9b141126 | 909 | |
c86f2054 GT |
910 | if (!BN_nnmod(val[0],a,m,ctx)) goto err; /* 1 */ |
911 | if (BN_is_zero(val[0])) | |
73c2522c | 912 | { |
b6358c89 GT |
913 | BN_zero(r); |
914 | ret = 1; | |
25439b76 | 915 | goto err; |
73c2522c | 916 | } |
d02b48c6 | 917 | |
dc434bbc BM |
918 | window = BN_window_bits_for_exponent_size(bits); |
919 | if (window > 1) | |
d02b48c6 | 920 | { |
c86f2054 | 921 | if (!BN_mod_mul(d,val[0],val[0],m,ctx)) |
dc434bbc BM |
922 | goto err; /* 2 */ |
923 | j=1<<(window-1); | |
924 | for (i=1; i<j; i++) | |
925 | { | |
c86f2054 GT |
926 | if(((val[i] = BN_CTX_get(ctx)) == NULL) || |
927 | !BN_mod_mul(val[i],val[i-1],d,m,ctx)) | |
dc434bbc BM |
928 | goto err; |
929 | } | |
d02b48c6 | 930 | } |
d02b48c6 RE |
931 | |
932 | start=1; /* This is used to avoid multiplication etc | |
933 | * when there is only the value '1' in the | |
934 | * buffer. */ | |
935 | wvalue=0; /* The 'value' of the window */ | |
936 | wstart=bits-1; /* The top bit of the window */ | |
937 | wend=0; /* The bottom bit of the window */ | |
938 | ||
939 | if (!BN_one(r)) goto err; | |
940 | ||
941 | for (;;) | |
942 | { | |
943 | if (BN_is_bit_set(p,wstart) == 0) | |
944 | { | |
945 | if (!start) | |
946 | if (!BN_mod_mul(r,r,r,m,ctx)) | |
947 | goto err; | |
948 | if (wstart == 0) break; | |
949 | wstart--; | |
950 | continue; | |
951 | } | |
952 | /* We now have wstart on a 'set' bit, we now need to work out | |
953 | * how bit a window to do. To do this we need to scan | |
954 | * forward until the last set bit before the end of the | |
955 | * window */ | |
956 | j=wstart; | |
957 | wvalue=1; | |
958 | wend=0; | |
959 | for (i=1; i<window; i++) | |
960 | { | |
961 | if (wstart-i < 0) break; | |
962 | if (BN_is_bit_set(p,wstart-i)) | |
963 | { | |
964 | wvalue<<=(i-wend); | |
965 | wvalue|=1; | |
966 | wend=i; | |
967 | } | |
968 | } | |
969 | ||
970 | /* wend is the size of the current window */ | |
971 | j=wend+1; | |
972 | /* add the 'bytes above' */ | |
973 | if (!start) | |
974 | for (i=0; i<j; i++) | |
975 | { | |
976 | if (!BN_mod_mul(r,r,r,m,ctx)) | |
977 | goto err; | |
978 | } | |
979 | ||
980 | /* wvalue will be an odd number < 2^window */ | |
c86f2054 | 981 | if (!BN_mod_mul(r,r,val[wvalue>>1],m,ctx)) |
d02b48c6 RE |
982 | goto err; |
983 | ||
984 | /* move the 'window' down further */ | |
985 | wstart-=wend+1; | |
986 | wvalue=0; | |
987 | start=0; | |
988 | if (wstart < 0) break; | |
989 | } | |
990 | ret=1; | |
991 | err: | |
9b141126 | 992 | BN_CTX_end(ctx); |
d870740c | 993 | bn_check_top(r); |
d02b48c6 RE |
994 | return(ret); |
995 | } | |
996 |