1 /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
4 * This package is an SSL implementation written
5 * by Eric Young (eay@cryptsoft.com).
6 * The implementation was written so as to conform with Netscapes SSL.
8 * This library is free for commercial and non-commercial use as long as
9 * the following conditions are aheared to. The following conditions
10 * apply to all code found in this distribution, be it the RC4, RSA,
11 * lhash, DES, etc., code; not just the SSL code. The SSL documentation
12 * included with this distribution is covered by the same copyright terms
13 * except that the holder is Tim Hudson (tjh@cryptsoft.com).
15 * Copyright remains Eric Young's, and as such any Copyright notices in
16 * the code are not to be removed.
17 * If this package is used in a product, Eric Young should be given attribution
18 * as the author of the parts of the library used.
19 * This can be in the form of a textual message at program startup or
20 * in documentation (online or textual) provided with the package.
22 * Redistribution and use in source and binary forms, with or without
23 * modification, are permitted provided that the following conditions
25 * 1. Redistributions of source code must retain the copyright
26 * notice, this list of conditions and the following disclaimer.
27 * 2. Redistributions in binary form must reproduce the above copyright
28 * notice, this list of conditions and the following disclaimer in the
29 * documentation and/or other materials provided with the distribution.
30 * 3. All advertising materials mentioning features or use of this software
31 * must display the following acknowledgement:
32 * "This product includes cryptographic software written by
33 * Eric Young (eay@cryptsoft.com)"
34 * The word 'cryptographic' can be left out if the rouines from the library
35 * being used are not cryptographic related :-).
36 * 4. If you include any Windows specific code (or a derivative thereof) from
37 * the apps directory (application code) you must include an acknowledgement:
38 * "This product includes software written by Tim Hudson (tjh@cryptsoft.com)"
40 * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND
41 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
42 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
43 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
44 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
45 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
46 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
47 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
48 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
49 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
52 * The licence and distribution terms for any publically available version or
53 * derivative of this code cannot be changed. i.e. this code cannot simply be
54 * copied and put under another distribution licence
55 * [including the GNU Public Licence.]
59 # undef NDEBUG /* avoid conflicting definitions */
65 #include "internal/cryptlib.h"
67 #include <openssl/opensslconf.h>
69 /* This stuff appears to be completely unused, so is deprecated */
70 #if OPENSSL_API_COMPAT < 0x00908000L
72 * For a 32 bit machine
81 static int bn_limit_bits = 0;
82 static int bn_limit_num = 8; /* (1<<bn_limit_bits) */
83 static int bn_limit_bits_low = 0;
84 static int bn_limit_num_low = 8; /* (1<<bn_limit_bits_low) */
85 static int bn_limit_bits_high = 0;
86 static int bn_limit_num_high = 8; /* (1<<bn_limit_bits_high) */
87 static int bn_limit_bits_mont = 0;
88 static int bn_limit_num_mont = 8; /* (1<<bn_limit_bits_mont) */
90 void BN_set_params(int mult, int high, int low, int mont)
93 if (mult > (int)(sizeof(int) * 8) - 1)
94 mult = sizeof(int) * 8 - 1;
96 bn_limit_num = 1 << mult;
99 if (high > (int)(sizeof(int) * 8) - 1)
100 high = sizeof(int) * 8 - 1;
101 bn_limit_bits_high = high;
102 bn_limit_num_high = 1 << high;
105 if (low > (int)(sizeof(int) * 8) - 1)
106 low = sizeof(int) * 8 - 1;
107 bn_limit_bits_low = low;
108 bn_limit_num_low = 1 << low;
111 if (mont > (int)(sizeof(int) * 8) - 1)
112 mont = sizeof(int) * 8 - 1;
113 bn_limit_bits_mont = mont;
114 bn_limit_num_mont = 1 << mont;
118 int BN_get_params(int which)
121 return (bn_limit_bits);
123 return (bn_limit_bits_high);
125 return (bn_limit_bits_low);
127 return (bn_limit_bits_mont);
133 const BIGNUM *BN_value_one(void)
135 static const BN_ULONG data_one = 1L;
136 static const BIGNUM const_one =
137 { (BN_ULONG *)&data_one, 1, 1, 0, BN_FLG_STATIC_DATA };
142 int BN_num_bits_word(BN_ULONG l)
144 static const unsigned char bits[256] = {
145 0, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4,
146 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
147 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
148 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
149 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
150 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
151 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
152 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
153 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
154 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
155 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
156 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
157 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
158 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
159 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
160 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
163 #if defined(SIXTY_FOUR_BIT_LONG)
164 if (l & 0xffffffff00000000L) {
165 if (l & 0xffff000000000000L) {
166 if (l & 0xff00000000000000L) {
167 return (bits[(int)(l >> 56)] + 56);
169 return (bits[(int)(l >> 48)] + 48);
171 if (l & 0x0000ff0000000000L) {
172 return (bits[(int)(l >> 40)] + 40);
174 return (bits[(int)(l >> 32)] + 32);
178 # ifdef SIXTY_FOUR_BIT
179 if (l & 0xffffffff00000000LL) {
180 if (l & 0xffff000000000000LL) {
181 if (l & 0xff00000000000000LL) {
182 return (bits[(int)(l >> 56)] + 56);
184 return (bits[(int)(l >> 48)] + 48);
186 if (l & 0x0000ff0000000000LL) {
187 return (bits[(int)(l >> 40)] + 40);
189 return (bits[(int)(l >> 32)] + 32);
195 #if defined(THIRTY_TWO_BIT) || defined(SIXTY_FOUR_BIT) || defined(SIXTY_FOUR_BIT_LONG)
196 if (l & 0xffff0000L) {
198 return (bits[(int)(l >> 24L)] + 24);
200 return (bits[(int)(l >> 16L)] + 16);
204 #if defined(THIRTY_TWO_BIT) || defined(SIXTY_FOUR_BIT) || defined(SIXTY_FOUR_BIT_LONG)
206 return (bits[(int)(l >> 8)] + 8);
209 return (bits[(int)(l)]);
214 int BN_num_bits(const BIGNUM *a)
221 return ((i * BN_BITS2) + BN_num_bits_word(a->d[i]));
224 static void bn_free_d(BIGNUM *a)
226 if (BN_get_flags(a,BN_FLG_SECURE))
227 OPENSSL_secure_free(a->d);
233 void BN_clear_free(BIGNUM *a)
241 OPENSSL_cleanse(a->d, a->dmax * sizeof(a->d[0]));
242 if (!BN_get_flags(a, BN_FLG_STATIC_DATA))
245 i = BN_get_flags(a, BN_FLG_MALLOCED);
246 OPENSSL_cleanse(a, sizeof(*a));
251 void BN_free(BIGNUM *a)
256 if (!BN_get_flags(a, BN_FLG_STATIC_DATA))
258 if (a->flags & BN_FLG_MALLOCED)
261 #if OPENSSL_API_COMPAT < 0x00908000L
262 a->flags |= BN_FLG_FREE;
268 void bn_init(BIGNUM *a)
280 if ((ret = OPENSSL_zalloc(sizeof(*ret))) == NULL) {
281 BNerr(BN_F_BN_NEW, ERR_R_MALLOC_FAILURE);
284 ret->flags = BN_FLG_MALLOCED;
289 BIGNUM *BN_secure_new(void)
291 BIGNUM *ret = BN_new();
293 ret->flags |= BN_FLG_SECURE;
297 /* This is used by bn_expand2() */
298 /* The caller MUST check that words > b->dmax before calling this */
299 static BN_ULONG *bn_expand_internal(const BIGNUM *b, int words)
301 BN_ULONG *A, *a = NULL;
307 if (words > (INT_MAX / (4 * BN_BITS2))) {
308 BNerr(BN_F_BN_EXPAND_INTERNAL, BN_R_BIGNUM_TOO_LONG);
311 if (BN_get_flags(b, BN_FLG_STATIC_DATA)) {
312 BNerr(BN_F_BN_EXPAND_INTERNAL, BN_R_EXPAND_ON_STATIC_BIGNUM_DATA);
315 if (BN_get_flags(b,BN_FLG_SECURE))
316 a = A = OPENSSL_secure_zalloc(words * sizeof(*a));
318 a = A = OPENSSL_zalloc(words * sizeof(*a));
320 BNerr(BN_F_BN_EXPAND_INTERNAL, ERR_R_MALLOC_FAILURE);
326 /* Check if the previous number needs to be copied */
328 for (i = b->top >> 2; i > 0; i--, A += 4, B += 4) {
330 * The fact that the loop is unrolled
331 * 4-wise is a tribute to Intel. It's
332 * the one that doesn't have enough
333 * registers to accommodate more data.
334 * I'd unroll it 8-wise otherwise:-)
336 * <appro@fy.chalmers.se>
338 BN_ULONG a0, a1, a2, a3;
349 * workaround for ultrix cc: without 'case 0', the optimizer does
350 * the switch table by doing a=top&3; a--; goto jump_table[a];
351 * which fails for top== 0
353 switch (b->top & 3) {
365 memset(A, 0, sizeof(*A) * words);
366 memcpy(A, b->d, sizeof(b->d[0]) * b->top);
373 * This is an internal function that should not be used in applications. It
374 * ensures that 'b' has enough room for a 'words' word number and initialises
375 * any unused part of b->d with leading zeros. It is mostly used by the
376 * various BIGNUM routines. If there is an error, NULL is returned. If not,
380 BIGNUM *bn_expand2(BIGNUM *b, int words)
384 if (words > b->dmax) {
385 BN_ULONG *a = bn_expand_internal(b, words);
389 OPENSSL_cleanse(b->d, b->dmax * sizeof(b->d[0]));
400 BIGNUM *BN_dup(const BIGNUM *a)
408 t = BN_get_flags(a, BN_FLG_SECURE) ? BN_secure_new() : BN_new();
411 if (!BN_copy(t, a)) {
419 BIGNUM *BN_copy(BIGNUM *a, const BIGNUM *b)
429 if (bn_wexpand(a, b->top) == NULL)
435 for (i = b->top >> 2; i > 0; i--, A += 4, B += 4) {
436 BN_ULONG a0, a1, a2, a3;
446 /* ultrix cc workaround, see comments in bn_expand_internal */
447 switch (b->top & 3) {
457 memcpy(a->d, b->d, sizeof(b->d[0]) * b->top);
466 void BN_swap(BIGNUM *a, BIGNUM *b)
468 int flags_old_a, flags_old_b;
470 int tmp_top, tmp_dmax, tmp_neg;
475 flags_old_a = a->flags;
476 flags_old_b = b->flags;
494 (flags_old_a & BN_FLG_MALLOCED) | (flags_old_b & BN_FLG_STATIC_DATA);
496 (flags_old_b & BN_FLG_MALLOCED) | (flags_old_a & BN_FLG_STATIC_DATA);
501 void BN_clear(BIGNUM *a)
505 memset(a->d, 0, sizeof(*a->d) * a->dmax);
510 BN_ULONG BN_get_word(const BIGNUM *a)
514 else if (a->top == 1)
520 int BN_set_word(BIGNUM *a, BN_ULONG w)
523 if (bn_expand(a, (int)sizeof(BN_ULONG) * 8) == NULL)
527 a->top = (w ? 1 : 0);
532 BIGNUM *BN_bin2bn(const unsigned char *s, int len, BIGNUM *ret)
544 /* Skip leading zero's. */
545 for ( ; len > 0 && *s == 0; s++, len--)
552 i = ((n - 1) / BN_BYTES) + 1;
553 m = ((n - 1) % (BN_BYTES));
554 if (bn_wexpand(ret, (int)i) == NULL) {
562 l = (l << 8L) | *(s++);
570 * need to call this due to clear byte at top if avoiding having the top
571 * bit set (-ve number)
577 /* ignore negative */
578 static int bn2binpad(const BIGNUM *a, unsigned char *to, int tolen)
589 /* Add leading zeroes if necessary */
591 memset(to, 0, tolen - i);
595 l = a->d[i / BN_BYTES];
596 *(to++) = (unsigned char)(l >> (8 * (i % BN_BYTES))) & 0xff;
601 int BN_bn2binpad(const BIGNUM *a, unsigned char *to, int tolen)
605 return bn2binpad(a, to, tolen);
608 int BN_bn2bin(const BIGNUM *a, unsigned char *to)
610 return bn2binpad(a, to, -1);
613 BIGNUM *BN_lebin2bn(const unsigned char *s, int len, BIGNUM *ret)
626 /* Skip trailing zeroes. */
627 for ( ; len > 0 && *s == 0; s--, len--)
634 i = ((n - 1) / BN_BYTES) + 1;
635 m = ((n - 1) % (BN_BYTES));
636 if (bn_wexpand(ret, (int)i) == NULL) {
644 l = (l << 8L) | *(s--);
652 * need to call this due to clear byte at top if avoiding having the top
653 * bit set (-ve number)
659 int BN_bn2lebinpad(const BIGNUM *a, unsigned char *to, int tolen)
667 /* Add trailing zeroes if necessary */
669 memset(to + i, 0, tolen - i);
672 l = a->d[i / BN_BYTES];
673 *(to--) = (unsigned char)(l >> (8 * (i % BN_BYTES))) & 0xff;
678 int BN_ucmp(const BIGNUM *a, const BIGNUM *b)
681 BN_ULONG t1, t2, *ap, *bp;
691 for (i = a->top - 1; i >= 0; i--) {
695 return ((t1 > t2) ? 1 : -1);
700 int BN_cmp(const BIGNUM *a, const BIGNUM *b)
706 if ((a == NULL) || (b == NULL)) {
718 if (a->neg != b->neg) {
736 for (i = a->top - 1; i >= 0; i--) {
747 int BN_set_bit(BIGNUM *a, int n)
757 if (bn_wexpand(a, i + 1) == NULL)
759 for (k = a->top; k < i + 1; k++)
764 a->d[i] |= (((BN_ULONG)1) << j);
769 int BN_clear_bit(BIGNUM *a, int n)
782 a->d[i] &= (~(((BN_ULONG)1) << j));
787 int BN_is_bit_set(const BIGNUM *a, int n)
798 return (int)(((a->d[i]) >> j) & ((BN_ULONG)1));
801 int BN_mask_bits(BIGNUM *a, int n)
817 a->d[w] &= ~(BN_MASK2 << b);
823 void BN_set_negative(BIGNUM *a, int b)
825 if (b && !BN_is_zero(a))
831 int bn_cmp_words(const BN_ULONG *a, const BN_ULONG *b, int n)
839 return ((aa > bb) ? 1 : -1);
840 for (i = n - 2; i >= 0; i--) {
844 return ((aa > bb) ? 1 : -1);
850 * Here follows a specialised variants of bn_cmp_words(). It has the
851 * property of performing the operation on arrays of different sizes. The
852 * sizes of those arrays is expressed through cl, which is the common length
853 * ( basicall, min(len(a),len(b)) ), and dl, which is the delta between the
854 * two lengths, calculated as len(a)-len(b). All lengths are the number of
858 int bn_cmp_part_words(const BN_ULONG *a, const BN_ULONG *b, int cl, int dl)
864 for (i = dl; i < 0; i++) {
866 return -1; /* a < b */
870 for (i = dl; i > 0; i--) {
872 return 1; /* a > b */
875 return bn_cmp_words(a, b, cl);
879 * Constant-time conditional swap of a and b.
880 * a and b are swapped if condition is not 0. The code assumes that at most one bit of condition is set.
881 * nwords is the number of words to swap. The code assumes that at least nwords are allocated in both a and b,
882 * and that no more than nwords are used by either a or b.
883 * a and b cannot be the same number
885 void BN_consttime_swap(BN_ULONG condition, BIGNUM *a, BIGNUM *b, int nwords)
890 bn_wcheck_size(a, nwords);
891 bn_wcheck_size(b, nwords);
894 assert((condition & (condition - 1)) == 0);
895 assert(sizeof(BN_ULONG) >= sizeof(int));
897 condition = ((condition - 1) >> (BN_BITS2 - 1)) - 1;
899 t = (a->top ^ b->top) & condition;
903 #define BN_CONSTTIME_SWAP(ind) \
905 t = (a->d[ind] ^ b->d[ind]) & condition; \
912 for (i = 10; i < nwords; i++)
913 BN_CONSTTIME_SWAP(i);
916 BN_CONSTTIME_SWAP(9); /* Fallthrough */
918 BN_CONSTTIME_SWAP(8); /* Fallthrough */
920 BN_CONSTTIME_SWAP(7); /* Fallthrough */
922 BN_CONSTTIME_SWAP(6); /* Fallthrough */
924 BN_CONSTTIME_SWAP(5); /* Fallthrough */
926 BN_CONSTTIME_SWAP(4); /* Fallthrough */
928 BN_CONSTTIME_SWAP(3); /* Fallthrough */
930 BN_CONSTTIME_SWAP(2); /* Fallthrough */
932 BN_CONSTTIME_SWAP(1); /* Fallthrough */
934 BN_CONSTTIME_SWAP(0);
936 #undef BN_CONSTTIME_SWAP
939 /* Bits of security, see SP800-57 */
941 int BN_security_bits(int L, int N)
961 return bits >= secbits ? secbits : bits;
964 void BN_zero_ex(BIGNUM *a)
970 int BN_abs_is_word(const BIGNUM *a, const BN_ULONG w)
972 return ((a->top == 1) && (a->d[0] == w)) || ((w == 0) && (a->top == 0));
975 int BN_is_zero(const BIGNUM *a)
980 int BN_is_one(const BIGNUM *a)
982 return BN_abs_is_word(a, 1) && !a->neg;
985 int BN_is_word(const BIGNUM *a, const BN_ULONG w)
987 return BN_abs_is_word(a, w) && (!w || !a->neg);
990 int BN_is_odd(const BIGNUM *a)
992 return (a->top > 0) && (a->d[0] & 1);
995 int BN_is_negative(const BIGNUM *a)
997 return (a->neg != 0);
1000 int BN_to_montgomery(BIGNUM *r, const BIGNUM *a, BN_MONT_CTX *mont,
1003 return BN_mod_mul_montgomery(r, a, &(mont->RR), mont, ctx);
1006 void BN_with_flags(BIGNUM *dest, const BIGNUM *b, int flags)
1010 dest->dmax = b->dmax;
1012 dest->flags = ((dest->flags & BN_FLG_MALLOCED)
1013 | (b->flags & ~BN_FLG_MALLOCED)
1014 | BN_FLG_STATIC_DATA | flags);
1017 BN_GENCB *BN_GENCB_new(void)
1021 if ((ret = OPENSSL_malloc(sizeof(*ret))) == NULL) {
1022 BNerr(BN_F_BN_GENCB_NEW, ERR_R_MALLOC_FAILURE);
1029 void BN_GENCB_free(BN_GENCB *cb)
1036 void BN_set_flags(BIGNUM *b, int n)
1041 int BN_get_flags(const BIGNUM *b, int n)
1043 return b->flags & n;
1046 /* Populate a BN_GENCB structure with an "old"-style callback */
1047 void BN_GENCB_set_old(BN_GENCB *gencb, void (*callback) (int, int, void *),
1050 BN_GENCB *tmp_gencb = gencb;
1052 tmp_gencb->arg = cb_arg;
1053 tmp_gencb->cb.cb_1 = callback;
1056 /* Populate a BN_GENCB structure with a "new"-style callback */
1057 void BN_GENCB_set(BN_GENCB *gencb, int (*callback) (int, int, BN_GENCB *),
1060 BN_GENCB *tmp_gencb = gencb;
1062 tmp_gencb->arg = cb_arg;
1063 tmp_gencb->cb.cb_2 = callback;
1066 void *BN_GENCB_get_arg(BN_GENCB *cb)
1071 BIGNUM *bn_wexpand(BIGNUM *a, int words)
1073 return (words <= a->dmax) ? a : bn_expand2(a, words);
1076 void bn_correct_top(BIGNUM *a)
1079 int tmp_top = a->top;
1082 for (ftl = &(a->d[tmp_top - 1]); tmp_top > 0; tmp_top--)