Botan  1.11.15
src/lib/pubkey/mce/mceliece_key.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/mceliece_key.h>
00013 #include <botan/internal/bit_ops.h>
00014 #include <botan/gf2m_small_m.h>
00015 #include <botan/mceliece.h>
00016 #include <botan/internal/code_based_key_gen.h>
00017 #include <botan/code_based_util.h>
00018 #include <botan/der_enc.h>
00019 #include <botan/ber_dec.h>
00020 #include <botan/workfactor.h>
00021 
00022 namespace Botan {
00023 
00024 McEliece_PrivateKey::McEliece_PrivateKey(polyn_gf2m const& goppa_polyn,
00025                                          std::vector<u32bit> const& parity_check_matrix_coeffs,
00026                                          std::vector<polyn_gf2m> const& square_root_matrix,
00027                                          std::vector<gf2m> const& inverse_support,
00028                                          std::vector<byte> const& public_matrix) :
00029    McEliece_PublicKey(public_matrix, goppa_polyn.get_degree(), inverse_support.size()),
00030    m_g(goppa_polyn),
00031    m_sqrtmod(square_root_matrix),
00032    m_Linv(inverse_support),
00033    m_coeffs(parity_check_matrix_coeffs),
00034    m_codimension(ceil_log2(inverse_support.size()) * goppa_polyn.get_degree()),
00035    m_dimension(inverse_support.size() - m_codimension)
00036    {
00037    };
00038 
00039 McEliece_PrivateKey::McEliece_PrivateKey(RandomNumberGenerator& rng, size_t code_length, size_t t)
00040    {
00041    u32bit ext_deg = ceil_log2(code_length);
00042    *this = generate_mceliece_key(rng, ext_deg, code_length, t);
00043    }
00044 
00045 unsigned McEliece_PublicKey::get_message_word_bit_length() const
00046    {
00047    u32bit codimension = ceil_log2(m_code_length) * m_t;
00048    return m_code_length - codimension;
00049    }
00050 
00051 AlgorithmIdentifier McEliece_PublicKey::algorithm_identifier() const
00052    {
00053    return AlgorithmIdentifier(get_oid(), std::vector<byte>());
00054    }
00055 
00056 std::vector<byte> McEliece_PublicKey::x509_subject_public_key() const
00057    {
00058    // encode the public key
00059    return unlock(DER_Encoder()
00060                  .start_cons(SEQUENCE)
00061                  .start_cons(SEQUENCE)
00062                  .encode(static_cast<size_t>(get_code_length()))
00063                  .encode(static_cast<size_t>(get_t()))
00064                  .end_cons()
00065                  .encode(m_public_matrix, OCTET_STRING)
00066                  .end_cons()
00067                  .get_contents());
00068    }
00069 
00070 McEliece_PublicKey::McEliece_PublicKey(const McEliece_PublicKey & other) :
00071    m_public_matrix(other.m_public_matrix),
00072    m_t(other.m_t),
00073    m_code_length(other.m_code_length)
00074    {
00075    }
00076 
00077 size_t McEliece_PublicKey::estimated_strength() const
00078    {
00079    const u32bit ext_deg = ceil_log2(m_code_length);
00080    const size_t k = m_code_length - ext_deg * m_t;
00081    return mceliece_work_factor(m_code_length, k, m_t);
00082    }
00083 
00084 McEliece_PublicKey::McEliece_PublicKey(const std::vector<byte>& key_bits)
00085    {
00086    BER_Decoder dec(key_bits);
00087    size_t n;
00088    size_t t;
00089    dec.start_cons(SEQUENCE)
00090       .start_cons(SEQUENCE)
00091       .decode(n)
00092       .decode(t)
00093       .end_cons()
00094       .decode(m_public_matrix, OCTET_STRING)
00095       .end_cons();
00096    m_t = t;
00097    m_code_length = n;
00098    }
00099 
00100 secure_vector<byte> McEliece_PrivateKey::pkcs8_private_key() const
00101    {
00102    DER_Encoder enc;
00103    enc.start_cons(SEQUENCE)
00104       .start_cons(SEQUENCE)
00105       .encode(static_cast<size_t>(get_code_length()))
00106       .encode(static_cast<size_t>(get_t()))
00107       .end_cons()
00108       .encode(m_public_matrix, OCTET_STRING)
00109       .encode(m_g.encode(), OCTET_STRING); // g as octet string
00110    enc.start_cons(SEQUENCE);
00111    for(u32bit i = 0; i < m_sqrtmod.size(); i++)
00112       {
00113       enc.encode(m_sqrtmod[i].encode(), OCTET_STRING);
00114       }
00115    enc.end_cons();
00116    secure_vector<byte> enc_support;
00117    for(u32bit i = 0; i < m_Linv.size(); i++)
00118       {
00119       enc_support.push_back(m_Linv[i] >> 8);
00120       enc_support.push_back(m_Linv[i]);
00121       }
00122    enc.encode(enc_support, OCTET_STRING);
00123    secure_vector<byte> enc_H;
00124    for(u32bit i = 0; i < m_coeffs.size(); i++)
00125       {
00126       enc_H.push_back(m_coeffs[i] >> 24);
00127       enc_H.push_back(m_coeffs[i] >> 16);
00128       enc_H.push_back(m_coeffs[i] >> 8);
00129       enc_H.push_back(m_coeffs[i]);
00130       }
00131    enc.encode(enc_H, OCTET_STRING);
00132    enc.end_cons();
00133    return enc.get_contents();
00134    }
00135 
00136 bool McEliece_PrivateKey::check_key(RandomNumberGenerator& rng, bool) const
00137    {
00138    McEliece_Private_Operation priv_op(*this);
00139    McEliece_Public_Operation pub_op(*this, get_code_length());
00140 
00141    secure_vector<byte> plaintext((this->get_message_word_bit_length()+7)/8);
00142    rng.randomize(&plaintext[0], plaintext.size() - 1);
00143    const secure_vector<gf2m> err_pos = create_random_error_positions(this->get_code_length(), this->get_t(), rng);
00144 
00145    mceliece_message_parts parts(err_pos, plaintext, this->get_code_length());
00146    secure_vector<byte> message_and_error_input = parts.get_concat();
00147    secure_vector<byte> ciphertext = pub_op.encrypt(&message_and_error_input[0], message_and_error_input.size(), rng);
00148    secure_vector<byte> message_and_error_output = priv_op.decrypt(&ciphertext[0], ciphertext.size());
00149 
00150    return (message_and_error_input == message_and_error_output);
00151    }
00152 
00153 McEliece_PrivateKey::McEliece_PrivateKey(const secure_vector<byte>& key_bits)
00154    {
00155    size_t n, t;
00156    secure_vector<byte> g_enc;
00157    BER_Decoder dec_base(key_bits);
00158    BER_Decoder dec = dec_base.start_cons(SEQUENCE)
00159       .start_cons(SEQUENCE)
00160       .decode(n)
00161       .decode(t)
00162       .end_cons()
00163       .decode(m_public_matrix, OCTET_STRING)
00164       .decode(g_enc, OCTET_STRING);
00165 
00166    if(t == 0 || n == 0)
00167       throw Decoding_Error("invalid McEliece parameters");
00168 
00169    u32bit ext_deg = ceil_log2(n);
00170    m_code_length = n;
00171    m_t = t;
00172    m_codimension = (ext_deg * t);
00173    m_dimension = (n - m_codimension);
00174 
00175    std::shared_ptr<gf2m_small_m::Gf2m_Field> sp_field(new gf2m_small_m::Gf2m_Field(ext_deg));
00176    m_g = polyn_gf2m(g_enc, sp_field);
00177    if(m_g.get_degree() != static_cast<int>(t))
00178       {
00179       throw Decoding_Error("degree of decoded Goppa polynomial is incorrect");
00180       }
00181    BER_Decoder dec2 = dec.start_cons(SEQUENCE);
00182    for(u32bit i = 0; i < t/2; i++)
00183       {
00184       secure_vector<byte> sqrt_enc;
00185       dec2.decode(sqrt_enc, OCTET_STRING);
00186       while(sqrt_enc.size() < (t*2))
00187          {
00188          // ensure that the length is always t
00189          sqrt_enc.push_back(0);
00190          sqrt_enc.push_back(0);
00191          }
00192       if(sqrt_enc.size() != t*2)
00193          {
00194          throw Decoding_Error("length of square root polynomial entry is too large");
00195          }
00196       m_sqrtmod.push_back(polyn_gf2m(sqrt_enc, sp_field));
00197       }
00198    secure_vector<byte> enc_support;
00199    BER_Decoder dec3 = dec2.end_cons()
00200       .decode(enc_support, OCTET_STRING);
00201    if(enc_support.size() % 2)
00202       {
00203       throw Decoding_Error("encoded support has odd length");
00204       }
00205    if(enc_support.size() / 2 != n)
00206       {
00207       throw Decoding_Error("encoded support has length different from code length");
00208       }
00209    for(u32bit i = 0; i < n*2; i+=2)
00210       {
00211       gf2m el = (enc_support[i] << 8) |  enc_support[i+1];
00212       m_Linv.push_back(el);
00213       }
00214    secure_vector<byte> enc_H;
00215    dec3.decode(enc_H, OCTET_STRING)
00216       .end_cons();
00217    if(enc_H.size() % 4)
00218       {
00219       throw Decoding_Error("encoded parity check matrix has length which is not a multiple of four");
00220       }
00221    if(enc_H.size()/4 != bit_size_to_32bit_size(m_codimension) * m_code_length )
00222       {
00223       throw Decoding_Error("encoded parity check matrix has wrong length");
00224       }
00225 
00226    for(u32bit i = 0; i < enc_H.size(); i+=4)
00227       {
00228       u32bit coeff = (enc_H[i] << 24) | (enc_H[i+1] << 16) | (enc_H[i+2] << 8) | enc_H[i+3];
00229       m_coeffs.push_back(coeff);
00230       }
00231 
00232    }
00233 
00234 
00235 bool McEliece_PrivateKey::operator==(const McEliece_PrivateKey & other) const
00236    {
00237    if(*static_cast<const McEliece_PublicKey*>(this) != *static_cast<const McEliece_PublicKey*>(&other))
00238       {
00239       return false;
00240       }
00241    if(m_g != other.m_g)
00242       {
00243       return false;
00244       }
00245 
00246    if( m_sqrtmod != other.m_sqrtmod)
00247       {
00248       return false;
00249       }
00250    if( m_Linv != other.m_Linv)
00251       {
00252       return false;
00253       }
00254    if( m_coeffs != other.m_coeffs)
00255       {
00256       return false;
00257       }
00258 
00259    if(m_codimension != other.m_codimension || m_dimension != other.m_dimension)
00260       {
00261       return false;
00262       }
00263 
00264    return true;
00265    }
00266 
00267 bool McEliece_PublicKey::operator==(const McEliece_PublicKey& other) const
00268    {
00269    if(m_public_matrix != other.m_public_matrix)
00270       {
00271       return false;
00272       }
00273    if(m_t != other.m_t )
00274       {
00275       return false;
00276       }
00277    if( m_code_length != other.m_code_length)
00278       {
00279       return false;
00280       }
00281    return true;
00282    }
00283 
00284 }
00285 
00286