13#include <botan/internal/frodo_matrix.h>
15#include <botan/assert.h>
17#include <botan/internal/bit_ops.h>
18#include <botan/internal/frodo_constants.h>
19#include <botan/internal/loadstor.h>
26#if defined(BOTAN_HAS_FRODOKEM_AES)
27 #include <botan/internal/frodo_aes_generator.h>
30#if defined(BOTAN_HAS_FRODOKEM_SHAKE)
31 #include <botan/internal/frodo_shake_generator.h>
50 return constants.mode().is_aes() ? 16 : 512;
53std::function<void(std::span<uint8_t> out, uint16_t first_row,
size_t nrows)> make_row_generator(
55#if defined(BOTAN_HAS_FRODOKEM_AES)
56 if(constants.mode().is_aes()) {
61#if defined(BOTAN_HAS_FRODOKEM_SHAKE)
62 if(constants.mode().is_shake()) {
78 const auto n = r.
size() / 2;
80 auto elements = make_elements_vector(
dimensions);
85 std::array<uint16_t, 16> cdf{};
88 for(
size_t j = 0; j != cdf_len; ++j) {
92 for(
auto& elem : elements) {
99 for(
size_t j = 0; j < cdf_len - 1; ++j) {
104 const uint16_t sample_u16 =
static_cast<uint16_t
>(
sample);
106 elem = sign.select(~sample_u16 + 1, sample_u16);
122 m_dim1(std::get<0>(dims)), m_dim2(std::get<1>(dims)), m_elements(make_elements_vector(dims)) {}
130 "FrodoMatrix dimension mismatch of E and S");
132 "FrodoMatrix dimension mismatch of new matrix dimensions and E");
134 auto elements = make_elements_vector(e.
dimensions());
135 const auto row_generator = make_row_generator(constants, seed_a);
142 const size_t row_chunk = frodo_row_chunk(constants);
143 std::vector<uint16_t> a_row_data(row_chunk * constants.
n(), 0);
146 const std::span<uint8_t> a_row_data_bytes(
reinterpret_cast<uint8_t*
>(a_row_data.data()),
147 sizeof(uint16_t) * a_row_data.size());
149 for(
size_t i = 0; i < constants.
n(); i += row_chunk) {
150 const size_t rows = std::min(row_chunk, constants.
n() - i);
152 row_generator(a_row_data_bytes.first(rows * constants.
n() *
sizeof(uint16_t)),
static_cast<uint16_t
>(i), rows);
156 if constexpr(std::endian::native == std::endian::big) {
161 for(
size_t r = 0; r < rows; r += 4) {
162 for(
size_t k = 0; k < constants.
n_bar(); ++k) {
163 std::array<uint16_t, 4> sum = {0};
164 for(
size_t j = 0; j < constants.
n(); ++j) {
169 const uint32_t sp = s.
elements_at(k * constants.
n() + j);
172 sum[0] +=
static_cast<uint16_t
>(a_row_data[(r + 0) * constants.
n() + j] * sp);
173 sum[1] +=
static_cast<uint16_t
>(a_row_data[(r + 1) * constants.
n() + j] * sp);
174 sum[2] +=
static_cast<uint16_t
>(a_row_data[(r + 2) * constants.
n() + j] * sp);
175 sum[3] +=
static_cast<uint16_t
>(a_row_data[(r + 3) * constants.
n() + j] * sp);
177 elements.at((i + r + 0) * constants.
n_bar() + k) =
179 elements.at((i + r + 3) * constants.
n_bar() + k) =
181 elements.at((i + r + 2) * constants.
n_bar() + k) =
183 elements.at((i + r + 1) * constants.
n_bar() + k) =
198 "FrodoMatrix dimension mismatch of E and S");
200 "FrodoMatrix dimension mismatch of new matrix dimensions and E");
202 auto elements = e.m_elements;
203 const auto row_generator = make_row_generator(constants, seed_a);
210 const size_t row_chunk = frodo_row_chunk(constants);
211 std::vector<uint16_t> a_row_data(row_chunk * constants.
n(), 0);
213 const std::span<uint8_t> a_row_data_bytes(
reinterpret_cast<uint8_t*
>(a_row_data.data()),
214 sizeof(uint16_t) * a_row_data.size());
217 for(
size_t i = 0; i < constants.
n(); i += row_chunk) {
218 const size_t rows = std::min(row_chunk, constants.
n() - i);
220 row_generator(a_row_data_bytes.first(rows * constants.
n() *
sizeof(uint16_t)),
static_cast<uint16_t
>(i), rows);
224 if constexpr(std::endian::native == std::endian::big) {
229 for(
size_t r = 0; r < rows; r += 8) {
230 for(
size_t j = 0; j < constants.
n_bar(); ++j) {
232 std::array<uint32_t , 8> sp{};
233 for(
size_t p = 0; p < 8; ++p) {
236 for(
size_t q = 0; q < constants.
n(); ++q) {
237 sum = elements[j * constants.
n() + q];
238 for(
size_t p = 0; p < 8; ++p) {
239 sum +=
static_cast<uint16_t
>(sp[p] * a_row_data[(r + p) * constants.
n() + q]);
241 elements[j * constants.
n() + q] = sum;
256 "FrodoMatrix dimension mismatch of B and S");
258 "FrodoMatrix dimension mismatch of B");
260 "FrodoMatrix dimension mismatch of E");
262 auto elements = make_elements_vector(e.
dimensions());
264 for(
size_t k = 0; k < constants.
n_bar(); ++k) {
265 for(
size_t i = 0; i < constants.
n_bar(); ++i) {
267 for(
size_t j = 0; j < constants.
n(); ++j) {
268 elements.at(k * constants.
n_bar() + i) +=
static_cast<uint16_t
>(
269 static_cast<uint32_t
>(s.
elements_at(k * constants.
n() + j)) *
279 const uint64_t mask = (uint64_t(1) << constants.
b()) - 1;
282 auto elements = make_elements_vector(
dimensions);
287 for(
size_t i = 0; i < (constants.
n_bar() * constants.
n_bar()) / 8; ++i) {
289 for(
size_t j = 0; j < constants.
b(); ++j) {
290 temp |=
static_cast<uint64_t
>(in[i * constants.
b() + j]) << (8 * j);
292 for(
size_t j = 0; j < 8; ++j) {
293 elements.at(pos++) =
static_cast<uint16_t
>((temp & mask) << (constants.
d() - constants.
b()));
294 temp >>= constants.
b();
307 auto elements = make_elements_vector(a.
dimensions());
309 for(
size_t i = 0; i < constants.
n_bar() * constants.
n_bar(); ++i) {
322 auto elements = make_elements_vector(a.
dimensions());
324 for(
size_t i = 0; i < constants.
n_bar() * constants.
n_bar(); ++i) {
334 return CT::is_equal(
reinterpret_cast<const uint8_t*
>(m_elements.data()),
335 reinterpret_cast<const uint8_t*
>(other.m_elements.data()),
336 sizeof(
decltype(m_elements)::value_type) * m_elements.size());
341 auto elements = make_elements_vector(
dimensions);
343 for(
size_t i = 0; i < constants.
n_bar(); ++i) {
344 for(
size_t j = 0; j < constants.
n_bar(); ++j) {
345 auto& current = elements.at(i * constants.
n_bar() + j);
347 for(
size_t k = 0; k < constants.
n(); ++k) {
349 const uint32_t b_ink = b.
elements_at(i * constants.
n() + k);
352 const uint32_t s_ink = s.
elements_at(j * constants.
n() + k);
354 current +=
static_cast<uint16_t
>(b_ink * s_ink);
388 const uint8_t nbits = std::min(
static_cast<uint8_t
>(8 - b), bits);
389 const uint16_t mask =
static_cast<uint16_t
>(1 << nbits) - 1;
390 const auto t =
static_cast<uint8_t
>((w >> (bits - nbits)) & mask);
391 out[i] = out[i] +
static_cast<uint8_t
>(t << (8 - b - nbits));
397 w = m_elements.at(j);
398 bits =
static_cast<uint8_t
>(constants.
d());
414 for(
unsigned int i = 0; i < m_elements.size(); ++i) {
422 const size_t nwords = (constants.
n_bar() * constants.
n_bar()) / 8;
423 const uint16_t maskex =
static_cast<uint16_t
>(1 << constants.
b()) - 1;
424 const uint16_t maskq =
static_cast<uint16_t
>(1 << constants.
d()) - 1;
429 for(
size_t i = 0; i < nwords; i++) {
430 uint64_t templong = 0;
431 for(
size_t j = 0; j < 8; j++) {
433 static_cast<uint16_t
>(((m_elements.at(index) & maskq) + (1 << (constants.
d() - constants.
b() - 1))) >>
434 (constants.
d() - constants.
b()));
435 templong |=
static_cast<uint64_t
>(temp & maskex) << (constants.
b() * j);
438 for(
size_t j = 0; j < constants.
b(); j++) {
439 out[i * constants.
b() + j] = (templong >> (8 * j)) & 0xFF;
449 const uint8_t lsb =
static_cast<uint8_t
>(constants.
d());
450 const size_t inlen = packed_bytes.
size();
455 auto elements = make_elements_vector(
dimensions);
462 while(i < outlen && (j < inlen || ((j == inlen) && (bits > 0)))) {
476 const uint8_t nbits = std::min(
static_cast<uint8_t
>(lsb - b), bits);
477 const uint16_t mask =
static_cast<uint16_t
>(1 << nbits) - 1;
478 const uint8_t t = (w >> (bits - nbits)) & mask;
480 elements.at(i) = elements.at(i) +
static_cast<uint16_t
>(t << (lsb - b - nbits));
483 w &=
static_cast<uint8_t
>(~(mask << bits));
504 auto elements = make_elements_vector(
dimensions);
512 if(constants.
d() <
sizeof(
decltype(m_elements)::value_type) * 8) {
513 const uint16_t mask =
static_cast<uint16_t
>(1 << constants.
d()) - 1;
514 for(
auto& elem : m_elements) {
#define BOTAN_ASSERT_NOMSG(expr)
#define BOTAN_ASSERT(expr, assertion_made)
#define BOTAN_ASSERT_UNREACHABLE()
static constexpr Mask< T > expand_bit(T v, size_t bit)
static constexpr Mask< T > is_lt(T x, T y)
uint16_t cdf_table_at(size_t i) const
size_t cdf_table_len() const
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)
void reduce(const FrodoKEMConstants &constants)
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)
FrodoPlaintext decode(const FrodoKEMConstants &constants) const
static FrodoMatrix add(const FrodoKEMConstants &constants, const FrodoMatrix &a, const FrodoMatrix &b)
std::tuple< size_t, size_t > Dimensions
static FrodoMatrix sample(const FrodoKEMConstants &constants, const Dimensions &dimensions, StrongSpan< const FrodoSampleR > r)
CT::Mask< uint8_t > constant_time_compare(const FrodoMatrix &other) const
FrodoPackedMatrix pack(const FrodoKEMConstants &constants) const
static FrodoMatrix encode(const FrodoKEMConstants &constants, StrongSpan< const FrodoPlaintext > in)
Dimensions dimensions() const
FrodoMatrix(Dimensions dims)
static FrodoMatrix unpack(const FrodoKEMConstants &constants, const Dimensions &dimensions, StrongSpan< const FrodoPackedMatrix > packed_bytes)
uint16_t elements_at(size_t i) const
size_t element_count() const
static FrodoMatrix mul_bs(const FrodoKEMConstants &constants, const FrodoMatrix &b_p, const FrodoMatrix &s)
static FrodoMatrix deserialize(const Dimensions &dimensions, StrongSpan< const FrodoSerializedMatrix > bytes)
size_t packed_size(const FrodoKEMConstants &constants) const
FrodoSerializedMatrix serialize() const
decltype(auto) data() noexcept(noexcept(this->m_span.data()))
decltype(auto) size() const noexcept(noexcept(this->m_span.size()))
decltype(auto) data() noexcept(noexcept(this->get().data()))
constexpr T value_barrier(T x)
constexpr CT::Mask< T > is_equal(const T x[], const T y[], size_t len)
Strong< secure_vector< uint8_t >, struct FrodoSerializedMatrix_ > FrodoSerializedMatrix
auto create_shake_row_generator(const FrodoKEMConstants &constants, StrongSpan< const FrodoSeedA > seed_a)
constexpr auto store_le(ParamTs &&... params)
auto create_aes_row_generator(const FrodoKEMConstants &constants, StrongSpan< const FrodoSeedA > seed_a)
BOTAN_FORCE_INLINE constexpr T ceil_tobytes(T bits)
constexpr auto load_le(ParamTs &&... params)
std::vector< T, secure_allocator< T > > secure_vector
Strong< secure_vector< uint8_t >, struct FrodoPlaintext_ > FrodoPlaintext
Strong< secure_vector< uint8_t >, struct FrodoSampleR_ > FrodoSampleR
constexpr void clear_mem(T *ptr, size_t n)