Botan  1.11.15
src/lib/pubkey/mce/goppa_code.cpp
Go to the documentation of this file.
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 }