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 <limits.h>
60 #include <string.h>
61
62 #include <openssl/err.h>
63 #include <openssl/mem.h>
64
65 #include "internal.h"
66 #include "../delocate.h"
67
68
BN_new(void)69 BIGNUM *BN_new(void) {
70 BIGNUM *bn = OPENSSL_malloc(sizeof(BIGNUM));
71
72 if (bn == NULL) {
73 OPENSSL_PUT_ERROR(BN, ERR_R_MALLOC_FAILURE);
74 return NULL;
75 }
76
77 OPENSSL_memset(bn, 0, sizeof(BIGNUM));
78 bn->flags = BN_FLG_MALLOCED;
79
80 return bn;
81 }
82
BN_init(BIGNUM * bn)83 void BN_init(BIGNUM *bn) {
84 OPENSSL_memset(bn, 0, sizeof(BIGNUM));
85 }
86
BN_free(BIGNUM * bn)87 void BN_free(BIGNUM *bn) {
88 if (bn == NULL) {
89 return;
90 }
91
92 if ((bn->flags & BN_FLG_STATIC_DATA) == 0) {
93 OPENSSL_free(bn->d);
94 }
95
96 if (bn->flags & BN_FLG_MALLOCED) {
97 OPENSSL_free(bn);
98 } else {
99 bn->d = NULL;
100 }
101 }
102
BN_clear_free(BIGNUM * bn)103 void BN_clear_free(BIGNUM *bn) {
104 BN_free(bn);
105 }
106
BN_dup(const BIGNUM * src)107 BIGNUM *BN_dup(const BIGNUM *src) {
108 BIGNUM *copy;
109
110 if (src == NULL) {
111 return NULL;
112 }
113
114 copy = BN_new();
115 if (copy == NULL) {
116 return NULL;
117 }
118
119 if (!BN_copy(copy, src)) {
120 BN_free(copy);
121 return NULL;
122 }
123
124 return copy;
125 }
126
BN_copy(BIGNUM * dest,const BIGNUM * src)127 BIGNUM *BN_copy(BIGNUM *dest, const BIGNUM *src) {
128 if (src == dest) {
129 return dest;
130 }
131
132 if (!bn_wexpand(dest, src->width)) {
133 return NULL;
134 }
135
136 OPENSSL_memcpy(dest->d, src->d, sizeof(src->d[0]) * src->width);
137
138 dest->width = src->width;
139 dest->neg = src->neg;
140 return dest;
141 }
142
BN_clear(BIGNUM * bn)143 void BN_clear(BIGNUM *bn) {
144 if (bn->d != NULL) {
145 OPENSSL_memset(bn->d, 0, bn->dmax * sizeof(bn->d[0]));
146 }
147
148 bn->width = 0;
149 bn->neg = 0;
150 }
151
DEFINE_METHOD_FUNCTION(BIGNUM,BN_value_one)152 DEFINE_METHOD_FUNCTION(BIGNUM, BN_value_one) {
153 static const BN_ULONG kOneLimbs[1] = { 1 };
154 out->d = (BN_ULONG*) kOneLimbs;
155 out->width = 1;
156 out->dmax = 1;
157 out->neg = 0;
158 out->flags = BN_FLG_STATIC_DATA;
159 }
160
161 // BN_num_bits_word returns the minimum number of bits needed to represent the
162 // value in |l|.
BN_num_bits_word(BN_ULONG l)163 unsigned BN_num_bits_word(BN_ULONG l) {
164 // |BN_num_bits| is often called on RSA prime factors. These have public bit
165 // lengths, but all bits beyond the high bit are secret, so count bits in
166 // constant time.
167 BN_ULONG x, mask;
168 int bits = (l != 0);
169
170 #if BN_BITS2 > 32
171 // Look at the upper half of |x|. |x| is at most 64 bits long.
172 x = l >> 32;
173 // Set |mask| to all ones if |x| (the top 32 bits of |l|) is non-zero and all
174 // all zeros otherwise.
175 mask = 0u - x;
176 mask = (0u - (mask >> (BN_BITS2 - 1)));
177 // If |x| is non-zero, the lower half is included in the bit count in full,
178 // and we count the upper half. Otherwise, we count the lower half.
179 bits += 32 & mask;
180 l ^= (x ^ l) & mask; // |l| is |x| if |mask| and remains |l| otherwise.
181 #endif
182
183 // The remaining blocks are analogous iterations at lower powers of two.
184 x = l >> 16;
185 mask = 0u - x;
186 mask = (0u - (mask >> (BN_BITS2 - 1)));
187 bits += 16 & mask;
188 l ^= (x ^ l) & mask;
189
190 x = l >> 8;
191 mask = 0u - x;
192 mask = (0u - (mask >> (BN_BITS2 - 1)));
193 bits += 8 & mask;
194 l ^= (x ^ l) & mask;
195
196 x = l >> 4;
197 mask = 0u - x;
198 mask = (0u - (mask >> (BN_BITS2 - 1)));
199 bits += 4 & mask;
200 l ^= (x ^ l) & mask;
201
202 x = l >> 2;
203 mask = 0u - x;
204 mask = (0u - (mask >> (BN_BITS2 - 1)));
205 bits += 2 & mask;
206 l ^= (x ^ l) & mask;
207
208 x = l >> 1;
209 mask = 0u - x;
210 mask = (0u - (mask >> (BN_BITS2 - 1)));
211 bits += 1 & mask;
212
213 return bits;
214 }
215
BN_num_bits(const BIGNUM * bn)216 unsigned BN_num_bits(const BIGNUM *bn) {
217 const int width = bn_minimal_width(bn);
218 if (width == 0) {
219 return 0;
220 }
221
222 return (width - 1) * BN_BITS2 + BN_num_bits_word(bn->d[width - 1]);
223 }
224
BN_num_bytes(const BIGNUM * bn)225 unsigned BN_num_bytes(const BIGNUM *bn) {
226 return (BN_num_bits(bn) + 7) / 8;
227 }
228
BN_zero(BIGNUM * bn)229 void BN_zero(BIGNUM *bn) {
230 bn->width = bn->neg = 0;
231 }
232
BN_one(BIGNUM * bn)233 int BN_one(BIGNUM *bn) {
234 return BN_set_word(bn, 1);
235 }
236
BN_set_word(BIGNUM * bn,BN_ULONG value)237 int BN_set_word(BIGNUM *bn, BN_ULONG value) {
238 if (value == 0) {
239 BN_zero(bn);
240 return 1;
241 }
242
243 if (!bn_wexpand(bn, 1)) {
244 return 0;
245 }
246
247 bn->neg = 0;
248 bn->d[0] = value;
249 bn->width = 1;
250 return 1;
251 }
252
BN_set_u64(BIGNUM * bn,uint64_t value)253 int BN_set_u64(BIGNUM *bn, uint64_t value) {
254 #if BN_BITS2 == 64
255 return BN_set_word(bn, value);
256 #elif BN_BITS2 == 32
257 if (value <= BN_MASK2) {
258 return BN_set_word(bn, (BN_ULONG)value);
259 }
260
261 if (!bn_wexpand(bn, 2)) {
262 return 0;
263 }
264
265 bn->neg = 0;
266 bn->d[0] = (BN_ULONG)value;
267 bn->d[1] = (BN_ULONG)(value >> 32);
268 bn->width = 2;
269 return 1;
270 #else
271 #error "BN_BITS2 must be 32 or 64."
272 #endif
273 }
274
bn_set_words(BIGNUM * bn,const BN_ULONG * words,size_t num)275 int bn_set_words(BIGNUM *bn, const BN_ULONG *words, size_t num) {
276 if (!bn_wexpand(bn, num)) {
277 return 0;
278 }
279 OPENSSL_memmove(bn->d, words, num * sizeof(BN_ULONG));
280 // |bn_wexpand| verified that |num| isn't too large.
281 bn->width = (int)num;
282 bn->neg = 0;
283 return 1;
284 }
285
bn_set_static_words(BIGNUM * bn,const BN_ULONG * words,size_t num)286 void bn_set_static_words(BIGNUM *bn, const BN_ULONG *words, size_t num) {
287 if ((bn->flags & BN_FLG_STATIC_DATA) == 0) {
288 OPENSSL_free(bn->d);
289 }
290 bn->d = (BN_ULONG *)words;
291
292 bn->width = num;
293 bn->dmax = num;
294 bn->neg = 0;
295 bn->flags |= BN_FLG_STATIC_DATA;
296 }
297
bn_fits_in_words(const BIGNUM * bn,size_t num)298 int bn_fits_in_words(const BIGNUM *bn, size_t num) {
299 // All words beyond |num| must be zero.
300 BN_ULONG mask = 0;
301 for (size_t i = num; i < (size_t)bn->width; i++) {
302 mask |= bn->d[i];
303 }
304 return mask == 0;
305 }
306
bn_copy_words(BN_ULONG * out,size_t num,const BIGNUM * bn)307 int bn_copy_words(BN_ULONG *out, size_t num, const BIGNUM *bn) {
308 if (bn->neg) {
309 OPENSSL_PUT_ERROR(BN, BN_R_NEGATIVE_NUMBER);
310 return 0;
311 }
312
313 size_t width = (size_t)bn->width;
314 if (width > num) {
315 if (!bn_fits_in_words(bn, num)) {
316 OPENSSL_PUT_ERROR(BN, BN_R_BIGNUM_TOO_LONG);
317 return 0;
318 }
319 width = num;
320 }
321
322 OPENSSL_memset(out, 0, sizeof(BN_ULONG) * num);
323 OPENSSL_memcpy(out, bn->d, sizeof(BN_ULONG) * width);
324 return 1;
325 }
326
BN_is_negative(const BIGNUM * bn)327 int BN_is_negative(const BIGNUM *bn) {
328 return bn->neg != 0;
329 }
330
BN_set_negative(BIGNUM * bn,int sign)331 void BN_set_negative(BIGNUM *bn, int sign) {
332 if (sign && !BN_is_zero(bn)) {
333 bn->neg = 1;
334 } else {
335 bn->neg = 0;
336 }
337 }
338
bn_wexpand(BIGNUM * bn,size_t words)339 int bn_wexpand(BIGNUM *bn, size_t words) {
340 BN_ULONG *a;
341
342 if (words <= (size_t)bn->dmax) {
343 return 1;
344 }
345
346 if (words > (INT_MAX / (4 * BN_BITS2))) {
347 OPENSSL_PUT_ERROR(BN, BN_R_BIGNUM_TOO_LONG);
348 return 0;
349 }
350
351 if (bn->flags & BN_FLG_STATIC_DATA) {
352 OPENSSL_PUT_ERROR(BN, BN_R_EXPAND_ON_STATIC_BIGNUM_DATA);
353 return 0;
354 }
355
356 a = OPENSSL_malloc(sizeof(BN_ULONG) * words);
357 if (a == NULL) {
358 OPENSSL_PUT_ERROR(BN, ERR_R_MALLOC_FAILURE);
359 return 0;
360 }
361
362 OPENSSL_memcpy(a, bn->d, sizeof(BN_ULONG) * bn->width);
363
364 OPENSSL_free(bn->d);
365 bn->d = a;
366 bn->dmax = (int)words;
367
368 return 1;
369 }
370
bn_expand(BIGNUM * bn,size_t bits)371 int bn_expand(BIGNUM *bn, size_t bits) {
372 if (bits + BN_BITS2 - 1 < bits) {
373 OPENSSL_PUT_ERROR(BN, BN_R_BIGNUM_TOO_LONG);
374 return 0;
375 }
376 return bn_wexpand(bn, (bits+BN_BITS2-1)/BN_BITS2);
377 }
378
bn_resize_words(BIGNUM * bn,size_t words)379 int bn_resize_words(BIGNUM *bn, size_t words) {
380 #if defined(OPENSSL_PPC64LE)
381 // This is a workaround for a miscompilation bug in Clang 7.0.1 on POWER.
382 // The unittests catch the miscompilation, if it occurs, and it manifests
383 // as a crash in |bn_fits_in_words|.
384 //
385 // The bug only triggers if building in FIPS mode and with -O3. Clang 8.0.1
386 // has the same bug but this workaround is not effective there---I've not
387 // been able to find a workaround for 8.0.1.
388 //
389 // At the time of writing (2019-08-08), Clang git does *not* have this bug
390 // and does not need this workaroud. The current git version should go on to
391 // be Clang 10 thus, once we can depend on that, this can be removed.
392 if (value_barrier_w((size_t)bn->width == words)) {
393 return 1;
394 }
395 #endif
396
397 if ((size_t)bn->width <= words) {
398 if (!bn_wexpand(bn, words)) {
399 return 0;
400 }
401 OPENSSL_memset(bn->d + bn->width, 0,
402 (words - bn->width) * sizeof(BN_ULONG));
403 bn->width = words;
404 return 1;
405 }
406
407 // All words beyond the new width must be zero.
408 if (!bn_fits_in_words(bn, words)) {
409 OPENSSL_PUT_ERROR(BN, BN_R_BIGNUM_TOO_LONG);
410 return 0;
411 }
412 bn->width = words;
413 return 1;
414 }
415
bn_select_words(BN_ULONG * r,BN_ULONG mask,const BN_ULONG * a,const BN_ULONG * b,size_t num)416 void bn_select_words(BN_ULONG *r, BN_ULONG mask, const BN_ULONG *a,
417 const BN_ULONG *b, size_t num) {
418 for (size_t i = 0; i < num; i++) {
419 OPENSSL_STATIC_ASSERT(sizeof(BN_ULONG) <= sizeof(crypto_word_t),
420 "crypto_word_t is too small");
421 r[i] = constant_time_select_w(mask, a[i], b[i]);
422 }
423 }
424
bn_minimal_width(const BIGNUM * bn)425 int bn_minimal_width(const BIGNUM *bn) {
426 int ret = bn->width;
427 while (ret > 0 && bn->d[ret - 1] == 0) {
428 ret--;
429 }
430 return ret;
431 }
432
bn_set_minimal_width(BIGNUM * bn)433 void bn_set_minimal_width(BIGNUM *bn) {
434 bn->width = bn_minimal_width(bn);
435 if (bn->width == 0) {
436 bn->neg = 0;
437 }
438 }
439