Botan 3.9.0
Crypto and TLS for C&
cmce_matrix.cpp
Go to the documentation of this file.
1/*
2 * Classic McEliece Matrix Logic
3 * Based on the public domain reference implementation by the designers
4 * (https://classic.mceliece.org/impl.html - released in Oct 2022 for NISTPQC-R4)
5 *
6 *
7 * (C) 2023 Jack Lloyd
8 * 2023,2024 Fabian Albert, Amos Treiber - Rohde & Schwarz Cybersecurity
9 *
10 * Botan is released under the Simplified BSD License (see license.txt)
11 **/
12
13#include <botan/internal/cmce_matrix.h>
14
15#include <botan/strong_type.h>
16
17namespace Botan {
18
19namespace {
20
21// Strong types for matrix used internally by Classic_McEliece_Matrix
23using CmceMatrix = Strong<std::vector<CmceMatrixRow>, struct CmceMatrix_>;
24
25} // Anonymous namespace
26
27namespace {
28
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);
31}
32
33/// Swaps bit i with bit j in 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);
40}
41
42size_t count_lsb_zeros(uint64_t n) {
43 size_t res = 0;
44 auto found_only_zeros = Botan::CT::Mask<uint64_t>::set();
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));
49 }
50
51 return res;
52}
53
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());
62 }
63 CmceMatrix mat(std::vector<CmceMatrixRow>(params.pk_no_rows(), CmceMatrixRow(params.n())));
64
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);
70 }
71 }
72 // Update for the next i so that:
73 // inv_g_of_alpha[j] = h_i_j = alpha_j^i/g(alpha_j)
74 for(size_t j = 0; j < params.n(); ++j) {
75 inv_g_of_alpha.at(j) *= alphas.at(j);
76 }
77 }
78
79 return mat;
80}
81
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");
86
87 const size_t pos_offset = params.pk_no_rows() - Classic_McEliece_Parameters::mu();
88
89 // Get the area of the matrix that needs to be (potentially) swapped.
90 // Its the sub m*t x nu matrix at column m*t - mu. For const time reasons,
91 // the sub-matrix is represented as an array of uint64_ts, where the 1st
92 // bit is the least significant bit
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));
97 }
98
99 // To find which columns need to be swapped to allow for a systematic matrix form, we need to
100 // investigate how a gauss algorithm affects the last mu rows of the swap area.
101 std::array<uint64_t, Classic_McEliece_Parameters::mu()> sub_mat; // NOLINT(*-member-init)
102
103 // Extract the bottom mu x nu matrix at offset pos_offset
104 for(size_t i = 0; i < Classic_McEliece_Parameters::mu(); i++) {
105 sub_mat[i] = matrix_swap_area[pos_offset + i];
106 }
107
108 std::array<size_t, Classic_McEliece_Parameters::mu()> pivot_indices = {0}; // ctz_list
109
110 // Identify the pivot indices, i.e., the indices of the leading ones for all rows
111 // when transforming the matrix into semi-systematic form. This algorithm is a modified
112 // Gauss algorithm.
113 for(size_t row_idx = 0; row_idx < Classic_McEliece_Parameters::mu(); ++row_idx) {
114 // Identify pivots (index of first 1) by OR-ing all subsequent rows into row_acc
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);
118 }
119
120 auto semi_systematic_form_failed = CT::Mask<uint64_t>::is_zero(row_acc);
121 if(semi_systematic_form_failed.as_choice().as_bool()) {
122 // If the current row and all subsequent rows are zero
123 // we cannot create a semi-systematic matrix
124 return std::nullopt;
125 }
126
127 // Using the row accumulator we can predict the index of the pivot
128 // bit for the current row, i.e., the first index where we can set
129 // the bit to one row by adding any subsequent row
130 size_t current_pivot_idx = count_lsb_zeros(row_acc);
131 pivot_indices.at(row_idx) = current_pivot_idx;
132
133 // Add subsequent rows to the current row, until the pivot
134 // bit is set.
135 for(size_t next_row = row_idx + 1; next_row < Classic_McEliece_Parameters::mu(); ++next_row) {
136 // Add next row if the pivot bit is still zero
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));
139 }
140
141 // Add the (new) current row to all subsequent rows, where the leading
142 // bit of the current bit is one. Therefore, the column of the leading
143 // bit becomes zero.
144 // Note: In normal gauss, we would also add the current row to rows
145 // above the current one. However, here we only need to identify
146 // the columns to swap. Therefore, we can ignore the upper rows.
147 for(size_t next_row = row_idx + 1; next_row < Classic_McEliece_Parameters::mu(); ++next_row) {
148 // Add the current row to next_row if the pivot bit of next_row is set
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));
151 }
152 }
153
154 // Create pivot bitvector from the pivot index vector
155 CmceColumnSelection pivots(Classic_McEliece_Parameters::nu());
156 for(auto pivot_idx : pivot_indices) {
157 for(size_t i = 0; i < Classic_McEliece_Parameters::nu(); ++i) {
158 auto mask_is_at_current_idx = Botan::CT::Mask<size_t>::is_equal(i, pivot_idx);
159 pivots.at(i) = static_cast<bool>(mask_is_at_current_idx.select(1, pivots.at(i).as<size_t>()));
160 }
161 }
162
163 // Swap the rows so the matrix can be transformed into systematic form
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));
167 }
168 }
169
170 // Reinsert the swapped columns into the matrix
171 for(size_t row = 0; row < params.pk_no_rows(); ++row) {
172 mat[row].subvector_replace(pos_offset, matrix_swap_area[row]);
173 }
174
175 return pivots;
176}
177
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");
181 // Initialized for systematic form instances
182 // Is overridden for semi systematic instances
183 auto pivots = CmceColumnSelection({0xFF, 0xFF, 0xFF, 0xFF, 0, 0, 0, 0});
184
185 // Gaussian Elimination
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) {
192 return std::nullopt;
193 } else {
194 pivots = std::move(ret_pivots.value());
195 }
196 }
197
198 // Iterates over all rows next_row under row diag_pos. If the bit at column
199 // diag_pos differs between row diag_pos and row next_row, row next_row is added to row diag_pos.
200 // This achieves that the respective bit at the diagonal becomes 1
201 // (if mat is systematic)
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());
204 }
205
206 // If the current bit on the diagonal is not set at this point
207 // the matrix is not systematic. We abort the computation in this case.
208 bool diag_bit_zero = !mat[diag_pos].at(diag_pos);
209 CT::unpoison(diag_bit_zero);
210 if(diag_bit_zero) {
211 return std::nullopt;
212 }
213
214 // Now the new row is added to all other rows, where the
215 // bit in the column of the current postion on the diagonal
216 // is still one
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());
220 }
221 }
222 }
223
224 return pivots;
225}
226
227std::vector<uint8_t> extract_pk_bytes_from_matrix(const Classic_McEliece_Parameters& params, const CmceMatrix& mat) {
228 // Store T of the matrix (I_mt|T) as a linear vector to represent the
229 // public key as defined in McEliece ISO 9.2.7
230 std::vector<uint8_t> big_t(params.pk_size_bytes());
231 auto big_t_stuffer = BufferStuffer(big_t);
232
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()));
235 }
236
237 BOTAN_ASSERT_NOMSG(big_t_stuffer.full());
238
239 return big_t;
240}
241
242} // namespace
243
244std::optional<std::pair<Classic_McEliece_Matrix, CmceColumnSelection>> Classic_McEliece_Matrix::create_matrix(
245 const Classic_McEliece_Parameters& params,
246 const Classic_McEliece_Field_Ordering& field_ordering,
248 auto mat = init_matrix_with_alphas(params, field_ordering, g);
249 auto pivots = apply_gauss(params, mat);
250
251 auto gauss_failed = !pivots.has_value();
252 CT::unpoison(gauss_failed);
253 if(gauss_failed) {
254 return std::nullopt;
255 }
256
257 auto pk_mat_bytes = extract_pk_bytes_from_matrix(params, mat);
258 return std::make_pair(Classic_McEliece_Matrix(params, std::move(pk_mat_bytes)), pivots.value());
259}
260
261std::optional<std::pair<Classic_McEliece_Matrix, CmceColumnSelection>>
263 Classic_McEliece_Field_Ordering& field_ordering,
265 auto pk_matrix_and_pivots = create_matrix(params, field_ordering, g);
266
267 bool matrix_creation_failed = !pk_matrix_and_pivots.has_value();
268 CT::unpoison(matrix_creation_failed);
269 if(matrix_creation_failed) {
270 return std::nullopt;
271 }
272
273 auto& [_, pivots] = pk_matrix_and_pivots.value();
274
275 if(params.is_f()) {
276 field_ordering.permute_with_pivots(params, pivots);
277 }
278
279 return pk_matrix_and_pivots;
280}
281
283 auto s = e.subvector<CmceCodeWord>(0, params.pk_no_rows());
284 auto e_T = e.subvector(params.pk_no_rows());
285 auto pk_slicer = BufferSlicer(m_mat_bytes);
286
287 for(size_t i = 0; i < params.pk_no_rows(); ++i) {
288 auto pk_current_bytes = pk_slicer.take(params.pk_row_size_bytes());
289 auto row = secure_bitvector(pk_current_bytes, params.n() - params.pk_no_rows());
290 row &= e_T;
291 s[i] ^= row.has_odd_hamming_weight().as_bool();
292 }
293
294 BOTAN_ASSERT_NOMSG(pk_slicer.empty());
295 return s;
296}
297} // namespace Botan
#define BOTAN_ASSERT_NOMSG(expr)
Definition assert.h:75
#define BOTAN_ASSERT(expr, assertion_made)
Definition assert.h:62
static constexpr Mask< T > set()
Definition ct_utils.h:410
static constexpr Mask< T > is_equal(T x, T y)
Definition ct_utils.h:470
Represents a field ordering for the Classic McEliece cryptosystem.
void permute_with_pivots(const Classic_McEliece_Parameters &params, 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 &params, 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 &params, 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 &params, 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 &params, std::vector< uint8_t > mat_bytes)
Create a Classic_McEliece_Matrix from bytes.
Definition cmce_matrix.h:84
Representation of a minimal polynomial in GF(q)[y].
Definition cmce_poly.h:81
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
Definition bitvector.h:1389
constexpr void unpoison(const T *p, size_t n)
Definition ct_utils.h:65
Strong< secure_bitvector, struct CmceCodeWord_ > CmceCodeWord
Represents C of decapsulation.
Definition cmce_types.h:52
bitvector_base< secure_allocator > secure_bitvector
Definition bitvector.h:1303
BOTAN_FORCE_INLINE constexpr void swap_bits(T &x, T &y, T mask, size_t shift)
Definition bit_ops.h:182
Strong< secure_bitvector, struct CmceErrorVector_ > CmceErrorVector
Represents e of encapsulation.
Definition cmce_types.h:49
Strong< secure_bitvector, struct CmceColumnSelection_ > CmceColumnSelection
Represents c of private key.
Definition cmce_types.h:46