1 /*
2 * Copyright 2014-2020 The OpenSSL Project Authors. All Rights Reserved.
3 *
4 * Licensed under the Apache License 2.0 (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_local.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 */
bn_compute_wNAF(const BIGNUM * scalar,int w,size_t * ret_len)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 goto err;
34 r[0] = 0;
35 *ret_len = 1;
36 return r;
37 }
38
39 if (w <= 0 || w > 7) { /* 'signed char' can represent integers with
40 * absolute values less than 2^7 */
41 ERR_raise(ERR_LIB_BN, ERR_R_INTERNAL_ERROR);
42 goto err;
43 }
44 bit = 1 << w; /* at most 128 */
45 next_bit = bit << 1; /* at most 256 */
46 mask = next_bit - 1; /* at most 255 */
47
48 if (BN_is_negative(scalar)) {
49 sign = -1;
50 }
51
52 if (scalar->d == NULL || scalar->top == 0) {
53 ERR_raise(ERR_LIB_BN, ERR_R_INTERNAL_ERROR);
54 goto err;
55 }
56
57 len = BN_num_bits(scalar);
58 r = OPENSSL_malloc(len + 1); /*
59 * Modified wNAF may be one digit longer than binary representation
60 * (*ret_len will be set to the actual length, i.e. at most
61 * BN_num_bits(scalar) + 1)
62 */
63 if (r == NULL)
64 goto err;
65 window_val = scalar->d[0] & mask;
66 j = 0;
67 while ((window_val != 0) || (j + w + 1 < len)) { /* if j+w+1 >= len,
68 * window_val will not
69 * increase */
70 int digit = 0;
71
72 /* 0 <= window_val <= 2^(w+1) */
73
74 if (window_val & 1) {
75 /* 0 < window_val < 2^(w+1) */
76
77 if (window_val & bit) {
78 digit = window_val - next_bit; /* -2^w < digit < 0 */
79
80 #if 1 /* modified wNAF */
81 if (j + w + 1 >= len) {
82 /*
83 * Special case for generating modified wNAFs:
84 * no new bits will be added into window_val,
85 * so using a positive digit here will decrease
86 * the total length of the representation
87 */
88
89 digit = window_val & (mask >> 1); /* 0 < digit < 2^w */
90 }
91 #endif
92 } else {
93 digit = window_val; /* 0 < digit < 2^w */
94 }
95
96 if (digit <= -bit || digit >= bit || !(digit & 1)) {
97 ERR_raise(ERR_LIB_BN, ERR_R_INTERNAL_ERROR);
98 goto err;
99 }
100
101 window_val -= digit;
102
103 /*
104 * now window_val is 0 or 2^(w+1) in standard wNAF generation;
105 * for modified window NAFs, it may also be 2^w
106 */
107 if (window_val != 0 && window_val != next_bit
108 && window_val != bit) {
109 ERR_raise(ERR_LIB_BN, ERR_R_INTERNAL_ERROR);
110 goto err;
111 }
112 }
113
114 r[j++] = sign * digit;
115
116 window_val >>= 1;
117 window_val += bit * BN_is_bit_set(scalar, j + w);
118
119 if (window_val > next_bit) {
120 ERR_raise(ERR_LIB_BN, ERR_R_INTERNAL_ERROR);
121 goto err;
122 }
123 }
124
125 if (j > len + 1) {
126 ERR_raise(ERR_LIB_BN, ERR_R_INTERNAL_ERROR);
127 goto err;
128 }
129 *ret_len = j;
130 return r;
131
132 err:
133 OPENSSL_free(r);
134 return NULL;
135 }
136
bn_get_top(const BIGNUM * a)137 int bn_get_top(const BIGNUM *a)
138 {
139 return a->top;
140 }
141
bn_get_dmax(const BIGNUM * a)142 int bn_get_dmax(const BIGNUM *a)
143 {
144 return a->dmax;
145 }
146
bn_set_all_zero(BIGNUM * a)147 void bn_set_all_zero(BIGNUM *a)
148 {
149 int i;
150
151 for (i = a->top; i < a->dmax; i++)
152 a->d[i] = 0;
153 }
154
bn_copy_words(BN_ULONG * out,const BIGNUM * in,int size)155 int bn_copy_words(BN_ULONG *out, const BIGNUM *in, int size)
156 {
157 if (in->top > size)
158 return 0;
159
160 memset(out, 0, sizeof(*out) * size);
161 if (in->d != NULL)
162 memcpy(out, in->d, sizeof(*out) * in->top);
163 return 1;
164 }
165
bn_get_words(const BIGNUM * a)166 BN_ULONG *bn_get_words(const BIGNUM *a)
167 {
168 return a->d;
169 }
170
bn_set_static_words(BIGNUM * a,const BN_ULONG * words,int size)171 void bn_set_static_words(BIGNUM *a, const BN_ULONG *words, int size)
172 {
173 /*
174 * |const| qualifier omission is compensated by BN_FLG_STATIC_DATA
175 * flag, which effectively means "read-only data".
176 */
177 a->d = (BN_ULONG *)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
bn_set_words(BIGNUM * a,const BN_ULONG * words,int num_words)184 int bn_set_words(BIGNUM *a, const BN_ULONG *words, int num_words)
185 {
186 if (bn_wexpand(a, num_words) == NULL) {
187 ERR_raise(ERR_LIB_BN, ERR_R_BN_LIB);
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 }
196
