13#include <botan/frodokem.h>
15#include <botan/assert.h>
16#include <botan/pubkey.h>
19#include <botan/internal/buffer_slicer.h>
20#include <botan/internal/buffer_stuffer.h>
21#include <botan/internal/concat_util.h>
22#include <botan/internal/ct_utils.h>
23#include <botan/internal/frodo_constants.h>
24#include <botan/internal/frodo_matrix.h>
25#include <botan/internal/frodo_types.h>
26#include <botan/internal/pk_ops_impl.h>
27#include <botan/internal/pk_options_impl.h>
35class FrodoKEM_PublicKeyInternal final {
37 FrodoKEM_PublicKeyInternal(FrodoKEMConstants constants,
FrodoSeedA seed_a, FrodoMatrix b) :
38 m_constants(std::move(constants)), m_seed_a(std::move(seed_a)), m_b(std::move(b)) {
39 auto shake = m_constants.create_xof();
40 shake->update(serialize());
44 const FrodoKEMConstants& constants()
const {
return m_constants; }
46 const FrodoSeedA& seed_a()
const {
return m_seed_a; }
48 const FrodoMatrix& b()
const {
return m_b; }
55 FrodoKEMConstants m_constants;
61class FrodoKEM_PrivateKeyInternal final {
63 FrodoKEM_PrivateKeyInternal(
FrodoSeedS s, FrodoMatrix s_trans) :
64 m_s(std::move(s)), m_s_trans(std::move(s_trans)) {}
68 const FrodoMatrix& s_trans()
const {
return m_s_trans; }
70 constexpr void _const_time_poison()
const {
CT::poison_all(m_s, m_s_trans); }
72 constexpr void _const_time_unpoison()
const {
CT::unpoison_all(m_s, m_s_trans); }
76 FrodoMatrix m_s_trans;
88 Frodo_KEM_Encryptor(std::shared_ptr<const FrodoKEM_PublicKeyInternal> key,
const PK_KEM_Options_Reader& options) :
91 size_t raw_kem_shared_key_length()
const override {
return m_public_key->constants().len_sec_bytes(); }
93 size_t encapsulated_key_length()
const override {
return m_public_key->constants().len_ct_bytes(); }
95 void raw_kem_encrypt(std::span<uint8_t> out_encapsulated_key,
96 std::span<uint8_t> out_shared_key,
97 RandomNumberGenerator& rng)
override {
98 const auto& constants = m_public_key->constants();
99 auto shake = constants.create_xof();
102 BufferStuffer out_ct_bs(out_encapsulated_key);
104 const auto c_1 = out_ct_bs.next<
FrodoPackedMatrix>(constants.len_packed_b_bytes());
105 const auto c_2 = out_ct_bs.next<
FrodoPackedMatrix>(constants.len_packed_c_bytes());
106 auto salt = out_ct_bs.next<
FrodoSalt>(constants.len_salt_bytes());
110 const auto u = rng.random_vec<
FrodoPlaintext>(constants.len_sec_bytes());
115 shake->update(m_public_key->hash());
118 const auto seed_se = shake->output<
FrodoSeedSE>(constants.len_se_bytes());
122 shake->update(constants.encapsulation_domain_separator());
123 shake->update(seed_se);
125 const auto s_p = sample_generator(std::tuple(constants.n_bar(), constants.n()));
127 const auto e_p = sample_generator(std::tuple(constants.n_bar(), constants.n()));
131 b_p.pack(constants, c_1);
133 const auto e_pp = sample_generator(std::tuple(constants.n_bar(), constants.n_bar()));
142 c.pack(constants, c_2);
144 shake->update(out_encapsulated_key);
146 shake->output(out_shared_key);
152 std::shared_ptr<const FrodoKEM_PublicKeyInternal> m_public_key;
157 Frodo_KEM_Decryptor(std::shared_ptr<const FrodoKEM_PublicKeyInternal> public_key,
158 std::shared_ptr<const FrodoKEM_PrivateKeyInternal> private_key,
159 const PK_KEM_Options_Reader& options) :
161 m_public_key(std::move(public_key)),
162 m_private_key(std::move(private_key)) {}
164 size_t raw_kem_shared_key_length()
const override {
return m_public_key->constants().len_sec_bytes(); }
166 size_t encapsulated_key_length()
const override {
return m_public_key->constants().len_ct_bytes(); }
168 void raw_kem_decrypt(std::span<uint8_t> out_shared_key, std::span<const uint8_t> encapsulated_key)
override {
171 const auto& constants = m_public_key->constants();
172 auto shake = constants.create_xof();
175 if(encapsulated_key.size() != constants.len_ct_bytes()) {
176 throw Invalid_Argument(
"FrodoKEM ciphertext does not have the correct byte count");
179 BufferSlicer ct_bs(encapsulated_key);
182 auto salt = ct_bs.take<
FrodoSalt>(constants.len_salt_bytes());
186 const auto c =
FrodoMatrix::unpack(constants, {constants.n_bar(), constants.n_bar()}, c_2);
191 const auto seed_u_p = m.decode(constants);
193 shake->update(m_public_key->hash());
194 shake->update(seed_u_p);
197 const auto seed_se_p = shake->output<
FrodoSeedSE>(constants.len_se_bytes());
201 shake->update(constants.encapsulation_domain_separator());
202 shake->update(seed_se_p);
203 const auto s_p = sample_generator(std::tuple(constants.n_bar(), constants.n()));
205 const auto e_p = sample_generator(std::tuple(constants.n_bar(), constants.n()));
209 const auto e_pp = sample_generator(std::tuple(constants.n_bar(), constants.n_bar()));
220 b_pp.reduce(constants);
221 c_p.reduce(constants);
226 const auto cmp = b_p.constant_time_compare(b_pp) & c.constant_time_compare(c_p);
231 shake->update(encapsulated_key);
232 shake->update(k_bar);
233 shake->output(out_shared_key);
239 std::shared_ptr<const FrodoKEM_PublicKeyInternal> m_public_key;
240 std::shared_ptr<const FrodoKEM_PrivateKeyInternal> m_private_key;
246 const auto bound =
static_cast<uint16_t
>(constants.cdf_table_len() - 1);
248 for(
size_t i = 0; i != s_trans.element_count(); ++i) {
250 const auto shifted =
static_cast<uint16_t
>(s_trans.elements_at(i) + bound);
253 return in_range.as_bool();
265 throw Decoding_Error(
"FrodoKEM public key does not have the correct byte count");
275 m_public = std::make_shared<FrodoKEM_PublicKeyInternal>(std::move(constants), std::move(seed_a), std::move(b));
282 throw Decoding_Error(
"Unexpected parameters for FrodoKEM public key");
287 m_public = std::make_shared<FrodoKEM_PublicKeyInternal>(
293 m_public = std::make_shared<FrodoKEM_PublicKeyInternal>(
304 return m_public->constants().mode().object_identifier();
312 return m_public->constants().estimated_strength();
334 return std::make_unique<FrodoKEM_PrivateKey>(rng,
m_public->constants().mode());
341 return std::make_unique<Frodo_KEM_Encryptor>(
m_public, options);
363 shake->update(seed_se);
366 auto s_trans = sample_generator(std::tuple(constants.
n_bar(), constants.
n()));
367 const auto e = sample_generator(std::tuple(constants.
n(), constants.
n_bar()));
374 m_public = std::make_shared<FrodoKEM_PublicKeyInternal>(std::move(constants), std::move(seed_a), std::move(b));
375 m_private = std::make_shared<FrodoKEM_PrivateKeyInternal>(std::move(s), std::move(s_trans));
382 throw Decoding_Error(
"FrodoKEM private key does not have the correct byte count");
395 if(!s_trans_in_range(constants, s_trans)) {
396 throw Decoding_Error(
"FrodoKEM private key matrix entry is out of range");
399 m_public = std::make_shared<FrodoKEM_PublicKeyInternal>(std::move(constants), std::move(seed_a), std::move(b));
400 m_private = std::make_shared<FrodoKEM_PrivateKeyInternal>(std::move(s), std::move(s_trans));
403 throw Decoding_Error(
"FrodoKEM embedded public key hash did not match recomputed value");
411 throw Decoding_Error(
"Unexpected parameters for FrodoKEM private key");
416 return std::make_unique<FrodoKEM_PublicKey>(*
this);
428 const auto K_prime = dec.
decrypt(c);
443 m_private->s_trans().serialize(),
452 return std::make_unique<Frodo_KEM_Decryptor>(
m_public, m_private, options);
#define BOTAN_ASSERT_NOMSG(expr)
bool parameters_are_empty() const
auto copy(const size_t count)
std::span< const uint8_t > take(const size_t count)
static constexpr Mask< T > is_lte(T x, T y)
static constexpr Mask< T > set()
FrodoDomainSeparator keygen_domain_separator() const
size_t len_private_key_bytes() const
size_t len_public_key_bytes() const
std::unique_ptr< XOF > create_xof() const
size_t len_sec_bytes() const
size_t len_se_bytes() const
size_t len_a_bytes() const
FrodoKEM_PrivateKey(RandomNumberGenerator &rng, FrodoKEMMode mode)
secure_vector< uint8_t > raw_private_key_bits() const override
bool check_key(RandomNumberGenerator &rng, bool strong) const override
std::unique_ptr< PK_Ops::KEM_Decryption > _create_kem_decryption_op(RandomNumberGenerator &rng, const PK_KEM_Options_Reader &options) const override
secure_vector< uint8_t > private_key_bits() const override
std::unique_ptr< Public_Key > public_key() const override
size_t estimated_strength() const override
std::shared_ptr< const FrodoKEM_PublicKeyInternal > m_public
std::unique_ptr< PK_Ops::KEM_Encryption > _create_kem_encryption_op(const PK_KEM_Options_Reader &options) const override
AlgorithmIdentifier algorithm_identifier() const override
size_t key_length() const override
FrodoKEM_PublicKey(std::span< const uint8_t > pub_key, FrodoKEMMode mode)
std::unique_ptr< Private_Key > generate_another(RandomNumberGenerator &rng) const final
std::vector< uint8_t > public_key_bits() const override
FrodoKEM_PublicKey & operator=(const FrodoKEM_PublicKey &other)
std::string algo_name() const override
bool check_key(RandomNumberGenerator &rng, bool strong) const override
std::vector< uint8_t > raw_public_key_bits() const override
FrodoKEM_PublicKey()=default
OID object_identifier() const override
static FrodoMatrix mul_add_sa_plus_e(const FrodoKEMConstants &constants, const FrodoMatrix &s, const FrodoMatrix &e, StrongSpan< const FrodoSeedA > seed_a)
static std::function< FrodoMatrix(const Dimensions &dimensions)> make_sample_generator(const FrodoKEMConstants &constants, Botan::XOF &shake)
static FrodoMatrix mul_add_sb_plus_e(const FrodoKEMConstants &constants, const FrodoMatrix &b, const FrodoMatrix &s, const FrodoMatrix &e)
static FrodoMatrix mul_add_as_plus_e(const FrodoKEMConstants &constants, const FrodoMatrix &s, const FrodoMatrix &e, StrongSpan< const FrodoSeedA > seed_a)
static FrodoMatrix sub(const FrodoKEMConstants &constants, const FrodoMatrix &a, const FrodoMatrix &b)
static FrodoMatrix add(const FrodoKEMConstants &constants, const FrodoMatrix &a, const FrodoMatrix &b)
static FrodoMatrix encode(const FrodoKEMConstants &constants, StrongSpan< const FrodoPlaintext > in)
static FrodoMatrix unpack(const FrodoKEMConstants &constants, const Dimensions &dimensions, StrongSpan< const FrodoPackedMatrix > packed_bytes)
static FrodoMatrix mul_bs(const FrodoKEMConstants &constants, const FrodoMatrix &b_p, const FrodoMatrix &s)
static FrodoMatrix deserialize(const Dimensions &dimensions, StrongSpan< const FrodoSerializedMatrix > bytes)
static std::pair< std::vector< uint8_t >, secure_vector< uint8_t > > destructure(KEM_Encapsulation &&kem)
void decrypt(std::span< uint8_t > out_shared_key, std::span< const uint8_t > encap_key, size_t desired_shared_key_len=32, std::span< const uint8_t > salt={})
KEM_Encapsulation encrypt(RandomNumberGenerator &rng, size_t desired_shared_key_len=32, std::span< const uint8_t > salt={})
void random_vec(std::span< uint8_t > v)
constexpr Mask< T > conditional_copy_mem(Mask< T > mask, T *dest, const T *if_set, const T *if_unset, size_t elems)
constexpr void poison_all(const Ts &... ts)
constexpr auto scoped_poison(const Ts &... xs)
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)
Strong< secure_vector< uint8_t >, struct FrodoSeedSE_ > FrodoSeedSE
Strong< secure_vector< uint8_t >, struct FrodoSerializedMatrix_ > FrodoSerializedMatrix
Strong< std::vector< uint8_t >, struct FrodoSeedZ_ > FrodoSeedZ
Strong< secure_vector< uint8_t >, struct FrodoIntermediateSharedSecret_ > FrodoIntermediateSharedSecret
Strong< std::vector< uint8_t >, struct FrodoPublicKeyHash_ > FrodoPublicKeyHash
void require_software_provider(const OptionsT &options, std::string_view algo_name)
constexpr auto concat(Rs &&... ranges)
std::vector< T, secure_allocator< T > > secure_vector
Strong< std::vector< uint8_t >, struct FrodoSeedA_ > FrodoSeedA
Strong< secure_vector< uint8_t >, struct FrodoPlaintext_ > FrodoPlaintext
Strong< std::vector< uint8_t >, struct FrodoSalt_ > FrodoSalt
Strong< std::vector< uint8_t >, struct FrodoPackedMatrix_ > FrodoPackedMatrix
Strong< secure_vector< uint8_t >, struct FrodoSeedS_ > FrodoSeedS