crypto/openssl/crypto/bn/bn_exp.c

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