aboutsummaryrefslogtreecommitdiffstats
path: root/src/lib/math/numbertheory/numthry.h
Commit message (Collapse)AuthorAgeFilesLines
* Modify BigInt constructorsJack Lloyd2021-04-241-1/+1
| | | | | | | | | Add static methods for very common (eg zero, one) or very uncommon (eg ECSDA truncated integers) construction methods, instead of using C++ constructors for all of these. Also adds from_s32 which allows creating a negative BigInt easily, instead of -BigInt(-x) -> BigInt::from_s32(x)
* Some DL_Group and Montgomery exp improvementsJack Lloyd2020-11-241-2/+5
| | | | Leverage precomputation better
* Remove mul_addJack Lloyd2020-11-081-12/+0
| | | | Testing shows it doesn't seem to matter for performance anyway
* Cleanup in number theoryJack Lloyd2020-11-081-107/+0
| | | | | | Remove or hide deprecated functions Consolidate some source files
* Some math deprecationsJack Lloyd2020-11-051-25/+34
| | | | | | | | | | | | | Mostly things that shouldn't be used (like almost Montgomery inverse, which isn't even constant time) or are very much just for internals (like the word-wise Montgomery inverse computation used for reduction). Make variable time division explicit; leaves plain divide as a call but it forwards to ct_divide now. All callers within the library are now explicitly consttime or vartime. Add a shortcut for modulus by one word - this hits quite often especially in the ECC code
* Resolve Doxygen warningsJack Lloyd2020-10-281-1/+1
|
* Optimize inverse_modJack Lloyd2020-03-061-1/+2
| | | | About 25% faster
* Avoid inlining the deprecated modular inverse functionsJack Lloyd2020-03-021-13/+4
| | | | | | | | Since doing so breaks ABI which otherwise is not touched so far in 2.14.0 release. Add BOTAN_DEPRECATED_API which is combination of DLL export and a deprecation warning.
* Clarify const-time guarantees of inverse_mod function [ci skip]Jack Lloyd2020-03-011-2/+5
|
* Remove use of Binary Extended Euclidean Algorithm for inversionJack Lloyd2020-03-011-7/+14
| | | | | Instead use two specialized algorithms, one for odd modulus and the other for power of 2 modulus, then combine the results using CRT.
* Use a const time algorithm for monty_inverseJack Lloyd2018-12-091-2/+2
| | | | | Previous EEA leaked information about the low word of the prime, which is a problem for RSA.
* Add Lucas test from FIPS 186-4Jack Lloyd2018-07-311-15/+22
| | | | | | | | | | This eliminates an issue identified in the paper "Prime and Prejudice: Primality Testing Under Adversarial Conditions" by Albrecht, Massimo, Paterson and Somorovsky where DL_Group::verify_group with strong=false would accept a composite q with probability 1/4096, which is exactly as the error bound is documented, but still unfortunate.
* Avoid potential side channel when generating RSA primesJack Lloyd2018-04-171-1/+16
| | | | | | | | | | Add a new function dedicated to generating RSA primes. Don't test for p.bits() > bits until the very end - rarely happens, and speeds up prime generation quite noticably. Add Miller-Rabin error probabilities for 1/2**128, which again speeds up RSA keygen and DL param gen quite a bit.
* Splitout binary extended GCD algorithmJack Lloyd2018-02-281-1/+11
| | | | | Makes it easier to benchmark, or call in cases where the const time algorithm is not required.
* Improve speed of prime generation especially safe primesJack Lloyd2018-01-161-6/+10
| | | | | | | | | | | | | | | | First, correct a bug in the sieve code. It would break early if a value did not match up with the sieve. However in that case, the sieve values would be out of sync with the value of p, and would be returning effectively random results. This caused prime generation to be slower than it should be, both because the sieve was incorrectly rejecting values that were not multiples of any small prime and was allowing values that were multiples of small primes to move on to the Miller-Rabin test. In the sieve, also sieve so that 2*q+1 is also not a multiple of the small primes. This speeds up safe prime generation. GH #1411
* More include header cleanupsJack Lloyd2017-09-211-1/+0
|
* Header file cleanupsJack Lloyd2017-09-211-1/+2
| | | | Some help from include-what-you-use
* Change header guard format to BOTAN_FOO_H_Jack Lloyd2017-09-201-2/+2
| | | | | | ISO C++ reserves names with double underscores in them Closes #512
* Add API stability annotations.Jack Lloyd2017-09-191-21/+21
| | | | | Defined in build.h, all equal to BOTAN_DLL so ties into existing system for exporting symbols.
* Fix description of coprime parameter to random_prime() [ci skip]René Korthaus2017-04-051-1/+1
| | | | Found during a review by BSI
* Speed up DSA param gen testJack Lloyd2016-12-261-1/+3
| | | | Record counter value in test data, and start the search from there.
* Convert to using standard uintN_t integer typesJack Lloyd2016-12-181-4/+4
| | | | | | Renames a couple of functions for somewhat better name consistency, eg make_u32bit becomes make_uint32. The old typedefs remain for now since probably lots of application code uses them.
* Fix doxygen warnings [ci skip]René Korthaus2016-10-191-2/+0
|
* Add ECGDSARené Korthaus2016-04-191-0/+11
|
* For odd moduli use a input-independent modular inverse algorithm.Jack Lloyd2016-02-201-3/+18
| | | | Also adds a (not const time) implementation of almost Montgomery reduction.
* Add tests and timings for inverse_modJack Lloyd2016-02-201-1/+8
|
* Add missing files. Remove cipher lookup from engine code.lloyd2015-02-011-4/+0
|
* Ensure all files have copyright and license info.lloyd2015-01-101-1/+1
| | | | | Update license header line to specify the terms and refer to the file, neither of which it included before.
* Any fixed MR iterations is probably wrong for somebody. Allow the userlloyd2014-04-251-1/+16
| | | | | | to specify a probability as well as if n was randomly chosen or not. If the input is random use a better bounds to reduce the number of needed tests.
* Use 20 Miller-Rabin iterations regardless of the size of the integer. Thislloyd2014-04-131-33/+1
| | | | | provides a much better worst-case error bound. Also take the nonce from anywhere in the usable range rather than limiting the bit size.
* Move lib into srclloyd2014-01-101-0/+237
generated by cgit v1.2.3 (git 2.39.1) at 2024-12-11 07:53:28 +0000