1 | /* |
2 | * Copyright 2014-2018 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 | */ |
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 | |