summaryrefslogtreecommitdiff
path: root/src/lib/libcrypto/bn (follow)
Commit message (Collapse)AuthorAgeFilesLines
...
* Add RCSIDtb2023-03-251-1/+1
|
* Add checks to ensure the uint16_t array isn't overflowed when thistb2023-03-251-0/+4
| | | | | script is run. This is more of an issue with uint16_t now than it was with prime_t aka BN_ULONG before r1.6.
* Zap an empty linetb2023-03-251-2/+1
|
* Ensure negative input to BN_mod_exp_mont_consttime() is correctly reduced.jsing2023-03-151-7/+4
| | | | | | | | | | A negative input to BN_mod_exp_mont_consttime() is not correctly reduced, remaining negative (when it should be in the range [0, m)). Fix this by unconditionally calling BN_nnmod() on the input. Fixes ossfuzz #55997. ok tb@
* Avoid -0 in BN_div_word().jsing2023-03-111-1/+5
| | | | | | | | | Currently, the use of BN_div_word() can result in -0 - avoid this by setting negative again, at the end of the computation. Should fix oss-fuzz 56667. ok tb@
* Correct sign handling in BN_add_word().jsing2023-03-111-3/+3
| | | | | | | | | | | | A sign handling bug was introduced to BN_add_word() in bn_word.c r1.18. When handling addition to a negative bignum, the BN_sub_word() call can result in the sign being flipped, which we need to account for. Use the same code in BN_sub_word() - while not technically needed here it keeps the code consistent. Issue discovered by tb@ ok tb@
* Improve bn_montgomery_multiply_words().jsing2023-03-071-10/+13
| | | | | | | | | | | | | Rather than calling bn_mul_add_words() twice - once to multiply and once to reduce - perform the multiplication and reduction in a single pass using bn_mulw_addw_addw() directly. Also simplify the addition of the resulting carries, which in turn allows us to avoid zeroing the top half of the temporary words. This provides a ~20-25% performance improvement for RSA operations on aarch64. ok tb@
* Slightly rework bn_mulw_addtw().jsing2023-03-071-5/+3
| | | | | | | | | Call bn_mulw_addw() rather than doing bn_mulw() follow by bn_addw(). This simplifies the code slightly, plus on some platforms bn_mulw_addw() can be optimised (and bn_mulw_addtw() will then benefit from such an optimisation). ok tb@
* Call BN_free() instead of BN_clear_free().jsing2023-03-072-7/+7
| | | | | | | BN_clear_free() is a wrapper that calls BN_free() - call BN_free() directly instead. ok tb@
* Limit bn_mul_mont() usage to sizes less than or equal to 8192 bits.jsing2023-03-071-1/+9
| | | | | | | | | | | | The assembly bn_mul_mont() implementations effectively use alloca() to allocate space for computation (at up to 8x the input size), without any limitation. This means that sufficiently large inputs lead to the stack being blown. Prevent this by using the C based implementation instead. Thanks to Jiayi Lin <jlin139 at asu dot edu> for reporting this to us. ok beck@ tb@
* Implement bn_montgomery_multiply()jsing2023-03-071-3/+86
| | | | | | | | | | | Provide a constant-time-style Montgomery multiplication implementation. Use this in place of the assembly bn_mul_mont() on platforms that either do not have an assembly implementation or have not compiled it in. Also use this as the fallback version for bn_mul_mont(), rather than falling back to a non-constant time implementation. ok beck@ tb@
* Refactor BN_mod_mul_montgomery().jsing2023-03-071-20/+48
| | | | | | | | | | Pull out the simplistic implementation (using BN_mul() or BN_sqr()) into a bn_mod_mul_montgomery_simple() function. Provide bn_mod_mul_montgomery() with an implementation that changes depending on if the assembly bn_mul_mont() is available or not. Turn BN_mod_mul_montgomery() and BN_to_montgomery() into callers of bn_mod_mul_montgomery(). ok beck@ tb@
* Delete unused and unsafe bn_mul_mont() example code.jsing2023-03-071-54/+1
| | | | | | This came from bn_asm.c and did not even compile until recently. ok beck@ tb@
* Fix comment for bn_mul2_mulw_addtw()jsing2023-03-071-5/+5
|
* Rewrite/simplify BN_from_montgomery_word() and BN_from_montgomery().jsing2023-02-281-92/+85
| | | | | | | | Rename BN_from_montgomery_word() to bn_montgomery_reduce() and rewrite it to be simpler and clearer, moving further towards constant time in the process. Clean up BN_from_montgomery() in the process. ok tb@
* Use separate lines instead of semicolons.bcook2023-02-251-4/+10
| | | | | | macOS aarch64 assembly dialect treats ; as comment instead of a newline ok tb@, jsing@
* Use explicit .text instead of .previous to please Windows/MinGW on amd64tb2023-02-231-1/+1
| | | | ok miod
* Adjust parentheses in mont->ri assignment.jsing2023-02-221-2/+2
| | | | Requested by tb@
* Replace bn_sub_part_words() with bn_sub().jsing2023-02-223-368/+18
| | | | | | | | Now that bn_sub() handles word arrays with potentially different lengths, we no longer need bn_sub_part_words() - call bn_sub() instead. This allows us to entirely remove the unnecessarily complex bn_sub_part_words() code. ok tb@
* Rework bn_add()/bn_sub() to operate on word arrays.jsing2023-02-223-82/+99
| | | | | | | | Rather than working on BIGNUMs, change bn_add()/bn_sub() to operate on word arrays that potentially differ in length. This matches the behaviour of s2n-bignum's bignum_add() and bignum_sub(). ok tb@
* Rewrite and simplify BN_MONT_CTX_set()jsing2023-02-222-98/+76
| | | | | | | | | | | | | | OpenSSL commit 4d524040bc8 changed BN_MONT_CTX_set() so that it computed a 64 bit N^-1 on both BN_BITS2 == 32 and BN_BITS2 == 64 platforms. However, the way in which this was done was to duplicate half the code and wrap it in #ifdef. Rewrite this code to use a single code path on all platforms, with #ifdef being limited to setting an additional word in the temporary N and storing the result on BN_BITS2 == 32 platforms. Also remove stack based BIGNUM in favour of using the already present BN_CTX. ok tb@
* remove extra argumentbcook2023-02-211-2/+2
| | | | ok tb@
* Unifdef MONT_WORD.jsing2023-02-212-75/+5
| | | | | | | | | | | It does not make sense to use code that is slower, currently broken and prevents the use of assembly Montgomery implementations. This is the result of `unifdef -m -DMONT_WORD`, followed by some manual clean up and the removal of the Ni bignum from BN_MONT_CTX (which was only used in the non-MONT_WORD case). ok miod@ tb@
* Move BN_MONT_CTX back to bn_local.h for now. It's still used by bn_exp.ctb2023-02-192-14/+14
|
* Rewrite BN_MONT_CTX_set_locked()jsing2023-02-191-23/+27
| | | | | | | | Rewrite and simplify BN_MONT_CTX_set_locked - in particular, only hold the lock for a short period of time, rather than holding a write lock for a module across an expensive operation. ok tb@
* First pass clean up of bn_mont.c.jsing2023-02-191-31/+37
| | | | | | | | | Use calloc() rather than malloc() with manual initialisation of all struct members to zero, use memset() instead of manually initialising all struct members to zero, use consistent naming, use BN_free() instead of BN_clear_free() (since it is the same thing). ok tb@
* Move BN_MONT_CTX_copy().jsing2023-02-191-19/+19
|
* Move struct bn_mont_ctx_st from bn_local.h to bn_mont.c.jsing2023-02-192-14/+14
| | | | | | No code outside of bn_mont.c needs access to it. ok tb@
* Provide optimised versions of bn_addw() and bn_subw() for aarch64.jsing2023-02-171-1/+35
|
* Remove now unused tangle of mul*/sqr* and BN_UMULT_* macros.jsing2023-02-171-251/+1
| | | | | | | No, I'm not trying to overwhelm you... however, we really no longer need this clutter. ok tb@
* Reimplement bn_sqr_comba{4,8}().jsing2023-02-172-102/+110
| | | | | | | | | | | | Use bignum primitives rather than the current mess of macros.The sqr_add_c macro gets replaced with bn_mulw_addtw(), while the sqr_add_c2 macro gets replaced with bn_mul2_mulw_addtw(). The variables in the comba functions have also been reordered, so that the patterns are easier to understand - the compiler can take care of optimising the inputs and outputs to avoid register moves. ok tb@
* Enable s2n-bignum word_clz() on amd64.jsing2023-02-163-3/+15
| | | | | | | | | The BN_num_bits_word() function is a hot path, being called more than 80 million times during a libcrypto regress run. The word_clz() implementation uses five instructions to do the same as the generic code that uses more than 60 instructions. Discussed with tb@
* Use bn_addw() in bn_mulw(), rather than duplicating add with carry code.jsing2023-02-161-12/+7
|
* Change include from _internal_s2n_bignum.h to s2n_bignum_internal.h.jsing2023-02-161-1/+1
|
* Include the ISC license from s2n-bignum's LICENSE file.jsing2023-02-161-1/+12
|
* Bring in word_clz.S from s2n-bignum for amd64.jsing2023-02-161-0/+48
|
* Rename bn_umul_hilo() to bn_mulw().jsing2023-02-169-105/+109
| | | | | | | | | This keeps the naming consistent with the other bignum primitives that have been recently introduced. Also, use 1/0 intead of h/l (e.g. a1 instead of ah), as this keeps consistency with other primitives and allows for naming that works with double word, triple word and quadruple word inputs/outputs. Discussed with tb@
* Add missing masks to accumulator version of bn_umul_hilo()jsing2023-02-161-1/+5
|
* Reimplement bn_add_words() and bn_sub_words() using bignum primitives.jsing2023-02-162-111/+88
| | | | | | | This removes the effectively duplicate BN_LLONG version of bn_add_words() and simplifies the code considerably. ok tb@
* Place bn_mul_add_words() after bn_mul_words().jsing2023-02-151-39/+39
|
* zap tabtb2023-02-151-2/+2
|
* Remove the misnamed and now unused mul, mul_add and mul_add_c macros.jsing2023-02-141-122/+2
| | | | | | There were only three versions of each one... ok tb@
* Reimplement bn_mul_words(), bn_mul_add_words() and bn_mul_comba{4,8}().jsing2023-02-141-235/+152
| | | | | | | | | | | | | | | | Use bignum primitives rather than the current mess of macros, which also allows us to remove the essentially duplicate versions of bn_mul_words() and bn_mul_add_words() for BN_LLONG. The "mul" macro gets replaced by bn_mulw_addw(), "mul_add" with bn_mulw_addw_addw() and "mul_add_c" with bn_mulw_addtw() (where 'w' indicates single word input and 'tw' indicates triple word input). The variables in the comba functions have also been reordered, so that the patterns are easier to understand - the compiler can take care of optimising the inputs and outputs to avoid register moves. ok tb@
* Provide big number primitives for word addition/multiplication.jsing2023-02-141-1/+114
| | | | | | | | | | These use a consistent naming scheme and are implemented using bitwise/constant time style operations, which should generally be safe on all platforms (until a compiler decides to optimise and use branches). More optimised versions can be provided for a given architecture. ok tb@
* Make BN_is_zero() check word values.jsing2023-02-141-4/+9
| | | | | | | | Rather than completely relying on top, check the words of a bignum. This gets us one step away from being dependent on top and additionally means that we correctly report zero even if top is not yet correct. ok tb@
* Fix a -0 corner case in BN_div_internal()jsing2023-02-141-3/+5
| | | | | | | | | | If the numerator is negative, the numerator and divisor are the same length (in words) and the absolute value of the divisor > the absolute value of the numerator, the "no_branch" case produces -0 since negative has already been set. Call BN_set_negative() at the end of the function to avoid this. ok tb@
* Reimplement BN_num_bits_word().jsing2023-02-141-20/+25
| | | | | | | | | | Provide a simpler and more readable bn_word_clz() function that returns the number of leading zeros for a given BN_ULONG, then implement BN_num_bits_word() using bn_word_clz(). This is a hot path and bn_word_clz() can now be replaced with architecture specific versions where possible. ok tb@
* Make BN_set_negative() closer to constant time.jsing2023-02-141-2/+3
| | | | ok tb@
* Provide bn_ct_{eq,ne}_zero{,_mask}() inline functions.jsing2023-02-141-1/+33
| | | | | | | These will be used to test a BN_ULONG in cases where constant time style behaviour is required. ok tb@
* Avoid negative zero.jsing2023-02-1310-36/+40
| | | | | | | | | | | | | | | | Whenever setting negative to one (or when it could potentially be one), always use BN_set_negative() since it checks for a zero valued bignum and will not permit negative to be set in this case. Since BN_is_zero() currently relies on top == 0, call BN_set_negative() after top has been set (or bn_correct_top() has been called). This fixes a long standing issue where -0 and +0 have been permitted, however multiple code paths (such as BN_cmp()) fail to treat these as equivalent. Prompted by Guido Vranken who is adding negative zero fuzzing to oss-fuzz. ok tb@
generated by cgit v1.2.3-55-g6feb (git 2.39.1) at 2025-08-26 14:41:29 +0000