For fun and also to provide feedback during the draft phase, I created a C11 implementation of the FIPS 203 initial public draft (IPD).
FIPS 203 is a slightly modified version of Kyber, and will (eventually) become NIST’s standarized post-quantum key encapsulation mechanism (KEM).
Features
- Full implementation of all three parameter sets from the FIPS 203 initial public draft.
- C11, no external dependencies (other than the standard library).
- Test suite w/ common sanitizers enabled (
make test). - Doxygen-friendly API documentation (
fips203ipd.h). Also available online here. - short example application (
examples/0-hello-kem/).
Note: This is an initial release based on the draft standard with no real optimization; it is slow and memory-intensive.
Another Note: Worth reading before relying on any Kyber implementation: 2020.10.03: The inability to count correctly, by Dan Bernstein (djb).
Example
Below is the source code and output of a minimal C11 example application which demonstrates the following:
- Alice generates a random KEM512 encapsulation/decapsulation key pair.
- Alice sends the encapsulation key to Bob.
- Bob uses the encapsulation key sent by Alice to encapsulate a random shared secret as ciphertext.
- Bob sends the ciphertext to Alice.
- Alice uses the decapsulation key to decapsulate the shared secret from the ciphertext sent by Bob.
- Application verifies that the shared secrets from steps #3 and #5 match.
This example is also included in the git repository as
examples/0-hello-kem/.
Example Source Code
//
// hello.c: minimal example of a two parties "alice" and "bob"
// generating a shared secret with KEM512.
//
// Build by typing `make` and run by typing `./hello`.
//
#include <stdio.h> // fputs()
#include <string.h> // memcmp()
#include "hex.h" // hex_write()
#include "rand-bytes.h" // rand_bytes()
#include "fips203ipd.h" // fips203ipd_*()
int main(void) {
//
// alice: generate keypair
//
uint8_t ek[FIPS203IPD_KEM512_EK_SIZE] = { 0 }; // encapsulation key
uint8_t dk[FIPS203IPD_KEM512_DK_SIZE] = { 0 }; // decapsulation key
{
// alice: get 64 random bytes for keygen()
uint8_t keygen_seed[64] = { 0 };
rand_bytes(keygen_seed, sizeof(keygen_seed));
fputs("alice: keygen random (64 bytes) = ", stdout);
hex_write(stdout, keygen_seed, sizeof(keygen_seed));
fputs("\n", stdout);
// alice: generate encapsulation/decapsulation key pair
fips203ipd_kem512_keygen(ek, dk, keygen_seed);
}
fputs("alice: generated encapsulation key `ek` and decapsulation key `dk`:\n", stdout);
printf("alice: ek (%d bytes) = ", FIPS203IPD_KEM512_EK_SIZE);
hex_write(stdout, ek, sizeof(ek));
printf("\nalice: dk (%d bytes) = ", FIPS203IPD_KEM512_DK_SIZE);
hex_write(stdout, dk, sizeof(dk));
fputs("\n", stdout);
// alice send `ek` to bob
fputs("alice: sending encapsulation key `ek` to bob\n\n", stdout);
//
// bob: generate shared secret and ciphertext
//
uint8_t b_key[32] = { 0 }; // shared secret
uint8_t ct[FIPS203IPD_KEM512_CT_SIZE] = { 0 }; // ciphertext
{
// bob: get 32 random bytes for encaps()
uint8_t encaps_seed[32] = { 0 };
rand_bytes(encaps_seed, sizeof(encaps_seed));
fputs("bob: encaps random (32 bytes) = ", stdout);
hex_write(stdout, encaps_seed, sizeof(encaps_seed));
fputs("\n", stdout);
// bob:
// 1. get encapsulation key `ek` from alice.
// 2. generate random shared secret.
// 3. use `ek` from step #1 to encapsulate the shared secret from step #2.
// 3. store the shared secret in `b_key`.
// 4. store the encapsulated shared secret (ciphertext) in `ct`.
fips203ipd_kem512_encaps(b_key, ct, ek, encaps_seed);
}
fputs("bob: generated secret `b_key` and ciphertext `ct`:\nbob: b_key (32 bytes) = ", stdout);
hex_write(stdout, b_key, sizeof(b_key));
printf("\nbob: ct (%d bytes) = ", FIPS203IPD_KEM512_CT_SIZE);
hex_write(stdout, ct, sizeof(ct));
fputs("\n", stdout);
// bob sends ciphertext `ct` to alice
fputs("bob: sending ciphertext `ct` to alice\n\n", stdout);
//
// alice: decapsulate shared secret
//
// alice:
// 1. get ciphertext `ct` from bob.
// 2. use decapsultion key `dk` to decapsulate shared secret from `ct`.
// 2. store shared secret in `a_key`.
uint8_t a_key[32] = { 0 };
fips203ipd_kem512_decaps(a_key, ct, dk);
fputs("alice: used `dk` to decapsulate secret from `ct` into `a_key`:\nalice: a_key (32 bytes) = ", stdout);
hex_write(stdout, a_key, sizeof(a_key));
fputs("\n\n", stdout);
// check result
if (!memcmp(a_key, b_key, sizeof(a_key))) {
// success: alice and bob have the same shared secret
fputs("SUCCESS! alice secret `a_key` and bob secret `b_key` match.\n", stdout);
return 0;
} else {
// failure: alice and bob do not have the same shared secret
fputs("FAILURE! alice secret `a_key` and bob secret `b_key` do not match.\n", stdout);
return -1;
}
}
Example Output
Output of ./hello with longer lines truncated for brevity:
> ./hello
alice: keygen random (64 bytes) = d656012a9eb09aa50e77a205188f0156e98276a584dcc11c2dfef0c06003ca38b233fab93e9f8dd5adec32278c8d091190112285b7389510bd610ec7b23376b2
alice: generated encapsulation key `ek` and decapsulation key `dk`:
alice: ek (800 bytes) = af3b0497f6 ... (omitted) ... 31f0f62cbd
alice: dk (1632 bytes) = e598a49eb0 ... (omitted) ... c06003ca38
alice: sending encapsulation key `ek` to bob
bob: encaps random (32 bytes) = 0db6c39742ba8cb8d9a1c437d62fed4c7fa04e944a47a73a94426dd3c33e6213
bob: generated secret `b_key` and ciphertext `ct`:
bob: b_key (32 bytes) = 32c9eb490db7e8500d9b209d78a9367fd73a967d8d58edff8655273c8d4ce8d5
bob: ct (768 bytes) = bd39ae1157 ... (omitted) ... 9b5751fc34
bob: sending ciphertext `ct` to alice
alice: used `dk` to decapsulate secret from `ct` into `a_key`:
alice: a_key (32 bytes) = 32c9eb490db7e8500d9b209d78a9367fd73a967d8d58edff8655273c8d4ce8d5
SUCCESS! alice secret `a_key` and bob secret `b_key` match.
Update (2023-10-10): Fixed typos, added rationale to intro, and added a brief explanation to the example section.
Update (2023-10-19): Released v0.2 with documentation improvements, speed improvements, a new example, and online API documentation.
