Botan 3.14.1
Crypto and TLS for C&
dilithium_algos.cpp
Go to the documentation of this file.
1/*
2 * Crystals Dilithium Internal Algorithms (aka. "Auxiliary Functions")
3 *
4 * This implements the auxiliary functions of the Crystals Dilithium signature
5 * scheme as specified in NIST FIPS 204, Chapter 7.
6 *
7 * Some implementations are based on the public domain reference implementation
8 * by the designers (https://github.com/pq-crystals/dilithium)
9 *
10 * (C) 2021-2024 Jack Lloyd
11 * (C) 2021-2022 Manuel Glaser and Michael Boric, Rohde & Schwarz Cybersecurity
12 * (C) 2021-2022 René Meusel and Hannes Rantzsch, neXenio GmbH
13 * (C) 2024 Fabian Albert and René Meusel, Rohde & Schwarz Cybersecurity
14 *
15 * Botan is released under the Simplified BSD License (see license.txt)
16 */
17
18#include <botan/internal/dilithium_algos.h>
19
20#include <botan/internal/bit_ops.h>
21#include <botan/internal/buffer_slicer.h>
22#include <botan/internal/buffer_stuffer.h>
23#include <botan/internal/ct_utils.h>
24#include <botan/internal/dilithium_keys.h>
25#include <botan/internal/dilithium_symmetric_primitives.h>
26#include <botan/internal/loadstor.h>
27#include <botan/internal/pqcrystals_encoding.h>
28#include <botan/internal/pqcrystals_helpers.h>
29#include <algorithm>
30#include <utility>
31
33
34namespace {
35
36/**
37 * Returns an all-one mask if @p x is negative, otherwise an all-zero mask.
38 */
39template <std::signed_integral T>
40constexpr auto is_negative_mask(T x) {
41 using unsigned_T = std::make_unsigned_t<T>;
42 return CT::Mask<unsigned_T>::expand_top_bit(static_cast<unsigned_T>(x));
43}
44
45template <DilithiumConstants::T b>
46constexpr std::make_unsigned_t<DilithiumConstants::T> map_range(DilithiumConstants::T c) {
47 // NIST FIPS 204, Algorithm 17 (BitPack)
48 // c is in range [-a, b] and must be mapped to [0, a + b] as follows:
49 BOTAN_DEBUG_ASSERT(b - c >= 0);
50 return b - c;
51}
52
53template <DilithiumConstants::T b>
54constexpr DilithiumConstants::T unmap_range(std::make_unsigned_t<DilithiumConstants::T> c) {
55 // NIST FIPS 204, Algorithm 19 (BitUnpack)
56 // c is in range [0, a + b] and must be mapped to [-a, b] as follows:
57 return static_cast<DilithiumConstants::T>(b - c);
58}
59
60template <DilithiumConstants::T a, DilithiumConstants::T b, CRYSTALS::crystals_trait PolyTrait, CRYSTALS::Domain D>
61constexpr void poly_pack(const CRYSTALS::Polynomial<PolyTrait, D>& p, BufferStuffer& stuffer) {
62 if constexpr(a == 0) {
63 // If `a` is 0, we assume SimpleBitPack (Algorithm 16) where the
64 // coefficients are in the range [0, b].
65 CRYSTALS::pack<b>(p, stuffer);
66 } else {
67 // Otherwise, for BitPack (Algorithm 17), we must map the coefficients to
68 // positive values as they are in the range [-a, b].
69 CRYSTALS::pack<a + b>(p, stuffer, map_range<b>);
70 }
71}
72
73template <DilithiumConstants::T a,
75 CRYSTALS::byte_source ByteSourceT,
78constexpr void poly_unpack(CRYSTALS::Polynomial<PolyTrait, D>& p, ByteSourceT& get_bytes, bool check_range = false) {
79 if constexpr(a == 0) {
80 // If `a` is 0, we assume SimpleBitUnpack (Algorithm 18) where the
81 // coefficients are in the range [0, b].
82 CRYSTALS::unpack<b>(p, get_bytes);
83 } else {
84 // Otherwise, BitUnpack (Algorithm 19) must map the unpacked coefficients
85 // to the range [-a, b].
86 CRYSTALS::unpack<a + b>(p, get_bytes, unmap_range<b>);
87 }
88
89 // `check_range` should only be enabled if the requested range is not fully
90 // covered by the encodeable range, i.e |range| is not a power of 2.
91 BOTAN_DEBUG_ASSERT(!check_range ||
92 (a >= 0 && b >= 0 && !is_power_of_2(static_cast<uint64_t>(b) - static_cast<uint64_t>(a) + 1)));
93
94 if(check_range && !p.ct_validate_value_range(-a, b)) {
95 throw Decoding_Error("Decoded polynomial coefficients out of range");
96 }
97}
98
99/**
100 * NIST FIPS 204, Algorithm 16 (SimpleBitPack)
101 * (for a = 2^(bitlen(q-1)-d) - 1)
102 */
103void poly_pack_t1(const DilithiumPoly& p, BufferStuffer& stuffer) {
104 constexpr auto b = (1 << (bitlen(DilithiumConstants::Q - 1) - DilithiumConstants::D)) - 1;
105 poly_pack<0, b>(p, stuffer);
106}
107
108/**
109 * NIST FIPS 204, Algorithm 16 (SimpleBitPack)
110 * (for a = (q-1)/(2*gamma2-1))
111 */
112void poly_pack_w1(const DilithiumPoly& p, BufferStuffer& stuffer, const DilithiumConstants& mode) {
114 const auto calculate_b = [](auto gamma2) { return ((DilithiumConstants::Q - 1) / (2 * gamma2)) - 1; };
115 switch(mode.gamma2()) {
116 case Gamma2::Qminus1DividedBy88:
117 return poly_pack<0, calculate_b(Gamma2::Qminus1DividedBy88)>(p, stuffer);
118 case Gamma2::Qminus1DividedBy32:
119 return poly_pack<0, calculate_b(Gamma2::Qminus1DividedBy32)>(p, stuffer);
120 }
121
123}
124
125/**
126 * NIST FIPS 204, Algorithm 17 (BitPack)
127 * (for a = -gamma1 - 1, b = gamma1)
128 */
129void poly_pack_gamma1(const DilithiumPoly& p, BufferStuffer& stuffer, const DilithiumConstants& mode) {
131 switch(mode.gamma1()) {
132 case Gamma1::ToThe17th:
133 return poly_pack<Gamma1::ToThe17th - 1, Gamma1::ToThe17th>(p, stuffer);
134 case Gamma1::ToThe19th:
135 return poly_pack<Gamma1::ToThe19th - 1, Gamma1::ToThe19th>(p, stuffer);
136 }
137
139}
140
141/**
142 * NIST FIPS 204, Algorithm 17 (BitPack)
143 * (for a = -eta, b = eta)
144 */
145void poly_pack_eta(const DilithiumPoly& p, BufferStuffer& stuffer, const DilithiumConstants& mode) {
147 switch(mode.eta()) {
148 case Eta::_2:
149 return poly_pack<Eta::_2, Eta::_2>(p, stuffer);
150 case Eta::_4:
151 return poly_pack<Eta::_4, Eta::_4>(p, stuffer);
152 }
153
155}
156
157/**
158 * NIST FIPS 204, Algorithm 17 (BitPack)
159 * (for a = -2^(d-1) - 1, b = 2^(d-1))
160 */
161void poly_pack_t0(const DilithiumPoly& p, BufferStuffer& stuffer) {
162 constexpr auto TwoToTheDminus1 = 1 << (DilithiumConstants::D - 1);
163 poly_pack<TwoToTheDminus1 - 1, TwoToTheDminus1>(p, stuffer);
164}
165
166/**
167 * NIST FIPS 204, Algorithm 18 (SimpleBitUnpack)
168 * (for a = 2^(bitlen(q-1)-d) - 1)
169 */
170void poly_unpack_t1(DilithiumPoly& p, BufferSlicer& slicer) {
171 constexpr auto b = (1 << (bitlen(DilithiumConstants::Q - 1) - DilithiumConstants::D)) - 1;
172 // The range of valid output coefficients [0, b] fully covers the encodeable
173 // range. Hence, no range check is needed despite this being exposed to
174 // potentially untrusted serialized public keys.
175 static_assert(b >= 0 && is_power_of_2(static_cast<uint32_t>(b) + 1));
176 poly_unpack<0, b>(p, slicer);
177}
178
179/**
180 * NIST FIPS 204, Algorithm 19 (BitUnpack)
181 * (for a = -gamma1 - 1, b = gamma1)
182 */
183template <typename ByteSourceT>
184void poly_unpack_gamma1(DilithiumPoly& p, ByteSourceT& byte_source, const DilithiumConstants& mode) {
186 switch(mode.gamma1()) {
187 case Gamma1::ToThe17th:
188 return poly_unpack<Gamma1::ToThe17th - 1, Gamma1::ToThe17th>(p, byte_source);
189 case Gamma1::ToThe19th:
190 return poly_unpack<Gamma1::ToThe19th - 1, Gamma1::ToThe19th>(p, byte_source);
191 }
192
194}
195
196/**
197 * NIST FIPS 204, Algorithm 19 (BitUnpack)
198 * (for a = -eta, b = eta)
199 */
200void poly_unpack_eta(DilithiumPoly& p, BufferSlicer& slicer, const DilithiumConstants& mode, bool check_range = false) {
202 switch(mode.eta()) {
203 case Eta::_2:
204 return poly_unpack<Eta::_2, Eta::_2>(p, slicer, check_range);
205 case Eta::_4:
206 return poly_unpack<Eta::_4, Eta::_4>(p, slicer, check_range);
207 }
208
210}
211
212/**
213 * NIST FIPS 204, Algorithm 19 (BitUnpack)
214 * (for a = -2^(d-1) - 1, b = 2^(d-1))
215 */
216void poly_unpack_t0(DilithiumPoly& p, BufferSlicer& slicer) {
217 constexpr auto TwoToTheDminus1 = 1 << (DilithiumConstants::D - 1);
218 poly_unpack<TwoToTheDminus1 - 1, TwoToTheDminus1>(p, slicer);
219}
220
221/**
222 * NIST FIPS 204, Algorithm 20 (HintBitPack)
223 */
224void hint_pack(const DilithiumPolyVec& h, BufferStuffer& stuffer, const DilithiumConstants& mode) {
225 BOTAN_ASSERT_NOMSG(h.size() == mode.k());
227
228 BufferStuffer bit_positions(stuffer.next(mode.omega()));
229 BufferStuffer offsets(stuffer.next(mode.k()));
230
231 uint8_t index = 0;
232 for(const auto& p : h) {
233 for(size_t i = 0; i < p.size(); ++i) {
234 if(p[i] == 1) {
235 bit_positions.append(static_cast<uint8_t>(i));
236 ++index;
237 }
238 }
239 offsets.append(index);
240 }
241
242 // Fill the remaining bit positions with zeros
243 bit_positions.append(0, bit_positions.remaining_capacity());
244}
245
246/**
247 * NIST FIPS 204, Algorithm 21 (HintBitUnpack)
248 */
249std::optional<DilithiumPolyVec> hint_unpack(BufferSlicer& slicer, const DilithiumConstants& mode) {
250 BufferSlicer bit_positions(slicer.take(mode.omega()));
251 BufferSlicer offsets(slicer.take(mode.k()));
252
253 DilithiumPolyVec hint(mode.k());
254 uint8_t index = 0;
255 for(auto& p : hint) {
256 const auto end_index = offsets.take_byte();
257
258 // Check the bounds of the end index for this polynomial
259 if(end_index < index || end_index > mode.omega()) {
260 return std::nullopt;
261 }
262
263 const auto set_bits = bit_positions.take(end_index - index);
264
265 // Check that the set bit positions are ordered (strong unforgeability)
266 // TODO: explicitly add a test for this, Whycheproof perhaps?
267 for(size_t i = 1; i < set_bits.size(); ++i) {
268 if(set_bits[i] <= set_bits[i - 1]) {
269 return std::nullopt;
270 }
271 }
272
273 // Set the specified bits in the polynomial
274 for(const auto i : set_bits) {
275 p[i] = 1;
276 }
277
278 index = end_index;
279 }
280
281 // Check that the remaining bit positions are all zero (strong unforgeability)
282 uint8_t sum = 0;
283 for(const uint8_t b : bit_positions.take(bit_positions.remaining())) {
284 sum |= b;
285 }
286
287 if(sum != 0) {
288 return std::nullopt;
289 }
290
292 return hint;
293}
294
295/**
296 * NIST FIPS 204, Algorithm 6, lines 5-7 (ML-DSA.KeyGen_internal)
297 *
298 * We have to expose this independently to derive the public key from the
299 * private key when loading a key pair from a serialized private key. This
300 * is needed because of Botan's design decision to let the private key
301 * class inherit from the public key class.
302 *
303 * TODO(Botan4): This should be refactored after PrivateKey does not inherit
304 * from PublicKey anymore.
305 */
306std::pair<DilithiumPolyVec, DilithiumPolyVec> compute_t1_and_t0(const DilithiumPolyMatNTT& A,
307 const DilithiumPolyVec& s1,
308 const DilithiumPolyVec& s2) {
309 auto t_hat = A * ntt(s1.clone());
310 t_hat.reduce();
311 auto t = inverse_ntt(std::move(t_hat));
312 t += s2;
314
316}
317
318} // namespace
319
320/**
321 * NIST FIPS 204, Algorithm 22 (pkEncode)
322 */
324 const DilithiumPolyVec& t1,
325 const DilithiumConstants& mode) {
327 BufferStuffer stuffer(pk);
328
329 stuffer.append(rho);
330 for(const auto& p : t1) {
331 poly_pack_t1(p, stuffer);
332 }
333
334 BOTAN_ASSERT_NOMSG(stuffer.full());
335 return pk;
336}
337
338/**
339 * NIST FIPS 204, Algorithm 23 (pkDecode)
340 */
341std::pair<DilithiumSeedRho, DilithiumPolyVec> decode_public_key(StrongSpan<const DilithiumSerializedPublicKey> pk,
342 const DilithiumConstants& mode) {
343 if(pk.size() != mode.public_key_bytes()) {
344 throw Decoding_Error("Dilithium: Invalid public key length");
345 }
346
347 BufferSlicer slicer(pk);
349
350 DilithiumPolyVec t1(mode.k());
351 for(auto& p : t1) {
352 poly_unpack_t1(p, slicer);
353 }
354 BOTAN_ASSERT_NOMSG(slicer.empty());
355
356 return {std::move(rho), std::move(t1)};
357}
358
359/**
360 * NIST FIPS 204, Algorithm 24 (skEncode)
361 */
363 const auto& [pk, sk] = keypair;
366 const auto& mode = sk->mode();
367 const auto scope = CT::scoped_poison(*sk);
368
369 DilithiumSerializedPrivateKey serialization(mode.private_key_bytes());
370 BufferStuffer stuffer(serialization);
371
372 stuffer.append(pk->rho());
373 stuffer.append(sk->signing_seed());
374 stuffer.append(pk->tr());
375
376 for(const auto& p : sk->s1()) {
377 poly_pack_eta(p, stuffer, mode);
378 }
379
380 for(const auto& p : sk->s2()) {
381 poly_pack_eta(p, stuffer, mode);
382 }
383
384 for(const auto& p : sk->t0()) {
385 poly_pack_t0(p, stuffer);
386 }
387
388 BOTAN_ASSERT_NOMSG(stuffer.full());
389 CT::unpoison(serialization);
390
391 return serialization;
392}
393
394/**
395 * NIST FIPS 204, Algorithm 25 (skDecode)
396 *
397 * Because Botan's Private_Key class inherits from Public_Key, we have to
398 * derive the public key from the private key here.
399 *
400 * TODO(Botan4): This should be refactored after PrivateKey does not inherit
401 * from PublicKey anymore.
402 */
404 const auto scope = CT::scoped_poison(sk);
405
406 if(sk.size() != mode.private_key_bytes()) {
407 throw Decoding_Error("invalid size for expanded ML-DSA (or Dilithium) private key");
408 }
409
410 BufferSlicer slicer(sk);
411
414 const auto tr = slicer.copy<DilithiumHashedPublicKey>(mode.public_key_hash_bytes());
415
416 DilithiumPolyVec s1(mode.l());
417 for(auto& p : s1) {
418 poly_unpack_eta(p, slicer, mode, true /* check decoded value range */);
419 }
420
421 DilithiumPolyVec s2(mode.k());
422 for(auto& p : s2) {
423 poly_unpack_eta(p, slicer, mode, true /* check decoded value range */);
424 }
425
426 DilithiumPolyVec t0(mode.k());
427 for(auto& p : t0) {
428 poly_unpack_t0(p, slicer);
429 }
430
431 BOTAN_ASSERT_NOMSG(slicer.empty());
432
433 // Currently, Botan's Private_Key class inherits from Public_Key, forcing us
434 // to derive the public key from the private key here.
435 // TODO(Botan4): Reconsider once PrivateKey/PublicKey issue is tackled.
436
437 CT::unpoison(rho); // rho is public (used in rejection sampling of matrix A)
438
439 const auto A = expand_A(rho, mode);
440 auto [t1, t0_recomputed] = compute_t1_and_t0(A, s1, s2);
441
442 CT::unpoison(t1); // part of the public key
443
445 std::make_shared<Dilithium_PublicKeyInternal>(mode, std::move(rho), std::move(t1)),
446 std::make_shared<Dilithium_PrivateKeyInternal>(std::move(mode),
447 std::nullopt, // decoding cannot recover the private seed
448 std::move(K),
449 std::move(s1),
450 std::move(s2),
451 std::move(t0)),
452 };
453
454 CT::unpoison(tr); // hash of the public key
455
456 if(keypair.first->tr() != tr) {
457 throw Decoding_Error("Calculated dilithium public key hash does not match the one stored in the private key");
458 }
459
460 CT::unpoison(*keypair.second);
461
462 // t0 is fully determined by (rho, s1, s2), so the encoded value must agree
463 CT::unpoison(t0_recomputed);
464 if(!std::ranges::equal(keypair.second->t0().coefficients(), t0_recomputed.coefficients())) {
465 throw Decoding_Error("Decoded dilithium private key t0 does not match the value derived from s1 and s2");
466 }
467
468 return keypair;
469}
470
471/**
472 * NIST FIPS 204, Algorithm 26 (sigEncode)
473 */
475 const DilithiumPolyVec& response,
476 const DilithiumPolyVec& hint,
477 const DilithiumConstants& mode) {
479 BufferStuffer stuffer(sig);
480
481 stuffer.append(c);
482 for(const auto& p : response) {
483 poly_pack_gamma1(p, stuffer, mode);
484 }
485 hint_pack(hint, stuffer, mode);
486
487 return sig;
488}
489
490/**
491 * NIST FIPS 204, Algorithm 27 (sigDecode)
492 */
493std::optional<std::tuple<DilithiumCommitmentHash, DilithiumPolyVec, DilithiumPolyVec>> decode_signature(
495 BufferSlicer slicer(sig);
496 BOTAN_ASSERT_NOMSG(slicer.remaining() == mode.signature_bytes());
497
498 auto commitment_hash = slicer.copy<DilithiumCommitmentHash>(mode.commitment_hash_full_bytes());
499
500 DilithiumPolyVec response(mode.l());
501 for(auto& p : response) {
502 poly_unpack_gamma1(p, slicer, mode);
503 }
504 BOTAN_ASSERT_NOMSG(slicer.remaining() == size_t(mode.omega()) + mode.k());
505
506 auto hint = hint_unpack(slicer, mode);
507 BOTAN_ASSERT_NOMSG(slicer.empty());
508 if(!hint.has_value()) {
509 return std::nullopt;
510 }
511
512 return std::make_tuple(std::move(commitment_hash), std::move(response), std::move(hint.value()));
513}
514
515/**
516 * NIST FIPS 204, Algorithm 28 (w1Encode)
517 */
520 BufferStuffer stuffer(commitment);
521
522 for(const auto& p : w1) {
523 poly_pack_w1(p, stuffer, mode);
524 }
525
526 return commitment;
527}
528
529/**
530 * NIST FIPS 204, Algorithm 29 (SampleInBall)
531 */
533 // This generator resembles the while loop in the spec.
534 auto xof = mode.symmetric_primitives().H(seed);
536
538 uint64_t signs = load_le(bounded_xof.next<8>());
539 for(size_t i = c.size() - mode.tau(); i < c.size(); ++i) {
540 const auto j = bounded_xof.next_byte([i](uint8_t byte) { return byte <= i; });
541 c[i] = c[j];
542 c[j] = 1 - 2 * (signs & 1);
543 signs >>= 1;
544 }
545
548
549 return c;
550}
551
552namespace {
553
554/**
555 * NIST FIPS 204, Algorithm 30 (RejNTTPoly)
556 */
557void sample_ntt_uniform(StrongSpan<const DilithiumSeedRho> rho,
559 uint16_t nonce,
560 const DilithiumConstants& mode) {
561 /**
562 * A generator that returns the next coefficient sampled from the XOF,
563 * according to: NIST FIPS 204, Algorithm 14 (CoeffFromThreeBytes).
564 */
565 auto xof = mode.symmetric_primitives().H(rho, nonce);
567
568 for(auto& coeff : p) {
569 coeff =
570 bounded_xof.next<3>([](const auto bytes) { return make_uint32(0, bytes[2], bytes[1], bytes[0]) & 0x7FFFFF; },
571 [](const uint32_t z) { return z < DilithiumConstants::Q; });
572 }
573
574 BOTAN_DEBUG_ASSERT(p.ct_validate_value_range(0, DilithiumConstants::Q - 1));
575}
576
577/**
578 * NIST FIPS 204, Algorithm 15 (CoeffFromHalfByte)
579 *
580 * Magic numbers for (b mod 5) are taken from the reference implementation.
581 */
582template <DilithiumConstants::DilithiumEta eta>
583std::optional<int32_t> coeff_from_halfbyte(uint8_t b) {
584 BOTAN_DEBUG_ASSERT(b < 16);
585
586 if constexpr(eta == DilithiumConstants::DilithiumEta::_2) {
587 if(CT::driveby_unpoison(b < 15)) {
588 b = b - (205U * b >> 10) * 5; // b = b mod 5
589 return 2 - b;
590 }
591 } else if constexpr(eta == DilithiumConstants::DilithiumEta::_4) {
592 if(CT::driveby_unpoison(b < 9)) {
593 return 4 - b;
594 }
595 }
596
597 return std::nullopt;
598}
599
600template <DilithiumConstants::DilithiumEta eta>
601void sample_uniform_eta(DilithiumPoly& p, Botan::XOF& xof) {
602 // A generator that returns the next coefficient sampled from the XOF. As the
603 // sampling uses half-bytes, this keeps track of the additionally sampled
604 // coefficient as needed.
605 auto next_coeff = [bounded_xof = Bounded_XOF<DilithiumConstants::SAMPLE_POLY_FROM_XOF_BOUND>(xof),
606 stashed_coeff = std::optional<int32_t>{}]() mutable -> int32_t {
607 if(auto stashed = std::exchange(stashed_coeff, std::nullopt)) {
608 return *stashed;
609 }
610
611 BOTAN_DEBUG_ASSERT(!stashed_coeff.has_value());
612 while(true) {
613 const auto b = bounded_xof.next_byte();
614 const auto z0 = coeff_from_halfbyte<eta>(b & 0x0F);
615 const auto z1 = coeff_from_halfbyte<eta>(b >> 4);
616
617 if(z0.has_value()) {
618 stashed_coeff = z1; // keep candidate z1 for the next invocation
619 return *z0;
620 } else if(z1.has_value()) {
621 // z0 was invalid, z1 is valid, nothing to stash
622 return *z1;
623 }
624 }
625 };
626
627 for(auto& coeff : p) {
628 coeff = next_coeff();
629 }
630}
631
632/**
633 * NIST FIPS 204, Algorithm 31 (RejBoundedPoly)
634 */
635void sample_uniform_eta(StrongSpan<const DilithiumSeedRhoPrime> rhoprime,
636 DilithiumPoly& p,
637 uint16_t nonce,
638 const DilithiumConstants& mode) {
640
641 auto xof = mode.symmetric_primitives().H(rhoprime, nonce);
642 switch(mode.eta()) {
643 case Eta::_2:
644 sample_uniform_eta<Eta::_2>(p, *xof);
645 break;
646 case Eta::_4:
647 sample_uniform_eta<Eta::_4>(p, *xof);
648 break;
649 }
650
651 // Rejection sampling is done. Secret polynomial can be repoisoned.
652 CT::poison(p);
653
654 BOTAN_DEBUG_ASSERT(p.ct_validate_value_range(-static_cast<int32_t>(mode.eta()), mode.eta()));
655}
656
657} // namespace
658
659/**
660 * NIST FIPS 204, Algorithm 6 (ML-DSA.KeyGen_internal)
661 *
662 * Lines 5-7 are extracted into a separate function, see above. The key
663 * encoding is deferred until the user explicitly invokes the encoding.
664 */
667 throw Decoding_Error("Invalid ML-DSA seed size");
668 }
669 const auto& sympriv = mode.symmetric_primitives();
670 CT::poison(xi);
671
672 auto [rho, rhoprime, K] = sympriv.H(xi);
673 CT::unpoison(rho); // rho is public (seed for the public matrix A)
674
675 const auto A = Dilithium_Algos::expand_A(rho, mode);
676 auto [s1, s2] = Dilithium_Algos::expand_s(rhoprime, mode);
677 auto [t1, t0] = Dilithium_Algos::compute_t1_and_t0(A, s1, s2);
678
679 CT::unpoison(t1); // part of the public key
680
682 std::make_shared<Dilithium_PublicKeyInternal>(mode, std::move(rho), std::move(t1)),
683 std::make_shared<Dilithium_PrivateKeyInternal>(
684 std::move(mode), std::move(xi), std::move(K), std::move(s1), std::move(s2), std::move(t0)),
685 };
686
687 CT::unpoison(*keypair.second);
688
689 return keypair;
690}
691
692/**
693 * NIST FIPS 204, Algorithm 32 (ExpandA)
694 *
695 * Note that the actual concatenation of rho, s and r is done downstream
696 * in the sampling function.
697 */
699 DilithiumPolyMatNTT A(mode.k(), mode.l());
700 for(uint8_t r = 0; r < mode.k(); ++r) {
701 for(uint8_t s = 0; s < mode.l(); ++s) {
702 sample_ntt_uniform(rho, A[r][s], load_le(std::array{s, r}), mode);
703 }
704 }
705 return A;
706}
707
708/**
709 * NIST FIPS 204, Algorithm 33 (ExpandS)
710 */
711std::pair<DilithiumPolyVec, DilithiumPolyVec> expand_s(StrongSpan<const DilithiumSeedRhoPrime> rhoprime,
712 const DilithiumConstants& mode) {
713 auto result = std::make_pair(DilithiumPolyVec(mode.l()), DilithiumPolyVec(mode.k()));
714 auto& [s1, s2] = result;
715
716 uint16_t nonce = 0;
717 for(auto& p : s1) {
718 sample_uniform_eta(rhoprime, p, nonce++, mode);
719 }
720
721 for(auto& p : s2) {
722 sample_uniform_eta(rhoprime, p, nonce++, mode);
723 }
724
725 return result;
726}
727
728/**
729 * NIST FIPS 204, Algorithm 34 (ExpandMask)
730 */
732 uint16_t nonce,
733 const DilithiumConstants& mode) {
734 DilithiumPolyVec s(mode.l());
735 for(auto& p : s) {
736 auto xof = mode.symmetric_primitives().H(rhoprime, nonce++);
737 poly_unpack_gamma1(p, *xof, mode);
738 }
739 return s;
740}
741
742/**
743 * NIST FIPS 204, Algorithm 35 (Power2Round)
744 *
745 * In contrast to the spec, this function takes a polynomial vector and
746 * performs the power2round operation on each coefficient in the vector.
747 * The actual Algorithm 35 as specified is actually just the inner lambda.
748 */
749std::pair<DilithiumPolyVec, DilithiumPolyVec> power2round(const DilithiumPolyVec& vec) {
750 // This procedure is taken verbatim from Dilithium's reference implementation.
751 const auto power2round = [d = DilithiumConstants::D](int32_t r) -> std::pair<int32_t, int32_t> {
752 const int32_t r1 = (r + (1 << (d - 1)) - 1) >> d;
753 const int32_t r0 = r - (r1 << d);
754 return {r1, r0};
755 };
756
757 auto result = std::make_pair(DilithiumPolyVec(vec.size()), DilithiumPolyVec(vec.size()));
758
759 for(size_t i = 0; i < vec.size(); ++i) {
760 for(size_t j = 0; j < vec[i].size(); ++j) {
761 std::tie(result.first[i][j], result.second[i][j]) = power2round(vec[i][j]);
762 }
763 }
764
765 return result;
766}
767
768namespace {
769
770/**
771 * NIST FIPS 204, Algorithm 36 (Decompose)
772 *
773 * The implementation is adapted from the verbatim reference implementation using
774 * the magic numbers that depend on the values of Q and gamma2 and ensure that
775 * this operation is done in constant-time.
776 */
777template <DilithiumConstants::DilithiumGamma2 gamma2>
778std::pair<int32_t, int32_t> decompose(int32_t r) {
779 int32_t r1 = (r + 127) >> 7;
780
782 r1 = (r1 * 1025 + (1 << 21)) >> 22;
783 r1 &= 15;
784 } else if constexpr(gamma2 == DilithiumConstants::DilithiumGamma2::Qminus1DividedBy88) {
785 r1 = (r1 * 11275 + (1 << 23)) >> 24;
786 r1 = is_negative_mask(43 - r1).if_not_set_return(r1);
787 }
788
789 int32_t r0 = r - r1 * 2 * gamma2;
790
791 // reduce r0 mod q
792 r0 -= is_negative_mask((DilithiumConstants::Q - 1) / 2 - r0).if_set_return(DilithiumConstants::Q);
793
794 return {r1, r0};
795}
796
797/**
798 * This is templated on all possible values of gamma2 to allow for compile-time
799 * optimization given the statically known value of gamma2.
800 */
801template <DilithiumConstants::DilithiumGamma2 gamma2>
802std::pair<DilithiumPolyVec, DilithiumPolyVec> decompose_all_coefficients(const DilithiumPolyVec& vec) {
803 auto result = std::make_pair(DilithiumPolyVec(vec.size()), DilithiumPolyVec(vec.size()));
804
805 for(size_t i = 0; i < vec.size(); ++i) {
806 for(size_t j = 0; j < vec[i].size(); ++j) {
807 std::tie(result.first[i][j], result.second[i][j]) = decompose<gamma2>(vec[i][j]);
808 }
809 }
810
811 return result;
812}
813
814} // namespace
815
816/**
817 * NIST FIPS 204, Algorithm 36 (Decompose) on a polynomial vector
818 *
819 * Algorithms 37 (HighBits) and 38 (LowBits) are not implemented explicitly,
820 * simply use the first (HighBits) and second (LowBits) element of the result.
821 */
822std::pair<DilithiumPolyVec, DilithiumPolyVec> decompose(const DilithiumPolyVec& vec, const DilithiumConstants& mode) {
824 switch(mode.gamma2()) {
825 case Gamma2::Qminus1DividedBy32:
826 return decompose_all_coefficients<Gamma2::Qminus1DividedBy32>(vec);
827 break;
828 case Gamma2::Qminus1DividedBy88:
829 return decompose_all_coefficients<Gamma2::Qminus1DividedBy88>(vec);
830 break;
831 }
832
834}
835
836/**
837 * NIST FIPS 204, Algorithm 39 (MakeHint)
838 *
839 * MakeHint is specified per value in FIPS 204. This implements the algorithm
840 * for the entire polynomial vector. The specified algorithm is equivalent to
841 * the inner lambda.
842 *
843 * TODO: This is taken from the reference implementation. We should implement it
844 * as specified in the spec, and see if that has any performance impact.
845 */
847 BOTAN_DEBUG_ASSERT(z.size() == r.size());
848
849 const auto make_hint = [gamma2 = uint32_t(mode.gamma2()),
850 q_gamma2 = static_cast<uint32_t>(DilithiumConstants::Q) - uint32_t(mode.gamma2())](
851 int32_t c0, int32_t c1) -> CT::Choice {
852 BOTAN_DEBUG_ASSERT(c0 >= 0);
853 BOTAN_DEBUG_ASSERT(c1 >= 0);
854
855 const uint32_t pc0 = static_cast<uint32_t>(c0);
856 const uint32_t pc1 = static_cast<uint32_t>(c1);
857
858 return (CT::Mask<uint32_t>::is_gt(pc0, gamma2) & CT::Mask<uint32_t>::is_lte(pc0, q_gamma2) &
860 .as_choice();
861 };
862
863 DilithiumPolyVec hint(r.size());
864
865 for(size_t i = 0; i < r.size(); ++i) {
866 for(size_t j = 0; j < r[i].size(); ++j) {
867 hint[i][j] = static_cast<int>(make_hint(z[i][j], r[i][j]).as_bool());
868 }
869 }
870
872
873 return hint;
874}
875
876namespace {
877
878/**
879 * This is templated on all possible values of gamma2 to allow for compile-time
880 * optimization given the statically known value of gamma2.
881 */
882template <DilithiumConstants::DilithiumGamma2 gamma2>
883void use_hint_on_coefficients(const DilithiumPolyVec& hints, DilithiumPolyVec& vec) {
884 constexpr auto m = (DilithiumConstants::Q - 1) / (2 * gamma2);
885
886 auto modulo_m = [](int32_t r1) -> int32_t {
887 BOTAN_DEBUG_ASSERT(r1 >= -static_cast<decltype(r1)>(m) && r1 <= static_cast<decltype(r1)>(m));
888 return (r1 + m) % m;
889 };
890
891 const auto use_hint = [&modulo_m](bool hint, int32_t r) -> int32_t {
892 auto [r1, r0] = decompose<gamma2>(r);
893
894 if(!hint) {
895 return r1;
896 }
897
898 if(r0 > 0) {
899 return modulo_m(r1 + 1);
900 } else {
901 return modulo_m(r1 - 1);
902 }
903 };
904
905 for(size_t i = 0; i < vec.size(); ++i) {
906 for(size_t j = 0; j < vec[i].size(); ++j) {
907 vec[i][j] = use_hint(hints[i][j], vec[i][j]);
908 }
909 }
910}
911
912} // namespace
913
914/**
915 * NIST FIPS 204, Algorithm 40 (UseHint)
916 *
917 * UseHint is specified per value in FIPS 204. This implements the algorithm
918 * for the entire polynomial vector. The specified algorithm is equivalent to
919 * the inner lambdas of 'use_hint_with_coefficients'.
920 */
921void use_hint(DilithiumPolyVec& vec, const DilithiumPolyVec& hints, const DilithiumConstants& mode) {
922 BOTAN_DEBUG_ASSERT(hints.size() == vec.size());
925
927 switch(mode.gamma2()) {
928 case Gamma2::Qminus1DividedBy32:
929 use_hint_on_coefficients<Gamma2::Qminus1DividedBy32>(hints, vec);
930 break;
931 case Gamma2::Qminus1DividedBy88:
932 use_hint_on_coefficients<Gamma2::Qminus1DividedBy88>(hints, vec);
933 break;
934 }
935
937}
938
939bool infinity_norm_within_bound(const DilithiumPolyVec& vec, size_t bound) {
940 BOTAN_DEBUG_ASSERT(bound <= (DilithiumConstants::Q - 1) / 8);
941
942 // It is ok to leak which coefficient violates the bound as the probability
943 // for each coefficient is independent of secret data but we must not leak
944 // the sign of the centralized representative.
945 for(const auto& p : vec) {
946 for(const auto c : p) {
947 const auto abs_c = c - is_negative_mask(c).if_set_return(2 * c);
948 if(CT::driveby_unpoison(abs_c >= bound)) {
949 return false;
950 }
951 }
952 }
953
954 return true;
955}
956
957} // namespace Botan::Dilithium_Algos
#define BOTAN_ASSERT_NOMSG(expr)
Definition assert.h:82
#define BOTAN_DEBUG_ASSERT(expr)
Definition assert.h:136
#define BOTAN_ASSERT_NONNULL(ptr)
Definition assert.h:121
#define BOTAN_ASSERT_UNREACHABLE()
Definition assert.h:173
size_t remaining() const
auto copy(const size_t count)
std::span< const uint8_t > take(const size_t count)
Helper class to ease in-place marshalling of concatenated fixed-length values.
constexpr void append(std::span< const uint8_t > buffer)
constexpr size_t remaining_capacity() const
constexpr std::span< uint8_t > next(size_t bytes)
constexpr bool full() const
ThisPolynomialVector clone() const
Definition pqcrystals.h:420
constexpr bool ct_validate_value_range(T min, T max) const noexcept
Definition pqcrystals.h:441
ThisPolynomialVector & conditional_add_q()
Definition pqcrystals.h:472
constexpr size_t hamming_weight() const noexcept
Definition pqcrystals.h:296
constexpr size_t size() const
Definition pqcrystals.h:278
constexpr bool ct_validate_value_range(T min, T max) const noexcept
Definition pqcrystals.h:291
static constexpr Mask< T > is_lte(T x, T y)
Definition ct_utils.h:468
static constexpr Mask< T > expand_top_bit(T v)
Definition ct_utils.h:420
static constexpr Mask< T > is_equal(T x, T y)
Definition ct_utils.h:447
static constexpr Mask< T > is_gt(T x, T y)
Definition ct_utils.h:463
static constexpr Mask< T > is_zero(T x)
Definition ct_utils.h:442
size_t public_key_bytes() const
byte length of the encoded public key
size_t commitment_hash_full_bytes() const
length of the entire commitment hash 'c~' in bytes (differs between R3 and ML-DSA)
static constexpr T Q
modulus
size_t signature_bytes() const
byte length of the encoded signature
DilithiumGamma1 gamma1() const
coefficient range of the randomly sampled mask 'y'
DilithiumEta eta() const
coefficient range of the private key's polynomial vectors 's1' and 's2'
uint8_t l() const
dimensions of the expanded matrix A
Dilithium_Symmetric_Primitives_Base & symmetric_primitives() const
static constexpr T D
number of dropped bits from t (see FIPS 204 Section 5)
static constexpr size_t SEED_RANDOMNESS_BYTES
DilithiumTau tau() const
hamming weight of the polynomial 'c' sampled from the commitment's hash
static constexpr size_t SEED_SIGNING_KEY_BYTES
int32_t T
base data type for most calculations
size_t public_key_hash_bytes() const
length of the public key hash 'tr' in bytes (differs between R3 and ML-DSA)
size_t private_key_bytes() const
byte length of the encoded private key
size_t serialized_commitment_bytes() const
byte length of the packed commitment polynomial vector 'w1'
DilithiumOmega omega() const
maximal hamming weight of the hint polynomial vector 'h'
uint8_t k() const
dimensions of the expanded matrix A
DilithiumGamma2 gamma2() const
low-order rounding range for decomposing the commitment from polynomial vector 'w'
static constexpr size_t SEED_RHO_BYTES
DilithiumHashedPublicKey H(StrongSpan< const DilithiumSerializedPublicKey > pk) const
decltype(auto) size() const noexcept(noexcept(this->m_span.size()))
size_type size() const noexcept(noexcept(this->get().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 decltype(auto) driveby_unpoison(T &&v)
Definition ct_utils.h:243
constexpr auto scoped_poison(const Ts &... xs)
Definition ct_utils.h:222
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
DilithiumSerializedPublicKey encode_public_key(StrongSpan< const DilithiumSeedRho > rho, const DilithiumPolyVec &t1, const DilithiumConstants &mode)
DilithiumInternalKeypair expand_keypair(DilithiumSeedRandomness xi, DilithiumConstants mode)
DilithiumSerializedSignature encode_signature(StrongSpan< const DilithiumCommitmentHash > c, const DilithiumPolyVec &response, const DilithiumPolyVec &hint, const DilithiumConstants &mode)
DilithiumSerializedPrivateKey encode_keypair(const DilithiumInternalKeypair &keypair)
DilithiumSerializedCommitment encode_commitment(const DilithiumPolyVec &w1, const DilithiumConstants &mode)
DilithiumInternalKeypair decode_keypair(StrongSpan< const DilithiumSerializedPrivateKey > sk, DilithiumConstants mode)
std::pair< DilithiumPolyVec, DilithiumPolyVec > power2round(const DilithiumPolyVec &vec)
bool infinity_norm_within_bound(const DilithiumPolyVec &vec, size_t bound)
std::pair< DilithiumPolyVec, DilithiumPolyVec > decompose(const DilithiumPolyVec &vec, const DilithiumConstants &mode)
DilithiumPolyVec expand_mask(StrongSpan< const DilithiumSeedRhoPrime > rhoprime, uint16_t nonce, const DilithiumConstants &mode)
DilithiumPolyMatNTT expand_A(StrongSpan< const DilithiumSeedRho > rho, const DilithiumConstants &mode)
void use_hint(DilithiumPolyVec &vec, const DilithiumPolyVec &hints, const DilithiumConstants &mode)
std::pair< DilithiumPolyVec, DilithiumPolyVec > expand_s(StrongSpan< const DilithiumSeedRhoPrime > rhoprime, const DilithiumConstants &mode)
std::pair< DilithiumSeedRho, DilithiumPolyVec > decode_public_key(StrongSpan< const DilithiumSerializedPublicKey > pk, const DilithiumConstants &mode)
std::optional< std::tuple< DilithiumCommitmentHash, DilithiumPolyVec, DilithiumPolyVec > > decode_signature(StrongSpan< const DilithiumSerializedSignature > sig, const DilithiumConstants &mode)
DilithiumPolyVec make_hint(const DilithiumPolyVec &z, const DilithiumPolyVec &r, const DilithiumConstants &mode)
DilithiumPoly sample_in_ball(StrongSpan< const DilithiumCommitmentHash > seed, const DilithiumConstants &mode)
BOTAN_FORCE_INLINE constexpr bool is_power_of_2(T arg)
Definition bit_ops.h:62
Strong< std::vector< uint8_t >, struct DilithiumSerializedSignature_ > DilithiumSerializedSignature
Serialized signature data.
Strong< secure_vector< uint8_t >, struct DilithiumSeedK_ > DilithiumSigningSeedK
Private seed K used during signing.
Strong< secure_vector< uint8_t >, struct DilithiumSeedRandomness_ > DilithiumSeedRandomness
Principal seed used to generate Dilithium key pairs.
detail::Bounded_XOF< XOF &, bound > Bounded_XOF
Botan::CRYSTALS::PolynomialVector< DilithiumPolyTraits, Botan::CRYSTALS::Domain::Normal > DilithiumPolyVec
Strong< std::vector< uint8_t >, struct DilithiumPublicSeed_ > DilithiumSeedRho
Public seed to sample the polynomial matrix A from.
Strong< secure_vector< uint8_t >, struct DilithiumSerializedPrivateKey_ > DilithiumSerializedPrivateKey
Serialized private key data.
constexpr uint32_t make_uint32(uint8_t i0, uint8_t i1, uint8_t i2, uint8_t i3)
Definition loadstor.h:104
Botan::CRYSTALS::Polynomial< DilithiumPolyTraits, Botan::CRYSTALS::Domain::NTT > DilithiumPolyNTT
Strong< std::vector< uint8_t >, struct DilithiumCommitmentHash_ > DilithiumCommitmentHash
Hash of the message representative and the signer's commitment.
BOTAN_FORCE_INLINE constexpr T rho(T x)
Definition rotate.h:53
Strong< std::vector< uint8_t >, struct DilithiumSerializedPublicKey_ > DilithiumSerializedPublicKey
Serialized public key data (result of pkEncode(pk)).
constexpr auto load_le(ParamTs &&... params)
Definition loadstor.h:495
Botan::CRYSTALS::Polynomial< DilithiumPolyTraits, Botan::CRYSTALS::Domain::Normal > DilithiumPoly
Strong< std::vector< uint8_t >, struct DilithiumSerializedCommitment_ > DilithiumSerializedCommitment
Serialized representation of a commitment w1.
Botan::CRYSTALS::PolynomialMatrix< DilithiumPolyTraits > DilithiumPolyMatNTT
constexpr auto bitlen(size_t x)
std::pair< std::shared_ptr< const Dilithium_PublicKeyInternal >, std::shared_ptr< const Dilithium_PrivateKeyInternal > > DilithiumInternalKeypair
Internal representation of a Dilithium key pair.
Strong< std::vector< uint8_t >, struct DilithiumHashedPublicKey_ > DilithiumHashedPublicKey