aboutsummaryrefslogtreecommitdiffstats
path: root/src/lib/math/numbertheory/numthry.h
Commit message (Collapse)AuthorAgeFilesLines
* 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