crypto/bn/bn_intern.c

   1 /*
   2  * Copyright 2014-2016 The OpenSSL Project Authors. All Rights Reserved.
   3  *
   4  * Licensed under the OpenSSL license (the "License").  You may not use
   5  * this file except in compliance with the License.  You can obtain a copy
   6  * in the file LICENSE in the source distribution or at
   7  * https://www.openssl.org/source/license.html
   8  */
   9
  10 #include "internal/cryptlib.h"
  11 #include "bn_lcl.h"
  12
  13 /*
  14  * Determine the modified width-(w+1) Non-Adjacent Form (wNAF) of 'scalar'.
  15  * This is an array  r[]  of values that are either zero or odd with an
  16  * absolute value less than  2^w  satisfying
  17  *     scalar = \sum_j r[j]*2^j
  18  * where at most one of any  w+1  consecutive digits is non-zero
  19  * with the exception that the most significant digit may be only
  20  * w-1 zeros away from that next non-zero digit.
  21  */
  22 signed char *bn_compute_wNAF(const BIGNUM *scalar, int w, size_t *ret_len)
  23 {
  24     int window_val;
  25     signed char *r = NULL;
  26     int sign = 1;
  27     int bit, next_bit, mask;
  28     size_t len = 0, j;
  29
  30     if (BN_is_zero(scalar)) {
  31         r = OPENSSL_malloc(1);
  32         if (r == NULL) {
  33             BNerr(BN_F_BN_COMPUTE_WNAF, ERR_R_MALLOC_FAILURE);
  34             goto err;
  35         }
  36         r[0] = 0;
  37         *ret_len = 1;
  38         return r;
  39     }
  40
  41     if (w <= 0 || w > 7) {      /* 'signed char' can represent integers with
  42                                  * absolute values less than 2^7 */
  43         BNerr(BN_F_BN_COMPUTE_WNAF, ERR_R_INTERNAL_ERROR);
  44         goto err;
  45     }
  46     bit = 1 << w;               /* at most 128 */
  47     next_bit = bit << 1;        /* at most 256 */
  48     mask = next_bit - 1;        /* at most 255 */
  49
  50     if (BN_is_negative(scalar)) {
  51         sign = -1;
  52     }
  53
  54     if (scalar->d == NULL || scalar->top == 0) {
  55         BNerr(BN_F_BN_COMPUTE_WNAF, ERR_R_INTERNAL_ERROR);
  56         goto err;
  57     }
  58
  59     len = BN_num_bits(scalar);
  60     r = OPENSSL_malloc(len + 1); /*
  61                                   * Modified wNAF may be one digit longer than binary representation
  62                                   * (*ret_len will be set to the actual length, i.e. at most
  63                                   * BN_num_bits(scalar) + 1)
  64                                   */
  65     if (r == NULL) {
  66         BNerr(BN_F_BN_COMPUTE_WNAF, ERR_R_MALLOC_FAILURE);
  67         goto err;
  68     }
  69     window_val = scalar->d[0] & mask;
  70     j = 0;
  71     while ((window_val != 0) || (j + w + 1 < len)) { /* if j+w+1 >= len,
  72                                                       * window_val will not
  73                                                       * increase */
  74         int digit = 0;
  75
  76         /* 0 <= window_val <= 2^(w+1) */
  77
  78         if (window_val & 1) {
  79             /* 0 < window_val < 2^(w+1) */
  80
  81             if (window_val & bit) {
  82                 digit = window_val - next_bit; /* -2^w < digit < 0 */
  83
  84 #if 1                           /* modified wNAF */
  85                 if (j + w + 1 >= len) {
  86                     /*
  87                      * Special case for generating modified wNAFs:
  88                      * no new bits will be added into window_val,
  89                      * so using a positive digit here will decrease
  90                      * the total length of the representation
  91                      */
  92
  93                     digit = window_val & (mask >> 1); /* 0 < digit < 2^w */
  94                 }
  95 #endif
  96             } else {
  97                 digit = window_val; /* 0 < digit < 2^w */
  98             }
  99
 100             if (digit <= -bit || digit >= bit || !(digit & 1)) {
 101                 BNerr(BN_F_BN_COMPUTE_WNAF, ERR_R_INTERNAL_ERROR);
 102                 goto err;
 103             }
 104
 105             window_val -= digit;
 106
 107             /*
 108              * now window_val is 0 or 2^(w+1) in standard wNAF generation;
 109              * for modified window NAFs, it may also be 2^w
 110              */
 111             if (window_val != 0 && window_val != next_bit
 112                 && window_val != bit) {
 113                 BNerr(BN_F_BN_COMPUTE_WNAF, ERR_R_INTERNAL_ERROR);
 114                 goto err;
 115             }
 116         }
 117
 118         r[j++] = sign * digit;
 119
 120         window_val >>= 1;
 121         window_val += bit * BN_is_bit_set(scalar, j + w);
 122
 123         if (window_val > next_bit) {
 124             BNerr(BN_F_BN_COMPUTE_WNAF, ERR_R_INTERNAL_ERROR);
 125             goto err;
 126         }
 127     }
 128
 129     if (j > len + 1) {
 130         BNerr(BN_F_BN_COMPUTE_WNAF, ERR_R_INTERNAL_ERROR);
 131         goto err;
 132     }
 133     *ret_len = j;
 134     return r;
 135
 136  err:
 137     OPENSSL_free(r);
 138     return NULL;
 139 }
 140
 141 int bn_get_top(const BIGNUM *a)
 142 {
 143     return a->top;
 144 }
 145
 146 int bn_get_dmax(const BIGNUM *a)
 147 {
 148     return a->dmax;
 149 }
 150
 151 void bn_set_all_zero(BIGNUM *a)
 152 {
 153     int i;
 154
 155     for (i = a->top; i < a->dmax; i++)
 156         a->d[i] = 0;
 157 }
 158
 159 int bn_copy_words(BN_ULONG *out, const BIGNUM *in, int size)
 160 {
 161     if (in->top > size)
 162         return 0;
 163
 164     memset(out, 0, sizeof(*out) * size);
 165     if (in->d != NULL)
 166         memcpy(out, in->d, sizeof(*out) * in->top);
 167     return 1;
 168 }
 169
 170 BN_ULONG *bn_get_words(const BIGNUM *a)
 171 {
 172     return a->d;
 173 }
 174
 175 void bn_set_static_words(BIGNUM *a, BN_ULONG *words, int size)
 176 {
 177     a->d = words;
 178     a->dmax = a->top = size;
 179     a->neg = 0;
 180     a->flags |= BN_FLG_STATIC_DATA;
 181     bn_correct_top(a);
 182 }
 183
 184 int bn_set_words(BIGNUM *a, BN_ULONG *words, int num_words)
 185 {
 186     if (bn_wexpand(a, num_words) == NULL) {
 187         BNerr(BN_F_BN_SET_WORDS, ERR_R_MALLOC_FAILURE);
 188         return 0;
 189     }
 190
 191     memcpy(a->d, words, sizeof(BN_ULONG) * num_words);
 192     a->top = num_words;
 193     bn_correct_top(a);
 194     return 1;
 195 }