9#include <botan/internal/polyn_gf2m.h>
11#include <botan/assert.h>
12#include <botan/exceptn.h>
13#include <botan/internal/bit_ops.h>
14#include <botan/internal/code_based_util.h>
20void patch_root_array(
gf2m res_root_arr[],
size_t res_root_arr_len,
size_t root_pos) {
21 volatile gf2m patch_elem = 0x01;
22 volatile gf2m cond_mask =
static_cast<gf2m>(root_pos == res_root_arr_len);
24 cond_mask = ~cond_mask;
25 patch_elem = patch_elem & cond_mask;
26 for(
size_t i = 0; i < res_root_arr_len; i++) {
27 patch_elem = patch_elem + 1;
28 gf2m masked_patch_elem = patch_elem & cond_mask;
29 res_root_arr[i] ^= masked_patch_elem++;
33class gf2m_decomp_rootfind_state {
35 gf2m_decomp_rootfind_state(
const polyn_gf2m& p_polyn,
size_t code_length);
37 void calc_LiK(
const polyn_gf2m&
sigma);
40 void calc_Ai_zero(
const polyn_gf2m&
sigma);
47 uint32_t m_outer_summands;
51 gf2m m_sigma_3_neq_0_mask;
57uint32_t brootf_decomp_calc_sum_limit(uint32_t t) {
61 uint32_t result = t - 4;
67gf2m_decomp_rootfind_state::gf2m_decomp_rootfind_state(
const polyn_gf2m& polyn,
size_t code_length) :
68 m_code_length(code_length), m_j(0), m_j_gray(0) {
69 std::shared_ptr<GF2m_Field> sp_field = polyn.get_sp_field();
70 int deg_sigma = polyn.get_degree();
72 throw Internal_Error(
"Unexpected degree in gf2m_decomp_rootfind_state");
75 gf2m coeff_3 = polyn.get_coef(3);
76 gf2m coeff_head = polyn.get_coef(deg_sigma);
78 this->m_sigma_3_l = sp_field->gf_l_from_n(coeff_3);
79 this->m_sigma_3_neq_0_mask = 0xFFFF;
82 this->m_sigma_3_l = sp_field->gf_l_from_n(coeff_head);
83 this->m_sigma_3_neq_0_mask = 0;
86 this->m_outer_summands = 1 + brootf_decomp_calc_sum_limit(deg_sigma);
87 this->m_Lik.resize(this->m_outer_summands * sp_field->get_extension_degree());
88 this->m_Aij.resize(this->m_outer_summands);
91void gf2m_decomp_rootfind_state::calc_Ai_zero(
const polyn_gf2m& sigma) {
95 for(uint32_t i = 0; i < this->m_outer_summands; i++) {
96 this->m_Aij[i] =
sigma.get_coef(5 * i);
102void gf2m_decomp_rootfind_state::calc_next_Aij() {
108 uint32_t Lik_pos_base = 0;
114 if((this->m_j & 1) != 0) {
117 }
else if((this->m_j & 2) != 0) {
119 Lik_pos_base = this->m_outer_summands;
120 }
else if((this->m_j & 4) != 0) {
122 Lik_pos_base = this->m_outer_summands * 2;
123 }
else if((this->m_j & 8) != 0) {
125 Lik_pos_base = this->m_outer_summands * 3;
126 }
else if((this->m_j & 16) != 0) {
127 Lik_pos_base = this->m_outer_summands * 4;
130 gf2m diff = this->m_j_gray ^ new_j_gray;
131 while(((
static_cast<gf2m>(1) << delta_offs) & diff) == 0) {
134 Lik_pos_base = delta_offs * this->m_outer_summands;
136 this->m_j_gray = new_j_gray;
138 for(uint32_t i = 0; i < this->m_outer_summands; i++) {
139 this->m_Aij[i] ^= this->m_Lik[Lik_pos_base + i];
143void gf2m_decomp_rootfind_state::calc_LiK(
const polyn_gf2m& sigma) {
144 std::shared_ptr<GF2m_Field> sp_field =
sigma.get_sp_field();
145 uint32_t d =
sigma.get_degree();
146 for(uint32_t k = 0; k < sp_field->get_extension_degree(); k++) {
147 uint32_t Lik_pos_base = k * this->m_outer_summands;
148 gf2m alpha_l_k_tt2_ttj[4];
149 alpha_l_k_tt2_ttj[0] = sp_field->gf_l_from_n(
static_cast<gf2m>(1) << k);
150 alpha_l_k_tt2_ttj[1] = sp_field->gf_mul_rrr(alpha_l_k_tt2_ttj[0], alpha_l_k_tt2_ttj[0]);
151 alpha_l_k_tt2_ttj[2] = sp_field->gf_mul_rrr(alpha_l_k_tt2_ttj[1], alpha_l_k_tt2_ttj[1]);
153 alpha_l_k_tt2_ttj[3] = sp_field->gf_mul_rrr(alpha_l_k_tt2_ttj[2], alpha_l_k_tt2_ttj[2]);
154 for(uint32_t i = 0; i < this->m_outer_summands; i++) {
155 const uint32_t five_i = 5 * i;
156 const uint32_t Lik_pos = Lik_pos_base + i;
157 this->m_Lik[Lik_pos] = 0;
158 for(
size_t j = 0; j <= 3; j++) {
159 uint32_t f_ind = five_i + (
static_cast<uint32_t
>(1) << j);
165 gf2m x = sp_field->gf_mul_zrz(alpha_l_k_tt2_ttj[j], f);
166 this->m_Lik[Lik_pos] ^= x;
172gf2m gf2m_decomp_rootfind_state::calc_Fxj_j_neq_0(
const polyn_gf2m& sigma, gf2m j_gray) {
175 std::shared_ptr<GF2m_Field> sp_field =
sigma.get_sp_field();
176 const gf2m jl_gray = sp_field->gf_l_from_n(j_gray);
177 gf2m xl_j_tt_5 = sp_field->gf_square_rr(jl_gray);
178 gf2m xl_gray_tt_3 = sp_field->gf_mul_rrr(xl_j_tt_5, jl_gray);
179 xl_j_tt_5 = sp_field->gf_mul_rrr(xl_j_tt_5, xl_gray_tt_3);
181 sum = sp_field->gf_mul_nrr(xl_gray_tt_3, this->m_sigma_3_l);
182 sum &= this->m_sigma_3_neq_0_mask;
187 sum ^= this->m_Aij[0];
190 if(this->m_outer_summands > 1) {
191 gf2m x = sp_field->gf_mul_zrz(xl_j_tt_5, this->m_Aij[1]);
195 gf2m xl_j_tt_5i = xl_j_tt_5;
197 for(uint32_t i = 2; i < this->m_outer_summands; i++) {
198 xl_j_tt_5i = sp_field->gf_mul_rrr(xl_j_tt_5i, xl_j_tt_5);
200 gf2m x = sp_field->gf_mul_zrz(xl_j_tt_5i, this->m_Aij[i]);
206secure_vector<gf2m> gf2m_decomp_rootfind_state::find_roots(
const polyn_gf2m& sigma) {
207 const int sigma_degree =
sigma.get_degree();
209 secure_vector<gf2m> result(sigma_degree);
210 uint32_t root_pos = 0;
212 this->calc_Ai_zero(sigma);
213 this->calc_LiK(sigma);
215 gf2m eval_result = 0;
217 if(this->m_j_gray == 0) {
218 eval_result =
sigma.get_coef(0);
220 eval_result = this->calc_Fxj_j_neq_0(sigma, this->m_j_gray);
223 if(eval_result == 0) {
224 result[root_pos] = this->m_j_gray;
228 if(this->m_j +
static_cast<uint32_t
>(1) == m_code_length) {
231 this->calc_next_Aij();
235 patch_root_array(result.data(), result.size(), root_pos);
242 gf2m_decomp_rootfind_state state(polyn, code_length);
243 return state.find_roots(polyn);
#define BOTAN_ASSERT(expr, assertion_made)
gf2m lex_to_gray(gf2m lex)
uint16_t expand_mask_16bit(T tst)
BOTAN_FORCE_INLINE constexpr T sigma(T x)
std::vector< T, secure_allocator< T > > secure_vector
secure_vector< gf2m > find_roots_gf2m_decomp(const polyn_gf2m &polyn, size_t code_length)