18#include <botan/internal/dilithium_algos.h>
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>
39template <std::
signed_
integral T>
40constexpr auto is_negative_mask(T x) {
41 using unsigned_T = std::make_unsigned_t<T>;
45template <DilithiumConstants::T b>
53template <DilithiumConstants::T b>
60template <DilithiumConstants::T a, DilithiumConstants::T b, CRYSTALS::crystals_trait PolyTrait, CRYSTALS::Domain D>
62 if constexpr(a == 0) {
79 if constexpr(a == 0) {
92 (a >= 0 && b >= 0 && !
is_power_of_2(
static_cast<uint64_t
>(b) -
static_cast<uint64_t
>(a) + 1)));
95 throw Decoding_Error(
"Decoded polynomial coefficients out of range");
105 poly_pack<0, b>(p, stuffer);
114 const auto calculate_b = [](
auto gamma2) {
return ((
DilithiumConstants::Q - 1) / (2 * gamma2)) - 1; };
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);
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);
149 return poly_pack<Eta::_2, Eta::_2>(p, stuffer);
151 return poly_pack<Eta::_4, Eta::_4>(p, stuffer);
163 poly_pack<TwoToTheDminus1 - 1, TwoToTheDminus1>(p, stuffer);
175 static_assert(b >= 0 &&
is_power_of_2(
static_cast<uint32_t
>(b) + 1));
176 poly_unpack<0, b>(p, slicer);
183template <
typename ByteSourceT>
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);
204 return poly_unpack<Eta::_2, Eta::_2>(p, slicer, check_range);
206 return poly_unpack<Eta::_4, Eta::_4>(p, slicer, check_range);
218 poly_unpack<TwoToTheDminus1 - 1, TwoToTheDminus1>(p, slicer);
232 for(
const auto& p : h) {
233 for(
size_t i = 0; i < p.
size(); ++i) {
235 bit_positions.
append(
static_cast<uint8_t
>(i));
255 for(
auto& p : hint) {
256 const auto end_index = offsets.
take_byte();
259 if(end_index < index || end_index > mode.
omega()) {
263 const auto set_bits = bit_positions.
take(end_index - index);
267 for(
size_t i = 1; i < set_bits.size(); ++i) {
268 if(set_bits[i] <= set_bits[i - 1]) {
274 for(
const auto i : set_bits) {
283 for(
const uint8_t b : bit_positions.
take(bit_positions.
remaining())) {
306std::pair<DilithiumPolyVec, DilithiumPolyVec> compute_t1_and_t0(
const DilithiumPolyMatNTT& A,
309 auto t_hat = A * ntt(s1.
clone());
311 auto t = inverse_ntt(std::move(t_hat));
330 for(
const auto& p : t1) {
331 poly_pack_t1(p, stuffer);
352 poly_unpack_t1(p, slicer);
356 return {std::move(
rho), std::move(t1)};
363 const auto& [pk, sk] = keypair;
366 const auto& mode = sk->mode();
372 stuffer.
append(pk->rho());
373 stuffer.
append(sk->signing_seed());
376 for(
const auto& p : sk->s1()) {
377 poly_pack_eta(p, stuffer, mode);
380 for(
const auto& p : sk->s2()) {
381 poly_pack_eta(p, stuffer, mode);
384 for(
const auto& p : sk->t0()) {
385 poly_pack_t0(p, stuffer);
391 return serialization;
407 throw Decoding_Error(
"invalid size for expanded ML-DSA (or Dilithium) private key");
418 poly_unpack_eta(p, slicer, mode,
true );
423 poly_unpack_eta(p, slicer, mode,
true );
428 poly_unpack_t0(p, slicer);
440 auto [t1, t0_recomputed] = compute_t1_and_t0(A, s1, s2);
445 std::make_shared<Dilithium_PublicKeyInternal>(mode, std::move(
rho), std::move(t1)),
446 std::make_shared<Dilithium_PrivateKeyInternal>(std::move(mode),
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");
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");
482 for(
const auto& p : response) {
483 poly_pack_gamma1(p, stuffer, mode);
485 hint_pack(hint, stuffer, mode);
493std::optional<std::tuple<DilithiumCommitmentHash, DilithiumPolyVec, DilithiumPolyVec>>
decode_signature(
501 for(
auto& p : response) {
502 poly_unpack_gamma1(p, slicer, mode);
506 auto hint = hint_unpack(slicer, mode);
508 if(!hint.has_value()) {
512 return std::make_tuple(std::move(commitment_hash), std::move(response), std::move(hint.value()));
522 for(
const auto& p : w1) {
523 poly_pack_w1(p, stuffer, mode);
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; });
542 c[j] = 1 - 2 * (signs & 1);
568 for(
auto& coeff : p) {
570 bounded_xof.next<3>([](
const auto bytes) {
return make_uint32(0, bytes[2], bytes[1], bytes[0]) & 0x7FFFFF; },
582template <DilithiumConstants::DilithiumEta eta>
583std::optional<int32_t> coeff_from_halfbyte(uint8_t b) {
588 b = b - (205U * b >> 10) * 5;
600template <DilithiumConstants::DilithiumEta eta>
606 stashed_coeff = std::optional<int32_t>{}]()
mutable -> int32_t {
607 if(
auto stashed = std::exchange(stashed_coeff, std::nullopt)) {
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);
620 }
else if(z1.has_value()) {
627 for(
auto& coeff : p) {
628 coeff = next_coeff();
635void sample_uniform_eta(StrongSpan<const DilithiumSeedRhoPrime> rhoprime,
638 const DilithiumConstants& mode) {
641 auto xof = mode.symmetric_primitives().H(rhoprime, nonce);
644 sample_uniform_eta<Eta::_2>(p, *xof);
647 sample_uniform_eta<Eta::_4>(p, *xof);
654 BOTAN_DEBUG_ASSERT(p.ct_validate_value_range(-
static_cast<int32_t
>(mode.eta()), mode.eta()));
672 auto [
rho, rhoprime, K] = sympriv.H(xi);
677 auto [t1, t0] = Dilithium_Algos::compute_t1_and_t0(A, s1, s2);
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)),
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);
714 auto& [s1, s2] = result;
718 sample_uniform_eta(rhoprime, p, nonce++, mode);
722 sample_uniform_eta(rhoprime, p, nonce++, mode);
737 poly_unpack_gamma1(p, *xof, mode);
752 const int32_t r1 = (r + (1 << (d - 1)) - 1) >> d;
753 const int32_t r0 = r - (r1 << d);
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]);
777template <DilithiumConstants::DilithiumGamma2 gamma2>
778std::pair<int32_t, int32_t>
decompose(int32_t r) {
779 int32_t r1 = (r + 127) >> 7;
782 r1 = (r1 * 1025 + (1 << 21)) >> 22;
785 r1 = (r1 * 11275 + (1 << 23)) >> 24;
786 r1 = is_negative_mask(43 - r1).if_not_set_return(r1);
789 int32_t r0 = r - r1 * 2 * gamma2;
801template <DilithiumConstants::DilithiumGamma2 gamma2>
802std::pair<DilithiumPolyVec, DilithiumPolyVec> decompose_all_coefficients(
const DilithiumPolyVec& vec) {
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]);
825 case Gamma2::Qminus1DividedBy32:
826 return decompose_all_coefficients<Gamma2::Qminus1DividedBy32>(vec);
828 case Gamma2::Qminus1DividedBy88:
829 return decompose_all_coefficients<Gamma2::Qminus1DividedBy88>(vec);
855 const uint32_t pc0 =
static_cast<uint32_t
>(c0);
856 const uint32_t pc1 =
static_cast<uint32_t
>(c1);
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());
882template <DilithiumConstants::DilithiumGamma2 gamma2>
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));
891 const auto use_hint = [&modulo_m](
bool hint, int32_t r) -> int32_t {
899 return modulo_m(r1 + 1);
901 return modulo_m(r1 - 1);
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]);
928 case Gamma2::Qminus1DividedBy32:
929 use_hint_on_coefficients<Gamma2::Qminus1DividedBy32>(hints, vec);
931 case Gamma2::Qminus1DividedBy88:
932 use_hint_on_coefficients<Gamma2::Qminus1DividedBy88>(hints, vec);
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);
#define BOTAN_ASSERT_NOMSG(expr)
#define BOTAN_DEBUG_ASSERT(expr)
#define BOTAN_ASSERT_NONNULL(ptr)
#define BOTAN_ASSERT_UNREACHABLE()
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
constexpr bool ct_validate_value_range(T min, T max) const noexcept
ThisPolynomialVector & conditional_add_q()
constexpr size_t hamming_weight() const noexcept
constexpr size_t size() const
constexpr bool ct_validate_value_range(T min, T max) const noexcept
static constexpr Mask< T > is_lte(T x, T y)
static constexpr Mask< T > expand_top_bit(T v)
static constexpr Mask< T > is_equal(T x, T y)
static constexpr Mask< T > is_gt(T x, T y)
static constexpr Mask< T > is_zero(T x)
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)
constexpr auto scoped_poison(const Ts &... xs)
constexpr void unpoison(const T *p, size_t n)
constexpr void poison(const T *p, size_t n)
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)
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)
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)
Strong< std::vector< uint8_t >, struct DilithiumSerializedPublicKey_ > DilithiumSerializedPublicKey
Serialized public key data (result of pkEncode(pk)).
constexpr auto load_le(ParamTs &&... params)
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