aboutsummaryrefslogtreecommitdiffstats
path: root/src/lib/math
Commit message (Collapse)AuthorAgeFilesLines
* Fix MSVC "optimization" warning about bool conversionsJack Lloyd2019-12-062-2/+2
|
* Remove the 32-bit x86 asm for MSVCJack Lloyd2019-11-232-272/+4
| | | | The numbers in #256 suggest that it does nothing at all for performance.
* Remove shift optimization for small word BigInt operator*=Jack Lloyd2019-10-301-16/+1
| | | | | Turns out to be a pessimization - removing improves ECDSA verify by up to 5% on Skylake.
* Fix error messageJack Lloyd2019-10-171-6/+6
|
* Fix coprimality check during prime generationJack Lloyd2019-10-171-27/+21
|
* When generating prime, avoid Lucas test if prob < 32Jack Lloyd2019-10-171-4/+6
| | | | | | | This improves strong prime generation slightly as otherwise we perform two (redundant) Lucas checks on q, first when generating q with weak probability and then a second time when doing the strong confirmation of q if 2*q+1 shows to be prime.
* Merge GH #2147 Add constant-time gcd computationJack Lloyd2019-10-162-15/+52
|\
| * Add constant-time gcdJack Lloyd2019-10-122-15/+52
| | | | | | | | | | Previous version leaked some (minimal) information from the loop bounds.
* | Improve speed of prime generation especially for RSA keygenJack Lloyd2019-10-121-31/+65
|/ | | | | | | | | | | | In RSA keygen we have to verify that p-1 and e are coprime. But this is expensive to compute. So first do a single round of Miller-Rabin primality test; only if that passes do we test coprimality. Improves RSA keygen times notably. All times averaged over many keygens: 1024-bit 21.74 ms -> 10.78 ms 2048-bit 94.93 ms -> 62.80 ms 3072-bit 296.79 ms -> 198.12 ms 4096-bit 738.07 ms -> 499.10 ms
* Deprecate many publically available headersJack Lloyd2019-09-066-6/+15
|
* Fix buildJack Lloyd2019-08-242-1/+3
|
* Inline the fixed window and Montgomery strategies into pow_mod.cppJack Lloyd2019-08-236-198/+133
|
* Remove pow_mod.h from power_mod implementationJack Lloyd2019-08-231-19/+23
|
* Fix bad compare in BigInt <<=Jack Lloyd2019-08-231-1/+1
| | | | Caused an extra allocation for no reason in some cases.
* Small BigInt optimizationsJack Lloyd2019-08-224-14/+15
| | | | Based on profiling RSA key generation
* Add function comment [ci skip]Jack Lloyd2019-08-171-0/+6
|
* Avoid using old pow_mod interface in RSAJack Lloyd2019-08-171-0/+1
| | | | | On its own gives a modest speedup (3-5%) to RSA sign/decrypt, and it is needed for another more complicated optimization.
* Fix Coverity issueJack Lloyd2019-07-101-3/+1
| | | | I think this is a false positive but whatever
* Fix LGTM warningJack Lloyd2019-07-051-4/+2
|
* Officially deprecate headersJack Lloyd2019-06-071-1/+1
| | | | | | | | | | Create BOTAN_DEPRECATED_HEADER so we can warn about this consistently. Shuffle around the filter headers so all of the concrete filters are defined in filters.h instead of being spread across many headers. Document which headers are deprecated as well as a list of headers which will be made internal-only in a future major release.
* Add script for running TLS fuzzerJack Lloyd2019-05-241-2/+2
| | | | Fix a few minor issues found thereby
* Use C++ raw strings in inline asmJack Lloyd2019-05-032-72/+64
|
* Fix feature macro checks.Jack Lloyd2019-04-262-4/+5
| | | | Add a checker script.
* Fix warningJack Lloyd2019-01-241-3/+6
|
* Doc updatesJack Lloyd2019-01-241-1/+3
|
* Revamp BigInt encoding and decoding.Jack Lloyd2019-01-244-103/+130
| | | | Deprecate some crufty functions. Optimize binary encoding/decoding.
* Fix some warnings from PVS-StudioJack Lloyd2019-01-171-2/+5
| | | | No real bugs, but pointed out some odd constructs and duplicated logic
* Fix use of macroJack Lloyd2018-12-311-1/+1
| | | | Assumed to be 0/1
* Simplifications in BigIntJack Lloyd2018-12-291-7/+1
| | | | | Use ct_is_zero instead of more complicated construction, and avoid duplicated size check/resize - Data::set_word will handle it.
* Make bigint_sub_abs const timeJack Lloyd2018-12-271-6/+3
|
* 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.
* Unpoison result of high_bits_freeJack Lloyd2018-12-241-0/+1
| | | | | Previously we unpoisoned the input to high_bit but this is no longer required. But still the output should be unpoisoned.
* Make ctz and high_bit faster and const-time-ishJack Lloyd2018-12-221-5/+0
| | | | | | | They get compiled as const-time on x86-64 with GCC but I don't think this can be totally relied on. But it is anyway an improvement. And, faster, because we compute it recursively
* Use consistent logic for OAEP and PKCS1v15 decodingJack Lloyd2018-12-212-6/+3
| | | | | | | | | | | | The decoding leaked some information about the delimiter index due to copying only exactly input_len - delim_idx bytes. I can't articulate a specific attack that would work here, but it is easy enough to fix this to run in const time instead, where all bytes are accessed regardless of the length of the padding. CT::copy_out is O(n^2) and thus terrible, but in practice it is only used with RSA decryption, and multiplication is also O(n^2) with the modulus size, so a few extra cycles here doesn't matter much.
* 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
* Merge GH #1774 Const time BigInt shiftsJack Lloyd2018-12-086-98/+83
|\
| * Avoid early exitJack Lloyd2018-12-071-4/+3
| |
| * Fix bug and avoid allocations in left shiftJack Lloyd2018-12-075-22/+36
| |
| * Const time the behavior of shifts [WIP]Jack Lloyd2018-12-063-87/+59
| | | | | | | | | | | | | | | | | | They would previously leak for example if the requested shift was 0. However, that should only happen in two situations: very dumb code explicitly requested a shift of zero (in which case we don't care if performance is poor, your code is dumb) or a variable shift that just happens to be zero, in which case the variable may be a secret, for instance this can be seen in the GCD computation.
* | In calc_sig_words save the size of m_reg before the loopJack Lloyd2018-12-081-3/+4
| |
* | Merge GH #1773 Add BigInt::ct_reduce_belowJack Lloyd2018-12-073-3/+39
|\ \ | |/ |/|
generated by cgit v1.2.3 (git 2.39.1) at 2024-12-17 20:03:18 +0000