summaryrefslogtreecommitdiff
path: root/src/lib/libcrypto/bn (follow)
Commit message (Collapse)AuthorAgeFilesLines
...
* Optimise bn_mul2_mulw_addtw() for aarch64.jsing2023-06-171-1/+28
| | | | | This provides significant performance gains for bn_sqr_comba4() and bn_sqr_comba8().
* Speed up Montgomery multiplication.jsing2023-06-171-10/+37
| | | | | | | | | | Factor out and optimise the inner loop for Montgomery multiplication, making use of bn_qwmulw_addqw_addw() to perform Montgomery multiplication by one word in larger steps. This provides a significant performance gain, especially on platforms where bn_qwmulw_addqw_addw() is (or can be) optimised. ok tb@
* Disallow aliasing of return value and modulustb2023-06-131-1/+44
| | | | | | | | | | | All the functions changed in this commit would silently misbehave if the return value aliases the modulus, most of the time they would succeed and return an incorrect result of 0 in that situation. This adjusts all the functions in BN_mod.c, others and documentation will follow later. Prompted by a bug report about BN_mod_inverse() by Guido Vranken. ok jsing
* Add a BN_R_INVALID_ARGUMENT error codetb2023-06-132-2/+4
| | | | | | | | | | One problem with OpenSSL error codes is that they tend to be too specific (another problem is that they are extremely ugly). So add an EINVAL-style error code. This will be used in an upcoming commit to disallow aliasing of the 'return value' with the modulus in BN_mod_* functions and should be applicable elsewhere, outside of this one narrow use case. ok jsing
* Optimise quad word primitives on aarch64.jsing2023-06-121-1/+136
| | | | This provides a performance gain across most BN operations.
* Provide and use various quad word primitives.jsing2023-06-123-27/+120
| | | | | | | | This includes bn_qwaddqw(), bn_qwsubqw(), bn_qwmulw_addw() and bn_qwmulw_addqw_addw(). These can typically be optimised on architectures that have a reasonable number of general purpose registers. ok tb@
* Reinstate bn_isqrt.c r1.8 and crypto_lock.c r1.3tb2023-06-041-4/+2
| | | | | | | | | | | | | | | This traded local copies of CTASSERT() to the one in crypto_internal.h. This change was backed out due to SHA-512 breakage on STRICT_ALIGNMENT architectures still using Fred Flintstone's gcc without asm sha512. Original commit message: Use crypto_internal.h's CTASSERT() Now that this macro is available in a header, let's use that version rather than copies in several .c files. discussed with jsing
* Fix variable reuse in BN_mod_inverse()tb2023-06-021-21/+15
| | | | | | | | | | | | | | | | | | The somewhat strange calculation m = a^{-1} (mod m) can return 0. This breaks because of BN_nnmod() having delicate semantics of which variable can be reused. BN_nnmod(a, a, m, ctx) works and the library relies on that. Here, the code ends up doing BN_nnmod(m, a, m, ctx) and this doesn't work. If the result of the initial BN_mod() is negative, then BN_nnmod() will return 0. Problem reported by Guido Vranken in https://github.com/openssl/openssl/issues/21110 This code is well covered by regress, but it does not currently have explicit test coverage. Such will be added soon. ok beck jsing
* Provide optimised bn_mulw_{addw,addw_addw,addtw}() for aarch64.jsing2023-05-281-1/+68
| | | | | This results in bn_mul_comba4() and bn_mul_comba8() requiring ~30% less instructions than they did previously.
* Provide optimised bn_addw_addw()/bn_subw_subw() for aarch64.jsing2023-05-281-1/+43
|
* Rewrite BN_{asc,dec,hex}2bn() using CBS.jsing2023-05-281-123/+224
| | | | | | | | | | | This gives us more readable and safer code. There are two intentional changes to behaviour - firstly, all three functions zero any BN that was passed in, prior to doing any further processing. This means that a passed BN is always in a known state, regardless of what happens later. Secondly, BN_asc2bn() now fails on NULL input, rather than crashing. This brings its behaviour inline with BN_dec2bn() and BN_hex2bn(). ok tb@
* backout alignment changes (breaking at least two architectures)deraadt2023-05-191-2/+4
|
* Use crypto_internal.h's CTASSERT()tb2023-05-171-4/+2
| | | | | | | Now that this macro is available in a header, let's use that version rather than copies in several .c files. discussed with jsing
* Use is_pseudoprime instead of is_prime in bn_bpsw.ctb2023-05-101-30/+33
| | | | | | | This is more accurate and improves readability a bit. Apart from a comment tweak this is sed + knfmt (which resulted in four wrapped lines). Discussed with beck and jsing
* Add Miller-Rabin test for random bases to BPSWtb2023-05-103-33/+130
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | The behavior of the BPSW primality test for numbers > 2^64 is not very well understood. While there is no known composite that passes the test, there are heuristics that indicate that there are likely infinitely many. Therefore it seems appropriate to harden the test. Having a settable number of MR rounds before doing a version of BPSW is also the approach taken by Go's primality check in math/big. This adds a new implementation of the old MR test that runs before running the strong Lucas test. I like to imagine that it's slightly cleaner code. We're effectively at about twice the cost of what we had a year ago. In addition, it adds some non-determinism in case there actually are false positives for the BPSW test. The implementation is straightforward. It could easily be tweaked to use the additional gcds in the "enhanced" MR test of FIPS 186-5, but as long as we are only going to throw away the additional info, that's not worth much. This is a first step towards incorporating some of the considerations in "A performant misuse-resistant API for Primality Testing" by Massimo and Paterson. Further work will happen in tree. In particular, there are plans to crank the number of Miller-Rabin tests considerably so as to have a guaranteed baseline. The manual will be updated shortly. positive feedback beck ok jsing
* bn_exp: also special case -1 modulustb2023-05-091-6/+6
| | | | | | | | | | Anything taken to the power of 0 is 1, and then reduced mod 1 or mod -1 it will be 0. If "anything" includes 0 or not is a matter of convention, but it should not depend on the sign of the modulus... Reported by Guido Vranken ok jsing (who had the same diff)
* Rewrite BN_bn2hex() using CBB/CBS.jsing2023-05-091-25/+35
| | | | ok tb@
* Rewrite BN_bn2dec() using CBB/CBS.jsing2023-05-091-63/+61
| | | | ok tb@
* Garbage collect BN_zero_ex()tb2023-04-301-7/+1
|
* whitespacetb2023-04-301-2/+2
|
* Remove a useless doxygen commenttb2023-04-271-5/+1
|
* Remove the deprecated API from BNtb2023-04-254-174/+5
|
* GF2m bites the dust. It won't be missed.tb2023-04-252-1330/+1
|
* BN_RECP_CTX moves to internaltb2023-04-251-3/+3
|
* Remove the horror show that is bn_nist and ecp_nisttb2023-04-252-1349/+1
| | | | | | This code is full of problematic C and is also otherwise of questionable quality. It is far from constant time and jsing informs me it also isn't faster. Good riddance.
* Remove the no longer used BN_MONT_CTX_init()tb2023-04-252-15/+2
|
* Move a few now internal prototypes to bn_local.htb2023-04-252-24/+17
|
* Remove old BN_one/BN_zero compat stufftb2023-04-251-13/+1
| | | | ok jsing
* Remove X9.31 supporttb2023-04-252-307/+1
| | | | ok jsing
* Remove the no longer used BN_CTX_init()tb2023-04-252-14/+2
| | | | ok jsing
* Add endbr64 where needed by inspection. Passes regresson tests.deraadt2023-04-2514-0/+24
| | | | ok jsing, and kind of tb an earlier version
* Improve bn_montgomery_multiply_words()jsing2023-04-221-9/+16
| | | | | | | | | Pull a number of invariants into variables, which avoids repeated loading from memory on architectures where sufficient registers are available. Also keep track of the per-iteration carry in a variable, rather than unnecessarily reading from and writing to memory. This gives a reasonable performance gain on some architectures (e.g. armv7)
* Rename Hex array to hex_digits.jsing2023-04-191-5/+5
| | | | ok tb@
* Move the BN_bn2bin()/BN_bin2bn() family to bn_convert.cjsing2023-04-192-182/+183
|
* Reorder functions.jsing2023-04-191-102/+102
| | | | No functional change.
* Move BN_options() from bn_convert.c to bn_lib.cjsing2023-04-192-21/+21
|
* unifdef BN_RECURSIONjsing2023-04-195-594/+5
| | | | | | | | | | | | This removes a bunch of incomplete and scary code, which potentially leaks secrets and is not constant time. A performance gain is achieved on arm64 for sizes that we care about, while a minimal decrease in performance is noted for larger sizes on some other platforms. While we will potentially reimplement Karatsuba (or Toom-Cook) at a later date, it will be easier and safer to do it from a clean slate. ok tb@
* Tweak indent and use named registers.jsing2023-04-171-13/+13
| | | | No functional change.
* Move BN_bn2mpi()/BN_mpi2bn() into bn_convert.cjsing2023-04-172-136/+73
|
* Mark X9.31 BN API for removaltb2023-04-161-1/+4
| | | | | | | This supports a mostly forgotten, seemingly unused and long retired standard. No need for this in our public API Dyson sphere. ok jsing
* The BN reciprocal API will also become internal-onlytb2023-04-161-1/+7
| | | | | | | This is unused outside of the library and could do with some reworking. That's easier without having to care about outside consumers. ok jsing
* Various BN*init() will be removed from the public APItb2023-04-161-1/+10
| | | | | | | | With the corresponding structs now being opaque, the only thing they are good for outside the library are memory leaks. They will be removed completely or become internal only. ok jsing
* Mark public bn_nist and ec_nist API for removaltb2023-04-161-1/+3
| | | | | | | | | | | | | The faster nist code is rife with problematic C. While this is generally considered to be a pleonasm nowadays, here it specifically refers to aliasing issues and other flavors of undefined behavior. With compilers and standardization committees becoming seemingly more determined about making C even more unusable than it already is, this code has resulted in miscompilations and generally is a target rich environment for fuzzers to feast on. We're better off without it. Go look while it's still there. It's some of the very worst we have to offer. ok jsing
* Remove now unused GF2m perlasm generatorstb2023-04-153-980/+0
|
* Rename the largely misnamed bn_print.c to bn_convert.cjsing2023-04-141-1/+1
| | | | | | | | This file primarily contains the various BN_bn2*() and BN_*2bn() functions (along with BN_print() and BN_options()). More function shuffling will follow. Discussed with tb@
* Provide and use bn_copy_words() in BN_copy().jsing2023-04-141-31/+15
| | | | | | | | This is simpler than the current code, while still being well optimised by compilers, across a range of architectures. In many cases we even get a performance gain for the BN sizes that we primarily care about. Joint work with tb@
* Add a new implementation of BN_mod_sqrt()tb2023-04-112-409/+726
| | | | | | | | | | | | | | | | | | | This is a reimplementation from scratch of the Tonelli-Shanks algorithm based on Henri Cohen "A Course in Computational Algebraic Number Theory", Springer GTM 138, section 1.5.1. It is API compatible with the previous implementation, so no documentation change is required. Contrary to the old implementation, this does not have any infinite loops and has various additional sanity checks to prevent misbehavior in case the input modulus is not a prime. It contains extensive comments and the individual parts of the algorithm are split into digestible chunks instead of having one huge function. One difference of note is that it BN_mod_sqrt() now always returns the smaller of the two possible answers. In other words, while its core is non-deterministic, its answer is not. ok jsing
* Remove some doubled empty linestb2023-04-091-7/+1
|
* bn_mont: fix typo in comment divisable -> divisibletb2023-04-071-2/+2
|
* Compress euclid() a littletb2023-04-031-49/+28
| | | | | | | | | | This function is spread out over way too many lines and has too much repetition. Once this is made a little more compact, it becomes clearer that this is a somewhat obfuscated version of binary gcd (it is not constant time therefore cryptographically unsound. It is not used internally). This will likely go away later. ok jsing
generated by cgit v1.2.3-55-g6feb (git 2.39.1) at 2025-03-27 22:09:58 +0000