aboutsummaryrefslogtreecommitdiffstats
path: root/src/lib/math/bigint/bigint.cpp
Commit message (Collapse)AuthorAgeFilesLines
* 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
|
* Header file cleanupsJack Lloyd2017-09-211-2/+0
| | | | Some help from include-what-you-use
* Convert to using standard uintN_t integer typesJack Lloyd2016-12-181-15/+15
| | | | | | 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.
* Internal header cleanupsJack Lloyd2015-09-191-1/+1
| | | | Only user-visible change is the removal of get_byte.h
* Fix BigInt random_integer() distribution issue.Simon Warta2015-07-241-2/+2
| | | | Fixes #108
* Refactor BigIntSimon Warta2015-07-241-0/+11
|
* BigInt::to_u32bit failed on 32-bit integers. GH #220Jack Lloyd2015-07-231-1/+1
|
* Fix round_upSimon Warta2015-07-151-2/+2
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 1. src/lib/codec/base64/base64.cpp: : (round_up<size_t>(input_length, 3) / 3) * 4; 2. src/lib/codec/base64/base64.cpp: : (round_up<size_t>(input_length, 4) * 3) / 4; 3. src/lib/filters/transform_filter.cpp: return round_up(target_size, update_granularity); 4. src/lib/math/bigint/bigint.cpp: m_reg.resize(round_up<size_t>(size, 8)); 5. src/lib/math/bigint/bigint.cpp: m_reg.resize(round_up<size_t>((length / WORD_BYTES) + 1, 8)); 6. src/lib/math/numbertheory/mp_numth.cpp: BigInt z(BigInt::Positive, round_up<size_t>(2*x_sw, 16)); 7. src/lib/modes/cbc/cbc.cpp: return round_up(input_length, cipher().block_size()); 8. src/lib/modes/ecb/ecb.cpp: return round_up(input_length, cipher().block_size()); 9. src/lib/modes/xts/xts.cpp: return round_up(input_length, cipher().block_size()); 10. src/lib/pbkdf/pbkdf2/pbkdf2.cpp: const size_t blocks_needed = round_up(out_len, prf_sz) / prf_sz; 11. src/lib/tls/tls_record.cpp: const size_t buf_size = round_up( 12. src/lib/utils/rounding.h:inline T round_up(T n, T align_to) 1. Reason for change 2. Reason for change 3. first argument cannot be 0 (`target_size = 1024`) 4. Is a bug in the current implementation iff `size = 0` 5. first argument cannot be 0 6. round_up should return 0 if `x_sw = 0` 7. ? 8. ? 9. ? 10. first argument cannot be 0 (`if(out_len == 0) return 0;`) 11. first argument is unlikely to be 0 (`iv_size + msg_length + mac_size + (block_size ? 1 : 0)`) 12. Implementation
* Add specialized reducers for P-192, P-224, P-256 and P-384lloyd2015-02-261-36/+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.
* Inline BigInt::get_bit and byte_atlloyd2015-01-081-21/+0
|
* Add specialized reduction for P-521 along with 9x9 Comba routines.lloyd2014-11-151-8/+3
| | | | | Roughly 35-50% faster on my laptop (depending on if mlock is enabled, the overhead in that allocator is becoming much more of a hotspot).
* Avoid a ubsan warning on GCC 4.9 due uninitialized sign enum beinglloyd2014-03-301-4/+0
| | | | read during swap (in the move constructor)
* Move lib into srclloyd2014-01-101-0/+350