13#include <botan/internal/cmce_matrix.h>
15#include <botan/strong_type.h>
29CT::Mask<uint64_t> bit_at_mask(uint64_t val,
size_t pos) {
30 return CT::Mask<uint64_t>::expand((
static_cast<uint64_t
>(1) << pos) & val);
34void swap_bits(uint64_t& val,
size_t i,
size_t j) {
35 uint64_t bit_i = (val >> i) & CT::value_barrier<uint64_t>(1);
36 uint64_t bit_j = (val >> j) & CT::value_barrier<uint64_t>(1);
37 uint64_t xor_sum = bit_i ^ bit_j;
38 val ^= (xor_sum << i);
39 val ^= (xor_sum << j);
42size_t count_lsb_zeros(uint64_t n) {
45 for(
size_t bit_pos = 0; bit_pos <
sizeof(uint64_t) * 8; ++bit_pos) {
46 auto bit_set_mask = bit_at_mask(n, bit_pos);
47 found_only_zeros &= ~bit_set_mask;
48 res +=
static_cast<size_t>(found_only_zeros.if_set_return(1));
54CmceMatrix init_matrix_with_alphas(
const Classic_McEliece_Parameters& params,
55 const Classic_McEliece_Field_Ordering& field_ordering,
56 const Classic_McEliece_Minimal_Polynomial& g) {
57 auto alphas = field_ordering.alphas(params.n());
58 std::vector<Classic_McEliece_GF> inv_g_of_alpha;
59 inv_g_of_alpha.reserve(params.n());
60 for(
const auto& alpha : alphas) {
61 inv_g_of_alpha.push_back(g(alpha).inv());
63 CmceMatrix mat(std::vector<CmceMatrixRow>(params.pk_no_rows(), CmceMatrixRow(params.n())));
65 for(
size_t i = 0; i < params.t(); ++i) {
66 for(
size_t j = 0; j < params.n(); ++j) {
67 const auto inv_g = inv_g_of_alpha[j].elem().get();
68 for(
size_t alpha_i_j_bit = 0; alpha_i_j_bit < params.m(); ++alpha_i_j_bit) {
69 mat[i * params.m() + alpha_i_j_bit][j] =
static_cast<bool>((inv_g >> alpha_i_j_bit) & 1);
74 for(
size_t j = 0; j < params.n(); ++j) {
75 inv_g_of_alpha.at(j) *= alphas.at(j);
82std::optional<CmceColumnSelection> move_columns(CmceMatrix& mat,
const Classic_McEliece_Parameters& params) {
83 BOTAN_ASSERT(mat.size() == params.pk_no_rows(),
"Matrix has incorrect number of rows");
84 BOTAN_ASSERT(mat.get().at(0).size() == params.n(),
"Matrix has incorrect number of columns");
85 static_assert(Classic_McEliece_Parameters::nu() == 64,
"nu needs to be 64");
87 const size_t pos_offset = params.pk_no_rows() - Classic_McEliece_Parameters::mu();
93 std::vector<uint64_t> matrix_swap_area;
94 matrix_swap_area.reserve(params.pk_no_rows());
95 for(
size_t i = 0; i < params.pk_no_rows(); ++i) {
96 matrix_swap_area.push_back(mat[i].subvector<uint64_t>(pos_offset));
101 std::array<uint64_t, Classic_McEliece_Parameters::mu()> sub_mat;
104 for(
size_t i = 0; i < Classic_McEliece_Parameters::mu(); i++) {
105 sub_mat[i] = matrix_swap_area[pos_offset + i];
108 std::array<size_t, Classic_McEliece_Parameters::mu()> pivot_indices = {0};
113 for(
size_t row_idx = 0; row_idx < Classic_McEliece_Parameters::mu(); ++row_idx) {
115 auto row_acc = sub_mat.at(row_idx);
116 for(
size_t next_row = row_idx + 1; next_row < Classic_McEliece_Parameters::mu(); ++next_row) {
117 row_acc |= sub_mat.at(next_row);
120 auto semi_systematic_form_failed = CT::Mask<uint64_t>::is_zero(row_acc);
121 if(semi_systematic_form_failed.as_choice().as_bool()) {
130 size_t current_pivot_idx = count_lsb_zeros(row_acc);
131 pivot_indices.at(row_idx) = current_pivot_idx;
135 for(
size_t next_row = row_idx + 1; next_row < Classic_McEliece_Parameters::mu(); ++next_row) {
137 auto add_next_row_mask = ~bit_at_mask(sub_mat.at(row_idx), current_pivot_idx);
138 sub_mat.at(row_idx) ^= add_next_row_mask.if_set_return(sub_mat.at(next_row));
147 for(
size_t next_row = row_idx + 1; next_row < Classic_McEliece_Parameters::mu(); ++next_row) {
149 auto add_to_next_row_mask = bit_at_mask(sub_mat.at(next_row), current_pivot_idx);
150 sub_mat.at(next_row) ^= add_to_next_row_mask.if_set_return(sub_mat.at(row_idx));
156 for(
auto pivot_idx : pivot_indices) {
157 for(
size_t i = 0; i < Classic_McEliece_Parameters::nu(); ++i) {
159 pivots.at(i) =
static_cast<bool>(mask_is_at_current_idx.select(1, pivots.at(i).as<
size_t>()));
164 for(
size_t mat_row = 0; mat_row < params.pk_no_rows(); ++mat_row) {
165 for(
size_t col = 0; col < Classic_McEliece_Parameters::mu(); ++col) {
166 swap_bits(matrix_swap_area.at(mat_row), col, pivot_indices.at(col));
171 for(
size_t row = 0; row < params.pk_no_rows(); ++row) {
172 mat[row].subvector_replace(pos_offset, matrix_swap_area[row]);
178std::optional<CmceColumnSelection> apply_gauss(
const Classic_McEliece_Parameters& params, CmceMatrix& mat) {
179 BOTAN_ASSERT(mat.size() == params.pk_no_rows(),
"Matrix has incorrect number of rows");
180 BOTAN_ASSERT(mat.get().at(0).size() == params.n(),
"Matrix has incorrect number of columns");
186 for(
size_t diag_pos = 0; diag_pos < params.pk_no_rows(); ++diag_pos) {
187 if(params.is_f() && diag_pos == params.pk_no_rows() - params.mu()) {
188 auto ret_pivots = move_columns(mat, params);
189 bool move_columns_failed = !ret_pivots.has_value();
190 CT::unpoison(move_columns_failed);
191 if(move_columns_failed) {
194 pivots = std::move(ret_pivots.value());
202 for(
size_t next_row = diag_pos + 1; next_row < params.pk_no_rows(); ++next_row) {
203 mat[diag_pos].get().ct_conditional_xor(!mat[diag_pos].at(diag_pos).as_choice(), mat[next_row].get());
208 bool diag_bit_zero = !mat[diag_pos].at(diag_pos);
209 CT::unpoison(diag_bit_zero);
217 for(
size_t row = 0; row < params.pk_no_rows(); ++row) {
218 if(row != diag_pos) {
219 mat[row].get().ct_conditional_xor(mat[row].at(diag_pos).as_choice(), mat[diag_pos].get());
227std::vector<uint8_t> extract_pk_bytes_from_matrix(
const Classic_McEliece_Parameters& params,
const CmceMatrix& mat) {
230 std::vector<uint8_t> big_t(params.pk_size_bytes());
231 auto big_t_stuffer = BufferStuffer(big_t);
233 for(
size_t row = 0; row < params.pk_no_rows(); ++row) {
234 mat[row].subvector(params.pk_no_rows()).to_bytes(big_t_stuffer.next(params.pk_row_size_bytes()));
248 auto mat = init_matrix_with_alphas(params, field_ordering, g);
249 auto pivots = apply_gauss(params, mat);
251 auto gauss_failed = !pivots.has_value();
257 auto pk_mat_bytes = extract_pk_bytes_from_matrix(params, mat);
261std::optional<std::pair<Classic_McEliece_Matrix, CmceColumnSelection>>
265 auto pk_matrix_and_pivots =
create_matrix(params, field_ordering, g);
267 bool matrix_creation_failed = !pk_matrix_and_pivots.has_value();
269 if(matrix_creation_failed) {
273 auto& [_, pivots] = pk_matrix_and_pivots.value();
279 return pk_matrix_and_pivots;
287 for(
size_t i = 0; i < params.
pk_no_rows(); ++i) {
291 s[i] ^= row.has_odd_hamming_weight().as_bool();
#define BOTAN_ASSERT_NOMSG(expr)
#define BOTAN_ASSERT(expr, assertion_made)
static constexpr Mask< T > set()
static constexpr Mask< T > is_equal(T x, T y)
Represents a field ordering for the Classic McEliece cryptosystem.
void permute_with_pivots(const Classic_McEliece_Parameters ¶ms, const CmceColumnSelection &pivots)
Permute the field ordering with the given pivots.
static std::optional< std::pair< Classic_McEliece_Matrix, CmceColumnSelection > > create_matrix(const Classic_McEliece_Parameters ¶ms, const Classic_McEliece_Field_Ordering &field_ordering, const Classic_McEliece_Minimal_Polynomial &g)
Create the matrix H for a Classic McEliece instance given its parameters, field ordering and minimal ...
CmceCodeWord mul(const Classic_McEliece_Parameters ¶ms, const CmceErrorVector &e) const
Multiply the Classic McEliece matrix H with a bitvector e.
static std::optional< std::pair< Classic_McEliece_Matrix, CmceColumnSelection > > create_matrix_and_apply_pivots(const Classic_McEliece_Parameters ¶ms, Classic_McEliece_Field_Ordering &field_ordering, const Classic_McEliece_Minimal_Polynomial &g)
Create the matrix H for a Classic McEliece instance given its parameters, field ordering and minimal ...
Classic_McEliece_Matrix(const Classic_McEliece_Parameters ¶ms, std::vector< uint8_t > mat_bytes)
Create a Classic_McEliece_Matrix from bytes.
Representation of a minimal polynomial in GF(q)[y].
size_t pk_no_rows() const
The number of rows in the public key's matrix.
size_t pk_row_size_bytes() const
The number of bytes for each row in the public key's matrix.
size_t n() const
The code length of the Classic McEliece instance.
auto subvector(size_type pos, std::optional< size_type > length=std::nullopt) const
constexpr void unpoison(const T *p, size_t n)
Strong< secure_bitvector, struct CmceCodeWord_ > CmceCodeWord
Represents C of decapsulation.
bitvector_base< secure_allocator > secure_bitvector
BOTAN_FORCE_INLINE constexpr void swap_bits(T &x, T &y, T mask, size_t shift)
Strong< secure_bitvector, struct CmceErrorVector_ > CmceErrorVector
Represents e of encapsulation.
Strong< secure_bitvector, struct CmceColumnSelection_ > CmceColumnSelection
Represents c of private key.