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)
248 BN_ULONG *A, *a = NULL;
254 if (words > (INT_MAX / (4 * BN_BITS2))) {
255 BNerr(BN_F_BN_EXPAND_INTERNAL, BN_R_BIGNUM_TOO_LONG);
258 if (BN_get_flags(b, BN_FLG_STATIC_DATA)) {
259 BNerr(BN_F_BN_EXPAND_INTERNAL, BN_R_EXPAND_ON_STATIC_BIGNUM_DATA);
262 if (BN_get_flags(b,BN_FLG_SECURE))
263 a = A = OPENSSL_secure_zalloc(words * sizeof(*a));
265 a = A = OPENSSL_zalloc(words * sizeof(*a));
267 BNerr(BN_F_BN_EXPAND_INTERNAL, ERR_R_MALLOC_FAILURE);
273 /* Check if the previous number needs to be copied */
275 for (i = b->top >> 2; i > 0; i--, A += 4, B += 4) {
277 * The fact that the loop is unrolled
278 * 4-wise is a tribute to Intel. It's
279 * the one that doesn't have enough
280 * registers to accommodate more data.
281 * I'd unroll it 8-wise otherwise:-)
283 * <appro@fy.chalmers.se>
285 BN_ULONG a0, a1, a2, a3;
295 switch (b->top & 3) {
303 /* Without the "case 0" some old optimizers got this wrong. */
308 memset(A, 0, sizeof(*A) * words);
309 memcpy(A, b->d, sizeof(b->d[0]) * b->top);
316 * This is an internal function that should not be used in applications. It
317 * ensures that 'b' has enough room for a 'words' word number and initialises
318 * any unused part of b->d with leading zeros. It is mostly used by the
319 * various BIGNUM routines. If there is an error, NULL is returned. If not,
323 BIGNUM *bn_expand2(BIGNUM *b, int words)
327 if (words > b->dmax) {
328 BN_ULONG *a = bn_expand_internal(b, words);
332 OPENSSL_cleanse(b->d, b->dmax * sizeof(b->d[0]));
343 BIGNUM *BN_dup(const BIGNUM *a)
351 t = BN_get_flags(a, BN_FLG_SECURE) ? BN_secure_new() : BN_new();
354 if (!BN_copy(t, a)) {
362 BIGNUM *BN_copy(BIGNUM *a, const BIGNUM *b)
372 if (bn_wexpand(a, b->top) == NULL)
378 for (i = b->top >> 2; i > 0; i--, A += 4, B += 4) {
379 BN_ULONG a0, a1, a2, a3;
389 /* ultrix cc workaround, see comments in bn_expand_internal */
390 switch (b->top & 3) {
400 memcpy(a->d, b->d, sizeof(b->d[0]) * b->top);
409 void BN_swap(BIGNUM *a, BIGNUM *b)
411 int flags_old_a, flags_old_b;
413 int tmp_top, tmp_dmax, tmp_neg;
418 flags_old_a = a->flags;
419 flags_old_b = b->flags;
437 (flags_old_a & BN_FLG_MALLOCED) | (flags_old_b & BN_FLG_STATIC_DATA);
439 (flags_old_b & BN_FLG_MALLOCED) | (flags_old_a & BN_FLG_STATIC_DATA);
444 void BN_clear(BIGNUM *a)
448 memset(a->d, 0, sizeof(*a->d) * a->dmax);
453 BN_ULONG BN_get_word(const BIGNUM *a)
457 else if (a->top == 1)
463 int BN_set_word(BIGNUM *a, BN_ULONG w)
466 if (bn_expand(a, (int)sizeof(BN_ULONG) * 8) == NULL)
470 a->top = (w ? 1 : 0);
475 BIGNUM *BN_bin2bn(const unsigned char *s, int len, BIGNUM *ret)
487 /* Skip leading zero's. */
488 for ( ; len > 0 && *s == 0; s++, len--)
495 i = ((n - 1) / BN_BYTES) + 1;
496 m = ((n - 1) % (BN_BYTES));
497 if (bn_wexpand(ret, (int)i) == NULL) {
505 l = (l << 8L) | *(s++);
513 * need to call this due to clear byte at top if avoiding having the top
514 * bit set (-ve number)
520 /* ignore negative */
521 static int bn2binpad(const BIGNUM *a, unsigned char *to, int tolen)
532 /* Add leading zeroes if necessary */
534 memset(to, 0, tolen - i);
538 l = a->d[i / BN_BYTES];
539 *(to++) = (unsigned char)(l >> (8 * (i % BN_BYTES))) & 0xff;
544 int BN_bn2binpad(const BIGNUM *a, unsigned char *to, int tolen)
548 return bn2binpad(a, to, tolen);
551 int BN_bn2bin(const BIGNUM *a, unsigned char *to)
553 return bn2binpad(a, to, -1);
556 BIGNUM *BN_lebin2bn(const unsigned char *s, int len, BIGNUM *ret)
569 /* Skip trailing zeroes. */
570 for ( ; len > 0 && *s == 0; s--, len--)
577 i = ((n - 1) / BN_BYTES) + 1;
578 m = ((n - 1) % (BN_BYTES));
579 if (bn_wexpand(ret, (int)i) == NULL) {
587 l = (l << 8L) | *(s--);
595 * need to call this due to clear byte at top if avoiding having the top
596 * bit set (-ve number)
602 int BN_bn2lebinpad(const BIGNUM *a, unsigned char *to, int tolen)
610 /* Add trailing zeroes if necessary */
612 memset(to + i, 0, tolen - i);
615 l = a->d[i / BN_BYTES];
616 *(to--) = (unsigned char)(l >> (8 * (i % BN_BYTES))) & 0xff;
621 int BN_ucmp(const BIGNUM *a, const BIGNUM *b)
624 BN_ULONG t1, t2, *ap, *bp;
634 for (i = a->top - 1; i >= 0; i--) {
638 return ((t1 > t2) ? 1 : -1);
643 int BN_cmp(const BIGNUM *a, const BIGNUM *b)
649 if ((a == NULL) || (b == NULL)) {
661 if (a->neg != b->neg) {
679 for (i = a->top - 1; i >= 0; i--) {
690 int BN_set_bit(BIGNUM *a, int n)
700 if (bn_wexpand(a, i + 1) == NULL)
702 for (k = a->top; k < i + 1; k++)
707 a->d[i] |= (((BN_ULONG)1) << j);
712 int BN_clear_bit(BIGNUM *a, int n)
725 a->d[i] &= (~(((BN_ULONG)1) << j));
730 int BN_is_bit_set(const BIGNUM *a, int n)
741 return (int)(((a->d[i]) >> j) & ((BN_ULONG)1));
744 int BN_mask_bits(BIGNUM *a, int n)
760 a->d[w] &= ~(BN_MASK2 << b);
766 void BN_set_negative(BIGNUM *a, int b)
768 if (b && !BN_is_zero(a))
774 int bn_cmp_words(const BN_ULONG *a, const BN_ULONG *b, int n)
782 return ((aa > bb) ? 1 : -1);
783 for (i = n - 2; i >= 0; i--) {
787 return ((aa > bb) ? 1 : -1);
793 * Here follows a specialised variants of bn_cmp_words(). It has the
794 * capability of performing the operation on arrays of different sizes. The
795 * sizes of those arrays is expressed through cl, which is the common length
796 * ( basically, min(len(a),len(b)) ), and dl, which is the delta between the
797 * two lengths, calculated as len(a)-len(b). All lengths are the number of
801 int bn_cmp_part_words(const BN_ULONG *a, const BN_ULONG *b, int cl, int dl)
807 for (i = dl; i < 0; i++) {
809 return -1; /* a < b */
813 for (i = dl; i > 0; i--) {
815 return 1; /* a > b */
818 return bn_cmp_words(a, b, cl);
822 * Constant-time conditional swap of a and b.
823 * a and b are swapped if condition is not 0. The code assumes that at most one bit of condition is set.
824 * nwords is the number of words to swap. The code assumes that at least nwords are allocated in both a and b,
825 * and that no more than nwords are used by either a or b.
826 * a and b cannot be the same number
828 void BN_consttime_swap(BN_ULONG condition, BIGNUM *a, BIGNUM *b, int nwords)
833 bn_wcheck_size(a, nwords);
834 bn_wcheck_size(b, nwords);
837 assert((condition & (condition - 1)) == 0);
838 assert(sizeof(BN_ULONG) >= sizeof(int));
840 condition = ((condition - 1) >> (BN_BITS2 - 1)) - 1;
842 t = (a->top ^ b->top) & condition;
846 #define BN_CONSTTIME_SWAP(ind) \
848 t = (a->d[ind] ^ b->d[ind]) & condition; \
855 for (i = 10; i < nwords; i++)
856 BN_CONSTTIME_SWAP(i);
859 BN_CONSTTIME_SWAP(9); /* Fallthrough */
861 BN_CONSTTIME_SWAP(8); /* Fallthrough */
863 BN_CONSTTIME_SWAP(7); /* Fallthrough */
865 BN_CONSTTIME_SWAP(6); /* Fallthrough */
867 BN_CONSTTIME_SWAP(5); /* Fallthrough */
869 BN_CONSTTIME_SWAP(4); /* Fallthrough */
871 BN_CONSTTIME_SWAP(3); /* Fallthrough */
873 BN_CONSTTIME_SWAP(2); /* Fallthrough */
875 BN_CONSTTIME_SWAP(1); /* Fallthrough */
877 BN_CONSTTIME_SWAP(0);
879 #undef BN_CONSTTIME_SWAP
882 /* Bits of security, see SP800-57 */
884 int BN_security_bits(int L, int N)
904 return bits >= secbits ? secbits : bits;
907 void BN_zero_ex(BIGNUM *a)
913 int BN_abs_is_word(const BIGNUM *a, const BN_ULONG w)
915 return ((a->top == 1) && (a->d[0] == w)) || ((w == 0) && (a->top == 0));
918 int BN_is_zero(const BIGNUM *a)
923 int BN_is_one(const BIGNUM *a)
925 return BN_abs_is_word(a, 1) && !a->neg;
928 int BN_is_word(const BIGNUM *a, const BN_ULONG w)
930 return BN_abs_is_word(a, w) && (!w || !a->neg);
933 int BN_is_odd(const BIGNUM *a)
935 return (a->top > 0) && (a->d[0] & 1);
938 int BN_is_negative(const BIGNUM *a)
940 return (a->neg != 0);
943 int BN_to_montgomery(BIGNUM *r, const BIGNUM *a, BN_MONT_CTX *mont,
946 return BN_mod_mul_montgomery(r, a, &(mont->RR), mont, ctx);
949 void BN_with_flags(BIGNUM *dest, const BIGNUM *b, int flags)
953 dest->dmax = b->dmax;
955 dest->flags = ((dest->flags & BN_FLG_MALLOCED)
956 | (b->flags & ~BN_FLG_MALLOCED)
957 | BN_FLG_STATIC_DATA | flags);
960 BN_GENCB *BN_GENCB_new(void)
964 if ((ret = OPENSSL_malloc(sizeof(*ret))) == NULL) {
965 BNerr(BN_F_BN_GENCB_NEW, ERR_R_MALLOC_FAILURE);
972 void BN_GENCB_free(BN_GENCB *cb)
979 void BN_set_flags(BIGNUM *b, int n)
984 int BN_get_flags(const BIGNUM *b, int n)
989 /* Populate a BN_GENCB structure with an "old"-style callback */
990 void BN_GENCB_set_old(BN_GENCB *gencb, void (*callback) (int, int, void *),
993 BN_GENCB *tmp_gencb = gencb;
995 tmp_gencb->arg = cb_arg;
996 tmp_gencb->cb.cb_1 = callback;
999 /* Populate a BN_GENCB structure with a "new"-style callback */
1000 void BN_GENCB_set(BN_GENCB *gencb, int (*callback) (int, int, BN_GENCB *),
1003 BN_GENCB *tmp_gencb = gencb;
1005 tmp_gencb->arg = cb_arg;
1006 tmp_gencb->cb.cb_2 = callback;
1009 void *BN_GENCB_get_arg(BN_GENCB *cb)
1014 BIGNUM *bn_wexpand(BIGNUM *a, int words)
1016 return (words <= a->dmax) ? a : bn_expand2(a, words);
1019 void bn_correct_top(BIGNUM *a)
1022 int tmp_top = a->top;
1025 for (ftl = &(a->d[tmp_top]); tmp_top > 0; tmp_top--) {