1 /* 2 * Copyright 2014-2018 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, const BN_ULONG *words, int size) 176 { 177 /* 178 * |const| qualifier omission is compensated by BN_FLG_STATIC_DATA 179 * flag, which effectively means "read-only data". 180 */ 181 a->d = (BN_ULONG *)words; 182 a->dmax = a->top = size; 183 a->neg = 0; 184 a->flags |= BN_FLG_STATIC_DATA; 185 bn_correct_top(a); 186 } 187 188 int bn_set_words(BIGNUM *a, const BN_ULONG *words, int num_words) 189 { 190 if (bn_wexpand(a, num_words) == NULL) { 191 BNerr(BN_F_BN_SET_WORDS, ERR_R_MALLOC_FAILURE); 192 return 0; 193 } 194 195 memcpy(a->d, words, sizeof(BN_ULONG) * num_words); 196 a->top = num_words; 197 bn_correct_top(a); 198 return 1; 199 } 200