[331] | 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 | void bn_set_top(BIGNUM *a, int top)
|
---|
| 147 | {
|
---|
| 148 | a->top = top;
|
---|
| 149 | }
|
---|
| 150 |
|
---|
| 151 | int bn_get_dmax(const BIGNUM *a)
|
---|
| 152 | {
|
---|
| 153 | return a->dmax;
|
---|
| 154 | }
|
---|
| 155 |
|
---|
| 156 | void bn_set_all_zero(BIGNUM *a)
|
---|
| 157 | {
|
---|
| 158 | int i;
|
---|
| 159 |
|
---|
| 160 | for (i = a->top; i < a->dmax; i++)
|
---|
| 161 | a->d[i] = 0;
|
---|
| 162 | }
|
---|
| 163 |
|
---|
| 164 | int bn_copy_words(BN_ULONG *out, const BIGNUM *in, int size)
|
---|
| 165 | {
|
---|
| 166 | if (in->top > size)
|
---|
| 167 | return 0;
|
---|
| 168 |
|
---|
| 169 | memset(out, 0, sizeof(*out) * size);
|
---|
| 170 | if (in->d != NULL)
|
---|
| 171 | memcpy(out, in->d, sizeof(*out) * in->top);
|
---|
| 172 | return 1;
|
---|
| 173 | }
|
---|
| 174 |
|
---|
| 175 | BN_ULONG *bn_get_words(const BIGNUM *a)
|
---|
| 176 | {
|
---|
| 177 | return a->d;
|
---|
| 178 | }
|
---|
| 179 |
|
---|
| 180 | void bn_set_static_words(BIGNUM *a, BN_ULONG *words, int size)
|
---|
| 181 | {
|
---|
| 182 | a->d = words;
|
---|
| 183 | a->dmax = a->top = size;
|
---|
| 184 | a->neg = 0;
|
---|
| 185 | a->flags |= BN_FLG_STATIC_DATA;
|
---|
| 186 | bn_correct_top(a);
|
---|
| 187 | }
|
---|
| 188 |
|
---|
| 189 | int bn_set_words(BIGNUM *a, BN_ULONG *words, int num_words)
|
---|
| 190 | {
|
---|
| 191 | if (bn_wexpand(a, num_words) == NULL) {
|
---|
| 192 | BNerr(BN_F_BN_SET_WORDS, ERR_R_MALLOC_FAILURE);
|
---|
| 193 | return 0;
|
---|
| 194 | }
|
---|
| 195 |
|
---|
| 196 | memcpy(a->d, words, sizeof(BN_ULONG) * num_words);
|
---|
| 197 | a->top = num_words;
|
---|
| 198 | bn_correct_top(a);
|
---|
| 199 | return 1;
|
---|
| 200 | }
|
---|
| 201 |
|
---|
| 202 | size_t bn_sizeof_BIGNUM(void)
|
---|
| 203 | {
|
---|
| 204 | return sizeof(BIGNUM);
|
---|
| 205 | }
|
---|
| 206 |
|
---|
| 207 | BIGNUM *bn_array_el(BIGNUM *base, int el)
|
---|
| 208 | {
|
---|
| 209 | return &base[el];
|
---|
| 210 | }
|
---|