9 #include <botan/polyn_gf2m.h>
10 #include <botan/internal/bit_ops.h>
11 #include <botan/internal/code_based_util.h>
12 #include <botan/exceptn.h>
18 uint32_t patch_root_array(
gf2m* res_root_arr,
19 uint32_t res_root_arr_len,
23 volatile gf2m patch_elem = 0x01;
24 volatile gf2m cond_mask = (root_pos == res_root_arr_len);
26 cond_mask = ~cond_mask;
27 patch_elem &= cond_mask;
28 for(i = 0; i < res_root_arr_len; i++)
31 gf2m masked_patch_elem = (patch_elem++) & cond_mask;
32 res_root_arr[i] ^= masked_patch_elem++;
34 return res_root_arr_len;
37 class gf2m_decomp_rootfind_state
40 gf2m_decomp_rootfind_state(
const polyn_gf2m & p_polyn, uint32_t
code_length);
42 void calc_LiK(
const polyn_gf2m & sigma);
43 gf2m calc_Fxj_j_neq_0(
const polyn_gf2m & sigma,
gf2m j_gray);
45 void calc_Ai_zero(
const polyn_gf2m & sigma);
46 secure_vector<gf2m> find_roots(
const polyn_gf2m & sigma);
47 uint32_t get_code_length()
const {
return code_length; }
62 gf2m brootf_decomp__gray_to_lex(
gf2m gray)
64 static_assert(
sizeof(
gf2m) == 2,
"Expected size");
65 gf2m result = gray ^ (gray>>8);
66 result ^= (result >> 4);
67 result ^= (result >> 2);
68 result ^= (result >> 1);
76 uint32_t brootf_decomp__calc_sum_limit(uint32_t t)
89 gf2m_decomp_rootfind_state::gf2m_decomp_rootfind_state(
const polyn_gf2m & polyn, uint32_t the_code_length) :
94 std::shared_ptr<GF2m_Field> sp_field = polyn.get_sp_field();
95 int deg_sigma = polyn.get_degree();
98 throw Internal_Error(
"Unexpected degree in gf2m_decomp_rootfind_state");
101 coeff_3 = polyn.get_coef( 3);
102 coeff_head = polyn.get_coef( deg_sigma);
105 this->
m_sigma_3_l = sp_field->gf_l_from_n(coeff_3);
111 this->
m_sigma_3_l = sp_field->gf_l_from_n(coeff_head);
120 void gf2m_decomp_rootfind_state::calc_Ai_zero(
const polyn_gf2m & sigma)
128 this->
m_Aij[i] = sigma.get_coef(5*i);
134 void gf2m_decomp_rootfind_state::calc_next_Aij()
142 gf2m diff, new_j_gray;
143 uint32_t Lik_pos_base;
153 else if(this->
m_j & 2)
157 else if( this->
m_j & 4)
159 Lik_pos_base = this->m_outer_summands * 2;
161 else if( this->
m_j & 8)
163 Lik_pos_base = this->m_outer_summands * 3;
165 else if( this->
m_j & 16)
167 Lik_pos_base = this->m_outer_summands * 4;
173 while(((static_cast<gf2m>(1) << delta_offs) & diff) == 0)
185 this->
m_Aij[i] ^= this->
m_Lik[Lik_pos_base + i];
190 void gf2m_decomp_rootfind_state::calc_LiK(
const polyn_gf2m & sigma)
192 std::shared_ptr<GF2m_Field> sp_field = sigma.get_sp_field();
194 d = sigma.get_degree();
195 for(k = 0; k < sp_field->get_extension_degree(); k++)
198 gf2m alpha_l_k_tt2_ttj[4];
199 alpha_l_k_tt2_ttj[0] = sp_field->gf_l_from_n(static_cast<gf2m>(1) << k);
200 alpha_l_k_tt2_ttj[1] = sp_field->gf_mul_rrr(alpha_l_k_tt2_ttj[0], alpha_l_k_tt2_ttj[0]);
201 alpha_l_k_tt2_ttj[2] = sp_field->gf_mul_rrr(alpha_l_k_tt2_ttj[1],alpha_l_k_tt2_ttj[1] );
203 alpha_l_k_tt2_ttj[3] = sp_field->gf_mul_rrr(alpha_l_k_tt2_ttj[2], alpha_l_k_tt2_ttj[2]);
207 uint32_t five_i = 5*i;
208 uint32_t Lik_pos = Lik_pos_base + i;
209 this->
m_Lik[Lik_pos] = 0;
210 for(j = 0; j <= 3; j++)
213 uint32_t f_ind = five_i + (
static_cast<uint32_t
>(1) << j);
218 f = sigma.get_coef( f_ind);
220 x = sp_field->gf_mul_zrz(alpha_l_k_tt2_ttj[j], f);
221 this->
m_Lik[Lik_pos] ^= x;
227 gf2m gf2m_decomp_rootfind_state::calc_Fxj_j_neq_0(
const polyn_gf2m & sigma,
gf2m j_gray)
232 std::shared_ptr<GF2m_Field> sp_field = sigma.get_sp_field();
233 const gf2m jl_gray = sp_field->gf_l_from_n(j_gray);
234 gf2m xl_j_tt_5 = sp_field->gf_square_rr(jl_gray);
235 gf2m xl_gray_tt_3 = sp_field->gf_mul_rrr(xl_j_tt_5, jl_gray);
236 xl_j_tt_5 = sp_field->gf_mul_rrr(xl_j_tt_5, xl_gray_tt_3);
239 sum = sp_field->gf_mul_nrr(xl_gray_tt_3, this->
m_sigma_3_l);
245 sum ^= this->
m_Aij[0];
248 if(this->m_outer_summands > 1)
251 x = sp_field->gf_mul_zrz(xl_j_tt_5, this->
m_Aij[1]);
255 gf2m xl_j_tt_5i = xl_j_tt_5;
260 xl_j_tt_5i = sp_field->gf_mul_rrr(xl_j_tt_5i, xl_j_tt_5);
262 x = sp_field->gf_mul_zrz(xl_j_tt_5i, this->
m_Aij[i]);
268 secure_vector<gf2m> gf2m_decomp_rootfind_state::find_roots(
const polyn_gf2m & sigma)
270 const int sigma_degree = sigma.get_degree();
272 secure_vector<gf2m> result(sigma_degree);
273 uint32_t root_pos = 0;
275 this->calc_Ai_zero(sigma);
276 this->calc_LiK(sigma);
282 eval_result = sigma.get_coef( 0);
286 eval_result = this->calc_Fxj_j_neq_0(sigma, this->
m_j_gray);
296 if(this->
m_j + static_cast<uint32_t>(1) == this->get_code_length())
300 this->calc_next_Aij();
304 root_pos = patch_root_array(result.data(), result.size(), root_pos);
305 result.resize(root_pos);
313 gf2m_decomp_rootfind_state state(polyn, code_length);
314 return state.find_roots(polyn);
secure_vector< gf2m > m_Aij
secure_vector< gf2m > m_Lik
#define BOTAN_ASSERT(expr, assertion_made)
std::vector< T, secure_allocator< T >> secure_vector
gf2m lex_to_gray(gf2m lex)
uint16_t expand_mask_16bit(T tst)
secure_vector< gf2m > find_roots_gf2m_decomp(const polyn_gf2m &polyn, uint32_t code_length)
gf2m m_sigma_3_neq_0_mask
uint32_t m_outer_summands