crypto/bn/bn_intern.c

   1 /* ====================================================================
   2  * Copyright (c) 1998-2014 The OpenSSL Project.  All rights reserved.
   3  *
   4  * Redistribution and use in source and binary forms, with or without
   5  * modification, are permitted provided that the following conditions
   6  * are met:
   7  *
   8  * 1. Redistributions of source code must retain the above copyright
   9  *    notice, this list of conditions and the following disclaimer.
  10  *
  11  * 2. Redistributions in binary form must reproduce the above copyright
  12  *    notice, this list of conditions and the following disclaimer in
  13  *    the documentation and/or other materials provided with the
  14  *    distribution.
  15  *
  16  * 3. All advertising materials mentioning features or use of this
  17  *    software must display the following acknowledgment:
  18  *    "This product includes software developed by the OpenSSL Project
  19  *    for use in the OpenSSL Toolkit. (http://www.openssl.org/)"
  20  *
  21  * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to
  22  *    endorse or promote products derived from this software without
  23  *    prior written permission. For written permission, please contact
  24  *    openssl-core@openssl.org.
  25  *
  26  * 5. Products derived from this software may not be called "OpenSSL"
  27  *    nor may "OpenSSL" appear in their names without prior written
  28  *    permission of the OpenSSL Project.
  29  *
  30  * 6. Redistributions of any form whatsoever must retain the following
  31  *    acknowledgment:
  32  *    "This product includes software developed by the OpenSSL Project
  33  *    for use in the OpenSSL Toolkit (http://www.openssl.org/)"
  34  *
  35  * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY
  36  * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  37  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  38  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE OpenSSL PROJECT OR
  39  * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  40  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  41  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  42  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  43  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
  44  * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  45  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
  46  * OF THE POSSIBILITY OF SUCH DAMAGE.
  47  * ====================================================================
  48  *
  49  * This product includes cryptographic software written by Eric Young
  50  * (eay@cryptsoft.com).  This product includes software written by Tim
  51  * Hudson (tjh@cryptsoft.com).
  52  *
  53  */
  54
  55 #include "cryptlib.h"
  56 #include "bn_lcl.h"
  57
  58 /*
  59  * Determine the modified width-(w+1) Non-Adjacent Form (wNAF) of 'scalar'.
  60  * This is an array  r[]  of values that are either zero or odd with an
  61  * absolute value less than  2^w  satisfying
  62  *     scalar = \sum_j r[j]*2^j
  63  * where at most one of any  w+1  consecutive digits is non-zero
  64  * with the exception that the most significant digit may be only
  65  * w-1 zeros away from that next non-zero digit.
  66  */
  67 signed char *bn_compute_wNAF(const BIGNUM *scalar, int w, size_t *ret_len)
  68 {
  69     int window_val;
  70     int ok = 0;
  71     signed char *r = NULL;
  72     int sign = 1;
  73     int bit, next_bit, mask;
  74     size_t len = 0, j;
  75
  76     if (BN_is_zero(scalar)) {
  77         r = OPENSSL_malloc(1);
  78         if (!r) {
  79             BNerr(BN_F_BN_COMPUTE_WNAF, ERR_R_MALLOC_FAILURE);
  80             goto err;
  81         }
  82         r[0] = 0;
  83         *ret_len = 1;
  84         return r;
  85     }
  86
  87     if (w <= 0 || w > 7) {      /* 'signed char' can represent integers with
  88                                  * absolute values less than 2^7 */
  89         BNerr(BN_F_BN_COMPUTE_WNAF, ERR_R_INTERNAL_ERROR);
  90         goto err;
  91     }
  92     bit = 1 << w;               /* at most 128 */
  93     next_bit = bit << 1;        /* at most 256 */
  94     mask = next_bit - 1;        /* at most 255 */
  95
  96     if (BN_is_negative(scalar)) {
  97         sign = -1;
  98     }
  99
 100     if (scalar->d == NULL || scalar->top == 0) {
 101         BNerr(BN_F_BN_COMPUTE_WNAF, ERR_R_INTERNAL_ERROR);
 102         goto err;
 103     }
 104
 105     len = BN_num_bits(scalar);
 106     r = OPENSSL_malloc(len + 1); /*
 107                                   * Modified wNAF may be one digit longer than binary representation
 108                                   * (*ret_len will be set to the actual length, i.e. at most
 109                                   * BN_num_bits(scalar) + 1)
 110                                   */
 111     if (r == NULL) {
 112         BNerr(BN_F_BN_COMPUTE_WNAF, ERR_R_MALLOC_FAILURE);
 113         goto err;
 114     }
 115     window_val = scalar->d[0] & mask;
 116     j = 0;
 117     while ((window_val != 0) || (j + w + 1 < len)) { /* if j+w+1 >= len,
 118                                                       * window_val will not
 119                                                       * increase */
 120         int digit = 0;
 121
 122         /* 0 <= window_val <= 2^(w+1) */
 123
 124         if (window_val & 1) {
 125             /* 0 < window_val < 2^(w+1) */
 126
 127             if (window_val & bit) {
 128                 digit = window_val - next_bit; /* -2^w < digit < 0 */
 129
 130 #if 1                           /* modified wNAF */
 131                 if (j + w + 1 >= len) {
 132                     /*
 133                      * Special case for generating modified wNAFs:
 134                      * no new bits will be added into window_val,
 135                      * so using a positive digit here will decrease
 136                      * the total length of the representation
 137                      */
 138
 139                     digit = window_val & (mask >> 1); /* 0 < digit < 2^w */
 140                 }
 141 #endif
 142             } else {
 143                 digit = window_val; /* 0 < digit < 2^w */
 144             }
 145
 146             if (digit <= -bit || digit >= bit || !(digit & 1)) {
 147                 BNerr(BN_F_BN_COMPUTE_WNAF, ERR_R_INTERNAL_ERROR);
 148                 goto err;
 149             }
 150
 151             window_val -= digit;
 152
 153             /*
 154              * now window_val is 0 or 2^(w+1) in standard wNAF generation;
 155              * for modified window NAFs, it may also be 2^w
 156              */
 157             if (window_val != 0 && window_val != next_bit
 158                 && window_val != bit) {
 159                 BNerr(BN_F_BN_COMPUTE_WNAF, ERR_R_INTERNAL_ERROR);
 160                 goto err;
 161             }
 162         }
 163
 164         r[j++] = sign * digit;
 165
 166         window_val >>= 1;
 167         window_val += bit * BN_is_bit_set(scalar, j + w);
 168
 169         if (window_val > next_bit) {
 170             BNerr(BN_F_BN_COMPUTE_WNAF, ERR_R_INTERNAL_ERROR);
 171             goto err;
 172         }
 173     }
 174
 175     if (j > len + 1) {
 176         BNerr(BN_F_BN_COMPUTE_WNAF, ERR_R_INTERNAL_ERROR);
 177         goto err;
 178     }
 179     len = j;
 180     ok = 1;
 181
 182  err:
 183     if (!ok) {
 184         OPENSSL_free(r);
 185         r = NULL;
 186     }
 187     if (ok)
 188         *ret_len = len;
 189     return r;
 190 }
 191
 192 int bn_get_top(const BIGNUM *a)
 193 {
 194     return a->top;
 195 }
 196
 197 void bn_set_top(BIGNUM *a, int top)
 198 {
 199     a->top = top;
 200 }
 201
 202 int bn_get_dmax(const BIGNUM *a)
 203 {
 204     return a->dmax;
 205 }
 206
 207 void bn_set_all_zero(BIGNUM *a)
 208 {
 209     int i;
 210
 211     for (i = a->top; i < a->dmax; i++)
 212         a->d[i] = 0;
 213 }
 214
 215 int bn_copy_words(BN_ULONG *out, const BIGNUM *in, int size)
 216 {
 217     if (in->top > size)
 218         return 0;
 219
 220     memset(out, 0, sizeof(BN_ULONG) * size);
 221     memcpy(out, in->d, sizeof(BN_ULONG) * in->top);
 222     return 1;
 223 }
 224
 225 BN_ULONG *bn_get_words(const BIGNUM *a)
 226 {
 227     return a->d;
 228 }
 229
 230 void bn_set_static_words(BIGNUM *a, BN_ULONG *words, int size)
 231 {
 232     a->d = words;
 233     a->dmax = a->top = size;
 234     a->neg = 0;
 235     a->flags |= BN_FLG_STATIC_DATA;
 236 }
 237
 238 void bn_set_data(BIGNUM *a, const void *data, size_t size)
 239 {
 240     memcpy(a->d, data, size);
 241 }
 242
 243 size_t bn_sizeof_BIGNUM(void)
 244 {
 245     return sizeof(BIGNUM);
 246 }
 247
 248 BIGNUM *bn_array_el(BIGNUM *base, int el)
 249 {
 250     return &base[el];
 251 }