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
);
335 if (BN_get_flags(b
, BN_FLG_CONSTTIME
) != 0)
336 BN_set_flags(a
, BN_FLG_CONSTTIME
);
344 void BN_swap(BIGNUM
*a
, BIGNUM
*b
)
346 int flags_old_a
, flags_old_b
;
348 int tmp_top
, tmp_dmax
, tmp_neg
;
353 flags_old_a
= a
->flags
;
354 flags_old_b
= b
->flags
;
372 (flags_old_a
& BN_FLG_MALLOCED
) | (flags_old_b
& BN_FLG_STATIC_DATA
);
374 (flags_old_b
& BN_FLG_MALLOCED
) | (flags_old_a
& BN_FLG_STATIC_DATA
);
379 void BN_clear(BIGNUM
*a
)
383 OPENSSL_cleanse(a
->d
, sizeof(*a
->d
) * a
->dmax
);
388 BN_ULONG
BN_get_word(const BIGNUM
*a
)
392 else if (a
->top
== 1)
398 int BN_set_word(BIGNUM
*a
, BN_ULONG w
)
401 if (bn_expand(a
, (int)sizeof(BN_ULONG
) * 8) == NULL
)
405 a
->top
= (w
? 1 : 0);
410 BIGNUM
*BN_bin2bn(const unsigned char *s
, int len
, BIGNUM
*ret
)
422 /* Skip leading zero's. */
423 for ( ; len
> 0 && *s
== 0; s
++, len
--)
430 i
= ((n
- 1) / BN_BYTES
) + 1;
431 m
= ((n
- 1) % (BN_BYTES
));
432 if (bn_wexpand(ret
, (int)i
) == NULL
) {
440 l
= (l
<< 8L) | *(s
++);
448 * need to call this due to clear byte at top if avoiding having the top
449 * bit set (-ve number)
455 /* ignore negative */
456 static int bn2binpad(const BIGNUM
*a
, unsigned char *to
, int tolen
)
467 /* Add leading zeroes if necessary */
469 memset(to
, 0, tolen
- i
);
473 l
= a
->d
[i
/ BN_BYTES
];
474 *(to
++) = (unsigned char)(l
>> (8 * (i
% BN_BYTES
))) & 0xff;
479 int BN_bn2binpad(const BIGNUM
*a
, unsigned char *to
, int tolen
)
483 return bn2binpad(a
, to
, tolen
);
486 int BN_bn2bin(const BIGNUM
*a
, unsigned char *to
)
488 return bn2binpad(a
, to
, -1);
491 BIGNUM
*BN_lebin2bn(const unsigned char *s
, int len
, BIGNUM
*ret
)
504 /* Skip trailing zeroes. */
505 for ( ; len
> 0 && s
[-1] == 0; s
--, len
--)
512 i
= ((n
- 1) / BN_BYTES
) + 1;
513 m
= ((n
- 1) % (BN_BYTES
));
514 if (bn_wexpand(ret
, (int)i
) == NULL
) {
531 * need to call this due to clear byte at top if avoiding having the top
532 * bit set (-ve number)
538 int BN_bn2lebinpad(const BIGNUM
*a
, unsigned char *to
, int tolen
)
546 /* Add trailing zeroes if necessary */
548 memset(to
+ i
, 0, tolen
- i
);
551 l
= a
->d
[i
/ BN_BYTES
];
553 *to
= (unsigned char)(l
>> (8 * (i
% BN_BYTES
))) & 0xff;
558 int BN_ucmp(const BIGNUM
*a
, const BIGNUM
*b
)
561 BN_ULONG t1
, t2
, *ap
, *bp
;
571 for (i
= a
->top
- 1; i
>= 0; i
--) {
575 return ((t1
> t2
) ? 1 : -1);
580 int BN_cmp(const BIGNUM
*a
, const BIGNUM
*b
)
586 if ((a
== NULL
) || (b
== NULL
)) {
598 if (a
->neg
!= b
->neg
) {
616 for (i
= a
->top
- 1; i
>= 0; i
--) {
627 int BN_set_bit(BIGNUM
*a
, int n
)
637 if (bn_wexpand(a
, i
+ 1) == NULL
)
639 for (k
= a
->top
; k
< i
+ 1; k
++)
644 a
->d
[i
] |= (((BN_ULONG
)1) << j
);
649 int BN_clear_bit(BIGNUM
*a
, int n
)
662 a
->d
[i
] &= (~(((BN_ULONG
)1) << j
));
667 int BN_is_bit_set(const BIGNUM
*a
, int n
)
678 return (int)(((a
->d
[i
]) >> j
) & ((BN_ULONG
)1));
681 int BN_mask_bits(BIGNUM
*a
, int n
)
697 a
->d
[w
] &= ~(BN_MASK2
<< b
);
703 void BN_set_negative(BIGNUM
*a
, int b
)
705 if (b
&& !BN_is_zero(a
))
711 int bn_cmp_words(const BN_ULONG
*a
, const BN_ULONG
*b
, int n
)
719 return ((aa
> bb
) ? 1 : -1);
720 for (i
= n
- 2; i
>= 0; i
--) {
724 return ((aa
> bb
) ? 1 : -1);
730 * Here follows a specialised variants of bn_cmp_words(). It has the
731 * capability of performing the operation on arrays of different sizes. The
732 * sizes of those arrays is expressed through cl, which is the common length
733 * ( basically, min(len(a),len(b)) ), and dl, which is the delta between the
734 * two lengths, calculated as len(a)-len(b). All lengths are the number of
738 int bn_cmp_part_words(const BN_ULONG
*a
, const BN_ULONG
*b
, int cl
, int dl
)
744 for (i
= dl
; i
< 0; i
++) {
746 return -1; /* a < b */
750 for (i
= dl
; i
> 0; i
--) {
752 return 1; /* a > b */
755 return bn_cmp_words(a
, b
, cl
);
759 * Constant-time conditional swap of a and b.
760 * a and b are swapped if condition is not 0. The code assumes that at most one bit of condition is set.
761 * nwords is the number of words to swap. The code assumes that at least nwords are allocated in both a and b,
762 * and that no more than nwords are used by either a or b.
763 * a and b cannot be the same number
765 void BN_consttime_swap(BN_ULONG condition
, BIGNUM
*a
, BIGNUM
*b
, int nwords
)
770 bn_wcheck_size(a
, nwords
);
771 bn_wcheck_size(b
, nwords
);
774 assert((condition
& (condition
- 1)) == 0);
775 assert(sizeof(BN_ULONG
) >= sizeof(int));
777 condition
= ((condition
- 1) >> (BN_BITS2
- 1)) - 1;
779 t
= (a
->top
^ b
->top
) & condition
;
783 #define BN_CONSTTIME_SWAP(ind) \
785 t = (a->d[ind] ^ b->d[ind]) & condition; \
792 for (i
= 10; i
< nwords
; i
++)
793 BN_CONSTTIME_SWAP(i
);
796 BN_CONSTTIME_SWAP(9); /* Fallthrough */
798 BN_CONSTTIME_SWAP(8); /* Fallthrough */
800 BN_CONSTTIME_SWAP(7); /* Fallthrough */
802 BN_CONSTTIME_SWAP(6); /* Fallthrough */
804 BN_CONSTTIME_SWAP(5); /* Fallthrough */
806 BN_CONSTTIME_SWAP(4); /* Fallthrough */
808 BN_CONSTTIME_SWAP(3); /* Fallthrough */
810 BN_CONSTTIME_SWAP(2); /* Fallthrough */
812 BN_CONSTTIME_SWAP(1); /* Fallthrough */
814 BN_CONSTTIME_SWAP(0);
816 #undef BN_CONSTTIME_SWAP
819 /* Bits of security, see SP800-57 */
821 int BN_security_bits(int L
, int N
)
841 return bits
>= secbits
? secbits
: bits
;
844 void BN_zero_ex(BIGNUM
*a
)
850 int BN_abs_is_word(const BIGNUM
*a
, const BN_ULONG w
)
852 return ((a
->top
== 1) && (a
->d
[0] == w
)) || ((w
== 0) && (a
->top
== 0));
855 int BN_is_zero(const BIGNUM
*a
)
860 int BN_is_one(const BIGNUM
*a
)
862 return BN_abs_is_word(a
, 1) && !a
->neg
;
865 int BN_is_word(const BIGNUM
*a
, const BN_ULONG w
)
867 return BN_abs_is_word(a
, w
) && (!w
|| !a
->neg
);
870 int BN_is_odd(const BIGNUM
*a
)
872 return (a
->top
> 0) && (a
->d
[0] & 1);
875 int BN_is_negative(const BIGNUM
*a
)
877 return (a
->neg
!= 0);
880 int BN_to_montgomery(BIGNUM
*r
, const BIGNUM
*a
, BN_MONT_CTX
*mont
,
883 return BN_mod_mul_montgomery(r
, a
, &(mont
->RR
), mont
, ctx
);
886 void BN_with_flags(BIGNUM
*dest
, const BIGNUM
*b
, int flags
)
890 dest
->dmax
= b
->dmax
;
892 dest
->flags
= ((dest
->flags
& BN_FLG_MALLOCED
)
893 | (b
->flags
& ~BN_FLG_MALLOCED
)
894 | BN_FLG_STATIC_DATA
| flags
);
897 BN_GENCB
*BN_GENCB_new(void)
901 if ((ret
= OPENSSL_malloc(sizeof(*ret
))) == NULL
) {
902 BNerr(BN_F_BN_GENCB_NEW
, ERR_R_MALLOC_FAILURE
);
909 void BN_GENCB_free(BN_GENCB
*cb
)
916 void BN_set_flags(BIGNUM
*b
, int n
)
921 int BN_get_flags(const BIGNUM
*b
, int n
)
926 /* Populate a BN_GENCB structure with an "old"-style callback */
927 void BN_GENCB_set_old(BN_GENCB
*gencb
, void (*callback
) (int, int, void *),
930 BN_GENCB
*tmp_gencb
= gencb
;
932 tmp_gencb
->arg
= cb_arg
;
933 tmp_gencb
->cb
.cb_1
= callback
;
936 /* Populate a BN_GENCB structure with a "new"-style callback */
937 void BN_GENCB_set(BN_GENCB
*gencb
, int (*callback
) (int, int, BN_GENCB
*),
940 BN_GENCB
*tmp_gencb
= gencb
;
942 tmp_gencb
->arg
= cb_arg
;
943 tmp_gencb
->cb
.cb_2
= callback
;
946 void *BN_GENCB_get_arg(BN_GENCB
*cb
)
951 BIGNUM
*bn_wexpand(BIGNUM
*a
, int words
)
953 return (words
<= a
->dmax
) ? a
: bn_expand2(a
, words
);
956 void bn_correct_top(BIGNUM
*a
)
959 int tmp_top
= a
->top
;
962 for (ftl
= &(a
->d
[tmp_top
]); tmp_top
> 0; tmp_top
--) {