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
)
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
);
324 if (BN_get_flags(b
, BN_FLG_CONSTTIME
) != 0)
325 BN_set_flags(a
, BN_FLG_CONSTTIME
);
333 void BN_swap(BIGNUM
*a
, BIGNUM
*b
)
335 int flags_old_a
, flags_old_b
;
337 int tmp_top
, tmp_dmax
, tmp_neg
;
342 flags_old_a
= a
->flags
;
343 flags_old_b
= b
->flags
;
361 (flags_old_a
& BN_FLG_MALLOCED
) | (flags_old_b
& BN_FLG_STATIC_DATA
);
363 (flags_old_b
& BN_FLG_MALLOCED
) | (flags_old_a
& BN_FLG_STATIC_DATA
);
368 void BN_clear(BIGNUM
*a
)
372 OPENSSL_cleanse(a
->d
, sizeof(*a
->d
) * a
->dmax
);
377 BN_ULONG
BN_get_word(const BIGNUM
*a
)
381 else if (a
->top
== 1)
387 int BN_set_word(BIGNUM
*a
, BN_ULONG w
)
390 if (bn_expand(a
, (int)sizeof(BN_ULONG
) * 8) == NULL
)
394 a
->top
= (w
? 1 : 0);
399 BIGNUM
*BN_bin2bn(const unsigned char *s
, int len
, BIGNUM
*ret
)
411 /* Skip leading zero's. */
412 for ( ; len
> 0 && *s
== 0; s
++, len
--)
419 i
= ((n
- 1) / BN_BYTES
) + 1;
420 m
= ((n
- 1) % (BN_BYTES
));
421 if (bn_wexpand(ret
, (int)i
) == NULL
) {
429 l
= (l
<< 8L) | *(s
++);
437 * need to call this due to clear byte at top if avoiding having the top
438 * bit set (-ve number)
444 /* ignore negative */
445 static int bn2binpad(const BIGNUM
*a
, unsigned char *to
, int tolen
)
456 /* Add leading zeroes if necessary */
458 memset(to
, 0, tolen
- i
);
462 l
= a
->d
[i
/ BN_BYTES
];
463 *(to
++) = (unsigned char)(l
>> (8 * (i
% BN_BYTES
))) & 0xff;
468 int BN_bn2binpad(const BIGNUM
*a
, unsigned char *to
, int tolen
)
472 return bn2binpad(a
, to
, tolen
);
475 int BN_bn2bin(const BIGNUM
*a
, unsigned char *to
)
477 return bn2binpad(a
, to
, -1);
480 BIGNUM
*BN_lebin2bn(const unsigned char *s
, int len
, BIGNUM
*ret
)
493 /* Skip trailing zeroes. */
494 for ( ; len
> 0 && s
[-1] == 0; s
--, len
--)
501 i
= ((n
- 1) / BN_BYTES
) + 1;
502 m
= ((n
- 1) % (BN_BYTES
));
503 if (bn_wexpand(ret
, (int)i
) == NULL
) {
520 * need to call this due to clear byte at top if avoiding having the top
521 * bit set (-ve number)
527 int BN_bn2lebinpad(const BIGNUM
*a
, unsigned char *to
, int tolen
)
535 /* Add trailing zeroes if necessary */
537 memset(to
+ i
, 0, tolen
- i
);
540 l
= a
->d
[i
/ BN_BYTES
];
542 *to
= (unsigned char)(l
>> (8 * (i
% BN_BYTES
))) & 0xff;
547 int BN_ucmp(const BIGNUM
*a
, const BIGNUM
*b
)
550 BN_ULONG t1
, t2
, *ap
, *bp
;
560 for (i
= a
->top
- 1; i
>= 0; i
--) {
564 return ((t1
> t2
) ? 1 : -1);
569 int BN_cmp(const BIGNUM
*a
, const BIGNUM
*b
)
575 if ((a
== NULL
) || (b
== NULL
)) {
587 if (a
->neg
!= b
->neg
) {
605 for (i
= a
->top
- 1; i
>= 0; i
--) {
616 int BN_set_bit(BIGNUM
*a
, int n
)
626 if (bn_wexpand(a
, i
+ 1) == NULL
)
628 for (k
= a
->top
; k
< i
+ 1; k
++)
633 a
->d
[i
] |= (((BN_ULONG
)1) << j
);
638 int BN_clear_bit(BIGNUM
*a
, int n
)
651 a
->d
[i
] &= (~(((BN_ULONG
)1) << j
));
656 int BN_is_bit_set(const BIGNUM
*a
, int n
)
667 return (int)(((a
->d
[i
]) >> j
) & ((BN_ULONG
)1));
670 int BN_mask_bits(BIGNUM
*a
, int n
)
686 a
->d
[w
] &= ~(BN_MASK2
<< b
);
692 void BN_set_negative(BIGNUM
*a
, int b
)
694 if (b
&& !BN_is_zero(a
))
700 int bn_cmp_words(const BN_ULONG
*a
, const BN_ULONG
*b
, int n
)
708 return ((aa
> bb
) ? 1 : -1);
709 for (i
= n
- 2; i
>= 0; i
--) {
713 return ((aa
> bb
) ? 1 : -1);
719 * Here follows a specialised variants of bn_cmp_words(). It has the
720 * capability of performing the operation on arrays of different sizes. The
721 * sizes of those arrays is expressed through cl, which is the common length
722 * ( basically, min(len(a),len(b)) ), and dl, which is the delta between the
723 * two lengths, calculated as len(a)-len(b). All lengths are the number of
727 int bn_cmp_part_words(const BN_ULONG
*a
, const BN_ULONG
*b
, int cl
, int dl
)
733 for (i
= dl
; i
< 0; i
++) {
735 return -1; /* a < b */
739 for (i
= dl
; i
> 0; i
--) {
741 return 1; /* a > b */
744 return bn_cmp_words(a
, b
, cl
);
748 * Constant-time conditional swap of a and b.
749 * a and b are swapped if condition is not 0. The code assumes that at most one bit of condition is set.
750 * nwords is the number of words to swap. The code assumes that at least nwords are allocated in both a and b,
751 * and that no more than nwords are used by either a or b.
752 * a and b cannot be the same number
754 void BN_consttime_swap(BN_ULONG condition
, BIGNUM
*a
, BIGNUM
*b
, int nwords
)
759 bn_wcheck_size(a
, nwords
);
760 bn_wcheck_size(b
, nwords
);
763 assert((condition
& (condition
- 1)) == 0);
764 assert(sizeof(BN_ULONG
) >= sizeof(int));
766 condition
= ((condition
- 1) >> (BN_BITS2
- 1)) - 1;
768 t
= (a
->top
^ b
->top
) & condition
;
772 #define BN_CONSTTIME_SWAP(ind) \
774 t = (a->d[ind] ^ b->d[ind]) & condition; \
781 for (i
= 10; i
< nwords
; i
++)
782 BN_CONSTTIME_SWAP(i
);
785 BN_CONSTTIME_SWAP(9); /* Fallthrough */
787 BN_CONSTTIME_SWAP(8); /* Fallthrough */
789 BN_CONSTTIME_SWAP(7); /* Fallthrough */
791 BN_CONSTTIME_SWAP(6); /* Fallthrough */
793 BN_CONSTTIME_SWAP(5); /* Fallthrough */
795 BN_CONSTTIME_SWAP(4); /* Fallthrough */
797 BN_CONSTTIME_SWAP(3); /* Fallthrough */
799 BN_CONSTTIME_SWAP(2); /* Fallthrough */
801 BN_CONSTTIME_SWAP(1); /* Fallthrough */
803 BN_CONSTTIME_SWAP(0);
805 #undef BN_CONSTTIME_SWAP
808 /* Bits of security, see SP800-57 */
810 int BN_security_bits(int L
, int N
)
830 return bits
>= secbits
? secbits
: bits
;
833 void BN_zero_ex(BIGNUM
*a
)
839 int BN_abs_is_word(const BIGNUM
*a
, const BN_ULONG w
)
841 return ((a
->top
== 1) && (a
->d
[0] == w
)) || ((w
== 0) && (a
->top
== 0));
844 int BN_is_zero(const BIGNUM
*a
)
849 int BN_is_one(const BIGNUM
*a
)
851 return BN_abs_is_word(a
, 1) && !a
->neg
;
854 int BN_is_word(const BIGNUM
*a
, const BN_ULONG w
)
856 return BN_abs_is_word(a
, w
) && (!w
|| !a
->neg
);
859 int BN_is_odd(const BIGNUM
*a
)
861 return (a
->top
> 0) && (a
->d
[0] & 1);
864 int BN_is_negative(const BIGNUM
*a
)
866 return (a
->neg
!= 0);
869 int BN_to_montgomery(BIGNUM
*r
, const BIGNUM
*a
, BN_MONT_CTX
*mont
,
872 return BN_mod_mul_montgomery(r
, a
, &(mont
->RR
), mont
, ctx
);
875 void BN_with_flags(BIGNUM
*dest
, const BIGNUM
*b
, int flags
)
879 dest
->dmax
= b
->dmax
;
881 dest
->flags
= ((dest
->flags
& BN_FLG_MALLOCED
)
882 | (b
->flags
& ~BN_FLG_MALLOCED
)
883 | BN_FLG_STATIC_DATA
| flags
);
886 BN_GENCB
*BN_GENCB_new(void)
890 if ((ret
= OPENSSL_malloc(sizeof(*ret
))) == NULL
) {
891 BNerr(BN_F_BN_GENCB_NEW
, ERR_R_MALLOC_FAILURE
);
898 void BN_GENCB_free(BN_GENCB
*cb
)
905 void BN_set_flags(BIGNUM
*b
, int n
)
910 int BN_get_flags(const BIGNUM
*b
, int n
)
915 /* Populate a BN_GENCB structure with an "old"-style callback */
916 void BN_GENCB_set_old(BN_GENCB
*gencb
, void (*callback
) (int, int, void *),
919 BN_GENCB
*tmp_gencb
= gencb
;
921 tmp_gencb
->arg
= cb_arg
;
922 tmp_gencb
->cb
.cb_1
= callback
;
925 /* Populate a BN_GENCB structure with a "new"-style callback */
926 void BN_GENCB_set(BN_GENCB
*gencb
, int (*callback
) (int, int, BN_GENCB
*),
929 BN_GENCB
*tmp_gencb
= gencb
;
931 tmp_gencb
->arg
= cb_arg
;
932 tmp_gencb
->cb
.cb_2
= callback
;
935 void *BN_GENCB_get_arg(BN_GENCB
*cb
)
940 BIGNUM
*bn_wexpand(BIGNUM
*a
, int words
)
942 return (words
<= a
->dmax
) ? a
: bn_expand2(a
, words
);
945 void bn_correct_top(BIGNUM
*a
)
948 int tmp_top
= a
->top
;
951 for (ftl
= &(a
->d
[tmp_top
]); tmp_top
> 0; tmp_top
--) {