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 OPENSSL_cleanse(a->d, 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[-1] == 0; s--, len--)
577 i = ((n - 1) / BN_BYTES) + 1;
578 m = ((n - 1) % (BN_BYTES));
579 if (bn_wexpand(ret, (int)i) == NULL) {
596 * need to call this due to clear byte at top if avoiding having the top
597 * bit set (-ve number)
603 int BN_bn2lebinpad(const BIGNUM *a, unsigned char *to, int tolen)
611 /* Add trailing zeroes if necessary */
613 memset(to + i, 0, tolen - i);
616 l = a->d[i / BN_BYTES];
618 *to = (unsigned char)(l >> (8 * (i % BN_BYTES))) & 0xff;
623 int BN_ucmp(const BIGNUM *a, const BIGNUM *b)
626 BN_ULONG t1, t2, *ap, *bp;
636 for (i = a->top - 1; i >= 0; i--) {
640 return ((t1 > t2) ? 1 : -1);
645 int BN_cmp(const BIGNUM *a, const BIGNUM *b)
651 if ((a == NULL) || (b == NULL)) {
663 if (a->neg != b->neg) {
681 for (i = a->top - 1; i >= 0; i--) {
692 int BN_set_bit(BIGNUM *a, int n)
702 if (bn_wexpand(a, i + 1) == NULL)
704 for (k = a->top; k < i + 1; k++)
709 a->d[i] |= (((BN_ULONG)1) << j);
714 int BN_clear_bit(BIGNUM *a, int n)
727 a->d[i] &= (~(((BN_ULONG)1) << j));
732 int BN_is_bit_set(const BIGNUM *a, int n)
743 return (int)(((a->d[i]) >> j) & ((BN_ULONG)1));
746 int BN_mask_bits(BIGNUM *a, int n)
762 a->d[w] &= ~(BN_MASK2 << b);
768 void BN_set_negative(BIGNUM *a, int b)
770 if (b && !BN_is_zero(a))
776 int bn_cmp_words(const BN_ULONG *a, const BN_ULONG *b, int n)
784 return ((aa > bb) ? 1 : -1);
785 for (i = n - 2; i >= 0; i--) {
789 return ((aa > bb) ? 1 : -1);
795 * Here follows a specialised variants of bn_cmp_words(). It has the
796 * capability of performing the operation on arrays of different sizes. The
797 * sizes of those arrays is expressed through cl, which is the common length
798 * ( basically, min(len(a),len(b)) ), and dl, which is the delta between the
799 * two lengths, calculated as len(a)-len(b). All lengths are the number of
803 int bn_cmp_part_words(const BN_ULONG *a, const BN_ULONG *b, int cl, int dl)
809 for (i = dl; i < 0; i++) {
811 return -1; /* a < b */
815 for (i = dl; i > 0; i--) {
817 return 1; /* a > b */
820 return bn_cmp_words(a, b, cl);
824 * Constant-time conditional swap of a and b.
825 * a and b are swapped if condition is not 0. The code assumes that at most one bit of condition is set.
826 * nwords is the number of words to swap. The code assumes that at least nwords are allocated in both a and b,
827 * and that no more than nwords are used by either a or b.
828 * a and b cannot be the same number
830 void BN_consttime_swap(BN_ULONG condition, BIGNUM *a, BIGNUM *b, int nwords)
835 bn_wcheck_size(a, nwords);
836 bn_wcheck_size(b, nwords);
839 assert((condition & (condition - 1)) == 0);
840 assert(sizeof(BN_ULONG) >= sizeof(int));
842 condition = ((condition - 1) >> (BN_BITS2 - 1)) - 1;
844 t = (a->top ^ b->top) & condition;
848 #define BN_CONSTTIME_SWAP(ind) \
850 t = (a->d[ind] ^ b->d[ind]) & condition; \
857 for (i = 10; i < nwords; i++)
858 BN_CONSTTIME_SWAP(i);
861 BN_CONSTTIME_SWAP(9); /* Fallthrough */
863 BN_CONSTTIME_SWAP(8); /* Fallthrough */
865 BN_CONSTTIME_SWAP(7); /* Fallthrough */
867 BN_CONSTTIME_SWAP(6); /* Fallthrough */
869 BN_CONSTTIME_SWAP(5); /* Fallthrough */
871 BN_CONSTTIME_SWAP(4); /* Fallthrough */
873 BN_CONSTTIME_SWAP(3); /* Fallthrough */
875 BN_CONSTTIME_SWAP(2); /* Fallthrough */
877 BN_CONSTTIME_SWAP(1); /* Fallthrough */
879 BN_CONSTTIME_SWAP(0);
881 #undef BN_CONSTTIME_SWAP
884 /* Bits of security, see SP800-57 */
886 int BN_security_bits(int L, int N)
906 return bits >= secbits ? secbits : bits;
909 void BN_zero_ex(BIGNUM *a)
915 int BN_abs_is_word(const BIGNUM *a, const BN_ULONG w)
917 return ((a->top == 1) && (a->d[0] == w)) || ((w == 0) && (a->top == 0));
920 int BN_is_zero(const BIGNUM *a)
925 int BN_is_one(const BIGNUM *a)
927 return BN_abs_is_word(a, 1) && !a->neg;
930 int BN_is_word(const BIGNUM *a, const BN_ULONG w)
932 return BN_abs_is_word(a, w) && (!w || !a->neg);
935 int BN_is_odd(const BIGNUM *a)
937 return (a->top > 0) && (a->d[0] & 1);
940 int BN_is_negative(const BIGNUM *a)
942 return (a->neg != 0);
945 int BN_to_montgomery(BIGNUM *r, const BIGNUM *a, BN_MONT_CTX *mont,
948 return BN_mod_mul_montgomery(r, a, &(mont->RR), mont, ctx);
951 void BN_with_flags(BIGNUM *dest, const BIGNUM *b, int flags)
955 dest->dmax = b->dmax;
957 dest->flags = ((dest->flags & BN_FLG_MALLOCED)
958 | (b->flags & ~BN_FLG_MALLOCED)
959 | BN_FLG_STATIC_DATA | flags);
962 BN_GENCB *BN_GENCB_new(void)
966 if ((ret = OPENSSL_malloc(sizeof(*ret))) == NULL) {
967 BNerr(BN_F_BN_GENCB_NEW, ERR_R_MALLOC_FAILURE);
974 void BN_GENCB_free(BN_GENCB *cb)
981 void BN_set_flags(BIGNUM *b, int n)
986 int BN_get_flags(const BIGNUM *b, int n)
991 /* Populate a BN_GENCB structure with an "old"-style callback */
992 void BN_GENCB_set_old(BN_GENCB *gencb, void (*callback) (int, int, void *),
995 BN_GENCB *tmp_gencb = gencb;
997 tmp_gencb->arg = cb_arg;
998 tmp_gencb->cb.cb_1 = callback;
1001 /* Populate a BN_GENCB structure with a "new"-style callback */
1002 void BN_GENCB_set(BN_GENCB *gencb, int (*callback) (int, int, BN_GENCB *),
1005 BN_GENCB *tmp_gencb = gencb;
1007 tmp_gencb->arg = cb_arg;
1008 tmp_gencb->cb.cb_2 = callback;
1011 void *BN_GENCB_get_arg(BN_GENCB *cb)
1016 BIGNUM *bn_wexpand(BIGNUM *a, int words)
1018 return (words <= a->dmax) ? a : bn_expand2(a, words);
1021 void bn_correct_top(BIGNUM *a)
1024 int tmp_top = a->top;
1027 for (ftl = &(a->d[tmp_top]); tmp_top > 0; tmp_top--) {