aboutsummaryrefslogtreecommitdiffstats
path: root/src/lib/math/bigint/big_ops2.cpp
Commit message (Collapse)AuthorAgeFilesLines
* Remove commented out non-constant-time codeJack Lloyd2020-03-061-19/+0
| | | | Quick testing indicates it is not even faster than the CT version anymore.
* 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 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-221-7/+4
| | | | Based on profiling RSA key generation
* Use consistent logic for OAEP and PKCS1v15 decodingJack Lloyd2018-12-211-2/+1
| | | | | | | | | | | | 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.
* Fix bug and avoid allocations in left shiftJack Lloyd2018-12-071-9/+6
|
* Const time the behavior of shifts [WIP]Jack Lloyd2018-12-061-22/+16
| | | | | | | | | 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.
* Use BigInt::cond_flip_signJack Lloyd2018-12-051-3/+1
|
* Fix shift operatorJack Lloyd2018-12-031-1/+1
| | | | This would continually reallocate to larger sizes which is bad news.
* Correct a bug in BigInt::operator%(word)Jack Lloyd2018-12-011-16/+14
| | | | | | If reducing a negative number modulo a power of 2, an incorrect result would be returned. This only affected the versions taking a single word as the modulo.
* Unroll mod_sub for 6 words also, helps P-384 quite a bitJack Lloyd2018-12-011-0/+2
|
* Add BigInt::mod_mulJack Lloyd2018-12-011-9/+29
|
* Simplify BigInt addition and subtractionJack Lloyd2018-11-301-98/+45
| | | | | Addition already has to handle negative numbers so make it do double duty for subtraction.
* Add CT::Mask typeJack Lloyd2018-11-281-1/+1
|
* Make more BigInt functions const-timeJack Lloyd2018-11-261-49/+55
| | | | In particular comparisons, calc sig words, and mod_sub are const time now.
* In operator>> avoid testing for zero unless requiredJack Lloyd2018-11-231-1/+1
|
* Optimize mod_subJack Lloyd2018-11-091-10/+21
| | | | | We already assumed the args are < modulus so we can avoid the call to sig_words. This provides a noticable speedup for ECDSA overall.
* Add a cache of sig words to BigIntJack Lloyd2018-11-091-20/+17
|
* Avoid unnecessary realloc in BigInt::mod_subJack Lloyd2018-06-171-2/+7
|
* Add BigInt functions for adding, subtracting and comparing with wordsJack Lloyd2018-04-261-25/+39
| | | | Avoids needless allocations for expressions like x - 1 or y <= 4.
* Add BigInt::mod_subJack Lloyd2018-04-231-0/+49
|
* Square is always positiveJack Lloyd2018-04-081-0/+1
|
* Add BigInt::square plus a speed test for BigInt multiplyJack Lloyd2018-04-081-0/+16
|
* Remove MP_WORD_BITS constantJack Lloyd2018-03-011-4/+4
| | | | Use the BOTAN_MP_WORD_BITS consistently
* Avoid needless allocation in BigInt operator+=Jack Lloyd2018-02-281-4/+2
| | | | Kind of amazing what a difference that made for overall ECDSA perf
* Avoid some needless allocationsJack Lloyd2018-02-261-11/+27
|
* Optimize Barrett reductionJack Lloyd2018-02-261-4/+53
| | | | | | | | | | OSS-Fuzz 6570 flagged an issue with slow modular exponentation. It turned out the problem was not in the library version but the simple square-and-multiply algorithm. Computing g^x % p with all three integers being dense (high Hamming weight) numbers took about 1.5 seconds on a fast machine with almost all of the time taken by the Barrett reductions. With these changes, same testcase now takes only a tiny fraction of a second.
* Add BigInt::operator*= taking a wordJack Lloyd2018-02-261-2/+17
| | | | Avoids memory allocation when multiplying by a small constant.
* Pass workspace size to various bigint_ functionsJack Lloyd2018-02-251-1/+1
| | | | | | These functions made assumptions about the workspace size available, which if incorrect would cause memory corruption. Since the length is always available at the caller, just provide it and avoid problems.
* Minor optimizations in BigInt memory handlingJack Lloyd2018-02-231-1/+3
| | | | Makes 4-6% difference for ECDSA
* Remove needless variableJack Lloyd2017-10-061-2/+0
|
* Convert to using standard uintN_t integer typesJack Lloyd2016-12-181-2/+2
| | | | | | 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.
* Reduction of code complexity in MP & ECC classes.Matthias Gierlings2016-06-191-4/+2
| | | | | | - reduced number of parameters in various methods - introduced structures and renamed variables to improve code readability.
* lib/math: Convert &vec[0] to vec.data()Daniel Seither2015-06-201-3/+3
|
* 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.
* Move lib into srclloyd2014-01-101-0/+221
generated by cgit v1.2.3 (git 2.39.1) at 2024-12-12 10:42:28 +0000