Debian Codegraph @

external/boringssl/crypto/bn/exponentiation.c

raw
1 /* Copyright (C) 1995-1998 Eric Young ([email protected])
2 * All rights reserved.
3 *
4 * This package is an SSL implementation written
5 * by Eric Young ([email protected]).
6 * The implementation was written so as to conform with Netscapes SSL.
7 *
8 * This library is free for commercial and non-commercial use as long as
9 * the following conditions are aheared to. The following conditions
10 * apply to all code found in this distribution, be it the RC4, RSA,
11 * lhash, DES, etc., code; not just the SSL code. The SSL documentation
12 * included with this distribution is covered by the same copyright terms
13 * except that the holder is Tim Hudson ([email protected]).
14 *
15 * Copyright remains Eric Young's, and as such any Copyright notices in
16 * the code are not to be removed.
17 * If this package is used in a product, Eric Young should be given attribution
18 * as the author of the parts of the library used.
19 * This can be in the form of a textual message at program startup or
20 * in documentation (online or textual) provided with the package.
21 *
22 * Redistribution and use in source and binary forms, with or without
23 * modification, are permitted provided that the following conditions
24 * are met:
25 * 1. Redistributions of source code must retain the copyright
26 * notice, this list of conditions and the following disclaimer.
27 * 2. Redistributions in binary form must reproduce the above copyright
28 * notice, this list of conditions and the following disclaimer in the
29 * documentation and/or other materials provided with the distribution.
30 * 3. All advertising materials mentioning features or use of this software
31 * must display the following acknowledgement:
32 * "This product includes cryptographic software written by
33 * Eric Young ([email protected])"
34 * The word 'cryptographic' can be left out if the rouines from the library
35 * being used are not cryptographic related :-).
36 * 4. If you include any Windows specific code (or a derivative thereof) from
37 * the apps directory (application code) you must include an acknowledgement:
38 * "This product includes software written by Tim Hudson ([email protected])"
39 *
40 * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND
41 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
42 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
43 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
44 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
45 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
46 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
47 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
48 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
49 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
50 * SUCH DAMAGE.
51 *
52 * The licence and distribution terms for any publically available version or
53 * derivative of this code cannot be changed. i.e. this code cannot simply be
54 * copied and put under another distribution licence
55 * [including the GNU Public Licence.]
56 */
57 /* ====================================================================
58 * Copyright (c) 1998-2005 The OpenSSL Project. All rights reserved.
59 *
60 * Redistribution and use in source and binary forms, with or without
61 * modification, are permitted provided that the following conditions
62 * are met:
63 *
64 * 1. Redistributions of source code must retain the above copyright
65 * notice, this list of conditions and the following disclaimer.
66 *
67 * 2. Redistributions in binary form must reproduce the above copyright
68 * notice, this list of conditions and the following disclaimer in
69 * the documentation and/or other materials provided with the
70 * distribution.
71 *
72 * 3. All advertising materials mentioning features or use of this
73 * software must display the following acknowledgment:
74 * "This product includes software developed by the OpenSSL Project
75 * for use in the OpenSSL Toolkit. (http://www.openssl.org/)"
76 *
77 * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to
78 * endorse or promote products derived from this software without
79 * prior written permission. For written permission, please contact
80 * [email protected].
81 *
82 * 5. Products derived from this software may not be called "OpenSSL"
83 * nor may "OpenSSL" appear in their names without prior written
84 * permission of the OpenSSL Project.
85 *
86 * 6. Redistributions of any form whatsoever must retain the following
87 * acknowledgment:
88 * "This product includes software developed by the OpenSSL Project
89 * for use in the OpenSSL Toolkit (http://www.openssl.org/)"
90 *
91 * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY
92 * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
93 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
94 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR
95 * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
96 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
97 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
98 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
99 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
100 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
101 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
102 * OF THE POSSIBILITY OF SUCH DAMAGE.
103 * ====================================================================
104 *
105 * This product includes cryptographic software written by Eric Young
106 * ([email protected]). This product includes software written by Tim
107 * Hudson ([email protected]). */
108
109 #include <openssl/bn.h>
110
111 #include <assert.h>
112 #include <string.h>
113
114 #include <openssl/cpu.h>
115 #include <openssl/err.h>
116 #include <openssl/mem.h>
117
118 #include "internal.h"
119
120
121 #if !defined(OPENSSL_NO_ASM) && defined(OPENSSL_X86_64)
122 #define OPENSSL_BN_ASM_MONT5
123 #define RSAZ_ENABLED
124
125 #include "rsaz_exp.h"
126
127 void bn_mul_mont_gather5(BN_ULONG *rp, const BN_ULONG *ap, const void *table,
128 const BN_ULONG *np, const BN_ULONG *n0, int num,
129 int power);
130 void bn_scatter5(const BN_ULONG *inp, size_t num, void *table, size_t power);
131 void bn_gather5(BN_ULONG *out, size_t num, void *table, size_t power);
132 void bn_power5(BN_ULONG *rp, const BN_ULONG *ap, const void *table,
133 const BN_ULONG *np, const BN_ULONG *n0, int num, int power);
134 int bn_from_montgomery(BN_ULONG *rp, const BN_ULONG *ap,
135 const BN_ULONG *not_used, const BN_ULONG *np,
136 const BN_ULONG *n0, int num);
137 #endif
138
139 int BN_exp(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx) {
140 int i, bits, ret = 0;
141 BIGNUM *v, *rr;
142
143 if ((p->flags & BN_FLG_CONSTTIME) != 0) {
144 /* BN_FLG_CONSTTIME only supported by BN_mod_exp_mont() */
145 OPENSSL_PUT_ERROR(BN, ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
146 return 0;
147 }
148
149 BN_CTX_start(ctx);
150 if (r == a || r == p) {
151 rr = BN_CTX_get(ctx);
152 } else {
153 rr = r;
154 }
155
156 v = BN_CTX_get(ctx);
157 if (rr == NULL || v == NULL) {
158 goto err;
159 }
160
161 if (BN_copy(v, a) == NULL) {
162 goto err;
163 }
164 bits = BN_num_bits(p);
165
166 if (BN_is_odd(p)) {
167 if (BN_copy(rr, a) == NULL) {
168 goto err;
169 }
170 } else {
171 if (!BN_one(rr)) {
172 goto err;
173 }
174 }
175
176 for (i = 1; i < bits; i++) {
177 if (!BN_sqr(v, v, ctx)) {
178 goto err;
179 }
180 if (BN_is_bit_set(p, i)) {
181 if (!BN_mul(rr, rr, v, ctx)) {
182 goto err;
183 }
184 }
185 }
186
187 if (r != rr && !BN_copy(r, rr)) {
188 goto err;
189 }
190 ret = 1;
191
192 err:
193 BN_CTX_end(ctx);
194 return ret;
195 }
196
197 /* maximum precomputation table size for *variable* sliding windows */
198 #define TABLE_SIZE 32
199
200 typedef struct bn_recp_ctx_st {
201 BIGNUM N; /* the divisor */
202 BIGNUM Nr; /* the reciprocal */
203 int num_bits;
204 int shift;
205 int flags;
206 } BN_RECP_CTX;
207
208 static void BN_RECP_CTX_init(BN_RECP_CTX *recp) {
209 BN_init(&recp->N);
210 BN_init(&recp->Nr);
211 recp->num_bits = 0;
212 recp->shift = 0;
213 recp->flags = 0;
214 }
215
216 static void BN_RECP_CTX_free(BN_RECP_CTX *recp) {
217 if (recp == NULL) {
218 return;
219 }
220
221 BN_free(&recp->N);
222 BN_free(&recp->Nr);
223 }
224
225 static int BN_RECP_CTX_set(BN_RECP_CTX *recp, const BIGNUM *d, BN_CTX *ctx) {
226 if (!BN_copy(&(recp->N), d)) {
227 return 0;
228 }
229 BN_zero(&recp->Nr);
230 recp->num_bits = BN_num_bits(d);
231 recp->shift = 0;
232
233 return 1;
234 }
235
236 /* len is the expected size of the result We actually calculate with an extra
237 * word of precision, so we can do faster division if the remainder is not
238 * required.
239 * r := 2^len / m */
240 static int BN_reciprocal(BIGNUM *r, const BIGNUM *m, int len, BN_CTX *ctx) {
241 int ret = -1;
242 BIGNUM *t;
243
244 BN_CTX_start(ctx);
245 t = BN_CTX_get(ctx);
246 if (t == NULL) {
247 goto err;
248 }
249
250 if (!BN_set_bit(t, len)) {
251 goto err;
252 }
253
254 if (!BN_div(r, NULL, t, m, ctx)) {
255 goto err;
256 }
257
258 ret = len;
259
260 err:
261 BN_CTX_end(ctx);
262 return ret;
263 }
264
265 static int BN_div_recp(BIGNUM *dv, BIGNUM *rem, const BIGNUM *m,
266 BN_RECP_CTX *recp, BN_CTX *ctx) {
267 int i, j, ret = 0;
268 BIGNUM *a, *b, *d, *r;
269
270 BN_CTX_start(ctx);
271 a = BN_CTX_get(ctx);
272 b = BN_CTX_get(ctx);
273 if (dv != NULL) {
274 d = dv;
275 } else {
276 d = BN_CTX_get(ctx);
277 }
278
279 if (rem != NULL) {
280 r = rem;
281 } else {
282 r = BN_CTX_get(ctx);
283 }
284
285 if (a == NULL || b == NULL || d == NULL || r == NULL) {
286 goto err;
287 }
288
289 if (BN_ucmp(m, &recp->N) < 0) {
290 BN_zero(d);
291 if (!BN_copy(r, m)) {
292 goto err;
293 }
294 BN_CTX_end(ctx);
295 return 1;
296 }
297
298 /* We want the remainder
299 * Given input of ABCDEF / ab
300 * we need multiply ABCDEF by 3 digests of the reciprocal of ab */
301
302 /* i := max(BN_num_bits(m), 2*BN_num_bits(N)) */
303 i = BN_num_bits(m);
304 j = recp->num_bits << 1;
305 if (j > i) {
306 i = j;
307 }
308
309 /* Nr := round(2^i / N) */
310 if (i != recp->shift) {
311 recp->shift =
312 BN_reciprocal(&(recp->Nr), &(recp->N), i,
313 ctx); /* BN_reciprocal returns i, or -1 for an error */
314 }
315
316 if (recp->shift == -1) {
317 goto err;
318 }
319
320 /* d := |round(round(m / 2^BN_num_bits(N)) * recp->Nr / 2^(i -
321 * BN_num_bits(N)))|
322 * = |round(round(m / 2^BN_num_bits(N)) * round(2^i / N) / 2^(i -
323 * BN_num_bits(N)))|
324 * <= |(m / 2^BN_num_bits(N)) * (2^i / N) * (2^BN_num_bits(N) / 2^i)|
325 * = |m/N| */
326 if (!BN_rshift(a, m, recp->num_bits)) {
327 goto err;
328 }
329 if (!BN_mul(b, a, &(recp->Nr), ctx)) {
330 goto err;
331 }
332 if (!BN_rshift(d, b, i - recp->num_bits)) {
333 goto err;
334 }
335 d->neg = 0;
336
337 if (!BN_mul(b, &(recp->N), d, ctx)) {
338 goto err;
339 }
340 if (!BN_usub(r, m, b)) {
341 goto err;
342 }
343 r->neg = 0;
344
345 j = 0;
346 while (BN_ucmp(r, &(recp->N)) >= 0) {
347 if (j++ > 2) {
348 OPENSSL_PUT_ERROR(BN, BN_R_BAD_RECIPROCAL);
349 goto err;
350 }
351 if (!BN_usub(r, r, &(recp->N))) {
352 goto err;
353 }
354 if (!BN_add_word(d, 1)) {
355 goto err;
356 }
357 }
358
359 r->neg = BN_is_zero(r) ? 0 : m->neg;
360 d->neg = m->neg ^ recp->N.neg;
361 ret = 1;
362
363 err:
364 BN_CTX_end(ctx);
365 return ret;
366 }
367
368 static int BN_mod_mul_reciprocal(BIGNUM *r, const BIGNUM *x, const BIGNUM *y,
369 BN_RECP_CTX *recp, BN_CTX *ctx) {
370 int ret = 0;
371 BIGNUM *a;
372 const BIGNUM *ca;
373
374 BN_CTX_start(ctx);
375 a = BN_CTX_get(ctx);
376 if (a == NULL) {
377 goto err;
378 }
379
380 if (y != NULL) {
381 if (x == y) {
382 if (!BN_sqr(a, x, ctx)) {
383 goto err;
384 }
385 } else {
386 if (!BN_mul(a, x, y, ctx)) {
387 goto err;
388 }
389 }
390 ca = a;
391 } else {
392 ca = x; /* Just do the mod */
393 }
394
395 ret = BN_div_recp(NULL, r, ca, recp, ctx);
396
397 err:
398 BN_CTX_end(ctx);
399 return ret;
400 }
401
402 /* BN_window_bits_for_exponent_size -- macro for sliding window mod_exp
403 * functions
404 *
405 * For window size 'w' (w >= 2) and a random 'b' bits exponent, the number of
406 * multiplications is a constant plus on average
407 *
408 * 2^(w-1) + (b-w)/(w+1);
409 *
410 * here 2^(w-1) is for precomputing the table (we actually need entries only
411 * for windows that have the lowest bit set), and (b-w)/(w+1) is an
412 * approximation for the expected number of w-bit windows, not counting the
413 * first one.
414 *
415 * Thus we should use
416 *
417 * w >= 6 if b > 671
418 * w = 5 if 671 > b > 239
419 * w = 4 if 239 > b > 79
420 * w = 3 if 79 > b > 23
421 * w <= 2 if 23 > b
422 *
423 * (with draws in between). Very small exponents are often selected
424 * with low Hamming weight, so we use w = 1 for b <= 23. */
425 #define BN_window_bits_for_exponent_size(b) \
426 ((b) > 671 ? 6 : \
427 (b) > 239 ? 5 : \
428 (b) > 79 ? 4 : \
429 (b) > 23 ? 3 : 1)
430
431 static int mod_exp_recp(BIGNUM *r, const BIGNUM *a, const BIGNUM *p,
432 const BIGNUM *m, BN_CTX *ctx) {
433 int i, j, bits, ret = 0, wstart, window;
434 int start = 1;
435 BIGNUM *aa;
436 /* Table of variables obtained from 'ctx' */
437 BIGNUM *val[TABLE_SIZE];
438 BN_RECP_CTX recp;
439
440 if (BN_get_flags(p, BN_FLG_CONSTTIME) != 0) {
441 /* BN_FLG_CONSTTIME only supported by BN_mod_exp_mont() */
442 OPENSSL_PUT_ERROR(BN, ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
443 return 0;
444 }
445
446 bits = BN_num_bits(p);
447
448 if (bits == 0) {
449 /* x**0 mod 1 is still zero. */
450 if (BN_is_one(m)) {
451 BN_zero(r);
452 return 1;
453 }
454 return BN_one(r);
455 }
456
457 BN_CTX_start(ctx);
458 aa = BN_CTX_get(ctx);
459 val[0] = BN_CTX_get(ctx);
460 if (!aa || !val[0]) {
461 goto err;
462 }
463
464 BN_RECP_CTX_init(&recp);
465 if (m->neg) {
466 /* ignore sign of 'm' */
467 if (!BN_copy(aa, m)) {
468 goto err;
469 }
470 aa->neg = 0;
471 if (BN_RECP_CTX_set(&recp, aa, ctx) <= 0) {
472 goto err;
473 }
474 } else {
475 if (BN_RECP_CTX_set(&recp, m, ctx) <= 0) {
476 goto err;
477 }
478 }
479
480 if (!BN_nnmod(val[0], a, m, ctx)) {
481 goto err; /* 1 */
482 }
483 if (BN_is_zero(val[0])) {
484 BN_zero(r);
485 ret = 1;
486 goto err;
487 }
488
489 window = BN_window_bits_for_exponent_size(bits);
490 if (window > 1) {
491 if (!BN_mod_mul_reciprocal(aa, val[0], val[0], &recp, ctx)) {
492 goto err; /* 2 */
493 }
494 j = 1 << (window - 1);
495 for (i = 1; i < j; i++) {
496 if (((val[i] = BN_CTX_get(ctx)) == NULL) ||
497 !BN_mod_mul_reciprocal(val[i], val[i - 1], aa, &recp, ctx)) {
498 goto err;
499 }
500 }
501 }
502
503 start = 1; /* This is used to avoid multiplication etc
504 * when there is only the value '1' in the
505 * buffer. */
506 wstart = bits - 1; /* The top bit of the window */
507
508 if (!BN_one(r)) {
509 goto err;
510 }
511
512 for (;;) {
513 int wvalue; /* The 'value' of the window */
514 int wend; /* The bottom bit of the window */
515
516 if (BN_is_bit_set(p, wstart) == 0) {
517 if (!start) {
518 if (!BN_mod_mul_reciprocal(r, r, r, &recp, ctx)) {
519 goto err;
520 }
521 }
522 if (wstart == 0) {
523 break;
524 }
525 wstart--;
526 continue;
527 }
528
529 /* We now have wstart on a 'set' bit, we now need to work out
530 * how bit a window to do. To do this we need to scan
531 * forward until the last set bit before the end of the
532 * window */
533 wvalue = 1;
534 wend = 0;
535 for (i = 1; i < window; i++) {
536 if (wstart - i < 0) {
537 break;
538 }
539 if (BN_is_bit_set(p, wstart - i)) {
540 wvalue <<= (i - wend);
541 wvalue |= 1;
542 wend = i;
543 }
544 }
545
546 /* wend is the size of the current window */
547 j = wend + 1;
548 /* add the 'bytes above' */
549 if (!start) {
550 for (i = 0; i < j; i++) {
551 if (!BN_mod_mul_reciprocal(r, r, r, &recp, ctx)) {
552 goto err;
553 }
554 }
555 }
556
557 /* wvalue will be an odd number < 2^window */
558 if (!BN_mod_mul_reciprocal(r, r, val[wvalue >> 1], &recp, ctx)) {
559 goto err;
560 }
561
562 /* move the 'window' down further */
563 wstart -= wend + 1;
564 start = 0;
565 if (wstart < 0) {
566 break;
567 }
568 }
569 ret = 1;
570
571 err:
572 BN_CTX_end(ctx);
573 BN_RECP_CTX_free(&recp);
574 return ret;
575 }
576
577 int BN_mod_exp(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, const BIGNUM *m,
578 BN_CTX *ctx) {
579 if (BN_is_odd(m)) {
580 return BN_mod_exp_mont(r, a, p, m, ctx, NULL);
581 }
582
583 return mod_exp_recp(r, a, p, m, ctx);
584 }
585
586 int BN_mod_exp_mont(BIGNUM *rr, const BIGNUM *a, const BIGNUM *p,
587 const BIGNUM *m, BN_CTX *ctx, const BN_MONT_CTX *mont) {
588 int i, j, bits, ret = 0, wstart, window;
589 int start = 1;
590 BIGNUM *d, *r;
591 const BIGNUM *aa;
592 /* Table of variables obtained from 'ctx' */
593 BIGNUM *val[TABLE_SIZE];
594 BN_MONT_CTX *new_mont = NULL;
595
596 if (BN_get_flags(p, BN_FLG_CONSTTIME) != 0) {
597 return BN_mod_exp_mont_consttime(rr, a, p, m, ctx, mont);
598 }
599
600 if (!BN_is_odd(m)) {
601 OPENSSL_PUT_ERROR(BN, BN_R_CALLED_WITH_EVEN_MODULUS);
602 return 0;
603 }
604 bits = BN_num_bits(p);
605 if (bits == 0) {
606 /* x**0 mod 1 is still zero. */
607 if (BN_is_one(m)) {
608 BN_zero(rr);
609 return 1;
610 }
611 return BN_one(rr);
612 }
613
614 BN_CTX_start(ctx);
615 d = BN_CTX_get(ctx);
616 r = BN_CTX_get(ctx);
617 val[0] = BN_CTX_get(ctx);
618 if (!d || !r || !val[0]) {
619 goto err;
620 }
621
622 /* Allocate a montgomery context if it was not supplied by the caller. */
623 if (mont == NULL) {
624 new_mont = BN_MONT_CTX_new();
625 if (new_mont == NULL || !BN_MONT_CTX_set(new_mont, m, ctx)) {
626 goto err;
627 }
628 mont = new_mont;
629 }
630
631 if (a->neg || BN_ucmp(a, m) >= 0) {
632 if (!BN_nnmod(val[0], a, m, ctx)) {
633 goto err;
634 }
635 aa = val[0];
636 } else {
637 aa = a;
638 }
639
640 if (BN_is_zero(aa)) {
641 BN_zero(rr);
642 ret = 1;
643 goto err;
644 }
645 if (!BN_to_montgomery(val[0], aa, mont, ctx)) {
646 goto err; /* 1 */
647 }
648
649 window = BN_window_bits_for_exponent_size(bits);
650 if (window > 1) {
651 if (!BN_mod_mul_montgomery(d, val[0], val[0], mont, ctx)) {
652 goto err; /* 2 */
653 }
654 j = 1 << (window - 1);
655 for (i = 1; i < j; i++) {
656 if (((val[i] = BN_CTX_get(ctx)) == NULL) ||
657 !BN_mod_mul_montgomery(val[i], val[i - 1], d, mont, ctx)) {
658 goto err;
659 }
660 }
661 }
662
663 start = 1; /* This is used to avoid multiplication etc
664 * when there is only the value '1' in the
665 * buffer. */
666 wstart = bits - 1; /* The top bit of the window */
667
668 j = m->top; /* borrow j */
669 if (m->d[j - 1] & (((BN_ULONG)1) << (BN_BITS2 - 1))) {
670 if (bn_wexpand(r, j) == NULL) {
671 goto err;
672 }
673 /* 2^(top*BN_BITS2) - m */
674 r->d[0] = (0 - m->d[0]) & BN_MASK2;
675 for (i = 1; i < j; i++) {
676 r->d[i] = (~m->d[i]) & BN_MASK2;
677 }
678 r->top = j;
679 /* Upper words will be zero if the corresponding words of 'm'
680 * were 0xfff[...], so decrement r->top accordingly. */
681 bn_correct_top(r);
682 } else if (!BN_to_montgomery(r, BN_value_one(), mont, ctx)) {
683 goto err;
684 }
685
686 for (;;) {
687 int wvalue; /* The 'value' of the window */
688 int wend; /* The bottom bit of the window */
689
690 if (BN_is_bit_set(p, wstart) == 0) {
691 if (!start && !BN_mod_mul_montgomery(r, r, r, mont, ctx)) {
692 goto err;
693 }
694 if (wstart == 0) {
695 break;
696 }
697 wstart--;
698 continue;
699 }
700
701 /* We now have wstart on a 'set' bit, we now need to work out how bit a
702 * window to do. To do this we need to scan forward until the last set bit
703 * before the end of the window */
704 wvalue = 1;
705 wend = 0;
706 for (i = 1; i < window; i++) {
707 if (wstart - i < 0) {
708 break;
709 }
710 if (BN_is_bit_set(p, wstart - i)) {
711 wvalue <<= (i - wend);
712 wvalue |= 1;
713 wend = i;
714 }
715 }
716
717 /* wend is the size of the current window */
718 j = wend + 1;
719 /* add the 'bytes above' */
720 if (!start) {
721 for (i = 0; i < j; i++) {
722 if (!BN_mod_mul_montgomery(r, r, r, mont, ctx)) {
723 goto err;
724 }
725 }
726 }
727
728 /* wvalue will be an odd number < 2^window */
729 if (!BN_mod_mul_montgomery(r, r, val[wvalue >> 1], mont, ctx)) {
730 goto err;
731 }
732
733 /* move the 'window' down further */
734 wstart -= wend + 1;
735 start = 0;
736 if (wstart < 0) {
737 break;
738 }
739 }
740
741 if (!BN_from_montgomery(rr, r, mont, ctx)) {
742 goto err;
743 }
744 ret = 1;
745
746 err:
747 BN_MONT_CTX_free(new_mont);
748 BN_CTX_end(ctx);
749 return ret;
750 }
751
752 /* BN_mod_exp_mont_consttime() stores the precomputed powers in a specific
753 * layout so that accessing any of these table values shows the same access
754 * pattern as far as cache lines are concerned. The following functions are
755 * used to transfer a BIGNUM from/to that table. */
756 static int copy_to_prebuf(const BIGNUM *b, int top, unsigned char *buf, int idx,
757 int window) {
758 int i, j;
759 const int width = 1 << window;
760 BN_ULONG *table = (BN_ULONG *) buf;
761
762 if (top > b->top) {
763 top = b->top; /* this works because 'buf' is explicitly zeroed */
764 }
765
766 for (i = 0, j = idx; i < top; i++, j += width) {
767 table[j] = b->d[i];
768 }
769
770 return 1;
771 }
772
773 static int copy_from_prebuf(BIGNUM *b, int top, unsigned char *buf, int idx,
774 int window) {
775 int i, j;
776 const int width = 1 << window;
777 volatile BN_ULONG *table = (volatile BN_ULONG *)buf;
778
779 if (bn_wexpand(b, top) == NULL) {
780 return 0;
781 }
782
783 if (window <= 3) {
784 for (i = 0; i < top; i++, table += width) {
785 BN_ULONG acc = 0;
786
787 for (j = 0; j < width; j++) {
788 acc |= table[j] & ((BN_ULONG)0 - (constant_time_eq_int(j, idx) & 1));
789 }
790
791 b->d[i] = acc;
792 }
793 } else {
794 int xstride = 1 << (window - 2);
795 BN_ULONG y0, y1, y2, y3;
796
797 i = idx >> (window - 2); /* equivalent of idx / xstride */
798 idx &= xstride - 1; /* equivalent of idx % xstride */
799
800 y0 = (BN_ULONG)0 - (constant_time_eq_int(i, 0) & 1);
801 y1 = (BN_ULONG)0 - (constant_time_eq_int(i, 1) & 1);
802 y2 = (BN_ULONG)0 - (constant_time_eq_int(i, 2) & 1);
803 y3 = (BN_ULONG)0 - (constant_time_eq_int(i, 3) & 1);
804
805 for (i = 0; i < top; i++, table += width) {
806 BN_ULONG acc = 0;
807
808 for (j = 0; j < xstride; j++) {
809 acc |= ((table[j + 0 * xstride] & y0) | (table[j + 1 * xstride] & y1) |
810 (table[j + 2 * xstride] & y2) | (table[j + 3 * xstride] & y3)) &
811 ((BN_ULONG)0 - (constant_time_eq_int(j, idx) & 1));
812 }
813
814 b->d[i] = acc;
815 }
816 }
817
818 b->top = top;
819 bn_correct_top(b);
820 return 1;
821 }
822
823 /* BN_mod_exp_mont_conttime is based on the assumption that the L1 data cache
824 * line width of the target processor is at least the following value. */
825 #define MOD_EXP_CTIME_MIN_CACHE_LINE_WIDTH (64)
826 #define MOD_EXP_CTIME_MIN_CACHE_LINE_MASK \
827 (MOD_EXP_CTIME_MIN_CACHE_LINE_WIDTH - 1)
828
829 /* Window sizes optimized for fixed window size modular exponentiation
830 * algorithm (BN_mod_exp_mont_consttime).
831 *
832 * To achieve the security goals of BN_mode_exp_mont_consttime, the maximum
833 * size of the window must not exceed
834 * log_2(MOD_EXP_CTIME_MIN_CACHE_LINE_WIDTH).
835 *
836 * Window size thresholds are defined for cache line sizes of 32 and 64, cache
837 * line sizes where log_2(32)=5 and log_2(64)=6 respectively. A window size of
838 * 7 should only be used on processors that have a 128 byte or greater cache
839 * line size. */
840 #if MOD_EXP_CTIME_MIN_CACHE_LINE_WIDTH == 64
841
842 #define BN_window_bits_for_ctime_exponent_size(b) \
843 ((b) > 937 ? 6 : (b) > 306 ? 5 : (b) > 89 ? 4 : (b) > 22 ? 3 : 1)
844 #define BN_MAX_WINDOW_BITS_FOR_CTIME_EXPONENT_SIZE (6)
845
846 #elif MOD_EXP_CTIME_MIN_CACHE_LINE_WIDTH == 32
847
848 #define BN_window_bits_for_ctime_exponent_size(b) \
849 ((b) > 306 ? 5 : (b) > 89 ? 4 : (b) > 22 ? 3 : 1)
850 #define BN_MAX_WINDOW_BITS_FOR_CTIME_EXPONENT_SIZE (5)
851
852 #endif
853
854 /* Given a pointer value, compute the next address that is a cache line
855 * multiple. */
856 #define MOD_EXP_CTIME_ALIGN(x_) \
857 ((unsigned char *)(x_) + \
858 (MOD_EXP_CTIME_MIN_CACHE_LINE_WIDTH - \
859 (((size_t)(x_)) & (MOD_EXP_CTIME_MIN_CACHE_LINE_MASK))))
860
861 /* This variant of BN_mod_exp_mont() uses fixed windows and the special
862 * precomputation memory layout to limit data-dependency to a minimum
863 * to protect secret exponents (cf. the hyper-threading timing attacks
864 * pointed out by Colin Percival,
865 * http://www.daemonology.net/hyperthreading-considered-harmful/)
866 */
867 int BN_mod_exp_mont_consttime(BIGNUM *rr, const BIGNUM *a, const BIGNUM *p,
868 const BIGNUM *m, BN_CTX *ctx,
869 const BN_MONT_CTX *mont) {
870 int i, bits, ret = 0, window, wvalue;
871 int top;
872 BN_MONT_CTX *new_mont = NULL;
873
874 int numPowers;
875 unsigned char *powerbufFree = NULL;
876 int powerbufLen = 0;
877 unsigned char *powerbuf = NULL;
878 BIGNUM tmp, am;
879
880 if (!BN_is_odd(m)) {
881 OPENSSL_PUT_ERROR(BN, BN_R_CALLED_WITH_EVEN_MODULUS);
882 return 0;
883 }
884
885 top = m->top;
886
887 bits = BN_num_bits(p);
888 if (bits == 0) {
889 /* x**0 mod 1 is still zero. */
890 if (BN_is_one(m)) {
891 BN_zero(rr);
892 return 1;
893 }
894 return BN_one(rr);
895 }
896
897 /* Allocate a montgomery context if it was not supplied by the caller. */
898 if (mont == NULL) {
899 new_mont = BN_MONT_CTX_new();
900 if (new_mont == NULL || !BN_MONT_CTX_set(new_mont, m, ctx)) {
901 goto err;
902 }
903 mont = new_mont;
904 }
905
906 #ifdef RSAZ_ENABLED
907 /* If the size of the operands allow it, perform the optimized
908 * RSAZ exponentiation. For further information see
909 * crypto/bn/rsaz_exp.c and accompanying assembly modules. */
910 if ((16 == a->top) && (16 == p->top) && (BN_num_bits(m) == 1024) &&
911 rsaz_avx2_eligible()) {
912 if (NULL == bn_wexpand(rr, 16)) {
913 goto err;
914 }
915 RSAZ_1024_mod_exp_avx2(rr->d, a->d, p->d, m->d, mont->RR.d, mont->n0[0]);
916 rr->top = 16;
917 rr->neg = 0;
918 bn_correct_top(rr);
919 ret = 1;
920 goto err;
921 } else if ((8 == a->top) && (8 == p->top) && (BN_num_bits(m) == 512)) {
922 if (NULL == bn_wexpand(rr, 8)) {
923 goto err;
924 }
925 RSAZ_512_mod_exp(rr->d, a->d, p->d, m->d, mont->n0[0], mont->RR.d);
926 rr->top = 8;
927 rr->neg = 0;
928 bn_correct_top(rr);
929 ret = 1;
930 goto err;
931 }
932 #endif
933
934 /* Get the window size to use with size of p. */
935 window = BN_window_bits_for_ctime_exponent_size(bits);
936 #if defined(OPENSSL_BN_ASM_MONT5)
937 if (window >= 5) {
938 window = 5; /* ~5% improvement for RSA2048 sign, and even for RSA4096 */
939 /* reserve space for mont->N.d[] copy */
940 powerbufLen += top * sizeof(mont->N.d[0]);
941 }
942 #endif
943
944 /* Allocate a buffer large enough to hold all of the pre-computed
945 * powers of am, am itself and tmp.
946 */
947 numPowers = 1 << window;
948 powerbufLen +=
949 sizeof(m->d[0]) *
950 (top * numPowers + ((2 * top) > numPowers ? (2 * top) : numPowers));
951 #ifdef alloca
952 if (powerbufLen < 3072) {
953 powerbufFree = alloca(powerbufLen + MOD_EXP_CTIME_MIN_CACHE_LINE_WIDTH);
954 } else
955 #endif
956 {
957 if ((powerbufFree = OPENSSL_malloc(
958 powerbufLen + MOD_EXP_CTIME_MIN_CACHE_LINE_WIDTH)) == NULL) {
959 goto err;
960 }
961 }
962
963 powerbuf = MOD_EXP_CTIME_ALIGN(powerbufFree);
964 memset(powerbuf, 0, powerbufLen);
965
966 #ifdef alloca
967 if (powerbufLen < 3072) {
968 powerbufFree = NULL;
969 }
970 #endif
971
972 /* lay down tmp and am right after powers table */
973 tmp.d = (BN_ULONG *)(powerbuf + sizeof(m->d[0]) * top * numPowers);
974 am.d = tmp.d + top;
975 tmp.top = am.top = 0;
976 tmp.dmax = am.dmax = top;
977 tmp.neg = am.neg = 0;
978 tmp.flags = am.flags = BN_FLG_STATIC_DATA;
979
980 /* prepare a^0 in Montgomery domain */
981 /* by Shay Gueron's suggestion */
982 if (m->d[top - 1] & (((BN_ULONG)1) << (BN_BITS2 - 1))) {
983 /* 2^(top*BN_BITS2) - m */
984 tmp.d[0] = (0 - m->d[0]) & BN_MASK2;
985 for (i = 1; i < top; i++) {
986 tmp.d[i] = (~m->d[i]) & BN_MASK2;
987 }
988 tmp.top = top;
989 } else if (!BN_to_montgomery(&tmp, BN_value_one(), mont, ctx)) {
990 goto err;
991 }
992
993 /* prepare a^1 in Montgomery domain */
994 if (a->neg || BN_ucmp(a, m) >= 0) {
995 if (!BN_mod(&am, a, m, ctx) ||
996 !BN_to_montgomery(&am, &am, mont, ctx)) {
997 goto err;
998 }
999 } else if (!BN_to_montgomery(&am, a, mont, ctx)) {
1000 goto err;
1001 }
1002
1003 #if defined(OPENSSL_BN_ASM_MONT5)
1004 /* This optimization uses ideas from http://eprint.iacr.org/2011/239,
1005 * specifically optimization of cache-timing attack countermeasures
1006 * and pre-computation optimization. */
1007
1008 /* Dedicated window==4 case improves 512-bit RSA sign by ~15%, but as
1009 * 512-bit RSA is hardly relevant, we omit it to spare size... */
1010 if (window == 5 && top > 1) {
1011 const BN_ULONG *n0 = mont->n0;
1012 BN_ULONG *np;
1013
1014 /* BN_to_montgomery can contaminate words above .top
1015 * [in BN_DEBUG[_DEBUG] build]... */
1016 for (i = am.top; i < top; i++) {
1017 am.d[i] = 0;
1018 }
1019 for (i = tmp.top; i < top; i++) {
1020 tmp.d[i] = 0;
1021 }
1022
1023 /* copy mont->N.d[] to improve cache locality */
1024 for (np = am.d + top, i = 0; i < top; i++) {
1025 np[i] = mont->N.d[i];
1026 }
1027
1028 bn_scatter5(tmp.d, top, powerbuf, 0);
1029 bn_scatter5(am.d, am.top, powerbuf, 1);
1030 bn_mul_mont(tmp.d, am.d, am.d, np, n0, top);
1031 bn_scatter5(tmp.d, top, powerbuf, 2);
1032
1033 /* same as above, but uses squaring for 1/2 of operations */
1034 for (i = 4; i < 32; i *= 2) {
1035 bn_mul_mont(tmp.d, tmp.d, tmp.d, np, n0, top);
1036 bn_scatter5(tmp.d, top, powerbuf, i);
1037 }
1038 for (i = 3; i < 8; i += 2) {
1039 int j;
1040 bn_mul_mont_gather5(tmp.d, am.d, powerbuf, np, n0, top, i - 1);
1041 bn_scatter5(tmp.d, top, powerbuf, i);
1042 for (j = 2 * i; j < 32; j *= 2) {
1043 bn_mul_mont(tmp.d, tmp.d, tmp.d, np, n0, top);
1044 bn_scatter5(tmp.d, top, powerbuf, j);
1045 }
1046 }
1047 for (; i < 16; i += 2) {
1048 bn_mul_mont_gather5(tmp.d, am.d, powerbuf, np, n0, top, i - 1);
1049 bn_scatter5(tmp.d, top, powerbuf, i);
1050 bn_mul_mont(tmp.d, tmp.d, tmp.d, np, n0, top);
1051 bn_scatter5(tmp.d, top, powerbuf, 2 * i);
1052 }
1053 for (; i < 32; i += 2) {
1054 bn_mul_mont_gather5(tmp.d, am.d, powerbuf, np, n0, top, i - 1);
1055 bn_scatter5(tmp.d, top, powerbuf, i);
1056 }
1057
1058 bits--;
1059 for (wvalue = 0, i = bits % 5; i >= 0; i--, bits--) {
1060 wvalue = (wvalue << 1) + BN_is_bit_set(p, bits);
1061 }
1062 bn_gather5(tmp.d, top, powerbuf, wvalue);
1063
1064 /* At this point |bits| is 4 mod 5 and at least -1. (|bits| is the first bit
1065 * that has not been read yet.) */
1066 assert(bits >= -1 && (bits == -1 || bits % 5 == 4));
1067
1068 /* Scan the exponent one window at a time starting from the most
1069 * significant bits.
1070 */
1071 if (top & 7) {
1072 while (bits >= 0) {
1073 for (wvalue = 0, i = 0; i < 5; i++, bits--) {
1074 wvalue = (wvalue << 1) + BN_is_bit_set(p, bits);
1075 }
1076
1077 bn_mul_mont(tmp.d, tmp.d, tmp.d, np, n0, top);
1078 bn_mul_mont(tmp.d, tmp.d, tmp.d, np, n0, top);
1079 bn_mul_mont(tmp.d, tmp.d, tmp.d, np, n0, top);
1080 bn_mul_mont(tmp.d, tmp.d, tmp.d, np, n0, top);
1081 bn_mul_mont(tmp.d, tmp.d, tmp.d, np, n0, top);
1082 bn_mul_mont_gather5(tmp.d, tmp.d, powerbuf, np, n0, top, wvalue);
1083 }
1084 } else {
1085 const uint8_t *p_bytes = (const uint8_t *)p->d;
1086 int max_bits = p->top * BN_BITS2;
1087 assert(bits < max_bits);
1088 /* |p = 0| has been handled as a special case, so |max_bits| is at least
1089 * one word. */
1090 assert(max_bits >= 64);
1091
1092 /* If the first bit to be read lands in the last byte, unroll the first
1093 * iteration to avoid reading past the bounds of |p->d|. (After the first
1094 * iteration, we are guaranteed to be past the last byte.) Note |bits|
1095 * here is the top bit, inclusive. */
1096 if (bits - 4 >= max_bits - 8) {
1097 /* Read five bits from |bits-4| through |bits|, inclusive. */
1098 wvalue = p_bytes[p->top * BN_BYTES - 1];
1099 wvalue >>= (bits - 4) & 7;
1100 wvalue &= 0x1f;
1101 bits -= 5;
1102 bn_power5(tmp.d, tmp.d, powerbuf, np, n0, top, wvalue);
1103 }
1104 while (bits >= 0) {
1105 /* Read five bits from |bits-4| through |bits|, inclusive. */
1106 int first_bit = bits - 4;
1107 wvalue = *(const uint16_t *) (p_bytes + (first_bit >> 3));
1108 wvalue >>= first_bit & 7;
1109 wvalue &= 0x1f;
1110 bits -= 5;
1111 bn_power5(tmp.d, tmp.d, powerbuf, np, n0, top, wvalue);
1112 }
1113 }
1114
1115 ret = bn_from_montgomery(tmp.d, tmp.d, NULL, np, n0, top);
1116 tmp.top = top;
1117 bn_correct_top(&tmp);
1118 if (ret) {
1119 if (!BN_copy(rr, &tmp)) {
1120 ret = 0;
1121 }
1122 goto err; /* non-zero ret means it's not error */
1123 }
1124 } else
1125 #endif
1126 {
1127 if (!copy_to_prebuf(&tmp, top, powerbuf, 0, window) ||
1128 !copy_to_prebuf(&am, top, powerbuf, 1, window)) {
1129 goto err;
1130 }
1131
1132 /* If the window size is greater than 1, then calculate
1133 * val[i=2..2^winsize-1]. Powers are computed as a*a^(i-1)
1134 * (even powers could instead be computed as (a^(i/2))^2
1135 * to use the slight performance advantage of sqr over mul).
1136 */
1137 if (window > 1) {
1138 if (!BN_mod_mul_montgomery(&tmp, &am, &am, mont, ctx) ||
1139 !copy_to_prebuf(&tmp, top, powerbuf, 2, window)) {
1140 goto err;
1141 }
1142 for (i = 3; i < numPowers; i++) {
1143 /* Calculate a^i = a^(i-1) * a */
1144 if (!BN_mod_mul_montgomery(&tmp, &am, &tmp, mont, ctx) ||
1145 !copy_to_prebuf(&tmp, top, powerbuf, i, window)) {
1146 goto err;
1147 }
1148 }
1149 }
1150
1151 bits--;
1152 for (wvalue = 0, i = bits % window; i >= 0; i--, bits--) {
1153 wvalue = (wvalue << 1) + BN_is_bit_set(p, bits);
1154 }
1155 if (!copy_from_prebuf(&tmp, top, powerbuf, wvalue, window)) {
1156 goto err;
1157 }
1158
1159 /* Scan the exponent one window at a time starting from the most
1160 * significant bits.
1161 */
1162 while (bits >= 0) {
1163 wvalue = 0; /* The 'value' of the window */
1164
1165 /* Scan the window, squaring the result as we go */
1166 for (i = 0; i < window; i++, bits--) {
1167 if (!BN_mod_mul_montgomery(&tmp, &tmp, &tmp, mont, ctx)) {
1168 goto err;
1169 }
1170 wvalue = (wvalue << 1) + BN_is_bit_set(p, bits);
1171 }
1172
1173 /* Fetch the appropriate pre-computed value from the pre-buf */
1174 if (!copy_from_prebuf(&am, top, powerbuf, wvalue, window)) {
1175 goto err;
1176 }
1177
1178 /* Multiply the result into the intermediate result */
1179 if (!BN_mod_mul_montgomery(&tmp, &tmp, &am, mont, ctx)) {
1180 goto err;
1181 }
1182 }
1183 }
1184
1185 /* Convert the final result from montgomery to standard format */
1186 if (!BN_from_montgomery(rr, &tmp, mont, ctx)) {
1187 goto err;
1188 }
1189 ret = 1;
1190
1191 err:
1192 BN_MONT_CTX_free(new_mont);
1193 if (powerbuf != NULL) {
1194 OPENSSL_cleanse(powerbuf, powerbufLen);
1195 OPENSSL_free(powerbufFree);
1196 }
1197 return (ret);
1198 }
1199
1200 int BN_mod_exp_mont_word(BIGNUM *rr, BN_ULONG a, const BIGNUM *p,
1201 const BIGNUM *m, BN_CTX *ctx,
1202 const BN_MONT_CTX *mont) {
1203 BIGNUM a_bignum;
1204 BN_init(&a_bignum);
1205
1206 int ret = 0;
1207
1208 if (!BN_set_word(&a_bignum, a)) {
1209 OPENSSL_PUT_ERROR(BN, ERR_R_INTERNAL_ERROR);
1210 goto err;
1211 }
1212
1213 ret = BN_mod_exp_mont(rr, &a_bignum, p, m, ctx, mont);
1214
1215 err:
1216 BN_free(&a_bignum);
1217
1218 return ret;
1219 }
1220
1221 #define TABLE_SIZE 32
1222
1223 int BN_mod_exp2_mont(BIGNUM *rr, const BIGNUM *a1, const BIGNUM *p1,
1224 const BIGNUM *a2, const BIGNUM *p2, const BIGNUM *m,
1225 BN_CTX *ctx, const BN_MONT_CTX *mont) {
1226 BIGNUM tmp;
1227 BN_init(&tmp);
1228
1229 int ret = 0;
1230 BN_MONT_CTX *new_mont = NULL;
1231
1232 /* Allocate a montgomery context if it was not supplied by the caller. */
1233 if (mont == NULL) {
1234 new_mont = BN_MONT_CTX_new();
1235 if (new_mont == NULL || !BN_MONT_CTX_set(new_mont, m, ctx)) {
1236 goto err;
1237 }
1238 mont = new_mont;
1239 }
1240
1241 /* BN_mod_mul_montgomery removes one Montgomery factor, so passing one
1242 * Montgomery-encoded and one non-Montgomery-encoded value gives a
1243 * non-Montgomery-encoded result. */
1244 if (!BN_mod_exp_mont(rr, a1, p1, m, ctx, mont) ||
1245 !BN_mod_exp_mont(&tmp, a2, p2, m, ctx, mont) ||
1246 !BN_to_montgomery(rr, rr, mont, ctx) ||
1247 !BN_mod_mul_montgomery(rr, rr, &tmp, mont, ctx)) {
1248 goto err;
1249 }
1250
1251 ret = 1;
1252
1253 err:
1254 BN_MONT_CTX_free(new_mont);
1255 BN_free(&tmp);
1256
1257 return ret;
1258 }