Botan 3.14.1
Crypto and TLS for C&
kyber_algos.cpp
Go to the documentation of this file.
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/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>
24
25#include <utility>
26
28
29namespace {
30
31/**
32 * NIST FIPS 203, Algorithm 5 (ByteEncode) for d < 12 in combination with
33 * Formula 4.7 (Compress)
34 */
35template <size_t d>
36 requires(d < 12)
37void poly_compress_and_encode(BufferStuffer& bs, const KyberPoly& p) {
38 CRYSTALS::pack<(1 << d) - 1>(p, bs, compress<d>);
39}
40
41/**
42 * NIST FIPS 203, Algorithm 5 (ByteEncode) for d == 12
43 */
44void byte_encode(BufferStuffer& bs, const KyberPolyNTT& p) {
46}
47
48/**
49 * NIST FIPS 203, Algorithm 6 (ByteDecode) for d < 12 in combination with
50 * Formula 4.8 (Decompress)
51 */
52template <size_t d>
53 requires(d < 12)
54void poly_decode_and_decompress(KyberPoly& p, BufferSlicer& bs) {
55 CRYSTALS::unpack<(1 << d) - 1>(p, bs, decompress<d>);
56}
57
58/**
59 * NIST FIPS 203, Algorithm 6 (ByteDecode) for d == 12
60 */
61void byte_decode(KyberPolyNTT& p, BufferSlicer& bs) {
63
64 if(!p.ct_validate_value_range(0, KyberConstants::Q - 1)) {
65 throw Decoding_Error("Decoded polynomial coefficients out of range");
66 }
67}
68
69/**
70 * NIST FIPS 203, Algorithm 7 (SampleNTT)
71 *
72 * Note that this assumes that the XOF has been initialized with the correct
73 * seed + two bytes of indices prior to invoking this function.
74 * See sample_matrix() below.
75 */
76void sample_ntt_uniform(KyberPolyNTT& p, XOF& xof) {
77 // A generator that returns the next coefficient sampled from the XOF. As the
78 // sampling uses half-bytes, this keeps track of the additionally sampled
79 // coefficient as needed.
80 auto sample = [stashed_coeff = std::optional<uint16_t>{},
81 bounded_xof =
83 auto lowerthan_q = [](uint32_t d) -> std::optional<uint16_t> {
84 if(d < KyberConstants::Q) {
85 return static_cast<uint16_t>(d);
86 } else {
87 return std::nullopt;
88 }
89 };
90
91 if(auto stashed = std::exchange(stashed_coeff, std::nullopt)) {
92 return *stashed; // value retained from a previous invocation
93 }
94
95 while(true) {
96 const auto [d1, d2] = bounded_xof.next<3>([&](const auto bytes) {
97 const auto x = load_le3(bytes);
98 return std::pair{lowerthan_q(x & 0x0FFF), lowerthan_q(x >> 12)};
99 });
100
101 if(d1.has_value()) {
102 stashed_coeff = d2; // keep candidate d2 for the next invocation
103 return *d1;
104 } else if(d2.has_value()) {
105 // d1 was invalid, d2 is valid, nothing to stash
106 return *d2;
107 }
108 }
109 };
110
111 for(auto& coeff : p) {
112 coeff = sample();
113 }
114}
115
116/**
117 * As above, but sampling from a pre-squeezed XOF output buffer. Returns
118 * false if the buffer did not contain enough accepted candidates.
119 */
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> {
123 if(d < KyberConstants::Q) {
124 return static_cast<uint16_t>(d);
125 } else {
126 return std::nullopt;
127 }
128 };
129
130 if(auto stashed = std::exchange(stashed_coeff, std::nullopt)) {
131 return stashed;
132 }
133
134 while(in.size() >= 3) {
135 const auto x = load_le3(in.first<3>());
136 in = in.subspan(3);
137
138 const auto d1 = lowerthan_q(x & 0x0FFF);
139 const auto d2 = lowerthan_q(x >> 12);
140
141 if(d1.has_value()) {
142 stashed_coeff = d2; // keep candidate d2 for the next invocation
143 return d1;
144 } else if(d2.has_value()) {
145 // d1 was invalid, d2 is valid, nothing to stash
146 return d2;
147 }
148 }
149
150 return std::nullopt; // not enough candidates left in the buffer
151 };
152
153 for(auto& coeff : p) {
154 if(auto c = sample()) {
155 coeff = *c;
156 } else {
157 return false; // buffer exhausted before all coefficients could be sampled
158 }
159 }
160
161 return true;
162}
163
164/**
165 * NIST FIPS 203, Algorithm 8 (SamplePolyCBD)
166 *
167 * Implementations for eta = 2 and eta = 3 are provided separately as template
168 * specializations below.
169 */
170template <KyberConstants::KyberEta eta>
171void sample_poly_cbd(KyberPoly& poly, StrongSpan<const KyberSamplingRandomness> randomness);
172
173/**
174 * NIST FIPS 203, Algorithm 8 (SamplePolyCBD) for eta = 2
175 */
176template <>
177void sample_poly_cbd<KyberConstants::KyberEta::_2>(KyberPoly& poly,
179 BufferSlicer bs(randomness);
180
181 for(size_t i = 0; i < poly.size() / 8; ++i) {
182 const uint32_t t = Botan::load_le(bs.take<4>());
183
184 // SWAR (SIMD within a Register) trick: calculate 16 2-bit-sums in parallel
185 constexpr uint32_t operand_bitmask = 0b01010101010101010101010101010101;
186
187 // clang-format off
188 const uint32_t d = ((t >> 0) & operand_bitmask) +
189 ((t >> 1) & operand_bitmask);
190 // clang-format on
191
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;
196 }
197 }
198
200}
201
202/**
203 * NIST FIPS 203, Algorithm 8 (SamplePolyCBD) for eta = 3
204 */
205template <>
206void sample_poly_cbd<KyberConstants::KyberEta::_3>(KyberPoly& poly,
208 BufferSlicer bs(randomness);
209
210 for(size_t i = 0; i < poly.size() / 4; ++i) {
211 const uint32_t t = load_le3(bs.take<3>());
212
213 // SWAR (SIMD within a Register) trick: calculate 8 3-bit-sums in parallel
214 constexpr uint32_t operand_bitmask = 0b00000000001001001001001001001001;
215
216 // clang-format off
217 const uint32_t d = ((t >> 0) & operand_bitmask) +
218 ((t >> 1) & operand_bitmask) +
219 ((t >> 2) & operand_bitmask);
220 // clang-format on
221
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;
226 }
227 }
228
230}
231
232} // namespace
233
234void encode_polynomial_vector(std::span<uint8_t> out, const KyberPolyVecNTT& vec) {
235 BufferStuffer bs(out);
236 for(const auto& v : vec) {
237 byte_encode(bs, v);
238 }
240}
241
242KyberPolyVecNTT decode_polynomial_vector(std::span<const uint8_t> a, const KyberConstants& mode) {
243 KyberPolyVecNTT vec(mode.k());
244
245 BufferSlicer bs(a);
246 for(auto& p : vec) {
247 byte_decode(p, bs);
248 }
250
251 return vec;
252}
253
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}
261
263 KyberMessage result(p.size() / 8);
264 BufferStuffer bs(result);
265 poly_compress_and_encode<1>(bs, p);
266 return result;
267}
268
269namespace {
270
271template <size_t d>
272void polyvec_compress_and_encode(BufferStuffer& sink, const KyberPolyVec& polyvec) {
273 for(const auto& p : polyvec) {
274 poly_compress_and_encode<d>(sink, p);
275 }
276}
277
278void compress_polyvec(std::span<uint8_t> out, const KyberPolyVec& pv, const KyberConstants& mode) {
279 BufferStuffer bs(out);
280
281 switch(mode.d_u()) {
283 polyvec_compress_and_encode<10>(bs, pv);
284 BOTAN_ASSERT_NOMSG(bs.full());
285 return;
287 polyvec_compress_and_encode<11>(bs, pv);
288 BOTAN_ASSERT_NOMSG(bs.full());
289 return;
290 }
291
293}
294
295void compress_poly(std::span<uint8_t> out, const KyberPoly& p, const KyberConstants& mode) {
296 BufferStuffer bs(out);
297
298 switch(mode.d_v()) {
300 poly_compress_and_encode<4>(bs, p);
301 BOTAN_ASSERT_NOMSG(bs.full());
302 return;
304 poly_compress_and_encode<5>(bs, p);
305 BOTAN_ASSERT_NOMSG(bs.full());
306 return;
307 }
308
310}
311
312template <size_t d>
313void polyvec_decode_and_decompress(KyberPolyVec& polyvec, BufferSlicer& source) {
314 for(auto& p : polyvec) {
315 poly_decode_and_decompress<d>(p, source);
316 }
317}
318
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");
322
323 KyberPolyVec r(mode.k());
324 BufferSlicer bs(buffer);
325
326 switch(mode.d_u()) {
328 polyvec_decode_and_decompress<10>(r, bs);
329 BOTAN_ASSERT_NOMSG(bs.empty());
330 return r;
332 polyvec_decode_and_decompress<11>(r, bs);
333 BOTAN_ASSERT_NOMSG(bs.empty());
334 return r;
335 }
336
338}
339
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");
342
343 KyberPoly r;
344 BufferSlicer bs(buffer);
345
346 switch(mode.d_v()) {
348 poly_decode_and_decompress<4>(r, bs);
349 BOTAN_ASSERT_NOMSG(bs.empty());
350 return r;
352 poly_decode_and_decompress<5>(r, bs);
353 BOTAN_ASSERT_NOMSG(bs.empty());
354 return r;
355 }
356
358}
359
360} // namespace
361
362/**
363 * NIST FIPS 203, Algorithms 16 (ML-KEM.KeyGen_internal), and
364 * 13 (K-PKE.KeyGen)
365 *
366 * In contrast to the specification, the expansion of rho and sigma is inlined
367 * with the actual PKE key generation. The sampling loops spelled out in
368 * FIPS 203 are hidden in the sample_* functions. The keys are kept in memory
369 * without serialization, which is deferred until requested.
370 */
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}
407
409 const KyberPolyVec& u,
410 const KyberPoly& v,
411 const KyberConstants& m_mode) {
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);
416}
417
419 const KyberConstants& mode) {
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);
432
433 return {decompress_polynomial_vector(pv, mode), decompress_polynomial(p, mode)};
434}
435
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}
476
477/**
478 * NIST FIPS 203, Algorithm 8 (SamplePolyCBD)
479 *
480 * The actual implementation is above. This just dispatches to the correct
481 * specialization based on the eta of the chosen mode.
482 */
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}
495
496} // namespace Botan::Kyber_Algos
#define BOTAN_ASSERT_NOMSG(expr)
Definition assert.h:82
#define BOTAN_ARG_CHECK(expr, msg)
Definition assert.h:33
#define BOTAN_ASSERT(expr, assertion_made)
Definition assert.h:69
#define BOTAN_ASSERT_UNREACHABLE()
Definition assert.h:173
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
Definition pqcrystals.h:278
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.
Definition kyber_algos.h:77
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)
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
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.
Definition kyber_types.h:45
Botan::CRYSTALS::Polynomial< KyberPolyTraits, Botan::CRYSTALS::Domain::Normal > KyberPoly
Definition kyber_types.h:29
detail::Bounded_XOF< XOF &, bound > Bounded_XOF
Botan::CRYSTALS::PolynomialVector< KyberPolyTraits, Botan::CRYSTALS::Domain::NTT > KyberPolyVecNTT
Definition kyber_types.h:26
Botan::CRYSTALS::Polynomial< KyberPolyTraits, Botan::CRYSTALS::Domain::NTT > KyberPolyNTT
Definition kyber_types.h:25
BOTAN_FORCE_INLINE constexpr T rho(T x)
Definition rotate.h:53
BOTAN_FORCE_INLINE constexpr T sigma(T x)
Definition rotate.h:45
constexpr auto load_le(ParamTs &&... params)
Definition loadstor.h:495
std::pair< std::shared_ptr< const Kyber_PublicKeyInternal >, std::shared_ptr< const Kyber_PrivateKeyInternal > > KyberInternalKeypair
Definition kyber_types.h:73
Botan::CRYSTALS::PolynomialMatrix< KyberPolyTraits > KyberPolyMat
Definition kyber_types.h:27
Botan::CRYSTALS::PolynomialVector< KyberPolyTraits, Botan::CRYSTALS::Domain::Normal > KyberPolyVec
Definition kyber_types.h:30
std::optional< KyberSeedRandomness > d
Definition kyber_types.h:80