1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
|
---
slug: C11 Implementation of FIPS 203 IPD
title: "C11 FIPS 203"
date: "2023-10-07T12:19:48-04:00"
---
I created a [C11][] implementation of the KEM512, KEM768, and KEM1024
parameter sets from the [FIPS 203 initial public draft
(IPD)][fips203ipd].
[FIPS 203][fips203ipd] is (or will be) [NIST's][nist] standardized
version of [Kyber][], a post-quantum [key encapsulation mechanism
(KEM)][kem].
### Features
* Full implementation of all three parameter sets from the [FIPS 203
initial public draft][fips203ipd]
* [C11][], no external dependencies
* Test suite w/ common sanitizers enabled (`make test`)
* API documentation (`fips203ipd.h`)
* short example application (`examples/0-hello-kem/`).
[Git Repository][github]
**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][djb-kyber], by [Dan Bernstein (djb)][djb].
## Example
This example application is also included in the [git
repository][github] as `examples/0-hello-kem/`.
### Source
```c
//
// 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;
}
}
```
### Output
Output of `./hello` with longer lines truncated for brevity:
```sh
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.
```
###
[c11]: https://en.wikipedia.org/wiki/C11_(C_standard_revision)
"ISO/IEC 9899:2011"
[SHA-3]: https://en.wikipedia.org/wiki/SHA-3
"Secure Hash Algorithm 3"
[sha3-mine]: https://github.com/pablotron/sha3
"My FIPS 202 (SHA-3) implementation."
[fips203ipd]: https://csrc.nist.gov/pubs/fips/203/ipd
"FIPS 203 (Initial Public Draft): Module-Lattice-Based Key-Encapsulation Mechanism Standard"
[fips202]: https://csrc.nist.gov/pubs/fips/202/final
"SHA-3 Standard: Permutation-Based Hash and Extendable-Output Functions"
[pqc-forum-decode-comment]: https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/ZRQvPT7kQ51NIRyJ%40disp3269
"pqc-forum mailing list discussion about reducing coefficients modulo Q during deserialization."
[nist]: https://nist.gov/
"National Institute of Standards and Technology"
[kyber]: https://pq-crystals.org/kyber/
"Kyber: post-quantum key encapsulation mechanism based on the hardness of the module learning with errors (m-LWE) problem."
[kem]: https://en.wikipedia.org/wiki/Key_encapsulation_mechanism
"Key encapsulation mechanism."
[gcc]: https://en.wikipedia.org/wiki/GNU_Compiler_Collection
"GNU Compiler Collection."
[clang]: https://en.wikipedia.org/wiki/Clang
"LLVM compiler front end."
[github]: https://github.com/pablotron/fips203ipd
"fips203ipd github repository."
[djb-kyber]: https://blog.cr.yp.to/20231003-countcorrectly.html
"2023.10.03: The inability to count correctly, by Dan Bernstein."
[djb]: https://en.wikipedia.org/wiki/Daniel_J._Bernstein
"Daniel J. Bernstein"
|
