Botan 3.14.1
Crypto and TLS for C&
Botan::Kyber_Algos Namespace Reference

Classes

class  PolynomialSampler

Functions

template<size_t d>
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>
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, StrongSpan< const KyberSamplingRandomness > randomness)

Function Documentation

◆ compress()

template<size_t d>
std::make_unsigned_t< KyberConstants::T > Botan::Kyber_Algos::compress ( KyberConstants::T x)
constexpr

NIST FIPS 203, Formula 4.7 (Compress)

Definition at line 32 of file kyber_helpers.h.

32 {
34 const uint32_t n = (static_cast<uint32_t>(x) << d) + KyberConstants::Q / 2;
35
36 // This is a mitigation for a potential side channel called "KyberSlash".
37 //
38 // It implements the division by Q using a multiplication and a shift. Most
39 // compilers would generate similar code for such a division by a constant.
40 // Though, in some cases, compilers might use a variable-time int division,
41 // resulting in a potential side channel.
42 //
43 // The constants below work for all values that appear in Kyber with the
44 // greatest being 3328 * 2^11 + Q // 2 = 6,817,408 < 2**23 = 8,388,608.
45 //
46 // See "Hacker's Delight" (Second Edition) by Henry S. Warren, Jr.
47 // Chapter 10-9 "Unsigned Division by Divisors >= 1"
48 BOTAN_DEBUG_ASSERT(n < (1 << 23));
49 static_assert(KyberConstants::Q == 3329);
50 using unsigned_T = std::make_unsigned_t<KyberConstants::T>;
51
52 constexpr uint64_t m = 2580335;
53 constexpr size_t p = 33;
54 constexpr unsigned_T mask = (1 << d) - 1;
55 return static_cast<unsigned_T>((n * m) >> p) & mask;
56}
#define BOTAN_DEBUG_ASSERT(expr)
Definition assert.h:136
static constexpr T Q
modulus

References BOTAN_DEBUG_ASSERT, and Botan::KyberConstants::Q.

◆ compress_ciphertext()

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

Definition at line 408 of file kyber_algos.cpp.

411 {
412 BufferStuffer bs(out);
413 compress_polyvec(bs.next(m_mode.polynomial_vector_compressed_bytes()), u, m_mode);
414 compress_poly(bs.next(m_mode.polynomial_compressed_bytes()), v, m_mode);
415 BOTAN_ASSERT_NOMSG(bs.full());
416}
#define BOTAN_ASSERT_NOMSG(expr)
Definition assert.h:82
Helper class to ease in-place marshalling of concatenated fixed-length values.
size_t polynomial_vector_compressed_bytes() const
byte length of an encoded compressed polynomial vector
size_t polynomial_compressed_bytes() const
byte length of an encoded compressed polynomial

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

Referenced by 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 242 of file kyber_algos.cpp.

242 {
243 KyberPolyVecNTT vec(mode.k());
244
245 BufferSlicer bs(a);
246 for(auto& p : vec) {
247 byte_decode(p, bs);
248 }
249 BOTAN_ASSERT_NOMSG(bs.empty());
250
251 return vec;
252}
Botan::CRYSTALS::PolynomialVector< KyberPolyTraits, Botan::CRYSTALS::Domain::NTT > KyberPolyVecNTT
Definition kyber_types.h:26

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

Referenced by Botan::Expanded_Keypair_Codec::decode_keypair().

◆ decompress()

template<size_t d>
KyberConstants::T Botan::Kyber_Algos::decompress ( std::make_unsigned_t< KyberConstants::T > x)
constexpr

NIST FIPS 203, Formula 4.8 (Decompress)

Definition at line 63 of file kyber_helpers.h.

63 {
64 BOTAN_DEBUG_ASSERT(x >= 0 && x < (1 << d));
65
66 constexpr uint32_t offset = 1 << (d - 1);
67 constexpr uint32_t mask = (1 << d) - 1;
68
69 const uint32_t xq = CT::value_barrier(static_cast<uint32_t>(x) & mask) * KyberConstants::Q;
70 return static_cast<KyberConstants::T>((xq + offset) >> d);
71}
int16_t T
base data type for most calculations
constexpr T value_barrier(T x)

References BOTAN_DEBUG_ASSERT, Botan::KyberConstants::Q, and Botan::CT::value_barrier().

◆ decompress_ciphertext()

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

Definition at line 418 of file kyber_algos.cpp.

419 {
420 const size_t pvb = mode.polynomial_vector_compressed_bytes();
421 const size_t pcb = mode.polynomial_compressed_bytes();
422
423 // FIPS 203, Section 7.3 check 1 "Ciphertext type check"
424 if(ct.size() != pvb + pcb) {
425 throw Decoding_Error("Kyber: unexpected ciphertext length");
426 }
427
428 BufferSlicer bs(ct);
429 const auto pv = bs.take(pvb);
430 const auto p = bs.take(pcb);
431 BOTAN_ASSERT_NOMSG(bs.empty());
432
433 return {decompress_polynomial_vector(pv, mode), decompress_polynomial(p, mode)};
434}
decltype(auto) size() const noexcept(noexcept(this->m_span.size()))

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

Referenced by 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 51 of file kyber_algos.h.

51 {
52 T r(mode.polynomial_vector_bytes());
54 return r;
55}
size_t polynomial_vector_bytes() const
byte length of an encoded polynomial vector
void encode_polynomial_vector(std::span< uint8_t > out, const KyberPolyVecNTT &vec)

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 234 of file kyber_algos.cpp.

234 {
235 BufferStuffer bs(out);
236 for(const auto& v : vec) {
237 byte_encode(bs, v);
238 }
239 BOTAN_ASSERT_NOMSG(bs.full());
240}

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

Referenced by Botan::Expanded_Keypair_Codec::encode_keypair(), 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 371 of file kyber_algos.cpp.

371 {
372 BOTAN_ARG_CHECK(seed.d.has_value(), "Cannot expand keypair without the full private seed");
373 const auto& d = seed.d.value();
374
375 CT::poison(d);
376 auto [rho, sigma] = mode.symmetric_primitives().G(d, mode);
377 CT::unpoison(rho); // rho is public (seed for the public matrix A)
378
379 // Algorithm 13 (K-PKE.KeyGen) ----------------
380
381 const auto A = Kyber_Algos::sample_matrix(rho, false /* not transposed */, mode);
382
383 // The nonce N is handled internally by the PolynomialSampler
385 auto [s_std, e_std] = ps.sample_polynomial_vector_pair_cbd_eta1();
386 auto s = ntt(std::move(s_std));
387 const auto e = ntt(std::move(e_std));
388
389 auto t = montgomery(A * s);
390 t += e;
391 t.reduce();
392
393 // Bring s into canonical [0,Q) form (as ByteEncode_12 requires), matching
394 // the representation produced when decoding a private key. This lets the
395 // secret key be serialized directly, without reducing a copy at encode time.
396 s.reduce();
397
398 // End Algorithm 13 ---------------------------
399
400 CT::unpoison_all(d, t, s);
401
402 return {
403 std::make_shared<Kyber_PublicKeyInternal>(mode, std::move(t), std::move(rho)),
404 std::make_shared<Kyber_PrivateKeyInternal>(std::move(mode), std::move(s), std::move(seed)),
405 };
406}
#define BOTAN_ARG_CHECK(expr, msg)
Definition assert.h:33
Kyber_Symmetric_Primitives & symmetric_primitives() const
std::pair< KyberSeedRho, KyberSeedSigma > G(StrongSpan< const KyberSeedRandomness > seed, const KyberConstants &mode) const
constexpr void unpoison_all(const Ts &... ts)
Definition ct_utils.h:207
constexpr void unpoison(const T *p, size_t n)
Definition ct_utils.h:67
constexpr void poison(const T *p, size_t n)
Definition ct_utils.h:56
KyberPolyMat sample_matrix(StrongSpan< const KyberSeedRho > seed, bool transposed, const KyberConstants &mode)
BOTAN_FORCE_INLINE constexpr T rho(T x)
Definition rotate.h:53
BOTAN_FORCE_INLINE constexpr T sigma(T x)
Definition rotate.h:45
std::optional< KyberSeedRandomness > d
Definition kyber_types.h:80

References BOTAN_ARG_CHECK, Botan::KyberPrivateKeySeed::d, Botan::Kyber_Symmetric_Primitives::G(), Botan::CT::poison(), Botan::rho(), sample_matrix(), Botan::Kyber_Algos::PolynomialSampler< SeedT >::sample_polynomial_vector_pair_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(), 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 23 of file kyber_helpers.h.

23 {
24 return Botan::load_le(std::array<uint8_t, 4>{in[0], in[1], in[2], 0});
25}
constexpr auto load_le(ParamTs &&... params)
Definition loadstor.h:495

References Botan::load_le().

◆ polynomial_from_message()

KyberPoly Botan::Kyber_Algos::polynomial_from_message ( StrongSpan< const KyberMessage > msg)

Definition at line 254 of file kyber_algos.cpp.

254 {
255 BOTAN_ASSERT(msg.size() == KyberConstants::N / 8, "message length must be N/8 bytes");
256 KyberPoly r;
257 BufferSlicer bs(msg);
258 poly_decode_and_decompress<1>(r, bs);
259 return r;
260}
#define BOTAN_ASSERT(expr, assertion_made)
Definition assert.h:69
static constexpr T N
number of coefficients in a polynomial
Botan::CRYSTALS::Polynomial< KyberPolyTraits, Botan::CRYSTALS::Domain::Normal > KyberPoly
Definition kyber_types.h:29

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

Referenced by Botan::Kyber_PublicKeyInternal::indcpa_encrypt().

◆ polynomial_to_message()

KyberMessage Botan::Kyber_Algos::polynomial_to_message ( const KyberPoly & p)

Definition at line 262 of file kyber_algos.cpp.

262 {
263 KyberMessage result(p.size() / 8);
264 BufferStuffer bs(result);
265 poly_compress_and_encode<1>(bs, p);
266 return result;
267}
constexpr size_t size() const
Definition pqcrystals.h:278
Strong< secure_vector< uint8_t >, struct KyberMessage_ > KyberMessage
Random message value to be encrypted by the CPA-secure Kyber encryption scheme.
Definition kyber_types.h:45

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

Referenced by Botan::Kyber_PrivateKeyInternal::indcpa_decrypt().

◆ 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 436 of file kyber_algos.cpp.

436 {
437 BOTAN_ASSERT(seed.size() == KyberConstants::SEED_BYTES, "unexpected seed size");
438
439 KyberPolyMat mat(mode.k(), mode.k());
440
441 const auto& sym = mode.symmetric_primitives();
442
443 // Pre-squeeze the XOFs of all matrix entries at once, sized so that
444 // the rejection sampling loop rarely (under 1% of the time) needs more.
445 constexpr size_t buffered_bytes = 3 * 168; // 3 SHAKE-128 blocks
446
447 const size_t lanes = static_cast<size_t>(mode.k()) * mode.k();
448 std::vector<uint8_t> buffer(lanes * buffered_bytes);
449 std::vector<std::tuple<uint8_t, uint8_t>> positions;
450 std::vector<std::span<uint8_t>> outputs;
451 positions.reserve(lanes);
452 outputs.reserve(lanes);
453
454 for(uint8_t i = 0; i < mode.k(); ++i) {
455 for(uint8_t j = 0; j < mode.k(); ++j) {
456 positions.push_back((transposed) ? std::tuple(i, j) : std::tuple(j, i));
457 outputs.push_back(std::span(buffer).subspan(outputs.size() * buffered_bytes, buffered_bytes));
458 }
459 }
460
461 sym.XOF_batch(outputs, seed, positions);
462
463 std::unique_ptr<Botan::XOF> xof;
464 size_t lane = 0;
465 for(uint8_t i = 0; i < mode.k(); ++i) {
466 for(uint8_t j = 0; j < mode.k(); ++j, ++lane) {
467 if(!sample_ntt_uniform_from_buffer(mat[i][j], outputs[lane])) {
468 sym.setup_XOF(xof, seed, positions[lane]);
469 sample_ntt_uniform(mat[i][j], *xof);
470 }
471 }
472 }
473
474 return mat;
475}
static constexpr size_t SEED_BYTES
Botan::CRYSTALS::PolynomialMatrix< KyberPolyTraits > KyberPolyMat
Definition kyber_types.h:27

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

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

◆ sample_polynomial_from_cbd()

void Botan::Kyber_Algos::sample_polynomial_from_cbd ( KyberPoly & poly,
KyberConstants::KyberEta eta,
StrongSpan< 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 483 of file kyber_algos.cpp.

485 {
486 switch(eta) {
488 return sample_poly_cbd<KyberConstants::KyberEta::_2>(poly, randomness);
490 return sample_poly_cbd<KyberConstants::KyberEta::_3>(poly, randomness);
491 }
492
494}
#define BOTAN_ASSERT_UNREACHABLE()
Definition assert.h:173

References Botan::KyberConstants::_2, Botan::KyberConstants::_3, and BOTAN_ASSERT_UNREACHABLE.