Botan::Kyber_Algos Namespace Reference

Classes
class	PolynomialSampler

Functions
template<size_t d> requires (d > 0 && d < 12)
constexpr std::make_unsigned_t< KyberConstants::T >	compress (KyberConstants::T x)
void	compress_ciphertext (StrongSpan< KyberCompressedCiphertext > out, const KyberPolyVec &u, const KyberPoly &v, const KyberConstants &m_mode)
KyberPolyVecNTT	decode_polynomial_vector (std::span< const uint8_t > a, const KyberConstants &mode)
template<size_t d> requires (d > 0 && d < 12)
constexpr KyberConstants::T	decompress (std::make_unsigned_t< KyberConstants::T > x)
std::pair< KyberPolyVec, KyberPoly >	decompress_ciphertext (StrongSpan< const KyberCompressedCiphertext > ct, const KyberConstants &mode)
template<concepts::resizable_byte_buffer T = secure_vector<uint8_t>>
T	encode_polynomial_vector (const KyberPolyVecNTT &vec, const KyberConstants &mode)
void	encode_polynomial_vector (std::span< uint8_t > out, const KyberPolyVecNTT &vec)
KyberInternalKeypair	expand_keypair (KyberPrivateKeySeed seed, KyberConstants mode)
uint32_t	load_le3 (std::span< const uint8_t, 3 > in)
KyberPoly	polynomial_from_message (StrongSpan< const KyberMessage > msg)
KyberMessage	polynomial_to_message (const KyberPoly &p)
template<typename T>
	PolynomialSampler (T, const KyberConstants &) -> PolynomialSampler< T >
KyberPolyMat	sample_matrix (StrongSpan< const KyberSeedRho > seed, bool transposed, const KyberConstants &mode)
void	sample_polynomial_from_cbd (KyberPoly &poly, KyberConstants::KyberEta eta, const KyberSamplingRandomness &randomness)

Function Documentation

compress()

template<size_t d>
requires (d > 0 && d < 12)

std::make_unsigned_t< KyberConstants::T > Botan::Kyber_Algos::compress ( KyberConstants::T x )

constexpr

NIST FIPS 203, Formula 4.7 (Compress)

Definition at line 33 of file kyber_helpers.h.

                                                                          {
   BOTAN_DEBUG_ASSERT(x >= 0 && x < KyberConstants::Q);
   const uint32_t n = (static_cast<uint32_t>(x) << d) + KyberConstants::Q / 2;
 
   // This is a mitigation for a potential side channel called "KyberSlash".
   //
   // It implements the division by Q using a multiplication and a shift. Most
   // compilers would generate similar code for such a division by a constant.
   // Though, in some cases, compilers might use a variable-time int division,
   // resulting in a potential side channel.
   //
   // The constants below work for all values that appear in Kyber with the
   // greatest being 3328 * 2^11 + Q // 2 = 6,817,408 < 2**23 = 8,388,608.
   //
   //   See "Hacker's Delight" (Second Edition) by Henry S. Warren, Jr.
   //   Chapter 10-9 "Unsigned Division by Divisors >= 1"
   BOTAN_DEBUG_ASSERT(n < (1 << 23));
   static_assert(KyberConstants::Q == 3329);
   using unsigned_T = std::make_unsigned_t<KyberConstants::T>;
 
   constexpr uint64_t m = 2580335;
   constexpr size_t p = 33;
   constexpr unsigned_T mask = (1 << d) - 1;
   return static_cast<unsigned_T>((n * m) >> p) & mask;
}

References BOTAN_DEBUG_ASSERT, compress(), and Botan::KyberConstants::Q.

Referenced by compress().

compress_ciphertext()

void Botan::Kyber_Algos::compress_ciphertext	(	StrongSpan< KyberCompressedCiphertext >	out,
		const KyberPolyVec &	u,
		const KyberPoly &	v,
		const KyberConstants &	m_mode )

Definition at line 354 of file kyber_algos.cpp.

                                                       {
   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());
}

References BOTAN_ASSERT_NOMSG, compress_ciphertext(), Botan::BufferStuffer::full(), Botan::BufferStuffer::next(), Botan::KyberConstants::polynomial_compressed_bytes(), and Botan::KyberConstants::polynomial_vector_compressed_bytes().

Referenced by compress_ciphertext(), and Botan::Kyber_PublicKeyInternal::indcpa_encrypt().

decode_polynomial_vector()

KyberPolyVecNTT Botan::Kyber_Algos::decode_polynomial_vector	(	std::span< const uint8_t >	a,
		const KyberConstants &	mode )

Definition at line 194 of file kyber_algos.cpp.

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

References BOTAN_ASSERT_NOMSG, decode_polynomial_vector(), Botan::BufferSlicer::empty(), and Botan::KyberConstants::k().

Referenced by Botan::Expanded_Keypair_Codec::decode_keypair(), and decode_polynomial_vector().

decompress()

template<size_t d>
requires (d > 0 && d < 12)

KyberConstants::T Botan::Kyber_Algos::decompress ( std::make_unsigned_t< KyberConstants::T > x )

constexpr

NIST FIPS 203, Formula 4.8 (Decompress)

Definition at line 64 of file kyber_helpers.h.

                                                                            {
   BOTAN_DEBUG_ASSERT(x >= 0 && x < (1 << d));
 
   constexpr uint32_t offset = 1 << (d - 1);
   constexpr uint32_t mask = (1 << d) - 1;
   return static_cast<KyberConstants::T>(((static_cast<uint32_t>(x) & mask) * KyberConstants::Q + offset) >> d);
}

References BOTAN_DEBUG_ASSERT, decompress(), and Botan::KyberConstants::Q.

Referenced by decompress().

decompress_ciphertext()

std::pair< KyberPolyVec, KyberPoly > Botan::Kyber_Algos::decompress_ciphertext	(	StrongSpan< const KyberCompressedCiphertext >	ct,
		const KyberConstants &	mode )

Definition at line 364 of file kyber_algos.cpp.

                                                                                     {
   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)};
}

References BOTAN_ASSERT_NOMSG, Botan::Decoding_Error::Decoding_Error(), decompress_ciphertext(), Botan::BufferSlicer::empty(), Botan::KyberConstants::polynomial_compressed_bytes(), Botan::KyberConstants::polynomial_vector_compressed_bytes(), Botan::StrongSpan< T >::size(), and Botan::BufferSlicer::take().

Referenced by decompress_ciphertext(), and Botan::Kyber_PrivateKeyInternal::indcpa_decrypt().

encode_polynomial_vector() [1/2]

template<concepts::resizable_byte_buffer T = secure_vector<uint8_t>>

T Botan::Kyber_Algos::encode_polynomial_vector	(	const KyberPolyVecNTT &	vec,
		const KyberConstants &	mode )

Definition at line 48 of file kyber_algos.h.

                                                                                   {
   T r(mode.polynomial_vector_bytes());
   encode_polynomial_vector(r, vec);
   return r;
}

References encode_polynomial_vector(), and Botan::KyberConstants::polynomial_vector_bytes().

encode_polynomial_vector() [2/2]

void Botan::Kyber_Algos::encode_polynomial_vector	(	std::span< uint8_t >	out,
		const KyberPolyVecNTT &	vec )

Definition at line 186 of file kyber_algos.cpp.

                                                                                {
   BufferStuffer bs(out);
   for(const auto& v : vec) {
      byte_encode(bs, v);
   }
   BOTAN_ASSERT_NOMSG(bs.full());
}

References BOTAN_ASSERT_NOMSG, encode_polynomial_vector(), and Botan::BufferStuffer::full().

Referenced by Botan::Kyber_PublicKey::check_key(), Botan::Expanded_Keypair_Codec::encode_keypair(), encode_polynomial_vector(), and encode_polynomial_vector().

expand_keypair()

KyberInternalKeypair Botan::Kyber_Algos::expand_keypair	(	KyberPrivateKeySeed	seed,
		KyberConstants	mode )

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.

Definition at line 323 of file kyber_algos.cpp.

                                                                                   {
   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)),
   };
}

References BOTAN_ARG_CHECK, Botan::KyberPrivateKeySeed::d, expand_keypair(), Botan::Kyber_Symmetric_Primitives::G(), Botan::CT::poison(), Botan::rho(), sample_matrix(), Botan::Kyber_Algos::PolynomialSampler< SeedT >::sample_polynomial_vector_cbd_eta1(), Botan::sigma(), Botan::KyberConstants::symmetric_primitives(), Botan::CT::unpoison(), and Botan::CT::unpoison_all().

Referenced by Botan::Seed_Expanding_Keypair_Codec::decode_keypair(), expand_keypair(), and Botan::Kyber_PrivateKey::Kyber_PrivateKey().

load_le3()

uint32_t Botan::Kyber_Algos::load_le3 ( std::span< const uint8_t, 3 > in )

inline

Special load_le<> that takes 3 bytes and returns a 32-bit integer.

Definition at line 24 of file kyber_helpers.h.

                                                       {
   return Botan::load_le(std::array<uint8_t, 4>{in[0], in[1], in[2], 0});
}

References Botan::load_le(), and load_le3().

Referenced by load_le3().

polynomial_from_message()

KyberPoly Botan::Kyber_Algos::polynomial_from_message

(

StrongSpan< const KyberMessage >

msg

)

Definition at line 206 of file kyber_algos.cpp.

                                                                      {
   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;
}

References BOTAN_ASSERT, Botan::KyberConstants::N, polynomial_from_message(), and Botan::StrongSpan< T >::size().

Referenced by Botan::Kyber_PublicKeyInternal::indcpa_encrypt(), and polynomial_from_message().

polynomial_to_message()

KyberMessage Botan::Kyber_Algos::polynomial_to_message

(

const KyberPoly &

p

)

Definition at line 214 of file kyber_algos.cpp.

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

References polynomial_to_message(), and Botan::CRYSTALS::Polynomial< Trait, D >::size().

Referenced by Botan::Kyber_PrivateKeyInternal::indcpa_decrypt(), and polynomial_to_message().

PolynomialSampler()

template<typename T>

Botan::Kyber_Algos::PolynomialSampler	(	T	,
		const KyberConstants &	) -> PolynomialSampler< T >

sample_matrix()

KyberPolyMat Botan::Kyber_Algos::sample_matrix	(	StrongSpan< const KyberSeedRho >	seed,
		bool	transposed,
		const KyberConstants &	mode )

Definition at line 382 of file kyber_algos.cpp.

                                                                                                             {
   BOTAN_ASSERT(seed.size() == KyberConstants::SEED_BYTES, "unexpected seed size");
 
   KyberPolyMat mat(mode.k(), mode.k());
 
   const auto& sym = mode.symmetric_primitives();
   std::unique_ptr<Botan::XOF> xof;
 
   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);
         sym.setup_XOF(xof, seed, pos);
         sample_ntt_uniform(mat[i][j], *xof);
      }
   }
 
   return mat;
}

References BOTAN_ASSERT, Botan::KyberConstants::k(), sample_matrix(), Botan::KyberConstants::SEED_BYTES, Botan::StrongSpan< T >::size(), and Botan::KyberConstants::symmetric_primitives().

Referenced by expand_keypair(), and sample_matrix().

sample_polynomial_from_cbd()

void Botan::Kyber_Algos::sample_polynomial_from_cbd	(	KyberPoly &	poly,
		KyberConstants::KyberEta	eta,
		const KyberSamplingRandomness &	randomness )

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.

Definition at line 407 of file kyber_algos.cpp.

                                                                           {
   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();
}

References Botan::KyberConstants::_2, Botan::KyberConstants::_3, BOTAN_ASSERT_UNREACHABLE, and sample_polynomial_from_cbd().

Referenced by sample_polynomial_from_cbd().