/src/boringssl/crypto/fipsmodule/bn/bn.c.inc
Line | Count | Source (jump to first uncovered line) |
1 | | /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) |
2 | | * All rights reserved. |
3 | | * |
4 | | * This package is an SSL implementation written |
5 | | * by Eric Young (eay@cryptsoft.com). |
6 | | * The implementation was written so as to conform with Netscapes SSL. |
7 | | * |
8 | | * This library is free for commercial and non-commercial use as long as |
9 | | * the following conditions are aheared to. The following conditions |
10 | | * apply to all code found in this distribution, be it the RC4, RSA, |
11 | | * lhash, DES, etc., code; not just the SSL code. The SSL documentation |
12 | | * included with this distribution is covered by the same copyright terms |
13 | | * except that the holder is Tim Hudson (tjh@cryptsoft.com). |
14 | | * |
15 | | * Copyright remains Eric Young's, and as such any Copyright notices in |
16 | | * the code are not to be removed. |
17 | | * If this package is used in a product, Eric Young should be given attribution |
18 | | * as the author of the parts of the library used. |
19 | | * This can be in the form of a textual message at program startup or |
20 | | * in documentation (online or textual) provided with the package. |
21 | | * |
22 | | * Redistribution and use in source and binary forms, with or without |
23 | | * modification, are permitted provided that the following conditions |
24 | | * are met: |
25 | | * 1. Redistributions of source code must retain the copyright |
26 | | * notice, this list of conditions and the following disclaimer. |
27 | | * 2. Redistributions in binary form must reproduce the above copyright |
28 | | * notice, this list of conditions and the following disclaimer in the |
29 | | * documentation and/or other materials provided with the distribution. |
30 | | * 3. All advertising materials mentioning features or use of this software |
31 | | * must display the following acknowledgement: |
32 | | * "This product includes cryptographic software written by |
33 | | * Eric Young (eay@cryptsoft.com)" |
34 | | * The word 'cryptographic' can be left out if the rouines from the library |
35 | | * being used are not cryptographic related :-). |
36 | | * 4. If you include any Windows specific code (or a derivative thereof) from |
37 | | * the apps directory (application code) you must include an acknowledgement: |
38 | | * "This product includes software written by Tim Hudson (tjh@cryptsoft.com)" |
39 | | * |
40 | | * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND |
41 | | * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE |
42 | | * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE |
43 | | * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE |
44 | | * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL |
45 | | * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS |
46 | | * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) |
47 | | * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT |
48 | | * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY |
49 | | * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF |
50 | | * SUCH DAMAGE. |
51 | | * |
52 | | * The licence and distribution terms for any publically available version or |
53 | | * derivative of this code cannot be changed. i.e. this code cannot simply be |
54 | | * copied and put under another distribution licence |
55 | | * [including the GNU Public Licence.] */ |
56 | | |
57 | | #include <openssl/bn.h> |
58 | | |
59 | | #include <assert.h> |
60 | | #include <limits.h> |
61 | | #include <string.h> |
62 | | |
63 | | #include <openssl/err.h> |
64 | | #include <openssl/mem.h> |
65 | | |
66 | | #include "internal.h" |
67 | | #include "../delocate.h" |
68 | | |
69 | | |
70 | | // BN_MAX_WORDS is the maximum number of words allowed in a |BIGNUM|. It is |
71 | | // sized so byte and bit counts of a |BIGNUM| always fit in |int|, with room to |
72 | | // spare. |
73 | 228k | #define BN_MAX_WORDS (INT_MAX / (4 * BN_BITS2)) |
74 | | |
75 | 302k | BIGNUM *BN_new(void) { |
76 | 302k | BIGNUM *bn = OPENSSL_malloc(sizeof(BIGNUM)); |
77 | | |
78 | 302k | if (bn == NULL) { |
79 | 0 | return NULL; |
80 | 0 | } |
81 | | |
82 | 302k | OPENSSL_memset(bn, 0, sizeof(BIGNUM)); |
83 | 302k | bn->flags = BN_FLG_MALLOCED; |
84 | | |
85 | 302k | return bn; |
86 | 302k | } |
87 | | |
88 | | BIGNUM *BN_secure_new(void) { return BN_new(); } |
89 | | |
90 | 2.25k | void BN_init(BIGNUM *bn) { |
91 | 2.25k | OPENSSL_memset(bn, 0, sizeof(BIGNUM)); |
92 | 2.25k | } |
93 | | |
94 | 69.8k | void BN_free(BIGNUM *bn) { |
95 | 69.8k | if (bn == NULL) { |
96 | 26.1k | return; |
97 | 26.1k | } |
98 | | |
99 | 43.6k | if ((bn->flags & BN_FLG_STATIC_DATA) == 0) { |
100 | 43.6k | OPENSSL_free(bn->d); |
101 | 43.6k | } |
102 | | |
103 | 43.6k | if (bn->flags & BN_FLG_MALLOCED) { |
104 | 41.4k | OPENSSL_free(bn); |
105 | 41.4k | } else { |
106 | 2.23k | bn->d = NULL; |
107 | 2.23k | } |
108 | 43.6k | } |
109 | | |
110 | 1.01k | void BN_clear_free(BIGNUM *bn) { |
111 | 1.01k | BN_free(bn); |
112 | 1.01k | } |
113 | | |
114 | 3.18k | BIGNUM *BN_dup(const BIGNUM *src) { |
115 | 3.18k | BIGNUM *copy; |
116 | | |
117 | 3.18k | if (src == NULL) { |
118 | 0 | return NULL; |
119 | 0 | } |
120 | | |
121 | 3.18k | copy = BN_new(); |
122 | 3.18k | if (copy == NULL) { |
123 | 0 | return NULL; |
124 | 0 | } |
125 | | |
126 | 3.18k | if (!BN_copy(copy, src)) { |
127 | 0 | BN_free(copy); |
128 | 0 | return NULL; |
129 | 0 | } |
130 | | |
131 | 3.18k | return copy; |
132 | 3.18k | } |
133 | | |
134 | 24.1k | BIGNUM *BN_copy(BIGNUM *dest, const BIGNUM *src) { |
135 | 24.1k | if (src == dest) { |
136 | 850 | return dest; |
137 | 850 | } |
138 | | |
139 | 23.3k | if (!bn_wexpand(dest, src->width)) { |
140 | 0 | return NULL; |
141 | 0 | } |
142 | | |
143 | 23.3k | OPENSSL_memcpy(dest->d, src->d, sizeof(src->d[0]) * src->width); |
144 | | |
145 | 23.3k | dest->width = src->width; |
146 | 23.3k | dest->neg = src->neg; |
147 | 23.3k | return dest; |
148 | 23.3k | } |
149 | | |
150 | | void BN_clear(BIGNUM *bn) { |
151 | | if (bn->d != NULL) { |
152 | | OPENSSL_memset(bn->d, 0, bn->dmax * sizeof(bn->d[0])); |
153 | | } |
154 | | |
155 | | bn->width = 0; |
156 | | bn->neg = 0; |
157 | | } |
158 | | |
159 | 2 | DEFINE_METHOD_FUNCTION(BIGNUM, BN_value_one) { |
160 | 2 | static const BN_ULONG kOneLimbs[1] = { 1 }; |
161 | 2 | out->d = (BN_ULONG*) kOneLimbs; |
162 | 2 | out->width = 1; |
163 | 2 | out->dmax = 1; |
164 | 2 | out->neg = 0; |
165 | 2 | out->flags = BN_FLG_STATIC_DATA; |
166 | 2 | } |
167 | | |
168 | | // BN_num_bits_word returns the minimum number of bits needed to represent the |
169 | | // value in |l|. |
170 | 56.0M | unsigned BN_num_bits_word(BN_ULONG l) { |
171 | | // |BN_num_bits| is often called on RSA prime factors. These have public bit |
172 | | // lengths, but all bits beyond the high bit are secret, so count bits in |
173 | | // constant time. |
174 | 56.0M | BN_ULONG x, mask; |
175 | 56.0M | int bits = (l != 0); |
176 | | |
177 | 56.0M | #if BN_BITS2 > 32 |
178 | | // Look at the upper half of |x|. |x| is at most 64 bits long. |
179 | 56.0M | x = l >> 32; |
180 | | // Set |mask| to all ones if |x| (the top 32 bits of |l|) is non-zero and all |
181 | | // all zeros otherwise. |
182 | 56.0M | mask = 0u - x; |
183 | 56.0M | mask = (0u - (mask >> (BN_BITS2 - 1))); |
184 | | // If |x| is non-zero, the lower half is included in the bit count in full, |
185 | | // and we count the upper half. Otherwise, we count the lower half. |
186 | 56.0M | bits += 32 & mask; |
187 | 56.0M | l ^= (x ^ l) & mask; // |l| is |x| if |mask| and remains |l| otherwise. |
188 | 56.0M | #endif |
189 | | |
190 | | // The remaining blocks are analogous iterations at lower powers of two. |
191 | 56.0M | x = l >> 16; |
192 | 56.0M | mask = 0u - x; |
193 | 56.0M | mask = (0u - (mask >> (BN_BITS2 - 1))); |
194 | 56.0M | bits += 16 & mask; |
195 | 56.0M | l ^= (x ^ l) & mask; |
196 | | |
197 | 56.0M | x = l >> 8; |
198 | 56.0M | mask = 0u - x; |
199 | 56.0M | mask = (0u - (mask >> (BN_BITS2 - 1))); |
200 | 56.0M | bits += 8 & mask; |
201 | 56.0M | l ^= (x ^ l) & mask; |
202 | | |
203 | 56.0M | x = l >> 4; |
204 | 56.0M | mask = 0u - x; |
205 | 56.0M | mask = (0u - (mask >> (BN_BITS2 - 1))); |
206 | 56.0M | bits += 4 & mask; |
207 | 56.0M | l ^= (x ^ l) & mask; |
208 | | |
209 | 56.0M | x = l >> 2; |
210 | 56.0M | mask = 0u - x; |
211 | 56.0M | mask = (0u - (mask >> (BN_BITS2 - 1))); |
212 | 56.0M | bits += 2 & mask; |
213 | 56.0M | l ^= (x ^ l) & mask; |
214 | | |
215 | 56.0M | x = l >> 1; |
216 | 56.0M | mask = 0u - x; |
217 | 56.0M | mask = (0u - (mask >> (BN_BITS2 - 1))); |
218 | 56.0M | bits += 1 & mask; |
219 | | |
220 | 56.0M | return bits; |
221 | 56.0M | } |
222 | | |
223 | 422k | unsigned BN_num_bits(const BIGNUM *bn) { |
224 | 422k | const int width = bn_minimal_width(bn); |
225 | 422k | if (width == 0) { |
226 | 5.01k | return 0; |
227 | 5.01k | } |
228 | | |
229 | 417k | return (width - 1) * BN_BITS2 + BN_num_bits_word(bn->d[width - 1]); |
230 | 422k | } |
231 | | |
232 | 14.9k | unsigned BN_num_bytes(const BIGNUM *bn) { |
233 | 14.9k | return (BN_num_bits(bn) + 7) / 8; |
234 | 14.9k | } |
235 | | |
236 | 6.97M | void BN_zero(BIGNUM *bn) { |
237 | 6.97M | bn->width = bn->neg = 0; |
238 | 6.97M | } |
239 | | |
240 | 364 | int BN_one(BIGNUM *bn) { |
241 | 364 | return BN_set_word(bn, 1); |
242 | 364 | } |
243 | | |
244 | 9.51k | int BN_set_word(BIGNUM *bn, BN_ULONG value) { |
245 | 9.51k | if (value == 0) { |
246 | 1 | BN_zero(bn); |
247 | 1 | return 1; |
248 | 1 | } |
249 | | |
250 | 9.51k | if (!bn_wexpand(bn, 1)) { |
251 | 0 | return 0; |
252 | 0 | } |
253 | | |
254 | 9.51k | bn->neg = 0; |
255 | 9.51k | bn->d[0] = value; |
256 | 9.51k | bn->width = 1; |
257 | 9.51k | return 1; |
258 | 9.51k | } |
259 | | |
260 | 0 | int BN_set_u64(BIGNUM *bn, uint64_t value) { |
261 | 0 | #if BN_BITS2 == 64 |
262 | 0 | return BN_set_word(bn, value); |
263 | | #elif BN_BITS2 == 32 |
264 | | if (value <= BN_MASK2) { |
265 | | return BN_set_word(bn, (BN_ULONG)value); |
266 | | } |
267 | | |
268 | | if (!bn_wexpand(bn, 2)) { |
269 | | return 0; |
270 | | } |
271 | | |
272 | | bn->neg = 0; |
273 | | bn->d[0] = (BN_ULONG)value; |
274 | | bn->d[1] = (BN_ULONG)(value >> 32); |
275 | | bn->width = 2; |
276 | | return 1; |
277 | | #else |
278 | | #error "BN_BITS2 must be 32 or 64." |
279 | | #endif |
280 | 0 | } |
281 | | |
282 | 48 | int bn_set_words(BIGNUM *bn, const BN_ULONG *words, size_t num) { |
283 | 48 | if (!bn_wexpand(bn, num)) { |
284 | 0 | return 0; |
285 | 0 | } |
286 | 48 | OPENSSL_memmove(bn->d, words, num * sizeof(BN_ULONG)); |
287 | | // |bn_wexpand| verified that |num| isn't too large. |
288 | 48 | bn->width = (int)num; |
289 | 48 | bn->neg = 0; |
290 | 48 | return 1; |
291 | 48 | } |
292 | | |
293 | 32 | void bn_set_static_words(BIGNUM *bn, const BN_ULONG *words, size_t num) { |
294 | 32 | if ((bn->flags & BN_FLG_STATIC_DATA) == 0) { |
295 | 32 | OPENSSL_free(bn->d); |
296 | 32 | } |
297 | 32 | bn->d = (BN_ULONG *)words; |
298 | | |
299 | 32 | assert(num <= BN_MAX_WORDS); |
300 | 32 | bn->width = (int)num; |
301 | 32 | bn->dmax = (int)num; |
302 | 32 | bn->neg = 0; |
303 | 32 | bn->flags |= BN_FLG_STATIC_DATA; |
304 | 32 | } |
305 | | |
306 | 937k | int bn_fits_in_words(const BIGNUM *bn, size_t num) { |
307 | | // All words beyond |num| must be zero. |
308 | 937k | BN_ULONG mask = 0; |
309 | 43.3M | for (size_t i = num; i < (size_t)bn->width; i++) { |
310 | 42.4M | mask |= bn->d[i]; |
311 | 42.4M | } |
312 | 937k | return mask == 0; |
313 | 937k | } |
314 | | |
315 | 94.9k | int bn_copy_words(BN_ULONG *out, size_t num, const BIGNUM *bn) { |
316 | 94.9k | if (bn->neg) { |
317 | 0 | OPENSSL_PUT_ERROR(BN, BN_R_NEGATIVE_NUMBER); |
318 | 0 | return 0; |
319 | 0 | } |
320 | | |
321 | 94.9k | size_t width = (size_t)bn->width; |
322 | 94.9k | if (width > num) { |
323 | 35 | if (!bn_fits_in_words(bn, num)) { |
324 | 31 | OPENSSL_PUT_ERROR(BN, BN_R_BIGNUM_TOO_LONG); |
325 | 31 | return 0; |
326 | 31 | } |
327 | 4 | width = num; |
328 | 4 | } |
329 | | |
330 | 94.8k | OPENSSL_memset(out, 0, sizeof(BN_ULONG) * num); |
331 | 94.8k | OPENSSL_memcpy(out, bn->d, sizeof(BN_ULONG) * width); |
332 | 94.8k | return 1; |
333 | 94.9k | } |
334 | | |
335 | 2.17M | int BN_is_negative(const BIGNUM *bn) { |
336 | 2.17M | return bn->neg != 0; |
337 | 2.17M | } |
338 | | |
339 | 4.27k | void BN_set_negative(BIGNUM *bn, int sign) { |
340 | 4.27k | if (sign && !BN_is_zero(bn)) { |
341 | 132 | bn->neg = 1; |
342 | 4.13k | } else { |
343 | 4.13k | bn->neg = 0; |
344 | 4.13k | } |
345 | 4.27k | } |
346 | | |
347 | 13.0M | int bn_wexpand(BIGNUM *bn, size_t words) { |
348 | 13.0M | BN_ULONG *a; |
349 | | |
350 | 13.0M | if (words <= (size_t)bn->dmax) { |
351 | 12.8M | return 1; |
352 | 12.8M | } |
353 | | |
354 | 228k | if (words > BN_MAX_WORDS) { |
355 | 0 | OPENSSL_PUT_ERROR(BN, BN_R_BIGNUM_TOO_LONG); |
356 | 0 | return 0; |
357 | 0 | } |
358 | | |
359 | 228k | if (bn->flags & BN_FLG_STATIC_DATA) { |
360 | 0 | OPENSSL_PUT_ERROR(BN, BN_R_EXPAND_ON_STATIC_BIGNUM_DATA); |
361 | 0 | return 0; |
362 | 0 | } |
363 | | |
364 | 228k | a = OPENSSL_calloc(words, sizeof(BN_ULONG)); |
365 | 228k | if (a == NULL) { |
366 | 0 | return 0; |
367 | 0 | } |
368 | | |
369 | 228k | OPENSSL_memcpy(a, bn->d, sizeof(BN_ULONG) * bn->width); |
370 | | |
371 | 228k | OPENSSL_free(bn->d); |
372 | 228k | bn->d = a; |
373 | 228k | bn->dmax = (int)words; |
374 | | |
375 | 228k | return 1; |
376 | 228k | } |
377 | | |
378 | 0 | int bn_expand(BIGNUM *bn, size_t bits) { |
379 | 0 | if (bits + BN_BITS2 - 1 < bits) { |
380 | 0 | OPENSSL_PUT_ERROR(BN, BN_R_BIGNUM_TOO_LONG); |
381 | 0 | return 0; |
382 | 0 | } |
383 | 0 | return bn_wexpand(bn, (bits+BN_BITS2-1)/BN_BITS2); |
384 | 0 | } |
385 | | |
386 | 2.32M | int bn_resize_words(BIGNUM *bn, size_t words) { |
387 | 2.32M | if ((size_t)bn->width <= words) { |
388 | 2.32M | if (!bn_wexpand(bn, words)) { |
389 | 0 | return 0; |
390 | 0 | } |
391 | 2.32M | OPENSSL_memset(bn->d + bn->width, 0, |
392 | 2.32M | (words - bn->width) * sizeof(BN_ULONG)); |
393 | 2.32M | bn->width = (int)words; |
394 | 2.32M | return 1; |
395 | 2.32M | } |
396 | | |
397 | | // All words beyond the new width must be zero. |
398 | 0 | if (!bn_fits_in_words(bn, words)) { |
399 | 0 | OPENSSL_PUT_ERROR(BN, BN_R_BIGNUM_TOO_LONG); |
400 | 0 | return 0; |
401 | 0 | } |
402 | 0 | bn->width = (int)words; |
403 | 0 | return 1; |
404 | 0 | } |
405 | | |
406 | | void bn_select_words(BN_ULONG *r, BN_ULONG mask, const BN_ULONG *a, |
407 | 39.3M | const BN_ULONG *b, size_t num) { |
408 | 975M | for (size_t i = 0; i < num; i++) { |
409 | 936M | static_assert(sizeof(BN_ULONG) <= sizeof(crypto_word_t), |
410 | 936M | "crypto_word_t is too small"); |
411 | 936M | r[i] = constant_time_select_w(mask, a[i], b[i]); |
412 | 936M | } |
413 | 39.3M | } |
414 | | |
415 | 3.58M | int bn_minimal_width(const BIGNUM *bn) { |
416 | 3.58M | int ret = bn->width; |
417 | 55.1M | while (ret > 0 && bn->d[ret - 1] == 0) { |
418 | 51.5M | ret--; |
419 | 51.5M | } |
420 | 3.58M | return ret; |
421 | 3.58M | } |
422 | | |
423 | 3.15M | void bn_set_minimal_width(BIGNUM *bn) { |
424 | 3.15M | bn->width = bn_minimal_width(bn); |
425 | 3.15M | if (bn->width == 0) { |
426 | 4.82k | bn->neg = 0; |
427 | 4.82k | } |
428 | 3.15M | } |