diff options
Diffstat (limited to 'src/lib/pubkey/mce')
22 files changed, 954 insertions, 1186 deletions
diff --git a/src/lib/pubkey/mce/binary_matrix.cpp b/src/lib/pubkey/mce/binary_matrix.cpp deleted file mode 100644 index 12c842669..000000000 --- a/src/lib/pubkey/mce/binary_matrix.cpp +++ /dev/null @@ -1,96 +0,0 @@ -/** - * (C) Copyright Projet SECRET, INRIA, Rocquencourt - * (C) Bhaskar Biswas and Nicolas Sendrier - * - * (C) 2014 cryptosource GmbH - * (C) 2014 Falko Strenzke [email protected] - * - * Botan is released under the Simplified BSD License (see license.txt) - * - */ - -#include <botan/internal/binary_matrix.h> -#include <botan/internal/xor_buf.h> - -namespace Botan { - -binary_matrix::binary_matrix (u32bit rown, u32bit coln) - { - m_coln = coln; - m_rown = rown; - m_rwdcnt = (1 + (m_coln - 1) / BITS_PER_U32); - m_elem = std::vector<u32bit>(m_rown * m_rwdcnt); - } - -void binary_matrix::row_xor(u32bit a, u32bit b) - { - u32bit i; - for(i=0;i<m_rwdcnt;i++) - { - m_elem[a*m_rwdcnt+i]^=m_elem[b*m_rwdcnt+i]; - } - } - -//the matrix is reduced from LSB...(from right) -secure_vector<int> binary_matrix::row_reduced_echelon_form() - { - u32bit i, failcnt, findrow, max=m_coln - 1; - - secure_vector<int> perm(m_coln); - for(i=0;i<m_coln;i++) - { - perm[i]=i;//initialize permutation. - } - failcnt = 0; - - for(i=0;i<m_rown;i++,max--) - { - findrow=0; - for(u32bit j=i;j<m_rown;j++) - { - if(coef(j,max)) - { - if (i!=j)//not needed as ith row is 0 and jth row is 1. - row_xor(i,j);//xor to the row.(swap)? - findrow=1; - break; - }//largest value found (end if) - } - - if(!findrow)//if no row with a 1 found then swap last column and the column with no 1 down. - { - perm[m_coln - m_rown - 1 - failcnt] = max; - failcnt++; - if (!max) - { - //CSEC_FREE_MEM_CHK_SET_NULL(*p_perm); - //CSEC_THR_RETURN(); - perm.resize(0); - } - i--; - } - else - { - perm[i+m_coln - m_rown] = max; - for(u32bit j=i+1;j<m_rown;j++)//fill the column downwards with 0's - { - if(coef(j,(max))) - { - row_xor(j,i);//check the arg. order. - } - } - - for(int j=i-1;j>=0;j--)//fill the column with 0's upwards too. - { - if(coef(j,(max))) - { - row_xor(j,i); - } - } - } - }//end for(i) - return perm; - } - - -} // end namespace Botan diff --git a/src/lib/pubkey/mce/binary_matrix.h b/src/lib/pubkey/mce/binary_matrix.h deleted file mode 100644 index feb44632f..000000000 --- a/src/lib/pubkey/mce/binary_matrix.h +++ /dev/null @@ -1,60 +0,0 @@ -/** - * (C) Copyright Projet SECRET, INRIA, Rocquencourt - * (C) Bhaskar Biswas and Nicolas Sendrier - * - * (C) 2014 cryptosource GmbH - * (C) 2014 Falko Strenzke [email protected] - * - * Botan is released under the Simplified BSD License (see license.txt) - * - */ - -#ifndef BOTAN_BINARY_MATRIX_H__ -#define BOTAN_BINARY_MATRIX_H__ - -#include <botan/secmem.h> - -namespace Botan { - -#define BITS_PER_U32 (8 * sizeof (u32bit)) - -struct binary_matrix - { - public: - binary_matrix(u32bit m_rown, u32bit m_coln); - - void row_xor(u32bit a, u32bit b); - secure_vector<int> row_reduced_echelon_form(); - - /** - * return the coefficient out of F_2 - */ - u32bit coef(u32bit i, u32bit j) - { - return (m_elem[(i) * m_rwdcnt + (j) / BITS_PER_U32] >> (j % BITS_PER_U32)) & 1; - }; - - void set_coef_to_one(u32bit i, u32bit j) - { - m_elem[(i) * m_rwdcnt + (j) / BITS_PER_U32] |= (1UL << ((j) % BITS_PER_U32)) ; - }; - - void toggle_coeff(u32bit i, u32bit j) - { - m_elem[(i) * m_rwdcnt + (j) / BITS_PER_U32] ^= (1UL << ((j) % BITS_PER_U32)) ; - } - - void set_to_zero() - { - zeroise(m_elem); - } - - u32bit m_rown; // number of rows. - u32bit m_coln; // number of columns. - u32bit m_rwdcnt; // number of words in a row - std::vector<u32bit> m_elem; - }; - -} - -#endif diff --git a/src/lib/pubkey/mce/code_based_key_gen.cpp b/src/lib/pubkey/mce/code_based_key_gen.cpp index a3749abef..44b1cb4d6 100644 --- a/src/lib/pubkey/mce/code_based_key_gen.cpp +++ b/src/lib/pubkey/mce/code_based_key_gen.cpp @@ -9,26 +9,139 @@ * */ -#include <botan/internal/code_based_key_gen.h> -#include <botan/code_based_util.h> -#include <botan/gf2m_rootfind_dcmp.h> -#include <botan/internal/binary_matrix.h> +#include <botan/mceliece.h> +#include <botan/internal/code_based_util.h> #include <botan/loadstor.h> -#include <botan/polyn_gf2m.h> namespace Botan { namespace { +struct binary_matrix + { + public: + binary_matrix(u32bit m_rown, u32bit m_coln); + + void row_xor(u32bit a, u32bit b); + secure_vector<int> row_reduced_echelon_form(); + + /** + * return the coefficient out of F_2 + */ + u32bit coef(u32bit i, u32bit j) + { + return (m_elem[(i) * m_rwdcnt + (j) / 32] >> (j % 32)) & 1; + }; + + void set_coef_to_one(u32bit i, u32bit j) + { + m_elem[(i) * m_rwdcnt + (j) / 32] |= (static_cast<u32bit>(1) << ((j) % 32)) ; + }; + + void toggle_coeff(u32bit i, u32bit j) + { + m_elem[(i) * m_rwdcnt + (j) / 32] ^= (static_cast<u32bit>(1) << ((j) % 32)) ; + } + + void set_to_zero() + { + zeroise(m_elem); + } + + //private: + u32bit m_rown; // number of rows. + u32bit m_coln; // number of columns. + u32bit m_rwdcnt; // number of words in a row + std::vector<u32bit> m_elem; + }; + +binary_matrix::binary_matrix (u32bit rown, u32bit coln) + { + m_coln = coln; + m_rown = rown; + m_rwdcnt = 1 + ((m_coln - 1) / 32); + m_elem = std::vector<u32bit>(m_rown * m_rwdcnt); + } + +void binary_matrix::row_xor(u32bit a, u32bit b) + { + u32bit i; + for(i=0;i<m_rwdcnt;i++) + { + m_elem[a*m_rwdcnt+i]^=m_elem[b*m_rwdcnt+i]; + } + } + +//the matrix is reduced from LSB...(from right) +secure_vector<int> binary_matrix::row_reduced_echelon_form() + { + u32bit i, failcnt, findrow, max=m_coln - 1; + + secure_vector<int> perm(m_coln); + for(i=0;i<m_coln;i++) + { + perm[i]=i;//initialize permutation. + } + failcnt = 0; + + for(i=0;i<m_rown;i++,max--) + { + findrow=0; + for(u32bit j=i;j<m_rown;j++) + { + if(coef(j,max)) + { + if (i!=j)//not needed as ith row is 0 and jth row is 1. + row_xor(i,j);//xor to the row.(swap)? + findrow=1; + break; + }//largest value found (end if) + } + + if(!findrow)//if no row with a 1 found then swap last column and the column with no 1 down. + { + perm[m_coln - m_rown - 1 - failcnt] = max; + failcnt++; + if (!max) + { + //CSEC_FREE_MEM_CHK_SET_NULL(*p_perm); + //CSEC_THR_RETURN(); + perm.resize(0); + } + i--; + } + else + { + perm[i+m_coln - m_rown] = max; + for(u32bit j=i+1;j<m_rown;j++)//fill the column downwards with 0's + { + if(coef(j,(max))) + { + row_xor(j,i);//check the arg. order. + } + } + + for(int j=i-1;j>=0;j--)//fill the column with 0's upwards too. + { + if(coef(j,(max))) + { + row_xor(j,i); + } + } + } + }//end for(i) + return perm; + } + void randomize_support(u32bit n, std::vector<gf2m> & L, RandomNumberGenerator & rng) { unsigned int i, j; - gf2m_small_m::gf2m tmp; + gf2m tmp; for (i = 0; i < n; ++i) { - gf2m_small_m::gf2m rnd; + gf2m rnd; rng.randomize(reinterpret_cast<byte*>(&rnd), sizeof(rnd)); j = rnd % n; // no rejection sampling, but for useful code-based parameters with n <= 13 this seem tolerable @@ -38,14 +151,14 @@ void randomize_support(u32bit n, std::vector<gf2m> & L, RandomNumberGenerator & } } -std::unique_ptr<binary_matrix> generate_R(std::vector<gf2m> &L, polyn_gf2m* g, std::shared_ptr<gf2m_small_m::Gf2m_Field> sp_field, u32bit code_length, u32bit t ) +std::unique_ptr<binary_matrix> generate_R(std::vector<gf2m> &L, polyn_gf2m* g, std::shared_ptr<GF2m_Field> sp_field, u32bit code_length, u32bit t ) { //L- Support //t- Number of errors //n- Length of the Goppa code //m- The extension degree of the GF //g- The generator polynomial. - gf2m_small_m::gf2m x,y; + gf2m x,y; u32bit i,j,k,r,n; std::vector<int> Laux(code_length); n=code_length; @@ -112,7 +225,7 @@ McEliece_PrivateKey generate_mceliece_key( RandomNumberGenerator & rng, u32bit e { throw Invalid_Argument("invalid McEliece parameters"); } - std::shared_ptr<gf2m_small_m::Gf2m_Field> sp_field ( new Gf2m_Field(ext_deg )); + std::shared_ptr<GF2m_Field> sp_field ( new GF2m_Field(ext_deg )); //pick the support......... std::vector<gf2m> L(code_length); diff --git a/src/lib/pubkey/mce/code_based_key_gen.h b/src/lib/pubkey/mce/code_based_key_gen.h deleted file mode 100644 index 6764e13d6..000000000 --- a/src/lib/pubkey/mce/code_based_key_gen.h +++ /dev/null @@ -1,26 +0,0 @@ -/** - * (C) Copyright Projet SECRET, INRIA, Rocquencourt - * (C) Bhaskar Biswas and Nicolas Sendrier - * - * (C) 2014 cryptosource GmbH - * (C) 2014 Falko Strenzke [email protected] - * - * Botan is released under the Simplified BSD License (see license.txt) - * - */ - -#ifndef BOTAN_CODE_BASED_KEY_GEN_H__ -#define BOTAN_CODE_BASED_KEY_GEN_H__ - -#include <botan/mceliece_key.h> - -namespace Botan { - -McEliece_PrivateKey generate_mceliece_key(RandomNumberGenerator &rng, - u32bit ext_deg, - u32bit code_length, - u32bit t); - -} - -#endif diff --git a/src/lib/pubkey/mce/code_based_util.h b/src/lib/pubkey/mce/code_based_util.h index 6b567dbff..a959ad0d3 100644 --- a/src/lib/pubkey/mce/code_based_util.h +++ b/src/lib/pubkey/mce/code_based_util.h @@ -13,6 +13,7 @@ #define BOTAN_CODE_BASED_UTIL_H__ #include <botan/gf2m_small_m.h> +#include <stdexcept> namespace Botan { @@ -28,18 +29,18 @@ u16bit expand_mask_16bit(T tst) return ~(result - 1); } -inline gf2m_small_m::gf2m gray_to_lex(gf2m_small_m::gf2m gray) +inline gf2m gray_to_lex(gf2m gray) { - gf2m_small_m::gf2m result = gray ^ (gray>>8); + gf2m result = gray ^ (gray >> 8); result ^= (result >> 4); result ^= (result >> 2); result ^= (result >> 1); return result; } -inline gf2m_small_m::gf2m lex_to_gray(gf2m_small_m::gf2m lex) +inline gf2m lex_to_gray(gf2m lex) { - return (lex>>1) ^ lex; + return (lex >> 1) ^ lex; } inline u32bit bit_size_to_byte_size(u32bit bit_size) diff --git a/src/lib/pubkey/mce/gf2m_rootfind_dcmp.cpp b/src/lib/pubkey/mce/gf2m_rootfind_dcmp.cpp index 2d4f06130..d23d05172 100644 --- a/src/lib/pubkey/mce/gf2m_rootfind_dcmp.cpp +++ b/src/lib/pubkey/mce/gf2m_rootfind_dcmp.cpp @@ -6,314 +6,307 @@ * */ -#include <botan/gf2m_rootfind_dcmp.h> -#include <botan/gf2m_small_m.h> +#include <botan/polyn_gf2m.h> #include <botan/internal/bit_ops.h> -#include <botan/code_based_util.h> +#include <botan/internal/code_based_util.h> -namespace Botan -{ +namespace Botan { namespace { - u32bit patch_root_array( - gf2m* res_root_arr, - u32bit res_root_arr_len, - u32bit root_pos) - { - volatile u32bit i; - volatile gf2m patch_elem = 0x01; - volatile gf2m cond_mask = (root_pos == res_root_arr_len); - cond_mask = expand_mask_16bit(cond_mask); - cond_mask = ~cond_mask; /* now cond = 1 if not enough roots */ - patch_elem &= cond_mask; - for(i = 0; i < res_root_arr_len; i++) - { +u32bit patch_root_array(gf2m* res_root_arr, + u32bit res_root_arr_len, + u32bit root_pos) + { + volatile u32bit i; + volatile gf2m patch_elem = 0x01; + volatile gf2m cond_mask = (root_pos == res_root_arr_len); + cond_mask = expand_mask_16bit(cond_mask); + cond_mask = ~cond_mask; /* now cond = 1 if not enough roots */ + patch_elem &= cond_mask; + for(i = 0; i < res_root_arr_len; i++) + { gf2m masked_patch_elem = (patch_elem++) & cond_mask; res_root_arr[i] ^= masked_patch_elem++; - } - return res_root_arr_len; - } - -struct gf2m_decomp_rootfind_state -{ - gf2m_decomp_rootfind_state(const polyn_gf2m & p_polyn, u32bit code_length); - - void calc_LiK(const polyn_gf2m & sigma); - gf2m calc_Fxj_j_neq_0( const polyn_gf2m & sigma, gf2m j_gray); - void calc_next_Aij(); - void calc_Ai_zero(const polyn_gf2m & sigma); - secure_vector<gf2m> find_roots(const polyn_gf2m & sigma); - u32bit get_code_length() const { return code_length; }; - u32bit code_length; - secure_vector<gf2m> m_Lik; // size is outer_summands * m - secure_vector<gf2m> m_Aij; // ... - u32bit m_outer_summands; - gf2m m_j; - gf2m m_j_gray; - gf2m m_sigma_3_l; - gf2m m_sigma_3_neq_0_mask; -} ; - + } + return res_root_arr_len; + } + +class gf2m_decomp_rootfind_state + { + public: + gf2m_decomp_rootfind_state(const polyn_gf2m & p_polyn, u32bit code_length); + + void calc_LiK(const polyn_gf2m & sigma); + gf2m calc_Fxj_j_neq_0( const polyn_gf2m & sigma, gf2m j_gray); + void calc_next_Aij(); + void calc_Ai_zero(const polyn_gf2m & sigma); + secure_vector<gf2m> find_roots(const polyn_gf2m & sigma); + u32bit get_code_length() const { return code_length; }; + u32bit code_length; + secure_vector<gf2m> m_Lik; // size is outer_summands * m + secure_vector<gf2m> m_Aij; // ... + u32bit m_outer_summands; + gf2m m_j; + gf2m m_j_gray; + gf2m m_sigma_3_l; + gf2m m_sigma_3_neq_0_mask; + }; /* - * !! Attention: assumes gf2m is 16bit !! - */ +* !! Attention: assumes gf2m is 16bit !! +*/ #if 0 gf2m brootf_decomp__gray_to_lex(gf2m gray) -{ - static_assert(sizeof(gf2m) == 2, "Expected size"); - gf2m result = gray ^ (gray>>8); - result ^= (result >> 4); - result ^= (result >> 2); - result ^= (result >> 1); - return result; -} + { + static_assert(sizeof(gf2m) == 2, "Expected size"); + gf2m result = gray ^ (gray>>8); + result ^= (result >> 4); + result ^= (result >> 2); + result ^= (result >> 1); + return result; + } #endif /** - * calculates ceil((t-4)/5) = outer_summands - 1 - */ +* calculates ceil((t-4)/5) = outer_summands - 1 +*/ u32bit brootf_decomp__calc_sum_limit(u32bit t) -{ - u32bit result; - if(t < 4) - { - return 0; - } - result = t - 4; - result += 4; - result /= 5; - return result; -} + { + u32bit result; + if(t < 4) + { + return 0; + } + result = t - 4; + result += 4; + result /= 5; + return result; + } + } secure_vector<gf2m> find_roots_gf2m_decomp(const polyn_gf2m & polyn, u32bit code_length) -{ - gf2m_decomp_rootfind_state state(polyn, code_length); - return state.find_roots(polyn); - -} + { + gf2m_decomp_rootfind_state state(polyn, code_length); + return state.find_roots(polyn); + } + +gf2m_decomp_rootfind_state::gf2m_decomp_rootfind_state(const polyn_gf2m & polyn, u32bit the_code_length) : + code_length(the_code_length) + { + gf2m coeff_3; + gf2m coeff_head; + std::shared_ptr<GF2m_Field> sp_field = polyn.get_sp_field(); + int deg_sigma = polyn.get_degree(); + if(deg_sigma <= 3) + { + throw std::exception(); + } + this->m_j = 0; + coeff_3 = polyn.get_coef( 3); + coeff_head = polyn.get_coef( deg_sigma); /* dummy value for SCA CM */ + if(coeff_3 != 0) + { + this->m_sigma_3_l = sp_field->gf_l_from_n(coeff_3); + this->m_sigma_3_neq_0_mask = 0xFFFF; + } + else + { + // dummy value needed for timing countermeasure + this->m_sigma_3_l = sp_field->gf_l_from_n(coeff_head); + this->m_sigma_3_neq_0_mask = 0 ; + } -gf2m_decomp_rootfind_state::gf2m_decomp_rootfind_state(const polyn_gf2m & polyn, u32bit the_code_length) - :code_length(the_code_length) -{ - - gf2m coeff_3; - gf2m coeff_head; - std::shared_ptr<gf2m_small_m::Gf2m_Field> sp_field = polyn.get_sp_field(); - int deg_sigma = polyn.get_degree(); - if(deg_sigma <= 3) - { - throw std::exception(); - } - this->m_j = 0; - coeff_3 = polyn.get_coef( 3); - coeff_head = polyn.get_coef( deg_sigma); /* dummy value for SCA CM */ - if(coeff_3 != 0) - { - this->m_sigma_3_l = sp_field->gf_l_from_n(coeff_3); - this->m_sigma_3_neq_0_mask = 0xFFFF; - } - else - { - // dummy value needed for timing countermeasure - this->m_sigma_3_l = sp_field->gf_l_from_n(coeff_head); - this->m_sigma_3_neq_0_mask = 0 ; - } - - this->m_outer_summands = 1 + brootf_decomp__calc_sum_limit(deg_sigma); - this->m_Lik.resize(this->m_outer_summands * sp_field->get_extension_degree()); - this->m_Aij.resize(this->m_outer_summands); -} + this->m_outer_summands = 1 + brootf_decomp__calc_sum_limit(deg_sigma); + this->m_Lik.resize(this->m_outer_summands * sp_field->get_extension_degree()); + this->m_Aij.resize(this->m_outer_summands); + } void gf2m_decomp_rootfind_state::calc_Ai_zero(const polyn_gf2m & sigma) -{ - u32bit i; - /* + { + u32bit i; + /* * this function assumes this the first gray code element is zero */ - for(i = 0; i < this->m_outer_summands; i++) - { - this->m_Aij[i] = sigma.get_coef(5*i); - } - this->m_j = 0; - this->m_j_gray = 0; -} + for(i = 0; i < this->m_outer_summands; i++) + { + this->m_Aij[i] = sigma.get_coef(5*i); + } + this->m_j = 0; + this->m_j_gray = 0; + } void gf2m_decomp_rootfind_state::calc_next_Aij() -{ - /* + { + /* * upon function entry, we have in the state j, Aij. * first thing, we declare Aij Aij_minusone and increase j. * Case j=0 upon function entry also included, then Aij contains A_{i,j=0}. */ - u32bit i; - gf2m diff, new_j_gray; - u32bit Lik_pos_base; - - this->m_j++; - - new_j_gray = lex_to_gray(this->m_j); - - if(this->m_j & 1) /* half of the times */ - { - Lik_pos_base = 0; - } - else if(this->m_j & 2) /* one quarter of the times */ - { - Lik_pos_base = this->m_outer_summands; - } - else if( this->m_j & 4) /* one eighth of the times */ - { - Lik_pos_base = this->m_outer_summands * 2; - } - else if( this->m_j & 8) /* one sixteenth of the times */ - { - Lik_pos_base = this->m_outer_summands * 3; - } - else if( this->m_j & 16) /* ... */ - { - Lik_pos_base = this->m_outer_summands * 4; - } - else - { - gf2m delta_offs = 5; - diff = this->m_j_gray ^ new_j_gray; - while(((static_cast<gf2m>(1) << delta_offs) & diff) == 0) - { - delta_offs++; - - } - Lik_pos_base = delta_offs * this->m_outer_summands; - } - this->m_j_gray = new_j_gray; - - i = 0; - for(; i < this->m_outer_summands; i++) - { - this->m_Aij[i] ^= this->m_Lik[Lik_pos_base + i]; - } + u32bit i; + gf2m diff, new_j_gray; + u32bit Lik_pos_base; + + this->m_j++; + + new_j_gray = lex_to_gray(this->m_j); + + if(this->m_j & 1) /* half of the times */ + { + Lik_pos_base = 0; + } + else if(this->m_j & 2) /* one quarter of the times */ + { + Lik_pos_base = this->m_outer_summands; + } + else if( this->m_j & 4) /* one eighth of the times */ + { + Lik_pos_base = this->m_outer_summands * 2; + } + else if( this->m_j & 8) /* one sixteenth of the times */ + { + Lik_pos_base = this->m_outer_summands * 3; + } + else if( this->m_j & 16) /* ... */ + { + Lik_pos_base = this->m_outer_summands * 4; + } + else + { + gf2m delta_offs = 5; + diff = this->m_j_gray ^ new_j_gray; + while(((static_cast<gf2m>(1) << delta_offs) & diff) == 0) + { + delta_offs++; + + } + Lik_pos_base = delta_offs * this->m_outer_summands; + } + this->m_j_gray = new_j_gray; + + i = 0; + for(; i < this->m_outer_summands; i++) + { + this->m_Aij[i] ^= this->m_Lik[Lik_pos_base + i]; + } + + } -} void gf2m_decomp_rootfind_state::calc_LiK(const polyn_gf2m & sigma) -{ - std::shared_ptr<gf2m_small_m::Gf2m_Field> sp_field = sigma.get_sp_field(); - u32bit i, k, d; - d = sigma.get_degree(); - for(k = 0; k < sp_field->get_extension_degree(); k++) - { - u32bit Lik_pos_base = k * this->m_outer_summands; - gf2m alpha_l_k_tt2_ttj[4]; - alpha_l_k_tt2_ttj[0] = sp_field->gf_l_from_n(static_cast<gf2m>(1) << k); - alpha_l_k_tt2_ttj[1] = sp_field->gf_mul_rrr(alpha_l_k_tt2_ttj[0], alpha_l_k_tt2_ttj[0]); - alpha_l_k_tt2_ttj[2] = sp_field->gf_mul_rrr(alpha_l_k_tt2_ttj[1],alpha_l_k_tt2_ttj[1] ); - - alpha_l_k_tt2_ttj[3] = sp_field->gf_mul_rrr(alpha_l_k_tt2_ttj[2], alpha_l_k_tt2_ttj[2]); - for(i = 0; i < this->m_outer_summands; i++) - { - u32bit j; - u32bit five_i = 5*i; - u32bit Lik_pos = Lik_pos_base + i; - this->m_Lik[Lik_pos] = 0; - for(j = 0; j <= 3; j++) + { + std::shared_ptr<GF2m_Field> sp_field = sigma.get_sp_field(); + u32bit i, k, d; + d = sigma.get_degree(); + for(k = 0; k < sp_field->get_extension_degree(); k++) { - gf2m f, x; - u32bit f_ind = five_i + (static_cast<u32bit>(1) << j); - if(f_ind > d) - { - break; - } - f = sigma.get_coef( f_ind); - - x = sp_field->gf_mul_zrz(alpha_l_k_tt2_ttj[j], f); - this->m_Lik[Lik_pos] ^= x; + u32bit Lik_pos_base = k * this->m_outer_summands; + gf2m alpha_l_k_tt2_ttj[4]; + alpha_l_k_tt2_ttj[0] = sp_field->gf_l_from_n(static_cast<gf2m>(1) << k); + alpha_l_k_tt2_ttj[1] = sp_field->gf_mul_rrr(alpha_l_k_tt2_ttj[0], alpha_l_k_tt2_ttj[0]); + alpha_l_k_tt2_ttj[2] = sp_field->gf_mul_rrr(alpha_l_k_tt2_ttj[1],alpha_l_k_tt2_ttj[1] ); + + alpha_l_k_tt2_ttj[3] = sp_field->gf_mul_rrr(alpha_l_k_tt2_ttj[2], alpha_l_k_tt2_ttj[2]); + for(i = 0; i < this->m_outer_summands; i++) + { + u32bit j; + u32bit five_i = 5*i; + u32bit Lik_pos = Lik_pos_base + i; + this->m_Lik[Lik_pos] = 0; + for(j = 0; j <= 3; j++) + { + gf2m f, x; + u32bit f_ind = five_i + (static_cast<u32bit>(1) << j); + if(f_ind > d) + { + break; + } + f = sigma.get_coef( f_ind); + + x = sp_field->gf_mul_zrz(alpha_l_k_tt2_ttj[j], f); + this->m_Lik[Lik_pos] ^= x; + } + } } - } - } -} + } gf2m gf2m_decomp_rootfind_state::calc_Fxj_j_neq_0( const polyn_gf2m & sigma, gf2m j_gray) -{ - //needs the A_{ij} to compute F(x)_j - gf2m sum = 0; - u32bit i; - std::shared_ptr<gf2m_small_m::Gf2m_Field> sp_field = sigma.get_sp_field(); - gf2m xl_j_tt_5i, xl_j_tt_5, xl_gray_tt_3; - gf2m jl_gray; - jl_gray = sp_field->gf_l_from_n(j_gray); - xl_j_tt_5 = sp_field->gf_square_rr(jl_gray); - xl_gray_tt_3 = sp_field->gf_mul_rrr(xl_j_tt_5, jl_gray); - xl_j_tt_5 = sp_field->gf_mul_rrr(xl_j_tt_5, xl_gray_tt_3); - - - sum = sp_field->gf_mul_nrr(xl_gray_tt_3, this->m_sigma_3_l); - sum &= this->m_sigma_3_neq_0_mask; - /* here, we rely on compiler to be unable to optimize + { + //needs the A_{ij} to compute F(x)_j + gf2m sum = 0; + u32bit i; + std::shared_ptr<GF2m_Field> sp_field = sigma.get_sp_field(); + gf2m xl_j_tt_5i, xl_j_tt_5, xl_gray_tt_3; + const gf2m jl_gray = sp_field->gf_l_from_n(j_gray); + xl_j_tt_5 = sp_field->gf_square_rr(jl_gray); + xl_gray_tt_3 = sp_field->gf_mul_rrr(xl_j_tt_5, jl_gray); + xl_j_tt_5 = sp_field->gf_mul_rrr(xl_j_tt_5, xl_gray_tt_3); + + + sum = sp_field->gf_mul_nrr(xl_gray_tt_3, this->m_sigma_3_l); + sum &= this->m_sigma_3_neq_0_mask; + /* here, we rely on compiler to be unable to optimize * for the state->sigma_3_neq_0_mask value */ - /* treat i = 0 special: */ - sum ^= this->m_Aij[0]; - /* treat i = 1 special also */ - if(this->m_outer_summands > 1) - { - gf2m x; - xl_j_tt_5i = xl_j_tt_5; - x = sp_field->gf_mul_zrz(xl_j_tt_5, this->m_Aij[1]); /* x_j^{5i} A_i^j */ - sum ^= x; - } - for(i = 2; i < this->m_outer_summands; i++) - { - gf2m x; - xl_j_tt_5i = sp_field->gf_mul_rrr(xl_j_tt_5i, xl_j_tt_5); - // now x_j_tt_5i lives up to its name - x = sp_field->gf_mul_zrz(xl_j_tt_5i, this->m_Aij[i]); /* x_j^{5i} A_i^(j) */ - sum ^= x; - } - return sum; -} - + /* treat i = 0 special: */ + sum ^= this->m_Aij[0]; + /* treat i = 1 special also */ + if(this->m_outer_summands > 1) + { + gf2m x; + xl_j_tt_5i = xl_j_tt_5; + x = sp_field->gf_mul_zrz(xl_j_tt_5, this->m_Aij[1]); /* x_j^{5i} A_i^j */ + sum ^= x; + } + for(i = 2; i < this->m_outer_summands; i++) + { + gf2m x; + xl_j_tt_5i = sp_field->gf_mul_rrr(xl_j_tt_5i, xl_j_tt_5); + // now x_j_tt_5i lives up to its name + x = sp_field->gf_mul_zrz(xl_j_tt_5i, this->m_Aij[i]); /* x_j^{5i} A_i^(j) */ + sum ^= x; + } + return sum; + } +secure_vector<gf2m> gf2m_decomp_rootfind_state::find_roots(const polyn_gf2m & sigma) + { + secure_vector<gf2m> result(sigma.get_degree()); + u32bit root_pos = 0; + this->calc_Ai_zero(sigma); + this->calc_LiK(sigma); + do + { + gf2m eval_result; + if(this->m_j_gray == 0) + { + eval_result = sigma.get_coef( 0); + } + else + { + eval_result = this->calc_Fxj_j_neq_0(sigma, this->m_j_gray); + } + + if(eval_result == 0) + { + + result[root_pos] = this->m_j_gray; + root_pos++; + + } + if(this->m_j + static_cast<u32bit>(1) == this->get_code_length()) + { + break; + } + this->calc_next_Aij(); + }while(1); + + // side channel / fault attack countermeasure: + root_pos = patch_root_array(result.data(), result.size(), root_pos); + result.resize(root_pos); + return result; + } -secure_vector<gf2m> gf2m_decomp_rootfind_state::find_roots(const polyn_gf2m & sigma) -{ - - secure_vector<gf2m> result(sigma.get_degree()); - u32bit root_pos = 0; - - this->calc_Ai_zero(sigma); - this->calc_LiK(sigma); - do - { - gf2m eval_result; - if(this->m_j_gray == 0) - { - eval_result = sigma.get_coef( 0); - } - else - { - eval_result = this->calc_Fxj_j_neq_0(sigma, this->m_j_gray); - } - - if(eval_result == 0) - { - - result[root_pos] = this->m_j_gray; - root_pos++; - - } - if(this->m_j + static_cast<u32bit>(1) == this->get_code_length()) - { - break; - } - this->calc_next_Aij(); - }while(1); - - // side channel / fault attack countermeasure: - root_pos = patch_root_array(result.data(), result.size(), root_pos); - result.resize(root_pos); - return result; -} } // end namespace Botan diff --git a/src/lib/pubkey/mce/gf2m_rootfind_dcmp.h b/src/lib/pubkey/mce/gf2m_rootfind_dcmp.h deleted file mode 100644 index 5914ad3ae..000000000 --- a/src/lib/pubkey/mce/gf2m_rootfind_dcmp.h +++ /dev/null @@ -1,24 +0,0 @@ -/** - * (C) 2014 cryptosource GmbH - * (C) 2014 Falko Strenzke [email protected] - * - * Botan is released under the Simplified BSD License (see license.txt) - */ - -#ifndef BOTAN_GF2M_ROOTFIND_DCMP_H__ -#define BOTAN_GF2M_ROOTFIND_DCMP_H__ - -#include <botan/polyn_gf2m.h> - -namespace Botan { - -/** -* Find the roots of a polynomial over GF(2^m) using the method by Federenko -* et al. -*/ -secure_vector<gf2m> find_roots_gf2m_decomp(const polyn_gf2m & polyn, - u32bit code_length); - -} - -#endif diff --git a/src/lib/pubkey/mce/gf2m_small_m.cpp b/src/lib/pubkey/mce/gf2m_small_m.cpp index 3de748939..11da30962 100644 --- a/src/lib/pubkey/mce/gf2m_small_m.cpp +++ b/src/lib/pubkey/mce/gf2m_small_m.cpp @@ -9,14 +9,11 @@ */ #include <botan/gf2m_small_m.h> -#include <botan/code_based_util.h> #include <string> #include <stdexcept> namespace Botan { -namespace gf2m_small_m { - #define MAX_EXT_DEG 16 namespace { @@ -41,78 +38,94 @@ unsigned int prim_poly[MAX_EXT_DEG + 1] = { 0210013 /* extension degree 16 */ }; -} - -u32bit encode_gf2m(gf2m to_enc, byte* mem) +std::vector<gf2m> gf_exp_table(size_t deg, gf2m prime_poly) { - mem[0] = to_enc >> 8; - mem[1] = to_enc & 0xFF; - return sizeof(to_enc); + // construct the table gf_exp[i]=alpha^i + + std::vector<gf2m> tab((1 << deg) + 1); + + tab[0] = 1; + for(size_t i = 1; i < tab.size(); ++i) + { + const bool overflow = tab[i - 1] >> (deg - 1); + tab[i] = (tab[i-1] << 1) ^ (overflow ? prime_poly : 0); + } + + return tab; } -gf2m decode_gf2m(const byte* mem) +const std::vector<gf2m>& exp_table(size_t deg) { - gf2m result; - result = mem[0] << 8; - result |= mem[1]; - return result; + static std::vector<gf2m> tabs[MAX_EXT_DEG + 1]; + + if(deg < 2 || deg > MAX_EXT_DEG) + throw std::runtime_error("GF2m_Field does not support degree " + std::to_string(deg)); + + if(tabs[deg].empty()) + tabs[deg] = gf_exp_table(deg, prim_poly[deg]); + + return tabs[deg]; } -// construct the table gf_exp[i]=alpha^i -void Gf2m_Field::init_exp() +std::vector<gf2m> gf_log_table(size_t deg, const std::vector<gf2m>& exp) { - m_gf_exp_table.resize(1 << get_extension_degree()); + std::vector<gf2m> tab(1 << deg); - m_gf_exp_table[0] = 1; - for(size_t i = 1; i < gf_ord(); ++i) + tab[0] = (1 << deg) - 1; // log of 0 is the order by convention + for (size_t i = 0; i < tab.size(); ++i) { - m_gf_exp_table[i] = m_gf_exp_table[i - 1] << 1; - if (m_gf_exp_table[i - 1] & (1 << (get_extension_degree()-1))) - { - m_gf_exp_table[i] ^= prim_poly[get_extension_degree()]; - } + tab[exp[i]] = i; } - - // hack for the multiplication - m_gf_exp_table[gf_ord()] = 1; + return tab; } -// construct the table gf_log[alpha^i]=i -void Gf2m_Field::init_log() +const std::vector<gf2m>& log_table(size_t deg) { - m_gf_log_table.resize(1 << get_extension_degree()); + static std::vector<gf2m> tabs[MAX_EXT_DEG + 1]; - m_gf_log_table[0] = gf_ord(); // log of 0 par convention - for (size_t i = 0; i < gf_ord() ; ++i) - { - m_gf_log_table[m_gf_exp_table[i]] = i; - } + if(deg < 2 || deg > MAX_EXT_DEG) + throw std::runtime_error("GF2m_Field does not support degree " + std::to_string(deg)); + + if(tabs[deg].empty()) + tabs[deg] = gf_log_table(deg, exp_table(deg)); + + return tabs[deg]; } +} -Gf2m_Field::Gf2m_Field(size_t extdeg) +u32bit encode_gf2m(gf2m to_enc, byte* mem) { - if(extdeg < 2 || extdeg > MAX_EXT_DEG) - throw std::runtime_error("Gf2m_Field does not support degree " + std::to_string(extdeg)); + mem[0] = to_enc >> 8; + mem[1] = to_enc & 0xFF; + return sizeof(to_enc); + } - m_gf_extension_degree = extdeg; - m_gf_cardinality = 1 << extdeg; - m_gf_multiplicative_order = m_gf_cardinality - 1; +gf2m decode_gf2m(const byte* mem) + { + gf2m result; + result = mem[0] << 8; + result |= mem[1]; + return result; + } - init_exp(); - init_log(); +GF2m_Field::GF2m_Field(size_t extdeg) : m_gf_extension_degree(extdeg), + m_gf_multiplicative_order((1 << extdeg) - 1), + m_gf_log_table(log_table(m_gf_extension_degree)), + m_gf_exp_table(exp_table(m_gf_extension_degree)) + { } -gf2m Gf2m_Field::gf_div(gf2m x, gf2m y) +gf2m GF2m_Field::gf_div(gf2m x, gf2m y) const { - s32bit sub_res = static_cast<s32bit>(m_gf_log_table[x]) - static_cast<s32bit>( m_gf_log_table[y]); - s32bit modq_res = static_cast<s32bit>(_gf_modq_1(sub_res)); - s32bit div_res = static_cast<s32bit>(x) ? static_cast<s32bit>(m_gf_exp_table[modq_res]) : 0; + const s32bit sub_res = static_cast<s32bit>(gf_log(x) - static_cast<s32bit>(gf_log(y))); + const s32bit modq_res = static_cast<s32bit>(_gf_modq_1(sub_res)); + const s32bit div_res = static_cast<s32bit>(x) ? static_cast<s32bit>(gf_exp(modq_res)) : 0; return static_cast<gf2m>(div_res); } // we suppose i >= 0. Par convention 0^0 = 1 -gf2m Gf2m_Field::gf_pow(gf2m x, int i) +gf2m GF2m_Field::gf_pow(gf2m x, int i) const { if (i == 0) return 1; @@ -123,13 +136,11 @@ gf2m Gf2m_Field::gf_pow(gf2m x, int i) // i mod (q-1) while (i >> get_extension_degree()) i = (i & (gf_ord())) + (i >> get_extension_degree()); - i *= m_gf_log_table[x]; + i *= gf_log(x); while (i >> get_extension_degree()) i = (i & (gf_ord())) + (i >> get_extension_degree()); - return m_gf_exp_table[i]; + return gf_exp(i); } } } - -} diff --git a/src/lib/pubkey/mce/gf2m_small_m.h b/src/lib/pubkey/mce/gf2m_small_m.h index 223dfd511..6a8de4424 100644 --- a/src/lib/pubkey/mce/gf2m_small_m.h +++ b/src/lib/pubkey/mce/gf2m_small_m.h @@ -17,213 +17,199 @@ namespace Botan { -namespace gf2m_small_m { - typedef u16bit gf2m; -class Gf2m_Field +/** +* GF(2^m) field for m = [2...16] +*/ +class BOTAN_DLL GF2m_Field { public: - Gf2m_Field(size_t extdeg); + GF2m_Field(size_t extdeg); - gf2m gf_mul(gf2m x, gf2m y) + gf2m gf_mul(gf2m x, gf2m y) const { return ((x) ? gf_mul_fast(x, y) : 0); } - gf2m gf_square(gf2m x) + gf2m gf_square(gf2m x) const { - return ((x) ? m_gf_exp_table[_gf_modq_1(m_gf_log_table[x] << 1)] : 0); + return ((x) ? gf_exp(_gf_modq_1(gf_log(x) << 1)) : 0); } - gf2m square_rr(gf2m x) + gf2m square_rr(gf2m x) const { return _gf_modq_1(x << 1); } - // naming convention of GF(2^m) field operations: - // l logarithmic, unreduced - // r logarithmic, reduced - // n normal, non-zero - // z normal, might be zero - // - inline gf2m gf_mul_lll(gf2m a, gf2m b); - inline gf2m gf_mul_rrr(gf2m a, gf2m b); - inline gf2m gf_mul_nrr(gf2m a, gf2m b); - inline gf2m gf_mul_rrn(gf2m a, gf2m y); - inline gf2m gf_mul_lnn(gf2m x, gf2m y); - inline gf2m gf_mul_rnn(gf2m x, gf2m y); - inline gf2m gf_mul_nrn(gf2m a, gf2m y); - inline gf2m gf_mul_rnr(gf2m y, gf2m a); - inline gf2m gf_mul_zrz(gf2m a, gf2m y); - inline gf2m gf_mul_zzr(gf2m a, gf2m y); - inline gf2m gf_mul_nnr(gf2m y, gf2m a); - inline gf2m gf_sqrt(gf2m x) ; - gf2m gf_div(gf2m x, gf2m y); - inline gf2m gf_div_rnn(gf2m x, gf2m y); - inline gf2m gf_div_rnr(gf2m x, gf2m b); - inline gf2m gf_div_nrr(gf2m a, gf2m b); - inline gf2m gf_div_zzr(gf2m x, gf2m b); - inline gf2m gf_inv(gf2m x); - inline gf2m gf_inv_rn(gf2m x); - inline gf2m gf_square_ln(gf2m x); - inline gf2m gf_square_rr(gf2m a) ; - inline gf2m gf_l_from_n(gf2m x); + gf2m gf_mul_fast(gf2m x, gf2m y) const + { + return ((y) ? gf_exp(_gf_modq_1(gf_log(x) + gf_log(y))) : 0); + } - inline gf2m gf_mul_fast(gf2m a, gf2m b); + /* + naming convention of GF(2^m) field operations: + l logarithmic, unreduced + r logarithmic, reduced + n normal, non-zero + z normal, might be zero + */ - gf2m gf_exp(gf2m i) + gf2m gf_mul_lll(gf2m a, gf2m b) const { - return m_gf_exp_table[i]; /* alpha^i */ + return (a + b); } - gf2m gf_log(gf2m i) + gf2m gf_mul_rrr(gf2m a, gf2m b) const { - return m_gf_log_table[i]; /* return i when x=alpha^i */ + return (_gf_modq_1(gf_mul_lll(a, b))); } - inline gf2m gf_ord() const + gf2m gf_mul_nrr(gf2m a, gf2m b) const { - return m_gf_multiplicative_order; + return (gf_exp(gf_mul_rrr(a, b))); } - inline gf2m get_extension_degree() const + gf2m gf_mul_rrn(gf2m a, gf2m y) const { - return m_gf_extension_degree; + return _gf_modq_1(gf_mul_lll(a, gf_log(y))); } - inline gf2m get_cardinality() const + gf2m gf_mul_rnr(gf2m y, gf2m a) const { - return m_gf_cardinality; + return gf_mul_rrn(a, y); } - gf2m gf_pow(gf2m x, int i) ; + gf2m gf_mul_lnn(gf2m x, gf2m y) const + { + return (gf_log(x) + gf_log(y)); + } - private: - gf2m m_gf_extension_degree, m_gf_cardinality, m_gf_multiplicative_order; - std::vector<gf2m> m_gf_log_table; - std::vector<gf2m> m_gf_exp_table; + gf2m gf_mul_rnn(gf2m x, gf2m y) const + { + return _gf_modq_1(gf_mul_lnn(x, y)); + } - inline gf2m _gf_modq_1(s32bit d); - void init_log(); - void init_exp(); - }; + gf2m gf_mul_nrn(gf2m a, gf2m y) const + { + return gf_exp(_gf_modq_1((a) + gf_log(y))); + } -gf2m Gf2m_Field::_gf_modq_1(s32bit d) - { - return (((d) & gf_ord()) + ((d) >> m_gf_extension_degree)); - } + /** + * zero operand allowed + */ + gf2m gf_mul_zrz(gf2m a, gf2m y) const + { + return ( (y == 0) ? 0 : gf_mul_nrn(a, y) ); + } -gf2m Gf2m_Field::gf_mul_fast(gf2m x, gf2m y) - { - return ((y) ? m_gf_exp_table[_gf_modq_1(m_gf_log_table[x] + m_gf_log_table[y])] : 0); - } + gf2m gf_mul_zzr(gf2m a, gf2m y) const + { + return gf_mul_zrz(y, a); + } -gf2m Gf2m_Field::gf_mul_lll(gf2m a, gf2m b) - { - return (a + b); - } + /** + * non-zero operand + */ + gf2m gf_mul_nnr(gf2m y, gf2m a) const + { + return gf_mul_nrn(a, y); + } -gf2m Gf2m_Field::gf_mul_rrr(gf2m a, gf2m b) - { - return (_gf_modq_1(gf_mul_lll(a, b))); - } + gf2m gf_sqrt(gf2m x) const + { + return ((x) ? gf_exp(_gf_modq_1(gf_log(x) << (get_extension_degree()-1))) : 0); + } -gf2m Gf2m_Field::gf_mul_nrr(gf2m a, gf2m b) - { - return (gf_exp(gf_mul_rrr(a, b))); - } + gf2m gf_div_rnn(gf2m x, gf2m y) const + { + return _gf_modq_1(gf_log(x) - gf_log(y)); + } -gf2m Gf2m_Field::gf_mul_rrn(gf2m a, gf2m y) - { - return _gf_modq_1(gf_mul_lll(a, gf_log(y))); - } + gf2m gf_div_rnr(gf2m x, gf2m b) const + { + return _gf_modq_1(gf_log(x) - b); + } -gf2m Gf2m_Field::gf_mul_rnr(gf2m y, gf2m a) - { - return gf_mul_rrn(a, y); - } + gf2m gf_div_nrr(gf2m a, gf2m b) const + { + return gf_exp(_gf_modq_1(a - b)); + } -gf2m Gf2m_Field::gf_mul_lnn(gf2m x, gf2m y) - { - return (m_gf_log_table[x] + m_gf_log_table[y]); - } -gf2m Gf2m_Field::gf_mul_rnn(gf2m x, gf2m y) - { - return _gf_modq_1(gf_mul_lnn(x, y)); - } + gf2m gf_div_zzr(gf2m x, gf2m b) const + { + return ((x) ? gf_exp(_gf_modq_1(gf_log(x) - b)) : 0); + } -gf2m Gf2m_Field::gf_mul_nrn(gf2m a, gf2m y) - { - return m_gf_exp_table[_gf_modq_1((a) + m_gf_log_table[y])]; - } + gf2m gf_inv(gf2m x) const + { + return gf_exp(gf_ord() - gf_log(x)); + } -/** -* zero operand allowed -*/ -gf2m Gf2m_Field::gf_mul_zrz(gf2m a, gf2m y) - { - return ( (y == 0) ? 0 : gf_mul_nrn(a, y) ); - } + gf2m gf_inv_rn(gf2m x) const + { + return (gf_ord() - gf_log(x)); + } -gf2m Gf2m_Field::gf_mul_zzr(gf2m a, gf2m y) - { - return gf_mul_zrz(y, a); - } -/** -* non-zero operand -*/ -gf2m Gf2m_Field::gf_mul_nnr(gf2m y, gf2m a) - { - return gf_mul_nrn( a, y); - } + gf2m gf_square_ln(gf2m x) const + { + return gf_log(x) << 1; + } -gf2m Gf2m_Field::gf_sqrt(gf2m x) - { - return ((x) ? m_gf_exp_table[_gf_modq_1(m_gf_log_table[x] << (m_gf_extension_degree-1))] : 0); - } + gf2m gf_square_rr(gf2m a) const + { + return a << 1; + } -gf2m Gf2m_Field::gf_div_rnn(gf2m x, gf2m y) - { - return _gf_modq_1(m_gf_log_table[x] - m_gf_log_table[y]); - } -gf2m Gf2m_Field::gf_div_rnr(gf2m x, gf2m b) - { - return _gf_modq_1(m_gf_log_table[x] - b); - } -gf2m Gf2m_Field::gf_div_nrr(gf2m a, gf2m b) - { - return m_gf_exp_table[_gf_modq_1(a - b)]; - } + gf2m gf_l_from_n(gf2m x) const + { + return gf_log(x); + } -gf2m Gf2m_Field::gf_div_zzr(gf2m x, gf2m b) - { - return ((x) ? m_gf_exp_table[_gf_modq_1(m_gf_log_table[x] - b)] : 0); - } + gf2m gf_div(gf2m x, gf2m y) const; -gf2m Gf2m_Field::gf_inv(gf2m x) - { - return m_gf_exp_table[gf_ord() - m_gf_log_table[x]]; - } -gf2m Gf2m_Field::gf_inv_rn(gf2m x) - { - return (gf_ord() - m_gf_log_table[x]); - } + gf2m gf_pow(gf2m x, int i) const; -gf2m Gf2m_Field::gf_square_ln(gf2m x) - { - return m_gf_log_table[x] << 1; - } + gf2m gf_exp(gf2m i) const + { + return m_gf_exp_table.at(i); /* alpha^i */ + } -gf2m Gf2m_Field::gf_square_rr(gf2m a) - { - return a << 1; - } + gf2m gf_log(gf2m i) const + { + return m_gf_log_table.at(i); /* return i when x=alpha^i */ + } -gf2m Gf2m_Field::gf_l_from_n(gf2m x) - { - return m_gf_log_table[x]; - } + gf2m gf_ord() const + { + return m_gf_multiplicative_order; + } + + gf2m get_extension_degree() const + { + return m_gf_extension_degree; + } + + gf2m get_cardinality() const + { + return static_cast<gf2m>(1 << get_extension_degree()); + } + + private: + gf2m _gf_modq_1(s32bit d) const + { + /* residual modulo q-1 + when -q < d < 0, we get (q-1+d) + when 0 <= d < q, we get (d) + when q <= d < 2q-1, we get (d-q+1) + */ + return (((d) & gf_ord()) + ((d) >> get_extension_degree())); + } + + gf2m m_gf_extension_degree, m_gf_multiplicative_order; + const std::vector<gf2m>& m_gf_log_table; + const std::vector<gf2m>& m_gf_exp_table; + }; u32bit encode_gf2m(gf2m to_enc, byte* mem); @@ -231,6 +217,4 @@ gf2m decode_gf2m(const byte* mem); } -} - #endif diff --git a/src/lib/pubkey/mce/goppa_code.cpp b/src/lib/pubkey/mce/goppa_code.cpp index 175508eac..637b8175a 100644 --- a/src/lib/pubkey/mce/goppa_code.cpp +++ b/src/lib/pubkey/mce/goppa_code.cpp @@ -9,10 +9,8 @@ * */ -#include <botan/goppa_code.h> - -#include <botan/gf2m_rootfind_dcmp.h> -#include <botan/code_based_util.h> +#include <botan/internal/mce_internal.h> +#include <botan/internal/code_based_util.h> namespace Botan { @@ -48,7 +46,7 @@ secure_vector<gf2m> goppa_decode(const polyn_gf2m & syndrom_polyn, u32bit code_length = Linv.size(); u32bit t = g.get_degree(); - std::shared_ptr<gf2m_small_m::Gf2m_Field> sp_field = g.get_sp_field(); + std::shared_ptr<GF2m_Field> sp_field = g.get_sp_field(); std::pair<polyn_gf2m, polyn_gf2m> h__aux = polyn_gf2m::eea_with_coefficients( syndrom_polyn, g, 1); polyn_gf2m & h = h__aux.first; @@ -125,6 +123,37 @@ secure_vector<gf2m> goppa_decode(const polyn_gf2m & syndrom_polyn, } } +void mceliece_decrypt(secure_vector<byte>& plaintext_out, + secure_vector<byte>& error_mask_out, + const secure_vector<byte>& ciphertext, + const McEliece_PrivateKey& key) + { + mceliece_decrypt(plaintext_out, error_mask_out, ciphertext.data(), ciphertext.size(), key); + } + +void mceliece_decrypt( + secure_vector<byte>& plaintext, + secure_vector<byte> & error_mask, + const byte ciphertext[], + size_t ciphertext_len, + const McEliece_PrivateKey & key) + { + secure_vector<gf2m> error_pos; + plaintext = mceliece_decrypt(error_pos, ciphertext, ciphertext_len, key); + + const size_t code_length = key.get_code_length(); + secure_vector<byte> result((code_length+7)/8); + for(auto&& pos : error_pos) + { + if(pos > code_length) + { + throw std::invalid_argument("error position larger than code size"); + } + result[pos / 8] |= (1 << (pos % 8)); + } + + error_mask = result; + } /** * @param p_err_pos_len must point to the available length of err_pos on input, the @@ -154,30 +183,27 @@ secure_vector<byte> mceliece_decrypt( throw Invalid_Argument("mce-decryption: wrong length of cleartext buffer"); } - secure_vector<u32bit> syndrome_vec(bit_size_to_32bit_size(codimension)); - matrix_arr_mul( - key.get_H_coeffs(), - key.get_code_length(), - bit_size_to_32bit_size(codimension), - ciphertext, - syndrome_vec.data(), syndrome_vec.size() ); + matrix_arr_mul(key.get_H_coeffs(), + key.get_code_length(), + bit_size_to_32bit_size(codimension), + ciphertext, + syndrome_vec.data(), syndrome_vec.size()); + secure_vector<byte> syndrome_byte_vec(bit_size_to_byte_size(codimension)); u32bit syndrome_byte_vec_size = syndrome_byte_vec.size(); for(u32bit i = 0; i < syndrome_byte_vec_size; i++) { syndrome_byte_vec[i] = syndrome_vec[i/4] >> (8* (i % 4)); } - syndrome_polyn = polyn_gf2m(t-1, syndrome_byte_vec.data(), bit_size_to_byte_size(codimension), key.get_goppa_polyn().get_sp_field()); - + syndrome_polyn = polyn_gf2m(t-1, syndrome_byte_vec.data(), bit_size_to_byte_size(codimension), key.get_goppa_polyn().get_sp_field()); syndrome_polyn.get_degree(); error_pos = goppa_decode(syndrome_polyn, key.get_goppa_polyn(), key.get_sqrtmod(), key.get_Linv()); u32bit nb_err = error_pos.size(); - secure_vector<byte> cleartext(cleartext_len); copy_mem(cleartext.data(), ciphertext, cleartext_len); @@ -192,6 +218,7 @@ secure_vector<byte> mceliece_decrypt( } cleartext[current / 8] ^= (1 << (current % 8)); } + if(unused_pt_bits) { cleartext[cleartext_len - 1] &= unused_pt_bits_mask; diff --git a/src/lib/pubkey/mce/goppa_code.h b/src/lib/pubkey/mce/goppa_code.h deleted file mode 100644 index 377cd9b3d..000000000 --- a/src/lib/pubkey/mce/goppa_code.h +++ /dev/null @@ -1,32 +0,0 @@ -/** - * (C) Copyright Projet SECRET, INRIA, Rocquencourt - * (C) Bhaskar Biswas and Nicolas Sendrier - * - * (C) 2014 cryptosource GmbH - * (C) 2014 Falko Strenzke [email protected] - * - * Botan is released under the Simplified BSD License (see license.txt) - * - */ - -#ifndef BOTAN_MCE_GOPPA_CODE_H__ -#define BOTAN_MCE_GOPPA_CODE_H__ - -#include <botan/polyn_gf2m.h> -#include <botan/mceliece_key.h> - -namespace Botan { - -std::vector<byte> mceliece_encrypt(const secure_vector<byte>& cleartext, - const std::vector<byte>& public_matrix, - const secure_vector<gf2m> & err_pos, - u32bit code_length); - -secure_vector<byte> mceliece_decrypt(secure_vector<gf2m> & error_pos, - const byte *ciphertext, - u32bit ciphertext_len, - const McEliece_PrivateKey& key); - -} - -#endif diff --git a/src/lib/pubkey/mce/info.txt b/src/lib/pubkey/mce/info.txt index c06e23b8e..1e9b848dd 100644 --- a/src/lib/pubkey/mce/info.txt +++ b/src/lib/pubkey/mce/info.txt @@ -1,17 +1,17 @@ -define MCELIECE 20141124 +define MCELIECE 20150922 <header:public> -code_based_util.h -gf2m_rootfind_dcmp.h -gf2m_small_m.h -goppa_code.h mce_kem.h mceliece.h -mceliece_key.h polyn_gf2m.h +gf2m_small_m.h </header:public> <header:internal> -binary_matrix.h -code_based_key_gen.h +code_based_util.h +mce_internal.h </header:internal> + +<requires> +sha2_64 +</requires> diff --git a/src/lib/pubkey/mce/mce_internal.h b/src/lib/pubkey/mce/mce_internal.h new file mode 100644 index 000000000..d35479080 --- /dev/null +++ b/src/lib/pubkey/mce/mce_internal.h @@ -0,0 +1,52 @@ +/** + * (C) Copyright Projet SECRET, INRIA, Rocquencourt + * (C) Bhaskar Biswas and Nicolas Sendrier + * + * (C) 2014 cryptosource GmbH + * (C) 2014 Falko Strenzke [email protected] + * + * Botan is released under the Simplified BSD License (see license.txt) + * + */ + +#ifndef BOTAN_MCELIECE_INTERNAL_H__ +#define BOTAN_MCELIECE_INTERNAL_H__ + +#include <botan/secmem.h> +#include <botan/types.h> +#include <botan/pk_ops.h> +#include <botan/mceliece.h> + +namespace Botan { + +void mceliece_decrypt(secure_vector<byte>& plaintext_out, + secure_vector<byte>& error_mask_out, + const byte ciphertext[], + size_t ciphertext_len, + const McEliece_PrivateKey& key); + +void mceliece_decrypt(secure_vector<byte>& plaintext_out, + secure_vector<byte>& error_mask_out, + const secure_vector<byte>& ciphertext, + const McEliece_PrivateKey& key); + +secure_vector<byte> mceliece_decrypt( + secure_vector<gf2m> & error_pos, + const byte *ciphertext, u32bit ciphertext_len, + const McEliece_PrivateKey & key); + +void mceliece_encrypt(secure_vector<byte>& ciphertext_out, + secure_vector<byte>& error_mask_out, + const secure_vector<byte>& plaintext, + const McEliece_PublicKey& key, + RandomNumberGenerator& rng); + +McEliece_PrivateKey generate_mceliece_key(RandomNumberGenerator &rng, + u32bit ext_deg, + u32bit code_length, + u32bit t); + +} + + +#endif diff --git a/src/lib/pubkey/mce/mce_kem.cpp b/src/lib/pubkey/mce/mce_kem.cpp index b24c42f85..dede67731 100644 --- a/src/lib/pubkey/mce/mce_kem.cpp +++ b/src/lib/pubkey/mce/mce_kem.cpp @@ -7,56 +7,42 @@ */ #include <botan/mce_kem.h> +#include <botan/internal/mce_internal.h> #include <botan/sha2_64.h> namespace Botan { McEliece_KEM_Encryptor::McEliece_KEM_Encryptor(const McEliece_PublicKey& public_key) : - m_raw_pub_op(public_key, public_key.get_code_length()) + m_key(public_key) { } std::pair<secure_vector<byte>, secure_vector<byte>> McEliece_KEM_Encryptor::encrypt(RandomNumberGenerator& rng) { - const McEliece_PublicKey& key = m_raw_pub_op.get_key(); - secure_vector<Botan::byte> plaintext((key.get_message_word_bit_length()+7)/8); - rng.randomize(plaintext.data(), plaintext.size()); + const secure_vector<byte> plaintext = m_key.random_plaintext_element(rng); - // unset unused bits in the last plaintext byte - u32bit used = key.get_message_word_bit_length() % 8; - if(used) - { - byte mask = (1 << used) - 1; - plaintext[plaintext.size() - 1] &= mask; - } - - secure_vector<gf2m> err_pos = create_random_error_positions(key.get_code_length(), key.get_t(), rng); - - mceliece_message_parts parts(err_pos, plaintext, key.get_code_length()); - secure_vector<Botan::byte> message_and_error_input = parts.get_concat(); + secure_vector<byte> ciphertext, error_mask; + mceliece_encrypt(ciphertext, error_mask, plaintext, m_key, rng); SHA_512 hash; - hash.update(message_and_error_input); + hash.update(plaintext); + hash.update(error_mask); secure_vector<byte> sym_key = hash.final(); - secure_vector<byte> ciphertext = m_raw_pub_op.encrypt(message_and_error_input.data(), - message_and_error_input.size(), rng); return std::make_pair(ciphertext, sym_key); } - -McEliece_KEM_Decryptor::McEliece_KEM_Decryptor(const McEliece_PrivateKey& mce_key) : - m_raw_priv_op(mce_key) - { - } +McEliece_KEM_Decryptor::McEliece_KEM_Decryptor(const McEliece_PrivateKey& key) : m_key(key) { } secure_vector<Botan::byte> McEliece_KEM_Decryptor::decrypt(const byte msg[], size_t msg_len) { - secure_vector<Botan::byte> message_and_error = m_raw_priv_op.decrypt(msg, msg_len); + secure_vector<byte> plaintext, error_mask; + mceliece_decrypt(plaintext, error_mask, msg, msg_len, m_key); SHA_512 hash; - hash.update(message_and_error); + hash.update(plaintext); + hash.update(error_mask); secure_vector<byte> sym_key = hash.final(); return sym_key; diff --git a/src/lib/pubkey/mce/mce_kem.h b/src/lib/pubkey/mce/mce_kem.h index 7a8d2f7ff..cd899d568 100644 --- a/src/lib/pubkey/mce/mce_kem.h +++ b/src/lib/pubkey/mce/mce_kem.h @@ -25,7 +25,7 @@ class BOTAN_DLL McEliece_KEM_Encryptor std::pair<secure_vector<byte>, secure_vector<byte>> encrypt(RandomNumberGenerator& rng); private: - McEliece_Public_Operation m_raw_pub_op; + const McEliece_PublicKey& m_key; }; class BOTAN_DLL McEliece_KEM_Decryptor @@ -45,10 +45,10 @@ class BOTAN_DLL McEliece_KEM_Decryptor secure_vector<Botan::byte> decrypt_vec(const std::vector<byte, Alloc>& v) { return decrypt(v.data(), v.size()); - } + private: - McEliece_Private_Operation m_raw_priv_op; + const McEliece_PrivateKey& m_key; }; } diff --git a/src/lib/pubkey/mce/mceliece.cpp b/src/lib/pubkey/mce/mceliece.cpp index 6bbe93ce3..dd05b8212 100644 --- a/src/lib/pubkey/mce/mceliece.cpp +++ b/src/lib/pubkey/mce/mceliece.cpp @@ -9,165 +9,127 @@ * */ +#include <botan/internal/mce_internal.h> #include <botan/mceliece.h> -#include <botan/mceliece_key.h> -#include <botan/internal/code_based_key_gen.h> -#include <botan/polyn_gf2m.h> -#include <botan/code_based_util.h> -#include <botan/goppa_code.h> +#include <botan/internal/code_based_util.h> #include <botan/internal/bit_ops.h> -#include <botan/internal/xor_buf.h> +#include <set> namespace Botan { namespace { -void concat_vectors(byte* x, const byte* a, const byte* b, u32bit dimension, u32bit codimension) +secure_vector<byte> concat_vectors(const secure_vector<byte>& a, const secure_vector<byte>& b, + u32bit dimension, u32bit codimension) { - if(dimension % 8 == 0) + secure_vector<byte> x(bit_size_to_byte_size(dimension) + bit_size_to_byte_size(codimension)); + + const size_t final_bits = dimension % 8; + + if(final_bits == 0) { const size_t dim_bytes = bit_size_to_byte_size(dimension); - copy_mem(x, a, dim_bytes); - copy_mem(x + dim_bytes, b, bit_size_to_byte_size(codimension)); + copy_mem(&x[0], a.data(), dim_bytes); + copy_mem(&x[dim_bytes], b.data(), bit_size_to_byte_size(codimension)); } else { - u32bit i, j, k, l; - i = dimension - 8 * (dimension/ 8); - j = 8 - i; - l = dimension / 8; - copy_mem(x, a, 1 * (dimension / 8)); - x[l] = static_cast<byte>(a[l] & ((1 << i) - 1)); - - for(k = 0; k < codimension / 8; ++k) + copy_mem(&x[0], a.data(), (dimension / 8)); + u32bit l = dimension / 8; + x[l] = static_cast<byte>(a[l] & ((1 << final_bits) - 1)); + + for(u32bit k = 0; k < codimension / 8; ++k) { - x[l] ^= static_cast<byte>(b[k] << i); + x[l] ^= static_cast<byte>(b[k] << final_bits); ++l; - x[l] = static_cast<byte>(b[k] >> j); + x[l] = static_cast<byte>(b[k] >> (8 - final_bits)); } - x[l] ^= static_cast<byte>(b[k] << i); + x[l] ^= static_cast<byte>(b[codimension/8] << final_bits); } + + return x; } -std::vector<byte> mult_by_pubkey(const byte *cleartext, - std::vector<byte> const& public_matrix, - u32bit code_length, u32bit t) +secure_vector<byte> mult_by_pubkey(const secure_vector<byte>& cleartext, + std::vector<byte> const& public_matrix, + u32bit code_length, u32bit t) { - std::vector<byte> ciphertext(code_length); - u32bit i, j; - u32bit ext_deg = ceil_log2(code_length); - u32bit codimension = ext_deg * t; - u32bit dimension = code_length - codimension; - std::vector<byte> cR(bit_size_to_32bit_size(codimension)* sizeof(u32bit)); + const u32bit ext_deg = ceil_log2(code_length); + const u32bit codimension = ext_deg * t; + const u32bit dimension = code_length - codimension; + secure_vector<byte> cR(bit_size_to_32bit_size(codimension) * sizeof(u32bit)); const byte* pt = public_matrix.data(); - for(i = 0; i < dimension / 8; ++i) + for(size_t i = 0; i < dimension / 8; ++i) { - for(j = 0; j < 8; ++j) + for(size_t j = 0; j < 8; ++j) { if(cleartext[i] & (1 << j)) { xor_buf(cR.data(), pt, cR.size()); } - pt += bit_size_to_32bit_size(codimension) * sizeof(u32bit); + pt += cR.size(); } } - for(j = 0; j < dimension % 8 ; ++j) + for(size_t i = 0; i < dimension % 8 ; ++i) { - if(cleartext[i] & (1 << j)) + if(cleartext[dimension/8] & (1 << i)) { - xor_buf(cR.data(), pt, bit_size_to_byte_size(codimension)); + xor_buf(cR.data(), pt, cR.size()); } - pt += bit_size_to_32bit_size(codimension) * sizeof(u32bit); + pt += cR.size(); } - concat_vectors(ciphertext.data(), cleartext, cR.data(), dimension, codimension); + secure_vector<byte> ciphertext = concat_vectors(cleartext, cR, dimension, codimension); + ciphertext.resize((code_length+7)/8); return ciphertext; } -} - -secure_vector<gf2m> create_random_error_positions(unsigned code_length, - unsigned error_weight, - RandomNumberGenerator& rng) - { - secure_vector<gf2m> result(error_weight); - gf2m i; - for(i = 0; i < result.size(); i++) - { - unsigned j; - char try_again = 0; - do - { - try_again = 0; - gf2m new_pos = random_code_element(code_length, rng); - for(j = 0; j < i; j++) - { - if(new_pos == result[j]) - { - try_again = 1; - break; - } - } - result[i] = new_pos; - } while(try_again); - } - return result; - } - -McEliece_Private_Operation::McEliece_Private_Operation(const McEliece_PrivateKey& private_key) - :m_priv_key(private_key) +secure_vector<byte> create_random_error_vector(unsigned code_length, + unsigned error_weight, + RandomNumberGenerator& rng) { - } - -secure_vector<byte> McEliece_Private_Operation::decrypt(const byte msg[], size_t msg_len) - { - secure_vector<gf2m> err_pos; + secure_vector<byte> result((code_length+7)/8); - secure_vector<byte> plaintext = mceliece_decrypt( - err_pos, - msg, msg_len, - m_priv_key - ); + size_t bits_set = 0; - return mceliece_message_parts(err_pos, plaintext, m_priv_key.get_code_length()).get_concat(); - } + while(bits_set < error_weight) + { + gf2m x = random_code_element(code_length, rng); -McEliece_Public_Operation::McEliece_Public_Operation(const McEliece_PublicKey& public_key, u32bit the_code_length) - :m_pub_key(public_key), - m_code_length(the_code_length) - {} + const size_t byte_pos = x / 8, bit_pos = x % 8; -secure_vector<byte> McEliece_Public_Operation::encrypt(const byte msg[], size_t msg_len, RandomNumberGenerator&) - { - mceliece_message_parts parts(msg, msg_len, m_pub_key.get_code_length()); - secure_vector<gf2m> err_pos = parts.get_error_positions(); - secure_vector<byte> message_word = parts.get_message_word(); - secure_vector<byte> ciphertext((m_pub_key.get_code_length()+7)/8); + const byte mask = (1 << bit_pos); + if(result[byte_pos] & mask) + continue; // already set this bit - std::vector<byte> ciphertext_tmp = mceliece_encrypt( message_word, m_pub_key.get_public_matrix(), err_pos, m_code_length); + result[byte_pos] |= mask; + bits_set++; + } - copy_mem(ciphertext.data(), ciphertext_tmp.data(), ciphertext.size()); - return ciphertext; + return result; } -std::vector<byte> mceliece_encrypt(const secure_vector<byte> & cleartext, - std::vector<byte> const& public_matrix, - const secure_vector<gf2m> & err_pos, - u32bit code_length) +} + +void mceliece_encrypt(secure_vector<byte>& ciphertext_out, + secure_vector<byte>& error_mask_out, + const secure_vector<byte>& plaintext, + const McEliece_PublicKey& key, + RandomNumberGenerator& rng) { - std::vector<byte> ciphertext = mult_by_pubkey(cleartext.data(), public_matrix, code_length, err_pos.size()); + secure_vector<byte> error_mask = create_random_error_vector(key.get_code_length(), key.get_t(), rng); - // flip t error positions - for(size_t i = 0; i < err_pos.size(); ++i) - { - ciphertext[err_pos[i] / 8] ^= (1 << (err_pos[i] % 8)); - } + secure_vector<byte> ciphertext = mult_by_pubkey(plaintext, key.get_public_matrix(), + key.get_code_length(), key.get_t()); - return ciphertext; + ciphertext ^= error_mask; + + ciphertext_out.swap(ciphertext); + error_mask_out.swap(error_mask); } } diff --git a/src/lib/pubkey/mce/mceliece.h b/src/lib/pubkey/mce/mceliece.h index c5f02470f..ead326230 100644 --- a/src/lib/pubkey/mce/mceliece.h +++ b/src/lib/pubkey/mce/mceliece.h @@ -9,141 +9,128 @@ * */ -#ifndef BOTAN_MCELIECE_H__ -#define BOTAN_MCELIECE_H__ +#ifndef BOTAN_MCELIECE_KEY_H__ +#define BOTAN_MCELIECE_KEY_H__ -#include <botan/secmem.h> -#include <botan/types.h> -#include <botan/pk_ops.h> -#include <botan/mceliece_key.h> - -#define MASK_LOG2_BYTE ((1 << 3) - 1) -#define _BITP_TO_BYTEP(__bit_pos) (__bit_pos >> 3) -#define _BITP_TO_BYTEOFFS(__bit_pos) (__bit_pos & MASK_LOG2_BYTE) +#include <botan/pk_keys.h> +#include <botan/polyn_gf2m.h> +#include <botan/exceptn.h> namespace Botan { -secure_vector<gf2m> BOTAN_DLL create_random_error_positions(unsigned code_length, unsigned error_weight, RandomNumberGenerator& rng); - -class mceliece_message_parts +class BOTAN_DLL McEliece_PublicKey : public virtual Public_Key { public: + McEliece_PublicKey(const std::vector<byte>& key_bits); - mceliece_message_parts(const secure_vector<gf2m>& err_pos, const byte* message, u32bit message_length, u32bit code_length) : - m_error_vector(error_vector_from_error_positions(err_pos.data(), err_pos.size(), code_length)), - m_code_length(code_length) - { - m_message_word.resize(message_length); - copy_mem(m_message_word.data(), message, message_length); - } - - mceliece_message_parts(const secure_vector<gf2m>& err_pos, const secure_vector<byte>& message, unsigned code_length) : - m_error_vector(error_vector_from_error_positions(err_pos.data(), err_pos.size(), code_length)), - m_message_word(message), - m_code_length(code_length) - {} - - static secure_vector<byte> error_vector_from_error_positions(const gf2m* err_pos, size_t err_pos_len, size_t code_length) - { - secure_vector<byte> result((code_length+7)/8); - for(unsigned i = 0; i < err_pos_len; i++) - { - u16bit pos = err_pos[i]; - u32bit byte_pos = _BITP_TO_BYTEP(pos); - if(byte_pos > result.size()) - { - throw Invalid_Argument("error position larger than code size"); - } - result[byte_pos] |= (1 << _BITP_TO_BYTEOFFS(pos)); - } - return result; - } - - mceliece_message_parts(const byte* message_concat_errors, size_t message_concat_errors_len, unsigned code_length) : - m_code_length(code_length) - { - size_t err_vec_len = (code_length+7)/8; - if(message_concat_errors_len < err_vec_len ) - { - throw Invalid_Argument("cannot split McEliece message parts"); - } - size_t err_vec_start_pos = message_concat_errors_len - err_vec_len; - m_message_word = secure_vector<byte>(err_vec_start_pos); - copy_mem(m_message_word.data(), message_concat_errors, err_vec_start_pos); - m_error_vector = secure_vector<byte>(err_vec_len); - copy_mem(m_error_vector.data(), &message_concat_errors[err_vec_start_pos], err_vec_len); - } - - secure_vector<byte> get_concat() const - { - secure_vector<byte> result(m_error_vector.size() + m_message_word.size()); - copy_mem(result.data(), m_message_word.data(), m_message_word.size()); - copy_mem(&result[m_message_word.size()], m_error_vector.data(), m_error_vector.size()); - return result; - } - - secure_vector<gf2m> get_error_positions() const - { - secure_vector<gf2m> result; - for(unsigned i = 0; i < m_code_length; i++) - { - if(i >= m_code_length) - { - throw Invalid_Argument("index out of range in get_error_positions()"); - } - if((m_error_vector[_BITP_TO_BYTEP(i)] >> _BITP_TO_BYTEOFFS(i)) & 1) - { - result.push_back(i); - } - } - return result; - } - - secure_vector<byte> get_error_vector() const { return m_error_vector; } - secure_vector<byte> get_message_word() const { return m_message_word; } - private: - secure_vector<byte> m_error_vector; - secure_vector<byte> m_message_word; - unsigned m_code_length; - }; + McEliece_PublicKey(std::vector<byte> const& pub_matrix, u32bit the_t, u32bit the_code_length) : + m_public_matrix(pub_matrix), + m_t(the_t), + m_code_length(the_code_length) + {} -class BOTAN_DLL McEliece_Private_Operation : public PK_Ops::Decryption - { - public: - McEliece_Private_Operation(const McEliece_PrivateKey& mce_key); + McEliece_PublicKey(const McEliece_PublicKey& other); - size_t max_input_bits() const override { return m_priv_key.max_input_bits(); } + secure_vector<byte> random_plaintext_element(RandomNumberGenerator& rng) const; - secure_vector<byte> decrypt(const byte msg[], size_t msg_len) override; + std::string algo_name() const override { return "McEliece"; } - McEliece_PrivateKey const& get_key() const { return m_priv_key; } + /** + * Get the maximum number of bits allowed to be fed to this key. + * @result the maximum number of input bits + */ + size_t max_input_bits() const override { return get_message_word_bit_length(); } - private: - const McEliece_PrivateKey m_priv_key; + AlgorithmIdentifier algorithm_identifier() const override; + + size_t estimated_strength() const override; + + std::vector<byte> x509_subject_public_key() const override; + + bool check_key(RandomNumberGenerator&, bool) const override + { return true; } + + u32bit get_t() const { return m_t; } + u32bit get_code_length() const { return m_code_length; } + u32bit get_message_word_bit_length() const; + const std::vector<byte>& get_public_matrix() const { return m_public_matrix; } + + bool operator==(const McEliece_PublicKey& other) const; + bool operator!=(const McEliece_PublicKey& other) const { return !(*this == other); } + + protected: + McEliece_PublicKey() {} + + std::vector<byte> m_public_matrix; + u32bit m_t; + u32bit m_code_length; }; -class BOTAN_DLL McEliece_Public_Operation : public PK_Ops::Encryption +class BOTAN_DLL McEliece_PrivateKey : public virtual McEliece_PublicKey, + public virtual Private_Key { public: - McEliece_Public_Operation(const McEliece_PublicKey& public_key, u32bit code_length); + /** + * Get the maximum number of bits allowed to be fed to this key. + * @result the maximum number of input bits + */ + size_t max_input_bits() const override { return m_Linv.size(); } + + /** + Generate a McEliece key pair + + Suggested parameters for a given security level (SL) + + SL=80 n=1632 t=33 - 59 KB pubkey 140 KB privkey + SL=107 n=2480 t=45 - 128 KB pubkey 300 KB privkey + SL=128 n=2960 t=57 - 195 KB pubkey 459 KB privkey + SL=147 n=3408 t=67 - 265 KB pubkey 622 KB privkey + SL=191 n=4624 t=95 - 516 KB pubkey 1234 KB privkey + SL=256 n=6624 t=115 - 942 KB pubkey 2184 KB privkey + */ + McEliece_PrivateKey(RandomNumberGenerator& rng, size_t code_length, size_t t); + + McEliece_PrivateKey(const secure_vector<byte>& key_bits); + + McEliece_PrivateKey(polyn_gf2m const& goppa_polyn, + std::vector<u32bit> const& parity_check_matrix_coeffs, + std::vector<polyn_gf2m> const& square_root_matrix, + std::vector<gf2m> const& inverse_support, + std::vector<byte> const& public_matrix ); + + bool check_key(RandomNumberGenerator& rng, bool strong) const override; - size_t max_input_bits() const override { return m_pub_key.max_input_bits(); } - secure_vector<byte> encrypt(const byte msg[], size_t msg_len, RandomNumberGenerator&) override; + polyn_gf2m const& get_goppa_polyn() const { return m_g; } + std::vector<u32bit> const& get_H_coeffs() const { return m_coeffs; } + std::vector<gf2m> const& get_Linv() const { return m_Linv; } + std::vector<polyn_gf2m> const& get_sqrtmod() const { return m_sqrtmod; } - McEliece_PublicKey const& get_key() const { return m_pub_key; } + inline u32bit get_dimension() const { return m_dimension; } + + inline u32bit get_codimension() const { return m_codimension; } + + secure_vector<byte> pkcs8_private_key() const override; + + bool operator==(const McEliece_PrivateKey & other) const; + + bool operator!=(const McEliece_PrivateKey& other) const { return !(*this == other); } private: - McEliece_PublicKey m_pub_key; - u32bit m_code_length; + polyn_gf2m m_g; + std::vector<polyn_gf2m> m_sqrtmod; + std::vector<gf2m> m_Linv; + std::vector<u32bit> m_coeffs; + + u32bit m_codimension; + u32bit m_dimension; }; /** * Estimate work factor for McEliece * @return estimated security level for these key parameters */ -BOTAN_DLL size_t mceliece_work_factor(size_t code_size, size_t k, size_t t); +BOTAN_DLL size_t mceliece_work_factor(size_t code_size, size_t t); } - #endif diff --git a/src/lib/pubkey/mce/mceliece_key.cpp b/src/lib/pubkey/mce/mceliece_key.cpp index 8cda0af89..8edbbf88a 100644 --- a/src/lib/pubkey/mce/mceliece_key.cpp +++ b/src/lib/pubkey/mce/mceliece_key.cpp @@ -9,15 +9,12 @@ * */ -#include <botan/mceliece_key.h> -#include <botan/internal/bit_ops.h> -#include <botan/gf2m_small_m.h> #include <botan/mceliece.h> -#include <botan/internal/code_based_key_gen.h> -#include <botan/code_based_util.h> +#include <botan/internal/mce_internal.h> +#include <botan/internal/bit_ops.h> +#include <botan/internal/code_based_util.h> #include <botan/der_enc.h> #include <botan/ber_dec.h> -#include <botan/workfactor.h> namespace Botan { @@ -42,12 +39,29 @@ McEliece_PrivateKey::McEliece_PrivateKey(RandomNumberGenerator& rng, size_t code *this = generate_mceliece_key(rng, ext_deg, code_length, t); } -unsigned McEliece_PublicKey::get_message_word_bit_length() const +u32bit McEliece_PublicKey::get_message_word_bit_length() const { u32bit codimension = ceil_log2(m_code_length) * m_t; return m_code_length - codimension; } +secure_vector<byte> McEliece_PublicKey::random_plaintext_element(RandomNumberGenerator& rng) const + { + const size_t bits = get_message_word_bit_length(); + + secure_vector<byte> plaintext((bits+7)/8); + rng.randomize(plaintext.data(), plaintext.size()); + + // unset unused bits in the last plaintext byte + if(u32bit used = bits % 8) + { + const byte mask = (1 << used) - 1; + plaintext[plaintext.size() - 1] &= mask; + } + + return plaintext; + } + AlgorithmIdentifier McEliece_PublicKey::algorithm_identifier() const { return AlgorithmIdentifier(get_oid(), std::vector<byte>()); @@ -55,16 +69,15 @@ AlgorithmIdentifier McEliece_PublicKey::algorithm_identifier() const std::vector<byte> McEliece_PublicKey::x509_subject_public_key() const { - // encode the public key - return unlock(DER_Encoder() - .start_cons(SEQUENCE) - .start_cons(SEQUENCE) - .encode(static_cast<size_t>(get_code_length())) - .encode(static_cast<size_t>(get_t())) - .end_cons() - .encode(m_public_matrix, OCTET_STRING) - .end_cons() - .get_contents()); + return DER_Encoder() + .start_cons(SEQUENCE) + .start_cons(SEQUENCE) + .encode(static_cast<size_t>(get_code_length())) + .encode(static_cast<size_t>(get_t())) + .end_cons() + .encode(m_public_matrix, OCTET_STRING) + .end_cons() + .get_contents_unlocked(); } McEliece_PublicKey::McEliece_PublicKey(const McEliece_PublicKey & other) : @@ -76,9 +89,7 @@ McEliece_PublicKey::McEliece_PublicKey(const McEliece_PublicKey & other) : size_t McEliece_PublicKey::estimated_strength() const { - const u32bit ext_deg = ceil_log2(m_code_length); - const size_t k = m_code_length - ext_deg * m_t; - return mceliece_work_factor(m_code_length, k, m_t); + return mceliece_work_factor(m_code_length, m_t); } McEliece_PublicKey::McEliece_PublicKey(const std::vector<byte>& key_bits) @@ -135,19 +146,20 @@ secure_vector<byte> McEliece_PrivateKey::pkcs8_private_key() const bool McEliece_PrivateKey::check_key(RandomNumberGenerator& rng, bool) const { - McEliece_Private_Operation priv_op(*this); - McEliece_Public_Operation pub_op(*this, get_code_length()); + const secure_vector<byte> plaintext = this->random_plaintext_element(rng); - secure_vector<byte> plaintext((this->get_message_word_bit_length()+7)/8); - rng.randomize(plaintext.data(), plaintext.size() - 1); - const secure_vector<gf2m> err_pos = create_random_error_positions(this->get_code_length(), this->get_t(), rng); + secure_vector<byte> ciphertext; + secure_vector<byte> errors; + mceliece_encrypt(ciphertext, errors, plaintext, *this, rng); - mceliece_message_parts parts(err_pos, plaintext, this->get_code_length()); - secure_vector<byte> message_and_error_input = parts.get_concat(); - secure_vector<byte> ciphertext = pub_op.encrypt(message_and_error_input.data(), message_and_error_input.size(), rng); - secure_vector<byte> message_and_error_output = priv_op.decrypt(ciphertext.data(), ciphertext.size()); + secure_vector<byte> plaintext_out; + secure_vector<byte> errors_out; + mceliece_decrypt(plaintext_out, errors_out, ciphertext, *this); - return (message_and_error_input == message_and_error_output); + if(errors != errors_out || plaintext != plaintext_out) + return false; + + return true; } McEliece_PrivateKey::McEliece_PrivateKey(const secure_vector<byte>& key_bits) @@ -172,7 +184,7 @@ McEliece_PrivateKey::McEliece_PrivateKey(const secure_vector<byte>& key_bits) m_codimension = (ext_deg * t); m_dimension = (n - m_codimension); - std::shared_ptr<gf2m_small_m::Gf2m_Field> sp_field(new gf2m_small_m::Gf2m_Field(ext_deg)); + std::shared_ptr<GF2m_Field> sp_field(new GF2m_Field(ext_deg)); m_g = polyn_gf2m(g_enc, sp_field); if(m_g.get_degree() != static_cast<int>(t)) { @@ -231,7 +243,6 @@ McEliece_PrivateKey::McEliece_PrivateKey(const secure_vector<byte>& key_bits) } - bool McEliece_PrivateKey::operator==(const McEliece_PrivateKey & other) const { if(*static_cast<const McEliece_PublicKey*>(this) != *static_cast<const McEliece_PublicKey*>(&other)) diff --git a/src/lib/pubkey/mce/mceliece_key.h b/src/lib/pubkey/mce/mceliece_key.h deleted file mode 100644 index 65ab04f16..000000000 --- a/src/lib/pubkey/mce/mceliece_key.h +++ /dev/null @@ -1,126 +0,0 @@ -/** - * (C) Copyright Projet SECRET, INRIA, Rocquencourt - * (C) Bhaskar Biswas and Nicolas Sendrier - * - * (C) 2014 cryptosource GmbH - * (C) 2014 Falko Strenzke [email protected] - * - * Botan is released under the Simplified BSD License (see license.txt) - * - */ - -#ifndef BOTAN_MCELIECE_KEY_H__ -#define BOTAN_MCELIECE_KEY_H__ - -#include <botan/exceptn.h> -#include <botan/pk_keys.h> -#include <botan/polyn_gf2m.h> - -namespace Botan { - -class BOTAN_DLL McEliece_PublicKey : public virtual Public_Key - { - public: - - McEliece_PublicKey(const std::vector<byte>& key_bits); - - McEliece_PublicKey(std::vector<byte> const& pub_matrix, u32bit the_t, u32bit the_code_length) : - m_public_matrix(pub_matrix), - m_t(the_t), - m_code_length(the_code_length) - {} - - McEliece_PublicKey(const McEliece_PublicKey & other); - - std::string algo_name() const override { return "McEliece"; } - - /** - * Get the maximum number of bits allowed to be fed to this key. - * This is the bitlength of the order of the base point. - * @result the maximum number of input bits - */ - size_t max_input_bits() const override - { - return get_message_word_bit_length(); - }; - - AlgorithmIdentifier algorithm_identifier() const override; - - size_t estimated_strength() const override; - - std::vector<byte> x509_subject_public_key() const override; - - bool check_key(RandomNumberGenerator&, bool) const override - { return true; } - - u32bit get_t() const { return m_t; } - u32bit get_code_length() const { return m_code_length; } - u32bit get_message_word_bit_length() const; - std::vector<byte> const& get_public_matrix() const { return m_public_matrix; } - - bool operator==(const McEliece_PublicKey& other) const; - bool operator!=(const McEliece_PublicKey& other) const { return !(*this == other); } - - protected: - McEliece_PublicKey() {} - - std::vector<byte> m_public_matrix; - u32bit m_t; - u32bit m_code_length; - }; - -class BOTAN_DLL McEliece_PrivateKey : public virtual McEliece_PublicKey, - public virtual Private_Key - { - public: - /** - * Get the maximum number of bits allowed to be fed to this key. - * This is the bitlength of the order of the base point. - * @result the maximum number of input bits - */ - size_t max_input_bits() const override { - return m_Linv.size(); - }; - - McEliece_PrivateKey(const secure_vector<byte>& key_bits); - - McEliece_PrivateKey(polyn_gf2m const& goppa_polyn, - std::vector<u32bit> const& parity_check_matrix_coeffs, - std::vector<polyn_gf2m> const& square_root_matrix, - std::vector<gf2m> const& inverse_support, - std::vector<byte> const& public_matrix ); - - McEliece_PrivateKey(RandomNumberGenerator& rng, size_t code_length, size_t t); - bool check_key(RandomNumberGenerator& rng, bool strong) const override; - - polyn_gf2m const& get_goppa_polyn() const { return m_g; }; - std::vector<u32bit> const& get_H_coeffs() const { return m_coeffs; }; - std::vector<gf2m> const& get_Linv() const { return m_Linv; }; - std::vector<polyn_gf2m> const& get_sqrtmod() const { return m_sqrtmod; }; - - inline u32bit get_dimension() const - { return m_dimension; }; - - inline u32bit get_codimension() const - { return m_codimension; }; - - - secure_vector<byte> pkcs8_private_key() const override; - - bool operator==(const McEliece_PrivateKey & other) const; - - bool operator!=(const McEliece_PrivateKey& other) const { return !(*this == other); }; - - private: - polyn_gf2m m_g; - std::vector<polyn_gf2m> m_sqrtmod; - std::vector<gf2m> m_Linv; - std::vector<u32bit> m_coeffs; - - u32bit m_codimension; - u32bit m_dimension; - }; - -} - -#endif diff --git a/src/lib/pubkey/mce/polyn_gf2m.cpp b/src/lib/pubkey/mce/polyn_gf2m.cpp index 9b3366757..4d9bcf2e8 100644 --- a/src/lib/pubkey/mce/polyn_gf2m.cpp +++ b/src/lib/pubkey/mce/polyn_gf2m.cpp @@ -10,15 +10,13 @@ */ #include <botan/polyn_gf2m.h> -#include <botan/gf2m_rootfind_dcmp.h> -#include <botan/code_based_util.h> -#include <botan/gf2m_small_m.h> +#include <botan/internal/code_based_util.h> #include <botan/internal/bit_ops.h> +#include <botan/rng.h> +#include <botan/exceptn.h> namespace Botan { -using namespace Botan::gf2m_small_m; - namespace { gf2m generate_gf2m_mask(gf2m a) @@ -40,8 +38,6 @@ unsigned nlz_16bit(u16bit x) } } -using namespace Botan::gf2m_small_m; - int polyn_gf2m::calc_degree_secure() const { int i = this->coeff.size() - 1; @@ -86,7 +82,7 @@ polyn_gf2m::polyn_gf2m(polyn_gf2m const& other) msp_field(other.msp_field) { } -polyn_gf2m::polyn_gf2m( int d, std::shared_ptr<gf2m_small_m::Gf2m_Field> sp_field) +polyn_gf2m::polyn_gf2m( int d, std::shared_ptr<GF2m_Field> sp_field) :m_deg(-1), coeff(d+1), msp_field(sp_field) @@ -115,7 +111,7 @@ void polyn_gf2m::realloc(u32bit new_size) this->coeff = secure_vector<gf2m>(new_size); } -polyn_gf2m::polyn_gf2m(const byte* mem, u32bit mem_len, std::shared_ptr<gf2m_small_m::Gf2m_Field> sp_field) +polyn_gf2m::polyn_gf2m(const byte* mem, u32bit mem_len, std::shared_ptr<GF2m_Field> sp_field) :msp_field(sp_field) { if(mem_len % sizeof(gf2m)) @@ -128,7 +124,7 @@ polyn_gf2m::polyn_gf2m(const byte* mem, u32bit mem_len, std::shared_ptr<gf2m_sma this->m_deg = -1; for(u32bit i = 0; i < size; i++) { - this->coeff[i] = gf2m_small_m::decode_gf2m(mem); + this->coeff[i] = decode_gf2m(mem); mem += sizeof(this->coeff[0]); } for(u32bit i = 0; i < size; i++) @@ -142,13 +138,13 @@ polyn_gf2m::polyn_gf2m(const byte* mem, u32bit mem_len, std::shared_ptr<gf2m_sma } -polyn_gf2m::polyn_gf2m( std::shared_ptr<gf2m_small_m::Gf2m_Field> sp_field ) +polyn_gf2m::polyn_gf2m( std::shared_ptr<GF2m_Field> sp_field ) : m_deg(-1), coeff(1), msp_field(sp_field) {} -polyn_gf2m::polyn_gf2m(int degree, const unsigned char* mem, u32bit mem_byte_len, std::shared_ptr<gf2m_small_m::Gf2m_Field> sp_field) +polyn_gf2m::polyn_gf2m(int degree, const unsigned char* mem, u32bit mem_byte_len, std::shared_ptr<GF2m_Field> sp_field) :msp_field(sp_field) { u32bit j, k, l; @@ -229,7 +225,7 @@ int polyn_gf2m::get_degree() const } -static gf2m eval_aux(const gf2m * /*restrict*/ coeff, gf2m a, int d, std::shared_ptr<gf2m_small_m::Gf2m_Field> sp_field) +static gf2m eval_aux(const gf2m * /*restrict*/ coeff, gf2m a, int d, std::shared_ptr<GF2m_Field> sp_field) { gf2m b; b = coeff[d--]; @@ -255,7 +251,7 @@ gf2m polyn_gf2m::eval(gf2m a) void polyn_gf2m::remainder(polyn_gf2m &p, const polyn_gf2m & g) { int i, j, d; - std::shared_ptr<gf2m_small_m::Gf2m_Field> msp_field = g.msp_field; + std::shared_ptr<GF2m_Field> msp_field = g.msp_field; d = p.get_degree() - g.get_degree(); if (d >= 0) { gf2m la = msp_field->gf_inv_rn(g.get_lead_coef()); @@ -314,7 +310,7 @@ polyn_gf2m polyn_gf2m::sqmod( const std::vector<polyn_gf2m> & sq, int d) { int i, j; gf2m la; - std::shared_ptr<gf2m_small_m::Gf2m_Field> sp_field = this->msp_field; + std::shared_ptr<GF2m_Field> sp_field = this->msp_field; polyn_gf2m result(d - 1, sp_field); // terms of low degree @@ -438,7 +434,7 @@ void polyn_gf2m::patchup_deg_secure( u32bit trgt_deg, volatile gf2m patch_elem) std::pair<polyn_gf2m, polyn_gf2m> polyn_gf2m::eea_with_coefficients( const polyn_gf2m & p, const polyn_gf2m & g, int break_deg) { - std::shared_ptr<gf2m_small_m::Gf2m_Field> msp_field = g.msp_field; + std::shared_ptr<GF2m_Field> msp_field = g.msp_field; int i, j, dr, du, delta; gf2m a; polyn_gf2m aux; @@ -512,7 +508,7 @@ std::pair<polyn_gf2m, polyn_gf2m> polyn_gf2m::eea_with_coefficients( const polyn else { /* t odd */ - cond1 = r0.get_degree() <= break_deg - 1; + cond1 = r0.get_degree() < break_deg; cond2 = u0.get_degree() < break_deg - 1; cond1 &= cond2; } @@ -625,7 +621,7 @@ std::pair<polyn_gf2m, polyn_gf2m> polyn_gf2m::eea_with_coefficients( const polyn return std::make_pair(u1,r1); // coefficients u,v } -polyn_gf2m::polyn_gf2m(int t, Botan::RandomNumberGenerator& rng, std::shared_ptr<gf2m_small_m::Gf2m_Field> sp_field) +polyn_gf2m::polyn_gf2m(int t, Botan::RandomNumberGenerator& rng, std::shared_ptr<GF2m_Field> sp_field) :m_deg(t), coeff(t+1), msp_field(sp_field) @@ -655,7 +651,7 @@ void polyn_gf2m::poly_shiftmod( const polyn_gf2m & g) { throw Invalid_Argument("shiftmod cannot be called on polynomials of degree 0 or less"); } - std::shared_ptr<gf2m_small_m::Gf2m_Field> msp_field = g.msp_field; + std::shared_ptr<GF2m_Field> msp_field = g.msp_field; t = g.get_degree(); a = msp_field->gf_div(this->coeff[t-1], g.coeff[t]); @@ -670,7 +666,7 @@ std::vector<polyn_gf2m> polyn_gf2m::sqrt_mod_init(const polyn_gf2m & g) { u32bit i, t; u32bit nb_polyn_sqrt_mat; - std::shared_ptr<gf2m_small_m::Gf2m_Field> msp_field = g.msp_field; + std::shared_ptr<GF2m_Field> msp_field = g.msp_field; std::vector<polyn_gf2m> result; t = g.get_degree(); nb_polyn_sqrt_mat = t/2; @@ -717,7 +713,7 @@ std::vector<polyn_gf2m> syndrome_init(polyn_gf2m const& generator, std::vector<g gf2m a; - std::shared_ptr<gf2m_small_m::Gf2m_Field> msp_field = generator.msp_field; + std::shared_ptr<GF2m_Field> msp_field = generator.msp_field; std::vector<polyn_gf2m> result; t = generator.get_degree(); @@ -744,7 +740,7 @@ std::vector<polyn_gf2m> syndrome_init(polyn_gf2m const& generator, std::vector<g return result; } -polyn_gf2m::polyn_gf2m(const secure_vector<byte>& encoded, std::shared_ptr<gf2m_small_m::Gf2m_Field> sp_field ) +polyn_gf2m::polyn_gf2m(const secure_vector<byte>& encoded, std::shared_ptr<GF2m_Field> sp_field ) :msp_field(sp_field) { if(encoded.size() % 2) diff --git a/src/lib/pubkey/mce/polyn_gf2m.h b/src/lib/pubkey/mce/polyn_gf2m.h index 6ec028a25..1c8cc5211 100644 --- a/src/lib/pubkey/mce/polyn_gf2m.h +++ b/src/lib/pubkey/mce/polyn_gf2m.h @@ -12,14 +12,14 @@ #ifndef BOTAN_POLYN_GF2M_H__ #define BOTAN_POLYN_GF2M_H__ +#include <botan/secmem.h> #include <botan/gf2m_small_m.h> -#include <botan/rng.h> #include <memory> #include <utility> namespace Botan { -using namespace gf2m_small_m; +class RandomNumberGenerator; struct polyn_gf2m { @@ -27,13 +27,13 @@ struct polyn_gf2m /** * create a zero polynomial: */ - polyn_gf2m( std::shared_ptr<gf2m_small_m::Gf2m_Field> sp_field ); + polyn_gf2m( std::shared_ptr<GF2m_Field> sp_field ); polyn_gf2m() :m_deg(-1) {}; - polyn_gf2m(const secure_vector<byte>& encoded, std::shared_ptr<gf2m_small_m::Gf2m_Field> sp_field ); + polyn_gf2m(const secure_vector<byte>& encoded, std::shared_ptr<GF2m_Field> sp_field ); polyn_gf2m& operator=(const polyn_gf2m&) = default; @@ -61,7 +61,7 @@ struct polyn_gf2m /** * create zero polynomial with reservation of space for a degree d polynomial */ - polyn_gf2m(int d, std::shared_ptr<gf2m_small_m::Gf2m_Field> sp_field); + polyn_gf2m(int d, std::shared_ptr<GF2m_Field> sp_field); polyn_gf2m(polyn_gf2m const& other); /** @@ -71,9 +71,9 @@ struct polyn_gf2m /** * random irreducible polynomial of degree t */ - polyn_gf2m(int t, RandomNumberGenerator& rng, std::shared_ptr<gf2m_small_m::Gf2m_Field> sp_field); + polyn_gf2m(int t, RandomNumberGenerator& rng, std::shared_ptr<GF2m_Field> sp_field); - std::shared_ptr<gf2m_small_m::Gf2m_Field> get_sp_field() const + std::shared_ptr<GF2m_Field> get_sp_field() const { return msp_field; }; gf2m& operator[](size_t i) { return coeff[i]; }; @@ -97,12 +97,12 @@ struct polyn_gf2m std::string to_string() const; /** decode a polynomial from memory: **/ - polyn_gf2m(const byte* mem, u32bit mem_len, std::shared_ptr<gf2m_small_m::Gf2m_Field> sp_field); + polyn_gf2m(const byte* mem, u32bit mem_len, std::shared_ptr<GF2m_Field> sp_field); // remove one! ^v! /** * create a polynomial from memory area (encoded) */ - polyn_gf2m(int degree, const unsigned char* mem, u32bit mem_byte_len, std::shared_ptr<gf2m_small_m::Gf2m_Field> sp_field); + polyn_gf2m(int degree, const unsigned char* mem, u32bit mem_byte_len, std::shared_ptr<GF2m_Field> sp_field); void encode(u32bit min_numo_coeffs, byte* mem, u32bit mem_len) const; @@ -149,13 +149,19 @@ struct polyn_gf2m public: int m_deg; secure_vector<gf2m> coeff; - std::shared_ptr<gf2m_small_m::Gf2m_Field> msp_field; + std::shared_ptr<GF2m_Field> msp_field; }; gf2m random_code_element(unsigned code_length, RandomNumberGenerator& rng); std::vector<polyn_gf2m> syndrome_init(polyn_gf2m const& generator, std::vector<gf2m> const& support, int n); +/** +* Find the roots of a polynomial over GF(2^m) using the method by Federenko +* et al. +*/ +secure_vector<gf2m> find_roots_gf2m_decomp(const polyn_gf2m & polyn, u32bit code_length); + } #endif diff --git a/src/lib/pubkey/mce/workfactor.cpp b/src/lib/pubkey/mce/workfactor.cpp index e7cf631d4..9594c0aab 100644 --- a/src/lib/pubkey/mce/workfactor.cpp +++ b/src/lib/pubkey/mce/workfactor.cpp @@ -8,6 +8,7 @@ */ #include <botan/mceliece.h> +#include <botan/internal/bit_ops.h> #include <cmath> namespace Botan { @@ -91,8 +92,10 @@ double best_wf(size_t n, size_t k, size_t w, size_t p) } -size_t mceliece_work_factor(size_t n, size_t k, size_t t) +size_t mceliece_work_factor(size_t n, size_t t) { + const size_t k = n - ceil_log2(n) * t; + double min = cout_total(n, k, t, 0, 0); // correspond a p=1 for(size_t p = 0; p != t / 2; ++p) { |