]>
Commit | Line | Data |
---|---|---|
85bcf27c MC |
1 | /* ==================================================================== |
2 | * Copyright (c) 1998-2014 The OpenSSL Project. All rights reserved. | |
3 | * | |
4 | * Redistribution and use in source and binary forms, with or without | |
5 | * modification, are permitted provided that the following conditions | |
6 | * are met: | |
7 | * | |
8 | * 1. Redistributions of source code must retain the above copyright | |
9 | * notice, this list of conditions and the following disclaimer. | |
10 | * | |
11 | * 2. Redistributions in binary form must reproduce the above copyright | |
12 | * notice, this list of conditions and the following disclaimer in | |
13 | * the documentation and/or other materials provided with the | |
14 | * distribution. | |
15 | * | |
16 | * 3. All advertising materials mentioning features or use of this | |
17 | * software must display the following acknowledgment: | |
18 | * "This product includes software developed by the OpenSSL Project | |
19 | * for use in the OpenSSL Toolkit. (http://www.openssl.org/)" | |
20 | * | |
21 | * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to | |
22 | * endorse or promote products derived from this software without | |
23 | * prior written permission. For written permission, please contact | |
24 | * openssl-core@openssl.org. | |
25 | * | |
26 | * 5. Products derived from this software may not be called "OpenSSL" | |
27 | * nor may "OpenSSL" appear in their names without prior written | |
28 | * permission of the OpenSSL Project. | |
29 | * | |
30 | * 6. Redistributions of any form whatsoever must retain the following | |
31 | * acknowledgment: | |
32 | * "This product includes software developed by the OpenSSL Project | |
33 | * for use in the OpenSSL Toolkit (http://www.openssl.org/)" | |
34 | * | |
35 | * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY | |
36 | * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE | |
37 | * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR | |
38 | * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR | |
39 | * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, | |
40 | * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT | |
41 | * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; | |
42 | * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) | |
43 | * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, | |
44 | * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) | |
45 | * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED | |
46 | * OF THE POSSIBILITY OF SUCH DAMAGE. | |
47 | * ==================================================================== | |
48 | * | |
49 | * This product includes cryptographic software written by Eric Young | |
50 | * (eay@cryptsoft.com). This product includes software written by Tim | |
51 | * Hudson (tjh@cryptsoft.com). | |
52 | * | |
53 | */ | |
54 | ||
55 | #include "cryptlib.h" | |
56 | #include "bn_lcl.h" | |
57 | ||
58 | /* | |
59 | * Determine the modified width-(w+1) Non-Adjacent Form (wNAF) of 'scalar'. | |
60 | * This is an array r[] of values that are either zero or odd with an | |
61 | * absolute value less than 2^w satisfying | |
62 | * scalar = \sum_j r[j]*2^j | |
63 | * where at most one of any w+1 consecutive digits is non-zero | |
64 | * with the exception that the most significant digit may be only | |
65 | * w-1 zeros away from that next non-zero digit. | |
66 | */ | |
67 | signed char *bn_compute_wNAF(const BIGNUM *scalar, int w, size_t *ret_len) | |
68 | { | |
69 | int window_val; | |
70 | int ok = 0; | |
71 | signed char *r = NULL; | |
72 | int sign = 1; | |
73 | int bit, next_bit, mask; | |
74 | size_t len = 0, j; | |
75 | ||
76 | if (BN_is_zero(scalar)) { | |
77 | r = OPENSSL_malloc(1); | |
78 | if (!r) { | |
79 | BNerr(BN_F_BN_COMPUTE_WNAF, ERR_R_MALLOC_FAILURE); | |
80 | goto err; | |
81 | } | |
82 | r[0] = 0; | |
83 | *ret_len = 1; | |
84 | return r; | |
85 | } | |
86 | ||
87 | if (w <= 0 || w > 7) { /* 'signed char' can represent integers with absolute values less than 2^7 */ | |
88 | BNerr(BN_F_BN_COMPUTE_WNAF, ERR_R_INTERNAL_ERROR); | |
89 | goto err; | |
90 | } | |
91 | bit = 1 << w; /* at most 128 */ | |
92 | next_bit = bit << 1; /* at most 256 */ | |
93 | mask = next_bit - 1; /* at most 255 */ | |
94 | ||
95 | if (BN_is_negative(scalar)) { | |
96 | sign = -1; | |
97 | } | |
98 | ||
99 | if (scalar->d == NULL || scalar->top == 0) { | |
100 | BNerr(BN_F_BN_COMPUTE_WNAF, ERR_R_INTERNAL_ERROR); | |
101 | goto err; | |
102 | } | |
103 | ||
104 | len = BN_num_bits(scalar); | |
105 | r = OPENSSL_malloc(len + 1); /* | |
106 | * Modified wNAF may be one digit longer than binary representation | |
107 | * (*ret_len will be set to the actual length, i.e. at most | |
108 | * BN_num_bits(scalar) + 1) | |
109 | */ | |
110 | if (r == NULL) { | |
111 | BNerr(BN_F_BN_COMPUTE_WNAF, ERR_R_MALLOC_FAILURE); | |
112 | goto err; | |
113 | } | |
114 | window_val = scalar->d[0] & mask; | |
115 | j = 0; | |
116 | while ((window_val != 0) || (j + w + 1 < len)) { /* if j+w+1 >= len, window_val will not increase */ | |
117 | int digit = 0; | |
118 | ||
119 | /* 0 <= window_val <= 2^(w+1) */ | |
120 | ||
121 | if (window_val & 1) { | |
122 | /* 0 < window_val < 2^(w+1) */ | |
123 | ||
124 | if (window_val & bit) { | |
125 | digit = window_val - next_bit; /* -2^w < digit < 0 */ | |
126 | ||
127 | #if 1 /* modified wNAF */ | |
128 | if (j + w + 1 >= len) { | |
129 | /* | |
130 | * Special case for generating modified wNAFs: | |
131 | * no new bits will be added into window_val, | |
132 | * so using a positive digit here will decrease | |
133 | * the total length of the representation | |
134 | */ | |
135 | ||
136 | digit = window_val & (mask >> 1); /* 0 < digit < 2^w */ | |
137 | } | |
138 | #endif | |
139 | } else { | |
140 | digit = window_val; /* 0 < digit < 2^w */ | |
141 | } | |
142 | ||
143 | if (digit <= -bit || digit >= bit || !(digit & 1)) { | |
144 | BNerr(BN_F_BN_COMPUTE_WNAF, ERR_R_INTERNAL_ERROR); | |
145 | goto err; | |
146 | } | |
147 | ||
148 | window_val -= digit; | |
149 | ||
150 | /* now window_val is 0 or 2^(w+1) in standard wNAF generation; | |
151 | * for modified window NAFs, it may also be 2^w | |
152 | */ | |
153 | if (window_val != 0 && window_val != next_bit && window_val != bit) { | |
154 | BNerr(BN_F_BN_COMPUTE_WNAF, ERR_R_INTERNAL_ERROR); | |
155 | goto err; | |
156 | } | |
157 | } | |
158 | ||
159 | r[j++] = sign * digit; | |
160 | ||
161 | window_val >>= 1; | |
162 | window_val += bit * BN_is_bit_set(scalar, j + w); | |
163 | ||
164 | if (window_val > next_bit) { | |
165 | BNerr(BN_F_BN_COMPUTE_WNAF, ERR_R_INTERNAL_ERROR); | |
166 | goto err; | |
167 | } | |
168 | } | |
169 | ||
170 | if (j > len + 1) { | |
171 | BNerr(BN_F_BN_COMPUTE_WNAF, ERR_R_INTERNAL_ERROR); | |
172 | goto err; | |
173 | } | |
174 | len = j; | |
175 | ok = 1; | |
176 | ||
177 | err: | |
178 | if (!ok) { | |
179 | OPENSSL_free(r); | |
180 | r = NULL; | |
181 | } | |
182 | if (ok) | |
183 | *ret_len = len; | |
184 | return r; | |
185 | } | |
186 | ||
187 | int bn_get_top(const BIGNUM *a) | |
188 | { | |
189 | return a->top; | |
190 | } | |
191 | ||
192 | void bn_set_top(BIGNUM *a, int top) | |
193 | { | |
194 | a->top = top; | |
195 | } | |
196 | ||
197 | int bn_get_dmax(const BIGNUM *a) | |
198 | { | |
199 | return a->dmax; | |
200 | } | |
201 | ||
202 | void bn_set_all_zero(BIGNUM *a) | |
203 | { | |
204 | int i; | |
205 | ||
206 | for (i = a->top; i < a->dmax; i++) a->d[i] = 0; | |
207 | } | |
208 | ||
209 | int bn_copy_words(BN_ULONG *out, const BIGNUM *in, int size) | |
210 | { | |
211 | if (in->top > size) | |
212 | return 0; | |
213 | ||
214 | memset(out, 0, sizeof(BN_ULONG) * size); | |
215 | memcpy(out, in->d, sizeof(BN_ULONG) * in->top); | |
216 | return 1; | |
217 | } | |
218 | ||
219 | BN_ULONG *bn_get_words(const BIGNUM *a) | |
220 | { | |
221 | return a->d; | |
222 | } | |
223 | ||
224 | void bn_set_static_words(BIGNUM *a, BN_ULONG *words, int size) | |
225 | { | |
226 | a->d = words; | |
227 | a->dmax = a->top = size; | |
228 | a->neg = 0; | |
229 | a->flags |= BN_FLG_STATIC_DATA; | |
230 | } | |
231 | ||
232 | void bn_set_data(BIGNUM *a, const void *data, size_t size) | |
233 | { | |
234 | memcpy(a->d, data, size); | |
235 | } | |
236 | ||
237 | size_t bn_sizeof_BIGNUM(void) | |
238 | { | |
239 | return sizeof(BIGNUM); | |
240 | } | |
241 | ||
242 | BIGNUM *bn_array_el(BIGNUM *base, int el) | |
243 | { | |
244 | return &base[el]; | |
245 | } | |
246 | ||
247 | ||
248 |