diff options
Diffstat (limited to 'src')
34 files changed, 1335 insertions, 1293 deletions
diff --git a/src/cmd/implementation/speed_public_key.cpp b/src/cmd/implementation/speed_public_key.cpp index 73bbd7c1e..83c0156ae 100644 --- a/src/cmd/implementation/speed_public_key.cpp +++ b/src/cmd/implementation/speed_public_key.cpp @@ -734,20 +734,21 @@ void benchmark_mce(RandomNumberGenerator& rng, Benchmark_Report& report) { const std::vector<std::pair<size_t, size_t>> params = { - { 1024, 35 }, - { 2048, 50 }, - { 2960, 56 }, + { 1632, 33 }, + { 2480, 45 }, + { 2960, 57 }, + { 3408, 67 }, + { 4264, 95 }, { 6624, 115 } }; const std::string algo_name = "McEliece"; - const std::string padding = "Raw"; for(auto& param : params) { Timer keygen_timer("keygen"); - Timer enc_timer(padding + " encrypt"); - Timer dec_timer(padding + " decrypt"); + Timer enc_timer("encrypt"); + Timer dec_timer("decrypt"); keygen_timer.start(); McEliece_PrivateKey priv_key(rng, param.first, param.second); @@ -776,9 +777,9 @@ void benchmark_mce(RandomNumberGenerator& rng, std::to_string(param.second); std::ostringstream keysize_report; - keysize_report << "(size " << pub_key.x509_subject_public_key().size() << " pub " - << priv_key.pkcs8_private_key().size() << " priv " - << pub_key.estimated_strength() << " work factor)"; + keysize_report << "(work factor " << pub_key.estimated_strength() << ", " + << "pub bytes " << pub_key.x509_subject_public_key().size() << " " + << "priv bytes " << priv_key.pkcs8_private_key().size() << ")"; report.report(nm + " " + keysize_report.str(), keygen_timer); report.report(nm, enc_timer); diff --git a/src/cmd/mce.cpp b/src/cmd/mce.cpp new file mode 100644 index 000000000..3b33df661 --- /dev/null +++ b/src/cmd/mce.cpp @@ -0,0 +1,117 @@ +#include "apps.h" + +#if defined(BOTAN_HAS_MCELIECE) + +#include <botan/mceliece.h> +#include <botan/mceies.h> +#include <botan/pkcs8.h> +#include <fstream> + +namespace { + +int mce(int argc, char* argv[]) + { + if(argc < 4) + { + std::cout << "Usage: " << argv[0] << " [keygen n t pass|keybits n t|encrypt file key|decrypt file key pass]\n"; + return 1; + } + + const std::string cmd = argv[1]; + + AutoSeeded_RNG rng; + + if(cmd == "keygen") + { + const size_t n = std::stol(argv[2]); + const size_t t = std::stol(argv[3]); + const std::string pass = argv[4]; + + McEliece_PrivateKey pk(rng, n, t); + + bool ok = pk.check_key(rng, true); + + if(!ok) + { + std::cout << "Keygen failed self-test\n"; + return 2; + } + + /* + secure_vector<byte> priv = PKCS8::BER_encode(pk); + std::vector<byte> pub = X509::BER_encode(pk); + std::cout << priv.size()/1024.0 << " " << pub.size()/1024.0 << "\n"; + */ + + std::ofstream pub_file("mce.pub"); + pub_file << X509::PEM_encode(pk); + pub_file.close(); + + std::ofstream priv_file("mce.priv"); + priv_file << PKCS8::PEM_encode(pk, rng, pass); + priv_file.close(); + } + else if(cmd == "keybits") + { + const size_t n = std::stol(argv[2]); + const size_t t = std::stol(argv[3]); + std::cout << "McEliece key with params (" << n << "," << t << ") has " + << mceliece_work_factor(n, t) << " bit security\n"; + } + else if(cmd == "encrypt") + { + std::unique_ptr<Public_Key> p8(X509::load_key(argv[3])); + const McEliece_PublicKey* key = dynamic_cast<McEliece_PublicKey*>(p8.get()); + + if(!key) + { + throw std::runtime_error("Loading McEliece public key failed"); + } + + const std::string input_path = argv[2]; + std::ifstream in(input_path, std::ios::binary); + std::string pt((std::istreambuf_iterator<char>(in)), std::istreambuf_iterator<char>()); + + secure_vector<byte> ct = mceies_encrypt(*key, + reinterpret_cast<const byte*>(pt.data()), + pt.size(), + nullptr, 0, rng, "AES-128/GCM"); + + std::cout << pt.size() << " -> " << ct.size() << "\n"; + + std::ofstream out(std::string(input_path) + ".ct", std::ios::binary); + out.write(reinterpret_cast<const char*>(ct.data()), ct.size()); + out.close(); + } + else if(cmd == "decrypt") + { + const std::string key_file = argv[3]; + const std::string pass = argv[4]; + std::unique_ptr<Private_Key> p8(PKCS8::load_key(key_file, rng, pass)); + const McEliece_PrivateKey* key = dynamic_cast<McEliece_PrivateKey*>(p8.get()); + + if(!key) + { + throw std::runtime_error("Loading McEliece private key failed"); + } + + std::ifstream in(argv[2], std::ios::binary); + std::string ct((std::istreambuf_iterator<char>(in)), std::istreambuf_iterator<char>()); + + secure_vector<byte> pt = mceies_decrypt(*key, + reinterpret_cast<const byte*>(ct.data()), + ct.size(), + nullptr, 0, "AES-128/GCM"); + + std::ofstream out("mce.plaintext", std::ios::binary); + out.write(reinterpret_cast<const char*>(pt.data()), pt.size()); + out.close(); + } + return 0; + } + +} + +REGISTER_APP(mce); + +#endif diff --git a/src/lib/pubkey/mce/binary_matrix.cpp b/src/lib/pubkey/mce/binary_matrix.cpp deleted file mode 100644 index 45c9aab13..000000000 --- a/src/lib/pubkey/mce/binary_matrix.cpp +++ /dev/null @@ -1,95 +0,0 @@ -/** - * (C) Copyright Projet SECRET, INRIA, Rocquencourt - * (C) Bhaskar Biswas and Nicolas Sendrier - * - * (C) 2014 cryptosource GmbH - * (C) 2014 Falko Strenzke [email protected] - * - * Botan is released under the Simplified BSD License (see license.txt) - * - */ - -#include <botan/internal/binary_matrix.h> - -namespace Botan { - -binary_matrix::binary_matrix (u32bit rown, u32bit coln) - { - m_coln = coln; - m_rown = rown; - m_rwdcnt = (1 + (m_coln - 1) / BITS_PER_U32); - m_elem = std::vector<u32bit>(m_rown * m_rwdcnt); - } - -void binary_matrix::row_xor(u32bit a, u32bit b) - { - u32bit i; - for(i=0;i<m_rwdcnt;i++) - { - m_elem[a*m_rwdcnt+i]^=m_elem[b*m_rwdcnt+i]; - } - } - -//the matrix is reduced from LSB...(from right) -secure_vector<int> binary_matrix::row_reduced_echelon_form() - { - u32bit i, failcnt, findrow, max=m_coln - 1; - - secure_vector<int> perm(m_coln); - for(i=0;i<m_coln;i++) - { - perm[i]=i;//initialize permutation. - } - failcnt = 0; - - for(i=0;i<m_rown;i++,max--) - { - findrow=0; - for(u32bit j=i;j<m_rown;j++) - { - if(coef(j,max)) - { - if (i!=j)//not needed as ith row is 0 and jth row is 1. - row_xor(i,j);//xor to the row.(swap)? - findrow=1; - break; - }//largest value found (end if) - } - - if(!findrow)//if no row with a 1 found then swap last column and the column with no 1 down. - { - perm[m_coln - m_rown - 1 - failcnt] = max; - failcnt++; - if (!max) - { - //CSEC_FREE_MEM_CHK_SET_NULL(*p_perm); - //CSEC_THR_RETURN(); - perm.resize(0); - } - i--; - } - else - { - perm[i+m_coln - m_rown] = max; - for(u32bit j=i+1;j<m_rown;j++)//fill the column downwards with 0's - { - if(coef(j,(max))) - { - row_xor(j,i);//check the arg. order. - } - } - - for(int j=i-1;j>=0;j--)//fill the column with 0's upwards too. - { - if(coef(j,(max))) - { - row_xor(j,i); - } - } - } - }//end for(i) - return perm; - } - - -} // end namespace Botan diff --git a/src/lib/pubkey/mce/binary_matrix.h b/src/lib/pubkey/mce/binary_matrix.h deleted file mode 100644 index feb44632f..000000000 --- a/src/lib/pubkey/mce/binary_matrix.h +++ /dev/null @@ -1,60 +0,0 @@ -/** - * (C) Copyright Projet SECRET, INRIA, Rocquencourt - * (C) Bhaskar Biswas and Nicolas Sendrier - * - * (C) 2014 cryptosource GmbH - * (C) 2014 Falko Strenzke [email protected] - * - * Botan is released under the Simplified BSD License (see license.txt) - * - */ - -#ifndef BOTAN_BINARY_MATRIX_H__ -#define BOTAN_BINARY_MATRIX_H__ - -#include <botan/secmem.h> - -namespace Botan { - -#define BITS_PER_U32 (8 * sizeof (u32bit)) - -struct binary_matrix - { - public: - binary_matrix(u32bit m_rown, u32bit m_coln); - - void row_xor(u32bit a, u32bit b); - secure_vector<int> row_reduced_echelon_form(); - - /** - * return the coefficient out of F_2 - */ - u32bit coef(u32bit i, u32bit j) - { - return (m_elem[(i) * m_rwdcnt + (j) / BITS_PER_U32] >> (j % BITS_PER_U32)) & 1; - }; - - void set_coef_to_one(u32bit i, u32bit j) - { - m_elem[(i) * m_rwdcnt + (j) / BITS_PER_U32] |= (1UL << ((j) % BITS_PER_U32)) ; - }; - - void toggle_coeff(u32bit i, u32bit j) - { - m_elem[(i) * m_rwdcnt + (j) / BITS_PER_U32] ^= (1UL << ((j) % BITS_PER_U32)) ; - } - - void set_to_zero() - { - zeroise(m_elem); - } - - u32bit m_rown; // number of rows. - u32bit m_coln; // number of columns. - u32bit m_rwdcnt; // number of words in a row - std::vector<u32bit> m_elem; - }; - -} - -#endif diff --git a/src/lib/pubkey/mce/code_based_key_gen.cpp b/src/lib/pubkey/mce/code_based_key_gen.cpp index a3749abef..44b1cb4d6 100644 --- a/src/lib/pubkey/mce/code_based_key_gen.cpp +++ b/src/lib/pubkey/mce/code_based_key_gen.cpp @@ -9,26 +9,139 @@ * */ -#include <botan/internal/code_based_key_gen.h> -#include <botan/code_based_util.h> -#include <botan/gf2m_rootfind_dcmp.h> -#include <botan/internal/binary_matrix.h> +#include <botan/mceliece.h> +#include <botan/internal/code_based_util.h> #include <botan/loadstor.h> -#include <botan/polyn_gf2m.h> namespace Botan { namespace { +struct binary_matrix + { + public: + binary_matrix(u32bit m_rown, u32bit m_coln); + + void row_xor(u32bit a, u32bit b); + secure_vector<int> row_reduced_echelon_form(); + + /** + * return the coefficient out of F_2 + */ + u32bit coef(u32bit i, u32bit j) + { + return (m_elem[(i) * m_rwdcnt + (j) / 32] >> (j % 32)) & 1; + }; + + void set_coef_to_one(u32bit i, u32bit j) + { + m_elem[(i) * m_rwdcnt + (j) / 32] |= (static_cast<u32bit>(1) << ((j) % 32)) ; + }; + + void toggle_coeff(u32bit i, u32bit j) + { + m_elem[(i) * m_rwdcnt + (j) / 32] ^= (static_cast<u32bit>(1) << ((j) % 32)) ; + } + + void set_to_zero() + { + zeroise(m_elem); + } + + //private: + u32bit m_rown; // number of rows. + u32bit m_coln; // number of columns. + u32bit m_rwdcnt; // number of words in a row + std::vector<u32bit> m_elem; + }; + +binary_matrix::binary_matrix (u32bit rown, u32bit coln) + { + m_coln = coln; + m_rown = rown; + m_rwdcnt = 1 + ((m_coln - 1) / 32); + m_elem = std::vector<u32bit>(m_rown * m_rwdcnt); + } + +void binary_matrix::row_xor(u32bit a, u32bit b) + { + u32bit i; + for(i=0;i<m_rwdcnt;i++) + { + m_elem[a*m_rwdcnt+i]^=m_elem[b*m_rwdcnt+i]; + } + } + +//the matrix is reduced from LSB...(from right) +secure_vector<int> binary_matrix::row_reduced_echelon_form() + { + u32bit i, failcnt, findrow, max=m_coln - 1; + + secure_vector<int> perm(m_coln); + for(i=0;i<m_coln;i++) + { + perm[i]=i;//initialize permutation. + } + failcnt = 0; + + for(i=0;i<m_rown;i++,max--) + { + findrow=0; + for(u32bit j=i;j<m_rown;j++) + { + if(coef(j,max)) + { + if (i!=j)//not needed as ith row is 0 and jth row is 1. + row_xor(i,j);//xor to the row.(swap)? + findrow=1; + break; + }//largest value found (end if) + } + + if(!findrow)//if no row with a 1 found then swap last column and the column with no 1 down. + { + perm[m_coln - m_rown - 1 - failcnt] = max; + failcnt++; + if (!max) + { + //CSEC_FREE_MEM_CHK_SET_NULL(*p_perm); + //CSEC_THR_RETURN(); + perm.resize(0); + } + i--; + } + else + { + perm[i+m_coln - m_rown] = max; + for(u32bit j=i+1;j<m_rown;j++)//fill the column downwards with 0's + { + if(coef(j,(max))) + { + row_xor(j,i);//check the arg. order. + } + } + + for(int j=i-1;j>=0;j--)//fill the column with 0's upwards too. + { + if(coef(j,(max))) + { + row_xor(j,i); + } + } + } + }//end for(i) + return perm; + } + void randomize_support(u32bit n, std::vector<gf2m> & L, RandomNumberGenerator & rng) { unsigned int i, j; - gf2m_small_m::gf2m tmp; + gf2m tmp; for (i = 0; i < n; ++i) { - gf2m_small_m::gf2m rnd; + gf2m rnd; rng.randomize(reinterpret_cast<byte*>(&rnd), sizeof(rnd)); j = rnd % n; // no rejection sampling, but for useful code-based parameters with n <= 13 this seem tolerable @@ -38,14 +151,14 @@ void randomize_support(u32bit n, std::vector<gf2m> & L, RandomNumberGenerator & } } -std::unique_ptr<binary_matrix> generate_R(std::vector<gf2m> &L, polyn_gf2m* g, std::shared_ptr<gf2m_small_m::Gf2m_Field> sp_field, u32bit code_length, u32bit t ) +std::unique_ptr<binary_matrix> generate_R(std::vector<gf2m> &L, polyn_gf2m* g, std::shared_ptr<GF2m_Field> sp_field, u32bit code_length, u32bit t ) { //L- Support //t- Number of errors //n- Length of the Goppa code //m- The extension degree of the GF //g- The generator polynomial. - gf2m_small_m::gf2m x,y; + gf2m x,y; u32bit i,j,k,r,n; std::vector<int> Laux(code_length); n=code_length; @@ -112,7 +225,7 @@ McEliece_PrivateKey generate_mceliece_key( RandomNumberGenerator & rng, u32bit e { throw Invalid_Argument("invalid McEliece parameters"); } - std::shared_ptr<gf2m_small_m::Gf2m_Field> sp_field ( new Gf2m_Field(ext_deg )); + std::shared_ptr<GF2m_Field> sp_field ( new GF2m_Field(ext_deg )); //pick the support......... std::vector<gf2m> L(code_length); diff --git a/src/lib/pubkey/mce/code_based_key_gen.h b/src/lib/pubkey/mce/code_based_key_gen.h deleted file mode 100644 index 6764e13d6..000000000 --- a/src/lib/pubkey/mce/code_based_key_gen.h +++ /dev/null @@ -1,26 +0,0 @@ -/** - * (C) Copyright Projet SECRET, INRIA, Rocquencourt - * (C) Bhaskar Biswas and Nicolas Sendrier - * - * (C) 2014 cryptosource GmbH - * (C) 2014 Falko Strenzke [email protected] - * - * Botan is released under the Simplified BSD License (see license.txt) - * - */ - -#ifndef BOTAN_CODE_BASED_KEY_GEN_H__ -#define BOTAN_CODE_BASED_KEY_GEN_H__ - -#include <botan/mceliece_key.h> - -namespace Botan { - -McEliece_PrivateKey generate_mceliece_key(RandomNumberGenerator &rng, - u32bit ext_deg, - u32bit code_length, - u32bit t); - -} - -#endif diff --git a/src/lib/pubkey/mce/code_based_util.h b/src/lib/pubkey/mce/code_based_util.h index 6b567dbff..a959ad0d3 100644 --- a/src/lib/pubkey/mce/code_based_util.h +++ b/src/lib/pubkey/mce/code_based_util.h @@ -13,6 +13,7 @@ #define BOTAN_CODE_BASED_UTIL_H__ #include <botan/gf2m_small_m.h> +#include <stdexcept> namespace Botan { @@ -28,18 +29,18 @@ u16bit expand_mask_16bit(T tst) return ~(result - 1); } -inline gf2m_small_m::gf2m gray_to_lex(gf2m_small_m::gf2m gray) +inline gf2m gray_to_lex(gf2m gray) { - gf2m_small_m::gf2m result = gray ^ (gray>>8); + gf2m result = gray ^ (gray >> 8); result ^= (result >> 4); result ^= (result >> 2); result ^= (result >> 1); return result; } -inline gf2m_small_m::gf2m lex_to_gray(gf2m_small_m::gf2m lex) +inline gf2m lex_to_gray(gf2m lex) { - return (lex>>1) ^ lex; + return (lex >> 1) ^ lex; } inline u32bit bit_size_to_byte_size(u32bit bit_size) diff --git a/src/lib/pubkey/mce/gf2m_rootfind_dcmp.cpp b/src/lib/pubkey/mce/gf2m_rootfind_dcmp.cpp index 2d4f06130..d23d05172 100644 --- a/src/lib/pubkey/mce/gf2m_rootfind_dcmp.cpp +++ b/src/lib/pubkey/mce/gf2m_rootfind_dcmp.cpp @@ -6,314 +6,307 @@ * */ -#include <botan/gf2m_rootfind_dcmp.h> -#include <botan/gf2m_small_m.h> +#include <botan/polyn_gf2m.h> #include <botan/internal/bit_ops.h> -#include <botan/code_based_util.h> +#include <botan/internal/code_based_util.h> -namespace Botan -{ +namespace Botan { namespace { - u32bit patch_root_array( - gf2m* res_root_arr, - u32bit res_root_arr_len, - u32bit root_pos) - { - volatile u32bit i; - volatile gf2m patch_elem = 0x01; - volatile gf2m cond_mask = (root_pos == res_root_arr_len); - cond_mask = expand_mask_16bit(cond_mask); - cond_mask = ~cond_mask; /* now cond = 1 if not enough roots */ - patch_elem &= cond_mask; - for(i = 0; i < res_root_arr_len; i++) - { +u32bit patch_root_array(gf2m* res_root_arr, + u32bit res_root_arr_len, + u32bit root_pos) + { + volatile u32bit i; + volatile gf2m patch_elem = 0x01; + volatile gf2m cond_mask = (root_pos == res_root_arr_len); + cond_mask = expand_mask_16bit(cond_mask); + cond_mask = ~cond_mask; /* now cond = 1 if not enough roots */ + patch_elem &= cond_mask; + for(i = 0; i < res_root_arr_len; i++) + { gf2m masked_patch_elem = (patch_elem++) & cond_mask; res_root_arr[i] ^= masked_patch_elem++; - } - return res_root_arr_len; - } - -struct gf2m_decomp_rootfind_state -{ - gf2m_decomp_rootfind_state(const polyn_gf2m & p_polyn, u32bit code_length); - - void calc_LiK(const polyn_gf2m & sigma); - gf2m calc_Fxj_j_neq_0( const polyn_gf2m & sigma, gf2m j_gray); - void calc_next_Aij(); - void calc_Ai_zero(const polyn_gf2m & sigma); - secure_vector<gf2m> find_roots(const polyn_gf2m & sigma); - u32bit get_code_length() const { return code_length; }; - u32bit code_length; - secure_vector<gf2m> m_Lik; // size is outer_summands * m - secure_vector<gf2m> m_Aij; // ... - u32bit m_outer_summands; - gf2m m_j; - gf2m m_j_gray; - gf2m m_sigma_3_l; - gf2m m_sigma_3_neq_0_mask; -} ; - + } + return res_root_arr_len; + } + +class gf2m_decomp_rootfind_state + { + public: + gf2m_decomp_rootfind_state(const polyn_gf2m & p_polyn, u32bit code_length); + + void calc_LiK(const polyn_gf2m & sigma); + gf2m calc_Fxj_j_neq_0( const polyn_gf2m & sigma, gf2m j_gray); + void calc_next_Aij(); + void calc_Ai_zero(const polyn_gf2m & sigma); + secure_vector<gf2m> find_roots(const polyn_gf2m & sigma); + u32bit get_code_length() const { return code_length; }; + u32bit code_length; + secure_vector<gf2m> m_Lik; // size is outer_summands * m + secure_vector<gf2m> m_Aij; // ... + u32bit m_outer_summands; + gf2m m_j; + gf2m m_j_gray; + gf2m m_sigma_3_l; + gf2m m_sigma_3_neq_0_mask; + }; /* - * !! Attention: assumes gf2m is 16bit !! - */ +* !! Attention: assumes gf2m is 16bit !! +*/ #if 0 gf2m brootf_decomp__gray_to_lex(gf2m gray) -{ - static_assert(sizeof(gf2m) == 2, "Expected size"); - gf2m result = gray ^ (gray>>8); - result ^= (result >> 4); - result ^= (result >> 2); - result ^= (result >> 1); - return result; -} + { + static_assert(sizeof(gf2m) == 2, "Expected size"); + gf2m result = gray ^ (gray>>8); + result ^= (result >> 4); + result ^= (result >> 2); + result ^= (result >> 1); + return result; + } #endif /** - * calculates ceil((t-4)/5) = outer_summands - 1 - */ +* calculates ceil((t-4)/5) = outer_summands - 1 +*/ u32bit brootf_decomp__calc_sum_limit(u32bit t) -{ - u32bit result; - if(t < 4) - { - return 0; - } - result = t - 4; - result += 4; - result /= 5; - return result; -} + { + u32bit result; + if(t < 4) + { + return 0; + } + result = t - 4; + result += 4; + result /= 5; + return result; + } + } secure_vector<gf2m> find_roots_gf2m_decomp(const polyn_gf2m & polyn, u32bit code_length) -{ - gf2m_decomp_rootfind_state state(polyn, code_length); - return state.find_roots(polyn); - -} + { + gf2m_decomp_rootfind_state state(polyn, code_length); + return state.find_roots(polyn); + } + +gf2m_decomp_rootfind_state::gf2m_decomp_rootfind_state(const polyn_gf2m & polyn, u32bit the_code_length) : + code_length(the_code_length) + { + gf2m coeff_3; + gf2m coeff_head; + std::shared_ptr<GF2m_Field> sp_field = polyn.get_sp_field(); + int deg_sigma = polyn.get_degree(); + if(deg_sigma <= 3) + { + throw std::exception(); + } + this->m_j = 0; + coeff_3 = polyn.get_coef( 3); + coeff_head = polyn.get_coef( deg_sigma); /* dummy value for SCA CM */ + if(coeff_3 != 0) + { + this->m_sigma_3_l = sp_field->gf_l_from_n(coeff_3); + this->m_sigma_3_neq_0_mask = 0xFFFF; + } + else + { + // dummy value needed for timing countermeasure + this->m_sigma_3_l = sp_field->gf_l_from_n(coeff_head); + this->m_sigma_3_neq_0_mask = 0 ; + } -gf2m_decomp_rootfind_state::gf2m_decomp_rootfind_state(const polyn_gf2m & polyn, u32bit the_code_length) - :code_length(the_code_length) -{ - - gf2m coeff_3; - gf2m coeff_head; - std::shared_ptr<gf2m_small_m::Gf2m_Field> sp_field = polyn.get_sp_field(); - int deg_sigma = polyn.get_degree(); - if(deg_sigma <= 3) - { - throw std::exception(); - } - this->m_j = 0; - coeff_3 = polyn.get_coef( 3); - coeff_head = polyn.get_coef( deg_sigma); /* dummy value for SCA CM */ - if(coeff_3 != 0) - { - this->m_sigma_3_l = sp_field->gf_l_from_n(coeff_3); - this->m_sigma_3_neq_0_mask = 0xFFFF; - } - else - { - // dummy value needed for timing countermeasure - this->m_sigma_3_l = sp_field->gf_l_from_n(coeff_head); - this->m_sigma_3_neq_0_mask = 0 ; - } - - this->m_outer_summands = 1 + brootf_decomp__calc_sum_limit(deg_sigma); - this->m_Lik.resize(this->m_outer_summands * sp_field->get_extension_degree()); - this->m_Aij.resize(this->m_outer_summands); -} + this->m_outer_summands = 1 + brootf_decomp__calc_sum_limit(deg_sigma); + this->m_Lik.resize(this->m_outer_summands * sp_field->get_extension_degree()); + this->m_Aij.resize(this->m_outer_summands); + } void gf2m_decomp_rootfind_state::calc_Ai_zero(const polyn_gf2m & sigma) -{ - u32bit i; - /* + { + u32bit i; + /* * this function assumes this the first gray code element is zero */ - for(i = 0; i < this->m_outer_summands; i++) - { - this->m_Aij[i] = sigma.get_coef(5*i); - } - this->m_j = 0; - this->m_j_gray = 0; -} + for(i = 0; i < this->m_outer_summands; i++) + { + this->m_Aij[i] = sigma.get_coef(5*i); + } + this->m_j = 0; + this->m_j_gray = 0; + } void gf2m_decomp_rootfind_state::calc_next_Aij() -{ - /* + { + /* * upon function entry, we have in the state j, Aij. * first thing, we declare Aij Aij_minusone and increase j. * Case j=0 upon function entry also included, then Aij contains A_{i,j=0}. */ - u32bit i; - gf2m diff, new_j_gray; - u32bit Lik_pos_base; - - this->m_j++; - - new_j_gray = lex_to_gray(this->m_j); - - if(this->m_j & 1) /* half of the times */ - { - Lik_pos_base = 0; - } - else if(this->m_j & 2) /* one quarter of the times */ - { - Lik_pos_base = this->m_outer_summands; - } - else if( this->m_j & 4) /* one eighth of the times */ - { - Lik_pos_base = this->m_outer_summands * 2; - } - else if( this->m_j & 8) /* one sixteenth of the times */ - { - Lik_pos_base = this->m_outer_summands * 3; - } - else if( this->m_j & 16) /* ... */ - { - Lik_pos_base = this->m_outer_summands * 4; - } - else - { - gf2m delta_offs = 5; - diff = this->m_j_gray ^ new_j_gray; - while(((static_cast<gf2m>(1) << delta_offs) & diff) == 0) - { - delta_offs++; - - } - Lik_pos_base = delta_offs * this->m_outer_summands; - } - this->m_j_gray = new_j_gray; - - i = 0; - for(; i < this->m_outer_summands; i++) - { - this->m_Aij[i] ^= this->m_Lik[Lik_pos_base + i]; - } + u32bit i; + gf2m diff, new_j_gray; + u32bit Lik_pos_base; + + this->m_j++; + + new_j_gray = lex_to_gray(this->m_j); + + if(this->m_j & 1) /* half of the times */ + { + Lik_pos_base = 0; + } + else if(this->m_j & 2) /* one quarter of the times */ + { + Lik_pos_base = this->m_outer_summands; + } + else if( this->m_j & 4) /* one eighth of the times */ + { + Lik_pos_base = this->m_outer_summands * 2; + } + else if( this->m_j & 8) /* one sixteenth of the times */ + { + Lik_pos_base = this->m_outer_summands * 3; + } + else if( this->m_j & 16) /* ... */ + { + Lik_pos_base = this->m_outer_summands * 4; + } + else + { + gf2m delta_offs = 5; + diff = this->m_j_gray ^ new_j_gray; + while(((static_cast<gf2m>(1) << delta_offs) & diff) == 0) + { + delta_offs++; + + } + Lik_pos_base = delta_offs * this->m_outer_summands; + } + this->m_j_gray = new_j_gray; + + i = 0; + for(; i < this->m_outer_summands; i++) + { + this->m_Aij[i] ^= this->m_Lik[Lik_pos_base + i]; + } + + } -} void gf2m_decomp_rootfind_state::calc_LiK(const polyn_gf2m & sigma) -{ - std::shared_ptr<gf2m_small_m::Gf2m_Field> sp_field = sigma.get_sp_field(); - u32bit i, k, d; - d = sigma.get_degree(); - for(k = 0; k < sp_field->get_extension_degree(); k++) - { - u32bit Lik_pos_base = k * this->m_outer_summands; - gf2m alpha_l_k_tt2_ttj[4]; - alpha_l_k_tt2_ttj[0] = sp_field->gf_l_from_n(static_cast<gf2m>(1) << k); - alpha_l_k_tt2_ttj[1] = sp_field->gf_mul_rrr(alpha_l_k_tt2_ttj[0], alpha_l_k_tt2_ttj[0]); - alpha_l_k_tt2_ttj[2] = sp_field->gf_mul_rrr(alpha_l_k_tt2_ttj[1],alpha_l_k_tt2_ttj[1] ); - - alpha_l_k_tt2_ttj[3] = sp_field->gf_mul_rrr(alpha_l_k_tt2_ttj[2], alpha_l_k_tt2_ttj[2]); - for(i = 0; i < this->m_outer_summands; i++) - { - u32bit j; - u32bit five_i = 5*i; - u32bit Lik_pos = Lik_pos_base + i; - this->m_Lik[Lik_pos] = 0; - for(j = 0; j <= 3; j++) + { + std::shared_ptr<GF2m_Field> sp_field = sigma.get_sp_field(); + u32bit i, k, d; + d = sigma.get_degree(); + for(k = 0; k < sp_field->get_extension_degree(); k++) { - gf2m f, x; - u32bit f_ind = five_i + (static_cast<u32bit>(1) << j); - if(f_ind > d) - { - break; - } - f = sigma.get_coef( f_ind); - - x = sp_field->gf_mul_zrz(alpha_l_k_tt2_ttj[j], f); - this->m_Lik[Lik_pos] ^= x; + u32bit Lik_pos_base = k * this->m_outer_summands; + gf2m alpha_l_k_tt2_ttj[4]; + alpha_l_k_tt2_ttj[0] = sp_field->gf_l_from_n(static_cast<gf2m>(1) << k); + alpha_l_k_tt2_ttj[1] = sp_field->gf_mul_rrr(alpha_l_k_tt2_ttj[0], alpha_l_k_tt2_ttj[0]); + alpha_l_k_tt2_ttj[2] = sp_field->gf_mul_rrr(alpha_l_k_tt2_ttj[1],alpha_l_k_tt2_ttj[1] ); + + alpha_l_k_tt2_ttj[3] = sp_field->gf_mul_rrr(alpha_l_k_tt2_ttj[2], alpha_l_k_tt2_ttj[2]); + for(i = 0; i < this->m_outer_summands; i++) + { + u32bit j; + u32bit five_i = 5*i; + u32bit Lik_pos = Lik_pos_base + i; + this->m_Lik[Lik_pos] = 0; + for(j = 0; j <= 3; j++) + { + gf2m f, x; + u32bit f_ind = five_i + (static_cast<u32bit>(1) << j); + if(f_ind > d) + { + break; + } + f = sigma.get_coef( f_ind); + + x = sp_field->gf_mul_zrz(alpha_l_k_tt2_ttj[j], f); + this->m_Lik[Lik_pos] ^= x; + } + } } - } - } -} + } gf2m gf2m_decomp_rootfind_state::calc_Fxj_j_neq_0( const polyn_gf2m & sigma, gf2m j_gray) -{ - //needs the A_{ij} to compute F(x)_j - gf2m sum = 0; - u32bit i; - std::shared_ptr<gf2m_small_m::Gf2m_Field> sp_field = sigma.get_sp_field(); - gf2m xl_j_tt_5i, xl_j_tt_5, xl_gray_tt_3; - gf2m jl_gray; - jl_gray = sp_field->gf_l_from_n(j_gray); - xl_j_tt_5 = sp_field->gf_square_rr(jl_gray); - xl_gray_tt_3 = sp_field->gf_mul_rrr(xl_j_tt_5, jl_gray); - xl_j_tt_5 = sp_field->gf_mul_rrr(xl_j_tt_5, xl_gray_tt_3); - - - sum = sp_field->gf_mul_nrr(xl_gray_tt_3, this->m_sigma_3_l); - sum &= this->m_sigma_3_neq_0_mask; - /* here, we rely on compiler to be unable to optimize + { + //needs the A_{ij} to compute F(x)_j + gf2m sum = 0; + u32bit i; + std::shared_ptr<GF2m_Field> sp_field = sigma.get_sp_field(); + gf2m xl_j_tt_5i, xl_j_tt_5, xl_gray_tt_3; + const gf2m jl_gray = sp_field->gf_l_from_n(j_gray); + xl_j_tt_5 = sp_field->gf_square_rr(jl_gray); + xl_gray_tt_3 = sp_field->gf_mul_rrr(xl_j_tt_5, jl_gray); + xl_j_tt_5 = sp_field->gf_mul_rrr(xl_j_tt_5, xl_gray_tt_3); + + + sum = sp_field->gf_mul_nrr(xl_gray_tt_3, this->m_sigma_3_l); + sum &= this->m_sigma_3_neq_0_mask; + /* here, we rely on compiler to be unable to optimize * for the state->sigma_3_neq_0_mask value */ - /* treat i = 0 special: */ - sum ^= this->m_Aij[0]; - /* treat i = 1 special also */ - if(this->m_outer_summands > 1) - { - gf2m x; - xl_j_tt_5i = xl_j_tt_5; - x = sp_field->gf_mul_zrz(xl_j_tt_5, this->m_Aij[1]); /* x_j^{5i} A_i^j */ - sum ^= x; - } - for(i = 2; i < this->m_outer_summands; i++) - { - gf2m x; - xl_j_tt_5i = sp_field->gf_mul_rrr(xl_j_tt_5i, xl_j_tt_5); - // now x_j_tt_5i lives up to its name - x = sp_field->gf_mul_zrz(xl_j_tt_5i, this->m_Aij[i]); /* x_j^{5i} A_i^(j) */ - sum ^= x; - } - return sum; -} - + /* treat i = 0 special: */ + sum ^= this->m_Aij[0]; + /* treat i = 1 special also */ + if(this->m_outer_summands > 1) + { + gf2m x; + xl_j_tt_5i = xl_j_tt_5; + x = sp_field->gf_mul_zrz(xl_j_tt_5, this->m_Aij[1]); /* x_j^{5i} A_i^j */ + sum ^= x; + } + for(i = 2; i < this->m_outer_summands; i++) + { + gf2m x; + xl_j_tt_5i = sp_field->gf_mul_rrr(xl_j_tt_5i, xl_j_tt_5); + // now x_j_tt_5i lives up to its name + x = sp_field->gf_mul_zrz(xl_j_tt_5i, this->m_Aij[i]); /* x_j^{5i} A_i^(j) */ + sum ^= x; + } + return sum; + } +secure_vector<gf2m> gf2m_decomp_rootfind_state::find_roots(const polyn_gf2m & sigma) + { + secure_vector<gf2m> result(sigma.get_degree()); + u32bit root_pos = 0; + this->calc_Ai_zero(sigma); + this->calc_LiK(sigma); + do + { + gf2m eval_result; + if(this->m_j_gray == 0) + { + eval_result = sigma.get_coef( 0); + } + else + { + eval_result = this->calc_Fxj_j_neq_0(sigma, this->m_j_gray); + } + + if(eval_result == 0) + { + + result[root_pos] = this->m_j_gray; + root_pos++; + + } + if(this->m_j + static_cast<u32bit>(1) == this->get_code_length()) + { + break; + } + this->calc_next_Aij(); + }while(1); + + // side channel / fault attack countermeasure: + root_pos = patch_root_array(result.data(), result.size(), root_pos); + result.resize(root_pos); + return result; + } -secure_vector<gf2m> gf2m_decomp_rootfind_state::find_roots(const polyn_gf2m & sigma) -{ - - secure_vector<gf2m> result(sigma.get_degree()); - u32bit root_pos = 0; - - this->calc_Ai_zero(sigma); - this->calc_LiK(sigma); - do - { - gf2m eval_result; - if(this->m_j_gray == 0) - { - eval_result = sigma.get_coef( 0); - } - else - { - eval_result = this->calc_Fxj_j_neq_0(sigma, this->m_j_gray); - } - - if(eval_result == 0) - { - - result[root_pos] = this->m_j_gray; - root_pos++; - - } - if(this->m_j + static_cast<u32bit>(1) == this->get_code_length()) - { - break; - } - this->calc_next_Aij(); - }while(1); - - // side channel / fault attack countermeasure: - root_pos = patch_root_array(result.data(), result.size(), root_pos); - result.resize(root_pos); - return result; -} } // end namespace Botan diff --git a/src/lib/pubkey/mce/gf2m_rootfind_dcmp.h b/src/lib/pubkey/mce/gf2m_rootfind_dcmp.h deleted file mode 100644 index 5914ad3ae..000000000 --- a/src/lib/pubkey/mce/gf2m_rootfind_dcmp.h +++ /dev/null @@ -1,24 +0,0 @@ -/** - * (C) 2014 cryptosource GmbH - * (C) 2014 Falko Strenzke [email protected] - * - * Botan is released under the Simplified BSD License (see license.txt) - */ - -#ifndef BOTAN_GF2M_ROOTFIND_DCMP_H__ -#define BOTAN_GF2M_ROOTFIND_DCMP_H__ - -#include <botan/polyn_gf2m.h> - -namespace Botan { - -/** -* Find the roots of a polynomial over GF(2^m) using the method by Federenko -* et al. -*/ -secure_vector<gf2m> find_roots_gf2m_decomp(const polyn_gf2m & polyn, - u32bit code_length); - -} - -#endif diff --git a/src/lib/pubkey/mce/gf2m_small_m.cpp b/src/lib/pubkey/mce/gf2m_small_m.cpp index 3de748939..11da30962 100644 --- a/src/lib/pubkey/mce/gf2m_small_m.cpp +++ b/src/lib/pubkey/mce/gf2m_small_m.cpp @@ -9,14 +9,11 @@ */ #include <botan/gf2m_small_m.h> -#include <botan/code_based_util.h> #include <string> #include <stdexcept> namespace Botan { -namespace gf2m_small_m { - #define MAX_EXT_DEG 16 namespace { @@ -41,78 +38,94 @@ unsigned int prim_poly[MAX_EXT_DEG + 1] = { 0210013 /* extension degree 16 */ }; -} - -u32bit encode_gf2m(gf2m to_enc, byte* mem) +std::vector<gf2m> gf_exp_table(size_t deg, gf2m prime_poly) { - mem[0] = to_enc >> 8; - mem[1] = to_enc & 0xFF; - return sizeof(to_enc); + // construct the table gf_exp[i]=alpha^i + + std::vector<gf2m> tab((1 << deg) + 1); + + tab[0] = 1; + for(size_t i = 1; i < tab.size(); ++i) + { + const bool overflow = tab[i - 1] >> (deg - 1); + tab[i] = (tab[i-1] << 1) ^ (overflow ? prime_poly : 0); + } + + return tab; } -gf2m decode_gf2m(const byte* mem) +const std::vector<gf2m>& exp_table(size_t deg) { - gf2m result; - result = mem[0] << 8; - result |= mem[1]; - return result; + static std::vector<gf2m> tabs[MAX_EXT_DEG + 1]; + + if(deg < 2 || deg > MAX_EXT_DEG) + throw std::runtime_error("GF2m_Field does not support degree " + std::to_string(deg)); + + if(tabs[deg].empty()) + tabs[deg] = gf_exp_table(deg, prim_poly[deg]); + + return tabs[deg]; } -// construct the table gf_exp[i]=alpha^i -void Gf2m_Field::init_exp() +std::vector<gf2m> gf_log_table(size_t deg, const std::vector<gf2m>& exp) { - m_gf_exp_table.resize(1 << get_extension_degree()); + std::vector<gf2m> tab(1 << deg); - m_gf_exp_table[0] = 1; - for(size_t i = 1; i < gf_ord(); ++i) + tab[0] = (1 << deg) - 1; // log of 0 is the order by convention + for (size_t i = 0; i < tab.size(); ++i) { - m_gf_exp_table[i] = m_gf_exp_table[i - 1] << 1; - if (m_gf_exp_table[i - 1] & (1 << (get_extension_degree()-1))) - { - m_gf_exp_table[i] ^= prim_poly[get_extension_degree()]; - } + tab[exp[i]] = i; } - - // hack for the multiplication - m_gf_exp_table[gf_ord()] = 1; + return tab; } -// construct the table gf_log[alpha^i]=i -void Gf2m_Field::init_log() +const std::vector<gf2m>& log_table(size_t deg) { - m_gf_log_table.resize(1 << get_extension_degree()); + static std::vector<gf2m> tabs[MAX_EXT_DEG + 1]; - m_gf_log_table[0] = gf_ord(); // log of 0 par convention - for (size_t i = 0; i < gf_ord() ; ++i) - { - m_gf_log_table[m_gf_exp_table[i]] = i; - } + if(deg < 2 || deg > MAX_EXT_DEG) + throw std::runtime_error("GF2m_Field does not support degree " + std::to_string(deg)); + + if(tabs[deg].empty()) + tabs[deg] = gf_log_table(deg, exp_table(deg)); + + return tabs[deg]; } +} -Gf2m_Field::Gf2m_Field(size_t extdeg) +u32bit encode_gf2m(gf2m to_enc, byte* mem) { - if(extdeg < 2 || extdeg > MAX_EXT_DEG) - throw std::runtime_error("Gf2m_Field does not support degree " + std::to_string(extdeg)); + mem[0] = to_enc >> 8; + mem[1] = to_enc & 0xFF; + return sizeof(to_enc); + } - m_gf_extension_degree = extdeg; - m_gf_cardinality = 1 << extdeg; - m_gf_multiplicative_order = m_gf_cardinality - 1; +gf2m decode_gf2m(const byte* mem) + { + gf2m result; + result = mem[0] << 8; + result |= mem[1]; + return result; + } - init_exp(); - init_log(); +GF2m_Field::GF2m_Field(size_t extdeg) : m_gf_extension_degree(extdeg), + m_gf_multiplicative_order((1 << extdeg) - 1), + m_gf_log_table(log_table(m_gf_extension_degree)), + m_gf_exp_table(exp_table(m_gf_extension_degree)) + { } -gf2m Gf2m_Field::gf_div(gf2m x, gf2m y) +gf2m GF2m_Field::gf_div(gf2m x, gf2m y) const { - s32bit sub_res = static_cast<s32bit>(m_gf_log_table[x]) - static_cast<s32bit>( m_gf_log_table[y]); - s32bit modq_res = static_cast<s32bit>(_gf_modq_1(sub_res)); - s32bit div_res = static_cast<s32bit>(x) ? static_cast<s32bit>(m_gf_exp_table[modq_res]) : 0; + const s32bit sub_res = static_cast<s32bit>(gf_log(x) - static_cast<s32bit>(gf_log(y))); + const s32bit modq_res = static_cast<s32bit>(_gf_modq_1(sub_res)); + const s32bit div_res = static_cast<s32bit>(x) ? static_cast<s32bit>(gf_exp(modq_res)) : 0; return static_cast<gf2m>(div_res); } // we suppose i >= 0. Par convention 0^0 = 1 -gf2m Gf2m_Field::gf_pow(gf2m x, int i) +gf2m GF2m_Field::gf_pow(gf2m x, int i) const { if (i == 0) return 1; @@ -123,13 +136,11 @@ gf2m Gf2m_Field::gf_pow(gf2m x, int i) // i mod (q-1) while (i >> get_extension_degree()) i = (i & (gf_ord())) + (i >> get_extension_degree()); - i *= m_gf_log_table[x]; + i *= gf_log(x); while (i >> get_extension_degree()) i = (i & (gf_ord())) + (i >> get_extension_degree()); - return m_gf_exp_table[i]; + return gf_exp(i); } } } - -} diff --git a/src/lib/pubkey/mce/gf2m_small_m.h b/src/lib/pubkey/mce/gf2m_small_m.h index 223dfd511..6a8de4424 100644 --- a/src/lib/pubkey/mce/gf2m_small_m.h +++ b/src/lib/pubkey/mce/gf2m_small_m.h @@ -17,213 +17,199 @@ namespace Botan { -namespace gf2m_small_m { - typedef u16bit gf2m; -class Gf2m_Field +/** +* GF(2^m) field for m = [2...16] +*/ +class BOTAN_DLL GF2m_Field { public: - Gf2m_Field(size_t extdeg); + GF2m_Field(size_t extdeg); - gf2m gf_mul(gf2m x, gf2m y) + gf2m gf_mul(gf2m x, gf2m y) const { return ((x) ? gf_mul_fast(x, y) : 0); } - gf2m gf_square(gf2m x) + gf2m gf_square(gf2m x) const { - return ((x) ? m_gf_exp_table[_gf_modq_1(m_gf_log_table[x] << 1)] : 0); + return ((x) ? gf_exp(_gf_modq_1(gf_log(x) << 1)) : 0); } - gf2m square_rr(gf2m x) + gf2m square_rr(gf2m x) const { return _gf_modq_1(x << 1); } - // naming convention of GF(2^m) field operations: - // l logarithmic, unreduced - // r logarithmic, reduced - // n normal, non-zero - // z normal, might be zero - // - inline gf2m gf_mul_lll(gf2m a, gf2m b); - inline gf2m gf_mul_rrr(gf2m a, gf2m b); - inline gf2m gf_mul_nrr(gf2m a, gf2m b); - inline gf2m gf_mul_rrn(gf2m a, gf2m y); - inline gf2m gf_mul_lnn(gf2m x, gf2m y); - inline gf2m gf_mul_rnn(gf2m x, gf2m y); - inline gf2m gf_mul_nrn(gf2m a, gf2m y); - inline gf2m gf_mul_rnr(gf2m y, gf2m a); - inline gf2m gf_mul_zrz(gf2m a, gf2m y); - inline gf2m gf_mul_zzr(gf2m a, gf2m y); - inline gf2m gf_mul_nnr(gf2m y, gf2m a); - inline gf2m gf_sqrt(gf2m x) ; - gf2m gf_div(gf2m x, gf2m y); - inline gf2m gf_div_rnn(gf2m x, gf2m y); - inline gf2m gf_div_rnr(gf2m x, gf2m b); - inline gf2m gf_div_nrr(gf2m a, gf2m b); - inline gf2m gf_div_zzr(gf2m x, gf2m b); - inline gf2m gf_inv(gf2m x); - inline gf2m gf_inv_rn(gf2m x); - inline gf2m gf_square_ln(gf2m x); - inline gf2m gf_square_rr(gf2m a) ; - inline gf2m gf_l_from_n(gf2m x); + gf2m gf_mul_fast(gf2m x, gf2m y) const + { + return ((y) ? gf_exp(_gf_modq_1(gf_log(x) + gf_log(y))) : 0); + } - inline gf2m gf_mul_fast(gf2m a, gf2m b); + /* + naming convention of GF(2^m) field operations: + l logarithmic, unreduced + r logarithmic, reduced + n normal, non-zero + z normal, might be zero + */ - gf2m gf_exp(gf2m i) + gf2m gf_mul_lll(gf2m a, gf2m b) const { - return m_gf_exp_table[i]; /* alpha^i */ + return (a + b); } - gf2m gf_log(gf2m i) + gf2m gf_mul_rrr(gf2m a, gf2m b) const { - return m_gf_log_table[i]; /* return i when x=alpha^i */ + return (_gf_modq_1(gf_mul_lll(a, b))); } - inline gf2m gf_ord() const + gf2m gf_mul_nrr(gf2m a, gf2m b) const { - return m_gf_multiplicative_order; + return (gf_exp(gf_mul_rrr(a, b))); } - inline gf2m get_extension_degree() const + gf2m gf_mul_rrn(gf2m a, gf2m y) const { - return m_gf_extension_degree; + return _gf_modq_1(gf_mul_lll(a, gf_log(y))); } - inline gf2m get_cardinality() const + gf2m gf_mul_rnr(gf2m y, gf2m a) const { - return m_gf_cardinality; + return gf_mul_rrn(a, y); } - gf2m gf_pow(gf2m x, int i) ; + gf2m gf_mul_lnn(gf2m x, gf2m y) const + { + return (gf_log(x) + gf_log(y)); + } - private: - gf2m m_gf_extension_degree, m_gf_cardinality, m_gf_multiplicative_order; - std::vector<gf2m> m_gf_log_table; - std::vector<gf2m> m_gf_exp_table; + gf2m gf_mul_rnn(gf2m x, gf2m y) const + { + return _gf_modq_1(gf_mul_lnn(x, y)); + } - inline gf2m _gf_modq_1(s32bit d); - void init_log(); - void init_exp(); - }; + gf2m gf_mul_nrn(gf2m a, gf2m y) const + { + return gf_exp(_gf_modq_1((a) + gf_log(y))); + } -gf2m Gf2m_Field::_gf_modq_1(s32bit d) - { - return (((d) & gf_ord()) + ((d) >> m_gf_extension_degree)); - } + /** + * zero operand allowed + */ + gf2m gf_mul_zrz(gf2m a, gf2m y) const + { + return ( (y == 0) ? 0 : gf_mul_nrn(a, y) ); + } -gf2m Gf2m_Field::gf_mul_fast(gf2m x, gf2m y) - { - return ((y) ? m_gf_exp_table[_gf_modq_1(m_gf_log_table[x] + m_gf_log_table[y])] : 0); - } + gf2m gf_mul_zzr(gf2m a, gf2m y) const + { + return gf_mul_zrz(y, a); + } -gf2m Gf2m_Field::gf_mul_lll(gf2m a, gf2m b) - { - return (a + b); - } + /** + * non-zero operand + */ + gf2m gf_mul_nnr(gf2m y, gf2m a) const + { + return gf_mul_nrn(a, y); + } -gf2m Gf2m_Field::gf_mul_rrr(gf2m a, gf2m b) - { - return (_gf_modq_1(gf_mul_lll(a, b))); - } + gf2m gf_sqrt(gf2m x) const + { + return ((x) ? gf_exp(_gf_modq_1(gf_log(x) << (get_extension_degree()-1))) : 0); + } -gf2m Gf2m_Field::gf_mul_nrr(gf2m a, gf2m b) - { - return (gf_exp(gf_mul_rrr(a, b))); - } + gf2m gf_div_rnn(gf2m x, gf2m y) const + { + return _gf_modq_1(gf_log(x) - gf_log(y)); + } -gf2m Gf2m_Field::gf_mul_rrn(gf2m a, gf2m y) - { - return _gf_modq_1(gf_mul_lll(a, gf_log(y))); - } + gf2m gf_div_rnr(gf2m x, gf2m b) const + { + return _gf_modq_1(gf_log(x) - b); + } -gf2m Gf2m_Field::gf_mul_rnr(gf2m y, gf2m a) - { - return gf_mul_rrn(a, y); - } + gf2m gf_div_nrr(gf2m a, gf2m b) const + { + return gf_exp(_gf_modq_1(a - b)); + } -gf2m Gf2m_Field::gf_mul_lnn(gf2m x, gf2m y) - { - return (m_gf_log_table[x] + m_gf_log_table[y]); - } -gf2m Gf2m_Field::gf_mul_rnn(gf2m x, gf2m y) - { - return _gf_modq_1(gf_mul_lnn(x, y)); - } + gf2m gf_div_zzr(gf2m x, gf2m b) const + { + return ((x) ? gf_exp(_gf_modq_1(gf_log(x) - b)) : 0); + } -gf2m Gf2m_Field::gf_mul_nrn(gf2m a, gf2m y) - { - return m_gf_exp_table[_gf_modq_1((a) + m_gf_log_table[y])]; - } + gf2m gf_inv(gf2m x) const + { + return gf_exp(gf_ord() - gf_log(x)); + } -/** -* zero operand allowed -*/ -gf2m Gf2m_Field::gf_mul_zrz(gf2m a, gf2m y) - { - return ( (y == 0) ? 0 : gf_mul_nrn(a, y) ); - } + gf2m gf_inv_rn(gf2m x) const + { + return (gf_ord() - gf_log(x)); + } -gf2m Gf2m_Field::gf_mul_zzr(gf2m a, gf2m y) - { - return gf_mul_zrz(y, a); - } -/** -* non-zero operand -*/ -gf2m Gf2m_Field::gf_mul_nnr(gf2m y, gf2m a) - { - return gf_mul_nrn( a, y); - } + gf2m gf_square_ln(gf2m x) const + { + return gf_log(x) << 1; + } -gf2m Gf2m_Field::gf_sqrt(gf2m x) - { - return ((x) ? m_gf_exp_table[_gf_modq_1(m_gf_log_table[x] << (m_gf_extension_degree-1))] : 0); - } + gf2m gf_square_rr(gf2m a) const + { + return a << 1; + } -gf2m Gf2m_Field::gf_div_rnn(gf2m x, gf2m y) - { - return _gf_modq_1(m_gf_log_table[x] - m_gf_log_table[y]); - } -gf2m Gf2m_Field::gf_div_rnr(gf2m x, gf2m b) - { - return _gf_modq_1(m_gf_log_table[x] - b); - } -gf2m Gf2m_Field::gf_div_nrr(gf2m a, gf2m b) - { - return m_gf_exp_table[_gf_modq_1(a - b)]; - } + gf2m gf_l_from_n(gf2m x) const + { + return gf_log(x); + } -gf2m Gf2m_Field::gf_div_zzr(gf2m x, gf2m b) - { - return ((x) ? m_gf_exp_table[_gf_modq_1(m_gf_log_table[x] - b)] : 0); - } + gf2m gf_div(gf2m x, gf2m y) const; -gf2m Gf2m_Field::gf_inv(gf2m x) - { - return m_gf_exp_table[gf_ord() - m_gf_log_table[x]]; - } -gf2m Gf2m_Field::gf_inv_rn(gf2m x) - { - return (gf_ord() - m_gf_log_table[x]); - } + gf2m gf_pow(gf2m x, int i) const; -gf2m Gf2m_Field::gf_square_ln(gf2m x) - { - return m_gf_log_table[x] << 1; - } + gf2m gf_exp(gf2m i) const + { + return m_gf_exp_table.at(i); /* alpha^i */ + } -gf2m Gf2m_Field::gf_square_rr(gf2m a) - { - return a << 1; - } + gf2m gf_log(gf2m i) const + { + return m_gf_log_table.at(i); /* return i when x=alpha^i */ + } -gf2m Gf2m_Field::gf_l_from_n(gf2m x) - { - return m_gf_log_table[x]; - } + gf2m gf_ord() const + { + return m_gf_multiplicative_order; + } + + gf2m get_extension_degree() const + { + return m_gf_extension_degree; + } + + gf2m get_cardinality() const + { + return static_cast<gf2m>(1 << get_extension_degree()); + } + + private: + gf2m _gf_modq_1(s32bit d) const + { + /* residual modulo q-1 + when -q < d < 0, we get (q-1+d) + when 0 <= d < q, we get (d) + when q <= d < 2q-1, we get (d-q+1) + */ + return (((d) & gf_ord()) + ((d) >> get_extension_degree())); + } + + gf2m m_gf_extension_degree, m_gf_multiplicative_order; + const std::vector<gf2m>& m_gf_log_table; + const std::vector<gf2m>& m_gf_exp_table; + }; u32bit encode_gf2m(gf2m to_enc, byte* mem); @@ -231,6 +217,4 @@ gf2m decode_gf2m(const byte* mem); } -} - #endif diff --git a/src/lib/pubkey/mce/goppa_code.cpp b/src/lib/pubkey/mce/goppa_code.cpp index 175508eac..637b8175a 100644 --- a/src/lib/pubkey/mce/goppa_code.cpp +++ b/src/lib/pubkey/mce/goppa_code.cpp @@ -9,10 +9,8 @@ * */ -#include <botan/goppa_code.h> - -#include <botan/gf2m_rootfind_dcmp.h> -#include <botan/code_based_util.h> +#include <botan/internal/mce_internal.h> +#include <botan/internal/code_based_util.h> namespace Botan { @@ -48,7 +46,7 @@ secure_vector<gf2m> goppa_decode(const polyn_gf2m & syndrom_polyn, u32bit code_length = Linv.size(); u32bit t = g.get_degree(); - std::shared_ptr<gf2m_small_m::Gf2m_Field> sp_field = g.get_sp_field(); + 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; @@ -125,6 +123,37 @@ secure_vector<gf2m> goppa_decode(const polyn_gf2m & syndrom_polyn, } } +void mceliece_decrypt(secure_vector<byte>& plaintext_out, + secure_vector<byte>& error_mask_out, + const secure_vector<byte>& ciphertext, + const McEliece_PrivateKey& key) + { + mceliece_decrypt(plaintext_out, error_mask_out, ciphertext.data(), ciphertext.size(), key); + } + +void mceliece_decrypt( + secure_vector<byte>& plaintext, + secure_vector<byte> & error_mask, + const byte 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<byte> result((code_length+7)/8); + for(auto&& pos : error_pos) + { + if(pos > code_length) + { + throw std::invalid_argument("error position larger than code size"); + } + result[pos / 8] |= (1 << (pos % 8)); + } + + error_mask = result; + } /** * @param p_err_pos_len must point to the available length of err_pos on input, the @@ -154,30 +183,27 @@ secure_vector<byte> mceliece_decrypt( throw Invalid_Argument("mce-decryption: wrong length of cleartext buffer"); } - secure_vector<u32bit> 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() ); + 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<byte> syndrome_byte_vec(bit_size_to_byte_size(codimension)); u32bit syndrome_byte_vec_size = syndrome_byte_vec.size(); for(u32bit i = 0; i < syndrome_byte_vec_size; i++) { syndrome_byte_vec[i] = 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 = 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()); u32bit nb_err = error_pos.size(); - secure_vector<byte> cleartext(cleartext_len); copy_mem(cleartext.data(), ciphertext, cleartext_len); @@ -192,6 +218,7 @@ secure_vector<byte> mceliece_decrypt( } cleartext[current / 8] ^= (1 << (current % 8)); } + if(unused_pt_bits) { cleartext[cleartext_len - 1] &= unused_pt_bits_mask; diff --git a/src/lib/pubkey/mce/goppa_code.h b/src/lib/pubkey/mce/goppa_code.h deleted file mode 100644 index 377cd9b3d..000000000 --- a/src/lib/pubkey/mce/goppa_code.h +++ /dev/null @@ -1,32 +0,0 @@ -/** - * (C) Copyright Projet SECRET, INRIA, Rocquencourt - * (C) Bhaskar Biswas and Nicolas Sendrier - * - * (C) 2014 cryptosource GmbH - * (C) 2014 Falko Strenzke [email protected] - * - * Botan is released under the Simplified BSD License (see license.txt) - * - */ - -#ifndef BOTAN_MCE_GOPPA_CODE_H__ -#define BOTAN_MCE_GOPPA_CODE_H__ - -#include <botan/polyn_gf2m.h> -#include <botan/mceliece_key.h> - -namespace Botan { - -std::vector<byte> mceliece_encrypt(const secure_vector<byte>& cleartext, - const std::vector<byte>& public_matrix, - const secure_vector<gf2m> & err_pos, - u32bit code_length); - -secure_vector<byte> mceliece_decrypt(secure_vector<gf2m> & error_pos, - const byte *ciphertext, - u32bit ciphertext_len, - const McEliece_PrivateKey& key); - -} - -#endif diff --git a/src/lib/pubkey/mce/info.txt b/src/lib/pubkey/mce/info.txt index c06e23b8e..1e9b848dd 100644 --- a/src/lib/pubkey/mce/info.txt +++ b/src/lib/pubkey/mce/info.txt @@ -1,17 +1,17 @@ -define MCELIECE 20141124 +define MCELIECE 20150922 <header:public> -code_based_util.h -gf2m_rootfind_dcmp.h -gf2m_small_m.h -goppa_code.h mce_kem.h mceliece.h -mceliece_key.h polyn_gf2m.h +gf2m_small_m.h </header:public> <header:internal> -binary_matrix.h -code_based_key_gen.h +code_based_util.h +mce_internal.h </header:internal> + +<requires> +sha2_64 +</requires> diff --git a/src/lib/pubkey/mce/mce_internal.h b/src/lib/pubkey/mce/mce_internal.h new file mode 100644 index 000000000..d35479080 --- /dev/null +++ b/src/lib/pubkey/mce/mce_internal.h @@ -0,0 +1,52 @@ +/** + * (C) Copyright Projet SECRET, INRIA, Rocquencourt + * (C) Bhaskar Biswas and Nicolas Sendrier + * + * (C) 2014 cryptosource GmbH + * (C) 2014 Falko Strenzke [email protected] + * + * Botan is released under the Simplified BSD License (see license.txt) + * + */ + +#ifndef BOTAN_MCELIECE_INTERNAL_H__ +#define BOTAN_MCELIECE_INTERNAL_H__ + +#include <botan/secmem.h> +#include <botan/types.h> +#include <botan/pk_ops.h> +#include <botan/mceliece.h> + +namespace Botan { + +void mceliece_decrypt(secure_vector<byte>& plaintext_out, + secure_vector<byte>& error_mask_out, + const byte ciphertext[], + size_t ciphertext_len, + const McEliece_PrivateKey& key); + +void mceliece_decrypt(secure_vector<byte>& plaintext_out, + secure_vector<byte>& error_mask_out, + const secure_vector<byte>& ciphertext, + const McEliece_PrivateKey& key); + +secure_vector<byte> mceliece_decrypt( + secure_vector<gf2m> & error_pos, + const byte *ciphertext, u32bit ciphertext_len, + const McEliece_PrivateKey & key); + +void mceliece_encrypt(secure_vector<byte>& ciphertext_out, + secure_vector<byte>& error_mask_out, + const secure_vector<byte>& plaintext, + const McEliece_PublicKey& key, + RandomNumberGenerator& rng); + +McEliece_PrivateKey generate_mceliece_key(RandomNumberGenerator &rng, + u32bit ext_deg, + u32bit code_length, + u32bit t); + +} + + +#endif diff --git a/src/lib/pubkey/mce/mce_kem.cpp b/src/lib/pubkey/mce/mce_kem.cpp index b24c42f85..dede67731 100644 --- a/src/lib/pubkey/mce/mce_kem.cpp +++ b/src/lib/pubkey/mce/mce_kem.cpp @@ -7,56 +7,42 @@ */ #include <botan/mce_kem.h> +#include <botan/internal/mce_internal.h> #include <botan/sha2_64.h> namespace Botan { McEliece_KEM_Encryptor::McEliece_KEM_Encryptor(const McEliece_PublicKey& public_key) : - m_raw_pub_op(public_key, public_key.get_code_length()) + m_key(public_key) { } std::pair<secure_vector<byte>, secure_vector<byte>> McEliece_KEM_Encryptor::encrypt(RandomNumberGenerator& rng) { - const McEliece_PublicKey& key = m_raw_pub_op.get_key(); - secure_vector<Botan::byte> plaintext((key.get_message_word_bit_length()+7)/8); - rng.randomize(plaintext.data(), plaintext.size()); + const secure_vector<byte> plaintext = m_key.random_plaintext_element(rng); - // unset unused bits in the last plaintext byte - u32bit used = key.get_message_word_bit_length() % 8; - if(used) - { - byte mask = (1 << used) - 1; - plaintext[plaintext.size() - 1] &= mask; - } - - secure_vector<gf2m> err_pos = create_random_error_positions(key.get_code_length(), key.get_t(), rng); - - mceliece_message_parts parts(err_pos, plaintext, key.get_code_length()); - secure_vector<Botan::byte> message_and_error_input = parts.get_concat(); + secure_vector<byte> ciphertext, error_mask; + mceliece_encrypt(ciphertext, error_mask, plaintext, m_key, rng); SHA_512 hash; - hash.update(message_and_error_input); + hash.update(plaintext); + hash.update(error_mask); secure_vector<byte> sym_key = hash.final(); - secure_vector<byte> ciphertext = m_raw_pub_op.encrypt(message_and_error_input.data(), - message_and_error_input.size(), rng); return std::make_pair(ciphertext, sym_key); } - -McEliece_KEM_Decryptor::McEliece_KEM_Decryptor(const McEliece_PrivateKey& mce_key) : - m_raw_priv_op(mce_key) - { - } +McEliece_KEM_Decryptor::McEliece_KEM_Decryptor(const McEliece_PrivateKey& key) : m_key(key) { } secure_vector<Botan::byte> McEliece_KEM_Decryptor::decrypt(const byte msg[], size_t msg_len) { - secure_vector<Botan::byte> message_and_error = m_raw_priv_op.decrypt(msg, msg_len); + secure_vector<byte> plaintext, error_mask; + mceliece_decrypt(plaintext, error_mask, msg, msg_len, m_key); SHA_512 hash; - hash.update(message_and_error); + hash.update(plaintext); + hash.update(error_mask); secure_vector<byte> sym_key = hash.final(); return sym_key; diff --git a/src/lib/pubkey/mce/mce_kem.h b/src/lib/pubkey/mce/mce_kem.h index 7a8d2f7ff..cd899d568 100644 --- a/src/lib/pubkey/mce/mce_kem.h +++ b/src/lib/pubkey/mce/mce_kem.h @@ -25,7 +25,7 @@ class BOTAN_DLL McEliece_KEM_Encryptor std::pair<secure_vector<byte>, secure_vector<byte>> encrypt(RandomNumberGenerator& rng); private: - McEliece_Public_Operation m_raw_pub_op; + const McEliece_PublicKey& m_key; }; class BOTAN_DLL McEliece_KEM_Decryptor @@ -45,10 +45,10 @@ class BOTAN_DLL McEliece_KEM_Decryptor secure_vector<Botan::byte> decrypt_vec(const std::vector<byte, Alloc>& v) { return decrypt(v.data(), v.size()); - } + private: - McEliece_Private_Operation m_raw_priv_op; + const McEliece_PrivateKey& m_key; }; } diff --git a/src/lib/pubkey/mce/mceliece.cpp b/src/lib/pubkey/mce/mceliece.cpp index 08b3f13a3..dd05b8212 100644 --- a/src/lib/pubkey/mce/mceliece.cpp +++ b/src/lib/pubkey/mce/mceliece.cpp @@ -9,164 +9,127 @@ * */ +#include <botan/internal/mce_internal.h> #include <botan/mceliece.h> -#include <botan/mceliece_key.h> -#include <botan/internal/code_based_key_gen.h> -#include <botan/polyn_gf2m.h> -#include <botan/code_based_util.h> -#include <botan/goppa_code.h> +#include <botan/internal/code_based_util.h> #include <botan/internal/bit_ops.h> +#include <set> namespace Botan { namespace { -void concat_vectors(byte* x, const byte* a, const byte* b, u32bit dimension, u32bit codimension) +secure_vector<byte> concat_vectors(const secure_vector<byte>& a, const secure_vector<byte>& b, + u32bit dimension, u32bit codimension) { - if(dimension % 8 == 0) + secure_vector<byte> x(bit_size_to_byte_size(dimension) + bit_size_to_byte_size(codimension)); + + const size_t final_bits = dimension % 8; + + if(final_bits == 0) { const size_t dim_bytes = bit_size_to_byte_size(dimension); - copy_mem(x, a, dim_bytes); - copy_mem(x + dim_bytes, b, bit_size_to_byte_size(codimension)); + copy_mem(&x[0], a.data(), dim_bytes); + copy_mem(&x[dim_bytes], b.data(), bit_size_to_byte_size(codimension)); } else { - u32bit i, j, k, l; - i = dimension - 8 * (dimension/ 8); - j = 8 - i; - l = dimension / 8; - copy_mem(x, a, 1 * (dimension / 8)); - x[l] = static_cast<byte>(a[l] & ((1 << i) - 1)); - - for(k = 0; k < codimension / 8; ++k) + copy_mem(&x[0], a.data(), (dimension / 8)); + u32bit l = dimension / 8; + x[l] = static_cast<byte>(a[l] & ((1 << final_bits) - 1)); + + for(u32bit k = 0; k < codimension / 8; ++k) { - x[l] ^= static_cast<byte>(b[k] << i); + x[l] ^= static_cast<byte>(b[k] << final_bits); ++l; - x[l] = static_cast<byte>(b[k] >> j); + x[l] = static_cast<byte>(b[k] >> (8 - final_bits)); } - x[l] ^= static_cast<byte>(b[k] << i); + x[l] ^= static_cast<byte>(b[codimension/8] << final_bits); } + + return x; } -std::vector<byte> mult_by_pubkey(const byte *cleartext, - std::vector<byte> const& public_matrix, - u32bit code_length, u32bit t) +secure_vector<byte> mult_by_pubkey(const secure_vector<byte>& cleartext, + std::vector<byte> const& public_matrix, + u32bit code_length, u32bit t) { - std::vector<byte> ciphertext(code_length); - u32bit i, j; - u32bit ext_deg = ceil_log2(code_length); - u32bit codimension = ext_deg * t; - u32bit dimension = code_length - codimension; - std::vector<byte> cR(bit_size_to_32bit_size(codimension)* sizeof(u32bit)); + const u32bit ext_deg = ceil_log2(code_length); + const u32bit codimension = ext_deg * t; + const u32bit dimension = code_length - codimension; + secure_vector<byte> cR(bit_size_to_32bit_size(codimension) * sizeof(u32bit)); const byte* pt = public_matrix.data(); - for(i = 0; i < dimension / 8; ++i) + for(size_t i = 0; i < dimension / 8; ++i) { - for(j = 0; j < 8; ++j) + for(size_t j = 0; j < 8; ++j) { if(cleartext[i] & (1 << j)) { xor_buf(cR.data(), pt, cR.size()); } - pt += bit_size_to_32bit_size(codimension) * sizeof(u32bit); + pt += cR.size(); } } - for(j = 0; j < dimension % 8 ; ++j) + for(size_t i = 0; i < dimension % 8 ; ++i) { - if(cleartext[i] & (1 << j)) + if(cleartext[dimension/8] & (1 << i)) { - xor_buf(cR.data(), pt, bit_size_to_byte_size(codimension)); + xor_buf(cR.data(), pt, cR.size()); } - pt += bit_size_to_32bit_size(codimension) * sizeof(u32bit); + pt += cR.size(); } - concat_vectors(ciphertext.data(), cleartext, cR.data(), dimension, codimension); + secure_vector<byte> ciphertext = concat_vectors(cleartext, cR, dimension, codimension); + ciphertext.resize((code_length+7)/8); return ciphertext; } -} - -secure_vector<gf2m> create_random_error_positions(unsigned code_length, - unsigned error_weight, - RandomNumberGenerator& rng) - { - secure_vector<gf2m> result(error_weight); - gf2m i; - for(i = 0; i < result.size(); i++) - { - unsigned j; - char try_again = 0; - do - { - try_again = 0; - gf2m new_pos = random_code_element(code_length, rng); - for(j = 0; j < i; j++) - { - if(new_pos == result[j]) - { - try_again = 1; - break; - } - } - result[i] = new_pos; - } while(try_again); - } - return result; - } - -McEliece_Private_Operation::McEliece_Private_Operation(const McEliece_PrivateKey& private_key) - :m_priv_key(private_key) +secure_vector<byte> create_random_error_vector(unsigned code_length, + unsigned error_weight, + RandomNumberGenerator& rng) { - } - -secure_vector<byte> McEliece_Private_Operation::decrypt(const byte msg[], size_t msg_len) - { - secure_vector<gf2m> err_pos; + secure_vector<byte> result((code_length+7)/8); - secure_vector<byte> plaintext = mceliece_decrypt( - err_pos, - msg, msg_len, - m_priv_key - ); + size_t bits_set = 0; - return mceliece_message_parts(err_pos, plaintext, m_priv_key.get_code_length()).get_concat(); - } + while(bits_set < error_weight) + { + gf2m x = random_code_element(code_length, rng); -McEliece_Public_Operation::McEliece_Public_Operation(const McEliece_PublicKey& public_key, u32bit the_code_length) - :m_pub_key(public_key), - m_code_length(the_code_length) - {} + const size_t byte_pos = x / 8, bit_pos = x % 8; -secure_vector<byte> McEliece_Public_Operation::encrypt(const byte msg[], size_t msg_len, RandomNumberGenerator&) - { - mceliece_message_parts parts(msg, msg_len, m_pub_key.get_code_length()); - secure_vector<gf2m> err_pos = parts.get_error_positions(); - secure_vector<byte> message_word = parts.get_message_word(); - secure_vector<byte> ciphertext((m_pub_key.get_code_length()+7)/8); + const byte mask = (1 << bit_pos); + if(result[byte_pos] & mask) + continue; // already set this bit - std::vector<byte> ciphertext_tmp = mceliece_encrypt( message_word, m_pub_key.get_public_matrix(), err_pos, m_code_length); + result[byte_pos] |= mask; + bits_set++; + } - copy_mem(ciphertext.data(), ciphertext_tmp.data(), ciphertext.size()); - return ciphertext; + return result; } -std::vector<byte> mceliece_encrypt(const secure_vector<byte> & cleartext, - std::vector<byte> const& public_matrix, - const secure_vector<gf2m> & err_pos, - u32bit code_length) +} + +void mceliece_encrypt(secure_vector<byte>& ciphertext_out, + secure_vector<byte>& error_mask_out, + const secure_vector<byte>& plaintext, + const McEliece_PublicKey& key, + RandomNumberGenerator& rng) { - std::vector<byte> ciphertext = mult_by_pubkey(cleartext.data(), public_matrix, code_length, err_pos.size()); + secure_vector<byte> error_mask = create_random_error_vector(key.get_code_length(), key.get_t(), rng); - // flip t error positions - for(size_t i = 0; i < err_pos.size(); ++i) - { - ciphertext[err_pos[i] / 8] ^= (1 << (err_pos[i] % 8)); - } + secure_vector<byte> ciphertext = mult_by_pubkey(plaintext, key.get_public_matrix(), + key.get_code_length(), key.get_t()); - return ciphertext; + ciphertext ^= error_mask; + + ciphertext_out.swap(ciphertext); + error_mask_out.swap(error_mask); } } diff --git a/src/lib/pubkey/mce/mceliece.h b/src/lib/pubkey/mce/mceliece.h index c5f02470f..ead326230 100644 --- a/src/lib/pubkey/mce/mceliece.h +++ b/src/lib/pubkey/mce/mceliece.h @@ -9,141 +9,128 @@ * */ -#ifndef BOTAN_MCELIECE_H__ -#define BOTAN_MCELIECE_H__ +#ifndef BOTAN_MCELIECE_KEY_H__ +#define BOTAN_MCELIECE_KEY_H__ -#include <botan/secmem.h> -#include <botan/types.h> -#include <botan/pk_ops.h> -#include <botan/mceliece_key.h> - -#define MASK_LOG2_BYTE ((1 << 3) - 1) -#define _BITP_TO_BYTEP(__bit_pos) (__bit_pos >> 3) -#define _BITP_TO_BYTEOFFS(__bit_pos) (__bit_pos & MASK_LOG2_BYTE) +#include <botan/pk_keys.h> +#include <botan/polyn_gf2m.h> +#include <botan/exceptn.h> namespace Botan { -secure_vector<gf2m> BOTAN_DLL create_random_error_positions(unsigned code_length, unsigned error_weight, RandomNumberGenerator& rng); - -class mceliece_message_parts +class BOTAN_DLL McEliece_PublicKey : public virtual Public_Key { public: + McEliece_PublicKey(const std::vector<byte>& key_bits); - mceliece_message_parts(const secure_vector<gf2m>& err_pos, const byte* message, u32bit message_length, u32bit code_length) : - m_error_vector(error_vector_from_error_positions(err_pos.data(), err_pos.size(), code_length)), - m_code_length(code_length) - { - m_message_word.resize(message_length); - copy_mem(m_message_word.data(), message, message_length); - } - - mceliece_message_parts(const secure_vector<gf2m>& err_pos, const secure_vector<byte>& message, unsigned code_length) : - m_error_vector(error_vector_from_error_positions(err_pos.data(), err_pos.size(), code_length)), - m_message_word(message), - m_code_length(code_length) - {} - - static secure_vector<byte> error_vector_from_error_positions(const gf2m* err_pos, size_t err_pos_len, size_t code_length) - { - secure_vector<byte> result((code_length+7)/8); - for(unsigned i = 0; i < err_pos_len; i++) - { - u16bit pos = err_pos[i]; - u32bit byte_pos = _BITP_TO_BYTEP(pos); - if(byte_pos > result.size()) - { - throw Invalid_Argument("error position larger than code size"); - } - result[byte_pos] |= (1 << _BITP_TO_BYTEOFFS(pos)); - } - return result; - } - - mceliece_message_parts(const byte* message_concat_errors, size_t message_concat_errors_len, unsigned code_length) : - m_code_length(code_length) - { - size_t err_vec_len = (code_length+7)/8; - if(message_concat_errors_len < err_vec_len ) - { - throw Invalid_Argument("cannot split McEliece message parts"); - } - size_t err_vec_start_pos = message_concat_errors_len - err_vec_len; - m_message_word = secure_vector<byte>(err_vec_start_pos); - copy_mem(m_message_word.data(), message_concat_errors, err_vec_start_pos); - m_error_vector = secure_vector<byte>(err_vec_len); - copy_mem(m_error_vector.data(), &message_concat_errors[err_vec_start_pos], err_vec_len); - } - - secure_vector<byte> get_concat() const - { - secure_vector<byte> result(m_error_vector.size() + m_message_word.size()); - copy_mem(result.data(), m_message_word.data(), m_message_word.size()); - copy_mem(&result[m_message_word.size()], m_error_vector.data(), m_error_vector.size()); - return result; - } - - secure_vector<gf2m> get_error_positions() const - { - secure_vector<gf2m> result; - for(unsigned i = 0; i < m_code_length; i++) - { - if(i >= m_code_length) - { - throw Invalid_Argument("index out of range in get_error_positions()"); - } - if((m_error_vector[_BITP_TO_BYTEP(i)] >> _BITP_TO_BYTEOFFS(i)) & 1) - { - result.push_back(i); - } - } - return result; - } - - secure_vector<byte> get_error_vector() const { return m_error_vector; } - secure_vector<byte> get_message_word() const { return m_message_word; } - private: - secure_vector<byte> m_error_vector; - secure_vector<byte> m_message_word; - unsigned m_code_length; - }; + McEliece_PublicKey(std::vector<byte> const& pub_matrix, u32bit the_t, u32bit the_code_length) : + m_public_matrix(pub_matrix), + m_t(the_t), + m_code_length(the_code_length) + {} -class BOTAN_DLL McEliece_Private_Operation : public PK_Ops::Decryption - { - public: - McEliece_Private_Operation(const McEliece_PrivateKey& mce_key); + McEliece_PublicKey(const McEliece_PublicKey& other); - size_t max_input_bits() const override { return m_priv_key.max_input_bits(); } + secure_vector<byte> random_plaintext_element(RandomNumberGenerator& rng) const; - secure_vector<byte> decrypt(const byte msg[], size_t msg_len) override; + std::string algo_name() const override { return "McEliece"; } - McEliece_PrivateKey const& get_key() const { return m_priv_key; } + /** + * Get the maximum number of bits allowed to be fed to this key. + * @result the maximum number of input bits + */ + size_t max_input_bits() const override { return get_message_word_bit_length(); } - private: - const McEliece_PrivateKey m_priv_key; + AlgorithmIdentifier algorithm_identifier() const override; + + size_t estimated_strength() const override; + + std::vector<byte> x509_subject_public_key() const override; + + bool check_key(RandomNumberGenerator&, bool) const override + { return true; } + + u32bit get_t() const { return m_t; } + u32bit get_code_length() const { return m_code_length; } + u32bit get_message_word_bit_length() const; + const std::vector<byte>& get_public_matrix() const { return m_public_matrix; } + + bool operator==(const McEliece_PublicKey& other) const; + bool operator!=(const McEliece_PublicKey& other) const { return !(*this == other); } + + protected: + McEliece_PublicKey() {} + + std::vector<byte> m_public_matrix; + u32bit m_t; + u32bit m_code_length; }; -class BOTAN_DLL McEliece_Public_Operation : public PK_Ops::Encryption +class BOTAN_DLL McEliece_PrivateKey : public virtual McEliece_PublicKey, + public virtual Private_Key { public: - McEliece_Public_Operation(const McEliece_PublicKey& public_key, u32bit code_length); + /** + * Get the maximum number of bits allowed to be fed to this key. + * @result the maximum number of input bits + */ + size_t max_input_bits() const override { return m_Linv.size(); } + + /** + Generate a McEliece key pair + + Suggested parameters for a given security level (SL) + + SL=80 n=1632 t=33 - 59 KB pubkey 140 KB privkey + SL=107 n=2480 t=45 - 128 KB pubkey 300 KB privkey + SL=128 n=2960 t=57 - 195 KB pubkey 459 KB privkey + SL=147 n=3408 t=67 - 265 KB pubkey 622 KB privkey + SL=191 n=4624 t=95 - 516 KB pubkey 1234 KB privkey + SL=256 n=6624 t=115 - 942 KB pubkey 2184 KB privkey + */ + McEliece_PrivateKey(RandomNumberGenerator& rng, size_t code_length, size_t t); + + McEliece_PrivateKey(const secure_vector<byte>& key_bits); + + McEliece_PrivateKey(polyn_gf2m const& goppa_polyn, + std::vector<u32bit> const& parity_check_matrix_coeffs, + std::vector<polyn_gf2m> const& square_root_matrix, + std::vector<gf2m> const& inverse_support, + std::vector<byte> const& public_matrix ); + + bool check_key(RandomNumberGenerator& rng, bool strong) const override; - size_t max_input_bits() const override { return m_pub_key.max_input_bits(); } - secure_vector<byte> encrypt(const byte msg[], size_t msg_len, RandomNumberGenerator&) override; + polyn_gf2m const& get_goppa_polyn() const { return m_g; } + std::vector<u32bit> const& get_H_coeffs() const { return m_coeffs; } + std::vector<gf2m> const& get_Linv() const { return m_Linv; } + std::vector<polyn_gf2m> const& get_sqrtmod() const { return m_sqrtmod; } - McEliece_PublicKey const& get_key() const { return m_pub_key; } + inline u32bit get_dimension() const { return m_dimension; } + + inline u32bit get_codimension() const { return m_codimension; } + + secure_vector<byte> pkcs8_private_key() const override; + + bool operator==(const McEliece_PrivateKey & other) const; + + bool operator!=(const McEliece_PrivateKey& other) const { return !(*this == other); } private: - McEliece_PublicKey m_pub_key; - u32bit m_code_length; + polyn_gf2m m_g; + std::vector<polyn_gf2m> m_sqrtmod; + std::vector<gf2m> m_Linv; + std::vector<u32bit> m_coeffs; + + u32bit m_codimension; + u32bit m_dimension; }; /** * Estimate work factor for McEliece * @return estimated security level for these key parameters */ -BOTAN_DLL size_t mceliece_work_factor(size_t code_size, size_t k, size_t t); +BOTAN_DLL size_t mceliece_work_factor(size_t code_size, size_t t); } - #endif diff --git a/src/lib/pubkey/mce/mceliece_key.cpp b/src/lib/pubkey/mce/mceliece_key.cpp index 8cda0af89..8edbbf88a 100644 --- a/src/lib/pubkey/mce/mceliece_key.cpp +++ b/src/lib/pubkey/mce/mceliece_key.cpp @@ -9,15 +9,12 @@ * */ -#include <botan/mceliece_key.h> -#include <botan/internal/bit_ops.h> -#include <botan/gf2m_small_m.h> #include <botan/mceliece.h> -#include <botan/internal/code_based_key_gen.h> -#include <botan/code_based_util.h> +#include <botan/internal/mce_internal.h> +#include <botan/internal/bit_ops.h> +#include <botan/internal/code_based_util.h> #include <botan/der_enc.h> #include <botan/ber_dec.h> -#include <botan/workfactor.h> namespace Botan { @@ -42,12 +39,29 @@ McEliece_PrivateKey::McEliece_PrivateKey(RandomNumberGenerator& rng, size_t code *this = generate_mceliece_key(rng, ext_deg, code_length, t); } -unsigned McEliece_PublicKey::get_message_word_bit_length() const +u32bit McEliece_PublicKey::get_message_word_bit_length() const { u32bit codimension = ceil_log2(m_code_length) * m_t; return m_code_length - codimension; } +secure_vector<byte> McEliece_PublicKey::random_plaintext_element(RandomNumberGenerator& rng) const + { + const size_t bits = get_message_word_bit_length(); + + secure_vector<byte> plaintext((bits+7)/8); + rng.randomize(plaintext.data(), plaintext.size()); + + // unset unused bits in the last plaintext byte + if(u32bit used = bits % 8) + { + const byte mask = (1 << used) - 1; + plaintext[plaintext.size() - 1] &= mask; + } + + return plaintext; + } + AlgorithmIdentifier McEliece_PublicKey::algorithm_identifier() const { return AlgorithmIdentifier(get_oid(), std::vector<byte>()); @@ -55,16 +69,15 @@ AlgorithmIdentifier McEliece_PublicKey::algorithm_identifier() const std::vector<byte> McEliece_PublicKey::x509_subject_public_key() const { - // encode the public key - return unlock(DER_Encoder() - .start_cons(SEQUENCE) - .start_cons(SEQUENCE) - .encode(static_cast<size_t>(get_code_length())) - .encode(static_cast<size_t>(get_t())) - .end_cons() - .encode(m_public_matrix, OCTET_STRING) - .end_cons() - .get_contents()); + return DER_Encoder() + .start_cons(SEQUENCE) + .start_cons(SEQUENCE) + .encode(static_cast<size_t>(get_code_length())) + .encode(static_cast<size_t>(get_t())) + .end_cons() + .encode(m_public_matrix, OCTET_STRING) + .end_cons() + .get_contents_unlocked(); } McEliece_PublicKey::McEliece_PublicKey(const McEliece_PublicKey & other) : @@ -76,9 +89,7 @@ McEliece_PublicKey::McEliece_PublicKey(const McEliece_PublicKey & other) : size_t McEliece_PublicKey::estimated_strength() const { - const u32bit ext_deg = ceil_log2(m_code_length); - const size_t k = m_code_length - ext_deg * m_t; - return mceliece_work_factor(m_code_length, k, m_t); + return mceliece_work_factor(m_code_length, m_t); } McEliece_PublicKey::McEliece_PublicKey(const std::vector<byte>& key_bits) @@ -135,19 +146,20 @@ secure_vector<byte> McEliece_PrivateKey::pkcs8_private_key() const bool McEliece_PrivateKey::check_key(RandomNumberGenerator& rng, bool) const { - McEliece_Private_Operation priv_op(*this); - McEliece_Public_Operation pub_op(*this, get_code_length()); + const secure_vector<byte> plaintext = this->random_plaintext_element(rng); - secure_vector<byte> plaintext((this->get_message_word_bit_length()+7)/8); - rng.randomize(plaintext.data(), plaintext.size() - 1); - const secure_vector<gf2m> err_pos = create_random_error_positions(this->get_code_length(), this->get_t(), rng); + secure_vector<byte> ciphertext; + secure_vector<byte> errors; + mceliece_encrypt(ciphertext, errors, plaintext, *this, rng); - mceliece_message_parts parts(err_pos, plaintext, this->get_code_length()); - secure_vector<byte> message_and_error_input = parts.get_concat(); - secure_vector<byte> ciphertext = pub_op.encrypt(message_and_error_input.data(), message_and_error_input.size(), rng); - secure_vector<byte> message_and_error_output = priv_op.decrypt(ciphertext.data(), ciphertext.size()); + secure_vector<byte> plaintext_out; + secure_vector<byte> errors_out; + mceliece_decrypt(plaintext_out, errors_out, ciphertext, *this); - return (message_and_error_input == message_and_error_output); + if(errors != errors_out || plaintext != plaintext_out) + return false; + + return true; } McEliece_PrivateKey::McEliece_PrivateKey(const secure_vector<byte>& key_bits) @@ -172,7 +184,7 @@ McEliece_PrivateKey::McEliece_PrivateKey(const secure_vector<byte>& key_bits) m_codimension = (ext_deg * t); m_dimension = (n - m_codimension); - std::shared_ptr<gf2m_small_m::Gf2m_Field> sp_field(new gf2m_small_m::Gf2m_Field(ext_deg)); + std::shared_ptr<GF2m_Field> sp_field(new GF2m_Field(ext_deg)); m_g = polyn_gf2m(g_enc, sp_field); if(m_g.get_degree() != static_cast<int>(t)) { @@ -231,7 +243,6 @@ McEliece_PrivateKey::McEliece_PrivateKey(const secure_vector<byte>& key_bits) } - bool McEliece_PrivateKey::operator==(const McEliece_PrivateKey & other) const { if(*static_cast<const McEliece_PublicKey*>(this) != *static_cast<const McEliece_PublicKey*>(&other)) diff --git a/src/lib/pubkey/mce/mceliece_key.h b/src/lib/pubkey/mce/mceliece_key.h deleted file mode 100644 index 65ab04f16..000000000 --- a/src/lib/pubkey/mce/mceliece_key.h +++ /dev/null @@ -1,126 +0,0 @@ -/** - * (C) Copyright Projet SECRET, INRIA, Rocquencourt - * (C) Bhaskar Biswas and Nicolas Sendrier - * - * (C) 2014 cryptosource GmbH - * (C) 2014 Falko Strenzke [email protected] - * - * Botan is released under the Simplified BSD License (see license.txt) - * - */ - -#ifndef BOTAN_MCELIECE_KEY_H__ -#define BOTAN_MCELIECE_KEY_H__ - -#include <botan/exceptn.h> -#include <botan/pk_keys.h> -#include <botan/polyn_gf2m.h> - -namespace Botan { - -class BOTAN_DLL McEliece_PublicKey : public virtual Public_Key - { - public: - - McEliece_PublicKey(const std::vector<byte>& key_bits); - - McEliece_PublicKey(std::vector<byte> const& pub_matrix, u32bit the_t, u32bit the_code_length) : - m_public_matrix(pub_matrix), - m_t(the_t), - m_code_length(the_code_length) - {} - - McEliece_PublicKey(const McEliece_PublicKey & other); - - std::string algo_name() const override { return "McEliece"; } - - /** - * Get the maximum number of bits allowed to be fed to this key. - * This is the bitlength of the order of the base point. - * @result the maximum number of input bits - */ - size_t max_input_bits() const override - { - return get_message_word_bit_length(); - }; - - AlgorithmIdentifier algorithm_identifier() const override; - - size_t estimated_strength() const override; - - std::vector<byte> x509_subject_public_key() const override; - - bool check_key(RandomNumberGenerator&, bool) const override - { return true; } - - u32bit get_t() const { return m_t; } - u32bit get_code_length() const { return m_code_length; } - u32bit get_message_word_bit_length() const; - std::vector<byte> const& get_public_matrix() const { return m_public_matrix; } - - bool operator==(const McEliece_PublicKey& other) const; - bool operator!=(const McEliece_PublicKey& other) const { return !(*this == other); } - - protected: - McEliece_PublicKey() {} - - std::vector<byte> m_public_matrix; - u32bit m_t; - u32bit m_code_length; - }; - -class BOTAN_DLL McEliece_PrivateKey : public virtual McEliece_PublicKey, - public virtual Private_Key - { - public: - /** - * Get the maximum number of bits allowed to be fed to this key. - * This is the bitlength of the order of the base point. - * @result the maximum number of input bits - */ - size_t max_input_bits() const override { - return m_Linv.size(); - }; - - McEliece_PrivateKey(const secure_vector<byte>& key_bits); - - McEliece_PrivateKey(polyn_gf2m const& goppa_polyn, - std::vector<u32bit> const& parity_check_matrix_coeffs, - std::vector<polyn_gf2m> const& square_root_matrix, - std::vector<gf2m> const& inverse_support, - std::vector<byte> const& public_matrix ); - - McEliece_PrivateKey(RandomNumberGenerator& rng, size_t code_length, size_t t); - bool check_key(RandomNumberGenerator& rng, bool strong) const override; - - polyn_gf2m const& get_goppa_polyn() const { return m_g; }; - std::vector<u32bit> const& get_H_coeffs() const { return m_coeffs; }; - std::vector<gf2m> const& get_Linv() const { return m_Linv; }; - std::vector<polyn_gf2m> const& get_sqrtmod() const { return m_sqrtmod; }; - - inline u32bit get_dimension() const - { return m_dimension; }; - - inline u32bit get_codimension() const - { return m_codimension; }; - - - secure_vector<byte> pkcs8_private_key() const override; - - bool operator==(const McEliece_PrivateKey & other) const; - - bool operator!=(const McEliece_PrivateKey& other) const { return !(*this == other); }; - - private: - polyn_gf2m m_g; - std::vector<polyn_gf2m> m_sqrtmod; - std::vector<gf2m> m_Linv; - std::vector<u32bit> m_coeffs; - - u32bit m_codimension; - u32bit m_dimension; - }; - -} - -#endif diff --git a/src/lib/pubkey/mce/polyn_gf2m.cpp b/src/lib/pubkey/mce/polyn_gf2m.cpp index 70404c57c..4d9bcf2e8 100644 --- a/src/lib/pubkey/mce/polyn_gf2m.cpp +++ b/src/lib/pubkey/mce/polyn_gf2m.cpp @@ -10,15 +10,13 @@ */ #include <botan/polyn_gf2m.h> -#include <botan/gf2m_rootfind_dcmp.h> -#include <botan/code_based_util.h> -#include <botan/gf2m_small_m.h> +#include <botan/internal/code_based_util.h> #include <botan/internal/bit_ops.h> +#include <botan/rng.h> +#include <botan/exceptn.h> namespace Botan { -using namespace Botan::gf2m_small_m; - namespace { gf2m generate_gf2m_mask(gf2m a) @@ -40,8 +38,6 @@ unsigned nlz_16bit(u16bit x) } } -using namespace Botan::gf2m_small_m; - int polyn_gf2m::calc_degree_secure() const { int i = this->coeff.size() - 1; @@ -86,7 +82,7 @@ polyn_gf2m::polyn_gf2m(polyn_gf2m const& other) msp_field(other.msp_field) { } -polyn_gf2m::polyn_gf2m( int d, std::shared_ptr<gf2m_small_m::Gf2m_Field> sp_field) +polyn_gf2m::polyn_gf2m( int d, std::shared_ptr<GF2m_Field> sp_field) :m_deg(-1), coeff(d+1), msp_field(sp_field) @@ -115,7 +111,7 @@ void polyn_gf2m::realloc(u32bit new_size) this->coeff = secure_vector<gf2m>(new_size); } -polyn_gf2m::polyn_gf2m(const byte* mem, u32bit mem_len, std::shared_ptr<gf2m_small_m::Gf2m_Field> sp_field) +polyn_gf2m::polyn_gf2m(const byte* mem, u32bit mem_len, std::shared_ptr<GF2m_Field> sp_field) :msp_field(sp_field) { if(mem_len % sizeof(gf2m)) @@ -128,7 +124,7 @@ polyn_gf2m::polyn_gf2m(const byte* mem, u32bit mem_len, std::shared_ptr<gf2m_sma this->m_deg = -1; for(u32bit i = 0; i < size; i++) { - this->coeff[i] = gf2m_small_m::decode_gf2m(mem); + this->coeff[i] = decode_gf2m(mem); mem += sizeof(this->coeff[0]); } for(u32bit i = 0; i < size; i++) @@ -142,13 +138,13 @@ polyn_gf2m::polyn_gf2m(const byte* mem, u32bit mem_len, std::shared_ptr<gf2m_sma } -polyn_gf2m::polyn_gf2m( std::shared_ptr<gf2m_small_m::Gf2m_Field> sp_field ) +polyn_gf2m::polyn_gf2m( std::shared_ptr<GF2m_Field> sp_field ) : m_deg(-1), coeff(1), msp_field(sp_field) {} -polyn_gf2m::polyn_gf2m(int degree, const unsigned char* mem, u32bit mem_byte_len, std::shared_ptr<gf2m_small_m::Gf2m_Field> sp_field) +polyn_gf2m::polyn_gf2m(int degree, const unsigned char* mem, u32bit mem_byte_len, std::shared_ptr<GF2m_Field> sp_field) :msp_field(sp_field) { u32bit j, k, l; @@ -229,7 +225,7 @@ int polyn_gf2m::get_degree() const } -static gf2m eval_aux(const gf2m * /*restrict*/ coeff, gf2m a, int d, std::shared_ptr<gf2m_small_m::Gf2m_Field> sp_field) +static gf2m eval_aux(const gf2m * /*restrict*/ coeff, gf2m a, int d, std::shared_ptr<GF2m_Field> sp_field) { gf2m b; b = coeff[d--]; @@ -255,7 +251,7 @@ gf2m polyn_gf2m::eval(gf2m a) void polyn_gf2m::remainder(polyn_gf2m &p, const polyn_gf2m & g) { int i, j, d; - std::shared_ptr<gf2m_small_m::Gf2m_Field> msp_field = g.msp_field; + std::shared_ptr<GF2m_Field> msp_field = g.msp_field; d = p.get_degree() - g.get_degree(); if (d >= 0) { gf2m la = msp_field->gf_inv_rn(g.get_lead_coef()); @@ -314,7 +310,7 @@ polyn_gf2m polyn_gf2m::sqmod( const std::vector<polyn_gf2m> & sq, int d) { int i, j; gf2m la; - std::shared_ptr<gf2m_small_m::Gf2m_Field> sp_field = this->msp_field; + std::shared_ptr<GF2m_Field> sp_field = this->msp_field; polyn_gf2m result(d - 1, sp_field); // terms of low degree @@ -438,7 +434,7 @@ void polyn_gf2m::patchup_deg_secure( u32bit trgt_deg, volatile gf2m patch_elem) std::pair<polyn_gf2m, polyn_gf2m> polyn_gf2m::eea_with_coefficients( const polyn_gf2m & p, const polyn_gf2m & g, int break_deg) { - std::shared_ptr<gf2m_small_m::Gf2m_Field> msp_field = g.msp_field; + std::shared_ptr<GF2m_Field> msp_field = g.msp_field; int i, j, dr, du, delta; gf2m a; polyn_gf2m aux; @@ -625,7 +621,7 @@ std::pair<polyn_gf2m, polyn_gf2m> polyn_gf2m::eea_with_coefficients( const polyn return std::make_pair(u1,r1); // coefficients u,v } -polyn_gf2m::polyn_gf2m(int t, Botan::RandomNumberGenerator& rng, std::shared_ptr<gf2m_small_m::Gf2m_Field> sp_field) +polyn_gf2m::polyn_gf2m(int t, Botan::RandomNumberGenerator& rng, std::shared_ptr<GF2m_Field> sp_field) :m_deg(t), coeff(t+1), msp_field(sp_field) @@ -655,7 +651,7 @@ void polyn_gf2m::poly_shiftmod( const polyn_gf2m & g) { throw Invalid_Argument("shiftmod cannot be called on polynomials of degree 0 or less"); } - std::shared_ptr<gf2m_small_m::Gf2m_Field> msp_field = g.msp_field; + std::shared_ptr<GF2m_Field> msp_field = g.msp_field; t = g.get_degree(); a = msp_field->gf_div(this->coeff[t-1], g.coeff[t]); @@ -670,7 +666,7 @@ std::vector<polyn_gf2m> polyn_gf2m::sqrt_mod_init(const polyn_gf2m & g) { u32bit i, t; u32bit nb_polyn_sqrt_mat; - std::shared_ptr<gf2m_small_m::Gf2m_Field> msp_field = g.msp_field; + std::shared_ptr<GF2m_Field> msp_field = g.msp_field; std::vector<polyn_gf2m> result; t = g.get_degree(); nb_polyn_sqrt_mat = t/2; @@ -717,7 +713,7 @@ std::vector<polyn_gf2m> syndrome_init(polyn_gf2m const& generator, std::vector<g gf2m a; - std::shared_ptr<gf2m_small_m::Gf2m_Field> msp_field = generator.msp_field; + std::shared_ptr<GF2m_Field> msp_field = generator.msp_field; std::vector<polyn_gf2m> result; t = generator.get_degree(); @@ -744,7 +740,7 @@ std::vector<polyn_gf2m> syndrome_init(polyn_gf2m const& generator, std::vector<g return result; } -polyn_gf2m::polyn_gf2m(const secure_vector<byte>& encoded, std::shared_ptr<gf2m_small_m::Gf2m_Field> sp_field ) +polyn_gf2m::polyn_gf2m(const secure_vector<byte>& encoded, std::shared_ptr<GF2m_Field> sp_field ) :msp_field(sp_field) { if(encoded.size() % 2) diff --git a/src/lib/pubkey/mce/polyn_gf2m.h b/src/lib/pubkey/mce/polyn_gf2m.h index 6ec028a25..1c8cc5211 100644 --- a/src/lib/pubkey/mce/polyn_gf2m.h +++ b/src/lib/pubkey/mce/polyn_gf2m.h @@ -12,14 +12,14 @@ #ifndef BOTAN_POLYN_GF2M_H__ #define BOTAN_POLYN_GF2M_H__ +#include <botan/secmem.h> #include <botan/gf2m_small_m.h> -#include <botan/rng.h> #include <memory> #include <utility> namespace Botan { -using namespace gf2m_small_m; +class RandomNumberGenerator; struct polyn_gf2m { @@ -27,13 +27,13 @@ struct polyn_gf2m /** * create a zero polynomial: */ - polyn_gf2m( std::shared_ptr<gf2m_small_m::Gf2m_Field> sp_field ); + polyn_gf2m( std::shared_ptr<GF2m_Field> sp_field ); polyn_gf2m() :m_deg(-1) {}; - polyn_gf2m(const secure_vector<byte>& encoded, std::shared_ptr<gf2m_small_m::Gf2m_Field> sp_field ); + polyn_gf2m(const secure_vector<byte>& encoded, std::shared_ptr<GF2m_Field> sp_field ); polyn_gf2m& operator=(const polyn_gf2m&) = default; @@ -61,7 +61,7 @@ struct polyn_gf2m /** * create zero polynomial with reservation of space for a degree d polynomial */ - polyn_gf2m(int d, std::shared_ptr<gf2m_small_m::Gf2m_Field> sp_field); + polyn_gf2m(int d, std::shared_ptr<GF2m_Field> sp_field); polyn_gf2m(polyn_gf2m const& other); /** @@ -71,9 +71,9 @@ struct polyn_gf2m /** * random irreducible polynomial of degree t */ - polyn_gf2m(int t, RandomNumberGenerator& rng, std::shared_ptr<gf2m_small_m::Gf2m_Field> sp_field); + polyn_gf2m(int t, RandomNumberGenerator& rng, std::shared_ptr<GF2m_Field> sp_field); - std::shared_ptr<gf2m_small_m::Gf2m_Field> get_sp_field() const + std::shared_ptr<GF2m_Field> get_sp_field() const { return msp_field; }; gf2m& operator[](size_t i) { return coeff[i]; }; @@ -97,12 +97,12 @@ struct polyn_gf2m std::string to_string() const; /** decode a polynomial from memory: **/ - polyn_gf2m(const byte* mem, u32bit mem_len, std::shared_ptr<gf2m_small_m::Gf2m_Field> sp_field); + polyn_gf2m(const byte* mem, u32bit mem_len, std::shared_ptr<GF2m_Field> sp_field); // remove one! ^v! /** * create a polynomial from memory area (encoded) */ - polyn_gf2m(int degree, const unsigned char* mem, u32bit mem_byte_len, std::shared_ptr<gf2m_small_m::Gf2m_Field> sp_field); + polyn_gf2m(int degree, const unsigned char* mem, u32bit mem_byte_len, std::shared_ptr<GF2m_Field> sp_field); void encode(u32bit min_numo_coeffs, byte* mem, u32bit mem_len) const; @@ -149,13 +149,19 @@ struct polyn_gf2m public: int m_deg; secure_vector<gf2m> coeff; - std::shared_ptr<gf2m_small_m::Gf2m_Field> msp_field; + std::shared_ptr<GF2m_Field> msp_field; }; gf2m random_code_element(unsigned code_length, RandomNumberGenerator& rng); std::vector<polyn_gf2m> syndrome_init(polyn_gf2m const& generator, std::vector<gf2m> const& support, int n); +/** +* Find the roots of a polynomial over GF(2^m) using the method by Federenko +* et al. +*/ +secure_vector<gf2m> find_roots_gf2m_decomp(const polyn_gf2m & polyn, u32bit code_length); + } #endif diff --git a/src/lib/pubkey/mce/workfactor.cpp b/src/lib/pubkey/mce/workfactor.cpp index e7cf631d4..9594c0aab 100644 --- a/src/lib/pubkey/mce/workfactor.cpp +++ b/src/lib/pubkey/mce/workfactor.cpp @@ -8,6 +8,7 @@ */ #include <botan/mceliece.h> +#include <botan/internal/bit_ops.h> #include <cmath> namespace Botan { @@ -91,8 +92,10 @@ double best_wf(size_t n, size_t k, size_t w, size_t p) } -size_t mceliece_work_factor(size_t n, size_t k, size_t t) +size_t mceliece_work_factor(size_t n, size_t t) { + const size_t k = n - ceil_log2(n) * t; + double min = cout_total(n, k, t, 0, 0); // correspond a p=1 for(size_t p = 0; p != t / 2; ++p) { diff --git a/src/lib/pubkey/mceies/mceies.cpp b/src/lib/pubkey/mceies/mceies.cpp index 58dde2e27..d4d956a54 100644 --- a/src/lib/pubkey/mceies/mceies.cpp +++ b/src/lib/pubkey/mceies/mceies.cpp @@ -31,9 +31,10 @@ secure_vector<byte> aead_key(const secure_vector<byte>& mk, secure_vector<byte> mceies_encrypt(const McEliece_PublicKey& pubkey, - const secure_vector<byte>& pt, - byte ad[], size_t ad_len, - RandomNumberGenerator& rng) + const byte pt[], size_t pt_len, + const byte ad[], size_t ad_len, + RandomNumberGenerator& rng, + const std::string& algo) { McEliece_KEM_Encryptor kem_op(pubkey); @@ -45,7 +46,6 @@ mceies_encrypt(const McEliece_PublicKey& pubkey, BOTAN_ASSERT(mce_ciphertext.size() == mce_code_bytes, "Unexpected size"); - const std::string algo = "AES-256/OCB"; std::unique_ptr<AEAD_Mode> aead(get_aead(algo, ENCRYPTION)); if(!aead) throw std::runtime_error("mce_encrypt unable to create AEAD instance '" + algo + "'"); @@ -57,10 +57,10 @@ mceies_encrypt(const McEliece_PublicKey& pubkey, const secure_vector<byte> nonce = rng.random_vec(nonce_len); - secure_vector<byte> msg(mce_ciphertext.size() + nonce.size() + pt.size()); + secure_vector<byte> msg(mce_ciphertext.size() + nonce.size() + pt_len); copy_mem(msg.data(), mce_ciphertext.data(), mce_ciphertext.size()); copy_mem(msg.data() + mce_ciphertext.size(), nonce.data(), nonce.size()); - copy_mem(msg.data() + mce_ciphertext.size() + nonce.size(), pt.data(), pt.size()); + copy_mem(msg.data() + mce_ciphertext.size() + nonce.size(), pt, pt_len); aead->start(nonce); aead->finish(msg, mce_ciphertext.size() + nonce.size()); @@ -69,8 +69,9 @@ mceies_encrypt(const McEliece_PublicKey& pubkey, secure_vector<byte> mceies_decrypt(const McEliece_PrivateKey& privkey, - const secure_vector<byte>& ct, - byte ad[], size_t ad_len) + const byte ct[], size_t ct_len, + const byte ad[], size_t ad_len, + const std::string& algo) { try { @@ -78,23 +79,21 @@ mceies_decrypt(const McEliece_PrivateKey& privkey, const size_t mce_code_bytes = (privkey.get_code_length() + 7) / 8; - - const std::string algo = "AES-256/OCB"; std::unique_ptr<AEAD_Mode> aead(get_aead(algo, DECRYPTION)); if(!aead) throw std::runtime_error("Unable to create AEAD instance '" + algo + "'"); const size_t nonce_len = aead->default_nonce_length(); - if(ct.size() < mce_code_bytes + nonce_len + aead->tag_size()) + if(ct_len < mce_code_bytes + nonce_len + aead->tag_size()) throw std::runtime_error("Input message too small to be valid"); - const secure_vector<byte> mce_key = kem_op.decrypt(ct.data(), mce_code_bytes); + const secure_vector<byte> mce_key = kem_op.decrypt(ct, mce_code_bytes); aead->set_key(aead_key(mce_key, *aead)); aead->set_associated_data(ad, ad_len); - secure_vector<byte> pt(ct.begin() + mce_code_bytes + nonce_len, ct.end()); + secure_vector<byte> pt(ct + mce_code_bytes + nonce_len, ct + ct_len); aead->start(&ct[mce_code_bytes], nonce_len); aead->finish(pt, 0); diff --git a/src/lib/pubkey/mceies/mceies.h b/src/lib/pubkey/mceies/mceies.h index 9ead21a17..b43e2065f 100644 --- a/src/lib/pubkey/mceies/mceies.h +++ b/src/lib/pubkey/mceies/mceies.h @@ -23,9 +23,10 @@ class McEliece_PrivateKey; */ secure_vector<byte> BOTAN_DLL mceies_encrypt(const McEliece_PublicKey& pubkey, - const secure_vector<byte>& pt, - byte ad[], size_t ad_len, - RandomNumberGenerator& rng); + const byte pt[], size_t pt_len, + const byte ad[], size_t ad_len, + RandomNumberGenerator& rng, + const std::string& aead = "AES-256/OCB"); /** * McEliece Integrated Encryption System @@ -34,8 +35,9 @@ BOTAN_DLL mceies_encrypt(const McEliece_PublicKey& pubkey, */ secure_vector<byte> BOTAN_DLL mceies_decrypt(const McEliece_PrivateKey& privkey, - const secure_vector<byte>& ct, - byte ad[], size_t ad_len); + const byte ct[], size_t ct_len, + const byte ad[], size_t ad_len, + const std::string& aead = "AES-256/OCB"); } diff --git a/src/lib/pubkey/pk_algs.cpp b/src/lib/pubkey/pk_algs.cpp index 75264d56f..689237a84 100644 --- a/src/lib/pubkey/pk_algs.cpp +++ b/src/lib/pubkey/pk_algs.cpp @@ -48,6 +48,10 @@ #include <botan/curve25519.h> #endif +#if defined(BOTAN_HAS_MCELIECE) + #include <botan/mceliece.h> +#endif + namespace Botan { Public_Key* make_public_key(const AlgorithmIdentifier& alg_id, @@ -107,6 +111,11 @@ Public_Key* make_public_key(const AlgorithmIdentifier& alg_id, return new Curve25519_PublicKey(alg_id, key_bits); #endif +#if defined(BOTAN_HAS_MCELIECE) + if(alg_name == "McEliece") + return new McEliece_PublicKey(unlock(key_bits)); +#endif + throw Decoding_Error("Unhandled PK algorithm " + alg_name); } @@ -168,6 +177,11 @@ Private_Key* make_private_key(const AlgorithmIdentifier& alg_id, return new Curve25519_PrivateKey(alg_id, key_bits, rng); #endif +#if defined(BOTAN_HAS_MCELIECE) + if(alg_name == "McEliece") + return new McEliece_PrivateKey(key_bits); +#endif + throw Decoding_Error("Unhandled PK algorithm " + alg_name); } diff --git a/src/lib/rng/hmac_drbg/hmac_drbg.cpp b/src/lib/rng/hmac_drbg/hmac_drbg.cpp index 22236c0cb..ad731b6b3 100644 --- a/src/lib/rng/hmac_drbg/hmac_drbg.cpp +++ b/src/lib/rng/hmac_drbg/hmac_drbg.cpp @@ -23,12 +23,12 @@ HMAC_DRBG::HMAC_DRBG(MessageAuthenticationCode* mac, HMAC_DRBG::HMAC_DRBG(const std::string& mac_name, RandomNumberGenerator* prng) : m_prng(prng), - m_V(m_mac->output_length(), 0x01), m_reseed_counter(0) { m_mac = MessageAuthenticationCode::create(mac_name); if(!m_mac) throw Algorithm_Not_Found(mac_name); + m_V = secure_vector<byte>(m_mac->output_length(), 0x01), m_mac->set_key(std::vector<byte>(m_mac->output_length(), 0x00)); } diff --git a/src/tests/data/pubkey/mce.vec b/src/tests/data/pubkey/mce.vec new file mode 100644 index 000000000..44817949b --- /dev/null +++ b/src/tests/data/pubkey/mce.vec @@ -0,0 +1,58 @@ + +McElieceSeed = C9A3649B5AC1AAFCE2E15B8C74FB0F2C776B10AB6C52F69AEB70700341479428 +KeyN = 1632 +KeyT = 33 +PublicKeyFingerprint = 2F5C0F9FF3E46D40E21AA4165B63DE2780F424438F9106D9C798801B7FAD05F5 +PrivateKeyFingerprint = 89AFCE27857051AF842A58FC903324414470AB0876A9FB8F739FB43485823CD9 +EncryptPRNGSeed = AABF99BAD11411A430D0AA2940148EE67D77DC44BE8734DA4A8B274561CBA2EC +SharedKey = A656D63F7FC8EF345AFBEE89B121BF5E45D301C5F5FF17DCDB227D84F22CF3D9DED9B00F5495B81CA41789549691BF4D6CF3E7069857E1CBFE9D63855949A89A +Ciphertext = E053B0773BDADE3C7625E108CC0B3746C36386E283F931970B7F4FE39F24498248458891A7843A843C4CAE3CAABB4CD0A80B1F944685A09CFFD944BFC9E41473769B8310E0BEED9E6C174E3C1E8A9E84A54C3120B5440B1F0F669830FAABA53FA2F00FD45CBC0522E647A5CDDC9135E805A88DCFB97ECAEEA2FF9577B2319F3828FB31C7D6470850DEC5B919FF5F3DC21C0BEC42DFADFDDE2675E03380222A480D0002B1C9D70F6C0A6D8F452FC556EDA9753C71BDC2DD530CE3314AB515F5118AD338A2165ED13DE0626707 + +McElieceSeed = C9A3649B5AC1AAFCE2E15B8C74FB0F2C776B10AB6C52F69AEB70700341479429 +KeyN = 2480 +KeyT = 45 +PublicKeyFingerprint = DDAC6EDF03B982E85FD60414E6C608F88694BB0C0FCCE99FCB044838E0C9CC9D +PrivateKeyFingerprint = 1949DFF555144AA0E2ED17CB4A3C71F4D7EEC1CCD9A3199D11E49BCA7FC81E4E +EncryptPRNGSeed = AABF99BAD11411A430D0AA2940148EE67D77DC44BE8734DA4A8B274561CBA2ED +SharedKey = 8F533C41E820EB0A6763FCC6AA88FE4FFFB2BAB1567639E8DB0E239CC4F595A1C6041B4EE3362D332A87FD81B9A81E413D4168CF67AE50519D2E5E698990CB0D +Ciphertext = 0CADE39676249382B1216579A4E4825325E13BE3198EDF913C4F35911DB3DD7CAE7D42158A9DC7599E2324B04A164E247BD5EA0CCDF964955AFF150561FB8CBB8A3FD712CEA114699FA2CEBC2CE837B1115D3E93819BBBB01785007B5380421266D8C3D2B802C8A4ECD5207EC675FFDBD8499A344E29E781A4E15C973D03130819D9B238A2596F68A59ED6628E49FE4ABEBAA5A0D4EACDA4DF1816F1C82F44025A2734FCE26FB7592B0BADF4D9FEDFAB37D54F2CA92D65A876D0E0F18A2FB586A80BD647D465190290FD856B1A8EED967BD77CD1637FD11655D1B135591A2D52B2D83E4A48B5777BB18D0E4D5E6392875AF9CF13B36AB4BBAE80073C8740B4987C3B28AC7778CFE6CDCE5E1ACBB05BB9E142B7C2239E1A41152F3617052D6EF96186CB6C2B4F684438CBA4F59954465466CD67E4457F + + +McElieceSeed = C9A3649B5AC1AAFCE2E15B8C74FB0F2C776B10AB6C52F69AEB70700341479430 +KeyN = 2960 +KeyT = 57 +PublicKeyFingerprint = 05707644DAE98856D432C24C19C41CDA333E36C04C81413E2D15E88EE129B4F7 +PrivateKeyFingerprint = 7BA1FEDF2E520945EC0321CE84F2A07B8407FFEC42EC715839AC0941BA1E9404 +EncryptPRNGSeed = AABF99BAD11411A430D0AA2940148EE67D77DC44BE8734DA4A8B274561CBA2EF +SharedKey = DEDFB2DBA755E94AD609F1DCA7F81D4BC5A39A4E07BF108D88A031F9E4CD2F46708EF1F9FDD27AAE56318928A5D89FA16C5F7F8D6ABF8019B549139E25142D2B +Ciphertext = AD9D75F29BD735082E95611DD8C1B9897FB35ABBA968AE8C66E99CECB679BB19344369404E73BA5C6549A8BFA25A2C3F90D3DC3C82E3B06815B0F02E013B3A9FB8EA9C38FEC8C61E58D260989D774DE0DBC8AE27A4C0B2AEAAC2EF43589A2F66D07FDA9B288C5F9DE5E9A59EB00A4C0A69581F7997830BAA9C6D77816DD78D574AD7BD732EA5A7F44E31FE6A30E4CC34896EB45D16C5227F3E31E1F3185614F5157F4D2B3A4B765BC9E3C24EC6D0AF02EDDDED78FB3874F0DAF7FF960FFF7E9445EEBE049200A43412AE99E16CB11BC7BD86BD61A0DB0402092E1D77153E24B5855D736125FDAE5957FBB79F7A5488CF53912681C80E58AF5DA31326A525342A60FAFD1B06E350A01209F7F77FCA2D66B13F17EC8880247F1B975F70A3CC96B5B90F418DE14D445BFC4897FAAFF52931306E84980B23F5D632AF0437AFBD4E6AF672B51AA2862BBDA3340EE77F2FDC4BEE06DB41592136549B55721CDD14FE06F475175EA15598EC65274B02D7D183A66622 + +McElieceSeed = C9A3649B5AC1AAFCE2E15B8C74FB0F2C776B10AB6C52F69AEB70700341479431 +KeyN = 3408 +KeyT = 67 +PublicKeyFingerprint = 87D94945188A898EFE3F62DDBB083DED2FAF74D83614F811DEE44ED1195B8DD4 +PrivateKeyFingerprint = D774748F55B9678D21A4234CF4141C073F5A389D52B64497E517EEE447B1762C +EncryptPRNGSeed = AABF99BAD11411A430D0AA2940148EE67D77DC44BE8734DA4A8B274561CBA2EF +SharedKey = E958F5A7EC2E284927BA6678169343359FE0768F9D1B2C0BDABA2D6E22FBD46BAE9C9FF0DA8238D2AAF9A125CC60F2FC757C47987850293934303D206DFBE06C +Ciphertext = AD9D75F09BD635082EB5611DD9C1E9897FB35E33E168AE0C66E9DCECA679BB19344369484E73AA5E6549A8BFA25A2C5F90D3D43C82E3B4681790F02E017B3A8FB8EA9C38FEC8C60E58D270989F774DE0DB48AE37A4C0B28EAAC2EF43589A0F66D07F5A9B2888DF9DE5E9A59EB00A4C0A6B581F7997838BAA9C6D67814DD68D574AD7BD732EA5A7F44C31FE6E30E4CC34896EB47D5685227F3E31C1D35A5614F5157F4D6B324B7E59C9E3C34CC6D0AF02EDDCEF78FB3874F2DAF7FF9607FF7E9445EEBE049210A53412AF99C16CB11BC7BD8EBD61A0FB0402896F1D57153E243585DD7B6125FDBE5957FBB79F7A5488CF13952681C00E59AF5DA31326A525142A60FAFD5B06E350A41209F7F77FC22D66B12F13EC8A80207B1B975F70F26A400CCCFC8A4AE20053EF1F8A3E7D2099AFE09A5812D50191461CABADE85E2249BFC78509CD45655AA1CBDF37707634F95A3818629AB4BA13AA3C2D78937CD05B38AFA01FADD1E7C558A5BEA03A022E7A61A7CCEDF3F78C12C888DFF3442033797CCECDC6A7006BFA1E5F17F23E4396DD5E18A324394E30A4B508D511E55C14DD89296085904E280D1E71970E + +McElieceSeed = 31C9A3649B5AC1AAFCE2E15B8C74FB0F2C776B10AB6C52F69AEB707003414794 +KeyN = 4624 +KeyT = 95 +PublicKeyFingerprint = E37CF72DE6ECD0E540316C1F4BC6F0391983D4E7B60C8ED13DCA801EEFA9A4E9 +PrivateKeyFingerprint = CDD13DFD3B067DE0A50D37C7CE97CF30E5024CDEF6A20043C09F81219B14B03E +EncryptPRNGSeed = CCBF99BAD11411A430D0AA2940148EE67D77DC44BE8734DA4A8B274561CBA22E +SharedKey = 8102784D063499813404A5FBEE50D64122E2C46217C9BAA76AE9021479B0E36D026809C8AEE2443772CEA7C13335017F9825E8BBA67D13786930C474771673FB +Ciphertext = BE6802091325EF912BC47FC694A0E26F015700F5987C057A70F2D984D3FF589FD6A3DC541912AF4DEA19F6A1C155972578CEA9F5C3A5AD02F85E28E5667FF129222A9585B85FD25A956A572487FBF3B62BBB0A96D360336D4DCBBBD194FC352837028C97F63C6BEBAC5D76A36968DD384F9F884594566E833AB87A8B9EEE5AA0CC9F0D45BE5E61C98C57DD52487F7EFD0AB085EB6D2DA652F7F1BAF6700EA52265412DBA0098B8055C82A46A43C7E89734371ADFB0FFD24D450BE5CE2477BC79BB2F6D85017289C582576AB95CCA9D3B10C4C60111AC9CEDE47294F476CEEF7611A189A5866151A6BA5EB6C362FB6F5A32CF930EFD9ED0CBD110D47060330AB71D9AB00403BF1CF7CDACFA2B1F373FF11B05E3820C93F6BD9D118161A585587A91AF356EF8254CD4CC2CEED87DE3724DDD5F2BDCFB0B75D230779A0D9E4AED49D630ACCFEC81DBF94064A21197BAC57AFFB2D82A637F36F7E64B7336B98288C65EAF18E37B0F8C06457BDA61FA3931480296BB32AACCECEC08E0FF6705352EA69BF12E64C1E6F837E857465148174915E1F1E7714739BED8133FB638ACC6F0D49392080B9E54E7386B430F6BC06DE38C2C92C351B7FCD7F247CB793DBB4E9430F8184C50213C02A9B32B7034A6E30B59CEEFCFA57DB0FE122F7B5A1B9D3EB290BCA9FDB9A2DF9C1638CE3AD84CA2267613D503F210A1A23E5B98B1CE1314FACDBC9C2D45278C312F9CC1A00CFC5086676ED2E9A67965F23D157C350DCFFD98511A4853F3BE54F5109B3D9C98EBB6558E14A427BE6AC73158454E5DDFA402CA3C2E45 + +McElieceSeed = 31C9A3649B5AC1AAFCE2E15B8C74FB0F2C776B10AB6C52F69AEB707003414795 +KeyN = 6624 +KeyT = 115 +PublicKeyFingerprint = 29A7BE3A3181534ABD5FF006EB8D5CCE71FDD27E0FD62E774A3C75C20BE84268 +PrivateKeyFingerprint = AA75AFB38ADA856FBEE6C973D53DF0AD07395C54AE83805BE59D57112A9EF6A3 +EncryptPRNGSeed = CCBF99BAD11411A430D0AA2940148EE67D77DC44BE8734DA4A8B274561CBA22F +SharedKey = F50F3E58A4788C03C44DBDE2C61ACC97A7CA8ADC6CC1D371416A7D6250BB3DD7526C55E666C9FCA31ADC5FA79CBEF72AA24B5BDC5F2E7AD255A0091A0DB7D127 +Ciphertext = 4A69DFA02182A20C59FD3D1291D110749C4BA57F38CE66D90485588C2CC4E1548180E9CBB58517479B978DF62A9B4E583D2D1C9BA3E61EDCF4D0249C54160E8547B8A91C5A2FE0E00FE95EF18FC865BFCD39EEE81DD79CAC36885AD2454FCFF4AB740CABD34563E08FA203FF96CEEF5E4FBA43DEC6C316E503B033DD4034F0E432DF646833603EEB8693843727F9F007CD78300A434BD379AA64BC1E1A04282C0BC23ACC6316DBC4919EFD123E4C87BF45F56E43C440453F85F93B014AEEB36CA0DCF9A7543C16C47625057B22A5E6E5681E3C2919225466DF16A32D32D475DF842E4D85C23DD9BD49BAC8D759B96FCBA00086095B7E3CCA2FD30AB884948003CDD64FD1E68AA7B36B2B740BAE029794193284AA4C1CF6DFC2916D2EA1AA20B64A81EEEF815456E260B77DC20C900F874E47962B0995E33A0832ED458EABDAE495B21178EDCBD3A973668E9C8F171139168B1AC442A387C9AA3D1ED9A6583A807BBCBF1A1A94E04B7638695D6F0C09F18B0732A2B5F4111C0D5F84E2F175280DE43525AEE72C036932927B3DDC4FD526B9DBD117C9CD37D64B0F77C103644FD7073977BB69F7367417E79D6A901686DB00E8E7C16C889E566CFB44D1C66E9C84251CB9CAFFB6FCA9B88999B08F8EC6203DEAF668E86689621D5BD56A1FB89623E2388FC93A92F9269ED2ADB70BC92E5F77D1DFE8805039F71A8132535110D1F1E4384BD2C21817DBB7D03DD88035D154106E2E3F7E1C3D4BD15C7F5AE469AC8BD016F98C9B01A66B8D8A0F72C7C9C176C2AEDC967B9AB4FCBF0FD99D0BEF8B151B224DCDA3691885414BC36B3707D2C97D44EE9F83A4F2F194E57533B16FBE673176E1FFC21C9F9A35AB35BDF94B9FDDDA179D035AA282DEE80DBC55489C6DE676C2B6D24790CCC15044AE952CACE8E7B4AA75C51632ACB52F75EE6A660979C46E89354C92C1FE60BDB7140BAAF7D22CAB8FC8865A1FA070416A28FEF51262E27E5F7C06CB46D68682BF2731014BB17CD18940563818EBA720A85A78E08491E7379E071A7B92253DF2BF6A8C14473D7247B81CBD565057BBF45116F1AD2045C6685257C39B12764DD0AAF8A9857D35960E41E44985DA2CC4E4A06D26157E01BAC866E40A3C1B28DED234129B89DEE47A2E22724F766876E6986B8C65 + + + diff --git a/src/tests/test_gf2m.cpp b/src/tests/test_gf2m.cpp new file mode 100644 index 000000000..7557672a6 --- /dev/null +++ b/src/tests/test_gf2m.cpp @@ -0,0 +1,46 @@ +/* +* (C) 2015 Jack Lloyd +* +* Botan is released under the Simplified BSD License (see license.txt) +*/ + +#include "tests.h" + +#if defined(BOTAN_HAS_MCELIECE) + +#include <botan/gf2m_small_m.h> + +BOTAN_TEST_CASE(gf2m, "GF(2^m)", { + + using namespace Botan; + + for(size_t degree = 2; degree <= 16; ++degree) + { + GF2m_Field field(degree); + + for(size_t i = 0; i <= field.gf_ord(); ++i) + { + gf2m a = i; + + BOTAN_TEST(field.gf_square(a), field.gf_mul(a, a), "Square and multiply"); + + /* + * This sequence is from the start of gf2m_decomp_rootfind_state::calc_Fxj_j_neq_0 + */ + { + const gf2m jl_gray = field.gf_l_from_n(a); + gf2m xl_j_tt_5 = field.gf_square_rr(jl_gray); + const gf2m xl_gray_tt_3 = field.gf_mul_rrr(xl_j_tt_5, jl_gray); + xl_j_tt_5 = field.gf_mul_rrr(xl_j_tt_5, xl_gray_tt_3); + gf2m s = field.gf_mul_nrr(xl_gray_tt_3, field.gf_ord()); + BOTAN_CONFIRM(s <= field.gf_ord(), "Less than order"); + } + } + } + }); + +#else + +SKIP_TEST(gf2m); + +#endif diff --git a/src/tests/test_mce.cpp b/src/tests/test_mce.cpp new file mode 100644 index 000000000..dbe5cc046 --- /dev/null +++ b/src/tests/test_mce.cpp @@ -0,0 +1,104 @@ +/* +* (C) 2015 Jack Lloyd +* +* Botan is released under the Simplified BSD License (see license.txt) +*/ + +#include "tests.h" + +#if defined(BOTAN_HAS_MCELIECE) + +#include <botan/mceliece.h> +#include <botan/mce_kem.h> +#include <botan/hmac_drbg.h> +#include <botan/hash.h> +#include <botan/hex.h> +#include <iostream> +#include <fstream> + +using namespace Botan; + +namespace { + +std::string hash_bytes(const byte b[], size_t len) + { + std::unique_ptr<HashFunction> hash(HashFunction::create("SHA-256")); + hash->update(b, len); + return hex_encode(hash->final()); + } + +template<typename A> +std::string hash_bytes(const std::vector<byte, A>& v) + { + return hash_bytes(v.data(), v.size()); + } + +size_t mce_test(const std::string& key_seed_hex, + size_t n, size_t t, + const std::string& exp_fingerprint_pub, + const std::string& exp_fingerprint_priv, + const std::string& encrypt_rng_seed_hex, + const std::string& ct_hex, + const std::string& shared_key_hex) + { + const secure_vector<byte> keygen_seed = hex_decode_locked(key_seed_hex); + const secure_vector<byte> encrypt_seed = hex_decode_locked(encrypt_rng_seed_hex); + + Test_State _test; + + HMAC_DRBG rng("HMAC(SHA-384)"); + + rng.add_entropy(keygen_seed.data(), keygen_seed.size()); + + McEliece_PrivateKey mce_priv(rng, n, t); + + const std::string f_pub = hash_bytes(mce_priv.x509_subject_public_key()); + const std::string f_priv = hash_bytes(mce_priv.pkcs8_private_key()); + + BOTAN_TEST(f_pub, exp_fingerprint_pub, "Public fingerprint"); + BOTAN_TEST(f_priv, exp_fingerprint_priv, "Private fingerprint"); + + rng.clear(); + rng.add_entropy(encrypt_seed.data(), encrypt_seed.size()); + + McEliece_KEM_Encryptor kem_enc(mce_priv); + McEliece_KEM_Decryptor kem_dec(mce_priv); + + const std::pair<secure_vector<byte>,secure_vector<byte> > ciphertext__sym_key = kem_enc.encrypt(rng); + const secure_vector<byte>& ciphertext = ciphertext__sym_key.first; + const secure_vector<byte>& sym_key_encr = ciphertext__sym_key.second; + + const secure_vector<byte> sym_key_decr = kem_dec.decrypt(ciphertext.data(), ciphertext.size()); + + BOTAN_TEST(ct_hex, hex_encode(ciphertext), "Ciphertext"); + BOTAN_TEST(hex_encode(sym_key_encr), shared_key_hex, "Encrypted key"); + BOTAN_TEST(hex_encode(sym_key_decr), shared_key_hex, "Decrypted key"); + + return _test.failed(); + } + +} + +size_t test_mce() + { + + std::ifstream vec(TEST_DATA_DIR "/pubkey/mce.vec"); + return run_tests_bb(vec, "McElieceSeed", "Ciphertext", true, + [](std::map<std::string, std::string> m) -> size_t + { + return mce_test(m["McElieceSeed"], + to_u32bit(m["KeyN"]), + to_u32bit(m["KeyT"]), + m["PublicKeyFingerprint"], + m["PrivateKeyFingerprint"], + m["EncryptPRNGSeed"], + m["Ciphertext"], + m["SharedKey"]); + }); + } + +#else + +SKIP_TEST(mce); + +#endif diff --git a/src/tests/test_mceliece.cpp b/src/tests/test_mceliece.cpp index 29f11edd7..0ed62b5ea 100644 --- a/src/tests/test_mceliece.cpp +++ b/src/tests/test_mceliece.cpp @@ -13,6 +13,7 @@ #include <botan/pubkey.h> #include <botan/oids.h> #include <botan/mceliece.h> +#include <botan/internal/code_based_util.h> #include <botan/mce_kem.h> #include <botan/loadstor.h> #include <botan/hex.h> @@ -32,35 +33,6 @@ namespace { const size_t MCE_RUNS = 5; -size_t test_mceliece_message_parts(RandomNumberGenerator& rng, size_t code_length, size_t error_weight) - { - secure_vector<gf2m> err_pos1 = create_random_error_positions(code_length, error_weight, rng); - secure_vector<byte> message1((code_length+7)/8); - rng.randomize(message1.data(), message1.size() - 1); - mceliece_message_parts parts1(err_pos1, message1, code_length); - secure_vector<byte> err_vec1 = parts1.get_error_vector(); - - secure_vector<byte> concat1 = parts1.get_concat(); - - mceliece_message_parts parts2( concat1.data(), concat1.size(), code_length); - - secure_vector<byte> err_vec2 = parts2.get_error_vector(); - if(err_vec1 != err_vec2) - { - std::cout << "error with error vector from message parts" << std::endl; - return 1; - } - - secure_vector<byte> message2 = parts2.get_message_word(); - if(message1 != message2) - { - std::cout << "error with message word from message parts" << std::endl; - return 1; - } - - return 0; - } - size_t test_mceliece_kem(const McEliece_PrivateKey& sk, const McEliece_PublicKey& pk, RandomNumberGenerator& rng) @@ -83,50 +55,26 @@ size_t test_mceliece_kem(const McEliece_PrivateKey& sk, std::cout << "mce KEM test failed, error during encryption/decryption" << std::endl; ++fails; } - -#if 0 - // takes a long time: - for(size_t j = 0; j < code_length; j++) - { - // flip the j-th bit in the ciphertext - secure_vector<byte> wrong_ct(ciphertext); - size_t byte_pos = j/8; - size_t bit_pos = j % 8; - wrong_ct[byte_pos] ^= 1 << bit_pos; - try - { - secure_vector<byte> decrypted = priv_op.decrypt(wrong_ct.data(), wrong_ct.size()); - } - catch(const Integrity_Failure) - { - continue; - } - std::cout << "manipulation in ciphertext not detected" << std::endl; - err_cnt++; - } -#endif - } return fails; } +/* size_t test_mceliece_raw(const McEliece_PrivateKey& sk, const McEliece_PublicKey& pk, RandomNumberGenerator& rng) { const size_t code_length = pk.get_code_length(); McEliece_Private_Operation priv_op(sk); - McEliece_Public_Operation pub_op(pk, code_length); + McEliece_Public_Operation pub_op(pk); size_t err_cnt = 0; for(size_t i = 0; i != MCE_RUNS; i++) { - secure_vector<byte> plaintext((pk.get_message_word_bit_length()+7)/8); - rng.randomize(plaintext.data(), plaintext.size() - 1); + const secure_vector<byte> plaintext = pk.random_plaintext_element(rng); secure_vector<gf2m> err_pos = create_random_error_positions(code_length, pk.get_t(), rng); - mceliece_message_parts parts(err_pos, plaintext, code_length); secure_vector<byte> message_and_error_input = parts.get_concat(); secure_vector<byte> ciphertext = pub_op.encrypt(message_and_error_input.data(), message_and_error_input.size(), rng); @@ -157,6 +105,7 @@ size_t test_mceliece_raw(const McEliece_PrivateKey& sk, return err_cnt; } +*/ #if defined(BOTAN_HAS_MCEIES) size_t test_mceies(const McEliece_PrivateKey& sk, @@ -172,8 +121,8 @@ size_t test_mceies(const McEliece_PrivateKey& sk, const size_t ad_len = sizeof(ad); const secure_vector<byte> pt = rng.random_vec(rng.next_byte()); - const secure_vector<byte> ct = mceies_encrypt(pk, pt, ad, ad_len, rng); - const secure_vector<byte> dec = mceies_decrypt(sk, ct, ad, ad_len); + const secure_vector<byte> ct = mceies_encrypt(pk, pt.data(), pt.size(), ad, ad_len, rng); + const secure_vector<byte> dec = mceies_decrypt(sk, ct.data(), ct.size(), ad, ad_len); if(pt != dec) { @@ -194,7 +143,7 @@ size_t test_mceies(const McEliece_PrivateKey& sk, try { - mceies_decrypt(sk, bad_ct, ad, ad_len); + mceies_decrypt(sk, bad_ct.data(), bad_ct.size(), ad, ad_len); std::cout << "Successfully decrypted manipulated ciphertext!" << std::endl; ++fails; } @@ -231,18 +180,7 @@ size_t test_mceliece() size_t code_length = params__n__t_min_max[i]; for(size_t t = params__n__t_min_max[i+1]; t <= params__n__t_min_max[i+2]; t++) { - //std::cout << "testing parameters n = " << code_length << ", t = " << t << std::endl; - - try - { - fails += test_mceliece_message_parts(rng, code_length, t); - } - catch(std::exception& e) - { - std::cout << e.what() << std::endl; - fails++; - } - tests += 1; + std::cout << "testing parameters n = " << code_length << ", t = " << t << std::endl; McEliece_PrivateKey sk1(rng, code_length, t); const McEliece_PublicKey& pk1 = sk1; @@ -273,17 +211,6 @@ size_t test_mceliece() try { - fails += test_mceliece_raw(sk, pk, rng); - } - catch(std::exception& e) - { - std::cout << e.what() << std::endl; - fails++; - } - tests += 1; - - try - { fails += test_mceliece_kem(sk, pk, rng); } catch(std::exception& e) diff --git a/src/tests/tests.cpp b/src/tests/tests.cpp index 763417209..d213b6a3a 100644 --- a/src/tests/tests.cpp +++ b/src/tests/tests.cpp @@ -301,7 +301,9 @@ int main(int argc, char* argv[]) DEF_TEST(ecdsa); DEF_TEST(gost_3410); DEF_TEST(curve25519); + DEF_TEST(gf2m); DEF_TEST(mceliece); + DEF_TEST(mce); DEF_TEST(ecc_unit); DEF_TEST(ecc_randomized); diff --git a/src/tests/tests.h b/src/tests/tests.h index 14ec5a17b..6d6a2d34c 100644 --- a/src/tests/tests.h +++ b/src/tests/tests.h @@ -142,7 +142,9 @@ size_t test_ecc_random(); size_t test_ecdsa(); size_t test_gost_3410(); size_t test_curve25519(); +size_t test_gf2m(); size_t test_mceliece(); +size_t test_mce(); // One off tests size_t test_ocb(); |