aboutsummaryrefslogtreecommitdiffstats
path: root/src/lib/math/numbertheory
Commit message (Collapse)AuthorAgeFilesLines
* increase miller-rabin iterations for dsa primes (FIPS-186-4)Never2017-02-131-2/+2
|
* Remove unused iostream includeJack Lloyd2017-01-201-1/+0
| | | | [ci skip]
* Tiny code simplificationJack Lloyd2016-12-301-3/+1
|
* Speed up DSA param gen testJack Lloyd2016-12-262-8/+14
| | | | Record counter value in test data, and start the search from there.
* Convert to using standard uintN_t integer typesJack Lloyd2016-12-188-19/+19
| | | | | | 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.
* Remove debug codeJack Lloyd2016-12-141-1/+1
|
* Fix exponentiation bug, related fixesJack Lloyd2016-12-146-15/+55
| | | | | | | | | | | | | | | GH #754 exposed a bug in the non-Montgomery exponentiation case. It turned out then when the fixed window was picked to any value > 1, the result would be incorrect due to an off by one. This is the one line fix in powm_fw.cpp Also fix a bug in bigint_mul which caused incorrect results, because the output BigInt was not being zeroed out before use. This is only exposed in rare cases, found (somewhat indirectly) in OSS-Fuzz #287. Add more modular exponentiation tests, which would have caught these issues earlier.
* In ressol, prohibit a >= pJack Lloyd2016-12-111-3/+5
| | | | Technically defined, but should never be seen in practical crypto context.
* Fix DSA parameter generation to use the correct loop bound.Jack Lloyd2016-11-031-5/+3
| | | | | | | | 4096 is the value from FIPS 186-2, FIPS 186-3 uses 4*pbits which is the obvious extension of the FIPS 186-2 scheme to larger parameter sizes. Pointed out by @neverhub Removes support for 512 and 768 bit DSA groups because WTF no.
* Fix doxygen warnings [ci skip]René Korthaus2016-10-191-2/+0
|
* Reduction of code complexity in MP & ECC classes.Matthias Gierlings2016-06-192-31/+13
| | | | | | - reduced number of parameters in various methods - introduced structures and renamed variables to improve code readability.
* Add explicit static_cast operations to eliminate implicit cast compiler ↵Dan Brown2016-04-272-2/+2
| | | | warnings.
* Add ECGDSARené Korthaus2016-04-192-0/+25
|
* Fix off by one in ressolJack Lloyd2016-03-151-1/+1
| | | | | Could attempt to allocate (size_t)-1 words with predicably bad_alloc results.
* Remaining cppcheck fixes that are not covered by GH #444Daniel Neus2016-03-052-9/+11
|
* cppcheck fixes: Class 'X' has a constructor with 1 argument that is not ↵Daniel Neus2016-03-052-2/+2
| | | | explicit.
* For odd moduli use a input-independent modular inverse algorithm.Jack Lloyd2016-02-202-36/+198
| | | | Also adds a (not const time) implementation of almost Montgomery reduction.
* Add tests and timings for inverse_modJack Lloyd2016-02-202-5/+13
|
* Fix two bugs in 1.11.27 which caused test failures.1.11.28Jack Lloyd2016-02-011-1/+1
| | | | | | | | | | | | | The check on each individual size in curve_mul is too strict since we rely on redc(x*1) during the on the curve computation. Fix an off by one in ressol which caused it to occasionally reject valid values. Updating version 1.11.28 since existing 1.11.27 tag already pushed :( Fix an off-by-one in ressol which would cause it to occasionly give up too early.
* Fix (nearly) infinite loop in RESSOL (modular square root).Jack Lloyd2016-02-011-8/+12
| | | | | | | It first computed the first i for q**(2**i) == 1, then checked that i was smaller than s. Given a composite modulus (for which the algorithm does not work), the loop might do a very large amount of work before returning the failure.
* Mass-prefix member vars with m_René Korthaus2016-01-085-49/+49
|
* Reroot the exception hierarchy into a toplevel Exception classJack Lloyd2015-12-111-1/+1
| | | | | | | | As the alternatives are unfortunate for applications trying to catch all library errors, and it seems deriving from std::runtime_error causes problems with MSVC DLLs (GH #340) Effectively reverts 2837e915d82e43
* Add prime and dl_group command line tools.Jack Lloyd2015-10-151-14/+42
| | | | | | Some cleanups in random_prime. Increase probability in prime tests from 1/2**64 to 1/2**128. Also break out of the sieve loop early if it has failed.
* Remove use of lookup.h in favor of new T::create API.Jack Lloyd2015-09-211-2/+4
|
* Add m_ prefix to member variable Power_Mod::m_coreSimon Warta2015-08-212-23/+23
|
* Expose the NIST prime values and reduction operations as plain functions.Jack Lloyd2015-08-081-14/+0
| | | | | | Previously they were hidden away as private functions on the CurveGFp types. This allows directly testing the reduction functions against other computational methods.
* math: Add missing overridesDaniel Seither2015-07-301-8/+8
|
* Fix round_upSimon Warta2015-07-151-1/+1
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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
* Make Botan compile when only some modules are enabledSimon Warta2015-07-031-1/+1
| | | | Fixes #146.
* lib/math: Convert &vec[0] to vec.data()Daniel Seither2015-06-203-9/+9
|
* Fix various bugs found by Coverity scanner.lloyd2015-05-152-0/+4
| | | | | | | Uninitialized variables, missing divide by zero checks, missing virtual destructor, etc. Only thing serious is bug in TLS maximum fragment decoder; missing breaks in switch statement meant receiver would treat any negotiated max frament as 4k limit.
* Fixlloyd2015-04-121-1/+1
|
* Remove the stray binary character making Python3 unhappy, removelloyd2015-04-121-3/+2
| | | | encoding= flags since they are not needed anymore and broke Python2.
* Cleanupslloyd2015-03-231-1/+1
|
* Remove algo factory, engines, global RNG, global state, etc.lloyd2015-02-041-2/+0
| | | | | | | | | | | | | | | Convert all uses of Algorithm_Factory and the engines to using Algo_Registry The shared pool of entropy sources remains but is moved to EntropySource. With that and few remaining initializations (default OIDs and aliases) moved elsewhere, the global state is empty and init and shutdown are no-ops. Remove almost all of the headers and code for handling the global state, except LibraryInitializer which remains as a compatability stub. Update seeding for blinding so only one hacky almost-global RNG instance needs to be setup instead of across all pubkey uses (it uses either the system RNG or an AutoSeeded_RNG if the system RNG is not available).
* Convert PK operations to using Algo_Registry instead of Engine.lloyd2015-02-031-18/+6
| | | | Remove global PRNG.
* Add missing files. Remove cipher lookup from engine code.lloyd2015-02-012-10/+3
|
* Ensure all files have copyright and license info.lloyd2015-01-1015-15/+15
| | | | | Update license header line to specify the terms and refer to the file, neither of which it included before.
* Any fixed MR iterations is probably wrong for somebody. Allow the userlloyd2014-04-254-7/+49
| | | | | | to specify a probability as well as if n was randomly chosen or not. If the input is random use a better bounds to reduce the number of needed tests.
* Use 20 Miller-Rabin iterations regardless of the size of the integer. Thislloyd2014-04-132-184/+39
| | | | | provides a much better worst-case error bound. Also take the nonce from anywhere in the usable range rather than limiting the bit size.
* Fix a bug in Miller-Rabin primality testing introduced in 1.8.3lloyd2014-04-101-5/+6
| | | | | | | | where we chose a single random nonce and tested it repeatedly, rather than choosing new nonces each time. Reported by Jeff Marrison. Also remove a pointless comparison (also pointed out by Jeff) and add an initial test using a witness of 2.
* Clang fixeslloyd2014-02-091-1/+0
|
* Guess I won't be needing theselloyd2014-01-181-1/+0
|
* Move lib into srclloyd2014-01-1016-0/+2463