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/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