2 * Copyright 1995-2016 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)
68 return (bn_limit_bits);
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)
188 OPENSSL_cleanse(a->d, a->dmax * sizeof(a->d[0]));
189 if (!BN_get_flags(a, BN_FLG_STATIC_DATA))
192 i = BN_get_flags(a, BN_FLG_MALLOCED);
193 OPENSSL_cleanse(a, sizeof(*a));
198 void BN_free(BIGNUM *a)
203 if (!BN_get_flags(a, BN_FLG_STATIC_DATA))
205 if (a->flags & BN_FLG_MALLOCED)
208 #if OPENSSL_API_COMPAT < 0x00908000L
209 a->flags |= BN_FLG_FREE;
215 void bn_init(BIGNUM *a)
227 if ((ret = OPENSSL_zalloc(sizeof(*ret))) == NULL) {
228 BNerr(BN_F_BN_NEW, ERR_R_MALLOC_FAILURE);
231 ret->flags = BN_FLG_MALLOCED;
236 BIGNUM *BN_secure_new(void)
238 BIGNUM *ret = BN_new();
240 ret->flags |= BN_FLG_SECURE;
244 /* This is used by bn_expand2() */
245 /* The caller MUST check that words > b->dmax before calling this */
246 static BN_ULONG *bn_expand_internal(const BIGNUM *b, int words)
252 if (words > (INT_MAX / (4 * BN_BITS2))) {
253 BNerr(BN_F_BN_EXPAND_INTERNAL, BN_R_BIGNUM_TOO_LONG);
256 if (BN_get_flags(b, BN_FLG_STATIC_DATA)) {
257 BNerr(BN_F_BN_EXPAND_INTERNAL, BN_R_EXPAND_ON_STATIC_BIGNUM_DATA);
260 if (BN_get_flags(b, BN_FLG_SECURE))
261 a = OPENSSL_secure_zalloc(words * sizeof(*a));
263 a = OPENSSL_zalloc(words * sizeof(*a));
265 BNerr(BN_F_BN_EXPAND_INTERNAL, ERR_R_MALLOC_FAILURE);
269 assert(b->top <= words);
271 memcpy(a, b->d, sizeof(*a) * b->top);
277 * This is an internal function that should not be used in applications. It
278 * ensures that 'b' has enough room for a 'words' word number and initialises
279 * any unused part of b->d with leading zeros. It is mostly used by the
280 * various BIGNUM routines. If there is an error, NULL is returned. If not,
284 BIGNUM *bn_expand2(BIGNUM *b, int words)
288 if (words > b->dmax) {
289 BN_ULONG *a = bn_expand_internal(b, words);
293 OPENSSL_cleanse(b->d, b->dmax * sizeof(b->d[0]));
304 BIGNUM *BN_dup(const BIGNUM *a)
312 t = BN_get_flags(a, BN_FLG_SECURE) ? BN_secure_new() : BN_new();
315 if (!BN_copy(t, a)) {
323 BIGNUM *BN_copy(BIGNUM *a, const BIGNUM *b)
329 if (bn_wexpand(a, b->top) == NULL)
333 memcpy(a->d, b->d, sizeof(b->d[0]) * b->top);
341 void BN_swap(BIGNUM *a, BIGNUM *b)
343 int flags_old_a, flags_old_b;
345 int tmp_top, tmp_dmax, tmp_neg;
350 flags_old_a = a->flags;
351 flags_old_b = b->flags;
369 (flags_old_a & BN_FLG_MALLOCED) | (flags_old_b & BN_FLG_STATIC_DATA);
371 (flags_old_b & BN_FLG_MALLOCED) | (flags_old_a & BN_FLG_STATIC_DATA);
376 void BN_clear(BIGNUM *a)
380 OPENSSL_cleanse(a->d, sizeof(*a->d) * a->dmax);
385 BN_ULONG BN_get_word(const BIGNUM *a)
389 else if (a->top == 1)
395 int BN_set_word(BIGNUM *a, BN_ULONG w)
398 if (bn_expand(a, (int)sizeof(BN_ULONG) * 8) == NULL)
402 a->top = (w ? 1 : 0);
407 BIGNUM *BN_bin2bn(const unsigned char *s, int len, BIGNUM *ret)
419 /* Skip leading zero's. */
420 for ( ; len > 0 && *s == 0; s++, len--)
427 i = ((n - 1) / BN_BYTES) + 1;
428 m = ((n - 1) % (BN_BYTES));
429 if (bn_wexpand(ret, (int)i) == NULL) {
437 l = (l << 8L) | *(s++);
445 * need to call this due to clear byte at top if avoiding having the top
446 * bit set (-ve number)
452 /* ignore negative */
453 static int bn2binpad(const BIGNUM *a, unsigned char *to, int tolen)
464 /* Add leading zeroes if necessary */
466 memset(to, 0, tolen - i);
470 l = a->d[i / BN_BYTES];
471 *(to++) = (unsigned char)(l >> (8 * (i % BN_BYTES))) & 0xff;
476 int BN_bn2binpad(const BIGNUM *a, unsigned char *to, int tolen)
480 return bn2binpad(a, to, tolen);
483 int BN_bn2bin(const BIGNUM *a, unsigned char *to)
485 return bn2binpad(a, to, -1);
488 BIGNUM *BN_lebin2bn(const unsigned char *s, int len, BIGNUM *ret)
501 /* Skip trailing zeroes. */
502 for ( ; len > 0 && s[-1] == 0; s--, len--)
509 i = ((n - 1) / BN_BYTES) + 1;
510 m = ((n - 1) % (BN_BYTES));
511 if (bn_wexpand(ret, (int)i) == NULL) {
528 * need to call this due to clear byte at top if avoiding having the top
529 * bit set (-ve number)
535 int BN_bn2lebinpad(const BIGNUM *a, unsigned char *to, int tolen)
543 /* Add trailing zeroes if necessary */
545 memset(to + i, 0, tolen - i);
548 l = a->d[i / BN_BYTES];
550 *to = (unsigned char)(l >> (8 * (i % BN_BYTES))) & 0xff;
555 int BN_ucmp(const BIGNUM *a, const BIGNUM *b)
558 BN_ULONG t1, t2, *ap, *bp;
568 for (i = a->top - 1; i >= 0; i--) {
572 return ((t1 > t2) ? 1 : -1);
577 int BN_cmp(const BIGNUM *a, const BIGNUM *b)
583 if ((a == NULL) || (b == NULL)) {
595 if (a->neg != b->neg) {
613 for (i = a->top - 1; i >= 0; i--) {
624 int BN_set_bit(BIGNUM *a, int n)
634 if (bn_wexpand(a, i + 1) == NULL)
636 for (k = a->top; k < i + 1; k++)
641 a->d[i] |= (((BN_ULONG)1) << j);
646 int BN_clear_bit(BIGNUM *a, int n)
659 a->d[i] &= (~(((BN_ULONG)1) << j));
664 int BN_is_bit_set(const BIGNUM *a, int n)
675 return (int)(((a->d[i]) >> j) & ((BN_ULONG)1));
678 int BN_mask_bits(BIGNUM *a, int n)
694 a->d[w] &= ~(BN_MASK2 << b);
700 void BN_set_negative(BIGNUM *a, int b)
702 if (b && !BN_is_zero(a))
708 int bn_cmp_words(const BN_ULONG *a, const BN_ULONG *b, int n)
716 return ((aa > bb) ? 1 : -1);
717 for (i = n - 2; i >= 0; i--) {
721 return ((aa > bb) ? 1 : -1);
727 * Here follows a specialised variants of bn_cmp_words(). It has the
728 * capability of performing the operation on arrays of different sizes. The
729 * sizes of those arrays is expressed through cl, which is the common length
730 * ( basically, min(len(a),len(b)) ), and dl, which is the delta between the
731 * two lengths, calculated as len(a)-len(b). All lengths are the number of
735 int bn_cmp_part_words(const BN_ULONG *a, const BN_ULONG *b, int cl, int dl)
741 for (i = dl; i < 0; i++) {
743 return -1; /* a < b */
747 for (i = dl; i > 0; i--) {
749 return 1; /* a > b */
752 return bn_cmp_words(a, b, cl);
756 * Constant-time conditional swap of a and b.
757 * a and b are swapped if condition is not 0. The code assumes that at most one bit of condition is set.
758 * nwords is the number of words to swap. The code assumes that at least nwords are allocated in both a and b,
759 * and that no more than nwords are used by either a or b.
760 * a and b cannot be the same number
762 void BN_consttime_swap(BN_ULONG condition, BIGNUM *a, BIGNUM *b, int nwords)
767 bn_wcheck_size(a, nwords);
768 bn_wcheck_size(b, nwords);
771 assert((condition & (condition - 1)) == 0);
772 assert(sizeof(BN_ULONG) >= sizeof(int));
774 condition = ((condition - 1) >> (BN_BITS2 - 1)) - 1;
776 t = (a->top ^ b->top) & condition;
780 #define BN_CONSTTIME_SWAP(ind) \
782 t = (a->d[ind] ^ b->d[ind]) & condition; \
789 for (i = 10; i < nwords; i++)
790 BN_CONSTTIME_SWAP(i);
793 BN_CONSTTIME_SWAP(9); /* Fallthrough */
795 BN_CONSTTIME_SWAP(8); /* Fallthrough */
797 BN_CONSTTIME_SWAP(7); /* Fallthrough */
799 BN_CONSTTIME_SWAP(6); /* Fallthrough */
801 BN_CONSTTIME_SWAP(5); /* Fallthrough */
803 BN_CONSTTIME_SWAP(4); /* Fallthrough */
805 BN_CONSTTIME_SWAP(3); /* Fallthrough */
807 BN_CONSTTIME_SWAP(2); /* Fallthrough */
809 BN_CONSTTIME_SWAP(1); /* Fallthrough */
811 BN_CONSTTIME_SWAP(0);
813 #undef BN_CONSTTIME_SWAP
816 /* Bits of security, see SP800-57 */
818 int BN_security_bits(int L, int N)
838 return bits >= secbits ? secbits : bits;
841 void BN_zero_ex(BIGNUM *a)
847 int BN_abs_is_word(const BIGNUM *a, const BN_ULONG w)
849 return ((a->top == 1) && (a->d[0] == w)) || ((w == 0) && (a->top == 0));
852 int BN_is_zero(const BIGNUM *a)
857 int BN_is_one(const BIGNUM *a)
859 return BN_abs_is_word(a, 1) && !a->neg;
862 int BN_is_word(const BIGNUM *a, const BN_ULONG w)
864 return BN_abs_is_word(a, w) && (!w || !a->neg);
867 int BN_is_odd(const BIGNUM *a)
869 return (a->top > 0) && (a->d[0] & 1);
872 int BN_is_negative(const BIGNUM *a)
874 return (a->neg != 0);
877 int BN_to_montgomery(BIGNUM *r, const BIGNUM *a, BN_MONT_CTX *mont,
880 return BN_mod_mul_montgomery(r, a, &(mont->RR), mont, ctx);
883 void BN_with_flags(BIGNUM *dest, const BIGNUM *b, int flags)
887 dest->dmax = b->dmax;
889 dest->flags = ((dest->flags & BN_FLG_MALLOCED)
890 | (b->flags & ~BN_FLG_MALLOCED)
891 | BN_FLG_STATIC_DATA | flags);
894 BN_GENCB *BN_GENCB_new(void)
898 if ((ret = OPENSSL_malloc(sizeof(*ret))) == NULL) {
899 BNerr(BN_F_BN_GENCB_NEW, ERR_R_MALLOC_FAILURE);
906 void BN_GENCB_free(BN_GENCB *cb)
913 void BN_set_flags(BIGNUM *b, int n)
918 int BN_get_flags(const BIGNUM *b, int n)
923 /* Populate a BN_GENCB structure with an "old"-style callback */
924 void BN_GENCB_set_old(BN_GENCB *gencb, void (*callback) (int, int, void *),
927 BN_GENCB *tmp_gencb = gencb;
929 tmp_gencb->arg = cb_arg;
930 tmp_gencb->cb.cb_1 = callback;
933 /* Populate a BN_GENCB structure with a "new"-style callback */
934 void BN_GENCB_set(BN_GENCB *gencb, int (*callback) (int, int, BN_GENCB *),
937 BN_GENCB *tmp_gencb = gencb;
939 tmp_gencb->arg = cb_arg;
940 tmp_gencb->cb.cb_2 = callback;
943 void *BN_GENCB_get_arg(BN_GENCB *cb)
948 BIGNUM *bn_wexpand(BIGNUM *a, int words)
950 return (words <= a->dmax) ? a : bn_expand2(a, words);
953 void bn_correct_top(BIGNUM *a)
956 int tmp_top = a->top;
959 for (ftl = &(a->d[tmp_top]); tmp_top > 0; tmp_top--) {