2 * Copyright 1995-2018 The OpenSSL Project Authors. All Rights Reserved.
4 * Licensed under the OpenSSL license (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
12 #include "internal/cryptlib.h"
14 #include <openssl/opensslconf.h>
16 /* This stuff appears to be completely unused, so is deprecated */
17 #if OPENSSL_API_COMPAT < 0x00908000L
19 * For a 32 bit machine
28 static int bn_limit_bits = 0;
29 static int bn_limit_num = 8; /* (1<<bn_limit_bits) */
30 static int bn_limit_bits_low = 0;
31 static int bn_limit_num_low = 8; /* (1<<bn_limit_bits_low) */
32 static int bn_limit_bits_high = 0;
33 static int bn_limit_num_high = 8; /* (1<<bn_limit_bits_high) */
34 static int bn_limit_bits_mont = 0;
35 static int bn_limit_num_mont = 8; /* (1<<bn_limit_bits_mont) */
37 void BN_set_params(int mult, int high, int low, int mont)
40 if (mult > (int)(sizeof(int) * 8) - 1)
41 mult = sizeof(int) * 8 - 1;
43 bn_limit_num = 1 << mult;
46 if (high > (int)(sizeof(int) * 8) - 1)
47 high = sizeof(int) * 8 - 1;
48 bn_limit_bits_high = high;
49 bn_limit_num_high = 1 << high;
52 if (low > (int)(sizeof(int) * 8) - 1)
53 low = sizeof(int) * 8 - 1;
54 bn_limit_bits_low = low;
55 bn_limit_num_low = 1 << low;
58 if (mont > (int)(sizeof(int) * 8) - 1)
59 mont = sizeof(int) * 8 - 1;
60 bn_limit_bits_mont = mont;
61 bn_limit_num_mont = 1 << mont;
65 int BN_get_params(int which)
70 return bn_limit_bits_high;
72 return bn_limit_bits_low;
74 return bn_limit_bits_mont;
80 const BIGNUM *BN_value_one(void)
82 static const BN_ULONG data_one = 1L;
83 static const BIGNUM const_one =
84 { (BN_ULONG *)&data_one, 1, 1, 0, BN_FLG_STATIC_DATA };
89 int BN_num_bits_word(BN_ULONG l)
91 static const unsigned char bits[256] = {
92 0, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4,
93 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
94 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
95 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
96 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
97 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
98 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
99 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
100 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
101 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
102 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
103 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
104 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
105 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
106 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
107 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
110 #if defined(SIXTY_FOUR_BIT_LONG)
111 if (l & 0xffffffff00000000L) {
112 if (l & 0xffff000000000000L) {
113 if (l & 0xff00000000000000L) {
114 return (bits[(int)(l >> 56)] + 56);
116 return (bits[(int)(l >> 48)] + 48);
118 if (l & 0x0000ff0000000000L) {
119 return (bits[(int)(l >> 40)] + 40);
121 return (bits[(int)(l >> 32)] + 32);
125 # ifdef SIXTY_FOUR_BIT
126 if (l & 0xffffffff00000000LL) {
127 if (l & 0xffff000000000000LL) {
128 if (l & 0xff00000000000000LL) {
129 return (bits[(int)(l >> 56)] + 56);
131 return (bits[(int)(l >> 48)] + 48);
133 if (l & 0x0000ff0000000000LL) {
134 return (bits[(int)(l >> 40)] + 40);
136 return (bits[(int)(l >> 32)] + 32);
142 #if defined(THIRTY_TWO_BIT) || defined(SIXTY_FOUR_BIT) || defined(SIXTY_FOUR_BIT_LONG)
143 if (l & 0xffff0000L) {
145 return (bits[(int)(l >> 24L)] + 24);
147 return (bits[(int)(l >> 16L)] + 16);
151 #if defined(THIRTY_TWO_BIT) || defined(SIXTY_FOUR_BIT) || defined(SIXTY_FOUR_BIT_LONG)
153 return (bits[(int)(l >> 8)] + 8);
156 return (bits[(int)(l)]);
161 int BN_num_bits(const BIGNUM *a)
168 return ((i * BN_BITS2) + BN_num_bits_word(a->d[i]));
171 static void bn_free_d(BIGNUM *a)
173 if (BN_get_flags(a, BN_FLG_SECURE))
174 OPENSSL_secure_free(a->d);
180 void BN_clear_free(BIGNUM *a)
184 if (a->d != NULL && !BN_get_flags(a, BN_FLG_STATIC_DATA)) {
185 OPENSSL_cleanse(a->d, a->dmax * sizeof(a->d[0]));
188 if (BN_get_flags(a, BN_FLG_MALLOCED)) {
189 OPENSSL_cleanse(a, sizeof(*a));
194 void BN_free(BIGNUM *a)
198 if (!BN_get_flags(a, BN_FLG_STATIC_DATA))
200 if (a->flags & BN_FLG_MALLOCED)
204 void bn_init(BIGNUM *a)
216 if ((ret = OPENSSL_zalloc(sizeof(*ret))) == NULL) {
217 BNerr(BN_F_BN_NEW, ERR_R_MALLOC_FAILURE);
220 ret->flags = BN_FLG_MALLOCED;
225 BIGNUM *BN_secure_new(void)
227 BIGNUM *ret = BN_new();
229 ret->flags |= BN_FLG_SECURE;
233 /* This is used by bn_expand2() */
234 /* The caller MUST check that words > b->dmax before calling this */
235 static BN_ULONG *bn_expand_internal(const BIGNUM *b, int words)
241 if (words > (INT_MAX / (4 * BN_BITS2))) {
242 BNerr(BN_F_BN_EXPAND_INTERNAL, BN_R_BIGNUM_TOO_LONG);
245 if (BN_get_flags(b, BN_FLG_STATIC_DATA)) {
246 BNerr(BN_F_BN_EXPAND_INTERNAL, BN_R_EXPAND_ON_STATIC_BIGNUM_DATA);
249 if (BN_get_flags(b, BN_FLG_SECURE))
250 a = OPENSSL_secure_zalloc(words * sizeof(*a));
252 a = OPENSSL_zalloc(words * sizeof(*a));
254 BNerr(BN_F_BN_EXPAND_INTERNAL, ERR_R_MALLOC_FAILURE);
258 assert(b->top <= words);
260 memcpy(a, b->d, sizeof(*a) * b->top);
266 * This is an internal function that should not be used in applications. It
267 * ensures that 'b' has enough room for a 'words' word number and initialises
268 * any unused part of b->d with leading zeros. It is mostly used by the
269 * various BIGNUM routines. If there is an error, NULL is returned. If not,
273 BIGNUM *bn_expand2(BIGNUM *b, int words)
277 if (words > b->dmax) {
278 BN_ULONG *a = bn_expand_internal(b, words);
282 OPENSSL_cleanse(b->d, b->dmax * sizeof(b->d[0]));
293 BIGNUM *BN_dup(const BIGNUM *a)
301 t = BN_get_flags(a, BN_FLG_SECURE) ? BN_secure_new() : BN_new();
304 if (!BN_copy(t, a)) {
312 BIGNUM *BN_copy(BIGNUM *a, const BIGNUM *b)
318 if (bn_wexpand(a, b->top) == NULL)
322 memcpy(a->d, b->d, sizeof(b->d[0]) * b->top);
330 void BN_swap(BIGNUM *a, BIGNUM *b)
332 int flags_old_a, flags_old_b;
334 int tmp_top, tmp_dmax, tmp_neg;
339 flags_old_a = a->flags;
340 flags_old_b = b->flags;
358 (flags_old_a & BN_FLG_MALLOCED) | (flags_old_b & BN_FLG_STATIC_DATA);
360 (flags_old_b & BN_FLG_MALLOCED) | (flags_old_a & BN_FLG_STATIC_DATA);
365 void BN_clear(BIGNUM *a)
369 OPENSSL_cleanse(a->d, sizeof(*a->d) * a->dmax);
374 BN_ULONG BN_get_word(const BIGNUM *a)
378 else if (a->top == 1)
384 int BN_set_word(BIGNUM *a, BN_ULONG w)
387 if (bn_expand(a, (int)sizeof(BN_ULONG) * 8) == NULL)
391 a->top = (w ? 1 : 0);
396 BIGNUM *BN_bin2bn(const unsigned char *s, int len, BIGNUM *ret)
408 /* Skip leading zero's. */
409 for ( ; len > 0 && *s == 0; s++, len--)
416 i = ((n - 1) / BN_BYTES) + 1;
417 m = ((n - 1) % (BN_BYTES));
418 if (bn_wexpand(ret, (int)i) == NULL) {
426 l = (l << 8L) | *(s++);
434 * need to call this due to clear byte at top if avoiding having the top
435 * bit set (-ve number)
441 /* ignore negative */
442 static int bn2binpad(const BIGNUM *a, unsigned char *to, int tolen)
453 /* Add leading zeroes if necessary */
455 memset(to, 0, tolen - i);
459 l = a->d[i / BN_BYTES];
460 *(to++) = (unsigned char)(l >> (8 * (i % BN_BYTES))) & 0xff;
465 int BN_bn2binpad(const BIGNUM *a, unsigned char *to, int tolen)
469 return bn2binpad(a, to, tolen);
472 int BN_bn2bin(const BIGNUM *a, unsigned char *to)
474 return bn2binpad(a, to, -1);
477 BIGNUM *BN_lebin2bn(const unsigned char *s, int len, BIGNUM *ret)
490 /* Skip trailing zeroes. */
491 for ( ; len > 0 && s[-1] == 0; s--, len--)
498 i = ((n - 1) / BN_BYTES) + 1;
499 m = ((n - 1) % (BN_BYTES));
500 if (bn_wexpand(ret, (int)i) == NULL) {
517 * need to call this due to clear byte at top if avoiding having the top
518 * bit set (-ve number)
524 int BN_bn2lebinpad(const BIGNUM *a, unsigned char *to, int tolen)
532 /* Add trailing zeroes if necessary */
534 memset(to + i, 0, tolen - i);
537 l = a->d[i / BN_BYTES];
539 *to = (unsigned char)(l >> (8 * (i % BN_BYTES))) & 0xff;
544 int BN_ucmp(const BIGNUM *a, const BIGNUM *b)
547 BN_ULONG t1, t2, *ap, *bp;
557 for (i = a->top - 1; i >= 0; i--) {
561 return ((t1 > t2) ? 1 : -1);
566 int BN_cmp(const BIGNUM *a, const BIGNUM *b)
572 if ((a == NULL) || (b == NULL)) {
584 if (a->neg != b->neg) {
602 for (i = a->top - 1; i >= 0; i--) {
613 int BN_set_bit(BIGNUM *a, int n)
623 if (bn_wexpand(a, i + 1) == NULL)
625 for (k = a->top; k < i + 1; k++)
630 a->d[i] |= (((BN_ULONG)1) << j);
635 int BN_clear_bit(BIGNUM *a, int n)
648 a->d[i] &= (~(((BN_ULONG)1) << j));
653 int BN_is_bit_set(const BIGNUM *a, int n)
664 return (int)(((a->d[i]) >> j) & ((BN_ULONG)1));
667 int BN_mask_bits(BIGNUM *a, int n)
683 a->d[w] &= ~(BN_MASK2 << b);
689 void BN_set_negative(BIGNUM *a, int b)
691 if (b && !BN_is_zero(a))
697 int bn_cmp_words(const BN_ULONG *a, const BN_ULONG *b, int n)
705 return ((aa > bb) ? 1 : -1);
706 for (i = n - 2; i >= 0; i--) {
710 return ((aa > bb) ? 1 : -1);
716 * Here follows a specialised variants of bn_cmp_words(). It has the
717 * capability of performing the operation on arrays of different sizes. The
718 * sizes of those arrays is expressed through cl, which is the common length
719 * ( basically, min(len(a),len(b)) ), and dl, which is the delta between the
720 * two lengths, calculated as len(a)-len(b). All lengths are the number of
724 int bn_cmp_part_words(const BN_ULONG *a, const BN_ULONG *b, int cl, int dl)
730 for (i = dl; i < 0; i++) {
732 return -1; /* a < b */
736 for (i = dl; i > 0; i--) {
738 return 1; /* a > b */
741 return bn_cmp_words(a, b, cl);
745 * Constant-time conditional swap of a and b.
746 * a and b are swapped if condition is not 0. The code assumes that at most one bit of condition is set.
747 * nwords is the number of words to swap. The code assumes that at least nwords are allocated in both a and b,
748 * and that no more than nwords are used by either a or b.
749 * a and b cannot be the same number
751 void BN_consttime_swap(BN_ULONG condition, BIGNUM *a, BIGNUM *b, int nwords)
756 bn_wcheck_size(a, nwords);
757 bn_wcheck_size(b, nwords);
760 assert((condition & (condition - 1)) == 0);
761 assert(sizeof(BN_ULONG) >= sizeof(int));
763 condition = ((condition - 1) >> (BN_BITS2 - 1)) - 1;
765 t = (a->top ^ b->top) & condition;
769 #define BN_CONSTTIME_SWAP(ind) \
771 t = (a->d[ind] ^ b->d[ind]) & condition; \
778 for (i = 10; i < nwords; i++)
779 BN_CONSTTIME_SWAP(i);
782 BN_CONSTTIME_SWAP(9); /* Fallthrough */
784 BN_CONSTTIME_SWAP(8); /* Fallthrough */
786 BN_CONSTTIME_SWAP(7); /* Fallthrough */
788 BN_CONSTTIME_SWAP(6); /* Fallthrough */
790 BN_CONSTTIME_SWAP(5); /* Fallthrough */
792 BN_CONSTTIME_SWAP(4); /* Fallthrough */
794 BN_CONSTTIME_SWAP(3); /* Fallthrough */
796 BN_CONSTTIME_SWAP(2); /* Fallthrough */
798 BN_CONSTTIME_SWAP(1); /* Fallthrough */
800 BN_CONSTTIME_SWAP(0);
802 #undef BN_CONSTTIME_SWAP
805 /* Bits of security, see SP800-57 */
807 int BN_security_bits(int L, int N)
827 return bits >= secbits ? secbits : bits;
830 void BN_zero_ex(BIGNUM *a)
836 int BN_abs_is_word(const BIGNUM *a, const BN_ULONG w)
838 return ((a->top == 1) && (a->d[0] == w)) || ((w == 0) && (a->top == 0));
841 int BN_is_zero(const BIGNUM *a)
846 int BN_is_one(const BIGNUM *a)
848 return BN_abs_is_word(a, 1) && !a->neg;
851 int BN_is_word(const BIGNUM *a, const BN_ULONG w)
853 return BN_abs_is_word(a, w) && (!w || !a->neg);
856 int BN_is_odd(const BIGNUM *a)
858 return (a->top > 0) && (a->d[0] & 1);
861 int BN_is_negative(const BIGNUM *a)
863 return (a->neg != 0);
866 int BN_to_montgomery(BIGNUM *r, const BIGNUM *a, BN_MONT_CTX *mont,
869 return BN_mod_mul_montgomery(r, a, &(mont->RR), mont, ctx);
872 void BN_with_flags(BIGNUM *dest, const BIGNUM *b, int flags)
876 dest->dmax = b->dmax;
878 dest->flags = ((dest->flags & BN_FLG_MALLOCED)
879 | (b->flags & ~BN_FLG_MALLOCED)
880 | BN_FLG_STATIC_DATA | flags);
883 BN_GENCB *BN_GENCB_new(void)
887 if ((ret = OPENSSL_malloc(sizeof(*ret))) == NULL) {
888 BNerr(BN_F_BN_GENCB_NEW, ERR_R_MALLOC_FAILURE);
895 void BN_GENCB_free(BN_GENCB *cb)
902 void BN_set_flags(BIGNUM *b, int n)
907 int BN_get_flags(const BIGNUM *b, int n)
912 /* Populate a BN_GENCB structure with an "old"-style callback */
913 void BN_GENCB_set_old(BN_GENCB *gencb, void (*callback) (int, int, void *),
916 BN_GENCB *tmp_gencb = gencb;
918 tmp_gencb->arg = cb_arg;
919 tmp_gencb->cb.cb_1 = callback;
922 /* Populate a BN_GENCB structure with a "new"-style callback */
923 void BN_GENCB_set(BN_GENCB *gencb, int (*callback) (int, int, BN_GENCB *),
926 BN_GENCB *tmp_gencb = gencb;
928 tmp_gencb->arg = cb_arg;
929 tmp_gencb->cb.cb_2 = callback;
932 void *BN_GENCB_get_arg(BN_GENCB *cb)
937 BIGNUM *bn_wexpand(BIGNUM *a, int words)
939 return (words <= a->dmax) ? a : bn_expand2(a, words);
942 void bn_correct_top(BIGNUM *a)
945 int tmp_top = a->top;
948 for (ftl = &(a->d[tmp_top]); tmp_top > 0; tmp_top--) {