aboutsummaryrefslogtreecommitdiffstats
path: root/src/lib/math/bigint/bigint.cpp
Commit message (Collapse)AuthorAgeFilesLines
* Remove various deprecated functionsJack Lloyd2020-11-081-45/+0
|
* Remove deprecated headers, make more headers internalJack Lloyd2020-11-061-1/+1
| | | | | | | | | Now modules default to internal headers instead of defaulting to public; making a new public API should be a visible and intentional choice. Brings the public header count from over 300 to around 150. Also removes the deprecated tls_blocking interface
* Correct hash to integer conversions for ECDSAJack Lloyd2020-10-281-7/+6
| | | | | When the hash and group sizes differ sometimes our conversion was different from standard. Closes #2415
* Deprecate BigInt::shrink_to_fitJack Lloyd2020-03-211-4/+2
| | | | Add const-time annotations to gcd implementation.
* Fix underflow bug in modular inverseJack Lloyd2020-03-081-0/+2
| | | | OSS-Fuzz 21115
* Add BigInt::ct_cond_addJack Lloyd2020-03-061-0/+9
| | | | Also make low_zero_bits constant time.
* Optimize BigInt::get_substringJack Lloyd2020-02-071-9/+18
| | | | Gives a small but measurable speedup (~1-2%) for RSA and ECDSA
* Deprecate many publically available headersJack Lloyd2019-09-061-0/+7
|
* Small BigInt optimizationsJack Lloyd2019-08-221-4/+4
| | | | Based on profiling RSA key generation
* Fix warningJack Lloyd2019-01-241-3/+6
|
* Revamp BigInt encoding and decoding.Jack Lloyd2019-01-241-15/+34
| | | | Deprecate some crufty functions. Optimize binary encoding/decoding.
* 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.
* 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
* Merge GH #1774 Const time BigInt shiftsJack Lloyd2018-12-081-9/+18
|\
| * Fix bug and avoid allocations in left shiftJack Lloyd2018-12-071-9/+18
| |
* | 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-071-2/+25
|\ \ | |/ |/|
| * Add BigInt::ct_reduce_belowJack Lloyd2018-12-061-2/+25
| |
* | Better logic in BigInt::bits wrt valgrind const time checksJack Lloyd2018-12-061-2/+3
|/
* Make BigInt::cond_flip_sign constant timeJack Lloyd2018-12-051-3/+9
|
* Remove some conditional branches from divisionJack Lloyd2018-12-051-1/+6
|
* Make binary extended Euclidean algorithm less branchyJack Lloyd2018-12-031-0/+12
| | | | This is still leaky, but much less than before.
* Add ct_modulo and BigInt::ct_cond_swapJack Lloyd2018-12-031-1/+10
|
* Add a const-time division algorithmJack Lloyd2018-12-021-2/+2
| | | | | | | | It is stupid and slow (~50-100x slower than variable time version) but still useful for protecting critical algorithms. Not currently used, waiting for OSS-Fuzz to test it for a while before we commit to it.
* Add BigInt::mod_mulJack Lloyd2018-12-011-2/+0
|
* Add CT::Mask typeJack Lloyd2018-11-281-8/+16
|
* Make more BigInt functions const-timeJack Lloyd2018-11-261-17/+51
| | | | In particular comparisons, calc sig words, and mod_sub are const time now.
* Add a cache of sig words to BigIntJack Lloyd2018-11-091-38/+50
|
* Simplify BigInt::get_substring a bitJack Lloyd2018-09-151-10/+11
| | | | And forbid 0 length substrings, which did not work correctly anyway.
* Cleanup of BigInt encoding/decoding functionsJack Lloyd2018-08-141-1/+1
| | | | | | | | | | | | | Instigated by finding a bug where BigInt::encode with decimal output would often have a leading '0' char. Which is papered over in the IO operator, but was exposed by botan_mp_to_str which called BigInt::encode directly. Split BigInt::encode/decode into two versions, one taking the Base argument and the other using the (previously default) binary base. With a view of eventually deprecating the versions taking a base. Add BigInt::to_dec_string() and BigInt::to_hex_string()
* Add Lucas test from FIPS 186-4Jack Lloyd2018-07-311-0/+15
| | | | | | | | | | 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.
* Inline BigInt::shrink_to_fitJack Lloyd2018-05-091-6/+0
| | | | Improves P-256 a bit
* Add BigInt functions for adding, subtracting and comparing with wordsJack Lloyd2018-04-261-0/+12
| | | | Avoids needless allocations for expressions like x - 1 or y <= 4.
* Add const time annotationsJack Lloyd2018-04-151-0/+12
|
* Shift ECDSA inputs to match OpenSSL behaviorJack Lloyd2018-03-211-0/+12
| | | | See also GH #986
* Simplify a common case BigInt constructorJack Lloyd2018-03-211-0/+5
|
* Store base point multiplies in a single std::vectorJack Lloyd2018-03-201-0/+11
| | | | | | | | | | | Since the point is public all the values are also, so this reduces pressure on the mlock allocator and may (slightly) help perf through cache read-ahead. Downside is cache based side channels are slightly easier (vs the data being stored in discontigious vectors). But we shouldn't rely on that in any case. And having it be in an array makes a masked table lookup easier to arrange.
* Remove MP_WORD_BITS constantJack Lloyd2018-03-011-6/+6
| | | | Use the BOTAN_MP_WORD_BITS consistently
* Inline some simple BigInt sign handling functionsJack Lloyd2018-03-011-29/+0
|
* Optimize P-256 and P-384 reductionJack Lloyd2018-02-261-3/+9
| | | | Precompute the multiples of the prime and then subtract directly.
* Optimize Barrett reductionJack Lloyd2018-02-261-0/+5
| | | | | | | | | | 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.
* Use reduce_below in PointGFpJack Lloyd2018-02-251-0/+2
| | | | Improves ECDSA times by 2-3%
* Add BigInt::reduce_belowJack Lloyd2018-02-251-0/+24
|
* Minor optimizations in BigInt memory handlingJack Lloyd2018-02-231-1/+1
| | | | Makes 4-6% difference for ECDSA
* New API for blinded ECC point multiplicationJack Lloyd2018-02-211-1/+1
| | | | No shared state
* Tiny optimization in BigInt::const_time_lookupJack Lloyd2018-02-131-1/+3
|
* Add wrappers for reinterpret_cast between char* and uint8_t*Jack Lloyd2017-10-031-1/+1
| | | | | | | Generally speaking reinterpret_cast is sketchy stuff. But the special case of char*/uint8_t* is both common and safe. By isolating those, the remaining (likely sketchy) cases are easier to grep for.
* Add valgrind annotations to check const_time_lookupJack Lloyd2017-09-261-0/+5
|
* Use a side channel silent table look up in the Montgomery exponentiationJack Lloyd2017-09-251-0/+24
|
generated by cgit v1.2.3 (git 2.39.1) at 2024-12-13 23:34:28 +0000