aboutsummaryrefslogtreecommitdiffstats
path: root/src/lib/math/numbertheory
Commit message (Collapse)AuthorAgeFilesLines
* Add script for running TLS fuzzerJack Lloyd2019-05-241-2/+2
| | | | Fix a few minor issues found thereby
* Fix feature macro checks.Jack Lloyd2019-04-262-4/+5
| | | | Add a checker script.
* Fix some warnings from PVS-StudioJack Lloyd2019-01-171-2/+5
| | | | No real bugs, but pointed out some odd constructs and duplicated logic
* Fix Barrett reduction input boundJack Lloyd2018-12-262-5/+5
| | | | | | | | | | | | In the long ago when I wrote the Barrett code I must have missed that Barrett works for any input < 2^2k where k is the word size of the modulus. Fixing this has several nice effects, it is faster because it replaces a multiprecision comparison with a single size_t compare, and now the branch does not reveal information about the input or modulus, but only their word lengths, which is not considered sensitive. Fixing this allows reverting the change make in a57ce5a4fd2 and now RSA signing is even slightly faster than in 2.8, rather than 30% slower.
* Avoid size-based bypass of the comparison in Barrett reduction.Jack Lloyd2018-12-241-1/+1
| | | | As it would leak if an input was > p^2, or just close to it in size.
* Avoid conditional branch in Barrett for negative inputsJack Lloyd2018-12-241-4/+27
|
* In NIST P-xxx reductions unpoison S before using itJack Lloyd2018-12-241-8/+10
| | | | | | | | Was already done in P-256 but not in P-{192,224,384}. This is a cache-based side channel which would be good to address. It seems like it would be very difficult to exploit even with perfect recovery, but crazier things have worked.
* Unroll const_time_lookup by 2Jack Lloyd2018-12-141-6/+10
| | | | | We know the lookup table is some power of 2, unrolling a bit allows more IPC
* Merge GH #1780 Use constant time algorithm for monty_inverseJack Lloyd2018-12-092-39/+23
|\
| * Use a const time algorithm for monty_inverseJack Lloyd2018-12-092-39/+23
| | | | | | | | | | Previous EEA leaked information about the low word of the prime, which is a problem for RSA.
* | Fix typoJack Lloyd2018-12-091-1/+1
| |
* | Avoid doing a variable time division during Montgomery setupJack Lloyd2018-12-093-4/+9
|/ | | | | | Instead require the inputs be reduced already. For RSA-CRT use Barrett which is const time already. For SRP6 inputs were not reduced, use the Barrett hook available in DL_Group.
* Move Miller-Rabin t param inside the blockJack Lloyd2018-12-091-2/+2
| | | | This var is not used if we use Baile-PSW instead
* Avoid repeated size checks when setting words in NIST reductionJack Lloyd2018-12-081-25/+33
| | | | This is a tiny thing but it saves over 100K cycles for P-384 ECDSA
* Add BigInt::ct_reduce_belowJack Lloyd2018-12-061-1/+2
|
* Reduce the base in the fixed window exponentiatorJack Lloyd2018-12-041-1/+1
| | | | | | | | | | | Otherwise we can end up calling the Barrett reducer with an input that is more than the square of the modulus, which will make it fall back to the (slow) const time division. This only affected even moduli, and only when the base was larger than the modulus. OSS-Fuzz 11750
* Make binary extended Euclidean algorithm less branchyJack Lloyd2018-12-031-12/+45
| | | | This is still leaky, but much less than before.
* Use const time reductions in Barrett and LCM computationsJack Lloyd2018-12-032-4/+6
|
* Avoid conditional operations in P-521 reductionJack Lloyd2018-12-011-30/+31
|
* Add BigInt::mod_mulJack Lloyd2018-12-012-16/+12
|
* Add CT::Mask typeJack Lloyd2018-11-281-2/+4
|
* Need to ensure minimum size hereJack Lloyd2018-11-271-0/+1
| | | | Previously handled by the early exit
* Optimizations for NIST reductionJack Lloyd2018-11-261-22/+20
| | | | Also avoid an early exit in P-521
* Make more BigInt functions const-timeJack Lloyd2018-11-261-3/+2
| | | | In particular comparisons, calc sig words, and mod_sub are const time now.
* Make exceptions easier to translate to error codesJack Lloyd2018-11-231-1/+1
| | | | | | | | | | | Avoid throwing base Botan::Exception type, as it is difficult to determine what the error is in that case. Add Exception::error_code and Exception::error_type which allows (for error code) more information about the error and (for error type) allows knowing the error type without requiring a sequence of catches. See GH #1742
* Avoid branching in the NIST prime reduction codeJack Lloyd2018-11-091-48/+10
| | | | | This is still vulnerable to a cache-based side channel since the multiple chosen leaks the final carry.
* Use resize instead of shrink_to_fitJack Lloyd2018-11-091-3/+3
| | | | Avoid recalculating significant words which slows down reduction
* Rename get_uint32_t to get_uint32Jack Lloyd2018-11-091-67/+67
|
* Minor optimization when primality checkingJack Lloyd2018-10-311-2/+4
| | | | | | | Avoid doing the comparison against the largest hard coded prime, when we know the prime table is 16 bits and we already have to compute the bitsize of n in order to calculate the required number of Miller-Rabin iterations.
* Use a smaller sieve when generating primesJack Lloyd2018-10-151-3/+7
| | | | | | | | | | This was the original behavior but 5af44a91ad switched the sieve to always be the size of the hardcoded prime table. But this ends up being quite a bit slower than necessary. Instead use as many sieve elements as bits in the desired prime which is probably not precisely optimal but seems to provide good speedups for both 1024 and 2048 bit prime generation. This is especially notable when generating strong primes.
* Fix some MSVC warningsJack Lloyd2018-09-303-6/+6
|
* Remove unneeded load_on autoJack Lloyd2018-09-041-2/+0
| | | | It is the default...
* Remove support for 8 or 16 bit BigInt wordsJack Lloyd2018-08-152-10/+2
| | | | | | | | | | It turned out 8 bit was very broken (failed to compile, due to overload problems with functions taking uint8_t vs word). 16 bit words work aside from a test failure, but is really slow. Practically speaking we are not in a position to support 16-bit CPUs very well. And being able to assume sizeof(word) >= sizeof(uint32_t) allows simplifying some code.
* Add some final annotationsJack Lloyd2018-08-131-1/+1
|
* Add Lucas test from FIPS 186-4Jack Lloyd2018-07-319-123/+382
| | | | | | | | | | 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.
* Fix some -Wshadow warningsJack Lloyd2018-06-291-2/+1
|
* Move reduction mod q to DL_GroupJack Lloyd2018-06-281-5/+11
| | | | | Avoids computing Barrett params many times and gives option for more optimizations in future.
* Avoid useless multiplication in Montgomery exponentiationJack Lloyd2018-06-263-22/+39
| | | | | | | | | | | | When beginning the loop we initialized a value to one (in Montgomery form) then multiply it by the first element looked up based on the exponent. But this will always (after Montgomery multiplication) be exactly the value we looked up in the table. So just assign it directly and avoid the redundant operation. Improves RSA verification by 5% or so since the number of multiplications is so small in that case saving even 1 in useful. For other operations there is no measurable improvement.
* Minor optimization for Montgomery exponentiationJack Lloyd2018-06-233-17/+26
| | | | | | | | | The loop started off by squaring the result value, but at that point it is always one (or the Montgomery representation thereof). Avoiding those squarings does not leak any information about the exponent, because we haven't even looked at the exponent at that point. Improves RSA verify performance by about 5%, everything else ~1% speedup
* Attempt to verify decoded ECC groups are using prime fieldsJack Lloyd2018-06-201-3/+20
| | | | | | | Otherwise ressol (part of point decompression) can end up in very long loop. OSS-Fuzz 9011
* Avoid a small timing channel in Barrett reductionJack Lloyd2018-06-201-8/+12
| | | | No known exploit for this but no point taking chances.
* Avoid a special case in Barrett reduction for x < modJack Lloyd2018-06-181-8/+3
| | | | This would have prevented CVE-2018-12435
* Avoid leaking size of exponentJack Lloyd2018-06-174-13/+22
| | | | See #1606 for discussion
* In Montgomery mul, avoid branching based on sig words of integersJack Lloyd2018-06-141-13/+21
| | | | Instead just assume they are the same size as the prime
* Fix a bug in Barrett reductionJack Lloyd2018-06-051-22/+30
| | | | | | -x*n % n would reduce to n instead of zero. Also some small optimizations and cleanups.
* Correct error in P-224 computationJack Lloyd2018-05-311-2/+3
| | | | | | | | If x was very small to start with x.size() might be under the limb count which would cause the final addition to throw because the destination array was smaller than the P-224 p being added. Caught by Wycheproof ECDSA tests
* Speed up DSA param genJack Lloyd2018-05-211-3/+6
| | | | Using Barrett reduction instead of division is ~10x faster.
* Fix typo in comment [ci skip]Jack Lloyd2018-05-171-1/+1
|
* Add clarifying comments and increase M-R tests for 256-bit integersJack Lloyd2018-05-151-3/+7
| | | | See #1542 and #1569
* Always use 1/2^-128 error bounds with Miller-RabinJack Lloyd2018-05-141-24/+14
| | | | | | | Simplifies the code and makes it easy to see we never use the weaker bounds even if the application expicitly requested it. GH #1569
generated by cgit v1.2.3 (git 2.39.1) at 2024-12-28 13:09:48 +0000