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