# RAMSTAKE
This code package contains implementations in C and Sage of Ramstake, which is a proposal for KEM submitted to the NIST post-quantum standardization project. Ramstake relies on sparse integer algebra along the lines of the Aggarwal et al. Mersenne prime cryptosystem; it achieves the KEM functionality via an implicit noisy key agreement protocol whose shared noisy key is then used as a one-time pad to securely transmit the seed from which the ciphertext was generated -- and from which the symmetric key is derived.
There are three parameter sets:
* Ramstake RS 216091 -- targets 128 bit security against classical computers.
* Ramstake RS 756839 -- targets 256 bit security against classical computers.
To save space, the following file descriptions are parameterized by the parameter set [paramset]. Their function is identical across parameter sets.
## Read Me
|-- ./README -- this file
# Written Specification
`-- ./Supporting_Documentation/ramstake.pdf -- design doc / spec file
## KAT Files
| |-- ./KAT/[paramset]/PQCkemKAT_[number].int -- intermediate KAT values, generated while PQCgenKAT_kem was running (and renamed to have matching number)
| |-- ./KAT/[paramset]/PQCkemKAT_[number].req -- generated by PQCgenKAT_kem
| `-- ./KAT/[paramset]/PQCkemKAT_[number].rsp -- generated by PQCgenKAT_kem
## Sage Implementation
| |-- ./Additional_Implementations/sage/[paramset]/CompactFIPS202.py -- keccak functions for sage implementation
| |-- ./Additional_Implementations/sage/[paramset]/csprng.py -- csprng identical to the C csprng; used for testing purposes only
| |-- ./Additional_Implementations/sage/[paramset]/ramstake.sage -- Ramstake functions
| |-- ./Additional_Implementations/sage/[paramset]/reedsolomon.sage -- Reed-Solomon decoder
| |-- ./Additional_Implementations/sage/[paramset]/codec_rs.sage -- interface between ramstake functions and Reed-Solomon codec
| `-- ./Additional_Implementations/sage/[paramset]/test.sage -- test procedure with identical output to test.c
Usage:
$> sage test.sage 1 deadbeef
Where 1 is the number of trials, and deadbeef is the hex encoding of the randomness seed. When the number of trials is 1, KATs will be generated. The operation of this test procedure is identical to that of the C implementations.
## Reference Implementation
| |-- ./Reference_Implementation/[paramset]/genapi.c -- generates api.h (to avoid computing the public key size etc by hand)
| |-- ./Reference_Implementation/[paramset]/api.h -- bindings for automatic benchmarking
| |-- ./Reference_Implementation/[paramset]/csprng.c -- implementation of the csprng interface using Keccak
| |-- ./Reference_Implementation/[paramset]/csprng.h -- csprng interface; this csprng is used only for testing purposes
| |-- ./Reference_Implementation/[paramset]/gf256x.c -- GF(256) arithmetic
| |-- ./Reference_Implementation/[paramset]/gf256x.h -- GF(256) arithmetic (used by RS codec)
| |-- ./Reference_Implementation/[paramset]/kem.c -- implementation of the interface of api.h using ramstake functions
| |-- ./Reference_Implementation/[paramset]/Makefile -- makefile to generate test or PQCgenKAT_kem or perform
| |-- ./Reference_Implementation/[paramset]/PQCgenKAT_kem.c -- generate KATs
| |-- ./Reference_Implementation/[paramset]/ramstake.c -- implementation of ramstake functions
| |-- ./Reference_Implementation/[paramset]/ramstake.h -- header file for ramstake functions
| |-- ./Reference_Implementation/[paramset]/reedsolomon.c -- Reed-Solomon encoding and decoding, implementation
| |-- ./Reference_Implementation/[paramset]/reedsolomon.h -- Reed-Solomon encoding and decoding, interface
| |-- ./Reference_Implementation/[paramset]/codec_rs.h -- interface between ramstake functions and Reed-Solomon codec
| |-- ./Reference_Implementation/[paramset]/codec_rs.c -- functions of the interface between ramstake functions and Reed-Solomon codec
| |-- ./Reference_Implementation/[paramset]/rng.c -- provided by NIST for KATs
| |-- ./Reference_Implementation/[paramset]/rng.h -- provided by NIST for KATs
| |-- ./Reference_Implementation/[paramset]/perform.c -- performance test
| `-- ./Reference_Implementation/[paramset]/test.c -- test procedure
Make sure the Makefile references the correct directory for the Keccak Code Package. Then:
* $> make api
generates the api.h file. By default api.h matches the collocated ramstake.h parameters, but this miniscript generates api.h after modifying ramstake.h.
* $> make test
compiles the test procedure; run as
$> ./test 1 deadbeef
where 1 is the number of trials and deadbeef is the hex encoding of the random seed. If the number of trials is one, KATs will be generated. This test procedure produces output identical to test.sage.
* $> make kat
compiles NIST's KAT generation program. Intermediate KATs will be sent to stdout. Run as
$> ./PQCgenKAT_kem > KAT.int
* $> make perform
generates a performance test, which collects timings and cycle counts for a user-defined number of trials. Run as
$> ./perform 10000 deadbeef
## Optimized Implementation
| |-- ./Optimized_Implementation/[paramset]/genapi.c -- generates api.h (to avoid computing the public key size etc by hand)
| |-- ./Optimized_Implementation/[paramset]/api.h -- bindings for automatic benchmarking
| |-- ./Optimized_Implementation/[paramset]/csprng.c -- implementation of the csprng interface using Keccak
| |-- ./Optimized_Implementation/[paramset]/csprng.h -- csprng interface; this csprng is used only for testing purposes
| |-- ./Optimized_Implementation/[paramset]/gf256x.c -- GF(256) arithmetic
| |-- ./Optimized_Implementation/[paramset]/gf256x.h -- GF(256) arithmetic (used by RS codec)
| |-- ./Optimized_Implementation/[paramset]/kem.c -- implementation of the inteface of api.h using ramstake functions
| |-- ./Optimized_Implementation/[paramset]/Makefile -- makefile to generate optimized test or PQCgenKAT_kem or perform
| |-- ./Optimized_Implementation/[paramset]/PQCgenKAT_kem.c -- generate KATs
| |-- ./Optimized_Implementation/[paramset]/ramstake.c -- implementation of ramstake functions
| |-- ./Optimized_Implementation/[paramset]/ramstake.h -- header file for ramstake functions
| |-- ./Optimized_Implementation/[paramset]/reedsolomon.c -- Reed-Solomon encoding and decoding, implementation
| |-- ./Optimized_Implementation/[paramset]/reedsolomon.h -- Reed-Solomon encoding and decoding, interface
| |-- ./Optimized_Implementation/[paramset]/codec_rs.h -- interface between ramstake functions and Reed-Solomon codec
| |-- ./Optimized_Implementation/[paramset]/codec_rs.c -- functions of the interface between ramstake functions and Reed-Solomon codec
| |-- ./Optimized_Implementation/[paramset]/rng.c -- provided by NIST for KATs
| |-- ./Optimized_Implementation/[paramset]/rng.h -- provided by NIST for KATs
| |-- ./Optimized_Implementation/[paramset]/perform.c -- performance test
| `-- ./Optimized_Implementation/[paramset]/test.c -- test procedure
Make sure the Makefile references the correct directory for the Keccak Code Package. Then:
* $> make api
generates the api.h file. By default api.h matches the collocated ramstake.h parameters, but this miniscript generates api.h after modifying ramstake.h.
* $> make test
compiles the test procedure; run as
$> ./test 1 deadbeef
where 1 is the number of trials and deadbeef is the hex encoding of the random seed. If the number of trials is one, KATs will be generated. This test procedure produces output identical to test.sage.
* $> make kat
compiles NIST's KAT generation program. Intermediate KATs will be sent to stdout. Run as
$> ./PQCgenKAT_kem > KAT.int
* $> make perform
generates a performance test, which collects timings and cycle counts for a user-defined number of trials. Run as
$> ./perform 10000 deadbeef