aboutsummaryrefslogtreecommitdiffstats
path: root/src/lib/math/bigint
Commit message (Collapse)AuthorAgeFilesLines
* Merge GH #1774 Const time BigInt shiftsJack Lloyd2018-12-085-41/+40
|\
| * Fix bug and avoid allocations in left shiftJack Lloyd2018-12-074-19/+33
| |
| * Const time the behavior of shifts [WIP]Jack Lloyd2018-12-062-31/+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.
* | 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-072-2/+37
|\ \ | |/ |/|
| * Add BigInt::ct_reduce_belowJack Lloyd2018-12-062-2/+37
| |
* | Better logic in BigInt::bits wrt valgrind const time checksJack Lloyd2018-12-061-2/+3
|/
* Do swaps in PointGFp instead of copiesJack Lloyd2018-12-051-1/+1
| | | | Saves 5% for ECDSA
* Avoid needless is_zero check in set_signJack Lloyd2018-12-051-4/+4
| | | | If not negative we don't need to check the size
* Make BigInt::cond_flip_sign constant timeJack Lloyd2018-12-051-3/+9
|
* Use BigInt::cond_flip_signJack Lloyd2018-12-053-7/+4
|
* Don't leak if x is zero eitherJack Lloyd2018-12-051-39/+37
|
* Remove some conditional branches from divisionJack Lloyd2018-12-053-22/+27
|
* Make binary extended Euclidean algorithm less branchyJack Lloyd2018-12-032-0/+17
| | | | This is still leaky, but much less than before.
* Extend ct_modulo to handle negative inputsJack Lloyd2018-12-031-8/+17
| | | | Unfortunately Barrett reductions API allows negative inputs
* Use const time reductions in Barrett and LCM computationsJack Lloyd2018-12-031-0/+17
|
* Fix shift operatorJack Lloyd2018-12-031-1/+1
| | | | This would continually reallocate to larger sizes which is bad news.
* Add ct_modulo and BigInt::ct_cond_swapJack Lloyd2018-12-034-7/+62
|
* Merge GH #1759 Add constant time divide by uint8_tJack Lloyd2018-12-033-7/+59
|\
| * Add a constant time divide variant for dividing by uint8_tJack Lloyd2018-12-023-7/+59
| | | | | | | | | | | | | | | | | | Originally wrote it for div-by-word but that ends up requiring a dword type which we don't always have. And uint8_t covers the most important cases of n = 10 and n = 58 (whenever I get around to writing base58). We could portably support up to div-by-uint32, but I don't think we need it. Nicely for n = 10, this is actually faster than the variable time division.
* | Make variable time division less branchyJack Lloyd2018-12-021-53/+46
|/ | | | This is still leaky, but better than nothing.
* Add a const-time division algorithmJack Lloyd2018-12-024-8/+69
| | | | | | | | 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.
* Correct a bug in BigInt::operator%(word)Jack Lloyd2018-12-012-21/+26
| | | | | | 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-013-13/+41
|
* Simplify BigInt addition and subtractionJack Lloyd2018-11-303-184/+115
| | | | | Addition already has to handle negative numbers so make it do double duty for subtraction.
* Add CT::Mask typeJack Lloyd2018-11-282-9/+17
|
* Make more BigInt functions const-timeJack Lloyd2018-11-263-74/+128
| | | | In particular comparisons, calc sig words, and mod_sub are const time now.
* Merge GH #1744 Make exception throws easier to debugJack Lloyd2018-11-232-3/+6
|\
| * Make exceptions easier to translate to error codesJack Lloyd2018-11-232-3/+6
| | | | | | | | | | | | | | | | | | | | | | 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
* | In operator>> avoid testing for zero unless requiredJack Lloyd2018-11-231-1/+1
|/
* Use resize instead of shrink_to_fitJack Lloyd2018-11-091-0/+7
| | | | Avoid recalculating significant words which slows down reduction
* 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-093-97/+232
|
* Simplify BigInt::is_zeroJack Lloyd2018-11-061-6/+1
| | | | | | The definition of return value of sig_words() means the integer is zero iff sig_words() returns zero, so there is no reason to scan over the data twice.
* Simplify BigInt::get_substring a bitJack Lloyd2018-09-151-10/+11
| | | | And forbid 0 length substrings, which did not work correctly anyway.
* Remove unneeded load_on autoJack Lloyd2018-09-041-2/+0
| | | | It is the default...
* Add operator*(BigInt, word)Jack Lloyd2018-08-232-0/+21
| | | | | Gets hit about 2 million times in the test suite, avoids creating a temp BigInt (with alloc+free) or checking size of y.
* Fix some Doxygen warningsJack Lloyd2018-08-151-1/+0
|
* Fix BigInt::to_{dec,hex}_string for zeroJack Lloyd2018-08-151-1/+8
| | | | They returned an empty string instead
* Cleanup of BigInt encoding/decoding functionsJack Lloyd2018-08-143-16/+138
| | | | | | | | | | | | | 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-312-0/+21
| | | | | | | | | | 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.
* Check arguments to BigInt::random_integerJack Lloyd2018-06-292-2/+5
|
* Document preconditions of BigInt::mod_add/mod_subJack Lloyd2018-06-231-0/+2
|
* Avoid needless alloc and copyJack Lloyd2018-06-211-0/+6
|
* Avoid unnecessary realloc in BigInt::mod_subJack Lloyd2018-06-171-2/+7
|
* Fix a bug in Barrett reductionJack Lloyd2018-06-051-4/+3
| | | | | | -x*n % n would reduce to n instead of zero. Also some small optimizations and cleanups.
* Inline BigInt::shrink_to_fitJack Lloyd2018-05-092-7/+5
| | | | Improves P-256 a bit
* Inline this operator+ [ci skip]Jack Lloyd2018-04-262-6/+1
|
* Add BigInt functions for adding, subtracting and comparing with wordsJack Lloyd2018-04-264-51/+142
| | | | Avoids needless allocations for expressions like x - 1 or y <= 4.
generated by cgit v1.2.3 (git 2.39.1) at 2024-12-26 02:03:25 +0000