aboutsummaryrefslogtreecommitdiffstats
path: root/src/lib/math
Commit message (Collapse)AuthorAgeFilesLines
* Speed up DSA param genJack Lloyd2018-05-211-3/+6
| | | | Using Barrett reduction instead of division is ~10x faster.
* Fix typo in comment [ci skip]Jack Lloyd2018-05-171-1/+1
|
* Add clarifying comments and increase M-R tests for 256-bit integersJack Lloyd2018-05-151-3/+7
| | | | See #1542 and #1569
* Always use 1/2^-128 error bounds with Miller-RabinJack Lloyd2018-05-141-24/+14
| | | | | | | Simplifies the code and makes it easy to see we never use the weaker bounds even if the application expicitly requested it. GH #1569
* Add message to BOTAN_ARG_CHECK and use it more widelyJack Lloyd2018-05-131-2/+1
|
* Inline BigInt::shrink_to_fitJack Lloyd2018-05-092-7/+5
| | | | Improves P-256 a bit
* Add 24-word wide Comba multiply/squareJack Lloyd2018-05-083-1/+1101
| | | | | | Improves performance on "odd" sized DH/RSA (eg 1536, 3072, 6144) where otherwise the Karatsuba operation bottoms out with 24-word operands which ended up in the basecase multiply.
* Remove needless allocation in Montgomery_Int::mul_byJack Lloyd2018-05-022-7/+41
|
* Make Montgomery_Int public, add function for addition with workspaceJack Lloyd2018-05-022-3/+11
|
* Inline this operator+ [ci skip]Jack Lloyd2018-04-262-6/+1
|
* Correct handling of gcd(p - 1, e) in RSA keygenJack Lloyd2018-04-261-7/+25
| | | | | | | | | | We were calling inverse mod but because p - 1 > e the binary extended euclidean algorithm was used instead of the const time version. Use the fact that e is odd (for RSA keys) to remove the factors of 2 from p - 1 and then check coprimality that way, since it allows using our const time algo.
* Rewrite GCD in less branchy way, and use Montgomery in M-R testJack Lloyd2018-04-261-16/+30
|
* 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.
* Add BigInt::mod_subJack Lloyd2018-04-232-0/+65
|
* Add early exit for P-192 reduceJack Lloyd2018-04-181-0/+5
|
* Remove now unused functionJack Lloyd2018-04-181-19/+0
|
* Optimize P-224 reductionJack Lloyd2018-04-181-47/+77
| | | | 5-7% faster ECDSA
* Further NIST reduction tweaksJack Lloyd2018-04-181-40/+44
|
* P-192 optimizationsJack Lloyd2018-04-181-34/+64
| | | | 5-7% faster for ECDSA and ECDH
* Micro optimizations in P-256 and P-384 reductionsJack Lloyd2018-04-181-30/+73
| | | | Improves ECDSA and ECDH by 1% or so.
* Minor optimizations for P-256 and P-384Jack Lloyd2018-04-171-161/+65
| | | | Improves ECDSA by ~5% on Skylake
* Avoid potential side channel when generating RSA primesJack Lloyd2018-04-173-41/+173
| | | | | | | | | | Add a new function dedicated to generating RSA primes. Don't test for p.bits() > bits until the very end - rarely happens, and speeds up prime generation quite noticably. Add Miller-Rabin error probabilities for 1/2**128, which again speeds up RSA keygen and DL param gen quite a bit.
* Add vars to split the two Karatsuba sub-workspacesJack Lloyd2018-04-161-14/+20
|
* Add const time annotationsJack Lloyd2018-04-155-6/+42
|
* Simplify Karatsuba codeJack Lloyd2018-04-153-39/+43
| | | | And set us up for eventually having this be completely const time.
* Add a Montgomery exponentiation that takes variable timeJack Lloyd2018-04-092-0/+38
| | | | | | | | In the case of RSA encryption/verification the public exponent is... public. So we don't need to carefully guard against side channels that leak the exponent. Improves RSA verification performance by 50% or more.
* Square is always positiveJack Lloyd2018-04-081-0/+1
|
* Add BigInt::square plus a speed test for BigInt multiplyJack Lloyd2018-04-083-8/+25
|
* Convert comba script to Python3Jack Lloyd2018-04-081-1/+1
|
* Split up asm constructs to avoid miscompilationJack Lloyd2018-04-051-30/+49
| | | | | | | The constraints were invalid as they missed the clobber of a/d registers. This caused miscompilation when using GCC -fno-plt option. GH #1524
* Fix some Doxygen errorsJack Lloyd2018-03-282-1/+3
|
* In Barrett avoid creating an unnecessary tempJack Lloyd2018-03-251-4/+4
|
* Fix some corner cases for small values in power_modJack Lloyd2018-03-241-1/+15
|
* Tiny optimization in Montgomery inverseJack Lloyd2018-03-221-1/+1
|
* Shift ECDSA inputs to match OpenSSL behaviorJack Lloyd2018-03-212-0/+21
| | | | See also GH #986
* Simplify a common case BigInt constructorJack Lloyd2018-03-212-1/+13
|
* Store base point multiplies in a single std::vectorJack Lloyd2018-03-202-0/+17
| | | | | | | | | | | 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 use of ;; to end linesJack Lloyd2018-03-192-2/+2
|
* Add basecase_sqr functionJack Lloyd2018-03-161-3/+29
| | | | | | Just a simple adaption of the n^2 multiply algorithm, so no performance impact. However makes the difference between squaring and multiply easier to see when profiling.
* Add Montgomery multiexponentiationJack Lloyd2018-03-154-0/+95
|
* Some additional operations on Montgomery_IntJack Lloyd2018-03-142-0/+45
| | | | Needed for #1432
* Add a facility for debug-mode assertionsJack Lloyd2018-03-141-3/+7
| | | | | When we want to check something but it is to expensive to do so in normal builds.
* Improve memory handling for PointGFpJack Lloyd2018-03-143-6/+3
|
* Allow passing workspace to Montgomery_IntJack Lloyd2018-03-133-34/+140
| | | | | | | Improves DH and RSA by 5-15% depending on param sizes. At larger sizes (3072+) doesn't make much difference since the cost of allocation is relatively small compared to the work.
* Reduce exponent size hereJack Lloyd2018-03-101-1/+1
| | | | Triggers for RSA exponents which improves RSA verify time by ~10%
* Add some helper functions for checking for Comba sizesJack Lloyd2018-03-101-15/+27
|
* Simplify indexing in this loopJack Lloyd2018-03-041-5/+5
|
* Fix header includesJack Lloyd2018-03-022-2/+3
|
* Implement product-scanning Montgomery reductionJack Lloyd2018-03-022-30/+88
| | | | | Results in 10-20% improvement for DH and RSA, 5% for ECC curves that use Montgomery form.
* Tiny but useful optimization in bigint_monty_redcJack Lloyd2018-03-011-1/+1
| | | | Increases perf of larger DH by 5-8%
generated by cgit v1.2.3 (git 2.39.1) at 2024-12-10 02:06:14 +0000