diff options
Diffstat (limited to 'comm/third_party/botan/src/lib/pubkey/mce/goppa_code.cpp')
| -rw-r--r-- | comm/third_party/botan/src/lib/pubkey/mce/goppa_code.cpp | 234 |
1 files changed, 234 insertions, 0 deletions
diff --git a/comm/third_party/botan/src/lib/pubkey/mce/goppa_code.cpp b/comm/third_party/botan/src/lib/pubkey/mce/goppa_code.cpp new file mode 100644 index 0000000000..f26716fabd --- /dev/null +++ b/comm/third_party/botan/src/lib/pubkey/mce/goppa_code.cpp @@ -0,0 +1,234 @@ +/* + * (C) Copyright Projet SECRET, INRIA, Rocquencourt + * (C) Bhaskar Biswas and Nicolas Sendrier + * + * (C) 2014 cryptosource GmbH + * (C) 2014 Falko Strenzke fstrenzke@cryptosource.de + * + * Botan is released under the Simplified BSD License (see license.txt) + * + */ + +#include <botan/internal/mce_internal.h> +#include <botan/internal/code_based_util.h> + +namespace Botan { + +namespace { + +void matrix_arr_mul(std::vector<uint32_t> matrix, + size_t numo_rows, + size_t words_per_row, + const uint8_t input_vec[], + uint32_t output_vec[], + size_t output_vec_len) + { + for(size_t j = 0; j < numo_rows; j++) + { + if((input_vec[j / 8] >> (j % 8)) & 1) + { + for(size_t i = 0; i < output_vec_len; i++) + { + output_vec[i] ^= matrix[j * (words_per_row) + i]; + } + } + } + } + +/** +* returns the error vector to the syndrome +*/ +secure_vector<gf2m> goppa_decode(const polyn_gf2m & syndrom_polyn, + const polyn_gf2m & g, + const std::vector<polyn_gf2m> & sqrtmod, + const std::vector<gf2m> & Linv) + { + const size_t code_length = Linv.size(); + gf2m a; + uint32_t t = g.get_degree(); + + 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; + polyn_gf2m & aux = h_aux.second; + a = sp_field->gf_inv(aux.get_coef(0)); + gf2m log_a = sp_field->gf_log(a); + for(int i = 0; i <= h.get_degree(); ++i) + { + h.set_coef(i,sp_field->gf_mul_zrz(log_a,h.get_coef(i))); + } + + // compute h(z) += z + h.add_to_coef( 1, 1); + // compute S square root of h (using sqrtmod) + polyn_gf2m S(t - 1, g.get_sp_field()); + + for(uint32_t i=0;i<t;i++) + { + a = sp_field->gf_sqrt(h.get_coef(i)); + + if(i & 1) + { + for(uint32_t j=0;j<t;j++) + { + S.add_to_coef( j, sp_field->gf_mul(a, sqrtmod[i/2].get_coef(j))); + } + } + else + { + S.add_to_coef( i/2, a); + } + } /* end for loop (i) */ + + + S.get_degree(); + + std::pair<polyn_gf2m, polyn_gf2m> v_u = polyn_gf2m::eea_with_coefficients(S, g, t/2+1); + polyn_gf2m & u = v_u.second; + polyn_gf2m & v = v_u.first; + + // sigma = u^2+z*v^2 + polyn_gf2m sigma ( t , g.get_sp_field()); + + const int u_deg = u.get_degree(); + BOTAN_ASSERT(u_deg >= 0, "Valid degree"); + for(int i = 0; i <= u_deg; ++i) + { + sigma.set_coef(2*i, sp_field->gf_square(u.get_coef(i))); + } + + const int v_deg = v.get_degree(); + BOTAN_ASSERT(v_deg >= 0, "Valid degree"); + for(int i = 0; i <= v_deg; ++i) + { + sigma.set_coef(2*i+1, sp_field->gf_square(v.get_coef(i))); + } + + secure_vector<gf2m> res = find_roots_gf2m_decomp(sigma, code_length); + size_t d = res.size(); + + secure_vector<gf2m> result(d); + for(uint32_t i = 0; i < d; ++i) + { + gf2m current = res[i]; + + gf2m tmp; + tmp = gray_to_lex(current); + /// XXX double assignment, possible bug? + if(tmp >= code_length) /* invalid root */ + { + result[i] = static_cast<gf2m>(i); + } + result[i] = Linv[tmp]; + } + + return result; + } +} + +void mceliece_decrypt(secure_vector<uint8_t>& plaintext_out, + secure_vector<uint8_t>& error_mask_out, + const secure_vector<uint8_t>& ciphertext, + const McEliece_PrivateKey& key) + { + mceliece_decrypt(plaintext_out, error_mask_out, ciphertext.data(), ciphertext.size(), key); + } + +void mceliece_decrypt( + secure_vector<uint8_t>& plaintext, + secure_vector<uint8_t> & error_mask, + const uint8_t 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<uint8_t> result((code_length+7)/8); + for(auto&& pos : error_pos) + { + if(pos > code_length) + { + throw Invalid_Argument("error position larger than code size"); + } + result[pos / 8] |= (1 << (pos % 8)); + } + + error_mask = result; + } + +/** +* @p p_err_pos_len must point to the available length of @p error_pos on input, the +* function will set it to the actual number of errors returned in the @p error_pos +* array */ +secure_vector<uint8_t> mceliece_decrypt( + secure_vector<gf2m> & error_pos, + const uint8_t *ciphertext, size_t ciphertext_len, + const McEliece_PrivateKey & key) + { + + const size_t dimension = key.get_dimension(); + const size_t codimension = key.get_codimension(); + const uint32_t t = key.get_goppa_polyn().get_degree(); + polyn_gf2m syndrome_polyn(key.get_goppa_polyn().get_sp_field()); // init as zero polyn + const unsigned unused_pt_bits = dimension % 8; + const uint8_t unused_pt_bits_mask = (1 << unused_pt_bits) - 1; + + if(ciphertext_len != (key.get_code_length()+7)/8) + { + throw Invalid_Argument("wrong size of McEliece ciphertext"); + } + const size_t cleartext_len = (key.get_message_word_bit_length()+7)/8; + + if(cleartext_len != bit_size_to_byte_size(dimension)) + { + throw Invalid_Argument("mce-decryption: wrong length of cleartext buffer"); + } + + secure_vector<uint32_t> 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()); + + secure_vector<uint8_t> syndrome_byte_vec(bit_size_to_byte_size(codimension)); + const size_t syndrome_byte_vec_size = syndrome_byte_vec.size(); + for(size_t i = 0; i < syndrome_byte_vec_size; i++) + { + syndrome_byte_vec[i] = static_cast<uint8_t>(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.get_degree(); + error_pos = goppa_decode(syndrome_polyn, key.get_goppa_polyn(), key.get_sqrtmod(), key.get_Linv()); + + const size_t nb_err = error_pos.size(); + + secure_vector<uint8_t> cleartext(cleartext_len); + copy_mem(cleartext.data(), ciphertext, cleartext_len); + + for(size_t i = 0; i < nb_err; i++) + { + gf2m current = error_pos[i]; + + if(current >= cleartext_len * 8) + { + // an invalid position, this shouldn't happen + continue; + } + cleartext[current / 8] ^= (1 << (current % 8)); + } + + if(unused_pt_bits) + { + cleartext[cleartext_len - 1] &= unused_pt_bits_mask; + } + + return cleartext; + } + +} |