14#include <botan/dilithium.h>
16#include <botan/exceptn.h>
17#include <botan/hash.h>
20#include <botan/internal/dilithium_polynomials.h>
21#include <botan/internal/fmt.h>
22#include <botan/internal/parsing.h>
23#include <botan/internal/pk_ops_impl.h>
24#include <botan/internal/shake.h>
25#include <botan/internal/stl_util.h>
36std::pair<Dilithium::PolynomialVector, Dilithium::PolynomialVector> calculate_t0_and_t1(
37 const DilithiumModeConstants& mode,
38 const std::vector<uint8_t>&
rho,
39 Dilithium::PolynomialVector s1,
40 const Dilithium::PolynomialVector& s2) {
56 Dilithium::PolynomialVector t0(mode.k());
57 Dilithium::PolynomialVector t1(mode.k());
60 return {std::move(t0), std::move(t1)};
64 if(str ==
"Dilithium-4x4-r3") {
67 if(str ==
"Dilithium-4x4-AES-r3") {
70 if(str ==
"Dilithium-6x5-r3") {
73 if(str ==
"Dilithium-6x5-AES-r3") {
76 if(str ==
"Dilithium-8x7-r3") {
79 if(str ==
"Dilithium-8x7-AES-r3") {
83 throw Invalid_Argument(
fmt(
"'{}' is not a valid Dilithium mode name", str));
99 return "Dilithium-4x4-r3";
101 return "Dilithium-4x4-AES-r3";
103 return "Dilithium-6x5-r3";
105 return "Dilithium-6x5-AES-r3";
107 return "Dilithium-8x7-r3";
109 return "Dilithium-8x7-AES-r3";
115class Dilithium_PublicKeyInternal {
119 Dilithium_PublicKeyInternal(DilithiumModeConstants mode, std::span<const uint8_t> raw_pk) :
120 m_mode(std::move(mode)) {
123 BufferSlicer s(raw_pk);
131 m_raw_pk_shake256 = compute_raw_pk_shake256();
134 Dilithium_PublicKeyInternal(DilithiumModeConstants mode,
135 std::vector<uint8_t> rho,
136 const Dilithium::PolynomialVector& s1,
137 const Dilithium::PolynomialVector& s2) :
138 m_mode(std::move(mode)),
139 m_rho(std::move(
rho)),
140 m_t1([&] {
return calculate_t0_and_t1(m_mode, m_rho, s1, s2).second; }()) {
143 m_raw_pk_shake256 = compute_raw_pk_shake256();
146 Dilithium_PublicKeyInternal(DilithiumModeConstants mode,
147 std::vector<uint8_t> rho,
148 Dilithium::PolynomialVector t1) :
149 m_mode(std::move(mode)), m_rho(std::move(
rho)), m_t1(std::move(t1)) {
152 m_raw_pk_shake256 = compute_raw_pk_shake256();
155 ~Dilithium_PublicKeyInternal() =
default;
157 Dilithium_PublicKeyInternal(
const Dilithium_PublicKeyInternal&) =
delete;
158 Dilithium_PublicKeyInternal(Dilithium_PublicKeyInternal&&) =
delete;
159 Dilithium_PublicKeyInternal& operator=(
const Dilithium_PublicKeyInternal& other) =
delete;
160 Dilithium_PublicKeyInternal& operator=(Dilithium_PublicKeyInternal&& other) =
delete;
164 const std::vector<uint8_t>& raw_pk_shake256()
const {
166 return m_raw_pk_shake256;
169 const Dilithium::PolynomialVector& t1()
const {
return m_t1; }
171 const std::vector<uint8_t>&
rho()
const {
return m_rho; }
173 const DilithiumModeConstants& mode()
const {
return m_mode; }
176 std::vector<uint8_t> compute_raw_pk_shake256()
const {
180 return shake.final_stdvec();
183 const DilithiumModeConstants m_mode;
184 std::vector<uint8_t> m_raw_pk_shake256;
185 std::vector<uint8_t> m_rho;
186 Dilithium::PolynomialVector m_t1;
189class Dilithium_PrivateKeyInternal {
191 Dilithium_PrivateKeyInternal(DilithiumModeConstants mode) : m_mode(std::move(mode)) {}
193 Dilithium_PrivateKeyInternal(DilithiumModeConstants mode,
194 std::vector<uint8_t> rho,
197 Dilithium::PolynomialVector s1,
198 Dilithium::PolynomialVector s2,
199 Dilithium::PolynomialVector t0) :
200 m_mode(std::move(mode)),
201 m_rho(std::move(
rho)),
203 m_key(std::move(key)),
206 m_s2(std::move(s2)) {}
208 Dilithium_PrivateKeyInternal(DilithiumModeConstants mode, std::span<const uint8_t> sk) :
209 Dilithium_PrivateKeyInternal(std::move(mode)) {
229 const DilithiumModeConstants& mode()
const {
return m_mode; }
231 const std::vector<uint8_t>&
rho()
const {
return m_rho; }
237 const Dilithium::PolynomialVector& s1()
const {
return m_s1; }
239 const Dilithium::PolynomialVector& s2()
const {
return m_s2; }
241 const Dilithium::PolynomialVector& t0()
const {
return m_t0; }
244 const DilithiumModeConstants m_mode;
245 std::vector<uint8_t> m_rho;
247 Dilithium::PolynomialVector m_t0, m_s1, m_s2;
250class Dilithium_Signature_Operation
final :
public PK_Ops::Signature {
252 Dilithium_Signature_Operation(
const Dilithium_PrivateKey& priv_key_dilithium,
bool randomized) :
253 m_priv_key(priv_key_dilithium),
255 Dilithium::PolynomialMatrix::generate_matrix(m_priv_key.m_private->
rho(), m_priv_key.m_private->mode())),
256 m_shake(DilithiumModeConstants::CRHBYTES * 8),
257 m_randomized(randomized) {
258 m_shake.
update(m_priv_key.m_private->tr());
261 void update(
const uint8_t msg[],
size_t msg_len)
override { m_shake.
update(msg, msg_len); }
267 m_shake.
update(m_priv_key.m_private->tr());
269 const auto& mode = m_priv_key.m_private->mode();
272 : mode.CRH(
concat(m_priv_key.m_private->get_key(), mu));
275 auto s1 = m_priv_key.m_private->s1();
278 auto s2 = m_priv_key.m_private->s2();
281 auto t0 = m_priv_key.m_private->t0();
286 for(uint32_t nonce = 0; nonce <= std::numeric_limits<uint16_t>::max(); ++nonce) {
288 Dilithium::PolynomialVector y(mode.l());
290 y.polyvecl_uniform_gamma1(rhoprime,
static_cast<uint16_t
>(nonce), mode);
305 auto w1_w0 = w1.polyvec_decompose(mode);
307 auto packed_w1 = std::get<0>(w1_w0).polyvec_pack_w1(mode);
311 shake256_variable.update(packed_w1.data(), packed_w1.size());
312 auto sm = shake256_variable.final();
318 s1.polyvec_pointwise_poly_montgomery(z, cp);
324 if(z.polyvec_chknorm(mode.gamma1() - mode.beta())) {
330 Dilithium::PolynomialVector h(mode.k());
331 s2.polyvec_pointwise_poly_montgomery(h, cp);
333 std::get<1>(w1_w0) -= h;
334 std::get<1>(w1_w0).reduce();
336 if(std::get<1>(w1_w0).polyvec_chknorm(mode.gamma2() - mode.beta())) {
341 t0.polyvec_pointwise_poly_montgomery(h, cp);
344 if(h.polyvec_chknorm(mode.gamma2())) {
348 std::get<1>(w1_w0).add_polyvec(h);
349 std::get<1>(w1_w0).cadd_q();
353 if(n > mode.omega()) {
358 return pack_sig(sm, z, h);
361 throw Internal_Error(
"Dilithium signature loop did not terminate");
364 size_t signature_length()
const override {
365 const auto& dilithium_math = m_priv_key.m_private->mode();
366 return dilithium_math.crypto_bytes();
369 AlgorithmIdentifier algorithm_identifier()
const override;
371 std::string hash_function()
const override {
return "SHAKE-256(512)"; }
376 const Dilithium::PolynomialVector& z,
377 const Dilithium::PolynomialVector& h) {
380 const auto& mode = m_priv_key.m_private->mode();
383 std::copy(c.begin(), c.end(), sig.begin());
386 for(
size_t i = 0; i < mode.l(); ++i) {
387 z.m_vec[i].polyz_pack(&sig[position + i * mode.polyz_packedbytes()], mode);
389 position += mode.l() * mode.polyz_packedbytes();
392 for(
size_t i = 0; i < mode.omega() + mode.k(); ++i) {
393 sig[i + position] = 0;
397 for(
size_t i = 0; i < mode.k(); ++i) {
399 if(h.m_vec[i].m_coeffs[j] != 0) {
400 sig[position + k] =
static_cast<uint8_t
>(j);
404 sig[position + mode.omega() + i] =
static_cast<uint8_t
>(k);
409 const Dilithium_PrivateKey m_priv_key;
410 const Dilithium::PolynomialMatrix m_matrix;
415AlgorithmIdentifier Dilithium_Signature_Operation::algorithm_identifier()
const {
419class Dilithium_Verification_Operation
final :
public PK_Ops::Verification {
421 Dilithium_Verification_Operation(
const Dilithium_PublicKey& pub_dilithium) :
422 m_pub_key(pub_dilithium.m_public),
423 m_matrix(Dilithium::PolynomialMatrix::generate_matrix(m_pub_key->
rho(), m_pub_key->mode())),
424 m_pk_hash(m_pub_key->raw_pk_shake256()),
425 m_shake(DilithiumModeConstants::CRHBYTES * 8) {
426 m_shake.
update(m_pk_hash);
434 void update(
const uint8_t msg[],
size_t msg_len)
override { m_shake.
update(msg, msg_len); }
440 bool is_valid_signature(
const uint8_t* sig,
size_t sig_len)
override {
445 m_shake.
update(m_pk_hash);
447 const auto& mode = m_pub_key->mode();
449 if(sig_len != mode.crypto_bytes()) {
453 Dilithium::PolynomialVector z(mode.l());
454 Dilithium::PolynomialVector h(mode.k());
455 std::vector<uint8_t> signature(sig, sig + sig_len);
456 std::array<uint8_t, DilithiumModeConstants::SEEDBYTES> c;
461 if(z.polyvec_chknorm(mode.gamma1() - mode.beta())) {
469 Dilithium::PolynomialVector t1 = m_pub_key->t1();
472 t1.polyvec_pointwise_poly_montgomery(t1, cp);
482 w1.polyvec_use_hint(w1, h, mode);
483 auto packed_w1 = w1.polyvec_pack_w1(mode);
487 shake256_variable.update(mu.data(), mu.size());
488 shake256_variable.update(packed_w1.data(), packed_w1.size());
489 auto c2 = shake256_variable.final();
492 return std::equal(c.begin(), c.end(), c2.begin());
495 std::string hash_function()
const override {
return "SHAKE-256(512)"; }
498 std::shared_ptr<Dilithium_PublicKeyInternal> m_pub_key;
499 const Dilithium::PolynomialMatrix m_matrix;
500 const std::vector<uint8_t> m_pk_hash;
510 "dilithium public key does not have the correct byte count");
512 m_public = std::make_shared<Dilithium_PublicKeyInternal>(std::move(mode), pk);
528 return m_public->mode().public_key_bytes();
532 return m_public->mode().nist_security_strength();
550 return std::make_unique<Dilithium_PrivateKey>(rng,
m_public->mode().mode());
554 std::string_view provider)
const {
555 BOTAN_ARG_CHECK(params.empty() || params ==
"Pure",
"Unexpected parameters for verifying with Dilithium");
556 if(provider.empty() || provider ==
"base") {
557 return std::make_unique<Dilithium_Verification_Operation>(*
this);
564 if(provider.empty() || provider ==
"base") {
566 throw Decoding_Error(
"Unexpected AlgorithmIdentifier for Dilithium X.509 signature");
568 return std::make_unique<Dilithium_Verification_Operation>(*
this);
598 auto [t0, t1] = calculate_t0_and_t1(mode,
rho, s1, s2);
600 m_public = std::make_shared<Dilithium_PublicKeyInternal>(mode,
rho, std::move(t1));
605 m_private = std::make_shared<Dilithium_PrivateKeyInternal>(
606 std::move(mode), std::move(
rho), std::move(tr), std::move(key), std::move(s1), std::move(s2), std::move(t0));
615 m_private = std::make_shared<Dilithium_PrivateKeyInternal>(std::move(mode), sk);
616 m_public = std::make_shared<Dilithium_PublicKeyInternal>(
617 m_private->mode(), m_private->rho(), m_private->s1(), m_private->s2());
625 return m_private->raw_sk();
629 std::string_view params,
630 std::string_view provider)
const {
633 BOTAN_ARG_CHECK(params.empty() || params ==
"Deterministic" || params ==
"Randomized",
634 "Unexpected parameters for signing with Dilithium");
636 const bool randomized = (params ==
"Randomized");
637 if(provider.empty() || provider ==
"base") {
638 return std::make_unique<Dilithium_Signature_Operation>(*
this, randomized);
644 return std::make_unique<Dilithium_PublicKey>(*
this);
#define BOTAN_ASSERT_NOMSG(expr)
#define BOTAN_STATE_CHECK(expr)
#define BOTAN_ARG_CHECK(expr, msg)
#define BOTAN_ASSERT_UNREACHABLE()
void update(const uint8_t in[], size_t length)
std::vector< uint8_t > final_stdvec()
static constexpr int32_t SEEDBYTES
size_t private_key_bytes() const
static constexpr int32_t POLYT0_PACKEDBYTES
size_t polyeta_packedbytes() const
static constexpr int32_t POLYT1_PACKEDBYTES
static constexpr int32_t N
decltype(auto) H(std::span< const uint8_t > seed, size_t out_len) const
static constexpr int32_t CRHBYTES
size_t public_key_bytes() const
OID object_identifier() const
std::string to_string() const
const std::vector< PolynomialVector > & get_matrix() const
static PolynomialMatrix generate_matrix(const std::vector< uint8_t > &rho, const DilithiumModeConstants &mode)
static PolynomialVector unpack_t1(std::span< const uint8_t > packed_t1, const DilithiumModeConstants &mode)
static bool unpack_sig(std::array< uint8_t, DilithiumModeConstants::SEEDBYTES > &c, PolynomialVector &z, PolynomialVector &h, const std::vector< uint8_t > &sig, const DilithiumModeConstants &mode)
secure_vector< uint8_t > polyvec_pack_t0() const
secure_vector< uint8_t > polyvec_pack_eta(const DilithiumModeConstants &mode) const
static PolynomialVector unpack_t0(std::span< const uint8_t > buffer, const DilithiumModeConstants &mode)
std::vector< Polynomial > m_vec
static void fill_polyvec_uniform_eta(PolynomialVector &v, const secure_vector< uint8_t > &seed, uint16_t nonce, const DilithiumModeConstants &mode)
static void fill_polyvecs_power2round(PolynomialVector &v1, PolynomialVector &v0, const PolynomialVector &v)
static PolynomialVector generate_polyvec_matrix_pointwise_montgomery(const std::vector< PolynomialVector > &mat, const PolynomialVector &v, const DilithiumModeConstants &mode)
std::vector< uint8_t > polyvec_pack_t1() const
static PolynomialVector unpack_eta(std::span< const uint8_t > buffer, size_t size, const DilithiumModeConstants &mode)
static size_t generate_hint_polyvec(PolynomialVector &h, const PolynomialVector &v0, const PolynomialVector &v1, const DilithiumModeConstants &mode)
static Polynomial poly_challenge(const uint8_t *seed, const DilithiumModeConstants &mode)
Dilithium_PrivateKey(RandomNumberGenerator &rng, DilithiumMode mode)
secure_vector< uint8_t > raw_private_key_bits() const override
std::unique_ptr< PK_Ops::Signature > create_signature_op(RandomNumberGenerator &, std::string_view params, std::string_view provider) const override
secure_vector< uint8_t > private_key_bits() const override
std::unique_ptr< Public_Key > public_key() const override
AlgorithmIdentifier algorithm_identifier() const override
std::vector< uint8_t > public_key_bits() const override
OID object_identifier() const override
bool check_key(RandomNumberGenerator &, bool) const override
std::unique_ptr< Private_Key > generate_another(RandomNumberGenerator &rng) const final
std::unique_ptr< PK_Ops::Verification > create_x509_verification_op(const AlgorithmIdentifier &signature_algorithm, std::string_view provider) const override
size_t key_length() const override
std::string algo_name() const override
size_t estimated_strength() const override
std::unique_ptr< PK_Ops::Verification > create_verification_op(std::string_view params, std::string_view provider) const override
Dilithium_PublicKey()=default
std::vector< uint8_t > raw_public_key_bits() const override
std::shared_ptr< Dilithium_PublicKeyInternal > m_public
std::string to_formatted_string() const
static OID from_string(std::string_view str)
void random_vec(std::span< uint8_t > v)
int(* update)(CTX *, const void *, CC_LONG len)
int(* final)(unsigned char *, CTX *)
std::string fmt(std::string_view format, const T &... args)
constexpr auto concat(Rs &&... ranges)
std::vector< T, secure_allocator< T > > secure_vector