This is the backbone implementation of our paper McEliece needs a Break and our second paper New Time-Memory Trade-Offs for Subset-Sum.
This repository aims to provide a STL which a few unique tweakes:
- Most (if not all) datastructures implemented in this library do not have a delete/remove operation. Meaning you cannot delete an element once inserted into the datastructure. But its possible to clear (or reset) the whole datastructure at once. Which doesnt super useful in general is very useful in the setting of cryptanalysis, where we only insert "useful" elements. And after we checked if there is no (partial-) solution somewhere, we can simply clear everything and start from the beginnning.
- constexpr: All datastructure assume that you know beforehand how many elements you need to insert. Or many elements you have to store at max. E.g. resizing of any datastructure is not possible. Also memory will never freed.
- HPC: All datastructure are optimized or implemented in a way to reduce cache-misses.
Basically you need a C++20 rdy compiler, cmake 3.20. For testing and
benchmarking you need gtest and googlebenchmark.
sudo pacman -S cmake make gtest benchmark clangsudo apt install libgtest-dev googletest cmake make It could be that googletest is not correctly installed, if so try;
# gtest is somehow quite difficult:
sudo cd /usr/src/gtest
sudo cmake .
sudo make
sudo cp *.a /usr/libnix-shell
mkdir build
cd build
cmake ..
makebrew install cmake make googletest autoconf automake libtool google-benchmark gcc libompMake sure that you use clang for the compilation via adding -DCMAKE_CXX_COMPILER=clang++
to the cmake command.
I wish you luck with this one.
-
= clang-11
-
= gcc-11
Specially gcc-10 is not supported, as it's not supporting basic concepts functionalities.
git clone --recurse-submodules -j4 https://github.com/FloydZ/cryptanalysislib
cd cryptanalysislib && mkdir build && cd build && cmake .. -DCMAKE_BUILD_TYPE=ReleaseA few notes on the cmake flags:
- for debugging you can also pass
-DCMAKE_BUILD_TYPE=Debug. - if you do not pass any flag (so neither
Debug, norRelease) and optimized build without SIMD will be compiled
The core concept of the main data containers of this library are Label and
Value. A Label is the result of the multiplication of an (error-) vector,
called Value with a Matrix. Or mathematical speaking: Label = Matrix*Value.
If you are familiar with ISD algorithms or the decoding of codewords, this looks
a lot like the syndrome equation s = H*e, where s is the sybdrome, e a
(probably) unknown error and H the parity check matrix of your code.
This design is chosen for the case in which the error vector e (which is
saved in a Value) is unknown. Hence one wants to iterate a lot of Values which
matches the correct Label you can order them in a List. As a matter
of fact, this libraries offers of lot of different implementations.
Internally a set of a Value, Label and Matrix is called an Element, which
maps each Value via a Matrix to an unique Value. More on each of those
containers you find here: Label, Value, Matrix,
Element.
The following things are implemented:
- Custom allocators which do not return a memory allocation, but memory blocks which do not allow for memory missuses.
- Binary- and Fq-Enumeration which enumerate vectors of length
nand weightwin a loop-less efficient way. Either a Chase-Sequence or a Gray-Code or a combination of both. - LinkedList
- HashMaps
- Permutation
- Search
- SIMD
A lot of different data containers are implemented:
BinaryContainer<T, len>is able to holdlenbits inlen/(sizeof(T)*8)limbs of typeT. Additionally, all importantadd,sub,comparefunctions are implementedkAryType<T, T2, q>represents a valuemod q. The second typeT2is needed to sanely implement the multiplication.kAryContainer<T, len>holdslenelementsmod qand each element is saved in its own limb of typeT.kAryPackedContainer<T, len>same askAryContainer<T, len>but the implementations stores as much as possible elementsmod qin one limb of typeT.
These datatypes can be used to instantiate a Label and Value
(which form together an Element<Value_T, Label_T, Matrix>), where
Label = H \times Value for any Matrix H of any type (binary, ternary,
kAry, ...).
Note: only for certain primes and prime-powers are speciallized arithmetics
implemented. If you chose an unsupported one, a slow generic backup
implementation will be used. If so you will be warned.
As well as this core datatypes the following list-containers are implemented:
Parallel_ListA list which separatesValuefromLabelin two different lists to allow faster enumeration of one of types while one does not care about the other. Additionally, each of the two lists is split into chucks on which threads can operate independent of each other. Note: sorting is currently not possible in this list.Parallel_List_FullElementSame asParallel_List, butValuesandLabelsare together saved in one list ofElements, which allows sorting.Parallel_List_IndexElementTODOListgeneric list implementation. Range checks are performed in every implementation.
All matrices are represented with the matrix class
The following sorting algorithms are available. -ska_sort -timsort
Currently ska_sort (Link)[https://github.com/skarupke/ska_sort] is used as
the main sorting algorithm. Note that sorting is avoided in the code as much
as possible. Do not sort if you want fast code.
Can be found here
explain:
- List generators,
- triple
- mccd mem tracker
- mccl: hashmap neu streiben ohne load factor, indem die hash funk ein rotate einbaut
- matrix: more tests via constexpr loops
- binary_matrix aufräumen
- Die sorting algorithmen in
list, davon die hashfunktionen zusammenfassen und die #ifdefs weg. Wahrscheinlichparallel.hweg? verstehe nicht so ganz was die implementierung soll, wenn ist ListT gibt.
React
Typescript
Django
Laravel
Facebook
Microsoft
Google
Alibaba
D3
Tencent