/src/botan/src/lib/pubkey/kyber/kyber_common/kyber_algos.cpp

Source (jump to first uncovered line)
/*
 * Crystals Kyber Internal Algorithms
 * Based on the public domain reference implementation by the
 * designers (https://github.com/pq-crystals/kyber)
 *
 * Further changes
 * (C) 2021-2024 Jack Lloyd
 * (C) 2021-2022 Manuel Glaser and Michael Boric, Rohde & Schwarz Cybersecurity
 * (C) 2021-2022 René Meusel and Hannes Rantzsch, neXenio GmbH
 * (C) 2024 René Meusel, Rohde & Schwarz Cybersecurity
 *
 * Botan is released under the Simplified BSD License (see license.txt)
 */

#include <botan/internal/kyber_algos.h>

#include <botan/internal/kyber_helpers.h>
#include <botan/internal/kyber_keys.h>
#include <botan/internal/loadstor.h>
#include <botan/internal/pqcrystals_encoding.h>
#include <botan/internal/pqcrystals_helpers.h>

#include <utility>

namespace Botan::Kyber_Algos {

namespace {

/**
 * NIST FIPS 203, Algorithm 5 (ByteEncode) for d < 12 in combination with
 * Formula 4.7 (Compress)
 */
template <size_t d>
   requires(d < 12)
void poly_compress_and_encode(BufferStuffer& bs, const KyberPoly& p) {
   CRYSTALS::pack<(1 << d) - 1>(p, bs, compress<d>);
}

/**
 * NIST FIPS 203, Algorithm 5 (ByteEncode) for d == 12
 */
void byte_encode(BufferStuffer& bs, const KyberPolyNTT& p) {
   CRYSTALS::pack<KyberConstants::Q - 1>(p, bs);
}

/**
 * NIST FIPS 203, Algorithm 6 (ByteDecode) for d < 12 in combination with
 * Formula 4.8 (Decompress)
 */
template <size_t d>
   requires(d < 12)
void poly_decode_and_decompress(KyberPoly& p, BufferSlicer& bs) {
   CRYSTALS::unpack<(1 << d) - 1>(p, bs, decompress<d>);
}

/**
 * NIST FIPS 203, Algorithm 6 (ByteDecode) for d == 12
 */
void byte_decode(KyberPolyNTT& p, BufferSlicer& bs) {
   CRYSTALS::unpack<KyberConstants::Q - 1>(p, bs);

   if(!p.ct_validate_value_range(0, KyberConstants::Q - 1)) {
      throw Decoding_Error("Decoded polynomial coefficients out of range");
   }
}

/**
 * NIST FIPS 203, Algorithm 7 (SampleNTT)
 *
 * Note that this assumes that the XOF has been initialized with the correct
 * seed + two bytes of indices prior to invoking this function.
 * See sample_matrix() below.
 */
void sample_ntt_uniform(KyberPolyNTT& p, XOF& xof) {
   // A generator that returns the next coefficient sampled from the XOF. As the
   // sampling uses half-bytes, this keeps track of the additionally sampled
   // coefficient as needed.
   auto sample = [stashed_coeff = std::optional<uint16_t>{},
                  bounded_xof =
                     Bounded_XOF<KyberConstants::SAMPLE_NTT_POLY_FROM_XOF_BOUND>(xof)]() mutable -> uint16_t {
      auto lowerthan_q = [](uint32_t d) -> std::optional<uint16_t> {
         if(d < KyberConstants::Q) {
            return static_cast<uint16_t>(d);
         } else {
            return std::nullopt;
         }
      };

      if(auto stashed = std::exchange(stashed_coeff, std::nullopt)) {
         return *stashed;  // value retained from a previous invocation
      }

      while(true) {
         const auto [d1, d2] = bounded_xof.next<3>([&](const auto bytes) {
            const auto x = load_le3(bytes);
            return std::pair{lowerthan_q(x & 0x0FFF), lowerthan_q(x >> 12)};
         });

         if(d1.has_value()) {
            stashed_coeff = d2;  // keep candidate d2 for the next invocation
            return *d1;
         } else if(d2.has_value()) {
            // d1 was invalid, d2 is valid, nothing to stash
            return *d2;
         }
      }
   };

   for(auto& coeff : p) {
      coeff = sample();
   }
}

/**
 * NIST FIPS 203, Algorithm 8 (SamplePolyCBD)
 *
 * Implementations for eta = 2 and eta = 3 are provided separately as template
 * specializations below.
 */
template <KyberConstants::KyberEta eta>
void sample_poly_cbd(KyberPoly& poly, StrongSpan<const KyberSamplingRandomness> randomness);

/**
 * NIST FIPS 203, Algorithm 8 (SamplePolyCBD) for eta = 2
 */
template <>
void sample_poly_cbd<KyberConstants::KyberEta::_2>(KyberPoly& poly,
                                                   StrongSpan<const KyberSamplingRandomness> randomness) {
   BufferSlicer bs(randomness);

   for(size_t i = 0; i < poly.size() / 8; ++i) {
      const uint32_t t = Botan::load_le(bs.take<4>());

      // SWAR (SIMD within a Register) trick: calculate 16 2-bit-sums in parallel
      constexpr uint32_t operand_bitmask = 0b01010101010101010101010101010101;

      // clang-format off
      const uint32_t d = ((t >> 0) & operand_bitmask) +
                         ((t >> 1) & operand_bitmask);
      // clang-format on

      for(size_t j = 0; j < 8; ++j) {
         const int16_t a = (d >> (4 * j + 0)) & 0x3;
         const int16_t b = (d >> (4 * j + 2)) & 0x3;
         poly[8 * i + j] = a - b;
      }
   }

   BOTAN_ASSERT_NOMSG(bs.empty());
}

/**
 * NIST FIPS 203, Algorithm 8 (SamplePolyCBD) for eta = 3
 */
template <>
void sample_poly_cbd<KyberConstants::KyberEta::_3>(KyberPoly& poly,
                                                   StrongSpan<const KyberSamplingRandomness> randomness) {
   BufferSlicer bs(randomness);

   for(size_t i = 0; i < poly.size() / 4; ++i) {
      const uint32_t t = load_le3(bs.take<3>());

      // SWAR (SIMD within a Register) trick: calculate 8 3-bit-sums in parallel
      constexpr uint32_t operand_bitmask = 0b00000000001001001001001001001001;

      // clang-format off
      const uint32_t d = ((t >> 0) & operand_bitmask) +
                         ((t >> 1) & operand_bitmask) +
                         ((t >> 2) & operand_bitmask);
      // clang-format on

      for(size_t j = 0; j < 4; ++j) {
         const int16_t a = (d >> (6 * j + 0)) & 0x7;
         const int16_t b = (d >> (6 * j + 3)) & 0x7;
         poly[4 * i + j] = a - b;
      }
   }

   BOTAN_ASSERT_NOMSG(bs.empty());
}

}  // namespace

void encode_polynomial_vector(std::span<uint8_t> out, const KyberPolyVecNTT& vec) {
   BufferStuffer bs(out);
   for(auto& v : vec) {
      byte_encode(bs, v);
   }
   BOTAN_ASSERT_NOMSG(bs.full());
}

KyberPolyVecNTT decode_polynomial_vector(std::span<const uint8_t> a, const KyberConstants& mode) {
   KyberPolyVecNTT vec(mode.k());

   BufferSlicer bs(a);
   for(auto& p : vec) {
      byte_decode(p, bs);
   }
   BOTAN_ASSERT_NOMSG(bs.empty());

   return vec;
}

KyberPoly polynomial_from_message(StrongSpan<const KyberMessage> msg) {
   BOTAN_ASSERT(msg.size() == KyberConstants::N / 8, "message length must be N/8 bytes");
   KyberPoly r;
   BufferSlicer bs(msg);
   poly_decode_and_decompress<1>(r, bs);
   return r;
}

KyberMessage polynomial_to_message(const KyberPoly& p) {
   KyberMessage result(p.size() / 8);
   BufferStuffer bs(result);
   poly_compress_and_encode<1>(bs, p);
   return result;
}

namespace {

template <size_t d>
void polyvec_compress_and_encode(BufferStuffer& sink, const KyberPolyVec& polyvec) {
   for(const auto& p : polyvec) {
      poly_compress_and_encode<d>(sink, p);
   }
}

void compress_polyvec(std::span<uint8_t> out, const KyberPolyVec& pv, const KyberConstants& mode) {
   BufferStuffer bs(out);

   switch(mode.d_u()) {
      case KyberConstants::KyberDu::_10:
         polyvec_compress_and_encode<10>(bs, pv);
         BOTAN_ASSERT_NOMSG(bs.full());
         return;
      case KyberConstants::KyberDu::_11:
         polyvec_compress_and_encode<11>(bs, pv);
         BOTAN_ASSERT_NOMSG(bs.full());
         return;
   }

   BOTAN_ASSERT_UNREACHABLE();
}

void compress_poly(std::span<uint8_t> out, const KyberPoly& p, const KyberConstants& mode) {
   BufferStuffer bs(out);

   switch(mode.d_v()) {
      case KyberConstants::KyberDv::_4:
         poly_compress_and_encode<4>(bs, p);
         BOTAN_ASSERT_NOMSG(bs.full());
         return;
      case KyberConstants::KyberDv::_5:
         poly_compress_and_encode<5>(bs, p);
         BOTAN_ASSERT_NOMSG(bs.full());
         return;
   }

   BOTAN_ASSERT_UNREACHABLE();
}

template <size_t d>
void polyvec_decode_and_decompress(KyberPolyVec& polyvec, BufferSlicer& source) {
   for(auto& p : polyvec) {
      poly_decode_and_decompress<d>(p, source);
   }
}

KyberPolyVec decompress_polynomial_vector(std::span<const uint8_t> buffer, const KyberConstants& mode) {
   BOTAN_ASSERT(buffer.size() == mode.polynomial_vector_compressed_bytes(),
                "unexpected length of compressed polynomial vector");

   KyberPolyVec r(mode.k());
   BufferSlicer bs(buffer);

   switch(mode.d_u()) {
      case KyberConstants::KyberDu::_10:
         polyvec_decode_and_decompress<10>(r, bs);
         BOTAN_ASSERT_NOMSG(bs.empty());
         return r;
      case KyberConstants::KyberDu::_11:
         polyvec_decode_and_decompress<11>(r, bs);
         BOTAN_ASSERT_NOMSG(bs.empty());
         return r;
   }

   BOTAN_ASSERT_UNREACHABLE();
}

KyberPoly decompress_polynomial(std::span<const uint8_t> buffer, const KyberConstants& mode) {
   BOTAN_ASSERT(buffer.size() == mode.polynomial_compressed_bytes(), "unexpected length of compressed polynomial");

   KyberPoly r;
   BufferSlicer bs(buffer);

   switch(mode.d_v()) {
      case KyberConstants::KyberDv::_4:
         poly_decode_and_decompress<4>(r, bs);
         BOTAN_ASSERT_NOMSG(bs.empty());
         return r;
      case KyberConstants::KyberDv::_5:
         poly_decode_and_decompress<5>(r, bs);
         BOTAN_ASSERT_NOMSG(bs.empty());
         return r;
   }

   BOTAN_ASSERT_UNREACHABLE();
}

}  // namespace

/**
 * NIST FIPS 203, Algorithms 16 (ML-KEM.KeyGen_internal), and
 *                           13 (K-PKE.KeyGen)
 *
 * In contrast to the specification, the expansion of rho and sigma is inlined
 * with the actual PKE key generation. The sampling loops spelled out in
 * FIPS 203 are hidden in the sample_* functions. The keys are kept in memory
 * without serialization, which is deferred until requested.
 */
KyberInternalKeypair expand_keypair(KyberPrivateKeySeed seed, KyberConstants mode) {
   BOTAN_ARG_CHECK(seed.d.has_value(), "Cannot expand keypair without the full private seed");
   const auto& d = seed.d.value();

   CT::poison(d);
   auto [rho, sigma] = mode.symmetric_primitives().G(d, mode);
   CT::unpoison(rho);  // rho is public (seed for the public matrix A)

   // Algorithm 13 (K-PKE.KeyGen) ----------------

   auto A = Kyber_Algos::sample_matrix(rho, false /* not transposed */, mode);

   // The nonce N is handled internally by the PolynomialSampler
   Kyber_Algos::PolynomialSampler ps(sigma, mode);
   auto s = ntt(ps.sample_polynomial_vector_cbd_eta1());
   const auto e = ntt(ps.sample_polynomial_vector_cbd_eta1());

   auto t = montgomery(A * s);
   t += e;
   t.reduce();

   // End Algorithm 13 ---------------------------

   CT::unpoison_all(d, t, s);

   return {
      std::make_shared<Kyber_PublicKeyInternal>(mode, std::move(t), std::move(rho)),
      std::make_shared<Kyber_PrivateKeyInternal>(std::move(mode), std::move(s), std::move(seed)),
   };
}

void compress_ciphertext(StrongSpan<KyberCompressedCiphertext> out,
                         const KyberPolyVec& u,
                         const KyberPoly& v,
                         const KyberConstants& m_mode) {
   BufferStuffer bs(out);
   compress_polyvec(bs.next(m_mode.polynomial_vector_compressed_bytes()), u, m_mode);
   compress_poly(bs.next(m_mode.polynomial_compressed_bytes()), v, m_mode);
   BOTAN_ASSERT_NOMSG(bs.full());
}

std::pair<KyberPolyVec, KyberPoly> decompress_ciphertext(StrongSpan<const KyberCompressedCiphertext> ct,
                                                         const KyberConstants& mode) {
   const size_t pvb = mode.polynomial_vector_compressed_bytes();
   const size_t pcb = mode.polynomial_compressed_bytes();

   // FIPS 203, Section 7.3 check 1 "Ciphertext type check"
   if(ct.size() != pvb + pcb) {
      throw Decoding_Error("Kyber: unexpected ciphertext length");
   }

   BufferSlicer bs(ct);
   auto pv = bs.take(pvb);
   auto p = bs.take(pcb);
   BOTAN_ASSERT_NOMSG(bs.empty());

   return {decompress_polynomial_vector(pv, mode), decompress_polynomial(p, mode)};
}

KyberPolyMat sample_matrix(StrongSpan<const KyberSeedRho> seed, bool transposed, const KyberConstants& mode) {
   BOTAN_ASSERT(seed.size() == KyberConstants::SEED_BYTES, "unexpected seed size");

   KyberPolyMat mat(mode.k(), mode.k());

   for(uint8_t i = 0; i < mode.k(); ++i) {
      for(uint8_t j = 0; j < mode.k(); ++j) {
         const auto pos = (transposed) ? std::tuple(i, j) : std::tuple(j, i);
         sample_ntt_uniform(mat[i][j], mode.symmetric_primitives().XOF(seed, pos));
      }
   }

   return mat;
}

/**
 * NIST FIPS 203, Algorithm 8 (SamplePolyCBD)
 *
 * The actual implementation is above. This just dispatches to the correct
 * specialization based on the eta of the chosen mode.
 */
void sample_polynomial_from_cbd(KyberPoly& poly,
                                KyberConstants::KyberEta eta,
                                const KyberSamplingRandomness& randomness) {
   switch(eta) {
      case KyberConstants::KyberEta::_2:
         return sample_poly_cbd<KyberConstants::KyberEta::_2>(poly, randomness);
      case KyberConstants::KyberEta::_3:
         return sample_poly_cbd<KyberConstants::KyberEta::_3>(poly, randomness);
   }

   BOTAN_ASSERT_UNREACHABLE();
}

}  // namespace Botan::Kyber_Algos

Coverage Report

Created: 2025-04-11 06:34

Line	Count	Source (jump to first uncovered line)
1		/*
2		* Crystals Kyber Internal Algorithms
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-2024 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		* (C) 2024 René Meusel, Rohde & Schwarz Cybersecurity
11		*
12		* Botan is released under the Simplified BSD License (see license.txt)
13		*/
14
15		#include <botan/internal/kyber_algos.h>
16
17		#include <botan/internal/kyber_helpers.h>
18		#include <botan/internal/kyber_keys.h>
19		#include <botan/internal/loadstor.h>
20		#include <botan/internal/pqcrystals_encoding.h>
21		#include <botan/internal/pqcrystals_helpers.h>
22
23		#include <utility>
24
25		namespace Botan::Kyber_Algos {
26
27		namespace {
28
29		/**
30		* NIST FIPS 203, Algorithm 5 (ByteEncode) for d < 12 in combination with
31		* Formula 4.7 (Compress)
32		*/
33		template <size_t d>
34		requires(d < 12)
35	0	void poly_compress_and_encode(BufferStuffer& bs, const KyberPoly& p) {
36	0	CRYSTALS::pack<(1 << d) - 1>(p, bs, compress<d>);
37	0	} Unexecuted instantiation: kyber_algos.cpp:_ZN5Botan11Kyber_Algos12_GLOBAL__N_124poly_compress_and_encodeILm10EQltT_Li12EEEvRNS_13BufferStufferERKNS_8CRYSTALS10PolynomialINS_15KyberPolyTraitsELNS5_6DomainE0EEE Unexecuted instantiation: kyber_algos.cpp:_ZN5Botan11Kyber_Algos12_GLOBAL__N_124poly_compress_and_encodeILm11EQltT_Li12EEEvRNS_13BufferStufferERKNS_8CRYSTALS10PolynomialINS_15KyberPolyTraitsELNS5_6DomainE0EEE Unexecuted instantiation: kyber_algos.cpp:_ZN5Botan11Kyber_Algos12_GLOBAL__N_124poly_compress_and_encodeILm4EQltT_Li12EEEvRNS_13BufferStufferERKNS_8CRYSTALS10PolynomialINS_15KyberPolyTraitsELNS5_6DomainE0EEE Unexecuted instantiation: kyber_algos.cpp:_ZN5Botan11Kyber_Algos12_GLOBAL__N_124poly_compress_and_encodeILm5EQltT_Li12EEEvRNS_13BufferStufferERKNS_8CRYSTALS10PolynomialINS_15KyberPolyTraitsELNS5_6DomainE0EEE Unexecuted instantiation: kyber_algos.cpp:_ZN5Botan11Kyber_Algos12_GLOBAL__N_124poly_compress_and_encodeILm1EQltT_Li12EEEvRNS_13BufferStufferERKNS_8CRYSTALS10PolynomialINS_15KyberPolyTraitsELNS5_6DomainE0EEE
38
39		/**
40		* NIST FIPS 203, Algorithm 5 (ByteEncode) for d == 12
41		*/
42	0	void byte_encode(BufferStuffer& bs, const KyberPolyNTT& p) {
43	0	CRYSTALS::pack<KyberConstants::Q - 1>(p, bs);
44	0	}
45
46		/**
47		* NIST FIPS 203, Algorithm 6 (ByteDecode) for d < 12 in combination with
48		* Formula 4.8 (Decompress)
49		*/
50		template <size_t d>
51		requires(d < 12)
52	0	void poly_decode_and_decompress(KyberPoly& p, BufferSlicer& bs) {
53	0	CRYSTALS::unpack<(1 << d) - 1>(p, bs, decompress<d>);
54	0	} Unexecuted instantiation: kyber_algos.cpp:_ZN5Botan11Kyber_Algos12_GLOBAL__N_126poly_decode_and_decompressILm10EQltT_Li12EEEvRNS_8CRYSTALS10PolynomialINS_15KyberPolyTraitsELNS3_6DomainE0EEERNS_12BufferSlicerE Unexecuted instantiation: kyber_algos.cpp:_ZN5Botan11Kyber_Algos12_GLOBAL__N_126poly_decode_and_decompressILm11EQltT_Li12EEEvRNS_8CRYSTALS10PolynomialINS_15KyberPolyTraitsELNS3_6DomainE0EEERNS_12BufferSlicerE Unexecuted instantiation: kyber_algos.cpp:_ZN5Botan11Kyber_Algos12_GLOBAL__N_126poly_decode_and_decompressILm4EQltT_Li12EEEvRNS_8CRYSTALS10PolynomialINS_15KyberPolyTraitsELNS3_6DomainE0EEERNS_12BufferSlicerE Unexecuted instantiation: kyber_algos.cpp:_ZN5Botan11Kyber_Algos12_GLOBAL__N_126poly_decode_and_decompressILm5EQltT_Li12EEEvRNS_8CRYSTALS10PolynomialINS_15KyberPolyTraitsELNS3_6DomainE0EEERNS_12BufferSlicerE Unexecuted instantiation: kyber_algos.cpp:_ZN5Botan11Kyber_Algos12_GLOBAL__N_126poly_decode_and_decompressILm1EQltT_Li12EEEvRNS_8CRYSTALS10PolynomialINS_15KyberPolyTraitsELNS3_6DomainE0EEERNS_12BufferSlicerE
55
56		/**
57		* NIST FIPS 203, Algorithm 6 (ByteDecode) for d == 12
58		*/
59	0	void byte_decode(KyberPolyNTT& p, BufferSlicer& bs) {
60	0	CRYSTALS::unpack<KyberConstants::Q - 1>(p, bs);
61
62	0	if(!p.ct_validate_value_range(0, KyberConstants::Q - 1)) {
63	0	throw Decoding_Error("Decoded polynomial coefficients out of range");
64	0	}
65	0	}
66
67		/**
68		* NIST FIPS 203, Algorithm 7 (SampleNTT)
69		*
70		* Note that this assumes that the XOF has been initialized with the correct
71		* seed + two bytes of indices prior to invoking this function.
72		* See sample_matrix() below.
73		*/
74	0	void sample_ntt_uniform(KyberPolyNTT& p, XOF& xof) {
75		// A generator that returns the next coefficient sampled from the XOF. As the
76		// sampling uses half-bytes, this keeps track of the additionally sampled
77		// coefficient as needed.
78	0	auto sample = [stashed_coeff = std::optional<uint16_t>{},
79	0	bounded_xof =
80	0	Bounded_XOF<KyberConstants::SAMPLE_NTT_POLY_FROM_XOF_BOUND>(xof)]() mutable -> uint16_t {
81	0	auto lowerthan_q = [](uint32_t d) -> std::optional<uint16_t> {
82	0	if(d < KyberConstants::Q) {
83	0	return static_cast<uint16_t>(d);
84	0	} else {
85	0	return std::nullopt;
86	0	}
87	0	};
88
89	0	if(auto stashed = std::exchange(stashed_coeff, std::nullopt)) {
90	0	return *stashed; // value retained from a previous invocation
91	0	}
92
93	0	while(true) {
94	0	const auto [d1, d2] = bounded_xof.next<3>([&](const auto bytes) {
95	0	const auto x = load_le3(bytes);
96	0	return std::pair{lowerthan_q(x & 0x0FFF), lowerthan_q(x >> 12)};
97	0	});
98
99	0	if(d1.has_value()) {
100	0	stashed_coeff = d2; // keep candidate d2 for the next invocation
101	0	return *d1;
102	0	} else if(d2.has_value()) {
103		// d1 was invalid, d2 is valid, nothing to stash
104	0	return *d2;
105	0	}
106	0	}
107	0	};
108
109	0	for(auto& coeff : p) {
110	0	coeff = sample();
111	0	}
112	0	}
113
114		/**
115		* NIST FIPS 203, Algorithm 8 (SamplePolyCBD)
116		*
117		* Implementations for eta = 2 and eta = 3 are provided separately as template
118		* specializations below.
119		*/
120		template <KyberConstants::KyberEta eta>
121		void sample_poly_cbd(KyberPoly& poly, StrongSpan<const KyberSamplingRandomness> randomness);
122
123		/**
124		* NIST FIPS 203, Algorithm 8 (SamplePolyCBD) for eta = 2
125		*/
126		template <>
127		void sample_poly_cbd<KyberConstants::KyberEta::_2>(KyberPoly& poly,
128	0	StrongSpan<const KyberSamplingRandomness> randomness) {
129	0	BufferSlicer bs(randomness);
130
131	0	for(size_t i = 0; i < poly.size() / 8; ++i) {
132	0	const uint32_t t = Botan::load_le(bs.take<4>());
133
134		// SWAR (SIMD within a Register) trick: calculate 16 2-bit-sums in parallel
135	0	constexpr uint32_t operand_bitmask = 0b01010101010101010101010101010101;
136
137		// clang-format off
138	0	const uint32_t d = ((t >> 0) & operand_bitmask) +
139	0	((t >> 1) & operand_bitmask);
140		// clang-format on
141
142	0	for(size_t j = 0; j < 8; ++j) {
143	0	const int16_t a = (d >> (4 * j + 0)) & 0x3;
144	0	const int16_t b = (d >> (4 * j + 2)) & 0x3;
145	0	poly[8 * i + j] = a - b;
146	0	}
147	0	}
148
149	0	BOTAN_ASSERT_NOMSG(bs.empty());
150	0	}
151
152		/**
153		* NIST FIPS 203, Algorithm 8 (SamplePolyCBD) for eta = 3
154		*/
155		template <>
156		void sample_poly_cbd<KyberConstants::KyberEta::_3>(KyberPoly& poly,
157	0	StrongSpan<const KyberSamplingRandomness> randomness) {
158	0	BufferSlicer bs(randomness);
159
160	0	for(size_t i = 0; i < poly.size() / 4; ++i) {
161	0	const uint32_t t = load_le3(bs.take<3>());
162
163		// SWAR (SIMD within a Register) trick: calculate 8 3-bit-sums in parallel
164	0	constexpr uint32_t operand_bitmask = 0b00000000001001001001001001001001;
165
166		// clang-format off
167	0	const uint32_t d = ((t >> 0) & operand_bitmask) +
168	0	((t >> 1) & operand_bitmask) +
169	0	((t >> 2) & operand_bitmask);
170		// clang-format on
171
172	0	for(size_t j = 0; j < 4; ++j) {
173	0	const int16_t a = (d >> (6 * j + 0)) & 0x7;
174	0	const int16_t b = (d >> (6 * j + 3)) & 0x7;
175	0	poly[4 * i + j] = a - b;
176	0	}
177	0	}
178
179	0	BOTAN_ASSERT_NOMSG(bs.empty());
180	0	}
181
182		} // namespace
183
184	0	void encode_polynomial_vector(std::span<uint8_t> out, const KyberPolyVecNTT& vec) {
185	0	BufferStuffer bs(out);
186	0	for(auto& v : vec) {
187	0	byte_encode(bs, v);
188	0	}
189	0	BOTAN_ASSERT_NOMSG(bs.full());
190	0	}
191
192	0	KyberPolyVecNTT decode_polynomial_vector(std::span<const uint8_t> a, const KyberConstants& mode) {
193	0	KyberPolyVecNTT vec(mode.k());
194
195	0	BufferSlicer bs(a);
196	0	for(auto& p : vec) {
197	0	byte_decode(p, bs);
198	0	}
199	0	BOTAN_ASSERT_NOMSG(bs.empty());
200
201	0	return vec;
202	0	}
203
204	0	KyberPoly polynomial_from_message(StrongSpan<const KyberMessage> msg) {
205	0	BOTAN_ASSERT(msg.size() == KyberConstants::N / 8, "message length must be N/8 bytes");
206	0	KyberPoly r;
207	0	BufferSlicer bs(msg);
208	0	poly_decode_and_decompress<1>(r, bs);
209	0	return r;
210	0	}
211
212	0	KyberMessage polynomial_to_message(const KyberPoly& p) {
213	0	KyberMessage result(p.size() / 8);
214	0	BufferStuffer bs(result);
215	0	poly_compress_and_encode<1>(bs, p);
216	0	return result;
217	0	}
218
219		namespace {
220
221		template <size_t d>
222	0	void polyvec_compress_and_encode(BufferStuffer& sink, const KyberPolyVec& polyvec) {
223	0	for(const auto& p : polyvec) {
224	0	poly_compress_and_encode<d>(sink, p);
225	0	}
226	0	} Unexecuted instantiation: kyber_algos.cpp:void Botan::Kyber_Algos::(anonymous namespace)::polyvec_compress_and_encode<10ul>(Botan::BufferStuffer&, Botan::CRYSTALS::PolynomialVector<Botan::KyberPolyTraits, (Botan::CRYSTALS::Domain)0> const&) Unexecuted instantiation: kyber_algos.cpp:void Botan::Kyber_Algos::(anonymous namespace)::polyvec_compress_and_encode<11ul>(Botan::BufferStuffer&, Botan::CRYSTALS::PolynomialVector<Botan::KyberPolyTraits, (Botan::CRYSTALS::Domain)0> const&)
227
228	0	void compress_polyvec(std::span<uint8_t> out, const KyberPolyVec& pv, const KyberConstants& mode) {
229	0	BufferStuffer bs(out);
230
231	0	switch(mode.d_u()) {
232	0	case KyberConstants::KyberDu::_10:
233	0	polyvec_compress_and_encode<10>(bs, pv);
234	0	BOTAN_ASSERT_NOMSG(bs.full());
235	0	return;
236	0	case KyberConstants::KyberDu::_11:
237	0	polyvec_compress_and_encode<11>(bs, pv);
238	0	BOTAN_ASSERT_NOMSG(bs.full());
239	0	return;
240	0	}
241
242	0	BOTAN_ASSERT_UNREACHABLE();
243	0	}
244
245	0	void compress_poly(std::span<uint8_t> out, const KyberPoly& p, const KyberConstants& mode) {
246	0	BufferStuffer bs(out);
247
248	0	switch(mode.d_v()) {
249	0	case KyberConstants::KyberDv::_4:
250	0	poly_compress_and_encode<4>(bs, p);
251	0	BOTAN_ASSERT_NOMSG(bs.full());
252	0	return;
253	0	case KyberConstants::KyberDv::_5:
254	0	poly_compress_and_encode<5>(bs, p);
255	0	BOTAN_ASSERT_NOMSG(bs.full());
256	0	return;
257	0	}
258
259	0	BOTAN_ASSERT_UNREACHABLE();
260	0	}
261
262		template <size_t d>
263	0	void polyvec_decode_and_decompress(KyberPolyVec& polyvec, BufferSlicer& source) {
264	0	for(auto& p : polyvec) {
265	0	poly_decode_and_decompress<d>(p, source);
266	0	}
267	0	} Unexecuted instantiation: kyber_algos.cpp:void Botan::Kyber_Algos::(anonymous namespace)::polyvec_decode_and_decompress<10ul>(Botan::CRYSTALS::PolynomialVector<Botan::KyberPolyTraits, (Botan::CRYSTALS::Domain)0>&, Botan::BufferSlicer&) Unexecuted instantiation: kyber_algos.cpp:void Botan::Kyber_Algos::(anonymous namespace)::polyvec_decode_and_decompress<11ul>(Botan::CRYSTALS::PolynomialVector<Botan::KyberPolyTraits, (Botan::CRYSTALS::Domain)0>&, Botan::BufferSlicer&)
268
269	0	KyberPolyVec decompress_polynomial_vector(std::span<const uint8_t> buffer, const KyberConstants& mode) {
270	0	BOTAN_ASSERT(buffer.size() == mode.polynomial_vector_compressed_bytes(),
271	0	"unexpected length of compressed polynomial vector");
272
273	0	KyberPolyVec r(mode.k());
274	0	BufferSlicer bs(buffer);
275
276	0	switch(mode.d_u()) {
277	0	case KyberConstants::KyberDu::_10:
278	0	polyvec_decode_and_decompress<10>(r, bs);
279	0	BOTAN_ASSERT_NOMSG(bs.empty());
280	0	return r;
281	0	case KyberConstants::KyberDu::_11:
282	0	polyvec_decode_and_decompress<11>(r, bs);
283	0	BOTAN_ASSERT_NOMSG(bs.empty());
284	0	return r;
285	0	}
286
287	0	BOTAN_ASSERT_UNREACHABLE();
288	0	}
289
290	0	KyberPoly decompress_polynomial(std::span<const uint8_t> buffer, const KyberConstants& mode) {
291	0	BOTAN_ASSERT(buffer.size() == mode.polynomial_compressed_bytes(), "unexpected length of compressed polynomial");
292
293	0	KyberPoly r;
294	0	BufferSlicer bs(buffer);
295
296	0	switch(mode.d_v()) {
297	0	case KyberConstants::KyberDv::_4:
298	0	poly_decode_and_decompress<4>(r, bs);
299	0	BOTAN_ASSERT_NOMSG(bs.empty());
300	0	return r;
301	0	case KyberConstants::KyberDv::_5:
302	0	poly_decode_and_decompress<5>(r, bs);
303	0	BOTAN_ASSERT_NOMSG(bs.empty());
304	0	return r;
305	0	}
306
307	0	BOTAN_ASSERT_UNREACHABLE();
308	0	}
309
310		} // namespace
311
312		/**
313		* NIST FIPS 203, Algorithms 16 (ML-KEM.KeyGen_internal), and
314		* 13 (K-PKE.KeyGen)
315		*
316		* In contrast to the specification, the expansion of rho and sigma is inlined
317		* with the actual PKE key generation. The sampling loops spelled out in
318		* FIPS 203 are hidden in the sample_* functions. The keys are kept in memory
319		* without serialization, which is deferred until requested.
320		*/
321	0	KyberInternalKeypair expand_keypair(KyberPrivateKeySeed seed, KyberConstants mode) {
322	0	BOTAN_ARG_CHECK(seed.d.has_value(), "Cannot expand keypair without the full private seed");
323	0	const auto& d = seed.d.value();
324
325	0	CT::poison(d);
326	0	auto [rho, sigma] = mode.symmetric_primitives().G(d, mode);
327	0	CT::unpoison(rho); // rho is public (seed for the public matrix A)
328
329		// Algorithm 13 (K-PKE.KeyGen) ----------------
330
331	0	auto A = Kyber_Algos::sample_matrix(rho, false /* not transposed */, mode);
332
333		// The nonce N is handled internally by the PolynomialSampler
334	0	Kyber_Algos::PolynomialSampler ps(sigma, mode);
335	0	auto s = ntt(ps.sample_polynomial_vector_cbd_eta1());
336	0	const auto e = ntt(ps.sample_polynomial_vector_cbd_eta1());
337
338	0	auto t = montgomery(A * s);
339	0	t += e;
340	0	t.reduce();
341
342		// End Algorithm 13 ---------------------------
343
344	0	CT::unpoison_all(d, t, s);
345
346	0	return {
347	0	std::make_shared<Kyber_PublicKeyInternal>(mode, std::move(t), std::move(rho)),
348	0	std::make_shared<Kyber_PrivateKeyInternal>(std::move(mode), std::move(s), std::move(seed)),
349	0	};
350	0	}
351
352		void compress_ciphertext(StrongSpan<KyberCompressedCiphertext> out,
353		const KyberPolyVec& u,
354		const KyberPoly& v,
355	0	const KyberConstants& m_mode) {
356	0	BufferStuffer bs(out);
357	0	compress_polyvec(bs.next(m_mode.polynomial_vector_compressed_bytes()), u, m_mode);
358	0	compress_poly(bs.next(m_mode.polynomial_compressed_bytes()), v, m_mode);
359	0	BOTAN_ASSERT_NOMSG(bs.full());
360	0	}
361
362		std::pair<KyberPolyVec, KyberPoly> decompress_ciphertext(StrongSpan<const KyberCompressedCiphertext> ct,
363	0	const KyberConstants& mode) {
364	0	const size_t pvb = mode.polynomial_vector_compressed_bytes();
365	0	const size_t pcb = mode.polynomial_compressed_bytes();
366
367		// FIPS 203, Section 7.3 check 1 "Ciphertext type check"
368	0	if(ct.size() != pvb + pcb) {
369	0	throw Decoding_Error("Kyber: unexpected ciphertext length");
370	0	}
371
372	0	BufferSlicer bs(ct);
373	0	auto pv = bs.take(pvb);
374	0	auto p = bs.take(pcb);
375	0	BOTAN_ASSERT_NOMSG(bs.empty());
376
377	0	return {decompress_polynomial_vector(pv, mode), decompress_polynomial(p, mode)};
378	0	}
379
380	0	KyberPolyMat sample_matrix(StrongSpan<const KyberSeedRho> seed, bool transposed, const KyberConstants& mode) {
381	0	BOTAN_ASSERT(seed.size() == KyberConstants::SEED_BYTES, "unexpected seed size");
382
383	0	KyberPolyMat mat(mode.k(), mode.k());
384
385	0	for(uint8_t i = 0; i < mode.k(); ++i) {
386	0	for(uint8_t j = 0; j < mode.k(); ++j) {
387	0	const auto pos = (transposed) ? std::tuple(i, j) : std::tuple(j, i);
388	0	sample_ntt_uniform(mat[i][j], mode.symmetric_primitives().XOF(seed, pos));
389	0	}
390	0	}
391
392	0	return mat;
393	0	}
394
395		/**
396		* NIST FIPS 203, Algorithm 8 (SamplePolyCBD)
397		*
398		* The actual implementation is above. This just dispatches to the correct
399		* specialization based on the eta of the chosen mode.
400		*/
401		void sample_polynomial_from_cbd(KyberPoly& poly,
402		KyberConstants::KyberEta eta,
403	0	const KyberSamplingRandomness& randomness) {
404	0	switch(eta) {
405	0	case KyberConstants::KyberEta::_2:
406	0	return sample_poly_cbd<KyberConstants::KyberEta::_2>(poly, randomness);
407	0	case KyberConstants::KyberEta::_3:
408	0	return sample_poly_cbd<KyberConstants::KyberEta::_3>(poly, randomness);
409	0	}
410
411	0	BOTAN_ASSERT_UNREACHABLE();
412	0	}
413
414		} // namespace Botan::Kyber_Algos