Branch data Line data Source code
1 : : /* crypto/bn/bn_exp.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.
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 : : */
58 : : /* ====================================================================
59 : : * Copyright (c) 1998-2005 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
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 : :
112 : : #define OPENSSL_FIPSAPI
113 : :
114 : : #include "cryptlib.h"
115 : : #include "bn_lcl.h"
116 : :
117 : : #include <stdlib.h>
118 : : #ifdef _WIN32
119 : : # include <malloc.h>
120 : : # ifndef alloca
121 : : # define alloca _alloca
122 : : # endif
123 : : #elif defined(__GNUC__)
124 : : # ifndef alloca
125 : : # define alloca(s) __builtin_alloca((s))
126 : : # endif
127 : : #elif defined(__sun)
128 : : # include <alloca.h>
129 : : #endif
130 : :
131 : : #undef RSAZ_ENABLED
132 : : #if defined(OPENSSL_BN_ASM_MONT) && \
133 : : (defined(__x86_64) || defined(__x86_64__) || \
134 : : defined(_M_AMD64) || defined(_M_X64))
135 : : # include "rsaz_exp.h"
136 : : # define RSAZ_ENABLED
137 : : #endif
138 : :
139 : : #undef SPARC_T4_MONT
140 : : #if defined(OPENSSL_BN_ASM_MONT) && (defined(__sparc__) || defined(__sparc))
141 : : # include "sparc_arch.h"
142 : : extern unsigned int OPENSSL_sparcv9cap_P[];
143 : : # define SPARC_T4_MONT
144 : : #endif
145 : :
146 : : /* maximum precomputation table size for *variable* sliding windows */
147 : : #define TABLE_SIZE 32
148 : :
149 : : /* this one works - simple but works */
150 : 15 : int BN_exp(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx)
151 : : {
152 : 15 : int i,bits,ret=0;
153 : : BIGNUM *v,*rr;
154 : :
155 [ - + ]: 15 : if (BN_get_flags(p, BN_FLG_CONSTTIME) != 0)
156 : : {
157 : : /* BN_FLG_CONSTTIME only supported by BN_mod_exp_mont() */
158 : 0 : BNerr(BN_F_BN_EXP,ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
159 : 0 : return -1;
160 : : }
161 : :
162 : 15 : BN_CTX_start(ctx);
163 [ - + ]: 15 : if ((r == a) || (r == p))
164 : 0 : rr = BN_CTX_get(ctx);
165 : : else
166 : : rr = r;
167 : 15 : v = BN_CTX_get(ctx);
168 [ + - ]: 15 : if (rr == NULL || v == NULL) goto err;
169 : :
170 [ + - ]: 15 : if (BN_copy(v,a) == NULL) goto err;
171 : 15 : bits=BN_num_bits(p);
172 : :
173 [ + - ][ + + ]: 15 : if (BN_is_odd(p))
174 [ + - ]: 8 : { if (BN_copy(rr,a) == NULL) goto err; }
175 [ + - ]: 15 : else { if (!BN_one(rr)) goto err; }
176 : :
177 [ + + ]: 60 : for (i=1; i<bits; i++)
178 : : {
179 [ + - ]: 45 : if (!BN_sqr(v,v,ctx)) goto err;
180 [ + + ]: 45 : if (BN_is_bit_set(p,i))
181 : : {
182 [ + - ]: 27 : if (!BN_mul(rr,rr,v,ctx)) goto err;
183 : : }
184 : : }
185 : : ret=1;
186 : : err:
187 [ - + ]: 15 : if (r != rr) BN_copy(r,rr);
188 : 15 : BN_CTX_end(ctx);
189 : : bn_check_top(r);
190 : 15 : return(ret);
191 : : }
192 : :
193 : :
194 : 1399 : int BN_mod_exp(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, const BIGNUM *m,
195 : : BN_CTX *ctx)
196 : : {
197 : : int ret;
198 : :
199 : : bn_check_top(a);
200 : : bn_check_top(p);
201 : : bn_check_top(m);
202 : :
203 : : /* For even modulus m = 2^k*m_odd, it might make sense to compute
204 : : * a^p mod m_odd and a^p mod 2^k separately (with Montgomery
205 : : * exponentiation for the odd part), using appropriate exponent
206 : : * reductions, and combine the results using the CRT.
207 : : *
208 : : * For now, we use Montgomery only if the modulus is odd; otherwise,
209 : : * exponentiation using the reciprocal-based quick remaindering
210 : : * algorithm is used.
211 : : *
212 : : * (Timing obtained with expspeed.c [computations a^p mod m
213 : : * where a, p, m are of the same length: 256, 512, 1024, 2048,
214 : : * 4096, 8192 bits], compared to the running time of the
215 : : * standard algorithm:
216 : : *
217 : : * BN_mod_exp_mont 33 .. 40 % [AMD K6-2, Linux, debug configuration]
218 : : * 55 .. 77 % [UltraSparc processor, but
219 : : * debug-solaris-sparcv8-gcc conf.]
220 : : *
221 : : * BN_mod_exp_recp 50 .. 70 % [AMD K6-2, Linux, debug configuration]
222 : : * 62 .. 118 % [UltraSparc, debug-solaris-sparcv8-gcc]
223 : : *
224 : : * On the Sparc, BN_mod_exp_recp was faster than BN_mod_exp_mont
225 : : * at 2048 and more bits, but at 512 and 1024 bits, it was
226 : : * slower even than the standard algorithm!
227 : : *
228 : : * "Real" timings [linux-elf, solaris-sparcv9-gcc configurations]
229 : : * should be obtained when the new Montgomery reduction code
230 : : * has been integrated into OpenSSL.)
231 : : */
232 : :
233 : : #define MONT_MUL_MOD
234 : : #define MONT_EXP_WORD
235 : : #define RECP_MUL_MOD
236 : :
237 : : #ifdef MONT_MUL_MOD
238 : : /* I have finally been able to take out this pre-condition of
239 : : * the top bit being set. It was caused by an error in BN_div
240 : : * with negatives. There was also another problem when for a^b%m
241 : : * a >= m. eay 07-May-97 */
242 : : /* if ((m->d[m->top-1]&BN_TBIT) && BN_is_odd(m)) */
243 : :
244 [ + - ][ + - ]: 1399 : if (BN_is_odd(m))
245 : : {
246 : : # ifdef MONT_EXP_WORD
247 [ + + ][ + - ]: 1399 : if (a->top == 1 && !a->neg && (BN_get_flags(p, BN_FLG_CONSTTIME) == 0))
[ + - ]
248 : 143 : {
249 : 143 : BN_ULONG A = a->d[0];
250 : 143 : ret=BN_mod_exp_mont_word(r,A,p,m,ctx,NULL);
251 : : }
252 : : else
253 : : # endif
254 : 1256 : ret=BN_mod_exp_mont(r,a,p,m,ctx,NULL);
255 : : }
256 : : else
257 : : #endif
258 : : #ifdef RECP_MUL_MOD
259 : 0 : { ret=BN_mod_exp_recp(r,a,p,m,ctx); }
260 : : #else
261 : : { ret=BN_mod_exp_simple(r,a,p,m,ctx); }
262 : : #endif
263 : :
264 : : bn_check_top(r);
265 : 1399 : return(ret);
266 : : }
267 : :
268 : :
269 : 300 : int BN_mod_exp_recp(BIGNUM *r, const BIGNUM *a, const BIGNUM *p,
270 : : const BIGNUM *m, BN_CTX *ctx)
271 : : {
272 : 300 : int i,j,bits,ret=0,wstart,wend,window,wvalue;
273 : 300 : int start=1;
274 : : BIGNUM *aa;
275 : : /* Table of variables obtained from 'ctx' */
276 : : BIGNUM *val[TABLE_SIZE];
277 : : BN_RECP_CTX recp;
278 : :
279 [ - + ]: 300 : if (BN_get_flags(p, BN_FLG_CONSTTIME) != 0)
280 : : {
281 : : /* BN_FLG_CONSTTIME only supported by BN_mod_exp_mont() */
282 : 0 : BNerr(BN_F_BN_MOD_EXP_RECP,ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
283 : 0 : return -1;
284 : : }
285 : :
286 : 300 : bits=BN_num_bits(p);
287 : :
288 [ - + ]: 300 : if (bits == 0)
289 : : {
290 : 0 : ret = BN_one(r);
291 : 0 : return ret;
292 : : }
293 : :
294 : 300 : BN_CTX_start(ctx);
295 : 300 : aa = BN_CTX_get(ctx);
296 : 300 : val[0] = BN_CTX_get(ctx);
297 [ + - ][ + - ]: 300 : if(!aa || !val[0]) goto err;
298 : :
299 : 300 : BN_RECP_CTX_init(&recp);
300 [ - + ]: 300 : if (m->neg)
301 : : {
302 : : /* ignore sign of 'm' */
303 [ # # ]: 0 : if (!BN_copy(aa, m)) goto err;
304 : 0 : aa->neg = 0;
305 [ # # ]: 0 : if (BN_RECP_CTX_set(&recp,aa,ctx) <= 0) goto err;
306 : : }
307 : : else
308 : : {
309 [ + - ]: 300 : if (BN_RECP_CTX_set(&recp,m,ctx) <= 0) goto err;
310 : : }
311 : :
312 [ + - ]: 300 : if (!BN_nnmod(val[0],a,m,ctx)) goto err; /* 1 */
313 [ - + ]: 300 : if (BN_is_zero(val[0]))
314 : : {
315 : 0 : BN_zero(r);
316 : 0 : ret = 1;
317 : 0 : goto err;
318 : : }
319 : :
320 [ + - ][ - + ]: 300 : window = BN_window_bits_for_exponent_size(bits);
[ # # ][ # # ]
321 [ + - ]: 300 : if (window > 1)
322 : : {
323 [ + - ]: 300 : if (!BN_mod_mul_reciprocal(aa,val[0],val[0],&recp,ctx))
324 : : goto err; /* 2 */
325 : 300 : j=1<<(window-1);
326 [ + + ]: 4800 : for (i=1; i<j; i++)
327 : : {
328 [ + - + - ]: 9000 : if(((val[i] = BN_CTX_get(ctx)) == NULL) ||
329 : 4500 : !BN_mod_mul_reciprocal(val[i],val[i-1],
330 : : aa,&recp,ctx))
331 : : goto err;
332 : : }
333 : : }
334 : :
335 : 300 : start=1; /* This is used to avoid multiplication etc
336 : : * when there is only the value '1' in the
337 : : * buffer. */
338 : 300 : wvalue=0; /* The 'value' of the window */
339 : 300 : wstart=bits-1; /* The top bit of the window */
340 : 300 : wend=0; /* The bottom bit of the window */
341 : :
342 [ + - ]: 55541 : if (!BN_one(r)) goto err;
343 : :
344 : : for (;;)
345 : : {
346 [ + + ]: 55541 : if (BN_is_bit_set(p,wstart) == 0)
347 : : {
348 [ + - ]: 36334 : if (!start)
349 [ + - ]: 36334 : if (!BN_mod_mul_reciprocal(r,r,r,&recp,ctx))
350 : : goto err;
351 [ + + ]: 36334 : if (wstart == 0) break;
352 : 36140 : wstart--;
353 : 36140 : continue;
354 : : }
355 : : /* We now have wstart on a 'set' bit, we now need to work out
356 : : * how bit a window to do. To do this we need to scan
357 : : * forward until the last set bit before the end of the
358 : : * window */
359 : : j=wstart;
360 : : wvalue=1;
361 : : wend=0;
362 [ + + ]: 95508 : for (i=1; i<window; i++)
363 : : {
364 [ + + ]: 76524 : if (wstart-i < 0) break;
365 [ + + ]: 76301 : if (BN_is_bit_set(p,wstart-i))
366 : : {
367 : 38707 : wvalue<<=(i-wend);
368 : 38707 : wvalue|=1;
369 : 38707 : wend=i;
370 : : }
371 : : }
372 : :
373 : : /* wend is the size of the current window */
374 : 19207 : j=wend+1;
375 : : /* add the 'bytes above' */
376 [ + + ]: 19207 : if (!start)
377 [ + + ]: 96471 : for (i=0; i<j; i++)
378 : : {
379 [ + - ]: 77564 : if (!BN_mod_mul_reciprocal(r,r,r,&recp,ctx))
380 : : goto err;
381 : : }
382 : :
383 : : /* wvalue will be an odd number < 2^window */
384 [ + - ]: 19207 : if (!BN_mod_mul_reciprocal(r,r,val[wvalue>>1],&recp,ctx))
385 : : goto err;
386 : :
387 : : /* move the 'window' down further */
388 : 19207 : wstart-=wend+1;
389 : 19207 : wvalue=0;
390 : 19207 : start=0;
391 [ + + ]: 19207 : if (wstart < 0) break;
392 : : }
393 : : ret=1;
394 : : err:
395 : 300 : BN_CTX_end(ctx);
396 : 300 : BN_RECP_CTX_free(&recp);
397 : : bn_check_top(r);
398 : 300 : return(ret);
399 : : }
400 : :
401 : :
402 : 11613 : int BN_mod_exp_mont(BIGNUM *rr, const BIGNUM *a, const BIGNUM *p,
403 : : const BIGNUM *m, BN_CTX *ctx, BN_MONT_CTX *in_mont)
404 : : {
405 : 11613 : int i,j,bits,ret=0,wstart,wend,window,wvalue;
406 : 11613 : int start=1;
407 : : BIGNUM *d,*r;
408 : : const BIGNUM *aa;
409 : : /* Table of variables obtained from 'ctx' */
410 : : BIGNUM *val[TABLE_SIZE];
411 : 11613 : BN_MONT_CTX *mont=NULL;
412 : :
413 [ + + ]: 11613 : if (BN_get_flags(p, BN_FLG_CONSTTIME) != 0)
414 : : {
415 : 4064 : return BN_mod_exp_mont_consttime(rr, a, p, m, ctx, in_mont);
416 : : }
417 : :
418 : : bn_check_top(a);
419 : : bn_check_top(p);
420 : : bn_check_top(m);
421 : :
422 [ + - ][ - + ]: 7549 : if (!BN_is_odd(m))
423 : : {
424 : 0 : BNerr(BN_F_BN_MOD_EXP_MONT,BN_R_CALLED_WITH_EVEN_MODULUS);
425 : 0 : return(0);
426 : : }
427 : 7549 : bits=BN_num_bits(p);
428 [ - + ]: 7549 : if (bits == 0)
429 : : {
430 : 0 : ret = BN_one(rr);
431 : 0 : return ret;
432 : : }
433 : :
434 : 7549 : BN_CTX_start(ctx);
435 : 7549 : d = BN_CTX_get(ctx);
436 : 7549 : r = BN_CTX_get(ctx);
437 : 7549 : val[0] = BN_CTX_get(ctx);
438 [ + - ][ + - ]: 7549 : if (!d || !r || !val[0]) goto err;
439 : :
440 : : /* If this is not done, things will break in the montgomery
441 : : * part */
442 : :
443 [ + + ]: 7549 : if (in_mont != NULL)
444 : : mont=in_mont;
445 : : else
446 : : {
447 [ + - ]: 1454 : if ((mont=BN_MONT_CTX_new()) == NULL) goto err;
448 [ + - ]: 1454 : if (!BN_MONT_CTX_set(mont,m,ctx)) goto err;
449 : : }
450 : :
451 [ + - ][ - + ]: 7549 : if (a->neg || BN_ucmp(a,m) >= 0)
452 : : {
453 [ # # ]: 0 : if (!BN_nnmod(val[0],a,m,ctx))
454 : : goto err;
455 : : aa= val[0];
456 : : }
457 : : else
458 : : aa=a;
459 [ + + ]: 7549 : if (BN_is_zero(aa))
460 : : {
461 : 2 : BN_zero(rr);
462 : 2 : ret = 1;
463 : 2 : goto err;
464 : : }
465 [ + - ]: 7547 : if (!BN_to_montgomery(val[0],aa,mont,ctx)) goto err; /* 1 */
466 : :
467 [ + - ][ + + ]: 7547 : window = BN_window_bits_for_exponent_size(bits);
[ + + ][ + + ]
468 [ + + ]: 7547 : if (window > 1)
469 : : {
470 [ + - ]: 2905 : if (!BN_mod_mul_montgomery(d,val[0],val[0],mont,ctx)) goto err; /* 2 */
471 : 2905 : j=1<<(window-1);
472 [ + + ]: 43584 : for (i=1; i<j; i++)
473 : : {
474 [ + - + - ]: 81358 : if(((val[i] = BN_CTX_get(ctx)) == NULL) ||
475 : 40679 : !BN_mod_mul_montgomery(val[i],val[i-1],
476 : : d,mont,ctx))
477 : : goto err;
478 : : }
479 : : }
480 : :
481 : 7547 : start=1; /* This is used to avoid multiplication etc
482 : : * when there is only the value '1' in the
483 : : * buffer. */
484 : 7547 : wvalue=0; /* The 'value' of the window */
485 : 7547 : wstart=bits-1; /* The top bit of the window */
486 : 7547 : wend=0; /* The bottom bit of the window */
487 : :
488 : : #if 1 /* by Shay Gueron's suggestion */
489 : 7547 : j = m->top; /* borrow j */
490 [ + + ]: 7547 : if (m->d[j-1] & (((BN_ULONG)1)<<(BN_BITS2-1)))
491 : : {
492 [ + + ][ + - ]: 7104 : if (bn_wexpand(r,j) == NULL) goto err;
493 : : /* 2^(top*BN_BITS2) - m */
494 : 7104 : r->d[0] = (0-m->d[0])&BN_MASK2;
495 [ + + ]: 101368 : for(i=1;i<j;i++) r->d[i] = (~m->d[i])&BN_MASK2;
496 : 7104 : r->top = j;
497 : : /* Upper words will be zero if the corresponding words of 'm'
498 : : * were 0xfff[...], so decrement r->top accordingly. */
499 [ + - ][ + + ]: 7593 : bn_correct_top(r);
[ + - ]
500 : : }
501 : : else
502 : : #endif
503 [ + - ]: 510275 : if (!BN_to_montgomery(r,BN_value_one(),mont,ctx)) goto err;
504 : : for (;;)
505 : : {
506 [ + + ]: 517379 : if (BN_is_bit_set(p,wstart) == 0)
507 : : {
508 [ + - ]: 355144 : if (!start)
509 : : {
510 [ + - ]: 355144 : if (!BN_mod_mul_montgomery(r,r,r,mont,ctx))
511 : : goto err;
512 : : }
513 [ + + ]: 355144 : if (wstart == 0) break;
514 : 354959 : wstart--;
515 : 354959 : continue;
516 : : }
517 : : /* We now have wstart on a 'set' bit, we now need to work out
518 : : * how bit a window to do. To do this we need to scan
519 : : * forward until the last set bit before the end of the
520 : : * window */
521 : : j=wstart;
522 : : wvalue=1;
523 : : wend=0;
524 [ + + ]: 757337 : for (i=1; i<window; i++)
525 : : {
526 [ + + ]: 597395 : if (wstart-i < 0) break;
527 [ + + ]: 595102 : if (BN_is_bit_set(p,wstart-i))
528 : : {
529 : 306636 : wvalue<<=(i-wend);
530 : 306636 : wvalue|=1;
531 : 306636 : wend=i;
532 : : }
533 : : }
534 : :
535 : : /* wend is the size of the current window */
536 : 162235 : j=wend+1;
537 : : /* add the 'bytes above' */
538 [ + + ]: 162235 : if (!start)
539 [ + + ]: 758536 : for (i=0; i<j; i++)
540 : : {
541 [ + - ]: 603848 : if (!BN_mod_mul_montgomery(r,r,r,mont,ctx))
542 : : goto err;
543 : : }
544 : :
545 : : /* wvalue will be an odd number < 2^window */
546 [ + - ]: 162235 : if (!BN_mod_mul_montgomery(r,r,val[wvalue>>1],mont,ctx))
547 : : goto err;
548 : :
549 : : /* move the 'window' down further */
550 : 162235 : wstart-=wend+1;
551 : 162235 : wvalue=0;
552 : 162235 : start=0;
553 [ + + ]: 162235 : if (wstart < 0) break;
554 : : }
555 : : #if defined(SPARC_T4_MONT)
556 : : if (OPENSSL_sparcv9cap_P[0]&(SPARCV9_VIS3|SPARCV9_PREFER_FPU))
557 : : {
558 : : j = mont->N.top; /* borrow j */
559 : : val[0]->d[0] = 1; /* borrow val[0] */
560 : : for (i=1;i<j;i++) val[0]->d[i] = 0;
561 : : val[0]->top = j;
562 : : if (!BN_mod_mul_montgomery(rr,r,val[0],mont,ctx)) goto err;
563 : : }
564 : : else
565 : : #endif
566 [ + - ]: 7547 : if (!BN_from_montgomery(rr,r,mont,ctx)) goto err;
567 : 7547 : ret=1;
568 : : err:
569 [ + + ]: 7549 : if ((in_mont == NULL) && (mont != NULL)) BN_MONT_CTX_free(mont);
570 : 7549 : BN_CTX_end(ctx);
571 : : bn_check_top(rr);
572 : 7549 : return(ret);
573 : : }
574 : :
575 : : #if defined(SPARC_T4_MONT)
576 : : static BN_ULONG bn_get_bits(const BIGNUM *a, int bitpos)
577 : : {
578 : : BN_ULONG ret=0;
579 : : int wordpos;
580 : :
581 : : wordpos = bitpos/BN_BITS2;
582 : : bitpos %= BN_BITS2;
583 : : if (wordpos>=0 && wordpos < a->top)
584 : : {
585 : : ret = a->d[wordpos]&BN_MASK2;
586 : : if (bitpos)
587 : : {
588 : : ret >>= bitpos;
589 : : if (++wordpos < a->top)
590 : : ret |= a->d[wordpos]<<(BN_BITS2-bitpos);
591 : : }
592 : : }
593 : :
594 : : return ret&BN_MASK2;
595 : : }
596 : : #endif
597 : :
598 : : /* BN_mod_exp_mont_consttime() stores the precomputed powers in a specific layout
599 : : * so that accessing any of these table values shows the same access pattern as far
600 : : * as cache lines are concerned. The following functions are used to transfer a BIGNUM
601 : : * from/to that table. */
602 : :
603 : 14324 : static int MOD_EXP_CTIME_COPY_TO_PREBUF(const BIGNUM *b, int top, unsigned char *buf, int idx, int width)
604 : : {
605 : : size_t i, j;
606 : :
607 [ + + ]: 7162 : if (top > b->top)
608 : 60 : top = b->top; /* this works because 'buf' is explicitly zeroed */
609 [ + + ]: 628074 : for (i = 0, j=idx; i < top * sizeof b->d[0]; i++, j+=width)
610 : : {
611 : 620912 : buf[j] = ((unsigned char*)b->d)[i];
612 : : }
613 : :
614 : 7162 : return 1;
615 : : }
616 : :
617 : 23810 : static int MOD_EXP_CTIME_COPY_FROM_PREBUF(BIGNUM *b, int top, unsigned char *buf, int idx, int width)
618 : : {
619 : : size_t i, j;
620 : :
621 [ - + ][ + - ]: 23810 : if (bn_wexpand(b, top) == NULL)
622 : : return 0;
623 : :
624 [ + + ]: 1841802 : for (i=0, j=idx; i < top * sizeof b->d[0]; i++, j+=width)
625 : : {
626 : 1817992 : ((unsigned char*)b->d)[i] = buf[j];
627 : : }
628 : :
629 : 23810 : b->top = top;
630 [ + - ][ + + ]: 24056 : bn_correct_top(b);
[ + - ]
631 : : return 1;
632 : : }
633 : :
634 : : /* Given a pointer value, compute the next address that is a cache line multiple. */
635 : : #define MOD_EXP_CTIME_ALIGN(x_) \
636 : : ((unsigned char*)(x_) + (MOD_EXP_CTIME_MIN_CACHE_LINE_WIDTH - (((size_t)(x_)) & (MOD_EXP_CTIME_MIN_CACHE_LINE_MASK))))
637 : :
638 : : /* This variant of BN_mod_exp_mont() uses fixed windows and the special
639 : : * precomputation memory layout to limit data-dependency to a minimum
640 : : * to protect secret exponents (cf. the hyper-threading timing attacks
641 : : * pointed out by Colin Percival,
642 : : * http://www.daemonology.net/hyperthreading-considered-harmful/)
643 : : */
644 : 4273 : int BN_mod_exp_mont_consttime(BIGNUM *rr, const BIGNUM *a, const BIGNUM *p,
645 : : const BIGNUM *m, BN_CTX *ctx, BN_MONT_CTX *in_mont)
646 : : {
647 : 4273 : int i,bits,ret=0,window,wvalue;
648 : : int top;
649 : 4273 : BN_MONT_CTX *mont=NULL;
650 : :
651 : : int numPowers;
652 : 4273 : unsigned char *powerbufFree=NULL;
653 : 4273 : int powerbufLen = 0;
654 : 4273 : unsigned char *powerbuf=NULL;
655 : : BIGNUM tmp, am;
656 : : #if defined(SPARC_T4_MONT)
657 : : unsigned int t4=0;
658 : : #endif
659 : :
660 : : bn_check_top(a);
661 : : bn_check_top(p);
662 : : bn_check_top(m);
663 : :
664 : 4273 : top = m->top;
665 : :
666 [ - + ]: 4273 : if (!(m->d[0] & 1))
667 : : {
668 : 0 : BNerr(BN_F_BN_MOD_EXP_MONT_CONSTTIME,BN_R_CALLED_WITH_EVEN_MODULUS);
669 : 0 : return(0);
670 : : }
671 : 4273 : bits=BN_num_bits(p);
672 [ + + ]: 4273 : if (bits == 0)
673 : : {
674 : 1 : ret = BN_one(rr);
675 : 1 : return ret;
676 : : }
677 : :
678 : 4272 : BN_CTX_start(ctx);
679 : :
680 : : /* Allocate a montgomery context if it was not supplied by the caller.
681 : : * If this is not done, things will break in the montgomery part.
682 : : */
683 [ + + ]: 4272 : if (in_mont != NULL)
684 : : mont=in_mont;
685 : : else
686 : : {
687 [ + - ]: 210 : if ((mont=BN_MONT_CTX_new()) == NULL) goto err;
688 [ + - ]: 210 : if (!BN_MONT_CTX_set(mont,m,ctx)) goto err;
689 : : }
690 : :
691 : : #ifdef RSAZ_ENABLED
692 : : /*
693 : : * If the size of the operands allow it, perform the optimized
694 : : * RSAZ exponentiation. For further information see
695 : : * crypto/bn/rsaz_exp.c and accompanying assembly modules.
696 : : */
697 [ + + ][ + + ]: 4272 : if ((16 == a->top) && (16 == p->top) && (BN_num_bits(m) == 1024)
[ + - ]
698 [ - + ]: 788 : && rsaz_avx2_eligible())
699 : : {
700 [ # # ][ # # ]: 0 : if (NULL == bn_wexpand(rr, 16)) goto err;
701 : 0 : RSAZ_1024_mod_exp_avx2(rr->d, a->d, p->d, m->d, mont->RR.d, mont->n0[0]);
702 : 0 : rr->top = 16;
703 : 0 : rr->neg = 0;
704 [ # # ][ # # ]: 0 : bn_correct_top(rr);
705 : 0 : ret = 1;
706 : 0 : goto err;
707 : : }
708 [ + + ][ + + ]: 4272 : else if ((8 == a->top) && (8 == p->top) && (BN_num_bits(m) == 512))
[ + + ]
709 : : {
710 [ + + ][ + - ]: 2168 : if (NULL == bn_wexpand(rr,8)) goto err;
711 : 2168 : RSAZ_512_mod_exp(rr->d, a->d, p->d, m->d, mont->n0[0], mont->RR.d);
712 : 2168 : rr->top = 8;
713 : 2168 : rr->neg = 0;
714 [ - + ][ + - ]: 2168 : bn_correct_top(rr);
715 : 2168 : ret = 1;
716 : 2168 : goto err;
717 : : }
718 : : #endif
719 : :
720 : : /* Get the window size to use with size of p. */
721 [ + + ][ + + ]: 2104 : window = BN_window_bits_for_ctime_exponent_size(bits);
[ + + ][ + + ]
722 : : #if defined(SPARC_T4_MONT)
723 : : if (window>=5 && (top&15)==0 && top<=64 &&
724 : : (OPENSSL_sparcv9cap_P[1]&(CFR_MONTMUL|CFR_MONTSQR))==
725 : : (CFR_MONTMUL|CFR_MONTSQR) &&
726 : : (t4=OPENSSL_sparcv9cap_P[0]))
727 : : window=5;
728 : : else
729 : : #endif
730 : : #if defined(OPENSSL_BN_ASM_MONT5)
731 [ + + ]: 2104 : if (window>=5)
732 : : {
733 : 1651 : window=5; /* ~5% improvement for RSA2048 sign, and even for RSA4096 */
734 [ + + ]: 1651 : if ((top&7)==0) powerbufLen += 2*top*sizeof(m->d[0]);
735 : : }
736 : : #endif
737 : : (void)0;
738 : :
739 : : /* Allocate a buffer large enough to hold all of the pre-computed
740 : : * powers of am, am itself and tmp.
741 : : */
742 : 2104 : numPowers = 1 << window;
743 : 4208 : powerbufLen += sizeof(m->d[0])*(top*numPowers +
744 : 2104 : ((2*top)>numPowers?(2*top):numPowers));
745 : : #ifdef alloca
746 [ + + ]: 2104 : if (powerbufLen < 3072)
747 : 1311 : powerbufFree = alloca(powerbufLen+MOD_EXP_CTIME_MIN_CACHE_LINE_WIDTH);
748 : : else
749 : : #endif
750 [ + - ]: 793 : if ((powerbufFree=(unsigned char*)OPENSSL_malloc(powerbufLen+MOD_EXP_CTIME_MIN_CACHE_LINE_WIDTH)) == NULL)
751 : : goto err;
752 : :
753 : 2104 : powerbuf = MOD_EXP_CTIME_ALIGN(powerbufFree);
754 : 2104 : memset(powerbuf, 0, powerbufLen);
755 : :
756 : : #ifdef alloca
757 [ + + ]: 2104 : if (powerbufLen < 3072)
758 : 1311 : powerbufFree = NULL;
759 : : #endif
760 : :
761 : : /* lay down tmp and am right after powers table */
762 : 2104 : tmp.d = (BN_ULONG *)(powerbuf + sizeof(m->d[0])*top*numPowers);
763 : 2104 : am.d = tmp.d + top;
764 : 2104 : tmp.top = am.top = 0;
765 : 2104 : tmp.dmax = am.dmax = top;
766 : 2104 : tmp.neg = am.neg = 0;
767 : 2104 : tmp.flags = am.flags = BN_FLG_STATIC_DATA;
768 : :
769 : : /* prepare a^0 in Montgomery domain */
770 : : #if 1 /* by Shay Gueron's suggestion */
771 [ + + ]: 2104 : if (m->d[top-1] & (((BN_ULONG)1)<<(BN_BITS2-1)))
772 : : {
773 : : /* 2^(top*BN_BITS2) - m */
774 : 1893 : tmp.d[0] = (0-m->d[0])&BN_MASK2;
775 [ + + ]: 23048 : for (i=1;i<top;i++) tmp.d[i] = (~m->d[i])&BN_MASK2;
776 : 1893 : tmp.top = top;
777 : : }
778 : : else
779 : : #endif
780 [ + - ]: 211 : if (!BN_to_montgomery(&tmp,BN_value_one(),mont,ctx)) goto err;
781 : :
782 : : /* prepare a^1 in Montgomery domain */
783 [ + - ][ + + ]: 2104 : if (a->neg || BN_ucmp(a,m) >= 0)
784 : : {
785 [ + - ]: 4 : if (!BN_mod(&am,a,m,ctx)) goto err;
786 [ + - ]: 4 : if (!BN_to_montgomery(&am,&am,mont,ctx)) goto err;
787 : : }
788 [ + - ]: 2100 : else if (!BN_to_montgomery(&am,a,mont,ctx)) goto err;
789 : :
790 : : #if defined(SPARC_T4_MONT)
791 : : if (t4)
792 : : {
793 : : typedef int (*bn_pwr5_mont_f)(BN_ULONG *tp,const BN_ULONG *np,
794 : : const BN_ULONG *n0,const void *table,int power,int bits);
795 : : int bn_pwr5_mont_t4_8(BN_ULONG *tp,const BN_ULONG *np,
796 : : const BN_ULONG *n0,const void *table,int power,int bits);
797 : : int bn_pwr5_mont_t4_16(BN_ULONG *tp,const BN_ULONG *np,
798 : : const BN_ULONG *n0,const void *table,int power,int bits);
799 : : int bn_pwr5_mont_t4_24(BN_ULONG *tp,const BN_ULONG *np,
800 : : const BN_ULONG *n0,const void *table,int power,int bits);
801 : : int bn_pwr5_mont_t4_32(BN_ULONG *tp,const BN_ULONG *np,
802 : : const BN_ULONG *n0,const void *table,int power,int bits);
803 : : static const bn_pwr5_mont_f pwr5_funcs[4] = {
804 : : bn_pwr5_mont_t4_8, bn_pwr5_mont_t4_16,
805 : : bn_pwr5_mont_t4_24, bn_pwr5_mont_t4_32 };
806 : : bn_pwr5_mont_f pwr5_worker = pwr5_funcs[top/16-1];
807 : :
808 : : typedef int (*bn_mul_mont_f)(BN_ULONG *rp,const BN_ULONG *ap,
809 : : const void *bp,const BN_ULONG *np,const BN_ULONG *n0);
810 : : int bn_mul_mont_t4_8(BN_ULONG *rp,const BN_ULONG *ap,
811 : : const void *bp,const BN_ULONG *np,const BN_ULONG *n0);
812 : : int bn_mul_mont_t4_16(BN_ULONG *rp,const BN_ULONG *ap,
813 : : const void *bp,const BN_ULONG *np,const BN_ULONG *n0);
814 : : int bn_mul_mont_t4_24(BN_ULONG *rp,const BN_ULONG *ap,
815 : : const void *bp,const BN_ULONG *np,const BN_ULONG *n0);
816 : : int bn_mul_mont_t4_32(BN_ULONG *rp,const BN_ULONG *ap,
817 : : const void *bp,const BN_ULONG *np,const BN_ULONG *n0);
818 : : static const bn_mul_mont_f mul_funcs[4] = {
819 : : bn_mul_mont_t4_8, bn_mul_mont_t4_16,
820 : : bn_mul_mont_t4_24, bn_mul_mont_t4_32 };
821 : : bn_mul_mont_f mul_worker = mul_funcs[top/16-1];
822 : :
823 : : void bn_mul_mont_vis3(BN_ULONG *rp,const BN_ULONG *ap,
824 : : const void *bp,const BN_ULONG *np,
825 : : const BN_ULONG *n0,int num);
826 : : void bn_mul_mont_t4(BN_ULONG *rp,const BN_ULONG *ap,
827 : : const void *bp,const BN_ULONG *np,
828 : : const BN_ULONG *n0,int num);
829 : : void bn_mul_mont_gather5_t4(BN_ULONG *rp,const BN_ULONG *ap,
830 : : const void *table,const BN_ULONG *np,
831 : : const BN_ULONG *n0,int num,int power);
832 : : void bn_flip_n_scatter5_t4(const BN_ULONG *inp,size_t num,
833 : : void *table,size_t power);
834 : : void bn_gather5_t4(BN_ULONG *out,size_t num,
835 : : void *table,size_t power);
836 : : void bn_flip_t4(BN_ULONG *dst,BN_ULONG *src,size_t num);
837 : :
838 : : BN_ULONG *np=mont->N.d, *n0=mont->n0;
839 : : int stride = 5*(6-(top/16-1)); /* multiple of 5, but less than 32 */
840 : :
841 : : /* BN_to_montgomery can contaminate words above .top
842 : : * [in BN_DEBUG[_DEBUG] build]... */
843 : : for (i=am.top; i<top; i++) am.d[i]=0;
844 : : for (i=tmp.top; i<top; i++) tmp.d[i]=0;
845 : :
846 : : bn_flip_n_scatter5_t4(tmp.d,top,powerbuf,0);
847 : : bn_flip_n_scatter5_t4(am.d,top,powerbuf,1);
848 : : if (!(*mul_worker)(tmp.d,am.d,am.d,np,n0) &&
849 : : !(*mul_worker)(tmp.d,am.d,am.d,np,n0))
850 : : bn_mul_mont_vis3(tmp.d,am.d,am.d,np,n0,top);
851 : : bn_flip_n_scatter5_t4(tmp.d,top,powerbuf,2);
852 : :
853 : : for (i=3; i<32; i++)
854 : : {
855 : : /* Calculate a^i = a^(i-1) * a */
856 : : if (!(*mul_worker)(tmp.d,tmp.d,am.d,np,n0) &&
857 : : !(*mul_worker)(tmp.d,tmp.d,am.d,np,n0))
858 : : bn_mul_mont_vis3(tmp.d,tmp.d,am.d,np,n0,top);
859 : : bn_flip_n_scatter5_t4(tmp.d,top,powerbuf,i);
860 : : }
861 : :
862 : : /* switch to 64-bit domain */
863 : : np = alloca(top*sizeof(BN_ULONG));
864 : : top /= 2;
865 : : bn_flip_t4(np,mont->N.d,top);
866 : :
867 : : bits--;
868 : : for (wvalue=0, i=bits%5; i>=0; i--,bits--)
869 : : wvalue = (wvalue<<1)+BN_is_bit_set(p,bits);
870 : : bn_gather5_t4(tmp.d,top,powerbuf,wvalue);
871 : :
872 : : /* Scan the exponent one window at a time starting from the most
873 : : * significant bits.
874 : : */
875 : : while (bits >= 0)
876 : : {
877 : : if (bits < stride) stride = bits+1;
878 : : bits -= stride;
879 : : wvalue = bn_get_bits(p,bits+1);
880 : :
881 : : if ((*pwr5_worker)(tmp.d,np,n0,powerbuf,wvalue,stride)) continue;
882 : : /* retry once and fall back */
883 : : if ((*pwr5_worker)(tmp.d,np,n0,powerbuf,wvalue,stride)) continue;
884 : :
885 : : bits += stride-5;
886 : : wvalue >>= stride-5;
887 : : wvalue &= 31;
888 : : bn_mul_mont_t4(tmp.d,tmp.d,tmp.d,np,n0,top);
889 : : bn_mul_mont_t4(tmp.d,tmp.d,tmp.d,np,n0,top);
890 : : bn_mul_mont_t4(tmp.d,tmp.d,tmp.d,np,n0,top);
891 : : bn_mul_mont_t4(tmp.d,tmp.d,tmp.d,np,n0,top);
892 : : bn_mul_mont_t4(tmp.d,tmp.d,tmp.d,np,n0,top);
893 : : bn_mul_mont_gather5_t4(tmp.d,tmp.d,powerbuf,np,n0,top,wvalue);
894 : : }
895 : :
896 : : bn_flip_t4(tmp.d,tmp.d,top);
897 : : top *= 2;
898 : : /* back to 32-bit domain */
899 : : tmp.top=top;
900 : : bn_correct_top(&tmp);
901 : : OPENSSL_cleanse(np,top*sizeof(BN_ULONG));
902 : : }
903 : : else
904 : : #endif
905 : : #if defined(OPENSSL_BN_ASM_MONT5)
906 : : /* This optimization uses ideas from http://eprint.iacr.org/2011/239,
907 : : * specifically optimization of cache-timing attack countermeasures
908 : : * and pre-computation optimization. */
909 : :
910 : : /* Dedicated window==4 case improves 512-bit RSA sign by ~15%, but as
911 : : * 512-bit RSA is hardly relevant, we omit it to spare size... */
912 [ + + ]: 2104 : if (window==5 && top>1)
913 : : {
914 : : void bn_mul_mont_gather5(BN_ULONG *rp,const BN_ULONG *ap,
915 : : const void *table,const BN_ULONG *np,
916 : : const BN_ULONG *n0,int num,int power);
917 : : void bn_scatter5(const BN_ULONG *inp,size_t num,
918 : : void *table,size_t power);
919 : : void bn_gather5(BN_ULONG *out,size_t num,
920 : : void *table,size_t power);
921 : : void bn_power5(BN_ULONG *rp,const BN_ULONG *ap,
922 : : const void *table,const BN_ULONG *np,
923 : : const BN_ULONG *n0,int num,int power);
924 : : int bn_get_bits5(const BN_ULONG *ap,int off);
925 : : int bn_from_montgomery(BN_ULONG *rp,const BN_ULONG *ap,
926 : : const BN_ULONG *not_used,const BN_ULONG *np,
927 : : const BN_ULONG *n0,int num);
928 : :
929 : 1651 : BN_ULONG *np=mont->N.d, *n0=mont->n0, *np2;
930 : :
931 : : /* BN_to_montgomery can contaminate words above .top
932 : : * [in BN_DEBUG[_DEBUG] build]... */
933 [ + + ]: 1684 : for (i=am.top; i<top; i++) am.d[i]=0;
934 [ + + ]: 1652 : for (i=tmp.top; i<top; i++) tmp.d[i]=0;
935 : :
936 [ + + ]: 1651 : if (top&7)
937 : : np2 = np;
938 : : else
939 [ + + ]: 21009 : for (np2=am.d+top,i=0; i<top; i++) np2[2*i]=np[i];
940 : :
941 : 1651 : bn_scatter5(tmp.d,top,powerbuf,0);
942 : 1651 : bn_scatter5(am.d,am.top,powerbuf,1);
943 : 1651 : bn_mul_mont(tmp.d,am.d,am.d,np,n0,top);
944 : 1651 : bn_scatter5(tmp.d,top,powerbuf,2);
945 : :
946 : : #if 0
947 : : for (i=3; i<32; i++)
948 : : {
949 : : /* Calculate a^i = a^(i-1) * a */
950 : : bn_mul_mont_gather5(tmp.d,am.d,powerbuf,np2,n0,top,i-1);
951 : : bn_scatter5(tmp.d,top,powerbuf,i);
952 : : }
953 : : #else
954 : : /* same as above, but uses squaring for 1/2 of operations */
955 [ + + ]: 6604 : for (i=4; i<32; i*=2)
956 : : {
957 : 4953 : bn_mul_mont(tmp.d,tmp.d,tmp.d,np,n0,top);
958 : 4953 : bn_scatter5(tmp.d,top,powerbuf,i);
959 : : }
960 [ + + ]: 6604 : for (i=3; i<8; i+=2)
961 : : {
962 : : int j;
963 : 4953 : bn_mul_mont_gather5(tmp.d,am.d,powerbuf,np2,n0,top,i-1);
964 : 4953 : bn_scatter5(tmp.d,top,powerbuf,i);
965 [ + + ]: 16510 : for (j=2*i; j<32; j*=2)
966 : : {
967 : 11557 : bn_mul_mont(tmp.d,tmp.d,tmp.d,np,n0,top);
968 : 11557 : bn_scatter5(tmp.d,top,powerbuf,j);
969 : : }
970 : : }
971 [ + + ]: 8255 : for (; i<16; i+=2)
972 : : {
973 : 6604 : bn_mul_mont_gather5(tmp.d,am.d,powerbuf,np2,n0,top,i-1);
974 : 6604 : bn_scatter5(tmp.d,top,powerbuf,i);
975 : 6604 : bn_mul_mont(tmp.d,tmp.d,tmp.d,np,n0,top);
976 : 6604 : bn_scatter5(tmp.d,top,powerbuf,2*i);
977 : : }
978 [ + + ]: 14859 : for (; i<32; i+=2)
979 : : {
980 : 13208 : bn_mul_mont_gather5(tmp.d,am.d,powerbuf,np2,n0,top,i-1);
981 : 13208 : bn_scatter5(tmp.d,top,powerbuf,i);
982 : : }
983 : : #endif
984 : 1651 : bits--;
985 [ + + ]: 5036 : for (wvalue=0, i=bits%5; i>=0; i--,bits--)
986 : 3385 : wvalue = (wvalue<<1)+BN_is_bit_set(p,bits);
987 : 1651 : bn_gather5(tmp.d,top,powerbuf,wvalue);
988 : :
989 : : /* Scan the exponent one window at a time starting from the most
990 : : * significant bits.
991 : : */
992 [ + + ]: 1651 : if (top&7)
993 [ + + ]: 1178 : while (bits >= 0)
994 : : {
995 [ + + ]: 6960 : for (wvalue=0, i=0; i<5; i++,bits--)
996 : 5800 : wvalue = (wvalue<<1)+BN_is_bit_set(p,bits);
997 : :
998 : 1160 : bn_mul_mont(tmp.d,tmp.d,tmp.d,np,n0,top);
999 : 1160 : bn_mul_mont(tmp.d,tmp.d,tmp.d,np,n0,top);
1000 : 1160 : bn_mul_mont(tmp.d,tmp.d,tmp.d,np,n0,top);
1001 : 1160 : bn_mul_mont(tmp.d,tmp.d,tmp.d,np,n0,top);
1002 : 1160 : bn_mul_mont(tmp.d,tmp.d,tmp.d,np,n0,top);
1003 : 1160 : bn_mul_mont_gather5(tmp.d,tmp.d,powerbuf,np,n0,top,wvalue);
1004 : : }
1005 : : else
1006 : : {
1007 [ + + ]: 247778 : while (bits >= 0)
1008 : : {
1009 : 246145 : wvalue = bn_get_bits5(p->d,bits-4);
1010 : 246145 : bits-=5;
1011 : 246145 : bn_power5(tmp.d,tmp.d,powerbuf,np2,n0,top,wvalue);
1012 : : }
1013 : : }
1014 : :
1015 : 1651 : ret=bn_from_montgomery(tmp.d,tmp.d,NULL,np2,n0,top);
1016 : 1651 : tmp.top=top;
1017 [ + - ][ + + ]: 1669 : bn_correct_top(&tmp);
[ + + ]
1018 [ + + ]: 1651 : if (ret)
1019 : : {
1020 [ - + ]: 1633 : if (!BN_copy(rr,&tmp)) ret=0;
1021 : : goto err; /* non-zero ret means it's not error */
1022 : : }
1023 : : }
1024 : : else
1025 : : #endif
1026 : : {
1027 [ + - ]: 453 : if (!MOD_EXP_CTIME_COPY_TO_PREBUF(&tmp, top, powerbuf, 0, numPowers)) goto err;
1028 [ + - ]: 453 : if (!MOD_EXP_CTIME_COPY_TO_PREBUF(&am, top, powerbuf, 1, numPowers)) goto err;
1029 : :
1030 : : /* If the window size is greater than 1, then calculate
1031 : : * val[i=2..2^winsize-1]. Powers are computed as a*a^(i-1)
1032 : : * (even powers could instead be computed as (a^(i/2))^2
1033 : : * to use the slight performance advantage of sqr over mul).
1034 : : */
1035 [ + + ]: 453 : if (window > 1)
1036 : : {
1037 [ + - ]: 448 : if (!BN_mod_mul_montgomery(&tmp,&am,&am,mont,ctx)) goto err;
1038 [ + - ]: 448 : if (!MOD_EXP_CTIME_COPY_TO_PREBUF(&tmp, top, powerbuf, 2, numPowers)) goto err;
1039 [ + + ]: 6256 : for (i=3; i<numPowers; i++)
1040 : : {
1041 : : /* Calculate a^i = a^(i-1) * a */
1042 [ + - ]: 5808 : if (!BN_mod_mul_montgomery(&tmp,&am,&tmp,mont,ctx))
1043 : : goto err;
1044 [ + - ]: 5808 : if (!MOD_EXP_CTIME_COPY_TO_PREBUF(&tmp, top, powerbuf, i, numPowers)) goto err;
1045 : : }
1046 : : }
1047 : :
1048 : 453 : bits--;
1049 [ + + ]: 1983 : for (wvalue=0, i=bits%window; i>=0; i--,bits--)
1050 : 1530 : wvalue = (wvalue<<1)+BN_is_bit_set(p,bits);
1051 [ + - ]: 453 : if (!MOD_EXP_CTIME_COPY_FROM_PREBUF(&tmp,top,powerbuf,wvalue,numPowers)) goto err;
1052 : :
1053 : : /* Scan the exponent one window at a time starting from the most
1054 : : * significant bits.
1055 : : */
1056 [ + + ]: 23810 : while (bits >= 0)
1057 : : {
1058 : : wvalue=0; /* The 'value' of the window */
1059 : :
1060 : : /* Scan the window, squaring the result as we go */
1061 [ + + ]: 116700 : for (i=0; i<window; i++,bits--)
1062 : : {
1063 [ + - ]: 93343 : if (!BN_mod_mul_montgomery(&tmp,&tmp,&tmp,mont,ctx)) goto err;
1064 : 93343 : wvalue = (wvalue<<1)+BN_is_bit_set(p,bits);
1065 : : }
1066 : :
1067 : : /* Fetch the appropriate pre-computed value from the pre-buf */
1068 [ + - ]: 23357 : if (!MOD_EXP_CTIME_COPY_FROM_PREBUF(&am, top, powerbuf, wvalue, numPowers)) goto err;
1069 : :
1070 : : /* Multiply the result into the intermediate result */
1071 [ + - ]: 23810 : if (!BN_mod_mul_montgomery(&tmp,&tmp,&am,mont,ctx)) goto err;
1072 : : }
1073 : : }
1074 : :
1075 : : /* Convert the final result from montgomery to standard format */
1076 : : #if defined(SPARC_T4_MONT)
1077 : : if (OPENSSL_sparcv9cap_P[0]&(SPARCV9_VIS3|SPARCV9_PREFER_FPU))
1078 : : {
1079 : : am.d[0] = 1; /* borrow am */
1080 : : for (i=1;i<top;i++) am.d[i] = 0;
1081 : : if (!BN_mod_mul_montgomery(rr,&tmp,&am,mont,ctx)) goto err;
1082 : : }
1083 : : else
1084 : : #endif
1085 [ + - ]: 471 : if (!BN_from_montgomery(rr,&tmp,mont,ctx)) goto err;
1086 : 471 : ret=1;
1087 : : err:
1088 [ + + ]: 4272 : if ((in_mont == NULL) && (mont != NULL)) BN_MONT_CTX_free(mont);
1089 [ + + ]: 4272 : if (powerbuf!=NULL)
1090 : : {
1091 : 2104 : OPENSSL_cleanse(powerbuf,powerbufLen);
1092 [ + + ]: 2104 : if (powerbufFree) OPENSSL_free(powerbufFree);
1093 : : }
1094 : 4272 : BN_CTX_end(ctx);
1095 : 4272 : return(ret);
1096 : : }
1097 : :
1098 : 145 : int BN_mod_exp_mont_word(BIGNUM *rr, BN_ULONG a, const BIGNUM *p,
1099 : : const BIGNUM *m, BN_CTX *ctx, BN_MONT_CTX *in_mont)
1100 : : {
1101 : 145 : BN_MONT_CTX *mont = NULL;
1102 : 145 : int b, bits, ret=0;
1103 : : int r_is_one;
1104 : : BN_ULONG w, next_w;
1105 : : BIGNUM *d, *r, *t;
1106 : : BIGNUM *swap_tmp;
1107 : : #define BN_MOD_MUL_WORD(r, w, m) \
1108 : : (BN_mul_word(r, (w)) && \
1109 : : (/* BN_ucmp(r, (m)) < 0 ? 1 :*/ \
1110 : : (BN_mod(t, r, m, ctx) && (swap_tmp = r, r = t, t = swap_tmp, 1))))
1111 : : /* BN_MOD_MUL_WORD is only used with 'w' large,
1112 : : * so the BN_ucmp test is probably more overhead
1113 : : * than always using BN_mod (which uses BN_copy if
1114 : : * a similar test returns true). */
1115 : : /* We can use BN_mod and do not need BN_nnmod because our
1116 : : * accumulator is never negative (the result of BN_mod does
1117 : : * not depend on the sign of the modulus).
1118 : : */
1119 : : #define BN_TO_MONTGOMERY_WORD(r, w, mont) \
1120 : : (BN_set_word(r, (w)) && BN_to_montgomery(r, r, (mont), ctx))
1121 : :
1122 [ - + ]: 145 : if (BN_get_flags(p, BN_FLG_CONSTTIME) != 0)
1123 : : {
1124 : : /* BN_FLG_CONSTTIME only supported by BN_mod_exp_mont() */
1125 : 0 : BNerr(BN_F_BN_MOD_EXP_MONT_WORD,ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
1126 : 0 : return -1;
1127 : : }
1128 : :
1129 : : bn_check_top(p);
1130 : : bn_check_top(m);
1131 : :
1132 [ + - ][ - + ]: 145 : if (!BN_is_odd(m))
1133 : : {
1134 : 0 : BNerr(BN_F_BN_MOD_EXP_MONT_WORD,BN_R_CALLED_WITH_EVEN_MODULUS);
1135 : 0 : return(0);
1136 : : }
1137 [ + + ]: 145 : if (m->top == 1)
1138 : 38 : a %= m->d[0]; /* make sure that 'a' is reduced */
1139 : :
1140 : 145 : bits = BN_num_bits(p);
1141 [ + + ]: 145 : if (bits == 0)
1142 : : {
1143 : : /* x**0 mod 1 is still zero. */
1144 [ + - ][ + + ]: 6 : if (BN_is_one(m))
[ + - ]
1145 : : {
1146 : 1 : ret = 1;
1147 : 1 : BN_zero(rr);
1148 : : }
1149 : : else
1150 : 5 : ret = BN_one(rr);
1151 : 6 : return ret;
1152 : : }
1153 [ - + ]: 139 : if (a == 0)
1154 : : {
1155 : 0 : BN_zero(rr);
1156 : 0 : ret = 1;
1157 : 0 : return ret;
1158 : : }
1159 : :
1160 : 139 : BN_CTX_start(ctx);
1161 : 139 : d = BN_CTX_get(ctx);
1162 : 139 : r = BN_CTX_get(ctx);
1163 : 139 : t = BN_CTX_get(ctx);
1164 [ + - ][ + - ]: 139 : if (d == NULL || r == NULL || t == NULL) goto err;
1165 : :
1166 [ + + ]: 139 : if (in_mont != NULL)
1167 : : mont=in_mont;
1168 : : else
1169 : : {
1170 [ + - ]: 137 : if ((mont = BN_MONT_CTX_new()) == NULL) goto err;
1171 [ + - ]: 137 : if (!BN_MONT_CTX_set(mont, m, ctx)) goto err;
1172 : : }
1173 : :
1174 : 139 : r_is_one = 1; /* except for Montgomery factor */
1175 : :
1176 : : /* bits-1 >= 0 */
1177 : :
1178 : : /* The result is accumulated in the product r*w. */
1179 : 139 : w = a; /* bit 'bits-1' of 'p' is always set */
1180 [ + + ]: 28370 : for (b = bits-2; b >= 0; b--)
1181 : : {
1182 : : /* First, square r*w. */
1183 : 28231 : next_w = w*w;
1184 [ + + ]: 28231 : if ((next_w/w) != w) /* overflow */
1185 : : {
1186 [ + + ]: 4029 : if (r_is_one)
1187 : : {
1188 [ + - ][ + - ]: 112 : if (!BN_TO_MONTGOMERY_WORD(r, w, mont)) goto err;
1189 : : r_is_one = 0;
1190 : : }
1191 : : else
1192 : : {
1193 [ + - ][ + - ]: 3917 : if (!BN_MOD_MUL_WORD(r, w, m)) goto err;
1194 : : }
1195 : : next_w = 1;
1196 : : }
1197 : 28231 : w = next_w;
1198 [ + + ]: 28231 : if (!r_is_one)
1199 : : {
1200 [ + - ]: 27672 : if (!BN_mod_mul_montgomery(r, r, r, mont, ctx)) goto err;
1201 : : }
1202 : :
1203 : : /* Second, multiply r*w by 'a' if exponent bit is set. */
1204 [ + + ]: 28231 : if (BN_is_bit_set(p, b))
1205 : : {
1206 : 14103 : next_w = w*a;
1207 [ + + ]: 14103 : if ((next_w/a) != w) /* overflow */
1208 : : {
1209 [ + + ]: 12 : if (r_is_one)
1210 : : {
1211 [ + - ][ + - ]: 1 : if (!BN_TO_MONTGOMERY_WORD(r, w, mont)) goto err;
1212 : : r_is_one = 0;
1213 : : }
1214 : : else
1215 : : {
1216 [ + - ][ + - ]: 11 : if (!BN_MOD_MUL_WORD(r, w, m)) goto err;
1217 : : }
1218 : 12 : next_w = a;
1219 : : }
1220 : 14103 : w = next_w;
1221 : : }
1222 : : }
1223 : :
1224 : : /* Finally, set r:=r*w. */
1225 [ + + ]: 139 : if (w != 1)
1226 : : {
1227 [ + + ]: 122 : if (r_is_one)
1228 : : {
1229 [ + - ][ + - ]: 24 : if (!BN_TO_MONTGOMERY_WORD(r, w, mont)) goto err;
1230 : : r_is_one = 0;
1231 : : }
1232 : : else
1233 : : {
1234 [ + - ][ + - ]: 98 : if (!BN_MOD_MUL_WORD(r, w, m)) goto err;
1235 : : }
1236 : : }
1237 : :
1238 [ + + ]: 139 : if (r_is_one) /* can happen only if a == 1*/
1239 : : {
1240 [ + - ]: 2 : if (!BN_one(rr)) goto err;
1241 : : }
1242 : : else
1243 : : {
1244 [ + - ]: 137 : if (!BN_from_montgomery(rr, r, mont, ctx)) goto err;
1245 : : }
1246 : : ret = 1;
1247 : : err:
1248 [ + + ]: 139 : if ((in_mont == NULL) && (mont != NULL)) BN_MONT_CTX_free(mont);
1249 : 139 : BN_CTX_end(ctx);
1250 : : bn_check_top(rr);
1251 : 139 : return(ret);
1252 : : }
1253 : :
1254 : :
1255 : : /* The old fallback, simple version :-) */
1256 : 202 : int BN_mod_exp_simple(BIGNUM *r, const BIGNUM *a, const BIGNUM *p,
1257 : : const BIGNUM *m, BN_CTX *ctx)
1258 : : {
1259 : 202 : int i,j,bits,ret=0,wstart,wend,window,wvalue;
1260 : 202 : int start=1;
1261 : : BIGNUM *d;
1262 : : /* Table of variables obtained from 'ctx' */
1263 : : BIGNUM *val[TABLE_SIZE];
1264 : :
1265 [ - + ]: 202 : if (BN_get_flags(p, BN_FLG_CONSTTIME) != 0)
1266 : : {
1267 : : /* BN_FLG_CONSTTIME only supported by BN_mod_exp_mont() */
1268 : 0 : BNerr(BN_F_BN_MOD_EXP_SIMPLE,ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
1269 : 0 : return -1;
1270 : : }
1271 : :
1272 : 202 : bits=BN_num_bits(p);
1273 : :
1274 [ - + ]: 202 : if (bits == 0)
1275 : : {
1276 : 0 : ret = BN_one(r);
1277 : 0 : return ret;
1278 : : }
1279 : :
1280 : 202 : BN_CTX_start(ctx);
1281 : 202 : d = BN_CTX_get(ctx);
1282 : 202 : val[0] = BN_CTX_get(ctx);
1283 [ + - ][ + - ]: 202 : if(!d || !val[0]) goto err;
1284 : :
1285 [ + - ]: 202 : if (!BN_nnmod(val[0],a,m,ctx)) goto err; /* 1 */
1286 [ - + ]: 202 : if (BN_is_zero(val[0]))
1287 : : {
1288 : 0 : BN_zero(r);
1289 : 0 : ret = 1;
1290 : 0 : goto err;
1291 : : }
1292 : :
1293 [ + + ][ - + ]: 202 : window = BN_window_bits_for_exponent_size(bits);
[ # # ][ # # ]
1294 [ + - ]: 202 : if (window > 1)
1295 : : {
1296 [ + - ]: 202 : if (!BN_mod_mul(d,val[0],val[0],m,ctx))
1297 : : goto err; /* 2 */
1298 : 202 : j=1<<(window-1);
1299 [ + + ]: 3264 : for (i=1; i<j; i++)
1300 : : {
1301 [ + - + - ]: 6124 : if(((val[i] = BN_CTX_get(ctx)) == NULL) ||
1302 : 3062 : !BN_mod_mul(val[i],val[i-1],d,m,ctx))
1303 : : goto err;
1304 : : }
1305 : : }
1306 : :
1307 : 202 : start=1; /* This is used to avoid multiplication etc
1308 : : * when there is only the value '1' in the
1309 : : * buffer. */
1310 : 202 : wvalue=0; /* The 'value' of the window */
1311 : 202 : wstart=bits-1; /* The top bit of the window */
1312 : 202 : wend=0; /* The bottom bit of the window */
1313 : :
1314 [ + - ]: 32787 : if (!BN_one(r)) goto err;
1315 : :
1316 : : for (;;)
1317 : : {
1318 [ + + ]: 32787 : if (BN_is_bit_set(p,wstart) == 0)
1319 : : {
1320 [ + - ]: 21864 : if (!start)
1321 [ + - ]: 21864 : if (!BN_mod_mul(r,r,r,m,ctx))
1322 : : goto err;
1323 [ + + ]: 21864 : if (wstart == 0) break;
1324 : 21770 : wstart--;
1325 : 21770 : continue;
1326 : : }
1327 : : /* We now have wstart on a 'set' bit, we now need to work out
1328 : : * how bit a window to do. To do this we need to scan
1329 : : * forward until the last set bit before the end of the
1330 : : * window */
1331 : : j=wstart;
1332 : : wvalue=1;
1333 : : wend=0;
1334 [ + + ]: 54496 : for (i=1; i<window; i++)
1335 : : {
1336 [ + + ]: 43698 : if (wstart-i < 0) break;
1337 [ + + ]: 43573 : if (BN_is_bit_set(p,wstart-i))
1338 : : {
1339 : 22023 : wvalue<<=(i-wend);
1340 : 22023 : wvalue|=1;
1341 : 22023 : wend=i;
1342 : : }
1343 : : }
1344 : :
1345 : : /* wend is the size of the current window */
1346 : 10923 : j=wend+1;
1347 : : /* add the 'bytes above' */
1348 [ + + ]: 10923 : if (!start)
1349 [ + + ]: 54101 : for (i=0; i<j; i++)
1350 : : {
1351 [ + - ]: 43380 : if (!BN_mod_mul(r,r,r,m,ctx))
1352 : : goto err;
1353 : : }
1354 : :
1355 : : /* wvalue will be an odd number < 2^window */
1356 [ + - ]: 10923 : if (!BN_mod_mul(r,r,val[wvalue>>1],m,ctx))
1357 : : goto err;
1358 : :
1359 : : /* move the 'window' down further */
1360 : 10923 : wstart-=wend+1;
1361 : 10923 : wvalue=0;
1362 : 10923 : start=0;
1363 [ + + ]: 10923 : if (wstart < 0) break;
1364 : : }
1365 : : ret=1;
1366 : : err:
1367 : 202 : BN_CTX_end(ctx);
1368 : : bn_check_top(r);
1369 : 202 : return(ret);
1370 : : }
|
