aboutsummaryrefslogtreecommitdiffstats
path: root/src/lib/math/bigint
Commit message (Collapse)AuthorAgeFilesLines
* Deprecate BigInt::shrink_to_fitJack Lloyd2020-03-212-5/+5
| | | | Add const-time annotations to gcd implementation.
* Fix underflow bug in modular inverseJack Lloyd2020-03-081-0/+2
| | | | OSS-Fuzz 21115
* Merge GH #2297 Add BigInt::ct_cond_addJack Lloyd2020-03-062-1/+15
|\
| * Add BigInt::ct_cond_addJack Lloyd2020-03-062-1/+15
| | | | | | | | Also make low_zero_bits constant time.
* | 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.
* Optimize BigInt::get_substringJack Lloyd2020-02-071-9/+18
| | | | Gives a small but measurable speedup (~1-2%) for RSA and ECDSA
* 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.
* Deprecate many publically available headersJack Lloyd2019-09-063-6/+10
|
* 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-223-11/+12
| | | | Based on profiling RSA key generation
* 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.
* 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.
* 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
* 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.
* 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
generated by cgit v1.2.3 (git 2.39.1) at 2024-12-22 22:10:14 +0000