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.]
60 #include "internal/cryptlib.h"
62 #include <openssl/opensslconf.h>
64 /* This stuff appears to be completely unused, so is deprecated */
65 #if OPENSSL_API_COMPAT < 0x00908000L
67 * For a 32 bit machine
76 static int bn_limit_bits = 0;
77 static int bn_limit_num = 8; /* (1<<bn_limit_bits) */
78 static int bn_limit_bits_low = 0;
79 static int bn_limit_num_low = 8; /* (1<<bn_limit_bits_low) */
80 static int bn_limit_bits_high = 0;
81 static int bn_limit_num_high = 8; /* (1<<bn_limit_bits_high) */
82 static int bn_limit_bits_mont = 0;
83 static int bn_limit_num_mont = 8; /* (1<<bn_limit_bits_mont) */
85 void BN_set_params(int mult, int high, int low, int mont)
88 if (mult > (int)(sizeof(int) * 8) - 1)
89 mult = sizeof(int) * 8 - 1;
91 bn_limit_num = 1 << mult;
94 if (high > (int)(sizeof(int) * 8) - 1)
95 high = sizeof(int) * 8 - 1;
96 bn_limit_bits_high = high;
97 bn_limit_num_high = 1 << high;
100 if (low > (int)(sizeof(int) * 8) - 1)
101 low = sizeof(int) * 8 - 1;
102 bn_limit_bits_low = low;
103 bn_limit_num_low = 1 << low;
106 if (mont > (int)(sizeof(int) * 8) - 1)
107 mont = sizeof(int) * 8 - 1;
108 bn_limit_bits_mont = mont;
109 bn_limit_num_mont = 1 << mont;
113 int BN_get_params(int which)
116 return (bn_limit_bits);
118 return (bn_limit_bits_high);
120 return (bn_limit_bits_low);
122 return (bn_limit_bits_mont);
128 const BIGNUM *BN_value_one(void)
130 static const BN_ULONG data_one = 1L;
131 static const BIGNUM const_one =
132 { (BN_ULONG *)&data_one, 1, 1, 0, BN_FLG_STATIC_DATA };
137 int BN_num_bits_word(BN_ULONG l)
139 static const unsigned char bits[256] = {
140 0, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4,
141 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
142 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
143 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
144 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
145 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
146 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
147 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
148 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
149 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
150 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
151 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
152 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
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,
158 #if defined(SIXTY_FOUR_BIT_LONG)
159 if (l & 0xffffffff00000000L) {
160 if (l & 0xffff000000000000L) {
161 if (l & 0xff00000000000000L) {
162 return (bits[(int)(l >> 56)] + 56);
164 return (bits[(int)(l >> 48)] + 48);
166 if (l & 0x0000ff0000000000L) {
167 return (bits[(int)(l >> 40)] + 40);
169 return (bits[(int)(l >> 32)] + 32);
173 # ifdef SIXTY_FOUR_BIT
174 if (l & 0xffffffff00000000LL) {
175 if (l & 0xffff000000000000LL) {
176 if (l & 0xff00000000000000LL) {
177 return (bits[(int)(l >> 56)] + 56);
179 return (bits[(int)(l >> 48)] + 48);
181 if (l & 0x0000ff0000000000LL) {
182 return (bits[(int)(l >> 40)] + 40);
184 return (bits[(int)(l >> 32)] + 32);
190 #if defined(THIRTY_TWO_BIT) || defined(SIXTY_FOUR_BIT) || defined(SIXTY_FOUR_BIT_LONG)
191 if (l & 0xffff0000L) {
193 return (bits[(int)(l >> 24L)] + 24);
195 return (bits[(int)(l >> 16L)] + 16);
199 #if defined(THIRTY_TWO_BIT) || defined(SIXTY_FOUR_BIT) || defined(SIXTY_FOUR_BIT_LONG)
201 return (bits[(int)(l >> 8)] + 8);
204 return (bits[(int)(l)]);
209 int BN_num_bits(const BIGNUM *a)
216 return ((i * BN_BITS2) + BN_num_bits_word(a->d[i]));
219 static void bn_free_d(BIGNUM *a)
221 if (BN_get_flags(a,BN_FLG_SECURE))
222 OPENSSL_secure_free(a->d);
228 void BN_clear_free(BIGNUM *a)
236 OPENSSL_cleanse(a->d, a->dmax * sizeof(a->d[0]));
237 if (!BN_get_flags(a, BN_FLG_STATIC_DATA))
240 i = BN_get_flags(a, BN_FLG_MALLOCED);
241 OPENSSL_cleanse(a, sizeof(*a));
246 void BN_free(BIGNUM *a)
251 if (!BN_get_flags(a, BN_FLG_STATIC_DATA))
253 if (a->flags & BN_FLG_MALLOCED)
256 #if OPENSSL_API_COMPAT < 0x00908000L
257 a->flags |= BN_FLG_FREE;
263 void bn_init(BIGNUM *a)
275 if ((ret = OPENSSL_zalloc(sizeof(*ret))) == NULL) {
276 BNerr(BN_F_BN_NEW, ERR_R_MALLOC_FAILURE);
279 ret->flags = BN_FLG_MALLOCED;
284 BIGNUM *BN_secure_new(void)
286 BIGNUM *ret = BN_new();
288 ret->flags |= BN_FLG_SECURE;
292 /* This is used by bn_expand2() */
293 /* The caller MUST check that words > b->dmax before calling this */
294 static BN_ULONG *bn_expand_internal(const BIGNUM *b, int words)
296 BN_ULONG *A, *a = NULL;
302 if (words > (INT_MAX / (4 * BN_BITS2))) {
303 BNerr(BN_F_BN_EXPAND_INTERNAL, BN_R_BIGNUM_TOO_LONG);
306 if (BN_get_flags(b, BN_FLG_STATIC_DATA)) {
307 BNerr(BN_F_BN_EXPAND_INTERNAL, BN_R_EXPAND_ON_STATIC_BIGNUM_DATA);
310 if (BN_get_flags(b,BN_FLG_SECURE))
311 a = A = OPENSSL_secure_zalloc(words * sizeof(*a));
313 a = A = OPENSSL_zalloc(words * sizeof(*a));
315 BNerr(BN_F_BN_EXPAND_INTERNAL, ERR_R_MALLOC_FAILURE);
321 /* Check if the previous number needs to be copied */
323 for (i = b->top >> 2; i > 0; i--, A += 4, B += 4) {
325 * The fact that the loop is unrolled
326 * 4-wise is a tribute to Intel. It's
327 * the one that doesn't have enough
328 * registers to accommodate more data.
329 * I'd unroll it 8-wise otherwise:-)
331 * <appro@fy.chalmers.se>
333 BN_ULONG a0, a1, a2, a3;
343 switch (b->top & 3) {
351 /* Without the "case 0" some old optimizers got this wrong. */
356 memset(A, 0, sizeof(*A) * words);
357 memcpy(A, b->d, sizeof(b->d[0]) * b->top);
364 * This is an internal function that should not be used in applications. It
365 * ensures that 'b' has enough room for a 'words' word number and initialises
366 * any unused part of b->d with leading zeros. It is mostly used by the
367 * various BIGNUM routines. If there is an error, NULL is returned. If not,
371 BIGNUM *bn_expand2(BIGNUM *b, int words)
375 if (words > b->dmax) {
376 BN_ULONG *a = bn_expand_internal(b, words);
380 OPENSSL_cleanse(b->d, b->dmax * sizeof(b->d[0]));
391 BIGNUM *BN_dup(const BIGNUM *a)
399 t = BN_get_flags(a, BN_FLG_SECURE) ? BN_secure_new() : BN_new();
402 if (!BN_copy(t, a)) {
410 BIGNUM *BN_copy(BIGNUM *a, const BIGNUM *b)
420 if (bn_wexpand(a, b->top) == NULL)
426 for (i = b->top >> 2; i > 0; i--, A += 4, B += 4) {
427 BN_ULONG a0, a1, a2, a3;
437 /* ultrix cc workaround, see comments in bn_expand_internal */
438 switch (b->top & 3) {
448 memcpy(a->d, b->d, sizeof(b->d[0]) * b->top);
457 void BN_swap(BIGNUM *a, BIGNUM *b)
459 int flags_old_a, flags_old_b;
461 int tmp_top, tmp_dmax, tmp_neg;
466 flags_old_a = a->flags;
467 flags_old_b = b->flags;
485 (flags_old_a & BN_FLG_MALLOCED) | (flags_old_b & BN_FLG_STATIC_DATA);
487 (flags_old_b & BN_FLG_MALLOCED) | (flags_old_a & BN_FLG_STATIC_DATA);
492 void BN_clear(BIGNUM *a)
496 memset(a->d, 0, sizeof(*a->d) * a->dmax);
501 BN_ULONG BN_get_word(const BIGNUM *a)
505 else if (a->top == 1)
511 int BN_set_word(BIGNUM *a, BN_ULONG w)
514 if (bn_expand(a, (int)sizeof(BN_ULONG) * 8) == NULL)
518 a->top = (w ? 1 : 0);
523 BIGNUM *BN_bin2bn(const unsigned char *s, int len, BIGNUM *ret)
535 /* Skip leading zero's. */
536 for ( ; len > 0 && *s == 0; s++, len--)
543 i = ((n - 1) / BN_BYTES) + 1;
544 m = ((n - 1) % (BN_BYTES));
545 if (bn_wexpand(ret, (int)i) == NULL) {
553 l = (l << 8L) | *(s++);
561 * need to call this due to clear byte at top if avoiding having the top
562 * bit set (-ve number)
568 /* ignore negative */
569 static int bn2binpad(const BIGNUM *a, unsigned char *to, int tolen)
580 /* Add leading zeroes if necessary */
582 memset(to, 0, tolen - i);
586 l = a->d[i / BN_BYTES];
587 *(to++) = (unsigned char)(l >> (8 * (i % BN_BYTES))) & 0xff;
592 int BN_bn2binpad(const BIGNUM *a, unsigned char *to, int tolen)
596 return bn2binpad(a, to, tolen);
599 int BN_bn2bin(const BIGNUM *a, unsigned char *to)
601 return bn2binpad(a, to, -1);
604 BIGNUM *BN_lebin2bn(const unsigned char *s, int len, BIGNUM *ret)
617 /* Skip trailing zeroes. */
618 for ( ; len > 0 && *s == 0; s--, len--)
625 i = ((n - 1) / BN_BYTES) + 1;
626 m = ((n - 1) % (BN_BYTES));
627 if (bn_wexpand(ret, (int)i) == NULL) {
635 l = (l << 8L) | *(s--);
643 * need to call this due to clear byte at top if avoiding having the top
644 * bit set (-ve number)
650 int BN_bn2lebinpad(const BIGNUM *a, unsigned char *to, int tolen)
658 /* Add trailing zeroes if necessary */
660 memset(to + i, 0, tolen - i);
663 l = a->d[i / BN_BYTES];
664 *(to--) = (unsigned char)(l >> (8 * (i % BN_BYTES))) & 0xff;
669 int BN_ucmp(const BIGNUM *a, const BIGNUM *b)
672 BN_ULONG t1, t2, *ap, *bp;
682 for (i = a->top - 1; i >= 0; i--) {
686 return ((t1 > t2) ? 1 : -1);
691 int BN_cmp(const BIGNUM *a, const BIGNUM *b)
697 if ((a == NULL) || (b == NULL)) {
709 if (a->neg != b->neg) {
727 for (i = a->top - 1; i >= 0; i--) {
738 int BN_set_bit(BIGNUM *a, int n)
748 if (bn_wexpand(a, i + 1) == NULL)
750 for (k = a->top; k < i + 1; k++)
755 a->d[i] |= (((BN_ULONG)1) << j);
760 int BN_clear_bit(BIGNUM *a, int n)
773 a->d[i] &= (~(((BN_ULONG)1) << j));
778 int BN_is_bit_set(const BIGNUM *a, int n)
789 return (int)(((a->d[i]) >> j) & ((BN_ULONG)1));
792 int BN_mask_bits(BIGNUM *a, int n)
808 a->d[w] &= ~(BN_MASK2 << b);
814 void BN_set_negative(BIGNUM *a, int b)
816 if (b && !BN_is_zero(a))
822 int bn_cmp_words(const BN_ULONG *a, const BN_ULONG *b, int n)
830 return ((aa > bb) ? 1 : -1);
831 for (i = n - 2; i >= 0; i--) {
835 return ((aa > bb) ? 1 : -1);
841 * Here follows a specialised variants of bn_cmp_words(). It has the
842 * property of performing the operation on arrays of different sizes. The
843 * sizes of those arrays is expressed through cl, which is the common length
844 * ( basicall, min(len(a),len(b)) ), and dl, which is the delta between the
845 * two lengths, calculated as len(a)-len(b). All lengths are the number of
849 int bn_cmp_part_words(const BN_ULONG *a, const BN_ULONG *b, int cl, int dl)
855 for (i = dl; i < 0; i++) {
857 return -1; /* a < b */
861 for (i = dl; i > 0; i--) {
863 return 1; /* a > b */
866 return bn_cmp_words(a, b, cl);
870 * Constant-time conditional swap of a and b.
871 * a and b are swapped if condition is not 0. The code assumes that at most one bit of condition is set.
872 * nwords is the number of words to swap. The code assumes that at least nwords are allocated in both a and b,
873 * and that no more than nwords are used by either a or b.
874 * a and b cannot be the same number
876 void BN_consttime_swap(BN_ULONG condition, BIGNUM *a, BIGNUM *b, int nwords)
881 bn_wcheck_size(a, nwords);
882 bn_wcheck_size(b, nwords);
885 assert((condition & (condition - 1)) == 0);
886 assert(sizeof(BN_ULONG) >= sizeof(int));
888 condition = ((condition - 1) >> (BN_BITS2 - 1)) - 1;
890 t = (a->top ^ b->top) & condition;
894 #define BN_CONSTTIME_SWAP(ind) \
896 t = (a->d[ind] ^ b->d[ind]) & condition; \
903 for (i = 10; i < nwords; i++)
904 BN_CONSTTIME_SWAP(i);
907 BN_CONSTTIME_SWAP(9); /* Fallthrough */
909 BN_CONSTTIME_SWAP(8); /* Fallthrough */
911 BN_CONSTTIME_SWAP(7); /* Fallthrough */
913 BN_CONSTTIME_SWAP(6); /* Fallthrough */
915 BN_CONSTTIME_SWAP(5); /* Fallthrough */
917 BN_CONSTTIME_SWAP(4); /* Fallthrough */
919 BN_CONSTTIME_SWAP(3); /* Fallthrough */
921 BN_CONSTTIME_SWAP(2); /* Fallthrough */
923 BN_CONSTTIME_SWAP(1); /* Fallthrough */
925 BN_CONSTTIME_SWAP(0);
927 #undef BN_CONSTTIME_SWAP
930 /* Bits of security, see SP800-57 */
932 int BN_security_bits(int L, int N)
952 return bits >= secbits ? secbits : bits;
955 void BN_zero_ex(BIGNUM *a)
961 int BN_abs_is_word(const BIGNUM *a, const BN_ULONG w)
963 return ((a->top == 1) && (a->d[0] == w)) || ((w == 0) && (a->top == 0));
966 int BN_is_zero(const BIGNUM *a)
971 int BN_is_one(const BIGNUM *a)
973 return BN_abs_is_word(a, 1) && !a->neg;
976 int BN_is_word(const BIGNUM *a, const BN_ULONG w)
978 return BN_abs_is_word(a, w) && (!w || !a->neg);
981 int BN_is_odd(const BIGNUM *a)
983 return (a->top > 0) && (a->d[0] & 1);
986 int BN_is_negative(const BIGNUM *a)
988 return (a->neg != 0);
991 int BN_to_montgomery(BIGNUM *r, const BIGNUM *a, BN_MONT_CTX *mont,
994 return BN_mod_mul_montgomery(r, a, &(mont->RR), mont, ctx);
997 void BN_with_flags(BIGNUM *dest, const BIGNUM *b, int flags)
1001 dest->dmax = b->dmax;
1003 dest->flags = ((dest->flags & BN_FLG_MALLOCED)
1004 | (b->flags & ~BN_FLG_MALLOCED)
1005 | BN_FLG_STATIC_DATA | flags);
1008 BN_GENCB *BN_GENCB_new(void)
1012 if ((ret = OPENSSL_malloc(sizeof(*ret))) == NULL) {
1013 BNerr(BN_F_BN_GENCB_NEW, ERR_R_MALLOC_FAILURE);
1020 void BN_GENCB_free(BN_GENCB *cb)
1027 void BN_set_flags(BIGNUM *b, int n)
1032 int BN_get_flags(const BIGNUM *b, int n)
1034 return b->flags & n;
1037 /* Populate a BN_GENCB structure with an "old"-style callback */
1038 void BN_GENCB_set_old(BN_GENCB *gencb, void (*callback) (int, int, void *),
1041 BN_GENCB *tmp_gencb = gencb;
1043 tmp_gencb->arg = cb_arg;
1044 tmp_gencb->cb.cb_1 = callback;
1047 /* Populate a BN_GENCB structure with a "new"-style callback */
1048 void BN_GENCB_set(BN_GENCB *gencb, int (*callback) (int, int, BN_GENCB *),
1051 BN_GENCB *tmp_gencb = gencb;
1053 tmp_gencb->arg = cb_arg;
1054 tmp_gencb->cb.cb_2 = callback;
1057 void *BN_GENCB_get_arg(BN_GENCB *cb)
1062 BIGNUM *bn_wexpand(BIGNUM *a, int words)
1064 return (words <= a->dmax) ? a : bn_expand2(a, words);
1067 void bn_correct_top(BIGNUM *a)
1070 int tmp_top = a->top;
1073 for (ftl = &(a->d[tmp_top - 1]); tmp_top > 0; tmp_top--)