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