Botan
1.11.15
|
00001 /** 00002 * (C) Copyright Projet SECRET, INRIA, Rocquencourt 00003 * (C) Bhaskar Biswas and Nicolas Sendrier 00004 * 00005 * (C) 2014 cryptosource GmbH 00006 * (C) 2014 Falko Strenzke fstrenzke@cryptosource.de 00007 * 00008 * Botan is released under the Simplified BSD License (see license.txt) 00009 * 00010 */ 00011 00012 #include <botan/goppa_code.h> 00013 00014 #include <botan/gf2m_rootfind_dcmp.h> 00015 #include <botan/code_based_util.h> 00016 00017 namespace Botan { 00018 00019 namespace { 00020 00021 void matrix_arr_mul(std::vector<u32bit> matrix, 00022 u32bit numo_rows, 00023 u32bit words_per_row, 00024 const byte* input_vec, 00025 u32bit* output_vec, u32bit output_vec_len) 00026 { 00027 for(size_t j = 0; j < numo_rows; j++) 00028 { 00029 if((input_vec[j / 8] >> (j % 8)) & 1) 00030 { 00031 for(size_t i = 0; i < output_vec_len; i ++) 00032 { 00033 output_vec[i] ^= matrix[ j * (words_per_row) + i]; 00034 } 00035 } 00036 } 00037 } 00038 00039 /** 00040 * returns the error vector to the syndrome 00041 */ 00042 secure_vector<gf2m> goppa_decode(const polyn_gf2m & syndrom_polyn, 00043 const polyn_gf2m & g, 00044 const std::vector<polyn_gf2m> & sqrtmod, 00045 const std::vector<gf2m> & Linv) 00046 { 00047 gf2m a; 00048 u32bit code_length = Linv.size(); 00049 u32bit t = g.get_degree(); 00050 00051 std::shared_ptr<gf2m_small_m::Gf2m_Field> sp_field = g.get_sp_field(); 00052 00053 std::pair<polyn_gf2m, polyn_gf2m> h__aux = polyn_gf2m::eea_with_coefficients( syndrom_polyn, g, 1); 00054 polyn_gf2m & h = h__aux.first; 00055 polyn_gf2m & aux = h__aux.second; 00056 a = sp_field->gf_inv(aux.get_coef(0)); 00057 gf2m log_a = sp_field->gf_log(a); 00058 for(int i = 0; i <= h.get_degree(); ++i) 00059 { 00060 h.set_coef(i,sp_field->gf_mul_zrz(log_a,h.get_coef(i))); 00061 } 00062 00063 // compute h(z) += z 00064 h.add_to_coef( 1, 1); 00065 // compute S square root of h (using sqrtmod) 00066 polyn_gf2m S(t - 1, g.get_sp_field()); 00067 00068 for(u32bit i=0;i<t;i++) 00069 { 00070 a = sp_field->gf_sqrt(h.get_coef(i)); 00071 00072 if(i & 1) 00073 { 00074 for(u32bit j=0;j<t;j++) 00075 { 00076 S.add_to_coef( j, sp_field->gf_mul(a, sqrtmod[i/2].get_coef(j))); 00077 } 00078 } 00079 else 00080 { 00081 S.add_to_coef( i/2, a); 00082 } 00083 } /* end for loop (i) */ 00084 00085 00086 S.get_degree(); 00087 00088 std::pair<polyn_gf2m, polyn_gf2m> v__u = polyn_gf2m::eea_with_coefficients(S, g, t/2+1); 00089 polyn_gf2m & u = v__u.second; 00090 polyn_gf2m & v = v__u.first; 00091 00092 // sigma = u^2+z*v^2 00093 polyn_gf2m sigma ( t , g.get_sp_field()); 00094 00095 const size_t u_deg = u.get_degree(); 00096 for(size_t i = 0; i <= u_deg; ++i) 00097 { 00098 sigma.set_coef(2*i, sp_field->gf_square(u.get_coef(i))); 00099 } 00100 00101 const size_t v_deg = v.get_degree(); 00102 for(size_t i = 0; i <= v_deg; ++i) 00103 { 00104 sigma.set_coef(2*i+1, sp_field->gf_square(v.get_coef(i))); 00105 } 00106 00107 secure_vector<gf2m> res = find_roots_gf2m_decomp(sigma, code_length); 00108 size_t d = res.size(); 00109 00110 secure_vector<gf2m> result(d); 00111 for(u32bit i = 0; i < d; ++i) 00112 { 00113 gf2m current = res[i]; 00114 00115 gf2m tmp; 00116 tmp = gray_to_lex(current); 00117 if(tmp >= code_length) /* invalid root */ 00118 { 00119 result[i] = i; 00120 } 00121 result[i] = Linv[tmp]; 00122 } 00123 00124 return result; 00125 } 00126 } 00127 00128 00129 /** 00130 * @param p_err_pos_len must point to the available length of err_pos on input, the 00131 * function will set it to the actual number of errors returned in the err_pos 00132 * array */ 00133 secure_vector<byte> mceliece_decrypt( 00134 secure_vector<gf2m> & error_pos, 00135 const byte *ciphertext, u32bit ciphertext_len, 00136 const McEliece_PrivateKey & key) 00137 { 00138 00139 u32bit dimension = key.get_dimension(); 00140 u32bit codimension = key.get_codimension(); 00141 u32bit t = key.get_goppa_polyn().get_degree(); 00142 polyn_gf2m syndrome_polyn(key.get_goppa_polyn().get_sp_field()); // init as zero polyn 00143 const unsigned unused_pt_bits = dimension % 8; 00144 const byte unused_pt_bits_mask = (1 << unused_pt_bits) - 1; 00145 00146 if(ciphertext_len != (key.get_code_length()+7)/8) 00147 { 00148 throw Invalid_Argument("wrong size of McEliece ciphertext"); 00149 } 00150 u32bit cleartext_len = (key.get_message_word_bit_length()+7)/8; 00151 00152 if(cleartext_len != bit_size_to_byte_size(dimension)) 00153 { 00154 throw Invalid_Argument("mce-decryption: wrong length of cleartext buffer"); 00155 } 00156 00157 00158 secure_vector<u32bit> syndrome_vec(bit_size_to_32bit_size(codimension)); 00159 matrix_arr_mul( 00160 key.get_H_coeffs(), 00161 key.get_code_length(), 00162 bit_size_to_32bit_size(codimension), 00163 ciphertext, 00164 &syndrome_vec[0], syndrome_vec.size() ); 00165 secure_vector<byte> syndrome_byte_vec(bit_size_to_byte_size(codimension)); 00166 u32bit syndrome_byte_vec_size = syndrome_byte_vec.size(); 00167 for(u32bit i = 0; i < syndrome_byte_vec_size; i++) 00168 { 00169 syndrome_byte_vec[i] = syndrome_vec[i/4] >> (8* (i % 4)); 00170 } 00171 syndrome_polyn = polyn_gf2m( t-1, &syndrome_byte_vec[0],bit_size_to_byte_size(codimension), key.get_goppa_polyn().get_sp_field()); 00172 00173 00174 00175 syndrome_polyn.get_degree(); 00176 error_pos = goppa_decode(syndrome_polyn, key.get_goppa_polyn(), key.get_sqrtmod(), key.get_Linv()); 00177 00178 u32bit nb_err = error_pos.size(); 00179 00180 00181 secure_vector<byte> cleartext(cleartext_len); 00182 copy_mem(&cleartext[0], ciphertext, cleartext_len); 00183 00184 for(u32bit i = 0; i < nb_err; i++) 00185 { 00186 gf2m current = error_pos[i]; 00187 00188 if(current >= cleartext_len * 8) 00189 { 00190 // an invalid position, this shouldn't happen 00191 continue; 00192 } 00193 cleartext[current / 8] ^= (1 << (current % 8)); 00194 } 00195 if(unused_pt_bits) 00196 { 00197 cleartext[cleartext_len - 1] &= unused_pt_bits_mask; 00198 } 00199 00200 return cleartext; 00201 } 00202 00203 }