aboutsummaryrefslogtreecommitdiffstats
path: root/src/math
Commit message (Collapse)AuthorAgeFilesLines
* Invert the meaning of the Miller-Rabin test; passes_test meant 'is notlloyd2011-06-161-9/+17
| | | | | | | | | | a witness'. Instead call it 'is_witness', returning true if a is a witness for n's compositness, or otherwise false. Also, the previous version would not check that the final value of y was n-1; if it isn't, then n is not prime. This would mean the false negative rate was higher than it should have been, though I'm not sure by how much exactly.
* Simplify Montgomery setup here a bitlloyd2011-06-071-6/+4
|
* Change order of arguments to bigint_monty_redc (internal interface,lloyd2011-06-023-46/+43
| | | | | | not exposed to callers) Switch back redc to using the inlined version (accidental change)
* Add monty sqr and multiply routines (they just call karatsuba and thenlloyd2011-06-024-43/+77
| | | | redc, currently)
* Reduce number of temporaries needed in point additionlloyd2011-06-011-22/+14
|
* Multi-expoentiation, using the single bit variation. Using a 2 or 3lloyd2011-06-012-0/+45
| | | | | | bit window may well improve things further. Currently seeing 20-25% improvement in ECDSA signature verification and 25 to 40% in GOST-34.10 verifications.
* Only call p.sig_words once in CurveGFp constructor.lloyd2011-05-191-4/+2
| | | | Fix build log; copy and paste error.
* Move the curve over GF(p) code back into its own subdirlloyd2011-05-195-5/+18
|
* Small cleanup in the Barrett reducer, now doesn't create a temp iflloyd2011-05-182-33/+35
| | | | abs(x) < modulus. Also remove unused member variables.
* Modify ECC points to do all math in Montgomery form, rather thanlloyd2011-05-174-156/+144
| | | | | | | | | | | | | converting back and forth. This gives a 10 to 20% speedup on a Core i7. In addition, the CurveGFp no longer contains a Barrett reducer, saving 3 BigInts worth of memory. Add a #if'ed out alternative to point multiplication using the Montgomery ladder technique. It runs in (more or less) constant time, but rather significantly slower than the 4 bit window technique currently used. Tweak the window sizes to match the theoretical optimums.
* Always writing to/reading from the carry word makes valgrind unhappy.lloyd2011-05-161-1/+2
|
* Add base64_decode. Seems to work OK, though incremental decoding islloyd2011-05-121-1/+0
| | | | not well tested.
* Add back BigInt::to_u32bitlloyd2011-05-102-17/+45
| | | | | | | Fix BigInt::get_substring when length is equal to 32 - an overflow would cause the mask to be equal to 0 thus producing nothing at all. Disable CVC by default, it's not ready for prime time in any sense.
* dword was set to a size_t if we were using a 16 bit limb. Caused by anlloyd2011-05-091-1/+1
| | | | overzealous perl script...
* Flatten out the mp directory since no alternative asm implemenationslloyd2011-04-256-13/+3
| | | | | | | for Montgomery or multiply/square currently exist and almost ceratainly won't be added during 1.10 Fix the name for Sun Studio in mp_asm64
* Rename all references of ia32 to x86-32 and amd64 to x86-64.lloyd2011-04-2211-10/+9
| | | | | | Back the reported version from 1.10.0 to 1.9.17 for the time being. Still on the fence if this will be 1.10.0 or another release candidate instead.
* More VC warning fixeslloyd2011-02-091-2/+4
|
* Oops - should not have used size_t here!lloyd2010-12-221-1/+1
|
* Avoid more VC warningslloyd2010-12-131-2/+2
|
* Avoid a conditional in point multiplicationlloyd2010-12-071-11/+7
|
* Use append operator instead of copylloyd2010-12-071-21/+16
|
* Compile fixlloyd2010-11-021-1/+1
|
* Doxygenlloyd2010-11-021-2/+1
|
* Make MemoryRegion::set protected, change all callerslloyd2010-10-292-4/+13
|
* BigInt::get_substring really shouldn't return size_t. Revert tolloyd2010-10-185-10/+8
| | | | | | u32bit. Maybe should be word? But that would restrict window sizes more than might be desirable (we couldn't use more than 8 bit window on the assumption that the lib might be using byte limbs). Messy.
* For const BigInt::operator[], return a const reference instead of alloyd2010-10-181-1/+1
| | | | | value, so you can always safely capture the result by a const reference.
* Use output_length() instead of OUTPUT_LENGTH pseudo-propertylloyd2010-10-131-1/+1
|
* Use size_t in all of math, remove to_u32bitlloyd2010-10-1234-373/+348
|
* Change ifs to compares to make it easier for a compiler to figure outlloyd2010-10-121-11/+9
| | | | | | it should use add with carry or conditional moves if available. Also remove the amd64 asm; the mp_amd64 code should be used for this case.
* Tidylloyd2010-09-301-1/+2
|
* Cleanup Karatsuba a bitlloyd2010-09-281-103/+107
|
* Cleanuplloyd2010-09-261-9/+9
|
* At some point I 'simplified' the divide code to always run thelloyd2010-09-261-1/+5
| | | | | | | | | | division algorithm unless x == y, but this could result in n - t + 1 being negative which would cause an attempt to allocate about 4 gigabytes of memory. Fix this, and also add an assertion check in the code to ensure that can't happen in any other way. Never reproduced this with 32 bit digits but it would show up if the build used 8 or 16 bit words.
* Move the core MPI functions to src/math/mp, leaving src/math/bigint justlloyd2010-09-2428-13/+24
| | | | for the implementation of the BigInt class
* Delete obsolete asm versionslloyd2010-09-247-781/+0
|
* Minor performance tweak, avoid zeroing things we'll immediately writelloyd2010-09-241-2/+1
| | | | to. Helps more than I would have thought.
* Modify bigint_monty_redc to take an additional workspace argument.lloyd2010-09-245-71/+83
| | | | | | | Modify it to avoid a timing condition during the compare at the end; this is done by always doing the subtraction, and then copying to the output either the pre-subtraction or post-subtraction value depending on if the final borrow was set or not.
* s/carry/borrow/ in subtraction routineslloyd2010-09-241-14/+18
|
* s/j/i for loop variableslloyd2010-09-241-36/+36
|
* Cleanuplloyd2010-09-232-16/+24
|
* Make these functions mostly constant-time, and in particular notlloyd2010-09-231-29/+9
| | | | | depending on the value of the final carry out for anything control-flow related.
* Update all uses of MemoryRegion::append to use either push_back or operator+=lloyd2010-09-151-4/+3
|
* More changes to avoid vector to pointer implicit conversionslloyd2010-09-142-6/+6
|
* More vector->pointer conversion removals.lloyd2010-09-132-5/+3
| | | | | | | | | | | Add RandomNumberGenerator::random_vec, which takes an length n and returns a new SecureVector with randomized contents of that size. This nicely covers most of the cases where randomize was being called on a vector, and is a little cleaner in the code as well, instead of vec.resize(length); rng.randomize(&vec[0], vec.size()); we just write vec = rng.random_vec(length);
* First set of changes for avoiding use implicit vector->pointer conversionslloyd2010-09-132-7/+7
|
* Anywhere where we use MemoryRegion::begin to get access to the raw pointerlloyd2010-09-135-16/+16
| | | | | representation (rather than in an interator context), instead use &buf[0], which works for both MemoryRegion and std::vector
* Big, invasive but mostly automated change, with a further attempt atlloyd2010-09-075-11/+11
| | | | | | | | | | | | | | harmonising MemoryRegion with std::vector: The MemoryRegion::clear() function would zeroise the buffer, but keep the memory allocated and the size unchanged. This is very different from STL's clear(), which is basically the equivalent to what is called destroy() in MemoryRegion. So to be able to replace MemoryRegion with a std::vector, we have to rename destroy() to clear() and we have to expose the current functionality of clear() in some other way, since vector doesn't support this operation. Do so by adding a global function named zeroise() which takes a MemoryRegion which is zeroed. Remove clear() to ensure all callers are updated.
* Realization while thinking about the recently added truncate: in a STLlloyd2010-09-072-5/+5
| | | | | | | | | | | | | | | | | | container like vector, truncate is simply resize, but what MemoryRegion called resize will zap the entire contents, and then what was resize was called grow_to. This is really problematic in terms of the goal of replacing MemoryRegion with a vector with a custom allocator. In this checkin: - Remove MemoryRegion::grow_to and MemoryRegion::truncate - Change the semantics of MemoryRegion::resize to change the size while keeping any current contents intact (up to the new size), zero initializing any new values. Unrelated, just noticed the lack while I was in there, add a version of CryptoBox::decrypt taking a std::string for the input.
* Avoid name clashing, Sun Studio doesn't like thislloyd2010-09-071-2/+3
|
* Update some callers that were using Hex_Encoder or Hex_Decoder butlloyd2010-09-031-15/+17
| | | | | | | | | | | | | | | | | | really didn't need to. The ones in symkey and big_code were actually calling accessor functions to do the encoding themselves without a Pipe (should have definitely recognized that as a code smell). These versions have changed semantically with this checkin - previously they would completely ignore bad inputs, but now invalid inputs are rejected. For instance, you cannot say SymmetricKey key("Only some of this is hex, most of it isn't"); And expect to get a valid key formed by filtering out the non-hex characters and then decoding it. This is almost certainly a good thing. Also fix include in Botan.xs
generated by cgit v1.2.3 (git 2.39.1) at 2024-12-14 05:13:32 +0000