1 /* $OpenBSD: bn_lib.c,v 1.48 2021/09/08 12:19:17 tb Exp $ */
2 /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
3  * All rights reserved.
4  *
5  * This package is an SSL implementation written
6  * by Eric Young (eay@cryptsoft.com).
7  * The implementation was written so as to conform with Netscapes SSL.
8  *
9  * This library is free for commercial and non-commercial use as long as
10  * the following conditions are aheared to.  The following conditions
11  * apply to all code found in this distribution, be it the RC4, RSA,
12  * lhash, DES, etc., code; not just the SSL code.  The SSL documentation
13  * included with this distribution is covered by the same copyright terms
14  * except that the holder is Tim Hudson (tjh@cryptsoft.com).
15  *
16  * Copyright remains Eric Young's, and as such any Copyright notices in
17  * the code are not to be removed.
18  * If this package is used in a product, Eric Young should be given attribution
19  * as the author of the parts of the library used.
20  * This can be in the form of a textual message at program startup or
21  * in documentation (online or textual) provided with the package.
22  *
23  * Redistribution and use in source and binary forms, with or without
24  * modification, are permitted provided that the following conditions
25  * are met:
26  * 1. Redistributions of source code must retain the copyright
27  *    notice, this list of conditions and the following disclaimer.
28  * 2. Redistributions in binary form must reproduce the above copyright
29  *    notice, this list of conditions and the following disclaimer in the
30  *    documentation and/or other materials provided with the distribution.
31  * 3. All advertising materials mentioning features or use of this software
32  *    must display the following acknowledgement:
33  *    "This product includes cryptographic software written by
34  *     Eric Young (eay@cryptsoft.com)"
35  *    The word 'cryptographic' can be left out if the rouines from the library
36  *    being used are not cryptographic related :-).
37  * 4. If you include any Windows specific code (or a derivative thereof) from
38  *    the apps directory (application code) you must include an acknowledgement:
39  *    "This product includes software written by Tim Hudson (tjh@cryptsoft.com)"
40  *
41  * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND
42  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
43  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
44  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
45  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
46  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
47  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
48  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
49  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
50  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
51  * SUCH DAMAGE.
52  *
53  * The licence and distribution terms for any publically available version or
54  * derivative of this code cannot be changed.  i.e. this code cannot simply be
55  * copied and put under another distribution licence
56  * [including the GNU Public Licence.]
57  */
58 
59 #ifndef BN_DEBUG
60 # undef NDEBUG /* avoid conflicting definitions */
61 # define NDEBUG
62 #endif
63 
64 #include <assert.h>
65 #include <limits.h>
66 #include <stdio.h>
67 #include <string.h>
68 
69 #include <openssl/opensslconf.h>
70 
71 #include <openssl/err.h>
72 
73 #include "bn_lcl.h"
74 
75 /* This stuff appears to be completely unused, so is deprecated */
76 #ifndef OPENSSL_NO_DEPRECATED
77 /* For a 32 bit machine
78  * 2 -   4 ==  128
79  * 3 -   8 ==  256
80  * 4 -  16 ==  512
81  * 5 -  32 == 1024
82  * 6 -  64 == 2048
83  * 7 - 128 == 4096
84  * 8 - 256 == 8192
85  */
86 static int bn_limit_bits = 0;
87 static int bn_limit_num = 8;        /* (1<<bn_limit_bits) */
88 static int bn_limit_bits_low = 0;
89 static int bn_limit_num_low = 8;    /* (1<<bn_limit_bits_low) */
90 static int bn_limit_bits_high = 0;
91 static int bn_limit_num_high = 8;   /* (1<<bn_limit_bits_high) */
92 static int bn_limit_bits_mont = 0;
93 static int bn_limit_num_mont = 8;   /* (1<<bn_limit_bits_mont) */
94 
95 void
BN_set_params(int mult,int high,int low,int mont)96 BN_set_params(int mult, int high, int low, int mont)
97 {
98 	if (mult >= 0) {
99 		if (mult > (int)(sizeof(int) * 8) - 1)
100 			mult = sizeof(int) * 8 - 1;
101 		bn_limit_bits = mult;
102 		bn_limit_num = 1 << mult;
103 	}
104 	if (high >= 0) {
105 		if (high > (int)(sizeof(int) * 8) - 1)
106 			high = sizeof(int) * 8 - 1;
107 		bn_limit_bits_high = high;
108 		bn_limit_num_high = 1 << high;
109 	}
110 	if (low >= 0) {
111 		if (low > (int)(sizeof(int) * 8) - 1)
112 			low = sizeof(int) * 8 - 1;
113 		bn_limit_bits_low = low;
114 		bn_limit_num_low = 1 << low;
115 	}
116 	if (mont >= 0) {
117 		if (mont > (int)(sizeof(int) * 8) - 1)
118 			mont = sizeof(int) * 8 - 1;
119 		bn_limit_bits_mont = mont;
120 		bn_limit_num_mont = 1 << mont;
121 	}
122 }
123 
124 int
BN_get_params(int which)125 BN_get_params(int which)
126 {
127 	if (which == 0)
128 		return (bn_limit_bits);
129 	else if (which == 1)
130 		return (bn_limit_bits_high);
131 	else if (which == 2)
132 		return (bn_limit_bits_low);
133 	else if (which == 3)
134 		return (bn_limit_bits_mont);
135 	else
136 		return (0);
137 }
138 #endif
139 
140 const BIGNUM *
BN_value_one(void)141 BN_value_one(void)
142 {
143 	static const BN_ULONG data_one = 1L;
144 	static const BIGNUM const_one = {
145 		(BN_ULONG *)&data_one, 1, 1, 0, BN_FLG_STATIC_DATA
146 	};
147 
148 	return (&const_one);
149 }
150 
151 int
BN_num_bits_word(BN_ULONG l)152 BN_num_bits_word(BN_ULONG l)
153 {
154 	BN_ULONG x, mask;
155 	int bits;
156 	unsigned int shift;
157 
158 	/* Constant time calculation of floor(log2(l)) + 1. */
159 	bits = (l != 0);
160 	shift = BN_BITS4;	/* On _LP64 this is 32, otherwise 16. */
161 	do {
162 		x = l >> shift;
163 		/* If x is 0, set mask to 0, otherwise set it to all 1s. */
164 		mask = ((~x & (x - 1)) >> (BN_BITS2 - 1)) - 1;
165 		bits += shift & mask;
166 		/* If x is 0, leave l alone, otherwise set l = x. */
167 		l ^= (x ^ l) & mask;
168 	} while ((shift /= 2) != 0);
169 
170 	return bits;
171 }
172 
173 int
BN_num_bits(const BIGNUM * a)174 BN_num_bits(const BIGNUM *a)
175 {
176 	int i = a->top - 1;
177 
178 	bn_check_top(a);
179 
180 	if (BN_is_zero(a))
181 		return 0;
182 	return ((i * BN_BITS2) + BN_num_bits_word(a->d[i]));
183 }
184 
185 void
BN_clear_free(BIGNUM * a)186 BN_clear_free(BIGNUM *a)
187 {
188 	int i;
189 
190 	if (a == NULL)
191 		return;
192 	bn_check_top(a);
193 	if (a->d != NULL && !(BN_get_flags(a, BN_FLG_STATIC_DATA)))
194 		freezero(a->d, a->dmax * sizeof(a->d[0]));
195 	i = BN_get_flags(a, BN_FLG_MALLOCED);
196 	explicit_bzero(a, sizeof(BIGNUM));
197 	if (i)
198 		free(a);
199 }
200 
201 void
BN_free(BIGNUM * a)202 BN_free(BIGNUM *a)
203 {
204 	BN_clear_free(a);
205 }
206 
207 void
BN_init(BIGNUM * a)208 BN_init(BIGNUM *a)
209 {
210 	memset(a, 0, sizeof(BIGNUM));
211 	bn_check_top(a);
212 }
213 
214 BIGNUM *
BN_new(void)215 BN_new(void)
216 {
217 	BIGNUM *ret;
218 
219 	if ((ret = malloc(sizeof(BIGNUM))) == NULL) {
220 		BNerror(ERR_R_MALLOC_FAILURE);
221 		return (NULL);
222 	}
223 	ret->flags = BN_FLG_MALLOCED;
224 	ret->top = 0;
225 	ret->neg = 0;
226 	ret->dmax = 0;
227 	ret->d = NULL;
228 	bn_check_top(ret);
229 	return (ret);
230 }
231 
232 /* This is used both by bn_expand2() and bn_dup_expand() */
233 /* The caller MUST check that words > b->dmax before calling this */
234 static BN_ULONG *
bn_expand_internal(const BIGNUM * b,int words)235 bn_expand_internal(const BIGNUM *b, int words)
236 {
237 	BN_ULONG *A, *a = NULL;
238 	const BN_ULONG *B;
239 	int i;
240 
241 	bn_check_top(b);
242 
243 	if (words > (INT_MAX/(4*BN_BITS2))) {
244 		BNerror(BN_R_BIGNUM_TOO_LONG);
245 		return NULL;
246 	}
247 	if (BN_get_flags(b, BN_FLG_STATIC_DATA)) {
248 		BNerror(BN_R_EXPAND_ON_STATIC_BIGNUM_DATA);
249 		return (NULL);
250 	}
251 	a = A = reallocarray(NULL, words, sizeof(BN_ULONG));
252 	if (A == NULL) {
253 		BNerror(ERR_R_MALLOC_FAILURE);
254 		return (NULL);
255 	}
256 #if 1
257 	B = b->d;
258 	/* Check if the previous number needs to be copied */
259 	if (B != NULL) {
260 		for (i = b->top >> 2; i > 0; i--, A += 4, B += 4) {
261 			/*
262 			 * The fact that the loop is unrolled
263 			 * 4-wise is a tribute to Intel. It's
264 			 * the one that doesn't have enough
265 			 * registers to accommodate more data.
266 			 * I'd unroll it 8-wise otherwise:-)
267 			 *
268 			 *		<appro@fy.chalmers.se>
269 			 */
270 			BN_ULONG a0, a1, a2, a3;
271 			a0 = B[0];
272 			a1 = B[1];
273 			a2 = B[2];
274 			a3 = B[3];
275 			A[0] = a0;
276 			A[1] = a1;
277 			A[2] = a2;
278 			A[3] = a3;
279 		}
280 		switch (b->top & 3) {
281 		case 3:
282 			A[2] = B[2];
283 		case 2:
284 			A[1] = B[1];
285 		case 1:
286 			A[0] = B[0];
287 		}
288 	}
289 
290 #else
291 	memset(A, 0, sizeof(BN_ULONG) * words);
292 	memcpy(A, b->d, sizeof(b->d[0]) * b->top);
293 #endif
294 
295 	return (a);
296 }
297 
298 /* This is an internal function that can be used instead of bn_expand2()
299  * when there is a need to copy BIGNUMs instead of only expanding the
300  * data part, while still expanding them.
301  * Especially useful when needing to expand BIGNUMs that are declared
302  * 'const' and should therefore not be changed.
303  * The reason to use this instead of a BN_dup() followed by a bn_expand2()
304  * is memory allocation overhead.  A BN_dup() followed by a bn_expand2()
305  * will allocate new memory for the BIGNUM data twice, and free it once,
306  * while bn_dup_expand() makes sure allocation is made only once.
307  */
308 
309 #ifndef OPENSSL_NO_DEPRECATED
310 BIGNUM *
bn_dup_expand(const BIGNUM * b,int words)311 bn_dup_expand(const BIGNUM *b, int words)
312 {
313 	BIGNUM *r = NULL;
314 
315 	bn_check_top(b);
316 
317 	/* This function does not work if
318 	 *      words <= b->dmax && top < words
319 	 * because BN_dup() does not preserve 'dmax'!
320 	 * (But bn_dup_expand() is not used anywhere yet.)
321 	 */
322 
323 	if (words > b->dmax) {
324 		BN_ULONG *a = bn_expand_internal(b, words);
325 
326 		if (a) {
327 			r = BN_new();
328 			if (r) {
329 				r->top = b->top;
330 				r->dmax = words;
331 				r->neg = b->neg;
332 				r->d = a;
333 			} else {
334 				/* r == NULL, BN_new failure */
335 				free(a);
336 			}
337 		}
338 		/* If a == NULL, there was an error in allocation in
339 		   bn_expand_internal(), and NULL should be returned */
340 	} else {
341 		r = BN_dup(b);
342 	}
343 
344 	bn_check_top(r);
345 	return r;
346 }
347 #endif
348 
349 /* This is an internal function that should not be used in applications.
350  * It ensures that 'b' has enough room for a 'words' word number
351  * and initialises any unused part of b->d with leading zeros.
352  * It is mostly used by the various BIGNUM routines. If there is an error,
353  * NULL is returned. If not, 'b' is returned. */
354 
355 BIGNUM *
bn_expand2(BIGNUM * b,int words)356 bn_expand2(BIGNUM *b, int words)
357 {
358 	bn_check_top(b);
359 
360 	if (words > b->dmax) {
361 		BN_ULONG *a = bn_expand_internal(b, words);
362 		if (!a)
363 			return NULL;
364 		if (b->d)
365 			freezero(b->d, b->dmax * sizeof(b->d[0]));
366 		b->d = a;
367 		b->dmax = words;
368 	}
369 
370 /* None of this should be necessary because of what b->top means! */
371 #if 0
372 	/* NB: bn_wexpand() calls this only if the BIGNUM really has to grow */
373 	if (b->top < b->dmax) {
374 		int i;
375 		BN_ULONG *A = &(b->d[b->top]);
376 		for (i = (b->dmax - b->top) >> 3; i > 0; i--, A += 8) {
377 			A[0] = 0;
378 			A[1] = 0;
379 			A[2] = 0;
380 			A[3] = 0;
381 			A[4] = 0;
382 			A[5] = 0;
383 			A[6] = 0;
384 			A[7] = 0;
385 		}
386 		for (i = (b->dmax - b->top)&7; i > 0; i--, A++)
387 			A[0] = 0;
388 		assert(A == &(b->d[b->dmax]));
389 	}
390 #endif
391 	bn_check_top(b);
392 	return b;
393 }
394 
395 BIGNUM *
BN_dup(const BIGNUM * a)396 BN_dup(const BIGNUM *a)
397 {
398 	BIGNUM *t;
399 
400 	if (a == NULL)
401 		return NULL;
402 	bn_check_top(a);
403 
404 	t = BN_new();
405 	if (t == NULL)
406 		return NULL;
407 	if (!BN_copy(t, a)) {
408 		BN_free(t);
409 		return NULL;
410 	}
411 	bn_check_top(t);
412 	return t;
413 }
414 
415 BIGNUM *
BN_copy(BIGNUM * a,const BIGNUM * b)416 BN_copy(BIGNUM *a, const BIGNUM *b)
417 {
418 	int i;
419 	BN_ULONG *A;
420 	const BN_ULONG *B;
421 
422 	bn_check_top(b);
423 
424 	if (a == b)
425 		return (a);
426 	if (bn_wexpand(a, b->top) == NULL)
427 		return (NULL);
428 
429 #if 1
430 	A = a->d;
431 	B = b->d;
432 	for (i = b->top >> 2; i > 0; i--, A += 4, B += 4) {
433 		BN_ULONG a0, a1, a2, a3;
434 		a0 = B[0];
435 		a1 = B[1];
436 		a2 = B[2];
437 		a3 = B[3];
438 		A[0] = a0;
439 		A[1] = a1;
440 		A[2] = a2;
441 		A[3] = a3;
442 	}
443 	switch (b->top & 3) {
444 	case 3:
445 		A[2] = B[2];
446 	case 2:
447 		A[1] = B[1];
448 	case 1:
449 		A[0] = B[0];
450 	}
451 #else
452 	memcpy(a->d, b->d, sizeof(b->d[0]) * b->top);
453 #endif
454 
455 	a->top = b->top;
456 	a->neg = b->neg;
457 	bn_check_top(a);
458 	return (a);
459 }
460 
461 void
BN_swap(BIGNUM * a,BIGNUM * b)462 BN_swap(BIGNUM *a, BIGNUM *b)
463 {
464 	int flags_old_a, flags_old_b;
465 	BN_ULONG *tmp_d;
466 	int tmp_top, tmp_dmax, tmp_neg;
467 
468 	bn_check_top(a);
469 	bn_check_top(b);
470 
471 	flags_old_a = a->flags;
472 	flags_old_b = b->flags;
473 
474 	tmp_d = a->d;
475 	tmp_top = a->top;
476 	tmp_dmax = a->dmax;
477 	tmp_neg = a->neg;
478 
479 	a->d = b->d;
480 	a->top = b->top;
481 	a->dmax = b->dmax;
482 	a->neg = b->neg;
483 
484 	b->d = tmp_d;
485 	b->top = tmp_top;
486 	b->dmax = tmp_dmax;
487 	b->neg = tmp_neg;
488 
489 	a->flags = (flags_old_a & BN_FLG_MALLOCED) |
490 	    (flags_old_b & BN_FLG_STATIC_DATA);
491 	b->flags = (flags_old_b & BN_FLG_MALLOCED) |
492 	    (flags_old_a & BN_FLG_STATIC_DATA);
493 	bn_check_top(a);
494 	bn_check_top(b);
495 }
496 
497 void
BN_clear(BIGNUM * a)498 BN_clear(BIGNUM *a)
499 {
500 	bn_check_top(a);
501 	if (a->d != NULL)
502 		explicit_bzero(a->d, a->dmax * sizeof(a->d[0]));
503 	a->top = 0;
504 	a->neg = 0;
505 }
506 
507 BN_ULONG
BN_get_word(const BIGNUM * a)508 BN_get_word(const BIGNUM *a)
509 {
510 	if (a->top > 1)
511 		return BN_MASK2;
512 	else if (a->top == 1)
513 		return a->d[0];
514 	/* a->top == 0 */
515 	return 0;
516 }
517 
518 BIGNUM *
bn_expand(BIGNUM * a,int bits)519 bn_expand(BIGNUM *a, int bits)
520 {
521 	if (bits > (INT_MAX - BN_BITS2 + 1))
522 		return (NULL);
523 
524 	if (((bits + BN_BITS2 - 1) / BN_BITS2) <= a->dmax)
525 		return (a);
526 
527 	return bn_expand2(a, (bits + BN_BITS2 - 1) / BN_BITS2);
528 }
529 
530 int
BN_set_word(BIGNUM * a,BN_ULONG w)531 BN_set_word(BIGNUM *a, BN_ULONG w)
532 {
533 	bn_check_top(a);
534 	if (bn_expand(a, (int)sizeof(BN_ULONG) * 8) == NULL)
535 		return (0);
536 	a->neg = 0;
537 	a->d[0] = w;
538 	a->top = (w ? 1 : 0);
539 	bn_check_top(a);
540 	return (1);
541 }
542 
543 BIGNUM *
BN_bin2bn(const unsigned char * s,int len,BIGNUM * ret)544 BN_bin2bn(const unsigned char *s, int len, BIGNUM *ret)
545 {
546 	unsigned int i, m;
547 	unsigned int n;
548 	BN_ULONG l;
549 	BIGNUM *bn = NULL;
550 
551 	if (len < 0)
552 		return (NULL);
553 	if (ret == NULL)
554 		ret = bn = BN_new();
555 	if (ret == NULL)
556 		return (NULL);
557 	bn_check_top(ret);
558 	l = 0;
559 	n = len;
560 	if (n == 0) {
561 		ret->top = 0;
562 		return (ret);
563 	}
564 	i = ((n - 1) / BN_BYTES) + 1;
565 	m = ((n - 1) % (BN_BYTES));
566 	if (bn_wexpand(ret, (int)i) == NULL) {
567 		BN_free(bn);
568 		return NULL;
569 	}
570 	ret->top = i;
571 	ret->neg = 0;
572 	while (n--) {
573 		l = (l << 8L) | *(s++);
574 		if (m-- == 0) {
575 			ret->d[--i] = l;
576 			l = 0;
577 			m = BN_BYTES - 1;
578 		}
579 	}
580 	/* need to call this due to clear byte at top if avoiding
581 	 * having the top bit set (-ve number) */
582 	bn_correct_top(ret);
583 	return (ret);
584 }
585 
586 typedef enum {
587 	big,
588 	little,
589 } endianness_t;
590 
591 /* ignore negative */
592 static int
bn2binpad(const BIGNUM * a,unsigned char * to,int tolen,endianness_t endianness)593 bn2binpad(const BIGNUM *a, unsigned char *to, int tolen, endianness_t endianness)
594 {
595 	int n;
596 	size_t i, lasti, j, atop, mask;
597 	BN_ULONG l;
598 
599 	/*
600 	 * In case |a| is fixed-top, BN_num_bytes can return bogus length,
601 	 * but it's assumed that fixed-top inputs ought to be "nominated"
602 	 * even for padded output, so it works out...
603 	 */
604 	n = BN_num_bytes(a);
605 	if (tolen == -1)
606 		tolen = n;
607 	else if (tolen < n) {	/* uncommon/unlike case */
608 		BIGNUM temp = *a;
609 
610 		bn_correct_top(&temp);
611 
612 		n = BN_num_bytes(&temp);
613 		if (tolen < n)
614 			return -1;
615 	}
616 
617 	/* Swipe through whole available data and don't give away padded zero. */
618 	atop = a->dmax * BN_BYTES;
619 	if (atop == 0) {
620 		explicit_bzero(to, tolen);
621 		return tolen;
622 	}
623 
624 	lasti = atop - 1;
625 	atop = a->top * BN_BYTES;
626 
627 	if (endianness == big)
628 		to += tolen; /* start from the end of the buffer */
629 
630 	for (i = 0, j = 0; j < (size_t)tolen; j++) {
631 		unsigned char val;
632 
633 		l = a->d[i / BN_BYTES];
634 		mask = 0 - ((j - atop) >> (8 * sizeof(i) - 1));
635 		val = (unsigned char)(l >> (8 * (i % BN_BYTES)) & mask);
636 
637 		if (endianness == big)
638 			*--to = val;
639 		else
640 			*to++ = val;
641 
642 		i += (i - lasti) >> (8 * sizeof(i) - 1); /* stay on last limb */
643 	}
644 
645 	return tolen;
646 }
647 
648 int
BN_bn2binpad(const BIGNUM * a,unsigned char * to,int tolen)649 BN_bn2binpad(const BIGNUM *a, unsigned char *to, int tolen)
650 {
651 	if (tolen < 0)
652 		return -1;
653 	return bn2binpad(a, to, tolen, big);
654 }
655 
656 int
BN_bn2bin(const BIGNUM * a,unsigned char * to)657 BN_bn2bin(const BIGNUM *a, unsigned char *to)
658 {
659 	return bn2binpad(a, to, -1, big);
660 }
661 
662 BIGNUM *
BN_lebin2bn(const unsigned char * s,int len,BIGNUM * ret)663 BN_lebin2bn(const unsigned char *s, int len, BIGNUM *ret)
664 {
665 	unsigned int i, m, n;
666 	BN_ULONG l;
667 	BIGNUM *bn = NULL;
668 
669 	if (ret == NULL)
670 		ret = bn = BN_new();
671 	if (ret == NULL)
672 		return NULL;
673 
674 	bn_check_top(ret);
675 
676 	s += len;
677 	/* Skip trailing zeroes. */
678 	for (; len > 0 && s[-1] == 0; s--, len--)
679 		continue;
680 
681 	n = len;
682 	if (n == 0) {
683 		ret->top = 0;
684 		return ret;
685 	}
686 
687 	i = ((n - 1) / BN_BYTES) + 1;
688 	m = (n - 1) % BN_BYTES;
689 	if (bn_wexpand(ret, (int)i) == NULL) {
690 		BN_free(bn);
691 		return NULL;
692 	}
693 
694 	ret->top = i;
695 	ret->neg = 0;
696 	l = 0;
697 	while (n-- > 0) {
698 		s--;
699 		l = (l << 8L) | *s;
700 		if (m-- == 0) {
701 			ret->d[--i] = l;
702 			l = 0;
703 			m = BN_BYTES - 1;
704 		}
705 	}
706 
707 	/*
708 	 * need to call this due to clear byte at top if avoiding having the
709 	 * top bit set (-ve number)
710 	 */
711 	bn_correct_top(ret);
712 
713 	return ret;
714 }
715 
716 int
BN_bn2lebinpad(const BIGNUM * a,unsigned char * to,int tolen)717 BN_bn2lebinpad(const BIGNUM *a, unsigned char *to, int tolen)
718 {
719 	if (tolen < 0)
720 		return -1;
721 
722 	return bn2binpad(a, to, tolen, little);
723 }
724 
725 int
BN_ucmp(const BIGNUM * a,const BIGNUM * b)726 BN_ucmp(const BIGNUM *a, const BIGNUM *b)
727 {
728 	int i;
729 	BN_ULONG t1, t2, *ap, *bp;
730 
731 	bn_check_top(a);
732 	bn_check_top(b);
733 
734 	i = a->top - b->top;
735 	if (i != 0)
736 		return (i);
737 	ap = a->d;
738 	bp = b->d;
739 	for (i = a->top - 1; i >= 0; i--) {
740 		t1 = ap[i];
741 		t2 = bp[i];
742 		if (t1 != t2)
743 			return ((t1 > t2) ? 1 : -1);
744 	}
745 	return (0);
746 }
747 
748 int
BN_cmp(const BIGNUM * a,const BIGNUM * b)749 BN_cmp(const BIGNUM *a, const BIGNUM *b)
750 {
751 	int i;
752 	int gt, lt;
753 	BN_ULONG t1, t2;
754 
755 	if ((a == NULL) || (b == NULL)) {
756 		if (a != NULL)
757 			return (-1);
758 		else if (b != NULL)
759 			return (1);
760 		else
761 			return (0);
762 	}
763 
764 	bn_check_top(a);
765 	bn_check_top(b);
766 
767 	if (a->neg != b->neg) {
768 		if (a->neg)
769 			return (-1);
770 		else
771 			return (1);
772 	}
773 	if (a->neg == 0) {
774 		gt = 1;
775 		lt = -1;
776 	} else {
777 		gt = -1;
778 		lt = 1;
779 	}
780 
781 	if (a->top > b->top)
782 		return (gt);
783 	if (a->top < b->top)
784 		return (lt);
785 	for (i = a->top - 1; i >= 0; i--) {
786 		t1 = a->d[i];
787 		t2 = b->d[i];
788 		if (t1 > t2)
789 			return (gt);
790 		if (t1 < t2)
791 			return (lt);
792 	}
793 	return (0);
794 }
795 
796 int
BN_set_bit(BIGNUM * a,int n)797 BN_set_bit(BIGNUM *a, int n)
798 {
799 	int i, j, k;
800 
801 	if (n < 0)
802 		return 0;
803 
804 	i = n / BN_BITS2;
805 	j = n % BN_BITS2;
806 	if (a->top <= i) {
807 		if (bn_wexpand(a, i + 1) == NULL)
808 			return (0);
809 		for (k = a->top; k < i + 1; k++)
810 			a->d[k] = 0;
811 		a->top = i + 1;
812 	}
813 
814 	a->d[i] |= (((BN_ULONG)1) << j);
815 	bn_check_top(a);
816 	return (1);
817 }
818 
819 int
BN_clear_bit(BIGNUM * a,int n)820 BN_clear_bit(BIGNUM *a, int n)
821 {
822 	int i, j;
823 
824 	bn_check_top(a);
825 	if (n < 0)
826 		return 0;
827 
828 	i = n / BN_BITS2;
829 	j = n % BN_BITS2;
830 	if (a->top <= i)
831 		return (0);
832 
833 	a->d[i] &= (~(((BN_ULONG)1) << j));
834 	bn_correct_top(a);
835 	return (1);
836 }
837 
838 int
BN_is_bit_set(const BIGNUM * a,int n)839 BN_is_bit_set(const BIGNUM *a, int n)
840 {
841 	int i, j;
842 
843 	bn_check_top(a);
844 	if (n < 0)
845 		return 0;
846 	i = n / BN_BITS2;
847 	j = n % BN_BITS2;
848 	if (a->top <= i)
849 		return 0;
850 	return (int)(((a->d[i]) >> j) & ((BN_ULONG)1));
851 }
852 
853 int
BN_mask_bits(BIGNUM * a,int n)854 BN_mask_bits(BIGNUM *a, int n)
855 {
856 	int b, w;
857 
858 	bn_check_top(a);
859 	if (n < 0)
860 		return 0;
861 
862 	w = n / BN_BITS2;
863 	b = n % BN_BITS2;
864 	if (w >= a->top)
865 		return 0;
866 	if (b == 0)
867 		a->top = w;
868 	else {
869 		a->top = w + 1;
870 		a->d[w] &= ~(BN_MASK2 << b);
871 	}
872 	bn_correct_top(a);
873 	return (1);
874 }
875 
876 void
BN_set_negative(BIGNUM * a,int b)877 BN_set_negative(BIGNUM *a, int b)
878 {
879 	if (b && !BN_is_zero(a))
880 		a->neg = 1;
881 	else
882 		a->neg = 0;
883 }
884 
885 int
bn_cmp_words(const BN_ULONG * a,const BN_ULONG * b,int n)886 bn_cmp_words(const BN_ULONG *a, const BN_ULONG *b, int n)
887 {
888 	int i;
889 	BN_ULONG aa, bb;
890 
891 	aa = a[n - 1];
892 	bb = b[n - 1];
893 	if (aa != bb)
894 		return ((aa > bb) ? 1 : -1);
895 	for (i = n - 2; i >= 0; i--) {
896 		aa = a[i];
897 		bb = b[i];
898 		if (aa != bb)
899 			return ((aa > bb) ? 1 : -1);
900 	}
901 	return (0);
902 }
903 
904 /* Here follows a specialised variants of bn_cmp_words().  It has the
905    property of performing the operation on arrays of different sizes.
906    The sizes of those arrays is expressed through cl, which is the
907    common length ( basicall, min(len(a),len(b)) ), and dl, which is the
908    delta between the two lengths, calculated as len(a)-len(b).
909    All lengths are the number of BN_ULONGs...  */
910 
911 int
bn_cmp_part_words(const BN_ULONG * a,const BN_ULONG * b,int cl,int dl)912 bn_cmp_part_words(const BN_ULONG *a, const BN_ULONG *b, int cl, int dl)
913 {
914 	int n, i;
915 
916 	n = cl - 1;
917 
918 	if (dl < 0) {
919 		for (i = dl; i < 0; i++) {
920 			if (b[n - i] != 0)
921 				return -1; /* a < b */
922 		}
923 	}
924 	if (dl > 0) {
925 		for (i = dl; i > 0; i--) {
926 			if (a[n + i] != 0)
927 				return 1; /* a > b */
928 		}
929 	}
930 	return bn_cmp_words(a, b, cl);
931 }
932 
933 /*
934  * Constant-time conditional swap of a and b.
935  * a and b are swapped if condition is not 0.
936  * The code assumes that at most one bit of condition is set.
937  * nwords is the number of words to swap.
938  * The code assumes that at least nwords are allocated in both a and b,
939  * and that no more than nwords are used by either a or b.
940  * a and b cannot be the same number
941  */
942 void
BN_consttime_swap(BN_ULONG condition,BIGNUM * a,BIGNUM * b,int nwords)943 BN_consttime_swap(BN_ULONG condition, BIGNUM *a, BIGNUM *b, int nwords)
944 {
945 	BN_ULONG t;
946 	int i;
947 
948 	bn_wcheck_size(a, nwords);
949 	bn_wcheck_size(b, nwords);
950 
951 	assert(a != b);
952 	assert((condition & (condition - 1)) == 0);
953 	assert(sizeof(BN_ULONG) >= sizeof(int));
954 
955 	condition = ((condition - 1) >> (BN_BITS2 - 1)) - 1;
956 
957 	t = (a->top^b->top) & condition;
958 	a->top ^= t;
959 	b->top ^= t;
960 
961 #define BN_CONSTTIME_SWAP(ind) \
962 	do { \
963 		t = (a->d[ind] ^ b->d[ind]) & condition; \
964 		a->d[ind] ^= t; \
965 		b->d[ind] ^= t; \
966 	} while (0)
967 
968 
969 	switch (nwords) {
970 	default:
971 		for (i = 10; i < nwords; i++)
972 			BN_CONSTTIME_SWAP(i);
973 		/* Fallthrough */
974 	case 10: BN_CONSTTIME_SWAP(9); /* Fallthrough */
975 	case 9: BN_CONSTTIME_SWAP(8); /* Fallthrough */
976 	case 8: BN_CONSTTIME_SWAP(7); /* Fallthrough */
977 	case 7: BN_CONSTTIME_SWAP(6); /* Fallthrough */
978 	case 6: BN_CONSTTIME_SWAP(5); /* Fallthrough */
979 	case 5: BN_CONSTTIME_SWAP(4); /* Fallthrough */
980 	case 4: BN_CONSTTIME_SWAP(3); /* Fallthrough */
981 	case 3: BN_CONSTTIME_SWAP(2); /* Fallthrough */
982 	case 2: BN_CONSTTIME_SWAP(1); /* Fallthrough */
983 	case 1:
984 		BN_CONSTTIME_SWAP(0);
985 	}
986 #undef BN_CONSTTIME_SWAP
987 }
988 
989 /*
990  * Constant-time conditional swap of a and b.
991  * a and b are swapped if condition is not 0.
992  * nwords is the number of words to swap.
993  */
994 int
BN_swap_ct(BN_ULONG condition,BIGNUM * a,BIGNUM * b,size_t nwords)995 BN_swap_ct(BN_ULONG condition, BIGNUM *a, BIGNUM *b, size_t nwords)
996 {
997 	BN_ULONG t;
998 	int i, words;
999 
1000 	if (a == b)
1001 		return 1;
1002 	if (nwords > INT_MAX)
1003 		return 0;
1004 	words = (int)nwords;
1005 	if (bn_wexpand(a, words) == NULL || bn_wexpand(b, words) == NULL)
1006 		return 0;
1007 	if (a->top > words || b->top > words) {
1008 		BNerror(BN_R_INVALID_LENGTH);
1009 		return 0;
1010 	}
1011 
1012 	/* Set condition to 0 (if it was zero) or all 1s otherwise. */
1013 	condition = ((~condition & (condition - 1)) >> (BN_BITS2 - 1)) - 1;
1014 
1015 	/* swap top field */
1016 	t = (a->top ^ b->top) & condition;
1017 	a->top ^= t;
1018 	b->top ^= t;
1019 
1020 	/* swap neg field */
1021 	t = (a->neg ^ b->neg) & condition;
1022 	a->neg ^= t;
1023 	b->neg ^= t;
1024 
1025 	/* swap BN_FLG_CONSTTIME from flag field */
1026 	t = ((a->flags ^ b->flags) & BN_FLG_CONSTTIME) & condition;
1027 	a->flags ^= t;
1028 	b->flags ^= t;
1029 
1030 	/* swap the data */
1031 	for (i = 0; i < words; i++) {
1032 		t = (a->d[i] ^ b->d[i]) & condition;
1033 		a->d[i] ^= t;
1034 		b->d[i] ^= t;
1035 	}
1036 
1037 	return 1;
1038 }
1039 
1040 BN_GENCB *
BN_GENCB_new(void)1041 BN_GENCB_new(void)
1042 {
1043 	BN_GENCB *cb;
1044 
1045 	if ((cb = calloc(1, sizeof(*cb))) == NULL)
1046 		return NULL;
1047 
1048 	return cb;
1049 }
1050 
1051 void
BN_GENCB_free(BN_GENCB * cb)1052 BN_GENCB_free(BN_GENCB *cb)
1053 {
1054 	if (cb == NULL)
1055 		return;
1056 	free(cb);
1057 }
1058 
1059 void *
BN_GENCB_get_arg(BN_GENCB * cb)1060 BN_GENCB_get_arg(BN_GENCB *cb)
1061 {
1062 	return cb->arg;
1063 }
1064