14#include <botan/kyber.h>
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>
22#include <botan/secmem.h>
23#include <botan/stream_cipher.h>
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>
32#if defined(BOTAN_HAS_KYBER)
33 #include <botan/internal/kyber_modern.h>
36#if defined(BOTAN_HAS_KYBER_90S)
37 #include <botan/internal/kyber_90s.h>
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")
67 throw Invalid_Argument(
fmt(
"'{}' is not a valid Kyber mode name", str));
76 : m_mode(kyber_mode_from_string(oid.to_formatted_string())) {}
79 : m_mode(kyber_mode_from_string(str)) {}
91 return "Kyber-512-90s-r3";
93 return "Kyber-768-90s-r3";
95 return "Kyber-1024-90s-r3";
97 return "Kyber-512-r3";
99 return "Kyber-768-r3";
101 return "Kyber-1024-r3";
112 static constexpr size_t N = 256;
113 static constexpr size_t Q = 3329;
114 static constexpr size_t Q_Inv = 62209;
116 static constexpr int16_t zetas[128] =
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
128 static constexpr int16_t zetas_inv[128] =
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
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;
147 KyberConstants(
const KyberMode mode) : m_mode(mode)
153 m_nist_strength = 128;
160 m_nist_strength = 192;
167 m_nist_strength = 256;
173#ifdef BOTAN_HAS_KYBER_90S
176 m_symmetric_primitives = std::make_unique<Kyber_90s_Symmetric_Primitives>();
179#ifdef BOTAN_HAS_KYBER
182 m_symmetric_primitives = std::make_unique<Kyber_Modern_Symmetric_Primitives>();
186 if(!m_symmetric_primitives)
188 throw Not_Implemented(
"requested Kyber mode is not enabled in this build");
192 ~KyberConstants() =
default;
194 KyberConstants(
const KyberConstants& other) : KyberConstants(other.m_mode)
198 KyberConstants(KyberConstants&& other) =
default;
199 KyberConstants& operator=(
const KyberConstants& other) =
delete;
200 KyberConstants& operator=(KyberConstants&& other) =
default;
202 KyberMode mode()
const
207 size_t estimated_strength()
const
209 return m_nist_strength;
227 size_t polynomial_vector_byte_length()
const
229 return kSerializedPolynomialByteLength * k();
232 size_t public_key_byte_length()
const
234 return polynomial_vector_byte_length() + kSeedLength;
237 size_t private_key_byte_length()
const
239 return polynomial_vector_byte_length() + public_key_byte_length() + kPublicKeyHashLength + kZLength;
242 std::unique_ptr<HashFunction> G()
const
244 return m_symmetric_primitives->G();
246 std::unique_ptr<HashFunction> H()
const
248 return m_symmetric_primitives->H();
250 std::unique_ptr<HashFunction> KDF()
const
252 return m_symmetric_primitives->KDF();
255 std::unique_ptr<Kyber_XOF> XOF(std::span<const uint8_t> seed)
const
257 return m_symmetric_primitives->XOF(seed);
260 secure_vector<uint8_t> PRF(std::span<const uint8_t> seed,
const uint8_t nonce,
const size_t outlen)
const
262 return m_symmetric_primitives->PRF(seed, nonce, outlen);
267 std::unique_ptr<Kyber_Symmetric_Primitives> m_symmetric_primitives;
268 size_t m_nist_strength;
281 for(
auto& coeff : m_coeffs)
283 coeff -= KyberConstants::Q;
284 coeff += (coeff >> 15) & KyberConstants::Q;
293 for(
auto& c : m_coeffs)
294 { c = barrett_reduce(c); }
297 template <
typename T = std::vector<u
int8_t>>
T to_bytes()
301 T r(KyberConstants::kSerializedPolynomialByteLength);
303 for(
size_t i = 0; i < size() / 2; ++i)
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);
319 static Polynomial cbd2(std::span<const uint8_t> buf)
323 BOTAN_ASSERT(buf.size() == (2 * r.size() / 4),
"wrong input buffer size for cbd2");
325 for(
size_t i = 0; i < r.size() / 8; ++i)
328 uint32_t d = t & 0x55555555;
329 d += (t >> 1) & 0x55555555;
331 for(
size_t j = 0; j < 8; ++j)
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;
348 static Polynomial cbd3(std::span<const uint8_t> buf)
352 BOTAN_ASSERT(buf.size() == (3 * r.size() / 4),
"wrong input buffer size for cbd3");
355 const auto load_le24 = [](
const uint8_t in[],
const size_t off)
357 const auto off3 = off * 3;
358 return make_uint32(0, in[off3 + 2], in[off3 + 1], in[off3]);
361 for(
size_t i = 0; i < r.size() / 4; ++i)
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;
368 for(
size_t j = 0; j < 4; ++j)
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;
382 static Polynomial getnoise_eta2(std::span<const uint8_t> seed, uint8_t nonce,
const KyberConstants& mode)
384 const auto eta2 = mode.eta2();
387 const auto outlen = eta2 * KyberConstants::N / 4;
388 return Polynomial::cbd2(mode.PRF(seed, nonce, outlen));
395 static Polynomial getnoise_eta1(std::span<const uint8_t> seed, uint8_t nonce,
const KyberConstants& mode)
397 const auto eta1 = mode.eta1();
398 BOTAN_ASSERT(eta1 == 2 || eta1 == 3,
"Invalid eta1 value");
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));
405 static Polynomial from_bytes(std::span<const uint8_t> a)
408 for(
size_t i = 0; i < r.size() / 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;
418 static Polynomial from_message(std::span<const uint8_t> msg)
420 BOTAN_ASSERT(msg.size() == KyberConstants::N / 8,
"message length must be Kyber_N/8 bytes");
423 for(
size_t i = 0; i < r.size() / 8; ++i)
425 for(
size_t j = 0; j < 8; ++j)
427 const auto mask = -
static_cast<int16_t
>((msg[i] >> j) & 1);
428 r.m_coeffs[8 * i + j] = mask & ((KyberConstants::Q + 1) / 2);
434 template <
typename T = secure_vector<u
int8_t>>
T to_message()
436 T result(size() / 8);
440 for(
size_t i = 0; i < size() / 8; ++i)
443 for(
size_t j = 0; j < 8; ++j)
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;
457 Polynomial&
operator+=(
const Polynomial& other)
459 for(
size_t i = 0; i < this->size(); ++i)
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];
471 Polynomial& operator-=(
const Polynomial& other)
473 for(
size_t i = 0; i < this->size(); ++i)
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];
484 static Polynomial basemul_montgomery(
const Polynomial& a,
const Polynomial& b)
490 auto basemul = [](int16_t r[2],
const int16_t s[2],
const int16_t t[2],
const int16_t zeta)
492 r[0] = fqmul(s[1], t[1]);
493 r[0] = fqmul(r[0], zeta);
494 r[0] += fqmul(s[0], t[0]);
496 r[1] = fqmul(s[0], t[1]);
497 r[1] += fqmul(s[1], t[0]);
502 for(
size_t i = 0; i < r.size() / 4; ++i)
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]);
516 static Polynomial sample_rej_uniform(Kyber_XOF& xof)
521 XOF_Reader(Kyber_XOF& xof) :
524 m_buf_pos(m_buf.size())
528 std::array<uint8_t, 3> next_3_bytes()
530 if(m_buf_pos == m_buf.size())
532 m_xof.write_output(m_buf);
538 std::array<uint8_t, 3> buf{
550 std::array<uint8_t, 3 * 64> m_buf;
554 auto xof_reader = XOF_Reader(xof);
558 while(count < p.size())
560 auto buf = xof_reader.next_3_bytes();
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;
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; }
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); }
591 for(
size_t len = size() / 2, k = 0; len >= 2; len /= 2)
593 for(
size_t start = 0, j = 0; start < size(); start = j + len)
595 const auto zeta = KyberConstants::zetas[++k];
596 for(j = start; j < start + len; ++j)
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;
614 for(
size_t len = 2, k = 0; len <= size() / 2; len *= 2)
616 for(
size_t start = 0, j = 0; start < size(); start = j + len)
618 const auto zeta = KyberConstants::zetas_inv[k++];
619 for(j = start; j < start + len; ++j)
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]);
628 for(
auto& c : m_coeffs)
629 { c = fqmul(c, KyberConstants::zetas_inv[127]); }
632 size_t size()
const {
return m_coeffs.size(); }
634 int16_t operator[](
size_t idx)
const
636 return m_coeffs[idx];
639 int16_t& operator[](
size_t idx)
641 return m_coeffs[idx];
649 static int16_t barrett_reduce(int16_t a)
652 const int16_t v = ((1U << 26) + KyberConstants::Q / 2) / KyberConstants::Q;
654 t =
static_cast<int32_t
>(v) * a >> 26;
655 t *= KyberConstants::Q;
662 static int16_t fqmul(int16_t a, int16_t b)
664 return montgomery_reduce(
static_cast<int32_t
>(a) * b);
671 static int16_t montgomery_reduce(int32_t a)
673 const int16_t u =
static_cast<int16_t
>(a * KyberConstants::Q_Inv);
674 int32_t t =
static_cast<int32_t
>(u) * KyberConstants::Q;
677 return static_cast<int16_t
>(t);
680 std::array<int16_t, KyberConstants::N> m_coeffs;
683class PolynomialVector
686 PolynomialVector() =
delete;
687 explicit PolynomialVector(
const size_t k) : m_vec(k)
691 static PolynomialVector from_bytes(std::span<const uint8_t> a,
const KyberConstants& mode)
693 BOTAN_ASSERT(a.size() == mode.polynomial_vector_byte_length(),
"wrong byte length for frombytes");
695 PolynomialVector r(mode.k());
696 for(
size_t i = 0; i < mode.k(); ++i)
698 r.m_vec[i] = Polynomial::from_bytes(a.subspan(0, KyberConstants::kSerializedPolynomialByteLength));
699 a = a.subspan(KyberConstants::kSerializedPolynomialByteLength);
707 static Polynomial pointwise_acc_montgomery(
const PolynomialVector& a,
const PolynomialVector& b)
709 BOTAN_ASSERT(a.m_vec.size() == b.m_vec.size(),
"pointwise_acc_montgomery works on equally sized "
710 "PolynomialVectors only");
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)
715 r += Polynomial::basemul_montgomery(a.m_vec[i], b.m_vec[i]);
722 static PolynomialVector getnoise_eta2(std::span<const uint8_t> seed, uint8_t nonce,
const KyberConstants& mode)
724 PolynomialVector r(mode.k());
726 for(
auto& p : r.m_vec)
728 p = Polynomial::getnoise_eta2(seed, nonce++, mode);
734 static PolynomialVector getnoise_eta1(std::span<const uint8_t> seed, uint8_t nonce,
const KyberConstants& mode)
736 PolynomialVector r(mode.k());
738 for(
auto& p : r.m_vec)
740 p = Polynomial::getnoise_eta1(seed, nonce++, mode);
746 template <
typename T = std::vector<u
int8_t>>
T to_bytes()
750 r.reserve(m_vec.size() * KyberConstants::kSerializedPolynomialByteLength);
753 const auto poly = v.to_bytes<
T>();
754 r.insert(r.end(), poly.begin(), poly.end());
772 PolynomialVector&
operator+=(
const PolynomialVector& other)
774 BOTAN_ASSERT(m_vec.size() == other.m_vec.size(),
"cannot add polynomial vectors of differing lengths");
776 for(
size_t i = 0; i < m_vec.size(); ++i)
777 { m_vec[i] += other.m_vec[i]; }
781 Polynomial& operator[](
size_t idx)
801 { v.invntt_tomont(); }
814 std::vector<Polynomial> m_vec;
817class PolynomialMatrix
820 PolynomialMatrix() =
delete;
822 static PolynomialMatrix generate(std::span<const uint8_t> seed,
const bool transposed,
823 const KyberConstants& mode)
825 BOTAN_ASSERT(seed.size() == KyberConstants::kSymBytes,
"unexpected seed size");
827 PolynomialMatrix matrix(mode);
829 auto xof = mode.XOF(seed);
831 for(uint8_t i = 0; i < mode.k(); ++i)
833 for(uint8_t j = 0; j < mode.k(); ++j)
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);
844 PolynomialVector pointwise_acc_montgomery(
const PolynomialVector& vec,
const bool with_mont =
false)
const
846 PolynomialVector result(m_mat.size());
848 for(
size_t i = 0; i < m_mat.size(); ++i)
850 result[i] = PolynomialVector::pointwise_acc_montgomery(m_mat[i], vec);
861 explicit PolynomialMatrix(
const KyberConstants& mode) : m_mat(mode.k(), PolynomialVector(mode.k()))
866 std::vector<PolynomialVector> m_mat;
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)
878 static Ciphertext from_bytes(std::span<const uint8_t> buffer,
const KyberConstants& mode)
880 const size_t pvb = polynomial_vector_compressed_bytes(mode);
881 const size_t pcb = polynomial_compressed_bytes(mode);
883 if(buffer.size() != pvb + pcb)
885 throw Decoding_Error(
"Kyber: unexpected ciphertext length");
888 auto pv = buffer.subspan(0, pvb);
889 auto p = buffer.subspan(pvb);
891 return Ciphertext(decompress_polynomial_vector(pv, mode), decompress_polynomial(p, mode), mode);
894 secure_vector<uint8_t> to_bytes()
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());
903 secure_vector<uint8_t> indcpa_decrypt(
const PolynomialVector& polynomials)
906 auto mp = PolynomialVector::pointwise_acc_montgomery(polynomials, m_b);
911 return mp.to_message();
915 static size_t polynomial_vector_compressed_bytes(
const KyberConstants& mode)
917 const auto k = mode.k();
918 return (k == 2 || k == 3) ? k * 320 : k * 352;
921 static size_t polynomial_compressed_bytes(
const KyberConstants& mode)
923 const auto k = mode.k();
924 return (k == 2 || k == 3) ? 128 : 160;
927 static secure_vector<uint8_t> compress(PolynomialVector& pv,
const KyberConstants& mode)
929 secure_vector<uint8_t> r(polynomial_vector_compressed_bytes(mode));
933 if(mode.k() == 2 || mode.k() == 3)
937 for(
size_t i = 0; i < mode.k(); ++i)
939 for(
size_t j = 0; j < KyberConstants::N / 4; ++j)
941 for(
size_t k = 0; k < 4; ++k)
943 (((
static_cast<uint32_t
>(pv[i][4 * j + k]) << 10) + KyberConstants::Q / 2) /
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);
960 for(
size_t i = 0; i < mode.k(); ++i)
962 for(
size_t j = 0; j < KyberConstants::N / 8; ++j)
964 for(
size_t k = 0; k < 8; ++k)
966 (((
static_cast<uint32_t
>(pv[i][8 * j + k]) << 11) + KyberConstants::Q / 2) /
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);
989 static secure_vector<uint8_t> compress(Polynomial& p,
const KyberConstants& mode)
991 secure_vector<uint8_t> r(polynomial_compressed_bytes(mode));
996 if(mode.k() == 2 || mode.k() == 3)
999 for(
size_t i = 0; i < p.size() / 8; ++i)
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) &
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);
1013 else if(mode.k() == 4)
1016 for(
size_t i = 0; i < p.size() / 8; ++i)
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) &
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);
1035 static PolynomialVector decompress_polynomial_vector(std::span<const uint8_t> buffer,
1036 const KyberConstants& mode)
1038 BOTAN_ASSERT(buffer.size() == polynomial_vector_compressed_bytes(mode),
1039 "unexpected length of compressed polynomial vector");
1041 PolynomialVector r(mode.k());
1042 const uint8_t* a = buffer.data();
1047 for(
size_t i = 0; i < mode.k(); ++i)
1049 for(
size_t j = 0; j < KyberConstants::N / 8; ++j)
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);
1061 for(
size_t k = 0; k < 8; ++k)
1063 (
static_cast<uint32_t
>(t[k] & 0x7FF) * KyberConstants::Q + 1024) >> 11;
1070 for(
size_t i = 0; i < mode.k(); ++i)
1072 for(
size_t j = 0; j < KyberConstants::N / 4; ++j)
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);
1080 for(
size_t k = 0; k < 4; ++k)
1082 (
static_cast<uint32_t
>(t[k] & 0x3FF) * KyberConstants::Q + 512) >> 10;
1090 static Polynomial decompress_polynomial(std::span<const uint8_t> buffer,
const KyberConstants& mode)
1092 BOTAN_ASSERT(buffer.size() == polynomial_compressed_bytes(mode),
"unexpected length of compressed polynomial");
1095 const uint8_t* a = buffer.data();
1100 for(
size_t i = 0; i < KyberConstants::N / 8; ++i)
1103 t[1] = (a[0] >> 5) | (a[1] << 3);
1105 t[3] = (a[1] >> 7) | (a[2] << 1);
1106 t[4] = (a[2] >> 4) | (a[3] << 4);
1108 t[6] = (a[3] >> 6) | (a[4] << 2);
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; }
1118 for(
size_t i = 0; i < KyberConstants::N / 2; ++i)
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;
1130 KyberConstants m_mode;
1131 PolynomialVector m_b;
1137class Kyber_PublicKeyInternal
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))
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))
1160 const PolynomialVector& polynomials()
const
1162 return m_polynomials;
1165 const std::vector<uint8_t>& seed()
const
1169 const KyberConstants& mode()
const
1174 const std::vector<uint8_t>& public_key_bits_raw()
const
1176 return m_public_key_bits_raw;
1179 const std::vector<uint8_t>& H_public_key_bits_raw()
const
1181 return m_H_public_key_bits_raw;
1184 Kyber_PublicKeyInternal() =
delete;
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;
1194class Kyber_PrivateKeyInternal
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))
1202 PolynomialVector& polynomials()
1204 return m_polynomials;
1207 const secure_vector<uint8_t>& z()
const
1212 const KyberConstants& mode()
const
1217 Kyber_PrivateKeyInternal() =
delete;
1220 KyberConstants m_mode;
1221 PolynomialVector m_polynomials;
1222 secure_vector<uint8_t> m_z;
1225class Kyber_KEM_Cryptor
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))
1235 secure_vector<uint8_t> indcpa_enc(std::span<const uint8_t> m,
1236 std::span<const uint8_t> coins)
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);
1242 auto k = Polynomial::from_message(m);
1247 auto bp = m_at.pointwise_acc_montgomery(sp);
1248 auto v = PolynomialVector::pointwise_acc_montgomery(m_public_key->polynomials(), sp);
1259 return Ciphertext(std::move(bp), v, m_mode).to_bytes();
1262 const KyberConstants& mode()
const {
return m_mode; }
1265 std::shared_ptr<const Kyber_PublicKeyInternal> m_public_key;
1266 const KyberConstants& m_mode;
1267 const PolynomialMatrix m_at;
1270class Kyber_KEM_Encryptor
final :
public PK_Ops::KEM_Encryption_with_KDF,
1271 protected Kyber_KEM_Cryptor
1274 Kyber_KEM_Encryptor(
const Kyber_PublicKey& key, std::string_view kdf)
1276 , Kyber_KEM_Cryptor(key.m_public)
1281 size_t raw_kem_shared_key_length()
const override
1286 size_t encapsulated_key_length()
const override
1288 const size_t key_length = m_key.key_length();
1302 void raw_kem_encrypt(secure_vector<uint8_t>& out_encapsulated_key,
1303 secure_vector<uint8_t>& out_shared_key,
1304 RandomNumberGenerator& rng)
override
1307 auto H = mode().H();
1308 auto G = mode().G();
1309 auto KDF = mode().KDF();
1311 H->update(rng.random_vec(KyberConstants::kSymBytes));
1312 const auto shared_secret = H->final();
1315 G->update(shared_secret);
1316 G->update(m_key.H_public_key_bits_raw());
1317 const auto g_out = G->final();
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);
1324 out_encapsulated_key = indcpa_enc(shared_secret, upper_g_out);
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();
1332 const Kyber_PublicKey& m_key;
1335class Kyber_KEM_Decryptor
final :
public PK_Ops::KEM_Decryption_with_KDF,
1336 protected Kyber_KEM_Cryptor
1339 Kyber_KEM_Decryptor(
const Kyber_PrivateKey& key, std::string_view kdf)
1341 , Kyber_KEM_Cryptor(key.m_public)
1346 size_t raw_kem_shared_key_length()
const override
1351 secure_vector<uint8_t> raw_kem_decrypt(
const uint8_t encap_key[],
size_t len_encap_key)
override
1354 auto H = mode().H();
1355 auto G = mode().G();
1356 auto KDF = mode().KDF();
1358 const auto shared_secret = indcpa_dec(encap_key, len_encap_key);
1361 G->update(shared_secret);
1362 G->update(m_key.H_public_key_bits_raw());
1364 const auto g_out = G->final();
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);
1371 H->update(encap_key, len_encap_key);
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");
1377 secure_vector<uint8_t> lower_g_out_final(lower_g_out.size());
1381 lower_g_out.data(), m_key.m_private->z().data(),
1382 lower_g_out_final.size());
1384 KDF->update(lower_g_out_final);
1385 KDF->update(H->final());
1387 return KDF->final();
1391 secure_vector<uint8_t> indcpa_dec(
const uint8_t c[],
size_t c_len)
1393 auto ct = Ciphertext::from_bytes(std::span(c, c_len), mode());
1394 return ct.indcpa_decrypt(m_key.m_private->polynomials());
1398 const Kyber_PrivateKey& m_key;
1423 return m_public->mode().estimated_strength();
1426std::shared_ptr<Kyber_PublicKeyInternal>
1429 KyberConstants
mode(m);
1431 if(pub_key.size() !=
mode.public_key_byte_length())
1433 throw Invalid_Argument(
"kyber public key does not have the correct byte count");
1438 auto poly_vec = s.
take(
mode.polynomial_vector_byte_length());
1439 auto seed = s.
take_vector(KyberConstants::kSeedLength);
1442 return std::make_shared<Kyber_PublicKeyInternal>(std::move(
mode), poly_vec, std::move(seed));
1446 std::span<const uint8_t> key_bits)
1451 : m_public(initialize_from_encoding(pub_key, m))
1455 : m_public(
std::make_shared<Kyber_PublicKeyInternal>(*other.m_public))
1465 return m_public->public_key_bits_raw();
1470 return m_public->H_public_key_bits_raw();
1475 return m_public->mode().public_key_byte_length();
1485 KyberConstants
mode(m);
1488 auto seed = G->process(rng.
random_vec(KyberConstants::kSymBytes));
1490 const auto middle = G->output_length() / 2;
1494 auto seed2 = s.
take(middle);
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);
1505 auto pkpv = a.pointwise_acc_montgomery(skpv,
true);
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),
1515 std::span<const uint8_t> key_bits) :
1520 KyberConstants
mode(m);
1522 if(
mode.private_key_byte_length() != sk.size())
1524 throw Invalid_Argument(
"kyber private key does not have the correct byte count");
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);
1537 m_private = std::make_shared<Kyber_PrivateKeyInternal>(std::move(
mode), std::move(skpv), std::move(z));
1544 return std::make_unique<Kyber_PublicKey>(*
this);
1560std::unique_ptr<PK_Ops::KEM_Encryption>
1562 std::string_view params,
1563 std::string_view provider)
const
1565 if(provider.empty() || provider ==
"base")
1566 return std::make_unique<Kyber_KEM_Encryptor>(*
this, params);
1571 std::string_view params,
1572 std::string_view provider)
const
1575 if(provider.empty() || provider ==
"base")
1576 return std::make_unique<Kyber_KEM_Decryptor>(*
this, params);
#define BOTAN_ASSERT_NOMSG(expr)
#define BOTAN_DEBUG_ASSERT(expr)
#define BOTAN_UNUSED(...)
#define BOTAN_ASSERT_EQUAL(expr1, expr2, assertion_made)
#define BOTAN_ASSERT(expr, assertion_made)
auto take_secure_vector(const size_t count)
void skip(const size_t count)
auto take_vector(const size_t count)
std::span< const uint8_t > take(const size_t count)
std::string to_string() const
OID object_identifier() const
std::unique_ptr< PK_Ops::KEM_Decryption > create_kem_decryption_op(RandomNumberGenerator &rng, std::string_view params, std::string_view provider) const override
std::unique_ptr< Public_Key > public_key() const override
Kyber_PrivateKey(RandomNumberGenerator &rng, KyberMode mode)
secure_vector< uint8_t > raw_private_key_bits() const override
secure_vector< uint8_t > private_key_bits() const override
static std::shared_ptr< Kyber_PublicKeyInternal > initialize_from_encoding(std::span< const uint8_t > pub_key, KyberMode m)
std::vector< uint8_t > public_key_bits() const override
bool check_key(RandomNumberGenerator &, bool) const override
std::string algo_name() const override
std::shared_ptr< Kyber_PublicKeyInternal > m_public
size_t key_length() const override
AlgorithmIdentifier algorithm_identifier() const override
const std::vector< uint8_t > & H_public_key_bits_raw() const
std::unique_ptr< PK_Ops::KEM_Encryption > create_kem_encryption_op(std::string_view params, std::string_view provider) const override
const std::vector< uint8_t > & public_key_bits_raw() const
OID object_identifier() const override
size_t estimated_strength() const override
std::string to_formatted_string() const
static OID from_string(std::string_view str)
KEM_Decryption_with_KDF(std::string_view kdf)
KEM_Encryption_with_KDF(std::string_view kdf)
void random_vec(std::span< uint8_t > v)
int(* final)(unsigned char *, CTX *)
Mask< T > conditional_copy_mem(T cnd, T *to, const T *from0, const T *from1, size_t elems)
constexpr uint32_t load_le< uint32_t >(const uint8_t in[], size_t off)
std::string fmt(std::string_view format, const T &... args)
constexpr uint32_t make_uint32(uint8_t i0, uint8_t i1, uint8_t i2, uint8_t i3)
bool constant_time_compare(const uint8_t x[], const uint8_t y[], size_t len)
std::vector< T, Alloc > & operator+=(std::vector< T, Alloc > &out, const std::vector< T, Alloc2 > &in)
BOTAN_FORCE_INLINE void unreachable()
decltype(auto) concat(Ts &&...buffers)
std::vector< T, secure_allocator< T > > secure_vector