117f01e99SJung-uk Kim /*
2640242a5SJung-uk Kim * Copyright 1995-2023 The OpenSSL Project Authors. All Rights Reserved.
317f01e99SJung-uk Kim *
4b077aed3SPierre Pronchery * Licensed under the Apache License 2.0 (the "License"). You may not use
517f01e99SJung-uk Kim * this file except in compliance with the License. You can obtain a copy
617f01e99SJung-uk Kim * in the file LICENSE in the source distribution or at
717f01e99SJung-uk Kim * https://www.openssl.org/source/license.html
817f01e99SJung-uk Kim */
917f01e99SJung-uk Kim
1017f01e99SJung-uk Kim #ifndef OSSL_CRYPTO_BN_LOCAL_H
1117f01e99SJung-uk Kim # define OSSL_CRYPTO_BN_LOCAL_H
1217f01e99SJung-uk Kim
1317f01e99SJung-uk Kim /*
1417f01e99SJung-uk Kim * The EDK2 build doesn't use bn_conf.h; it sets THIRTY_TWO_BIT or
1517f01e99SJung-uk Kim * SIXTY_FOUR_BIT in its own environment since it doesn't re-run our
1617f01e99SJung-uk Kim * Configure script and needs to support both 32-bit and 64-bit.
1717f01e99SJung-uk Kim */
1817f01e99SJung-uk Kim # include <openssl/opensslconf.h>
1917f01e99SJung-uk Kim
2017f01e99SJung-uk Kim # if !defined(OPENSSL_SYS_UEFI)
2117f01e99SJung-uk Kim # include "crypto/bn_conf.h"
2217f01e99SJung-uk Kim # endif
2317f01e99SJung-uk Kim
2417f01e99SJung-uk Kim # include "crypto/bn.h"
25b077aed3SPierre Pronchery # include "internal/cryptlib.h"
26b077aed3SPierre Pronchery # include "internal/numbers.h"
2717f01e99SJung-uk Kim
2817f01e99SJung-uk Kim /*
2917f01e99SJung-uk Kim * These preprocessor symbols control various aspects of the bignum headers
3017f01e99SJung-uk Kim * and library code. They're not defined by any "normal" configuration, as
31b077aed3SPierre Pronchery * they are intended for development and testing purposes. NB: defining
32b077aed3SPierre Pronchery * them can be useful for debugging application code as well as openssl
3317f01e99SJung-uk Kim * itself. BN_DEBUG - turn on various debugging alterations to the bignum
34b077aed3SPierre Pronchery * code BN_RAND_DEBUG - uses random poisoning of unused words to trip up
35b077aed3SPierre Pronchery * mismanagement of bignum internals. Enable BN_RAND_DEBUG is known to
36b077aed3SPierre Pronchery * break some of the OpenSSL tests.
3717f01e99SJung-uk Kim */
38b077aed3SPierre Pronchery # if defined(BN_RAND_DEBUG) && !defined(BN_DEBUG)
39b077aed3SPierre Pronchery # define BN_DEBUG
40b077aed3SPierre Pronchery # endif
41b077aed3SPierre Pronchery # if defined(BN_RAND_DEBUG)
42b077aed3SPierre Pronchery # include <openssl/rand.h>
43b077aed3SPierre Pronchery # endif
44b077aed3SPierre Pronchery
45b077aed3SPierre Pronchery /*
46b077aed3SPierre Pronchery * This should limit the stack usage due to alloca to about 4K.
47b077aed3SPierre Pronchery * BN_SOFT_LIMIT is a soft limit equivalent to 2*OPENSSL_RSA_MAX_MODULUS_BITS.
48b077aed3SPierre Pronchery * Beyond that size bn_mul_mont is no longer used, and the constant time
49b077aed3SPierre Pronchery * assembler code is disabled, due to the blatant alloca and bn_mul_mont usage.
50b077aed3SPierre Pronchery * Note that bn_mul_mont does an alloca that is hidden away in assembly.
51b077aed3SPierre Pronchery * It is not recommended to do computations with numbers exceeding this limit,
52b077aed3SPierre Pronchery * since the result will be highly version dependent:
53b077aed3SPierre Pronchery * While the current OpenSSL version will use non-optimized, but safe code,
54b077aed3SPierre Pronchery * previous versions will use optimized code, that may crash due to unexpected
55b077aed3SPierre Pronchery * stack overflow, and future versions may very well turn this into a hard
56b077aed3SPierre Pronchery * limit.
57b077aed3SPierre Pronchery * Note however, that it is possible to override the size limit using
58b077aed3SPierre Pronchery * "./config -DBN_SOFT_LIMIT=<limit>" if necessary, and the O/S specific
59b077aed3SPierre Pronchery * stack limit is known and taken into consideration.
60b077aed3SPierre Pronchery */
61b077aed3SPierre Pronchery # ifndef BN_SOFT_LIMIT
62b077aed3SPierre Pronchery # define BN_SOFT_LIMIT (4096 / BN_BYTES)
63b077aed3SPierre Pronchery # endif
6417f01e99SJung-uk Kim
6517f01e99SJung-uk Kim # ifndef OPENSSL_SMALL_FOOTPRINT
6617f01e99SJung-uk Kim # define BN_MUL_COMBA
6717f01e99SJung-uk Kim # define BN_SQR_COMBA
6817f01e99SJung-uk Kim # define BN_RECURSION
6917f01e99SJung-uk Kim # endif
7017f01e99SJung-uk Kim
7117f01e99SJung-uk Kim /*
7217f01e99SJung-uk Kim * This next option uses the C libraries (2 word)/(1 word) function. If it is
7317f01e99SJung-uk Kim * not defined, I use my C version (which is slower). The reason for this
7417f01e99SJung-uk Kim * flag is that when the particular C compiler library routine is used, and
7517f01e99SJung-uk Kim * the library is linked with a different compiler, the library is missing.
7617f01e99SJung-uk Kim * This mostly happens when the library is built with gcc and then linked
7717f01e99SJung-uk Kim * using normal cc. This would be a common occurrence because gcc normally
7817f01e99SJung-uk Kim * produces code that is 2 times faster than system compilers for the big
7917f01e99SJung-uk Kim * number stuff. For machines with only one compiler (or shared libraries),
8017f01e99SJung-uk Kim * this should be on. Again this in only really a problem on machines using
8117f01e99SJung-uk Kim * "long long's", are 32bit, and are not using my assembler code.
8217f01e99SJung-uk Kim */
8317f01e99SJung-uk Kim # if defined(OPENSSL_SYS_MSDOS) || defined(OPENSSL_SYS_WINDOWS) || \
8417f01e99SJung-uk Kim defined(OPENSSL_SYS_WIN32) || defined(linux)
8517f01e99SJung-uk Kim # define BN_DIV2W
8617f01e99SJung-uk Kim # endif
8717f01e99SJung-uk Kim
8817f01e99SJung-uk Kim /*
8917f01e99SJung-uk Kim * 64-bit processor with LP64 ABI
9017f01e99SJung-uk Kim */
9117f01e99SJung-uk Kim # ifdef SIXTY_FOUR_BIT_LONG
9217f01e99SJung-uk Kim # define BN_ULLONG unsigned long long
9317f01e99SJung-uk Kim # define BN_BITS4 32
9417f01e99SJung-uk Kim # define BN_MASK2 (0xffffffffffffffffL)
9517f01e99SJung-uk Kim # define BN_MASK2l (0xffffffffL)
9617f01e99SJung-uk Kim # define BN_MASK2h (0xffffffff00000000L)
9717f01e99SJung-uk Kim # define BN_MASK2h1 (0xffffffff80000000L)
9817f01e99SJung-uk Kim # define BN_DEC_CONV (10000000000000000000UL)
9917f01e99SJung-uk Kim # define BN_DEC_NUM 19
10017f01e99SJung-uk Kim # define BN_DEC_FMT1 "%lu"
10117f01e99SJung-uk Kim # define BN_DEC_FMT2 "%019lu"
10217f01e99SJung-uk Kim # endif
10317f01e99SJung-uk Kim
10417f01e99SJung-uk Kim /*
10517f01e99SJung-uk Kim * 64-bit processor other than LP64 ABI
10617f01e99SJung-uk Kim */
10717f01e99SJung-uk Kim # ifdef SIXTY_FOUR_BIT
10817f01e99SJung-uk Kim # undef BN_LLONG
10917f01e99SJung-uk Kim # undef BN_ULLONG
11017f01e99SJung-uk Kim # define BN_BITS4 32
11117f01e99SJung-uk Kim # define BN_MASK2 (0xffffffffffffffffLL)
11217f01e99SJung-uk Kim # define BN_MASK2l (0xffffffffL)
11317f01e99SJung-uk Kim # define BN_MASK2h (0xffffffff00000000LL)
11417f01e99SJung-uk Kim # define BN_MASK2h1 (0xffffffff80000000LL)
11517f01e99SJung-uk Kim # define BN_DEC_CONV (10000000000000000000ULL)
11617f01e99SJung-uk Kim # define BN_DEC_NUM 19
11717f01e99SJung-uk Kim # define BN_DEC_FMT1 "%llu"
11817f01e99SJung-uk Kim # define BN_DEC_FMT2 "%019llu"
11917f01e99SJung-uk Kim # endif
12017f01e99SJung-uk Kim
12117f01e99SJung-uk Kim # ifdef THIRTY_TWO_BIT
12217f01e99SJung-uk Kim # ifdef BN_LLONG
12317f01e99SJung-uk Kim # if defined(_WIN32) && !defined(__GNUC__)
12417f01e99SJung-uk Kim # define BN_ULLONG unsigned __int64
12517f01e99SJung-uk Kim # else
12617f01e99SJung-uk Kim # define BN_ULLONG unsigned long long
12717f01e99SJung-uk Kim # endif
12817f01e99SJung-uk Kim # endif
12917f01e99SJung-uk Kim # define BN_BITS4 16
13017f01e99SJung-uk Kim # define BN_MASK2 (0xffffffffL)
13117f01e99SJung-uk Kim # define BN_MASK2l (0xffff)
13217f01e99SJung-uk Kim # define BN_MASK2h1 (0xffff8000L)
13317f01e99SJung-uk Kim # define BN_MASK2h (0xffff0000L)
13417f01e99SJung-uk Kim # define BN_DEC_CONV (1000000000L)
13517f01e99SJung-uk Kim # define BN_DEC_NUM 9
13617f01e99SJung-uk Kim # define BN_DEC_FMT1 "%u"
13717f01e99SJung-uk Kim # define BN_DEC_FMT2 "%09u"
13817f01e99SJung-uk Kim # endif
13917f01e99SJung-uk Kim
14017f01e99SJung-uk Kim
14117f01e99SJung-uk Kim /*-
14217f01e99SJung-uk Kim * Bignum consistency macros
14317f01e99SJung-uk Kim * There is one "API" macro, bn_fix_top(), for stripping leading zeroes from
14417f01e99SJung-uk Kim * bignum data after direct manipulations on the data. There is also an
14517f01e99SJung-uk Kim * "internal" macro, bn_check_top(), for verifying that there are no leading
14617f01e99SJung-uk Kim * zeroes. Unfortunately, some auditing is required due to the fact that
14717f01e99SJung-uk Kim * bn_fix_top() has become an overabused duct-tape because bignum data is
14817f01e99SJung-uk Kim * occasionally passed around in an inconsistent state. So the following
14917f01e99SJung-uk Kim * changes have been made to sort this out;
15017f01e99SJung-uk Kim * - bn_fix_top()s implementation has been moved to bn_correct_top()
15117f01e99SJung-uk Kim * - if BN_DEBUG isn't defined, bn_fix_top() maps to bn_correct_top(), and
15217f01e99SJung-uk Kim * bn_check_top() is as before.
15317f01e99SJung-uk Kim * - if BN_DEBUG *is* defined;
15417f01e99SJung-uk Kim * - bn_check_top() tries to pollute unused words even if the bignum 'top' is
155b077aed3SPierre Pronchery * consistent. (ed: only if BN_RAND_DEBUG is defined)
15617f01e99SJung-uk Kim * - bn_fix_top() maps to bn_check_top() rather than "fixing" anything.
15717f01e99SJung-uk Kim * The idea is to have debug builds flag up inconsistent bignums when they
15817f01e99SJung-uk Kim * occur. If that occurs in a bn_fix_top(), we examine the code in question; if
15917f01e99SJung-uk Kim * the use of bn_fix_top() was appropriate (ie. it follows directly after code
16017f01e99SJung-uk Kim * that manipulates the bignum) it is converted to bn_correct_top(), and if it
16117f01e99SJung-uk Kim * was not appropriate, we convert it permanently to bn_check_top() and track
16217f01e99SJung-uk Kim * down the cause of the bug. Eventually, no internal code should be using the
16317f01e99SJung-uk Kim * bn_fix_top() macro. External applications and libraries should try this with
16417f01e99SJung-uk Kim * their own code too, both in terms of building against the openssl headers
16517f01e99SJung-uk Kim * with BN_DEBUG defined *and* linking with a version of OpenSSL built with it
16617f01e99SJung-uk Kim * defined. This not only improves external code, it provides more test
16717f01e99SJung-uk Kim * coverage for openssl's own code.
16817f01e99SJung-uk Kim */
16917f01e99SJung-uk Kim
17017f01e99SJung-uk Kim # ifdef BN_DEBUG
17117f01e99SJung-uk Kim /*
17217f01e99SJung-uk Kim * The new BN_FLG_FIXED_TOP flag marks vectors that were not treated with
17317f01e99SJung-uk Kim * bn_correct_top, in other words such vectors are permitted to have zeros
17417f01e99SJung-uk Kim * in most significant limbs. Such vectors are used internally to achieve
17517f01e99SJung-uk Kim * execution time invariance for critical operations with private keys.
17617f01e99SJung-uk Kim * It's BN_DEBUG-only flag, because user application is not supposed to
17717f01e99SJung-uk Kim * observe it anyway. Moreover, optimizing compiler would actually remove
17817f01e99SJung-uk Kim * all operations manipulating the bit in question in non-BN_DEBUG build.
17917f01e99SJung-uk Kim */
18017f01e99SJung-uk Kim # define BN_FLG_FIXED_TOP 0x10000
181b077aed3SPierre Pronchery # ifdef BN_RAND_DEBUG
18217f01e99SJung-uk Kim # define bn_pollute(a) \
18317f01e99SJung-uk Kim do { \
18417f01e99SJung-uk Kim const BIGNUM *_bnum1 = (a); \
18517f01e99SJung-uk Kim if (_bnum1->top < _bnum1->dmax) { \
18617f01e99SJung-uk Kim unsigned char _tmp_char; \
18717f01e99SJung-uk Kim /* We cast away const without the compiler knowing, any \
18817f01e99SJung-uk Kim * *genuinely* constant variables that aren't mutable \
18917f01e99SJung-uk Kim * wouldn't be constructed with top!=dmax. */ \
19017f01e99SJung-uk Kim BN_ULONG *_not_const; \
19117f01e99SJung-uk Kim memcpy(&_not_const, &_bnum1->d, sizeof(_not_const)); \
192b077aed3SPierre Pronchery (void)RAND_bytes(&_tmp_char, 1); /* Debug only - safe to ignore error return */\
19317f01e99SJung-uk Kim memset(_not_const + _bnum1->top, _tmp_char, \
19417f01e99SJung-uk Kim sizeof(*_not_const) * (_bnum1->dmax - _bnum1->top)); \
19517f01e99SJung-uk Kim } \
19617f01e99SJung-uk Kim } while(0)
19717f01e99SJung-uk Kim # else
19817f01e99SJung-uk Kim # define bn_pollute(a)
19917f01e99SJung-uk Kim # endif
20017f01e99SJung-uk Kim # define bn_check_top(a) \
20117f01e99SJung-uk Kim do { \
20217f01e99SJung-uk Kim const BIGNUM *_bnum2 = (a); \
20317f01e99SJung-uk Kim if (_bnum2 != NULL) { \
20417f01e99SJung-uk Kim int _top = _bnum2->top; \
20517f01e99SJung-uk Kim (void)ossl_assert((_top == 0 && !_bnum2->neg) || \
20617f01e99SJung-uk Kim (_top && ((_bnum2->flags & BN_FLG_FIXED_TOP) \
20717f01e99SJung-uk Kim || _bnum2->d[_top - 1] != 0))); \
20817f01e99SJung-uk Kim bn_pollute(_bnum2); \
20917f01e99SJung-uk Kim } \
21017f01e99SJung-uk Kim } while(0)
21117f01e99SJung-uk Kim
21217f01e99SJung-uk Kim # define bn_fix_top(a) bn_check_top(a)
21317f01e99SJung-uk Kim
21417f01e99SJung-uk Kim # define bn_check_size(bn, bits) bn_wcheck_size(bn, ((bits+BN_BITS2-1))/BN_BITS2)
21517f01e99SJung-uk Kim # define bn_wcheck_size(bn, words) \
21617f01e99SJung-uk Kim do { \
21717f01e99SJung-uk Kim const BIGNUM *_bnum2 = (bn); \
21817f01e99SJung-uk Kim assert((words) <= (_bnum2)->dmax && \
21917f01e99SJung-uk Kim (words) >= (_bnum2)->top); \
22017f01e99SJung-uk Kim /* avoid unused variable warning with NDEBUG */ \
22117f01e99SJung-uk Kim (void)(_bnum2); \
22217f01e99SJung-uk Kim } while(0)
22317f01e99SJung-uk Kim
22417f01e99SJung-uk Kim # else /* !BN_DEBUG */
22517f01e99SJung-uk Kim
22617f01e99SJung-uk Kim # define BN_FLG_FIXED_TOP 0
22717f01e99SJung-uk Kim # define bn_pollute(a)
22817f01e99SJung-uk Kim # define bn_check_top(a)
22917f01e99SJung-uk Kim # define bn_fix_top(a) bn_correct_top(a)
23017f01e99SJung-uk Kim # define bn_check_size(bn, bits)
23117f01e99SJung-uk Kim # define bn_wcheck_size(bn, words)
23217f01e99SJung-uk Kim
23317f01e99SJung-uk Kim # endif
23417f01e99SJung-uk Kim
23517f01e99SJung-uk Kim BN_ULONG bn_mul_add_words(BN_ULONG *rp, const BN_ULONG *ap, int num,
23617f01e99SJung-uk Kim BN_ULONG w);
23717f01e99SJung-uk Kim BN_ULONG bn_mul_words(BN_ULONG *rp, const BN_ULONG *ap, int num, BN_ULONG w);
23817f01e99SJung-uk Kim void bn_sqr_words(BN_ULONG *rp, const BN_ULONG *ap, int num);
23917f01e99SJung-uk Kim BN_ULONG bn_div_words(BN_ULONG h, BN_ULONG l, BN_ULONG d);
24017f01e99SJung-uk Kim BN_ULONG bn_add_words(BN_ULONG *rp, const BN_ULONG *ap, const BN_ULONG *bp,
24117f01e99SJung-uk Kim int num);
24217f01e99SJung-uk Kim BN_ULONG bn_sub_words(BN_ULONG *rp, const BN_ULONG *ap, const BN_ULONG *bp,
24317f01e99SJung-uk Kim int num);
24417f01e99SJung-uk Kim
24517f01e99SJung-uk Kim struct bignum_st {
24617f01e99SJung-uk Kim BN_ULONG *d; /* Pointer to an array of 'BN_BITS2' bit
24717f01e99SJung-uk Kim * chunks. */
24817f01e99SJung-uk Kim int top; /* Index of last used d +1. */
24917f01e99SJung-uk Kim /* The next are internal book keeping for bn_expand. */
25017f01e99SJung-uk Kim int dmax; /* Size of the d array. */
25117f01e99SJung-uk Kim int neg; /* one if the number is negative */
25217f01e99SJung-uk Kim int flags;
25317f01e99SJung-uk Kim };
25417f01e99SJung-uk Kim
25517f01e99SJung-uk Kim /* Used for montgomery multiplication */
25617f01e99SJung-uk Kim struct bn_mont_ctx_st {
25717f01e99SJung-uk Kim int ri; /* number of bits in R */
25817f01e99SJung-uk Kim BIGNUM RR; /* used to convert to montgomery form,
25917f01e99SJung-uk Kim possibly zero-padded */
26017f01e99SJung-uk Kim BIGNUM N; /* The modulus */
26117f01e99SJung-uk Kim BIGNUM Ni; /* R*(1/R mod N) - N*Ni = 1 (Ni is only
26217f01e99SJung-uk Kim * stored for bignum algorithm) */
26317f01e99SJung-uk Kim BN_ULONG n0[2]; /* least significant word(s) of Ni; (type
26417f01e99SJung-uk Kim * changed with 0.9.9, was "BN_ULONG n0;"
26517f01e99SJung-uk Kim * before) */
26617f01e99SJung-uk Kim int flags;
26717f01e99SJung-uk Kim };
26817f01e99SJung-uk Kim
26917f01e99SJung-uk Kim /*
27017f01e99SJung-uk Kim * Used for reciprocal division/mod functions It cannot be shared between
27117f01e99SJung-uk Kim * threads
27217f01e99SJung-uk Kim */
27317f01e99SJung-uk Kim struct bn_recp_ctx_st {
27417f01e99SJung-uk Kim BIGNUM N; /* the divisor */
27517f01e99SJung-uk Kim BIGNUM Nr; /* the reciprocal */
27617f01e99SJung-uk Kim int num_bits;
27717f01e99SJung-uk Kim int shift;
27817f01e99SJung-uk Kim int flags;
27917f01e99SJung-uk Kim };
28017f01e99SJung-uk Kim
28117f01e99SJung-uk Kim /* Used for slow "generation" functions. */
28217f01e99SJung-uk Kim struct bn_gencb_st {
28317f01e99SJung-uk Kim unsigned int ver; /* To handle binary (in)compatibility */
28417f01e99SJung-uk Kim void *arg; /* callback-specific data */
28517f01e99SJung-uk Kim union {
28617f01e99SJung-uk Kim /* if (ver==1) - handles old style callbacks */
28717f01e99SJung-uk Kim void (*cb_1) (int, int, void *);
28817f01e99SJung-uk Kim /* if (ver==2) - new callback style */
28917f01e99SJung-uk Kim int (*cb_2) (int, int, BN_GENCB *);
29017f01e99SJung-uk Kim } cb;
29117f01e99SJung-uk Kim };
29217f01e99SJung-uk Kim
29317f01e99SJung-uk Kim /*-
29417f01e99SJung-uk Kim * BN_window_bits_for_exponent_size -- macro for sliding window mod_exp functions
29517f01e99SJung-uk Kim *
29617f01e99SJung-uk Kim *
29717f01e99SJung-uk Kim * For window size 'w' (w >= 2) and a random 'b' bits exponent,
29817f01e99SJung-uk Kim * the number of multiplications is a constant plus on average
29917f01e99SJung-uk Kim *
30017f01e99SJung-uk Kim * 2^(w-1) + (b-w)/(w+1);
30117f01e99SJung-uk Kim *
30217f01e99SJung-uk Kim * here 2^(w-1) is for precomputing the table (we actually need
30317f01e99SJung-uk Kim * entries only for windows that have the lowest bit set), and
30417f01e99SJung-uk Kim * (b-w)/(w+1) is an approximation for the expected number of
30517f01e99SJung-uk Kim * w-bit windows, not counting the first one.
30617f01e99SJung-uk Kim *
30717f01e99SJung-uk Kim * Thus we should use
30817f01e99SJung-uk Kim *
30917f01e99SJung-uk Kim * w >= 6 if b > 671
31017f01e99SJung-uk Kim * w = 5 if 671 > b > 239
31117f01e99SJung-uk Kim * w = 4 if 239 > b > 79
31217f01e99SJung-uk Kim * w = 3 if 79 > b > 23
31317f01e99SJung-uk Kim * w <= 2 if 23 > b
31417f01e99SJung-uk Kim *
31517f01e99SJung-uk Kim * (with draws in between). Very small exponents are often selected
31617f01e99SJung-uk Kim * with low Hamming weight, so we use w = 1 for b <= 23.
31717f01e99SJung-uk Kim */
31817f01e99SJung-uk Kim # define BN_window_bits_for_exponent_size(b) \
31917f01e99SJung-uk Kim ((b) > 671 ? 6 : \
32017f01e99SJung-uk Kim (b) > 239 ? 5 : \
32117f01e99SJung-uk Kim (b) > 79 ? 4 : \
32217f01e99SJung-uk Kim (b) > 23 ? 3 : 1)
32317f01e99SJung-uk Kim
32417f01e99SJung-uk Kim /*
32517f01e99SJung-uk Kim * BN_mod_exp_mont_consttime is based on the assumption that the L1 data cache
32617f01e99SJung-uk Kim * line width of the target processor is at least the following value.
32717f01e99SJung-uk Kim */
32817f01e99SJung-uk Kim # define MOD_EXP_CTIME_MIN_CACHE_LINE_WIDTH ( 64 )
32917f01e99SJung-uk Kim # define MOD_EXP_CTIME_MIN_CACHE_LINE_MASK (MOD_EXP_CTIME_MIN_CACHE_LINE_WIDTH - 1)
33017f01e99SJung-uk Kim
33117f01e99SJung-uk Kim /*
33217f01e99SJung-uk Kim * Window sizes optimized for fixed window size modular exponentiation
33317f01e99SJung-uk Kim * algorithm (BN_mod_exp_mont_consttime). To achieve the security goals of
33417f01e99SJung-uk Kim * BN_mode_exp_mont_consttime, the maximum size of the window must not exceed
33517f01e99SJung-uk Kim * log_2(MOD_EXP_CTIME_MIN_CACHE_LINE_WIDTH). Window size thresholds are
33617f01e99SJung-uk Kim * defined for cache line sizes of 32 and 64, cache line sizes where
33717f01e99SJung-uk Kim * log_2(32)=5 and log_2(64)=6 respectively. A window size of 7 should only be
33817f01e99SJung-uk Kim * used on processors that have a 128 byte or greater cache line size.
33917f01e99SJung-uk Kim */
34017f01e99SJung-uk Kim # if MOD_EXP_CTIME_MIN_CACHE_LINE_WIDTH == 64
34117f01e99SJung-uk Kim
34217f01e99SJung-uk Kim # define BN_window_bits_for_ctime_exponent_size(b) \
34317f01e99SJung-uk Kim ((b) > 937 ? 6 : \
34417f01e99SJung-uk Kim (b) > 306 ? 5 : \
34517f01e99SJung-uk Kim (b) > 89 ? 4 : \
34617f01e99SJung-uk Kim (b) > 22 ? 3 : 1)
34717f01e99SJung-uk Kim # define BN_MAX_WINDOW_BITS_FOR_CTIME_EXPONENT_SIZE (6)
34817f01e99SJung-uk Kim
34917f01e99SJung-uk Kim # elif MOD_EXP_CTIME_MIN_CACHE_LINE_WIDTH == 32
35017f01e99SJung-uk Kim
35117f01e99SJung-uk Kim # define BN_window_bits_for_ctime_exponent_size(b) \
35217f01e99SJung-uk Kim ((b) > 306 ? 5 : \
35317f01e99SJung-uk Kim (b) > 89 ? 4 : \
35417f01e99SJung-uk Kim (b) > 22 ? 3 : 1)
35517f01e99SJung-uk Kim # define BN_MAX_WINDOW_BITS_FOR_CTIME_EXPONENT_SIZE (5)
35617f01e99SJung-uk Kim
35717f01e99SJung-uk Kim # endif
35817f01e99SJung-uk Kim
35917f01e99SJung-uk Kim /* Pentium pro 16,16,16,32,64 */
36017f01e99SJung-uk Kim /* Alpha 16,16,16,16.64 */
36117f01e99SJung-uk Kim # define BN_MULL_SIZE_NORMAL (16)/* 32 */
36217f01e99SJung-uk Kim # define BN_MUL_RECURSIVE_SIZE_NORMAL (16)/* 32 less than */
36317f01e99SJung-uk Kim # define BN_SQR_RECURSIVE_SIZE_NORMAL (16)/* 32 */
36417f01e99SJung-uk Kim # define BN_MUL_LOW_RECURSIVE_SIZE_NORMAL (32)/* 32 */
36517f01e99SJung-uk Kim # define BN_MONT_CTX_SET_SIZE_WORD (64)/* 32 */
36617f01e99SJung-uk Kim
36717f01e99SJung-uk Kim # if !defined(OPENSSL_NO_ASM) && !defined(OPENSSL_NO_INLINE_ASM) && !defined(PEDANTIC)
36817f01e99SJung-uk Kim /*
36917f01e99SJung-uk Kim * BN_UMULT_HIGH section.
37017f01e99SJung-uk Kim * If the compiler doesn't support 2*N integer type, then you have to
37117f01e99SJung-uk Kim * replace every N*N multiplication with 4 (N/2)*(N/2) accompanied by some
37217f01e99SJung-uk Kim * shifts and additions which unavoidably results in severe performance
37317f01e99SJung-uk Kim * penalties. Of course provided that the hardware is capable of producing
37417f01e99SJung-uk Kim * 2*N result... That's when you normally start considering assembler
37517f01e99SJung-uk Kim * implementation. However! It should be pointed out that some CPUs (e.g.,
37617f01e99SJung-uk Kim * PowerPC, Alpha, and IA-64) provide *separate* instruction calculating
37717f01e99SJung-uk Kim * the upper half of the product placing the result into a general
37817f01e99SJung-uk Kim * purpose register. Now *if* the compiler supports inline assembler,
37917f01e99SJung-uk Kim * then it's not impossible to implement the "bignum" routines (and have
38017f01e99SJung-uk Kim * the compiler optimize 'em) exhibiting "native" performance in C. That's
38117f01e99SJung-uk Kim * what BN_UMULT_HIGH macro is about:-) Note that more recent compilers do
38217f01e99SJung-uk Kim * support 2*64 integer type, which is also used here.
38317f01e99SJung-uk Kim */
38417f01e99SJung-uk Kim # if defined(__SIZEOF_INT128__) && __SIZEOF_INT128__==16 && \
38517f01e99SJung-uk Kim (defined(SIXTY_FOUR_BIT) || defined(SIXTY_FOUR_BIT_LONG))
386b077aed3SPierre Pronchery # define BN_UMULT_HIGH(a,b) (((uint128_t)(a)*(b))>>64)
38717f01e99SJung-uk Kim # define BN_UMULT_LOHI(low,high,a,b) ({ \
388b077aed3SPierre Pronchery uint128_t ret=(uint128_t)(a)*(b); \
38917f01e99SJung-uk Kim (high)=ret>>64; (low)=ret; })
39017f01e99SJung-uk Kim # elif defined(__alpha) && (defined(SIXTY_FOUR_BIT_LONG) || defined(SIXTY_FOUR_BIT))
39117f01e99SJung-uk Kim # if defined(__DECC)
39217f01e99SJung-uk Kim # include <c_asm.h>
39317f01e99SJung-uk Kim # define BN_UMULT_HIGH(a,b) (BN_ULONG)asm("umulh %a0,%a1,%v0",(a),(b))
39417f01e99SJung-uk Kim # elif defined(__GNUC__) && __GNUC__>=2
39517f01e99SJung-uk Kim # define BN_UMULT_HIGH(a,b) ({ \
39617f01e99SJung-uk Kim register BN_ULONG ret; \
39717f01e99SJung-uk Kim asm ("umulh %1,%2,%0" \
39817f01e99SJung-uk Kim : "=r"(ret) \
39917f01e99SJung-uk Kim : "r"(a), "r"(b)); \
40017f01e99SJung-uk Kim ret; })
40117f01e99SJung-uk Kim # endif /* compiler */
40217f01e99SJung-uk Kim # elif defined(_ARCH_PPC64) && defined(SIXTY_FOUR_BIT_LONG)
40317f01e99SJung-uk Kim # if defined(__GNUC__) && __GNUC__>=2
40417f01e99SJung-uk Kim # define BN_UMULT_HIGH(a,b) ({ \
40517f01e99SJung-uk Kim register BN_ULONG ret; \
40617f01e99SJung-uk Kim asm ("mulhdu %0,%1,%2" \
40717f01e99SJung-uk Kim : "=r"(ret) \
40817f01e99SJung-uk Kim : "r"(a), "r"(b)); \
40917f01e99SJung-uk Kim ret; })
41017f01e99SJung-uk Kim # endif /* compiler */
41117f01e99SJung-uk Kim # elif (defined(__x86_64) || defined(__x86_64__)) && \
41217f01e99SJung-uk Kim (defined(SIXTY_FOUR_BIT_LONG) || defined(SIXTY_FOUR_BIT))
41317f01e99SJung-uk Kim # if defined(__GNUC__) && __GNUC__>=2
41417f01e99SJung-uk Kim # define BN_UMULT_HIGH(a,b) ({ \
41517f01e99SJung-uk Kim register BN_ULONG ret,discard; \
41617f01e99SJung-uk Kim asm ("mulq %3" \
41717f01e99SJung-uk Kim : "=a"(discard),"=d"(ret) \
41817f01e99SJung-uk Kim : "a"(a), "g"(b) \
41917f01e99SJung-uk Kim : "cc"); \
42017f01e99SJung-uk Kim ret; })
42117f01e99SJung-uk Kim # define BN_UMULT_LOHI(low,high,a,b) \
42217f01e99SJung-uk Kim asm ("mulq %3" \
42317f01e99SJung-uk Kim : "=a"(low),"=d"(high) \
42417f01e99SJung-uk Kim : "a"(a),"g"(b) \
42517f01e99SJung-uk Kim : "cc");
42617f01e99SJung-uk Kim # endif
42717f01e99SJung-uk Kim # elif (defined(_M_AMD64) || defined(_M_X64)) && defined(SIXTY_FOUR_BIT)
42817f01e99SJung-uk Kim # if defined(_MSC_VER) && _MSC_VER>=1400
42917f01e99SJung-uk Kim unsigned __int64 __umulh(unsigned __int64 a, unsigned __int64 b);
43017f01e99SJung-uk Kim unsigned __int64 _umul128(unsigned __int64 a, unsigned __int64 b,
43117f01e99SJung-uk Kim unsigned __int64 *h);
43217f01e99SJung-uk Kim # pragma intrinsic(__umulh,_umul128)
43317f01e99SJung-uk Kim # define BN_UMULT_HIGH(a,b) __umulh((a),(b))
43417f01e99SJung-uk Kim # define BN_UMULT_LOHI(low,high,a,b) ((low)=_umul128((a),(b),&(high)))
43517f01e99SJung-uk Kim # endif
43617f01e99SJung-uk Kim # elif defined(__mips) && (defined(SIXTY_FOUR_BIT) || defined(SIXTY_FOUR_BIT_LONG))
43717f01e99SJung-uk Kim # if defined(__GNUC__) && __GNUC__>=2
43817f01e99SJung-uk Kim # define BN_UMULT_HIGH(a,b) ({ \
43917f01e99SJung-uk Kim register BN_ULONG ret; \
44017f01e99SJung-uk Kim asm ("dmultu %1,%2" \
44117f01e99SJung-uk Kim : "=h"(ret) \
44217f01e99SJung-uk Kim : "r"(a), "r"(b) : "l"); \
44317f01e99SJung-uk Kim ret; })
44417f01e99SJung-uk Kim # define BN_UMULT_LOHI(low,high,a,b) \
44517f01e99SJung-uk Kim asm ("dmultu %2,%3" \
44617f01e99SJung-uk Kim : "=l"(low),"=h"(high) \
44717f01e99SJung-uk Kim : "r"(a), "r"(b));
44817f01e99SJung-uk Kim # endif
44917f01e99SJung-uk Kim # elif defined(__aarch64__) && defined(SIXTY_FOUR_BIT_LONG)
45017f01e99SJung-uk Kim # if defined(__GNUC__) && __GNUC__>=2
45117f01e99SJung-uk Kim # define BN_UMULT_HIGH(a,b) ({ \
45217f01e99SJung-uk Kim register BN_ULONG ret; \
45317f01e99SJung-uk Kim asm ("umulh %0,%1,%2" \
45417f01e99SJung-uk Kim : "=r"(ret) \
45517f01e99SJung-uk Kim : "r"(a), "r"(b)); \
45617f01e99SJung-uk Kim ret; })
45717f01e99SJung-uk Kim # endif
45817f01e99SJung-uk Kim # endif /* cpu */
45917f01e99SJung-uk Kim # endif /* OPENSSL_NO_ASM */
46017f01e99SJung-uk Kim
461b077aed3SPierre Pronchery # ifdef BN_RAND_DEBUG
46217f01e99SJung-uk Kim # define bn_clear_top2max(a) \
46317f01e99SJung-uk Kim { \
46417f01e99SJung-uk Kim int ind = (a)->dmax - (a)->top; \
46517f01e99SJung-uk Kim BN_ULONG *ftl = &(a)->d[(a)->top-1]; \
46617f01e99SJung-uk Kim for (; ind != 0; ind--) \
46717f01e99SJung-uk Kim *(++ftl) = 0x0; \
46817f01e99SJung-uk Kim }
46917f01e99SJung-uk Kim # else
47017f01e99SJung-uk Kim # define bn_clear_top2max(a)
47117f01e99SJung-uk Kim # endif
47217f01e99SJung-uk Kim
47317f01e99SJung-uk Kim # ifdef BN_LLONG
47417f01e99SJung-uk Kim /*******************************************************************
47517f01e99SJung-uk Kim * Using the long long type, has to be twice as wide as BN_ULONG...
47617f01e99SJung-uk Kim */
47717f01e99SJung-uk Kim # define Lw(t) (((BN_ULONG)(t))&BN_MASK2)
47817f01e99SJung-uk Kim # define Hw(t) (((BN_ULONG)((t)>>BN_BITS2))&BN_MASK2)
47917f01e99SJung-uk Kim
48017f01e99SJung-uk Kim # define mul_add(r,a,w,c) { \
48117f01e99SJung-uk Kim BN_ULLONG t; \
48217f01e99SJung-uk Kim t=(BN_ULLONG)w * (a) + (r) + (c); \
48317f01e99SJung-uk Kim (r)= Lw(t); \
48417f01e99SJung-uk Kim (c)= Hw(t); \
48517f01e99SJung-uk Kim }
48617f01e99SJung-uk Kim
48717f01e99SJung-uk Kim # define mul(r,a,w,c) { \
48817f01e99SJung-uk Kim BN_ULLONG t; \
48917f01e99SJung-uk Kim t=(BN_ULLONG)w * (a) + (c); \
49017f01e99SJung-uk Kim (r)= Lw(t); \
49117f01e99SJung-uk Kim (c)= Hw(t); \
49217f01e99SJung-uk Kim }
49317f01e99SJung-uk Kim
49417f01e99SJung-uk Kim # define sqr(r0,r1,a) { \
49517f01e99SJung-uk Kim BN_ULLONG t; \
49617f01e99SJung-uk Kim t=(BN_ULLONG)(a)*(a); \
49717f01e99SJung-uk Kim (r0)=Lw(t); \
49817f01e99SJung-uk Kim (r1)=Hw(t); \
49917f01e99SJung-uk Kim }
50017f01e99SJung-uk Kim
50117f01e99SJung-uk Kim # elif defined(BN_UMULT_LOHI)
50217f01e99SJung-uk Kim # define mul_add(r,a,w,c) { \
50317f01e99SJung-uk Kim BN_ULONG high,low,ret,tmp=(a); \
50417f01e99SJung-uk Kim ret = (r); \
50517f01e99SJung-uk Kim BN_UMULT_LOHI(low,high,w,tmp); \
50617f01e99SJung-uk Kim ret += (c); \
5078f1ef87aSJung-uk Kim (c) = (ret<(c)); \
50817f01e99SJung-uk Kim (c) += high; \
50917f01e99SJung-uk Kim ret += low; \
5108f1ef87aSJung-uk Kim (c) += (ret<low); \
51117f01e99SJung-uk Kim (r) = ret; \
51217f01e99SJung-uk Kim }
51317f01e99SJung-uk Kim
51417f01e99SJung-uk Kim # define mul(r,a,w,c) { \
51517f01e99SJung-uk Kim BN_ULONG high,low,ret,ta=(a); \
51617f01e99SJung-uk Kim BN_UMULT_LOHI(low,high,w,ta); \
51717f01e99SJung-uk Kim ret = low + (c); \
51817f01e99SJung-uk Kim (c) = high; \
5198f1ef87aSJung-uk Kim (c) += (ret<low); \
52017f01e99SJung-uk Kim (r) = ret; \
52117f01e99SJung-uk Kim }
52217f01e99SJung-uk Kim
52317f01e99SJung-uk Kim # define sqr(r0,r1,a) { \
52417f01e99SJung-uk Kim BN_ULONG tmp=(a); \
52517f01e99SJung-uk Kim BN_UMULT_LOHI(r0,r1,tmp,tmp); \
52617f01e99SJung-uk Kim }
52717f01e99SJung-uk Kim
52817f01e99SJung-uk Kim # elif defined(BN_UMULT_HIGH)
52917f01e99SJung-uk Kim # define mul_add(r,a,w,c) { \
53017f01e99SJung-uk Kim BN_ULONG high,low,ret,tmp=(a); \
53117f01e99SJung-uk Kim ret = (r); \
53217f01e99SJung-uk Kim high= BN_UMULT_HIGH(w,tmp); \
53317f01e99SJung-uk Kim ret += (c); \
53417f01e99SJung-uk Kim low = (w) * tmp; \
5358f1ef87aSJung-uk Kim (c) = (ret<(c)); \
53617f01e99SJung-uk Kim (c) += high; \
53717f01e99SJung-uk Kim ret += low; \
5388f1ef87aSJung-uk Kim (c) += (ret<low); \
53917f01e99SJung-uk Kim (r) = ret; \
54017f01e99SJung-uk Kim }
54117f01e99SJung-uk Kim
54217f01e99SJung-uk Kim # define mul(r,a,w,c) { \
54317f01e99SJung-uk Kim BN_ULONG high,low,ret,ta=(a); \
54417f01e99SJung-uk Kim low = (w) * ta; \
54517f01e99SJung-uk Kim high= BN_UMULT_HIGH(w,ta); \
54617f01e99SJung-uk Kim ret = low + (c); \
54717f01e99SJung-uk Kim (c) = high; \
5488f1ef87aSJung-uk Kim (c) += (ret<low); \
54917f01e99SJung-uk Kim (r) = ret; \
55017f01e99SJung-uk Kim }
55117f01e99SJung-uk Kim
55217f01e99SJung-uk Kim # define sqr(r0,r1,a) { \
55317f01e99SJung-uk Kim BN_ULONG tmp=(a); \
55417f01e99SJung-uk Kim (r0) = tmp * tmp; \
55517f01e99SJung-uk Kim (r1) = BN_UMULT_HIGH(tmp,tmp); \
55617f01e99SJung-uk Kim }
55717f01e99SJung-uk Kim
55817f01e99SJung-uk Kim # else
55917f01e99SJung-uk Kim /*************************************************************
56017f01e99SJung-uk Kim * No long long type
56117f01e99SJung-uk Kim */
56217f01e99SJung-uk Kim
56317f01e99SJung-uk Kim # define LBITS(a) ((a)&BN_MASK2l)
56417f01e99SJung-uk Kim # define HBITS(a) (((a)>>BN_BITS4)&BN_MASK2l)
56517f01e99SJung-uk Kim # define L2HBITS(a) (((a)<<BN_BITS4)&BN_MASK2)
56617f01e99SJung-uk Kim
56717f01e99SJung-uk Kim # define LLBITS(a) ((a)&BN_MASKl)
56817f01e99SJung-uk Kim # define LHBITS(a) (((a)>>BN_BITS2)&BN_MASKl)
56917f01e99SJung-uk Kim # define LL2HBITS(a) ((BN_ULLONG)((a)&BN_MASKl)<<BN_BITS2)
57017f01e99SJung-uk Kim
57117f01e99SJung-uk Kim # define mul64(l,h,bl,bh) \
57217f01e99SJung-uk Kim { \
57317f01e99SJung-uk Kim BN_ULONG m,m1,lt,ht; \
57417f01e99SJung-uk Kim \
57517f01e99SJung-uk Kim lt=l; \
57617f01e99SJung-uk Kim ht=h; \
57717f01e99SJung-uk Kim m =(bh)*(lt); \
57817f01e99SJung-uk Kim lt=(bl)*(lt); \
57917f01e99SJung-uk Kim m1=(bl)*(ht); \
58017f01e99SJung-uk Kim ht =(bh)*(ht); \
5818f1ef87aSJung-uk Kim m=(m+m1)&BN_MASK2; ht += L2HBITS((BN_ULONG)(m < m1)); \
58217f01e99SJung-uk Kim ht+=HBITS(m); \
58317f01e99SJung-uk Kim m1=L2HBITS(m); \
5848f1ef87aSJung-uk Kim lt=(lt+m1)&BN_MASK2; ht += (lt < m1); \
58517f01e99SJung-uk Kim (l)=lt; \
58617f01e99SJung-uk Kim (h)=ht; \
58717f01e99SJung-uk Kim }
58817f01e99SJung-uk Kim
58917f01e99SJung-uk Kim # define sqr64(lo,ho,in) \
59017f01e99SJung-uk Kim { \
59117f01e99SJung-uk Kim BN_ULONG l,h,m; \
59217f01e99SJung-uk Kim \
59317f01e99SJung-uk Kim h=(in); \
59417f01e99SJung-uk Kim l=LBITS(h); \
59517f01e99SJung-uk Kim h=HBITS(h); \
59617f01e99SJung-uk Kim m =(l)*(h); \
59717f01e99SJung-uk Kim l*=l; \
59817f01e99SJung-uk Kim h*=h; \
59917f01e99SJung-uk Kim h+=(m&BN_MASK2h1)>>(BN_BITS4-1); \
60017f01e99SJung-uk Kim m =(m&BN_MASK2l)<<(BN_BITS4+1); \
6018f1ef87aSJung-uk Kim l=(l+m)&BN_MASK2; h += (l < m); \
60217f01e99SJung-uk Kim (lo)=l; \
60317f01e99SJung-uk Kim (ho)=h; \
60417f01e99SJung-uk Kim }
60517f01e99SJung-uk Kim
60617f01e99SJung-uk Kim # define mul_add(r,a,bl,bh,c) { \
60717f01e99SJung-uk Kim BN_ULONG l,h; \
60817f01e99SJung-uk Kim \
60917f01e99SJung-uk Kim h= (a); \
61017f01e99SJung-uk Kim l=LBITS(h); \
61117f01e99SJung-uk Kim h=HBITS(h); \
61217f01e99SJung-uk Kim mul64(l,h,(bl),(bh)); \
61317f01e99SJung-uk Kim \
61417f01e99SJung-uk Kim /* non-multiply part */ \
6158f1ef87aSJung-uk Kim l=(l+(c))&BN_MASK2; h += (l < (c)); \
61617f01e99SJung-uk Kim (c)=(r); \
6178f1ef87aSJung-uk Kim l=(l+(c))&BN_MASK2; h += (l < (c)); \
61817f01e99SJung-uk Kim (c)=h&BN_MASK2; \
61917f01e99SJung-uk Kim (r)=l; \
62017f01e99SJung-uk Kim }
62117f01e99SJung-uk Kim
62217f01e99SJung-uk Kim # define mul(r,a,bl,bh,c) { \
62317f01e99SJung-uk Kim BN_ULONG l,h; \
62417f01e99SJung-uk Kim \
62517f01e99SJung-uk Kim h= (a); \
62617f01e99SJung-uk Kim l=LBITS(h); \
62717f01e99SJung-uk Kim h=HBITS(h); \
62817f01e99SJung-uk Kim mul64(l,h,(bl),(bh)); \
62917f01e99SJung-uk Kim \
63017f01e99SJung-uk Kim /* non-multiply part */ \
6318f1ef87aSJung-uk Kim l+=(c); h += ((l&BN_MASK2) < (c)); \
63217f01e99SJung-uk Kim (c)=h&BN_MASK2; \
63317f01e99SJung-uk Kim (r)=l&BN_MASK2; \
63417f01e99SJung-uk Kim }
63517f01e99SJung-uk Kim # endif /* !BN_LLONG */
63617f01e99SJung-uk Kim
63717f01e99SJung-uk Kim void BN_RECP_CTX_init(BN_RECP_CTX *recp);
63817f01e99SJung-uk Kim void BN_MONT_CTX_init(BN_MONT_CTX *ctx);
63917f01e99SJung-uk Kim
64017f01e99SJung-uk Kim void bn_init(BIGNUM *a);
64117f01e99SJung-uk Kim void bn_mul_normal(BN_ULONG *r, BN_ULONG *a, int na, BN_ULONG *b, int nb);
64217f01e99SJung-uk Kim void bn_mul_comba8(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b);
64317f01e99SJung-uk Kim void bn_mul_comba4(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b);
64417f01e99SJung-uk Kim void bn_sqr_normal(BN_ULONG *r, const BN_ULONG *a, int n, BN_ULONG *tmp);
64517f01e99SJung-uk Kim void bn_sqr_comba8(BN_ULONG *r, const BN_ULONG *a);
64617f01e99SJung-uk Kim void bn_sqr_comba4(BN_ULONG *r, const BN_ULONG *a);
64717f01e99SJung-uk Kim int bn_cmp_words(const BN_ULONG *a, const BN_ULONG *b, int n);
64817f01e99SJung-uk Kim int bn_cmp_part_words(const BN_ULONG *a, const BN_ULONG *b, int cl, int dl);
64917f01e99SJung-uk Kim void bn_mul_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n2,
65017f01e99SJung-uk Kim int dna, int dnb, BN_ULONG *t);
65117f01e99SJung-uk Kim void bn_mul_part_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b,
65217f01e99SJung-uk Kim int n, int tna, int tnb, BN_ULONG *t);
65317f01e99SJung-uk Kim void bn_sqr_recursive(BN_ULONG *r, const BN_ULONG *a, int n2, BN_ULONG *t);
65417f01e99SJung-uk Kim void bn_mul_low_normal(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n);
65517f01e99SJung-uk Kim void bn_mul_low_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n2,
65617f01e99SJung-uk Kim BN_ULONG *t);
65717f01e99SJung-uk Kim BN_ULONG bn_sub_part_words(BN_ULONG *r, const BN_ULONG *a, const BN_ULONG *b,
65817f01e99SJung-uk Kim int cl, int dl);
65917f01e99SJung-uk Kim int bn_mul_mont(BN_ULONG *rp, const BN_ULONG *ap, const BN_ULONG *bp,
66017f01e99SJung-uk Kim const BN_ULONG *np, const BN_ULONG *n0, int num);
6618f1ef87aSJung-uk Kim void bn_correct_top_consttime(BIGNUM *a);
66217f01e99SJung-uk Kim BIGNUM *int_bn_mod_inverse(BIGNUM *in,
66317f01e99SJung-uk Kim const BIGNUM *a, const BIGNUM *n, BN_CTX *ctx,
66417f01e99SJung-uk Kim int *noinv);
66517f01e99SJung-uk Kim
bn_expand(BIGNUM * a,int bits)66617f01e99SJung-uk Kim static ossl_inline BIGNUM *bn_expand(BIGNUM *a, int bits)
66717f01e99SJung-uk Kim {
66817f01e99SJung-uk Kim if (bits > (INT_MAX - BN_BITS2 + 1))
66917f01e99SJung-uk Kim return NULL;
67017f01e99SJung-uk Kim
67117f01e99SJung-uk Kim if (((bits+BN_BITS2-1)/BN_BITS2) <= (a)->dmax)
67217f01e99SJung-uk Kim return a;
67317f01e99SJung-uk Kim
67417f01e99SJung-uk Kim return bn_expand2((a),(bits+BN_BITS2-1)/BN_BITS2);
67517f01e99SJung-uk Kim }
67617f01e99SJung-uk Kim
677b077aed3SPierre Pronchery int ossl_bn_check_prime(const BIGNUM *w, int checks, BN_CTX *ctx,
678b077aed3SPierre Pronchery int do_trial_division, BN_GENCB *cb);
679b077aed3SPierre Pronchery
68017f01e99SJung-uk Kim #endif
681