/src/botan/src/lib/pubkey/kyber/kyber_common/kyber.cpp
Line | Count | Source (jump to first uncovered line) |
1 | | /* |
2 | | * Crystals Kyber key encapsulation mechanism |
3 | | * Based on the public domain reference implementation by the |
4 | | * designers (https://github.com/pq-crystals/kyber) |
5 | | * |
6 | | * Further changes |
7 | | * (C) 2021-2022 Jack Lloyd |
8 | | * (C) 2021-2022 Manuel Glaser and Michael Boric, Rohde & Schwarz Cybersecurity |
9 | | * (C) 2021-2022 René Meusel and Hannes Rantzsch, neXenio GmbH |
10 | | * |
11 | | * Botan is released under the Simplified BSD License (see license.txt) |
12 | | */ |
13 | | |
14 | | #include <botan/kyber.h> |
15 | | |
16 | | #include <botan/assert.h> |
17 | | #include <botan/ber_dec.h> |
18 | | #include <botan/hash.h> |
19 | | #include <botan/mem_ops.h> |
20 | | #include <botan/pubkey.h> |
21 | | #include <botan/rng.h> |
22 | | #include <botan/secmem.h> |
23 | | #include <botan/stream_cipher.h> |
24 | | |
25 | | #include <botan/internal/pk_ops_impl.h> |
26 | | #include <botan/internal/kyber_symmetric_primitives.h> |
27 | | #include <botan/internal/loadstor.h> |
28 | | #include <botan/internal/ct_utils.h> |
29 | | #include <botan/internal/stl_util.h> |
30 | | |
31 | | #if defined(BOTAN_HAS_KYBER) |
32 | | #include <botan/internal/kyber_modern.h> |
33 | | #endif |
34 | | |
35 | | #if defined(BOTAN_HAS_KYBER_90S) |
36 | | #include <botan/internal/kyber_90s.h> |
37 | | #endif |
38 | | |
39 | | #include <algorithm> |
40 | | #include <array> |
41 | | #include <iterator> |
42 | | #include <memory> |
43 | | #include <optional> |
44 | | #include <vector> |
45 | | #include <limits> |
46 | | |
47 | | namespace Botan { |
48 | | |
49 | | namespace { |
50 | | |
51 | | KyberMode::Mode kyber_mode_from_string(const std::string& str) |
52 | 0 | { |
53 | 0 | if(str == "Kyber-512-90s-r3") |
54 | 0 | return KyberMode::Kyber512_90s; |
55 | 0 | if(str == "Kyber-768-90s-r3") |
56 | 0 | return KyberMode::Kyber768_90s; |
57 | 0 | if(str == "Kyber-1024-90s-r3") |
58 | 0 | return KyberMode::Kyber1024_90s; |
59 | 0 | if(str == "Kyber-512-r3") |
60 | 0 | return KyberMode::Kyber512; |
61 | 0 | if(str == "Kyber-768-r3") |
62 | 0 | return KyberMode::Kyber768; |
63 | 0 | if(str == "Kyber-1024-r3") |
64 | 0 | return KyberMode::Kyber1024; |
65 | | |
66 | 0 | throw Invalid_Argument(str + " is not a valid Kyber mode name"); |
67 | 0 | } |
68 | | |
69 | | } |
70 | | |
71 | | KyberMode::KyberMode(Mode mode) |
72 | 0 | : m_mode(mode) {} |
73 | | |
74 | | KyberMode::KyberMode(const OID& oid) |
75 | 0 | : m_mode(kyber_mode_from_string(oid.to_formatted_string())) {} |
76 | | |
77 | | KyberMode::KyberMode(const std::string& str) |
78 | 0 | : m_mode(kyber_mode_from_string(str)) {} |
79 | | |
80 | | OID KyberMode::object_identifier() const |
81 | 0 | { |
82 | 0 | return OID::from_string(to_string()); |
83 | 0 | } |
84 | | |
85 | | std::string KyberMode::to_string() const |
86 | 0 | { |
87 | 0 | switch (m_mode) |
88 | 0 | { |
89 | 0 | case Kyber512_90s: |
90 | 0 | return "Kyber-512-90s-r3"; |
91 | 0 | case Kyber768_90s: |
92 | 0 | return "Kyber-768-90s-r3"; |
93 | 0 | case Kyber1024_90s: |
94 | 0 | return "Kyber-1024-90s-r3"; |
95 | 0 | case Kyber512: |
96 | 0 | return "Kyber-512-r3"; |
97 | 0 | case Kyber768: |
98 | 0 | return "Kyber-768-r3"; |
99 | 0 | case Kyber1024: |
100 | 0 | return "Kyber-1024-r3"; |
101 | 0 | } |
102 | | |
103 | 0 | unreachable(); |
104 | 0 | } |
105 | | |
106 | | namespace { |
107 | | |
108 | | class KyberConstants |
109 | | { |
110 | | public: |
111 | | static constexpr size_t N = 256; |
112 | | static constexpr size_t Q = 3329; |
113 | | static constexpr size_t Q_Inv = 62209; |
114 | | |
115 | | static constexpr int16_t zetas[128] = |
116 | | { |
117 | | 2285, 2571, 2970, 1812, 1493, 1422, 287, 202, 3158, 622, 1577, 182, 962, 2127, 1855, 1468, |
118 | | 573, 2004, 264, 383, 2500, 1458, 1727, 3199, 2648, 1017, 732, 608, 1787, 411, 3124, 1758, |
119 | | 1223, 652, 2777, 1015, 2036, 1491, 3047, 1785, 516, 3321, 3009, 2663, 1711, 2167, 126, 1469, |
120 | | 2476, 3239, 3058, 830, 107, 1908, 3082, 2378, 2931, 961, 1821, 2604, 448, 2264, 677, 2054, |
121 | | 2226, 430, 555, 843, 2078, 871, 1550, 105, 422, 587, 177, 3094, 3038, 2869, 1574, 1653, |
122 | | 3083, 778, 1159, 3182, 2552, 1483, 2727, 1119, 1739, 644, 2457, 349, 418, 329, 3173, 3254, |
123 | | 817, 1097, 603, 610, 1322, 2044, 1864, 384, 2114, 3193, 1218, 1994, 2455, 220, 2142, 1670, |
124 | | 2144, 1799, 2051, 794, 1819, 2475, 2459, 478, 3221, 3021, 996, 991, 958, 1869, 1522, 1628 |
125 | | }; |
126 | | |
127 | | static constexpr int16_t zetas_inv[128] = |
128 | | { |
129 | | 1701, 1807, 1460, 2371, 2338, 2333, 308, 108, 2851, 870, 854, 1510, 2535, 1278, 1530, 1185, |
130 | | 1659, 1187, 3109, 874, 1335, 2111, 136, 1215, 2945, 1465, 1285, 2007, 2719, 2726, 2232, 2512, |
131 | | 75, 156, 3000, 2911, 2980, 872, 2685, 1590, 2210, 602, 1846, 777, 147, 2170, 2551, 246, |
132 | | 1676, 1755, 460, 291, 235, 3152, 2742, 2907, 3224, 1779, 2458, 1251, 2486, 2774, 2899, 1103, |
133 | | 1275, 2652, 1065, 2881, 725, 1508, 2368, 398, 951, 247, 1421, 3222, 2499, 271, 90, 853, |
134 | | 1860, 3203, 1162, 1618, 666, 320, 8, 2813, 1544, 282, 1838, 1293, 2314, 552, 2677, 2106, |
135 | | 1571, 205, 2918, 1542, 2721, 2597, 2312, 681, 130, 1602, 1871, 829, 2946, 3065, 1325, 2756, |
136 | | 1861, 1474, 1202, 2367, 3147, 1752, 2707, 171, 3127, 3042, 1907, 1836, 1517, 359, 758, 1441 |
137 | | }; |
138 | | |
139 | | static constexpr size_t kSymBytes = 32; |
140 | | static constexpr size_t kSeedLength = kSymBytes; |
141 | | static constexpr size_t kSerializedPolynomialByteLength = N / 2 * 3; |
142 | | static constexpr size_t kPublicKeyHashLength = 32; |
143 | | static constexpr size_t kZLength = kSymBytes; |
144 | | |
145 | | public: |
146 | | KyberConstants(const KyberMode mode) : m_mode(mode) |
147 | 0 | { |
148 | 0 | switch(mode.mode()) |
149 | 0 | { |
150 | 0 | case KyberMode::Kyber512: |
151 | 0 | case KyberMode::Kyber512_90s: |
152 | 0 | m_nist_strength = 128; |
153 | 0 | m_k = 2; |
154 | 0 | m_eta1 = 3; |
155 | 0 | break; |
156 | | |
157 | 0 | case KyberMode::Kyber768: |
158 | 0 | case KyberMode::Kyber768_90s: |
159 | 0 | m_nist_strength = 192; |
160 | 0 | m_k = 3; |
161 | 0 | m_eta1 = 2; |
162 | 0 | break; |
163 | | |
164 | 0 | case KyberMode::Kyber1024: |
165 | 0 | case KyberMode::Kyber1024_90s: |
166 | 0 | m_nist_strength = 256; |
167 | 0 | m_k = 4; |
168 | 0 | m_eta1 = 2; |
169 | 0 | break; |
170 | 0 | } |
171 | | |
172 | 0 | #ifdef BOTAN_HAS_KYBER_90S |
173 | 0 | if(mode.is_90s()) |
174 | 0 | { |
175 | 0 | m_symmetric_primitives = std::make_unique<Kyber_90s_Symmetric_Primitives>(); |
176 | 0 | } |
177 | 0 | #endif |
178 | 0 | #ifdef BOTAN_HAS_KYBER |
179 | 0 | if(!mode.is_90s()) |
180 | 0 | { |
181 | 0 | m_symmetric_primitives = std::make_unique<Kyber_Modern_Symmetric_Primitives>(); |
182 | 0 | } |
183 | 0 | #endif |
184 | |
|
185 | 0 | if(!m_symmetric_primitives) |
186 | 0 | { |
187 | 0 | throw Not_Implemented("requested Kyber mode is not enabled in this build"); |
188 | 0 | } |
189 | 0 | } |
190 | | |
191 | 0 | ~KyberConstants() = default; |
192 | | |
193 | | KyberConstants(const KyberConstants& other) : KyberConstants(other.m_mode) |
194 | 0 | { |
195 | 0 | } |
196 | | |
197 | 0 | KyberConstants(KyberConstants&& other) = default; |
198 | | KyberConstants& operator=(const KyberConstants& other) = delete; |
199 | | KyberConstants& operator=(KyberConstants&& other) = default; |
200 | | |
201 | | KyberMode mode() const |
202 | 0 | { |
203 | 0 | return m_mode; |
204 | 0 | } |
205 | | |
206 | | size_t estimated_strength() const |
207 | 0 | { |
208 | 0 | return m_nist_strength; |
209 | 0 | } |
210 | | |
211 | | uint8_t k() const |
212 | 0 | { |
213 | 0 | return m_k; |
214 | 0 | } |
215 | | |
216 | | uint8_t eta1() const |
217 | 0 | { |
218 | 0 | return m_eta1; |
219 | 0 | } |
220 | | |
221 | | uint8_t eta2() const |
222 | 0 | { |
223 | 0 | return 2; |
224 | 0 | } |
225 | | |
226 | | size_t polynomial_vector_byte_length() const |
227 | 0 | { |
228 | 0 | return kSerializedPolynomialByteLength * k(); |
229 | 0 | } |
230 | | |
231 | | size_t public_key_byte_length() const |
232 | 0 | { |
233 | 0 | return polynomial_vector_byte_length() + kSeedLength; |
234 | 0 | } |
235 | | |
236 | | size_t private_key_byte_length() const |
237 | 0 | { |
238 | 0 | return polynomial_vector_byte_length() + public_key_byte_length() + kPublicKeyHashLength + kZLength; |
239 | 0 | } |
240 | | |
241 | | std::unique_ptr<HashFunction> G() const |
242 | 0 | { |
243 | 0 | return m_symmetric_primitives->G(); |
244 | 0 | } |
245 | | std::unique_ptr<HashFunction> H() const |
246 | 0 | { |
247 | 0 | return m_symmetric_primitives->H(); |
248 | 0 | } |
249 | | std::unique_ptr<HashFunction> KDF() const |
250 | 0 | { |
251 | 0 | return m_symmetric_primitives->KDF(); |
252 | 0 | } |
253 | | std::unique_ptr<StreamCipher> XOF(const std::vector<uint8_t>& seed, |
254 | | const std::tuple<uint8_t, uint8_t>& matrix_position) const |
255 | 0 | { |
256 | 0 | return m_symmetric_primitives->XOF(seed, matrix_position); |
257 | 0 | } |
258 | | |
259 | | secure_vector<uint8_t> PRF(const secure_vector<uint8_t>& seed, const uint8_t nonce, const size_t outlen) const |
260 | 0 | { |
261 | 0 | return m_symmetric_primitives->PRF(seed, nonce, outlen); |
262 | 0 | } |
263 | | |
264 | | private: |
265 | | KyberMode m_mode; |
266 | | std::unique_ptr<Kyber_Symmetric_Primitives> m_symmetric_primitives; |
267 | | size_t m_nist_strength; |
268 | | uint8_t m_k; |
269 | | uint8_t m_eta1; |
270 | | }; |
271 | | |
272 | | // declarations required pre-C++17 (at least with GCC) |
273 | | constexpr int16_t KyberConstants::zetas[128]; |
274 | | constexpr int16_t KyberConstants::zetas_inv[128]; |
275 | | |
276 | | class Polynomial |
277 | | { |
278 | | public: |
279 | | std::array<int16_t, KyberConstants::N> m_coeffs; |
280 | | |
281 | | /** |
282 | | * Applies conditional subtraction of q to each coefficient of the polynomial. |
283 | | */ |
284 | | void csubq() |
285 | 0 | { |
286 | 0 | for(auto& coeff : m_coeffs) |
287 | 0 | { |
288 | 0 | coeff -= KyberConstants::Q; |
289 | 0 | coeff += (coeff >> 15) & KyberConstants::Q; |
290 | 0 | } |
291 | 0 | } |
292 | | |
293 | | /** |
294 | | * Applies Barrett reduction to all coefficients of the polynomial |
295 | | */ |
296 | | void reduce() |
297 | 0 | { |
298 | 0 | for(auto& c : m_coeffs) |
299 | 0 | { c = barrett_reduce(c); } |
300 | 0 | } |
301 | | |
302 | | template <typename T = std::vector<uint8_t>> T to_bytes() |
303 | 0 | { |
304 | 0 | this->csubq(); |
305 | |
|
306 | 0 | T r(KyberConstants::kSerializedPolynomialByteLength); |
307 | |
|
308 | 0 | for(size_t i = 0; i < m_coeffs.size() / 2; ++i) |
309 | 0 | { |
310 | 0 | const uint16_t t0 = m_coeffs[2 * i]; |
311 | 0 | const uint16_t t1 = m_coeffs[2 * i + 1]; |
312 | 0 | r[3 * i + 0] = static_cast<uint8_t>(t0 >> 0); |
313 | 0 | r[3 * i + 1] = static_cast<uint8_t>((t0 >> 8) | (t1 << 4)); |
314 | 0 | r[3 * i + 2] = static_cast<uint8_t>(t1 >> 4); |
315 | 0 | } |
316 | |
|
317 | 0 | return r; |
318 | 0 | } Unexecuted instantiation: kyber.cpp:std::__1::vector<unsigned char, std::__1::allocator<unsigned char> > Botan::(anonymous namespace)::Polynomial::to_bytes<std::__1::vector<unsigned char, std::__1::allocator<unsigned char> > >() Unexecuted instantiation: kyber.cpp:std::__1::vector<unsigned char, Botan::secure_allocator<unsigned char> > Botan::(anonymous namespace)::Polynomial::to_bytes<std::__1::vector<unsigned char, Botan::secure_allocator<unsigned char> > >() |
319 | | |
320 | | /** |
321 | | * Given an array of uniformly random bytes, compute polynomial with coefficients |
322 | | * distributed according to a centered binomial distribution with parameter eta=2 |
323 | | */ |
324 | | static Polynomial cbd2(const secure_vector<uint8_t>& buf) |
325 | 0 | { |
326 | 0 | Polynomial r; |
327 | |
|
328 | 0 | BOTAN_ASSERT(buf.size() == (2 * r.m_coeffs.size() / 4), "wrong input buffer size for cbd2"); |
329 | |
|
330 | 0 | for(size_t i = 0; i < r.m_coeffs.size() / 8; ++i) |
331 | 0 | { |
332 | 0 | uint32_t t = load_le<uint32_t>(buf.data(), i); |
333 | 0 | uint32_t d = t & 0x55555555; |
334 | 0 | d += (t >> 1) & 0x55555555; |
335 | |
|
336 | 0 | for(size_t j = 0; j < 8; ++j) |
337 | 0 | { |
338 | 0 | int16_t a = (d >> (4 * j + 0)) & 0x3; |
339 | 0 | int16_t b = (d >> (4 * j + 2)) & 0x3; |
340 | 0 | r.m_coeffs[8 * i + j] = a - b; |
341 | 0 | } |
342 | 0 | } |
343 | |
|
344 | 0 | return r; |
345 | 0 | } |
346 | | |
347 | | /** |
348 | | * Given an array of uniformly random bytes, compute polynomial with coefficients |
349 | | * distributed according to a centered binomial distribution with parameter eta=3 |
350 | | * |
351 | | * This function is only needed for Kyber-512 |
352 | | */ |
353 | | static Polynomial cbd3(const secure_vector<uint8_t>& buf) |
354 | 0 | { |
355 | 0 | Polynomial r; |
356 | |
|
357 | 0 | BOTAN_ASSERT(buf.size() == (3 * r.m_coeffs.size() / 4), "wrong input buffer size for cbd3"); |
358 | | |
359 | | // Note: load_le<> does not support loading a 3-byte value |
360 | 0 | const auto load_le24 = [](const uint8_t in[], const size_t off) |
361 | 0 | { |
362 | 0 | const auto off3 = off * 3; |
363 | 0 | return make_uint32(0, in[off3 + 2], in[off3 + 1], in[off3]); |
364 | 0 | }; |
365 | |
|
366 | 0 | for(size_t i = 0; i < r.m_coeffs.size() / 4; ++i) |
367 | 0 | { |
368 | 0 | uint32_t t = load_le24(buf.data(), i); |
369 | 0 | uint32_t d = t & 0x00249249; |
370 | 0 | d += (t >> 1) & 0x00249249; |
371 | 0 | d += (t >> 2) & 0x00249249; |
372 | |
|
373 | 0 | for(size_t j = 0; j < 4; ++j) |
374 | 0 | { |
375 | 0 | int16_t a = (d >> (6 * j + 0)) & 0x7; |
376 | 0 | int16_t b = (d >> (6 * j + 3)) & 0x7; |
377 | 0 | r.m_coeffs[4 * i + j] = a - b; |
378 | 0 | } |
379 | 0 | } |
380 | 0 | return r; |
381 | 0 | } |
382 | | |
383 | | /** |
384 | | * Sample a polynomial deterministically from a seed and a nonce, with output |
385 | | * polynomial close to centered binomial distribution with parameter eta=2. |
386 | | */ |
387 | | static Polynomial getnoise_eta2(const secure_vector<uint8_t>& seed, uint8_t nonce, const KyberConstants& mode) |
388 | 0 | { |
389 | 0 | const auto eta2 = mode.eta2(); |
390 | 0 | BOTAN_ASSERT(eta2 == 2, "Invalid eta2 value"); |
391 | |
|
392 | 0 | const auto outlen = eta2 * KyberConstants::N / 4; |
393 | 0 | return Polynomial::cbd2(mode.PRF(seed, nonce, outlen)); |
394 | 0 | } |
395 | | |
396 | | /** |
397 | | * Sample a polynomial deterministically from a seed and a nonce, with output |
398 | | * polynomial close to centered binomial distribution with parameter mode.eta1() |
399 | | */ |
400 | | static Polynomial getnoise_eta1(const secure_vector<uint8_t>& seed, uint8_t nonce, const KyberConstants& mode) |
401 | 0 | { |
402 | 0 | const auto eta1 = mode.eta1(); |
403 | 0 | BOTAN_ASSERT(eta1 == 2 || eta1 == 3, "Invalid eta1 value"); |
404 | |
|
405 | 0 | const auto outlen = eta1 * KyberConstants::N / 4; |
406 | 0 | return (eta1 == 2) ? Polynomial::cbd2(mode.PRF(seed, nonce, outlen)) |
407 | 0 | : Polynomial::cbd3(mode.PRF(seed, nonce, outlen)); |
408 | 0 | } |
409 | | |
410 | | template <typename Alloc> |
411 | | static Polynomial from_bytes(const std::vector<uint8_t, Alloc>& a, const size_t offset = 0) |
412 | 0 | { |
413 | 0 | Polynomial r; |
414 | 0 | for(size_t i = 0; i < r.m_coeffs.size() / 2; ++i) |
415 | 0 | { |
416 | 0 | r.m_coeffs[2 * i] = |
417 | 0 | ((a[3 * i + 0 + offset] >> 0) | (static_cast<uint16_t>(a[3 * i + 1 + offset]) << 8)) & 0xFFF; |
418 | 0 | r.m_coeffs[2 * i + 1] = |
419 | 0 | ((a[3 * i + 1 + offset] >> 4) | (static_cast<uint16_t>(a[3 * i + 2 + offset]) << 4)) & 0xFFF; |
420 | 0 | } |
421 | 0 | return r; |
422 | 0 | } Unexecuted instantiation: kyber.cpp:Botan::(anonymous namespace)::Polynomial Botan::(anonymous namespace)::Polynomial::from_bytes<std::__1::allocator<unsigned char> >(std::__1::vector<unsigned char, std::__1::allocator<unsigned char> > const&, unsigned long) Unexecuted instantiation: kyber.cpp:Botan::(anonymous namespace)::Polynomial Botan::(anonymous namespace)::Polynomial::from_bytes<Botan::secure_allocator<unsigned char> >(std::__1::vector<unsigned char, Botan::secure_allocator<unsigned char> > const&, unsigned long) |
423 | | |
424 | | template <typename Alloc> static Polynomial from_message(const std::vector<uint8_t, Alloc>& msg) |
425 | 0 | { |
426 | 0 | BOTAN_ASSERT(msg.size() == KyberConstants::N / 8, "message length must be Kyber_N/8 bytes"); |
427 | |
|
428 | 0 | Polynomial r; |
429 | 0 | for(size_t i = 0; i < r.m_coeffs.size() / 8; ++i) |
430 | 0 | { |
431 | 0 | for(size_t j = 0; j < 8; ++j) |
432 | 0 | { |
433 | 0 | const auto mask = -static_cast<int16_t>((msg[i] >> j) & 1); |
434 | 0 | r.m_coeffs[8 * i + j] = mask & ((KyberConstants::Q + 1) / 2); |
435 | 0 | } |
436 | 0 | } |
437 | 0 | return r; |
438 | 0 | } |
439 | | |
440 | | template <typename T = secure_vector<uint8_t>> T to_message() |
441 | 0 | { |
442 | 0 | T result(m_coeffs.size() / 8); |
443 | |
|
444 | 0 | this->csubq(); |
445 | |
|
446 | 0 | for(size_t i = 0; i < m_coeffs.size() / 8; ++i) |
447 | 0 | { |
448 | 0 | result[i] = 0; |
449 | 0 | for(size_t j = 0; j < 8; ++j) |
450 | 0 | { |
451 | 0 | const uint16_t t = (((static_cast<uint16_t>(this->m_coeffs[8 * i + j]) << 1) + KyberConstants::Q / 2) / |
452 | 0 | KyberConstants::Q) & |
453 | 0 | 1; |
454 | 0 | result[i] |= t << j; |
455 | 0 | } |
456 | 0 | } |
457 | |
|
458 | 0 | return result; |
459 | 0 | } |
460 | | |
461 | | /** |
462 | | * Adds two polynomials element-wise. Does not perform a reduction after the addition. |
463 | | * Therefore this operation might cause an integer overflow. |
464 | | */ |
465 | | Polynomial& operator+=(const Polynomial& other) |
466 | 0 | { |
467 | 0 | for(size_t i = 0; i < this->m_coeffs.size(); ++i) |
468 | 0 | { |
469 | 0 | BOTAN_DEBUG_ASSERT(static_cast<int32_t>(this->m_coeffs[i]) + other.m_coeffs[i] <= std::numeric_limits<int16_t>::max()); |
470 | 0 | this->m_coeffs[i] = this->m_coeffs[i] + other.m_coeffs[i]; |
471 | 0 | } |
472 | 0 | return *this; |
473 | 0 | } |
474 | | |
475 | | /** |
476 | | * Subtracts two polynomials element-wise. Does not perform a reduction after the subtraction. |
477 | | * Therefore this operation might cause an integer underflow. |
478 | | */ |
479 | | Polynomial& operator-=(const Polynomial& other) |
480 | 0 | { |
481 | 0 | for(size_t i = 0; i < this->m_coeffs.size(); ++i) |
482 | 0 | { |
483 | 0 | BOTAN_DEBUG_ASSERT(static_cast<int32_t>(other.m_coeffs[i]) - this->m_coeffs[i] >= std::numeric_limits<int16_t>::min()); |
484 | 0 | this->m_coeffs[i] = other.m_coeffs[i] - this->m_coeffs[i]; |
485 | 0 | } |
486 | 0 | return *this; |
487 | 0 | } |
488 | | |
489 | | /** |
490 | | * Multiplication of two polynomials in NTT domain |
491 | | */ |
492 | | static Polynomial basemul_montgomery(const Polynomial& a, const Polynomial& b) |
493 | 0 | { |
494 | | /** |
495 | | * Multiplication of polynomials in Zq[X]/(X^2-zeta) used for |
496 | | * multiplication of elements in Rq in NTT domain. |
497 | | */ |
498 | 0 | auto basemul = [](int16_t r[2], const int16_t s[2], const int16_t t[2], const int16_t zeta) |
499 | 0 | { |
500 | 0 | r[0] = fqmul(s[1], t[1]); |
501 | 0 | r[0] = fqmul(r[0], zeta); |
502 | 0 | r[0] += fqmul(s[0], t[0]); |
503 | |
|
504 | 0 | r[1] = fqmul(s[0], t[1]); |
505 | 0 | r[1] += fqmul(s[1], t[0]); |
506 | 0 | }; |
507 | |
|
508 | 0 | Polynomial r; |
509 | |
|
510 | 0 | for(size_t i = 0; i < r.m_coeffs.size() / 4; ++i) |
511 | 0 | { |
512 | 0 | basemul(&r.m_coeffs[4 * i], &a.m_coeffs[4 * i], &b.m_coeffs[4 * i], KyberConstants::zetas[64 + i]); |
513 | 0 | basemul(&r.m_coeffs[4 * i + 2], &a.m_coeffs[4 * i + 2], &b.m_coeffs[4 * i + 2], |
514 | 0 | -KyberConstants::zetas[64 + i]); |
515 | 0 | } |
516 | |
|
517 | 0 | return r; |
518 | 0 | } |
519 | | |
520 | | /** |
521 | | * Run rejection sampling on uniform random bytes to generate uniform |
522 | | * random integers mod q. |
523 | | */ |
524 | | static Polynomial sample_rej_uniform(std::unique_ptr<StreamCipher> xof) |
525 | 0 | { |
526 | 0 | Polynomial p; |
527 | |
|
528 | 0 | size_t count = 0; |
529 | 0 | while(count < p.m_coeffs.size()) |
530 | 0 | { |
531 | | // TODO: this is called a lot and is likely a bottleneck |
532 | | // (cipher1() is virtual) |
533 | 0 | std::array<uint8_t, 3> buf{0, 0, 0}; |
534 | 0 | xof->cipher1(buf.data(), buf.size()); |
535 | |
|
536 | 0 | const uint16_t val0 = ((buf[0] >> 0) | (static_cast<uint16_t>(buf[1]) << 8)) & 0xFFF; |
537 | 0 | const uint16_t val1 = ((buf[1] >> 4) | (static_cast<uint16_t>(buf[2]) << 4)) & 0xFFF; |
538 | |
|
539 | 0 | if(val0 < KyberConstants::Q) |
540 | 0 | { p.m_coeffs[count++] = val0; } |
541 | 0 | if(count < p.m_coeffs.size() && val1 < KyberConstants::Q) |
542 | 0 | { p.m_coeffs[count++] = val1; } |
543 | 0 | } |
544 | |
|
545 | 0 | return p; |
546 | 0 | } |
547 | | |
548 | | /** |
549 | | * Inplace conversion of all coefficients of a polynomial from normal |
550 | | * domain to Montgomery domain. |
551 | | */ |
552 | | void tomont() |
553 | 0 | { |
554 | 0 | constexpr int16_t f = (1ULL << 32) % KyberConstants::Q; |
555 | 0 | for(auto& c : m_coeffs) |
556 | 0 | { c = montgomery_reduce(static_cast<int32_t>(c) * f); } |
557 | 0 | } |
558 | | |
559 | | /** |
560 | | * Computes negacyclic number-theoretic transform (NTT) of a polynomial in place; |
561 | | * inputs assumed to be in normal order, output in bitreversed order. |
562 | | */ |
563 | | void ntt() |
564 | 0 | { |
565 | 0 | for(size_t len = m_coeffs.size() / 2, k = 0; len >= 2; len /= 2) |
566 | 0 | { |
567 | 0 | for(size_t start = 0, j = 0; start < m_coeffs.size(); start = j + len) |
568 | 0 | { |
569 | 0 | const auto zeta = KyberConstants::zetas[++k]; |
570 | 0 | for(j = start; j < start + len; ++j) |
571 | 0 | { |
572 | 0 | const auto t = fqmul(zeta, m_coeffs[j + len]); |
573 | 0 | m_coeffs[j + len] = m_coeffs[j] - t; |
574 | 0 | m_coeffs[j] = m_coeffs[j] + t; |
575 | 0 | } |
576 | 0 | } |
577 | 0 | } |
578 | |
|
579 | 0 | reduce(); |
580 | 0 | } |
581 | | |
582 | | /** |
583 | | * Computes inverse of negacyclic number-theoretic transform (NTT) of a polynomial |
584 | | * in place; inputs assumed to be in bitreversed order, output in normal order. |
585 | | */ |
586 | | void invntt_tomont() |
587 | 0 | { |
588 | 0 | for(size_t len = 2, k = 0; len <= m_coeffs.size() / 2; len *= 2) |
589 | 0 | { |
590 | 0 | for(size_t start = 0, j = 0; start < m_coeffs.size(); start = j + len) |
591 | 0 | { |
592 | 0 | const auto zeta = KyberConstants::zetas_inv[k++]; |
593 | 0 | for(j = start; j < start + len; ++j) |
594 | 0 | { |
595 | 0 | const auto t = m_coeffs[j]; |
596 | 0 | m_coeffs[j] = barrett_reduce(t + m_coeffs[j + len]); |
597 | 0 | m_coeffs[j + len] = fqmul(zeta, t - m_coeffs[j + len]); |
598 | 0 | } |
599 | 0 | } |
600 | 0 | } |
601 | |
|
602 | 0 | for(auto& c : m_coeffs) |
603 | 0 | { c = fqmul(c, KyberConstants::zetas_inv[127]); } |
604 | 0 | } |
605 | | |
606 | | private: |
607 | | /** |
608 | | * Barrett reduction; given a 16-bit integer a, computes 16-bit integer congruent |
609 | | * to a mod q in {0,...,q}. |
610 | | */ |
611 | | static int16_t barrett_reduce(int16_t a) |
612 | 0 | { |
613 | 0 | int16_t t; |
614 | 0 | const int16_t v = ((1U << 26) + KyberConstants::Q / 2) / KyberConstants::Q; |
615 | |
|
616 | 0 | t = static_cast<int32_t>(v) * a >> 26; |
617 | 0 | t *= KyberConstants::Q; |
618 | 0 | return a - t; |
619 | 0 | } |
620 | | |
621 | | /** |
622 | | * Multiplication followed by Montgomery reduction. |
623 | | */ |
624 | | static int16_t fqmul(int16_t a, int16_t b) |
625 | 0 | { |
626 | 0 | return montgomery_reduce(static_cast<int32_t>(a) * b); |
627 | 0 | } |
628 | | |
629 | | /** |
630 | | * Montgomery reduction; given a 32-bit integer a, computes 16-bit integer |
631 | | * congruent to a * R^-1 mod q, where R=2^16 |
632 | | */ |
633 | | static int16_t montgomery_reduce(int32_t a) |
634 | 0 | { |
635 | 0 | const int16_t u = static_cast<int16_t>(a * KyberConstants::Q_Inv); |
636 | 0 | int32_t t = static_cast<int32_t>(u) * KyberConstants::Q; |
637 | 0 | t = a - t; |
638 | 0 | t >>= 16; |
639 | 0 | return static_cast<int16_t>(t); |
640 | 0 | } |
641 | | }; |
642 | | |
643 | | class PolynomialVector |
644 | | { |
645 | | public: |
646 | | std::vector<Polynomial> m_vec; |
647 | | |
648 | | public: |
649 | | PolynomialVector() = delete; |
650 | | explicit PolynomialVector(const size_t k) : m_vec(k) |
651 | 0 | { |
652 | 0 | } |
653 | | |
654 | | template <typename Alloc> |
655 | | static PolynomialVector from_bytes(const std::vector<uint8_t, Alloc>& a, const KyberConstants& mode) |
656 | 0 | { |
657 | 0 | BOTAN_ASSERT(a.size() == mode.polynomial_vector_byte_length(), "wrong byte length for frombytes"); |
658 | |
|
659 | 0 | PolynomialVector r(mode.k()); |
660 | 0 | for(size_t i = 0; i < mode.k(); ++i) |
661 | 0 | { r.m_vec[i] = Polynomial::from_bytes(a, i * KyberConstants::kSerializedPolynomialByteLength); } |
662 | 0 | return r; |
663 | 0 | } Unexecuted instantiation: kyber.cpp:Botan::(anonymous namespace)::PolynomialVector Botan::(anonymous namespace)::PolynomialVector::from_bytes<std::__1::allocator<unsigned char> >(std::__1::vector<unsigned char, std::__1::allocator<unsigned char> > const&, Botan::(anonymous namespace)::KyberConstants const&) Unexecuted instantiation: kyber.cpp:Botan::(anonymous namespace)::PolynomialVector Botan::(anonymous namespace)::PolynomialVector::from_bytes<Botan::secure_allocator<unsigned char> >(std::__1::vector<unsigned char, Botan::secure_allocator<unsigned char> > const&, Botan::(anonymous namespace)::KyberConstants const&) |
664 | | |
665 | | /** |
666 | | * Pointwise multiply elements of a and b, accumulate into r, and multiply by 2^-16. |
667 | | */ |
668 | | static Polynomial pointwise_acc_montgomery(const PolynomialVector& a, const PolynomialVector& b) |
669 | 0 | { |
670 | 0 | BOTAN_ASSERT(a.m_vec.size() == b.m_vec.size(), "pointwise_acc_montgomery works on equally sized " |
671 | 0 | "PolynomialVectors only"); |
672 | |
|
673 | 0 | auto r = Polynomial::basemul_montgomery(a.m_vec[0], b.m_vec[0]); |
674 | 0 | for(size_t i = 1; i < a.m_vec.size(); ++i) |
675 | 0 | { |
676 | 0 | r += Polynomial::basemul_montgomery(a.m_vec[i], b.m_vec[i]); |
677 | 0 | } |
678 | |
|
679 | 0 | r.reduce(); |
680 | 0 | return r; |
681 | 0 | } |
682 | | |
683 | | static PolynomialVector getnoise_eta2(const secure_vector<uint8_t>& seed, uint8_t nonce, const KyberConstants& mode) |
684 | 0 | { |
685 | 0 | PolynomialVector r(mode.k()); |
686 | |
|
687 | 0 | for(auto& p : r.m_vec) |
688 | 0 | { |
689 | 0 | p = Polynomial::getnoise_eta2(seed, nonce++, mode); |
690 | 0 | } |
691 | |
|
692 | 0 | return r; |
693 | 0 | } |
694 | | |
695 | | static PolynomialVector getnoise_eta1(const secure_vector<uint8_t>& seed, uint8_t nonce, const KyberConstants& mode) |
696 | 0 | { |
697 | 0 | PolynomialVector r(mode.k()); |
698 | |
|
699 | 0 | for(auto& p : r.m_vec) |
700 | 0 | { |
701 | 0 | p = Polynomial::getnoise_eta1(seed, nonce++, mode); |
702 | 0 | } |
703 | |
|
704 | 0 | return r; |
705 | 0 | } |
706 | | |
707 | | template <typename T = std::vector<uint8_t>> T to_bytes() |
708 | 0 | { |
709 | 0 | T r; |
710 | |
|
711 | 0 | r.reserve(m_vec.size() * KyberConstants::kSerializedPolynomialByteLength); |
712 | 0 | for(auto& v : m_vec) |
713 | 0 | { |
714 | 0 | const auto poly = v.to_bytes<T>(); |
715 | 0 | r.insert(r.end(), poly.begin(), poly.end()); |
716 | 0 | } |
717 | |
|
718 | 0 | return r; |
719 | 0 | } Unexecuted instantiation: kyber.cpp:std::__1::vector<unsigned char, std::__1::allocator<unsigned char> > Botan::(anonymous namespace)::PolynomialVector::to_bytes<std::__1::vector<unsigned char, std::__1::allocator<unsigned char> > >() Unexecuted instantiation: kyber.cpp:std::__1::vector<unsigned char, Botan::secure_allocator<unsigned char> > Botan::(anonymous namespace)::PolynomialVector::to_bytes<std::__1::vector<unsigned char, Botan::secure_allocator<unsigned char> > >() |
720 | | |
721 | | /** |
722 | | * Applies conditional subtraction of q to each coefficient of each element |
723 | | * of the vector of polynomials. |
724 | | */ |
725 | | void csubq() |
726 | 0 | { |
727 | 0 | for(auto& p : m_vec) |
728 | 0 | { |
729 | 0 | p.csubq(); |
730 | 0 | } |
731 | 0 | } |
732 | | |
733 | | PolynomialVector& operator+=(const PolynomialVector& other) |
734 | 0 | { |
735 | 0 | BOTAN_ASSERT(m_vec.size() == other.m_vec.size(), "cannot add polynomial vectors of differing lengths"); |
736 | |
|
737 | 0 | for(size_t i = 0; i < m_vec.size(); ++i) |
738 | 0 | { m_vec[i] += other.m_vec[i]; } |
739 | 0 | return *this; |
740 | 0 | } |
741 | | |
742 | | /** |
743 | | * Applies Barrett reduction to each coefficient of each element of a vector of polynomials. |
744 | | */ |
745 | | void reduce() |
746 | 0 | { |
747 | 0 | for(auto& v : m_vec) |
748 | 0 | { v.reduce(); } |
749 | 0 | } |
750 | | |
751 | | /** |
752 | | * Apply inverse NTT to all elements of a vector of polynomials and multiply by Montgomery factor 2^16. |
753 | | */ |
754 | | void invntt_tomont() |
755 | 0 | { |
756 | 0 | for(auto& v : m_vec) |
757 | 0 | { v.invntt_tomont(); } |
758 | 0 | } |
759 | | |
760 | | /** |
761 | | * Apply forward NTT to all elements of a vector of polynomials. |
762 | | */ |
763 | | void ntt() |
764 | 0 | { |
765 | 0 | for(auto& v : m_vec) |
766 | 0 | { v.ntt(); } |
767 | 0 | } |
768 | | }; |
769 | | |
770 | | class PolynomialMatrix |
771 | | { |
772 | | private: |
773 | | std::vector<PolynomialVector> m_mat; |
774 | | |
775 | | public: |
776 | | PolynomialMatrix() = delete; |
777 | | |
778 | | static PolynomialMatrix generate(const std::vector<uint8_t>& seed, const bool transposed, |
779 | | const KyberConstants& mode) |
780 | 0 | { |
781 | 0 | BOTAN_ASSERT(seed.size() == KyberConstants::kSymBytes, "unexpected seed size"); |
782 | |
|
783 | 0 | PolynomialMatrix matrix(mode); |
784 | |
|
785 | 0 | for(uint8_t i = 0; i < mode.k(); ++i) |
786 | 0 | { |
787 | 0 | for(uint8_t j = 0; j < mode.k(); ++j) |
788 | 0 | { |
789 | 0 | const auto pos = (transposed) ? std::tuple(i, j) : std::tuple(j, i); |
790 | 0 | matrix.m_mat[i].m_vec[j] = Polynomial::sample_rej_uniform(mode.XOF(seed, pos)); |
791 | 0 | } |
792 | 0 | } |
793 | |
|
794 | 0 | return matrix; |
795 | 0 | } |
796 | | |
797 | | PolynomialVector pointwise_acc_montgomery(const PolynomialVector& vec, const bool with_mont = false) |
798 | 0 | { |
799 | 0 | PolynomialVector result(m_mat.size()); |
800 | |
|
801 | 0 | for(size_t i = 0; i < m_mat.size(); ++i) |
802 | 0 | { |
803 | 0 | result.m_vec[i] = PolynomialVector::pointwise_acc_montgomery(m_mat[i], vec); |
804 | 0 | if(with_mont) |
805 | 0 | { |
806 | 0 | result.m_vec[i].tomont(); |
807 | 0 | } |
808 | 0 | } |
809 | |
|
810 | 0 | return result; |
811 | 0 | } |
812 | | |
813 | | private: |
814 | | explicit PolynomialMatrix(const KyberConstants& mode) : m_mat(mode.k(), PolynomialVector(mode.k())) |
815 | 0 | { |
816 | 0 | } |
817 | | }; |
818 | | |
819 | | class Ciphertext |
820 | | { |
821 | | protected: |
822 | | KyberConstants m_mode; |
823 | | |
824 | | public: |
825 | | PolynomialVector b; |
826 | | Polynomial v; |
827 | | |
828 | | public: |
829 | | Ciphertext() = delete; |
830 | | Ciphertext(PolynomialVector b_, Polynomial v_, KyberConstants mode) |
831 | | : m_mode(std::move(mode)), b(std::move(b_)), v(std::move(v_)) |
832 | 0 | { |
833 | 0 | } |
834 | | |
835 | | static Ciphertext from_bytes(secure_vector<uint8_t> buffer, const KyberConstants& mode) |
836 | 0 | { |
837 | 0 | const auto expected_length = polynomial_vector_compressed_bytes(mode) + polynomial_compressed_bytes(mode); |
838 | |
|
839 | 0 | if(buffer.size() != expected_length) |
840 | 0 | { |
841 | 0 | throw Invalid_Argument("unexpected length of ciphertext buffer"); |
842 | 0 | } |
843 | | |
844 | 0 | secure_vector<uint8_t> pv(buffer.begin(), buffer.begin() + polynomial_vector_compressed_bytes(mode)); |
845 | 0 | secure_vector<uint8_t> p(buffer.begin() + polynomial_vector_compressed_bytes(mode), buffer.end()); |
846 | |
|
847 | 0 | return Ciphertext(decompress_polynomial_vector(pv, mode), decompress_polynomial(p, mode), mode); |
848 | 0 | } |
849 | | |
850 | | secure_vector<uint8_t> to_bytes() |
851 | 0 | { |
852 | 0 | auto ct = compress(b, m_mode); |
853 | 0 | const auto p = compress(v, m_mode); |
854 | 0 | ct.insert(ct.end(), p.begin(), p.end()); |
855 | |
|
856 | 0 | return ct; |
857 | 0 | } |
858 | | |
859 | | private: |
860 | | static size_t polynomial_vector_compressed_bytes(const KyberConstants& mode) |
861 | 0 | { |
862 | 0 | const auto k = mode.k(); |
863 | 0 | return (k == 2 || k == 3) ? k * 320 : k * 352; |
864 | 0 | } |
865 | | |
866 | | static size_t polynomial_compressed_bytes(const KyberConstants& mode) |
867 | 0 | { |
868 | 0 | const auto k = mode.k(); |
869 | 0 | return (k == 2 || k == 3) ? 128 : 160; |
870 | 0 | } |
871 | | |
872 | | static secure_vector<uint8_t> compress(PolynomialVector& pv, const KyberConstants& mode) |
873 | 0 | { |
874 | 0 | secure_vector<uint8_t> r(polynomial_vector_compressed_bytes(mode)); |
875 | |
|
876 | 0 | pv.csubq(); |
877 | |
|
878 | 0 | if(mode.k() == 2 || mode.k() == 3) |
879 | 0 | { |
880 | 0 | uint16_t t[4]; |
881 | 0 | size_t offset = 0; |
882 | 0 | for(size_t i = 0; i < mode.k(); ++i) |
883 | 0 | { |
884 | 0 | for(size_t j = 0; j < KyberConstants::N / 4; ++j) |
885 | 0 | { |
886 | 0 | for(size_t k = 0; k < 4; ++k) |
887 | 0 | t[k] = |
888 | 0 | (((static_cast<uint32_t>(pv.m_vec[i].m_coeffs[4 * j + k]) << 10) + KyberConstants::Q / 2) / |
889 | 0 | KyberConstants::Q) & |
890 | 0 | 0x3ff; |
891 | |
|
892 | 0 | r[0 + offset] = static_cast<uint8_t>(t[0] >> 0); |
893 | 0 | r[1 + offset] = static_cast<uint8_t>((t[0] >> 8) | (t[1] << 2)); |
894 | 0 | r[2 + offset] = static_cast<uint8_t>((t[1] >> 6) | (t[2] << 4)); |
895 | 0 | r[3 + offset] = static_cast<uint8_t>((t[2] >> 4) | (t[3] << 6)); |
896 | 0 | r[4 + offset] = static_cast<uint8_t>(t[3] >> 2); |
897 | 0 | offset += 5; |
898 | 0 | } |
899 | 0 | } |
900 | 0 | } |
901 | 0 | else |
902 | 0 | { |
903 | 0 | uint16_t t[8]; |
904 | 0 | size_t offset = 0; |
905 | 0 | for(size_t i = 0; i < mode.k(); ++i) |
906 | 0 | { |
907 | 0 | for(size_t j = 0; j < KyberConstants::N / 8; ++j) |
908 | 0 | { |
909 | 0 | for(size_t k = 0; k < 8; ++k) |
910 | 0 | t[k] = |
911 | 0 | (((static_cast<uint32_t>(pv.m_vec[i].m_coeffs[8 * j + k]) << 11) + KyberConstants::Q / 2) / |
912 | 0 | KyberConstants::Q) & |
913 | 0 | 0x7ff; |
914 | |
|
915 | 0 | r[0 + offset] = static_cast<uint8_t>(t[0] >> 0); |
916 | 0 | r[1 + offset] = static_cast<uint8_t>((t[0] >> 8) | (t[1] << 3)); |
917 | 0 | r[2 + offset] = static_cast<uint8_t>((t[1] >> 5) | (t[2] << 6)); |
918 | 0 | r[3 + offset] = static_cast<uint8_t>(t[2] >> 2); |
919 | 0 | r[4 + offset] = static_cast<uint8_t>((t[2] >> 10) | (t[3] << 1)); |
920 | 0 | r[5 + offset] = static_cast<uint8_t>((t[3] >> 7) | (t[4] << 4)); |
921 | 0 | r[6 + offset] = static_cast<uint8_t>((t[4] >> 4) | (t[5] << 7)); |
922 | 0 | r[7 + offset] = static_cast<uint8_t>(t[5] >> 1); |
923 | 0 | r[8 + offset] = static_cast<uint8_t>((t[5] >> 9) | (t[6] << 2)); |
924 | 0 | r[9 + offset] = static_cast<uint8_t>((t[6] >> 6) | (t[7] << 5)); |
925 | 0 | r[10 + offset] = static_cast<uint8_t>(t[7] >> 3); |
926 | 0 | offset += 11; |
927 | 0 | } |
928 | 0 | } |
929 | 0 | } |
930 | |
|
931 | 0 | return r; |
932 | 0 | } |
933 | | |
934 | | static secure_vector<uint8_t> compress(Polynomial& p, const KyberConstants& mode) |
935 | 0 | { |
936 | 0 | secure_vector<uint8_t> r(polynomial_compressed_bytes(mode)); |
937 | |
|
938 | 0 | p.csubq(); |
939 | |
|
940 | 0 | uint8_t t[8]; |
941 | 0 | if(mode.k() == 2 || mode.k() == 3) |
942 | 0 | { |
943 | 0 | size_t offset = 0; |
944 | 0 | for(size_t i = 0; i < p.m_coeffs.size() / 8; ++i) |
945 | 0 | { |
946 | 0 | for(size_t j = 0; j < 8; ++j) |
947 | 0 | t[j] = (((static_cast<uint16_t>(p.m_coeffs[8 * i + j]) << 4) + KyberConstants::Q / 2) / |
948 | 0 | KyberConstants::Q) & |
949 | 0 | 15; |
950 | |
|
951 | 0 | r[0 + offset] = t[0] | (t[1] << 4); |
952 | 0 | r[1 + offset] = t[2] | (t[3] << 4); |
953 | 0 | r[2 + offset] = t[4] | (t[5] << 4); |
954 | 0 | r[3 + offset] = t[6] | (t[7] << 4); |
955 | 0 | offset += 4; |
956 | 0 | } |
957 | 0 | } |
958 | 0 | else if(mode.k() == 4) |
959 | 0 | { |
960 | 0 | size_t offset = 0; |
961 | 0 | for(size_t i = 0; i < p.m_coeffs.size() / 8; ++i) |
962 | 0 | { |
963 | 0 | for(size_t j = 0; j < 8; ++j) |
964 | 0 | t[j] = (((static_cast<uint32_t>(p.m_coeffs[8 * i + j]) << 5) + KyberConstants::Q / 2) / |
965 | 0 | KyberConstants::Q) & |
966 | 0 | 31; |
967 | |
|
968 | 0 | r[0 + offset] = (t[0] >> 0) | (t[1] << 5); |
969 | 0 | r[1 + offset] = (t[1] >> 3) | (t[2] << 2) | (t[3] << 7); |
970 | 0 | r[2 + offset] = (t[3] >> 1) | (t[4] << 4); |
971 | 0 | r[3 + offset] = (t[4] >> 4) | (t[5] << 1) | (t[6] << 6); |
972 | 0 | r[4 + offset] = (t[6] >> 2) | (t[7] << 3); |
973 | 0 | offset += 5; |
974 | 0 | } |
975 | 0 | } |
976 | |
|
977 | 0 | return r; |
978 | 0 | } |
979 | | |
980 | | static PolynomialVector decompress_polynomial_vector(const secure_vector<uint8_t>& buffer, |
981 | | const KyberConstants& mode) |
982 | 0 | { |
983 | 0 | BOTAN_ASSERT(buffer.size() == polynomial_vector_compressed_bytes(mode), |
984 | 0 | "unexpected length of compressed polynomial vector"); |
985 | |
|
986 | 0 | PolynomialVector r(mode.k()); |
987 | 0 | auto a = buffer.data(); |
988 | |
|
989 | 0 | if(mode.k() == 4) |
990 | 0 | { |
991 | 0 | uint16_t t[8]; |
992 | 0 | for(size_t i = 0; i < mode.k(); ++i) |
993 | 0 | { |
994 | 0 | for(size_t j = 0; j < KyberConstants::N / 8; ++j) |
995 | 0 | { |
996 | 0 | t[0] = (a[0] >> 0) | (static_cast<uint16_t>(a[1]) << 8); |
997 | 0 | t[1] = (a[1] >> 3) | (static_cast<uint16_t>(a[2]) << 5); |
998 | 0 | t[2] = (a[2] >> 6) | (static_cast<uint16_t>(a[3]) << 2) | (static_cast<uint16_t>(a[4]) << 10); |
999 | 0 | t[3] = (a[4] >> 1) | (static_cast<uint16_t>(a[5]) << 7); |
1000 | 0 | t[4] = (a[5] >> 4) | (static_cast<uint16_t>(a[6]) << 4); |
1001 | 0 | t[5] = (a[6] >> 7) | (static_cast<uint16_t>(a[7]) << 1) | (static_cast<uint16_t>(a[8]) << 9); |
1002 | 0 | t[6] = (a[8] >> 2) | (static_cast<uint16_t>(a[9]) << 6); |
1003 | 0 | t[7] = (a[9] >> 5) | (static_cast<uint16_t>(a[10]) << 3); |
1004 | 0 | a += 11; |
1005 | |
|
1006 | 0 | for(size_t k = 0; k < 8; ++k) |
1007 | 0 | r.m_vec[i].m_coeffs[8 * j + k] = |
1008 | 0 | (static_cast<uint32_t>(t[k] & 0x7FF) * KyberConstants::Q + 1024) >> 11; |
1009 | 0 | } |
1010 | 0 | } |
1011 | 0 | } |
1012 | 0 | else |
1013 | 0 | { |
1014 | 0 | uint16_t t[4]; |
1015 | 0 | for(size_t i = 0; i < mode.k(); ++i) |
1016 | 0 | { |
1017 | 0 | for(size_t j = 0; j < KyberConstants::N / 4; ++j) |
1018 | 0 | { |
1019 | 0 | t[0] = (a[0] >> 0) | (static_cast<uint16_t>(a[1]) << 8); |
1020 | 0 | t[1] = (a[1] >> 2) | (static_cast<uint16_t>(a[2]) << 6); |
1021 | 0 | t[2] = (a[2] >> 4) | (static_cast<uint16_t>(a[3]) << 4); |
1022 | 0 | t[3] = (a[3] >> 6) | (static_cast<uint16_t>(a[4]) << 2); |
1023 | 0 | a += 5; |
1024 | |
|
1025 | 0 | for(size_t k = 0; k < 4; ++k) |
1026 | 0 | r.m_vec[i].m_coeffs[4 * j + k] = |
1027 | 0 | (static_cast<uint32_t>(t[k] & 0x3FF) * KyberConstants::Q + 512) >> 10; |
1028 | 0 | } |
1029 | 0 | } |
1030 | 0 | } |
1031 | |
|
1032 | 0 | return r; |
1033 | 0 | } |
1034 | | |
1035 | | static Polynomial decompress_polynomial(const secure_vector<uint8_t>& buffer, const KyberConstants& mode) |
1036 | 0 | { |
1037 | 0 | BOTAN_ASSERT(buffer.size() == polynomial_compressed_bytes(mode), "unexpected length of compressed polynomial"); |
1038 | |
|
1039 | 0 | Polynomial r; |
1040 | 0 | auto a = buffer.data(); |
1041 | |
|
1042 | 0 | if(mode.k() == 4) |
1043 | 0 | { |
1044 | 0 | uint8_t t[8]; |
1045 | 0 | for(size_t i = 0; i < KyberConstants::N / 8; ++i) |
1046 | 0 | { |
1047 | 0 | t[0] = (a[0] >> 0); |
1048 | 0 | t[1] = (a[0] >> 5) | (a[1] << 3); |
1049 | 0 | t[2] = (a[1] >> 2); |
1050 | 0 | t[3] = (a[1] >> 7) | (a[2] << 1); |
1051 | 0 | t[4] = (a[2] >> 4) | (a[3] << 4); |
1052 | 0 | t[5] = (a[3] >> 1); |
1053 | 0 | t[6] = (a[3] >> 6) | (a[4] << 2); |
1054 | 0 | t[7] = (a[4] >> 3); |
1055 | 0 | a += 5; |
1056 | |
|
1057 | 0 | for(size_t j = 0; j < 8; ++j) |
1058 | 0 | { r.m_coeffs[8 * i + j] = (static_cast<uint32_t>(t[j] & 31) * KyberConstants::Q + 16) >> 5; } |
1059 | 0 | } |
1060 | 0 | } |
1061 | 0 | else |
1062 | 0 | { |
1063 | 0 | for(size_t i = 0; i < KyberConstants::N / 2; ++i) |
1064 | 0 | { |
1065 | 0 | r.m_coeffs[2 * i + 0] = ((static_cast<uint16_t>(a[0] & 15) * KyberConstants::Q) + 8) >> 4; |
1066 | 0 | r.m_coeffs[2 * i + 1] = ((static_cast<uint16_t>(a[0] >> 4) * KyberConstants::Q) + 8) >> 4; |
1067 | 0 | a += 1; |
1068 | 0 | } |
1069 | 0 | } |
1070 | |
|
1071 | 0 | return r; |
1072 | 0 | } |
1073 | | }; |
1074 | | |
1075 | | } // anonymous namespace |
1076 | | |
1077 | | class Kyber_PublicKeyInternal |
1078 | | { |
1079 | | public: |
1080 | | Kyber_PublicKeyInternal(KyberConstants mode, std::vector<uint8_t> polynomials, std::vector<uint8_t> seed) |
1081 | | : m_mode(std::move(mode)), |
1082 | | m_polynomials(PolynomialVector::from_bytes(polynomials, m_mode)), |
1083 | | m_seed(std::move(seed)) |
1084 | 0 | { |
1085 | 0 | } |
1086 | | |
1087 | | Kyber_PublicKeyInternal(KyberConstants mode, PolynomialVector polynomials, std::vector<uint8_t> seed) |
1088 | | : m_mode(std::move(mode)), m_polynomials(std::move(polynomials)), m_seed(std::move(seed)) |
1089 | 0 | { |
1090 | 0 | } |
1091 | | |
1092 | | PolynomialVector& polynomials() |
1093 | 0 | { |
1094 | 0 | return m_polynomials; |
1095 | 0 | } |
1096 | | const std::vector<uint8_t>& seed() const |
1097 | 0 | { |
1098 | 0 | return m_seed; |
1099 | 0 | } |
1100 | | const KyberConstants& mode() const |
1101 | 0 | { |
1102 | 0 | return m_mode; |
1103 | 0 | } |
1104 | | |
1105 | | Kyber_PublicKeyInternal() = delete; |
1106 | | |
1107 | | private: |
1108 | | KyberConstants m_mode; |
1109 | | PolynomialVector m_polynomials; |
1110 | | std::vector<uint8_t> m_seed; |
1111 | | }; |
1112 | | |
1113 | | class Kyber_PrivateKeyInternal |
1114 | | { |
1115 | | public: |
1116 | | Kyber_PrivateKeyInternal(KyberConstants mode, PolynomialVector polynomials, secure_vector<uint8_t> z) |
1117 | | : m_mode(std::move(mode)), m_polynomials(std::move(polynomials)), m_z(std::move(z)) |
1118 | 0 | { |
1119 | 0 | } |
1120 | | |
1121 | | PolynomialVector& polynomials() |
1122 | 0 | { |
1123 | 0 | return m_polynomials; |
1124 | 0 | } |
1125 | | |
1126 | | const secure_vector<uint8_t>& z() const |
1127 | 0 | { |
1128 | 0 | return m_z; |
1129 | 0 | } |
1130 | | |
1131 | | const KyberConstants& mode() const |
1132 | 0 | { |
1133 | 0 | return m_mode; |
1134 | 0 | } |
1135 | | |
1136 | | Kyber_PrivateKeyInternal() = delete; |
1137 | | |
1138 | | private: |
1139 | | KyberConstants m_mode; |
1140 | | PolynomialVector m_polynomials; |
1141 | | secure_vector<uint8_t> m_z; |
1142 | | }; |
1143 | | |
1144 | | class Kyber_KEM_Cryptor |
1145 | | { |
1146 | | protected: |
1147 | | const KyberConstants& m_mode; |
1148 | | |
1149 | | protected: |
1150 | | Kyber_KEM_Cryptor(const KyberConstants& mode) : m_mode(mode) |
1151 | 0 | { |
1152 | 0 | } |
1153 | | |
1154 | | secure_vector<uint8_t> indcpa_enc(const secure_vector<uint8_t>& m, |
1155 | | const secure_vector<uint8_t>& coins, |
1156 | | const std::shared_ptr<Kyber_PublicKeyInternal> pk) |
1157 | 0 | { |
1158 | 0 | auto sp = PolynomialVector::getnoise_eta1(coins, 0, m_mode); |
1159 | 0 | auto ep = PolynomialVector::getnoise_eta2(coins, m_mode.k(), m_mode); |
1160 | 0 | auto epp = Polynomial::getnoise_eta2(coins, 2 * m_mode.k(), m_mode); |
1161 | |
|
1162 | 0 | auto k = Polynomial::from_message(m); |
1163 | 0 | auto at = PolynomialMatrix::generate(pk->seed(), true, m_mode); |
1164 | |
|
1165 | 0 | sp.ntt(); |
1166 | | |
1167 | | // matrix-vector multiplication |
1168 | 0 | auto bp = at.pointwise_acc_montgomery(sp); |
1169 | 0 | auto v = PolynomialVector::pointwise_acc_montgomery(pk->polynomials(), sp); |
1170 | |
|
1171 | 0 | bp.invntt_tomont(); |
1172 | 0 | v.invntt_tomont(); |
1173 | |
|
1174 | 0 | bp += ep; |
1175 | 0 | v += epp; |
1176 | 0 | v += k; |
1177 | 0 | bp.reduce(); |
1178 | 0 | v.reduce(); |
1179 | |
|
1180 | 0 | return Ciphertext(std::move(bp), std::move(v), m_mode).to_bytes(); |
1181 | 0 | } |
1182 | | }; |
1183 | | |
1184 | | class Kyber_KEM_Encryptor final : public PK_Ops::KEM_Encryption_with_KDF, |
1185 | | protected Kyber_KEM_Cryptor |
1186 | | { |
1187 | | public: |
1188 | | Kyber_KEM_Encryptor(const Kyber_PublicKey& key, const std::string& kdf) |
1189 | | : KEM_Encryption_with_KDF(kdf) |
1190 | | , Kyber_KEM_Cryptor(key.m_public->mode()) |
1191 | | , m_key(key) |
1192 | 0 | { |
1193 | 0 | } |
1194 | | |
1195 | | void raw_kem_encrypt(secure_vector<uint8_t>& out_encapsulated_key, |
1196 | | secure_vector<uint8_t>& out_shared_key, |
1197 | | RandomNumberGenerator& rng) override |
1198 | 0 | { |
1199 | | // naming from kyber spec |
1200 | 0 | auto H = m_mode.H(); |
1201 | 0 | auto G = m_mode.G(); |
1202 | 0 | auto KDF = m_mode.KDF(); |
1203 | |
|
1204 | 0 | H->update(rng.random_vec(KyberConstants::kSymBytes)); |
1205 | 0 | const auto shared_secret = H->final(); |
1206 | | |
1207 | | // Multitarget countermeasure for coins + contributory KEM |
1208 | 0 | G->update(shared_secret); |
1209 | 0 | G->update(H->process(m_key.public_key_bits_raw())); |
1210 | 0 | const auto g_out = G->final(); |
1211 | |
|
1212 | 0 | const auto middle = G->output_length() / 2; |
1213 | 0 | const auto lower_g_out = secure_vector<uint8_t>(g_out.begin(), g_out.begin() + middle); |
1214 | 0 | const auto upper_g_out = secure_vector<uint8_t>(g_out.begin() + middle, g_out.end()); |
1215 | |
|
1216 | 0 | out_encapsulated_key = indcpa_enc(shared_secret, upper_g_out, m_key.m_public); |
1217 | |
|
1218 | 0 | KDF->update(lower_g_out); |
1219 | 0 | KDF->update(H->process(out_encapsulated_key)); |
1220 | 0 | out_shared_key = KDF->final(); |
1221 | 0 | } |
1222 | | |
1223 | | private: |
1224 | | const Kyber_PublicKey& m_key; |
1225 | | }; |
1226 | | |
1227 | | class Kyber_KEM_Decryptor final : public PK_Ops::KEM_Decryption_with_KDF, |
1228 | | protected Kyber_KEM_Cryptor |
1229 | | { |
1230 | | public: |
1231 | | Kyber_KEM_Decryptor(const Kyber_PrivateKey& key, const std::string& kdf) |
1232 | | : PK_Ops::KEM_Decryption_with_KDF(kdf) |
1233 | | , Kyber_KEM_Cryptor(key.m_private->mode()) |
1234 | | , m_key(key) |
1235 | 0 | { |
1236 | 0 | } |
1237 | | |
1238 | | secure_vector<uint8_t> raw_kem_decrypt(const uint8_t encap_key[], size_t len_encap_key) override |
1239 | 0 | { |
1240 | | // naming from kyber spec |
1241 | 0 | auto H = m_mode.H(); |
1242 | 0 | auto G = m_mode.G(); |
1243 | 0 | auto KDF = m_mode.KDF(); |
1244 | |
|
1245 | 0 | const auto shared_secret = indcpa_dec(encap_key, len_encap_key); |
1246 | | |
1247 | | // Multitarget countermeasure for coins + contributory KEM |
1248 | 0 | G->update(shared_secret); |
1249 | 0 | G->update(H->process(m_key.public_key_bits_raw())); |
1250 | |
|
1251 | 0 | const auto g_out = G->final(); |
1252 | |
|
1253 | 0 | const auto middle = G->output_length() / 2; |
1254 | 0 | const auto lower_g_out = secure_vector<uint8_t>(g_out.begin(), g_out.begin() + middle); |
1255 | 0 | const auto upper_g_out = secure_vector<uint8_t>(g_out.begin() + middle, g_out.end()); |
1256 | |
|
1257 | 0 | H->update(encap_key, len_encap_key); |
1258 | |
|
1259 | 0 | const auto cmp = indcpa_enc(shared_secret, upper_g_out, m_key.m_public); |
1260 | 0 | BOTAN_ASSERT(len_encap_key == cmp.size(), "output of indcpa_enc has unexpected length"); |
1261 | | |
1262 | | // Overwrite pre-k with z on re-encryption failure (constant time) |
1263 | 0 | secure_vector<uint8_t> lower_g_out_final(lower_g_out.size()); |
1264 | 0 | const uint8_t reencrypt_success = constant_time_compare(encap_key, cmp.data(), len_encap_key); |
1265 | 0 | BOTAN_ASSERT_NOMSG(lower_g_out.size() == m_key.m_private->z().size()); |
1266 | 0 | CT::conditional_copy_mem(reencrypt_success, lower_g_out_final.data(), |
1267 | 0 | lower_g_out.data(), m_key.m_private->z().data(), |
1268 | 0 | lower_g_out_final.size()); |
1269 | |
|
1270 | 0 | KDF->update(lower_g_out_final); |
1271 | 0 | KDF->update(H->final()); |
1272 | |
|
1273 | 0 | return KDF->final(); |
1274 | 0 | } |
1275 | | |
1276 | | private: |
1277 | | secure_vector<uint8_t> indcpa_dec(const uint8_t* c, size_t c_len) |
1278 | 0 | { |
1279 | 0 | auto ct = Ciphertext::from_bytes(secure_vector<uint8_t>(c, c + c_len), m_mode); |
1280 | |
|
1281 | 0 | ct.b.ntt(); |
1282 | 0 | auto mp = PolynomialVector::pointwise_acc_montgomery(m_key.m_private->polynomials(), ct.b); |
1283 | 0 | mp.invntt_tomont(); |
1284 | |
|
1285 | 0 | mp -= ct.v; |
1286 | 0 | mp.reduce(); |
1287 | 0 | return mp.to_message(); |
1288 | 0 | } |
1289 | | |
1290 | | private: |
1291 | | const Kyber_PrivateKey& m_key; |
1292 | | }; |
1293 | | |
1294 | | KyberMode Kyber_PublicKey::mode() const |
1295 | 0 | { |
1296 | 0 | return m_public->mode().mode(); |
1297 | 0 | } |
1298 | | |
1299 | | std::string Kyber_PublicKey::algo_name() const |
1300 | 0 | { |
1301 | 0 | return object_identifier().to_formatted_string(); |
1302 | 0 | } |
1303 | | |
1304 | | AlgorithmIdentifier Kyber_PublicKey::algorithm_identifier() const |
1305 | 0 | { |
1306 | 0 | return AlgorithmIdentifier(mode().object_identifier(), AlgorithmIdentifier::USE_EMPTY_PARAM); |
1307 | 0 | } |
1308 | | |
1309 | | OID Kyber_PublicKey::object_identifier() const |
1310 | 0 | { |
1311 | 0 | return mode().object_identifier(); |
1312 | 0 | } |
1313 | | |
1314 | | size_t Kyber_PublicKey::estimated_strength() const |
1315 | 0 | { |
1316 | 0 | return m_public->mode().estimated_strength(); |
1317 | 0 | } |
1318 | | |
1319 | | void Kyber_PublicKey::initialize_from_encoding(const std::vector<uint8_t>& pub_key, |
1320 | | KyberMode m, |
1321 | | KyberKeyEncoding encoding) |
1322 | 0 | { |
1323 | 0 | KyberConstants mode(m); |
1324 | |
|
1325 | 0 | std::vector<uint8_t> poly_vec, seed; |
1326 | |
|
1327 | 0 | switch(encoding) |
1328 | 0 | { |
1329 | 0 | case KyberKeyEncoding::Full: |
1330 | 0 | BER_Decoder(pub_key) |
1331 | 0 | .start_sequence() |
1332 | 0 | .decode(poly_vec, ASN1_Type::OctetString) |
1333 | 0 | .decode(seed, ASN1_Type::OctetString) |
1334 | 0 | .end_cons(); |
1335 | 0 | break; |
1336 | 0 | case KyberKeyEncoding::Raw: |
1337 | 0 | if(pub_key.size() != mode.public_key_byte_length()) |
1338 | 0 | { |
1339 | 0 | throw Invalid_Argument("kyber public key does not have the correct byte count"); |
1340 | 0 | } |
1341 | 0 | poly_vec = std::vector<uint8_t>(pub_key.begin(), pub_key.end() - KyberConstants::kSeedLength); |
1342 | 0 | seed = std::vector<uint8_t>(pub_key.end() - KyberConstants::kSeedLength, pub_key.end()); |
1343 | 0 | break; |
1344 | 0 | } |
1345 | | |
1346 | 0 | if(poly_vec.size() != mode.polynomial_vector_byte_length()) |
1347 | 0 | { |
1348 | 0 | throw Invalid_Argument("kyber public key t-param does not have the correct byte count"); |
1349 | 0 | } |
1350 | | |
1351 | 0 | if(seed.size() != KyberConstants::kSeedLength) |
1352 | 0 | { |
1353 | 0 | throw Invalid_Argument("kyber public key rho-param does not have the correct byte count"); |
1354 | 0 | } |
1355 | | |
1356 | 0 | m_public = std::make_shared<Kyber_PublicKeyInternal>(std::move(mode), std::move(poly_vec), std::move(seed)); |
1357 | 0 | } |
1358 | | |
1359 | | Kyber_PublicKey::Kyber_PublicKey(const AlgorithmIdentifier& alg_id, |
1360 | | const std::vector<uint8_t>& key_bits) : |
1361 | | Kyber_PublicKey(key_bits, |
1362 | | KyberMode(alg_id.oid()), |
1363 | | KyberKeyEncoding::Full) |
1364 | 0 | {} Unexecuted instantiation: Botan::Kyber_PublicKey::Kyber_PublicKey(Botan::AlgorithmIdentifier const&, std::__1::vector<unsigned char, std::__1::allocator<unsigned char> > const&) Unexecuted instantiation: Botan::Kyber_PublicKey::Kyber_PublicKey(Botan::AlgorithmIdentifier const&, std::__1::vector<unsigned char, std::__1::allocator<unsigned char> > const&) |
1365 | | |
1366 | | Kyber_PublicKey::Kyber_PublicKey(const std::vector<uint8_t>& pub_key, |
1367 | | KyberMode m, |
1368 | | KyberKeyEncoding encoding) |
1369 | | : Kyber_PublicKey() |
1370 | 0 | { |
1371 | 0 | initialize_from_encoding(pub_key, m, encoding); |
1372 | 0 | } Unexecuted instantiation: Botan::Kyber_PublicKey::Kyber_PublicKey(std::__1::vector<unsigned char, std::__1::allocator<unsigned char> > const&, Botan::KyberMode, Botan::KyberKeyEncoding) Unexecuted instantiation: Botan::Kyber_PublicKey::Kyber_PublicKey(std::__1::vector<unsigned char, std::__1::allocator<unsigned char> > const&, Botan::KyberMode, Botan::KyberKeyEncoding) |
1373 | | |
1374 | | Kyber_PublicKey::Kyber_PublicKey(const Kyber_PublicKey& other) |
1375 | | : m_public(std::make_shared<Kyber_PublicKeyInternal>(*other.m_public)), m_key_encoding(other.m_key_encoding) |
1376 | 0 | { |
1377 | 0 | } Unexecuted instantiation: Botan::Kyber_PublicKey::Kyber_PublicKey(Botan::Kyber_PublicKey const&) Unexecuted instantiation: Botan::Kyber_PublicKey::Kyber_PublicKey(Botan::Kyber_PublicKey const&) |
1378 | | |
1379 | | std::vector<uint8_t> Kyber_PublicKey::public_key_bits() const |
1380 | 0 | { |
1381 | 0 | switch(m_key_encoding) |
1382 | 0 | { |
1383 | 0 | case KyberKeyEncoding::Full: |
1384 | 0 | return public_key_bits_der(); |
1385 | 0 | case KyberKeyEncoding::Raw: |
1386 | 0 | return public_key_bits_raw(); |
1387 | 0 | } |
1388 | | |
1389 | 0 | unreachable(); |
1390 | 0 | } |
1391 | | |
1392 | | std::vector<uint8_t> Kyber_PublicKey::public_key_bits_raw() const |
1393 | 0 | { |
1394 | 0 | return concat(m_public->polynomials().to_bytes<std::vector<uint8_t>>(), |
1395 | 0 | m_public->seed()); |
1396 | 0 | } |
1397 | | |
1398 | | std::vector<uint8_t> Kyber_PublicKey::public_key_bits_der() const |
1399 | 0 | { |
1400 | 0 | std::vector<uint8_t> output; |
1401 | 0 | DER_Encoder der(output); |
1402 | |
|
1403 | 0 | der.start_sequence() |
1404 | 0 | .encode(m_public->polynomials().to_bytes<std::vector<uint8_t>>(), ASN1_Type::OctetString) |
1405 | 0 | .encode(m_public->seed(), ASN1_Type::OctetString) |
1406 | 0 | .end_cons(); |
1407 | |
|
1408 | 0 | return output; |
1409 | 0 | } |
1410 | | |
1411 | | size_t Kyber_PublicKey::key_length() const |
1412 | 0 | { |
1413 | 0 | return m_public->mode().public_key_byte_length(); |
1414 | 0 | } |
1415 | | |
1416 | | bool Kyber_PublicKey::check_key(RandomNumberGenerator&, bool) const |
1417 | 0 | { |
1418 | 0 | return true; // ?? |
1419 | 0 | } |
1420 | | |
1421 | | Kyber_PrivateKey::Kyber_PrivateKey(RandomNumberGenerator& rng, KyberMode m) |
1422 | 0 | { |
1423 | 0 | KyberConstants mode(m); |
1424 | |
|
1425 | 0 | auto G = mode.G(); |
1426 | 0 | auto seed = G->process(rng.random_vec(KyberConstants::kSymBytes)); |
1427 | |
|
1428 | 0 | const auto middle = G->output_length() / 2; |
1429 | 0 | std::vector<uint8_t> seed1(seed.begin(), seed.begin() + middle); |
1430 | 0 | secure_vector<uint8_t> seed2(seed.begin() + middle, seed.end()); |
1431 | |
|
1432 | 0 | auto a = PolynomialMatrix::generate(seed1, false, mode); |
1433 | 0 | auto skpv = PolynomialVector::getnoise_eta1(seed2, 0, mode); |
1434 | 0 | auto e = PolynomialVector::getnoise_eta1(seed2, mode.k(), mode); |
1435 | |
|
1436 | 0 | skpv.ntt(); |
1437 | 0 | e.ntt(); |
1438 | | |
1439 | | // matrix-vector multiplication |
1440 | 0 | auto pkpv = a.pointwise_acc_montgomery(skpv, true); |
1441 | 0 | pkpv += e; |
1442 | 0 | pkpv.reduce(); |
1443 | |
|
1444 | 0 | m_public = std::make_shared<Kyber_PublicKeyInternal>(mode, std::move(pkpv), std::move(seed1)); |
1445 | 0 | m_private = std::make_shared<Kyber_PrivateKeyInternal>(std::move(mode), std::move(skpv), |
1446 | 0 | rng.random_vec(KyberConstants::kZLength)); |
1447 | 0 | } Unexecuted instantiation: Botan::Kyber_PrivateKey::Kyber_PrivateKey(Botan::RandomNumberGenerator&, Botan::KyberMode) Unexecuted instantiation: Botan::Kyber_PrivateKey::Kyber_PrivateKey(Botan::RandomNumberGenerator&, Botan::KyberMode) |
1448 | | |
1449 | | Kyber_PrivateKey::Kyber_PrivateKey(const AlgorithmIdentifier& alg_id, |
1450 | | const secure_vector<uint8_t>& key_bits) : |
1451 | | Kyber_PrivateKey(key_bits, |
1452 | | KyberMode(alg_id.oid()), |
1453 | | KyberKeyEncoding::Full) |
1454 | 0 | {} Unexecuted instantiation: Botan::Kyber_PrivateKey::Kyber_PrivateKey(Botan::AlgorithmIdentifier const&, std::__1::vector<unsigned char, Botan::secure_allocator<unsigned char> > const&) Unexecuted instantiation: Botan::Kyber_PrivateKey::Kyber_PrivateKey(Botan::AlgorithmIdentifier const&, std::__1::vector<unsigned char, Botan::secure_allocator<unsigned char> > const&) |
1455 | | |
1456 | | Kyber_PrivateKey::Kyber_PrivateKey(const secure_vector<uint8_t>& sk, |
1457 | | KyberMode m, |
1458 | | KyberKeyEncoding encoding) |
1459 | 0 | { |
1460 | 0 | KyberConstants mode(m); |
1461 | |
|
1462 | 0 | if(encoding == KyberKeyEncoding::Full) |
1463 | 0 | { |
1464 | 0 | secure_vector<uint8_t> z, skpv; |
1465 | 0 | BER_Object pub_key; |
1466 | |
|
1467 | 0 | std::vector<uint8_t> pkpv, seed; |
1468 | |
|
1469 | 0 | auto dec = BER_Decoder(sk) |
1470 | 0 | .start_sequence() |
1471 | 0 | .decode_and_check<size_t>(0, "kyber private key does have a version other than 0") |
1472 | 0 | .decode(z, ASN1_Type::OctetString) |
1473 | 0 | .decode(skpv, ASN1_Type::OctetString); |
1474 | |
|
1475 | 0 | try |
1476 | 0 | { |
1477 | 0 | dec.start_sequence().decode(pkpv, ASN1_Type::OctetString).decode(seed, ASN1_Type::OctetString).end_cons(); |
1478 | 0 | } |
1479 | 0 | catch(const BER_Decoding_Error&) |
1480 | 0 | { |
1481 | 0 | throw Invalid_Argument("reading private key without an embedded public key is not supported"); |
1482 | 0 | } |
1483 | | |
1484 | | // skipping the public key hash |
1485 | 0 | dec.discard_remaining().end_cons(); |
1486 | |
|
1487 | 0 | if(skpv.size() != mode.polynomial_vector_byte_length()) |
1488 | 0 | { |
1489 | 0 | throw Invalid_Argument("kyber private key sample-param does not have the correct byte count"); |
1490 | 0 | } |
1491 | | |
1492 | 0 | if(z.size() != KyberConstants::kZLength) |
1493 | 0 | { |
1494 | 0 | throw Invalid_Argument("kyber private key z-param does not have the correct byte count"); |
1495 | 0 | } |
1496 | | |
1497 | 0 | m_public = std::make_shared<Kyber_PublicKeyInternal>(m, std::move(pkpv), std::move(seed)); |
1498 | 0 | m_private = std::make_shared<Kyber_PrivateKeyInternal>(std::move(mode), |
1499 | 0 | PolynomialVector::from_bytes(skpv, mode), std::move(z)); |
1500 | 0 | } |
1501 | 0 | else if(encoding == KyberKeyEncoding::Raw) |
1502 | 0 | { |
1503 | 0 | if(mode.private_key_byte_length() != sk.size()) |
1504 | 0 | { |
1505 | 0 | throw Invalid_Argument("kyber private key does not have the correct byte count"); |
1506 | 0 | } |
1507 | | |
1508 | 0 | const auto off_pub_key = mode.polynomial_vector_byte_length(); |
1509 | 0 | const auto pub_key_len = mode.public_key_byte_length(); |
1510 | |
|
1511 | 0 | auto skpv = secure_vector<uint8_t>(sk.begin(), sk.begin() + off_pub_key); |
1512 | 0 | auto pub_key = std::vector<uint8_t>(sk.begin() + off_pub_key, sk.begin() + off_pub_key + pub_key_len); |
1513 | | // skipping the public key hash |
1514 | 0 | auto z = secure_vector<uint8_t>(sk.end() - KyberConstants::kZLength, sk.end()); |
1515 | |
|
1516 | 0 | initialize_from_encoding(pub_key, m, encoding); |
1517 | 0 | m_private = std::make_shared<Kyber_PrivateKeyInternal>(std::move(mode), |
1518 | 0 | PolynomialVector::from_bytes(skpv, mode), std::move(z)); |
1519 | 0 | } |
1520 | | |
1521 | 0 | BOTAN_ASSERT(m_private && m_public, "reading private key encoding"); |
1522 | 0 | } Unexecuted instantiation: Botan::Kyber_PrivateKey::Kyber_PrivateKey(std::__1::vector<unsigned char, Botan::secure_allocator<unsigned char> > const&, Botan::KyberMode, Botan::KyberKeyEncoding) Unexecuted instantiation: Botan::Kyber_PrivateKey::Kyber_PrivateKey(std::__1::vector<unsigned char, Botan::secure_allocator<unsigned char> > const&, Botan::KyberMode, Botan::KyberKeyEncoding) |
1523 | | |
1524 | | std::unique_ptr<Public_Key> Kyber_PrivateKey::public_key() const |
1525 | 0 | { |
1526 | 0 | auto public_key = std::make_unique<Kyber_PublicKey>(*this); |
1527 | 0 | public_key->set_binary_encoding(binary_encoding()); |
1528 | 0 | return public_key; |
1529 | 0 | } |
1530 | | |
1531 | | secure_vector<uint8_t> Kyber_PrivateKey::private_key_bits() const |
1532 | 0 | { |
1533 | 0 | switch(m_key_encoding) |
1534 | 0 | { |
1535 | 0 | case KyberKeyEncoding::Full: |
1536 | 0 | return private_key_bits_der(); |
1537 | 0 | case KyberKeyEncoding::Raw: |
1538 | 0 | return private_key_bits_raw(); |
1539 | 0 | } |
1540 | | |
1541 | 0 | unreachable(); |
1542 | 0 | } |
1543 | | |
1544 | | secure_vector<uint8_t> Kyber_PrivateKey::private_key_bits_raw() const |
1545 | 0 | { |
1546 | 0 | const auto pub_key = public_key_bits_raw(); |
1547 | 0 | const auto pub_key_sv = secure_vector<uint8_t>(pub_key.begin(), pub_key.end()); |
1548 | 0 | const auto pub_key_hash = m_private->mode().H()->process(pub_key); |
1549 | |
|
1550 | 0 | return concat(m_private->polynomials().to_bytes<secure_vector<uint8_t>>(), |
1551 | 0 | pub_key_sv, pub_key_hash, |
1552 | 0 | m_private->z()); |
1553 | 0 | } |
1554 | | |
1555 | | secure_vector<uint8_t> Kyber_PrivateKey::private_key_bits_der() const |
1556 | 0 | { |
1557 | 0 | secure_vector<uint8_t> output; |
1558 | 0 | DER_Encoder der(output); |
1559 | |
|
1560 | 0 | const auto pub_key = public_key_bits_der(); |
1561 | 0 | const auto pub_key_hash = m_private->mode().H()->process(pub_key); |
1562 | |
|
1563 | 0 | der.start_sequence() |
1564 | 0 | .encode(size_t(0), ASN1_Type::Integer, ASN1_Class::Universal) |
1565 | 0 | .encode(m_private->z(), ASN1_Type::OctetString) |
1566 | 0 | .encode(m_private->polynomials().to_bytes<secure_vector<uint8_t>>(), ASN1_Type::OctetString) |
1567 | 0 | .raw_bytes(pub_key) |
1568 | 0 | .encode(pub_key_hash, ASN1_Type::OctetString) |
1569 | 0 | .end_cons(); |
1570 | |
|
1571 | 0 | return output; |
1572 | 0 | } |
1573 | | |
1574 | | std::unique_ptr<PK_Ops::KEM_Encryption> Kyber_PublicKey::create_kem_encryption_op(RandomNumberGenerator& rng, |
1575 | | const std::string& params, |
1576 | | const std::string& provider) const |
1577 | 0 | { |
1578 | 0 | BOTAN_UNUSED(rng); |
1579 | 0 | if(provider.empty() || provider == "base") |
1580 | 0 | return std::make_unique<Kyber_KEM_Encryptor>(*this, params); |
1581 | 0 | throw Provider_Not_Found(algo_name(), provider); |
1582 | 0 | } |
1583 | | |
1584 | | std::unique_ptr<PK_Ops::KEM_Decryption> Kyber_PrivateKey::create_kem_decryption_op(RandomNumberGenerator& rng, |
1585 | | const std::string& params, |
1586 | | const std::string& provider) const |
1587 | 0 | { |
1588 | 0 | BOTAN_UNUSED(rng); |
1589 | 0 | if(provider.empty() || provider == "base") |
1590 | 0 | return std::make_unique<Kyber_KEM_Decryptor>(*this, params); |
1591 | 0 | throw Provider_Not_Found(algo_name(), provider); |
1592 | 0 | } |
1593 | | |
1594 | | } // namespace Botan |