15#include <botan/internal/kyber_algos.h>
17#include <botan/internal/buffer_slicer.h>
18#include <botan/internal/buffer_stuffer.h>
19#include <botan/internal/kyber_helpers.h>
20#include <botan/internal/kyber_keys.h>
21#include <botan/internal/loadstor.h>
22#include <botan/internal/pqcrystals_encoding.h>
23#include <botan/internal/pqcrystals_helpers.h>
65 throw Decoding_Error(
"Decoded polynomial coefficients out of range");
80 auto sample = [stashed_coeff = std::optional<uint16_t>{},
83 auto lowerthan_q = [](uint32_t d) -> std::optional<uint16_t> {
85 return static_cast<uint16_t
>(d);
91 if(
auto stashed = std::exchange(stashed_coeff, std::nullopt)) {
96 const auto [d1, d2] = bounded_xof.next<3>([&](
const auto bytes) {
98 return std::pair{lowerthan_q(x & 0x0FFF), lowerthan_q(x >> 12)};
104 }
else if(d2.has_value()) {
111 for(
auto& coeff : p) {
120bool sample_ntt_uniform_from_buffer(
KyberPolyNTT& p, std::span<const uint8_t> buf) {
121 auto sample = [in = buf, stashed_coeff = std::optional<uint16_t>{}]()
mutable -> std::optional<uint16_t> {
122 const auto lowerthan_q = [](uint32_t d) -> std::optional<uint16_t> {
124 return static_cast<uint16_t
>(d);
130 if(
auto stashed = std::exchange(stashed_coeff, std::nullopt)) {
134 while(in.size() >= 3) {
135 const auto x =
load_le3(in.first<3>());
138 const auto d1 = lowerthan_q(x & 0x0FFF);
139 const auto d2 = lowerthan_q(x >> 12);
144 }
else if(d2.has_value()) {
153 for(
auto& coeff : p) {
154 if(
auto c = sample()) {
170template <KyberConstants::KyberEta eta>
177void sample_poly_cbd<KyberConstants::KyberEta::_2>(
KyberPoly& poly,
181 for(
size_t i = 0; i < poly.
size() / 8; ++i) {
185 constexpr uint32_t operand_bitmask = 0b01010101010101010101010101010101;
188 const uint32_t d = ((t >> 0) & operand_bitmask) +
189 ((t >> 1) & operand_bitmask);
192 for(
size_t j = 0; j < 8; ++j) {
193 const int16_t a = (d >> (4 * j + 0)) & 0x3;
194 const int16_t b = (d >> (4 * j + 2)) & 0x3;
195 poly[8 * i + j] = a - b;
206void sample_poly_cbd<KyberConstants::KyberEta::_3>(
KyberPoly& poly,
210 for(
size_t i = 0; i < poly.
size() / 4; ++i) {
214 constexpr uint32_t operand_bitmask = 0b00000000001001001001001001001001;
217 const uint32_t d = ((t >> 0) & operand_bitmask) +
218 ((t >> 1) & operand_bitmask) +
219 ((t >> 2) & operand_bitmask);
222 for(
size_t j = 0; j < 4; ++j) {
223 const int16_t a = (d >> (6 * j + 0)) & 0x7;
224 const int16_t b = (d >> (6 * j + 3)) & 0x7;
225 poly[4 * i + j] = a - b;
236 for(
const auto& v : vec) {
258 poly_decode_and_decompress<1>(r, bs);
265 poly_compress_and_encode<1>(bs, p);
273 for(
const auto& p : polyvec) {
274 poly_compress_and_encode<d>(sink, p);
278void compress_polyvec(std::span<uint8_t> out,
const KyberPolyVec& pv,
const KyberConstants& mode) {
279 BufferStuffer bs(out);
283 polyvec_compress_and_encode<10>(bs, pv);
287 polyvec_compress_and_encode<11>(bs, pv);
295void compress_poly(std::span<uint8_t> out,
const KyberPoly& p,
const KyberConstants& mode) {
296 BufferStuffer bs(out);
300 poly_compress_and_encode<4>(bs, p);
304 poly_compress_and_encode<5>(bs, p);
313void polyvec_decode_and_decompress(
KyberPolyVec& polyvec, BufferSlicer& source) {
314 for(
auto& p : polyvec) {
315 poly_decode_and_decompress<d>(p, source);
319KyberPolyVec decompress_polynomial_vector(std::span<const uint8_t> buffer,
const KyberConstants& mode) {
320 BOTAN_ASSERT(buffer.size() == mode.polynomial_vector_compressed_bytes(),
321 "unexpected length of compressed polynomial vector");
324 BufferSlicer bs(buffer);
328 polyvec_decode_and_decompress<10>(r, bs);
332 polyvec_decode_and_decompress<11>(r, bs);
340KyberPoly decompress_polynomial(std::span<const uint8_t> buffer,
const KyberConstants& mode) {
341 BOTAN_ASSERT(buffer.size() == mode.polynomial_compressed_bytes(),
"unexpected length of compressed polynomial");
344 BufferSlicer bs(buffer);
348 poly_decode_and_decompress<4>(r, bs);
352 poly_decode_and_decompress<5>(r, bs);
372 BOTAN_ARG_CHECK(seed.
d.has_value(),
"Cannot expand keypair without the full private seed");
373 const auto& d = seed.
d.value();
386 auto s = ntt(std::move(s_std));
387 const auto e = ntt(std::move(e_std));
389 auto t = montgomery(A * s);
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)),
424 if(ct.
size() != pvb + pcb) {
429 const auto pv = bs.
take(pvb);
430 const auto p = bs.
take(pcb);
433 return {decompress_polynomial_vector(pv, mode), decompress_polynomial(p, mode)};
445 constexpr size_t buffered_bytes = 3 * 168;
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);
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));
461 sym.XOF_batch(outputs, seed, positions);
463 std::unique_ptr<Botan::XOF> xof;
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);
488 return sample_poly_cbd<KyberConstants::KyberEta::_2>(poly, randomness);
490 return sample_poly_cbd<KyberConstants::KyberEta::_3>(poly, randomness);
#define BOTAN_ASSERT_NOMSG(expr)
#define BOTAN_ARG_CHECK(expr, msg)
#define BOTAN_ASSERT(expr, assertion_made)
#define BOTAN_ASSERT_UNREACHABLE()
std::span< const uint8_t > take(const size_t count)
Helper class to ease in-place marshalling of concatenated fixed-length values.
constexpr std::span< uint8_t > next(size_t bytes)
constexpr bool full() const
constexpr size_t size() const
size_t polynomial_vector_compressed_bytes() const
byte length of an encoded compressed polynomial vector
static constexpr T N
number of coefficients in a polynomial
size_t polynomial_compressed_bytes() const
byte length of an encoded compressed polynomial
static constexpr T Q
modulus
static constexpr size_t SEED_BYTES
Kyber_Symmetric_Primitives & symmetric_primitives() const
std::pair< KyberPolyVec, KyberPolyVec > sample_polynomial_vector_pair_cbd_eta1()
Samples two polynomial vectors in a single PRF batch.
std::pair< KyberSeedRho, KyberSeedSigma > G(StrongSpan< const KyberSeedRandomness > seed, const KyberConstants &mode) const
decltype(auto) size() const noexcept(noexcept(this->m_span.size()))
constexpr void unpack(Polynomial< PolyTrait, D > &p, ByteSourceT &byte_source, UnmapFnT unmap)
constexpr void pack(const Polynomial< PolyTrait, D > &p, BufferStuffer &stuffer, MapFnT map)
constexpr void unpoison_all(const Ts &... ts)
constexpr void unpoison(const T *p, size_t n)
constexpr void poison(const T *p, size_t n)
void encode_polynomial_vector(std::span< uint8_t > out, const KyberPolyVecNTT &vec)
KyberMessage polynomial_to_message(const KyberPoly &p)
KyberPolyMat sample_matrix(StrongSpan< const KyberSeedRho > seed, bool transposed, const KyberConstants &mode)
constexpr std::make_unsigned_t< KyberConstants::T > compress(KyberConstants::T x)
constexpr KyberConstants::T decompress(std::make_unsigned_t< KyberConstants::T > x)
uint32_t load_le3(std::span< const uint8_t, 3 > in)
void compress_ciphertext(StrongSpan< KyberCompressedCiphertext > out, const KyberPolyVec &u, const KyberPoly &v, const KyberConstants &m_mode)
KyberInternalKeypair expand_keypair(KyberPrivateKeySeed seed, KyberConstants mode)
KyberPoly polynomial_from_message(StrongSpan< const KyberMessage > msg)
void sample_polynomial_from_cbd(KyberPoly &poly, KyberConstants::KyberEta eta, StrongSpan< const KyberSamplingRandomness > randomness)
std::pair< KyberPolyVec, KyberPoly > decompress_ciphertext(StrongSpan< const KyberCompressedCiphertext > ct, const KyberConstants &mode)
KyberPolyVecNTT decode_polynomial_vector(std::span< const uint8_t > a, const KyberConstants &mode)
Strong< secure_vector< uint8_t >, struct KyberMessage_ > KyberMessage
Random message value to be encrypted by the CPA-secure Kyber encryption scheme.
Botan::CRYSTALS::Polynomial< KyberPolyTraits, Botan::CRYSTALS::Domain::Normal > KyberPoly
detail::Bounded_XOF< XOF &, bound > Bounded_XOF
Botan::CRYSTALS::PolynomialVector< KyberPolyTraits, Botan::CRYSTALS::Domain::NTT > KyberPolyVecNTT
Botan::CRYSTALS::Polynomial< KyberPolyTraits, Botan::CRYSTALS::Domain::NTT > KyberPolyNTT
BOTAN_FORCE_INLINE constexpr T rho(T x)
BOTAN_FORCE_INLINE constexpr T sigma(T x)
constexpr auto load_le(ParamTs &&... params)
std::pair< std::shared_ptr< const Kyber_PublicKeyInternal >, std::shared_ptr< const Kyber_PrivateKeyInternal > > KyberInternalKeypair
Botan::CRYSTALS::PolynomialMatrix< KyberPolyTraits > KyberPolyMat
Botan::CRYSTALS::PolynomialVector< KyberPolyTraits, Botan::CRYSTALS::Domain::Normal > KyberPolyVec
std::optional< KyberSeedRandomness > d