lib/libcrypto/bn/bn_exp2.c

   1 /* $OpenBSD: bn_exp2.c,v 1.12 2017/01/29 17:49:22 beck Exp $ */
   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-2000 The OpenSSL Project.  All rights reserved.
  60  *
  61  * Redistribution and use in source and binary forms, with or without
  62  * modification, are permitted provided that the following conditions
  63  * are met:
  64  *
  65  * 1. Redistributions of source code must retain the above copyright
  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 <stdio.h>
 113
 114 #include <openssl/err.h>
 115
 116 #include "bn_lcl.h"
 117
 118 #define TABLE_SIZE      32
 119
 120 int
 121 BN_mod_exp2_mont(BIGNUM *rr, const BIGNUM *a1, const BIGNUM *p1,
 122     const BIGNUM *a2, const BIGNUM *p2, const BIGNUM *m, BN_CTX *ctx,
 123     BN_MONT_CTX *in_mont)
 124 {
 125         int i, j, bits, b, bits1, bits2, ret = 0, wpos1, wpos2, window1, window2, wvalue1, wvalue2;
 126         int r_is_one = 1;
 127         BIGNUM *d, *r;
 128         const BIGNUM *a_mod_m;
 129         /* Tables of variables obtained from 'ctx' */
 130         BIGNUM *val1[TABLE_SIZE], *val2[TABLE_SIZE];
 131         BN_MONT_CTX *mont = NULL;
 132
 133         bn_check_top(a1);
 134         bn_check_top(p1);
 135         bn_check_top(a2);
 136         bn_check_top(p2);
 137         bn_check_top(m);
 138
 139         if (!(m->d[0] & 1)) {
 140                 BNerror(BN_R_CALLED_WITH_EVEN_MODULUS);
 141                 return (0);
 142         }
 143         bits1 = BN_num_bits(p1);
 144         bits2 = BN_num_bits(p2);
 145         if ((bits1 == 0) && (bits2 == 0)) {
 146                 ret = BN_one(rr);
 147                 return ret;
 148         }
 149
 150         bits = (bits1 > bits2) ? bits1 : bits2;
 151
 152         BN_CTX_start(ctx);
 153         if ((d = BN_CTX_get(ctx)) == NULL)
 154                 goto err;
 155         if ((r = BN_CTX_get(ctx)) == NULL)
 156                 goto err;
 157         if ((val1[0] = BN_CTX_get(ctx)) == NULL)
 158                 goto err;
 159         if ((val2[0] = BN_CTX_get(ctx)) == NULL)
 160                 goto err;
 161
 162         if (in_mont != NULL)
 163                 mont = in_mont;
 164         else {
 165                 if ((mont = BN_MONT_CTX_new()) == NULL)
 166                         goto err;
 167                 if (!BN_MONT_CTX_set(mont, m, ctx))
 168                         goto err;
 169         }
 170
 171         window1 = BN_window_bits_for_exponent_size(bits1);
 172         window2 = BN_window_bits_for_exponent_size(bits2);
 173
 174         /*
 175          * Build table for a1:   val1[i] := a1^(2*i + 1) mod m  for i = 0 .. 2^(window1-1)
 176          */
 177         if (a1->neg || BN_ucmp(a1, m) >= 0) {
 178                 if (!BN_mod_ct(val1[0], a1, m, ctx))
 179                         goto err;
 180                 a_mod_m = val1[0];
 181         } else
 182                 a_mod_m = a1;
 183         if (BN_is_zero(a_mod_m)) {
 184                 BN_zero(rr);
 185                 ret = 1;
 186                 goto err;
 187         }
 188
 189         if (!BN_to_montgomery(val1[0], a_mod_m, mont, ctx))
 190                 goto err;
 191         if (window1 > 1) {
 192                 if (!BN_mod_mul_montgomery(d, val1[0], val1[0], mont, ctx))
 193                         goto err;
 194
 195                 j = 1 << (window1 - 1);
 196                 for (i = 1; i < j; i++) {
 197                         if (((val1[i] = BN_CTX_get(ctx)) == NULL) ||
 198                             !BN_mod_mul_montgomery(val1[i], val1[i - 1],
 199                             d, mont, ctx))
 200                                 goto err;
 201                 }
 202         }
 203
 204
 205         /*
 206          * Build table for a2:   val2[i] := a2^(2*i + 1) mod m  for i = 0 .. 2^(window2-1)
 207          */
 208         if (a2->neg || BN_ucmp(a2, m) >= 0) {
 209                 if (!BN_mod_ct(val2[0], a2, m, ctx))
 210                         goto err;
 211                 a_mod_m = val2[0];
 212         } else
 213                 a_mod_m = a2;
 214         if (BN_is_zero(a_mod_m)) {
 215                 BN_zero(rr);
 216                 ret = 1;
 217                 goto err;
 218         }
 219         if (!BN_to_montgomery(val2[0], a_mod_m, mont, ctx))
 220                 goto err;
 221         if (window2 > 1) {
 222                 if (!BN_mod_mul_montgomery(d, val2[0], val2[0], mont, ctx))
 223                         goto err;
 224
 225                 j = 1 << (window2 - 1);
 226                 for (i = 1; i < j; i++) {
 227                         if (((val2[i] = BN_CTX_get(ctx)) == NULL) ||
 228                             !BN_mod_mul_montgomery(val2[i], val2[i - 1],
 229                             d, mont, ctx))
 230                                 goto err;
 231                 }
 232         }
 233
 234
 235         /* Now compute the power product, using independent windows. */
 236         r_is_one = 1;
 237         wvalue1 = 0;  /* The 'value' of the first window */
 238         wvalue2 = 0;  /* The 'value' of the second window */
 239         wpos1 = 0;    /* If wvalue1 > 0, the bottom bit of the first window */
 240         wpos2 = 0;    /* If wvalue2 > 0, the bottom bit of the second window */
 241
 242         if (!BN_to_montgomery(r, BN_value_one(), mont, ctx))
 243                 goto err;
 244         for (b = bits - 1; b >= 0; b--) {
 245                 if (!r_is_one) {
 246                         if (!BN_mod_mul_montgomery(r, r,r, mont, ctx))
 247                                 goto err;
 248                 }
 249
 250                 if (!wvalue1)
 251                         if (BN_is_bit_set(p1, b)) {
 252                         /* consider bits b-window1+1 .. b for this window */
 253                         i = b - window1 + 1;
 254                         while (!BN_is_bit_set(p1, i)) /* works for i<0 */
 255                                 i++;
 256                         wpos1 = i;
 257                         wvalue1 = 1;
 258                         for (i = b - 1; i >= wpos1; i--) {
 259                                 wvalue1 <<= 1;
 260                                 if (BN_is_bit_set(p1, i))
 261                                         wvalue1++;
 262                         }
 263                 }
 264
 265                 if (!wvalue2)
 266                         if (BN_is_bit_set(p2, b)) {
 267                         /* consider bits b-window2+1 .. b for this window */
 268                         i = b - window2 + 1;
 269                         while (!BN_is_bit_set(p2, i))
 270                                 i++;
 271                         wpos2 = i;
 272                         wvalue2 = 1;
 273                         for (i = b - 1; i >= wpos2; i--) {
 274                                 wvalue2 <<= 1;
 275                                 if (BN_is_bit_set(p2, i))
 276                                         wvalue2++;
 277                         }
 278                 }
 279
 280                 if (wvalue1 && b == wpos1) {
 281                         /* wvalue1 is odd and < 2^window1 */
 282                         if (!BN_mod_mul_montgomery(r, r, val1[wvalue1 >> 1],
 283                             mont, ctx))
 284                                 goto err;
 285                         wvalue1 = 0;
 286                         r_is_one = 0;
 287                 }
 288
 289                 if (wvalue2 && b == wpos2) {
 290                         /* wvalue2 is odd and < 2^window2 */
 291                         if (!BN_mod_mul_montgomery(r, r, val2[wvalue2 >> 1],
 292                             mont, ctx))
 293                                 goto err;
 294                         wvalue2 = 0;
 295                         r_is_one = 0;
 296                 }
 297         }
 298         if (!BN_from_montgomery(rr, r,mont, ctx))
 299                 goto err;
 300         ret = 1;
 301
 302 err:
 303         if ((in_mont == NULL) && (mont != NULL))
 304                 BN_MONT_CTX_free(mont);
 305         BN_CTX_end(ctx);
 306         bn_check_top(rr);
 307         return (ret);
 308 }