diff options
| -rw-r--r-- | src/cmd/speed_pk.cpp | 5 | ||||
| -rw-r--r-- | src/lib/pubkey/mce/mceliece.h | 6 | ||||
| -rw-r--r-- | src/lib/pubkey/mce/mceliece_key.cpp | 4 | ||||
| -rw-r--r-- | src/lib/pubkey/mce/workfactor.cpp | 114 | ||||
| -rw-r--r-- | src/lib/pubkey/workfactor.cpp | 5 | ||||
| -rw-r--r-- | src/lib/pubkey/workfactor.h | 6 |
6 files changed, 125 insertions, 15 deletions
diff --git a/src/cmd/speed_pk.cpp b/src/cmd/speed_pk.cpp index 141248d7d..6d20065cc 100644 --- a/src/cmd/speed_pk.cpp +++ b/src/cmd/speed_pk.cpp @@ -682,8 +682,6 @@ void benchmark_mce(RandomNumberGenerator& rng, Benchmark_Report& report) { const std::vector<std::pair<size_t, size_t>> params = { - { 256, 15 }, - { 512, 33 }, { 1024, 35 }, { 2048, 50 }, { 2960, 56 }, @@ -727,7 +725,8 @@ void benchmark_mce(RandomNumberGenerator& rng, std::ostringstream keysize_report; keysize_report << "(size " << pub_key.x509_subject_public_key().size() << " pub " - << priv_key.pkcs8_private_key().size() << " priv)"; + << priv_key.pkcs8_private_key().size() << " priv " + << pub_key.estimated_strength() << " work factor)"; report.report(nm + " " + keysize_report.str(), keygen_timer); report.report(nm, enc_timer); diff --git a/src/lib/pubkey/mce/mceliece.h b/src/lib/pubkey/mce/mceliece.h index ee5f8ab8f..6e6dffe02 100644 --- a/src/lib/pubkey/mce/mceliece.h +++ b/src/lib/pubkey/mce/mceliece.h @@ -143,6 +143,12 @@ class BOTAN_DLL McEliece_Public_Operation : public PK_Ops::Encryption u32bit m_code_length; }; +/** +* 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); + } diff --git a/src/lib/pubkey/mce/mceliece_key.cpp b/src/lib/pubkey/mce/mceliece_key.cpp index 7da5aefed..2b4a277ad 100644 --- a/src/lib/pubkey/mce/mceliece_key.cpp +++ b/src/lib/pubkey/mce/mceliece_key.cpp @@ -76,7 +76,9 @@ McEliece_PublicKey::McEliece_PublicKey(const McEliece_PublicKey & other) : size_t McEliece_PublicKey::estimated_strength() const { - return mceliece_work_factor(m_t, m_code_length); + 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); } McEliece_PublicKey::McEliece_PublicKey(const std::vector<byte>& key_bits) diff --git a/src/lib/pubkey/mce/workfactor.cpp b/src/lib/pubkey/mce/workfactor.cpp new file mode 100644 index 000000000..18eaf65e5 --- /dev/null +++ b/src/lib/pubkey/mce/workfactor.cpp @@ -0,0 +1,114 @@ +/** + * (C) Copyright Projet SECRET, INRIA, Rocquencourt + * (C) Bhaskar Biswas and Nicolas Sendrier + * + * Distributed under the terms of the Botan license + * + */ + +#include <botan/mceliece.h> +#include <cmath> + +namespace Botan { + +namespace { + +double binomial(size_t n, size_t k) + { + double x = 1; + + for(size_t i = 0; i != k; ++i) + { + x *= n - i; + x /= k -i; + } + + return x; + } + +double log_binomial(size_t n, size_t k) + { + double x = 0; + + for(size_t i = 0; i != k; ++i) + { + x += std::log(n - i); + x -= std::log(k - i); + } + + return x / std::log(2); + } + +double nb_iter(size_t n, size_t k, size_t w, size_t p, size_t l) + { + double x = 2 * log_binomial(k / 2, p); + x += log_binomial(n - k - l, w - 2 * p); + x = log_binomial(n, w) - x; + return x; + } + +double cout_iter(size_t n, size_t k, size_t p, size_t l) + { + // x <- binomial(k/2,p) + double x = binomial(k / 2, p); + // i <- log[2](binomial(k/2,p)) + size_t i = (size_t) (std::log(x) / std::log(2)); // normalement i < 2^31 + // res <- 2*p*(n-k-l)*binomial(k/2,p)^2/2^l + double res = 2 * p * (n - k - l) * ldexp(x * x, -l); + // x <- binomial(k/2,p)*2*(2*l+log[2](binomial(k/2,p))) + x *= 2 * (2 * l + i); + // res <- k*(n-k)/2 + + // binomial(k/2,p)*2*(2*l+log[2](binomial(k/2,p))) + + // 2*p*(n-k-l)*binomial(k/2,p)^2/2^l + res += x + k * ((n - k) / 2.0); + + return std::log(res) / std::log(2); + } + +double cout_total(size_t n, size_t k, size_t w, size_t p, size_t l) + { + return nb_iter(n, k, w, p, l) + cout_iter(n, k, p, l); + } + +double best_wf(size_t n, size_t k, size_t w, size_t p) + { + if(p >= k / 2) + return -1; + + // On part de l = u, en faisant croitre l. + // On s'arrète dés que le work factor croit. + // Puis on explore les valeurs <u, mais en tenant de la convexite' + + double min = cout_total(n, k, w, p, 0); + for(size_t l = 1; l < n - k; ++l) + { + double lwf = cout_total(n, k, w, p, l); + if(lwf < min) + { + min = lwf; + } + else + break; + } + + return min; + } + +} + +size_t mceliece_work_factor(size_t n, size_t k, size_t t) + { + double min = cout_total(n, k, t, 0, 0); // correspond a p=1 + for(size_t p = 0; p != t / 2; ++p) + { + double lwf = best_wf(n, k + 1, t, p); + if(lwf < 0) + break; + + min = std::min(min, lwf); + } + + return min; + } + +} diff --git a/src/lib/pubkey/workfactor.cpp b/src/lib/pubkey/workfactor.cpp index 972d03af9..5665c5269 100644 --- a/src/lib/pubkey/workfactor.cpp +++ b/src/lib/pubkey/workfactor.cpp @@ -11,11 +11,6 @@ namespace Botan { -size_t mceliece_work_factor(size_t code_size, size_t t) - { - return 0; - } - size_t ecp_work_factor(size_t bits) { return bits / 2; diff --git a/src/lib/pubkey/workfactor.h b/src/lib/pubkey/workfactor.h index 37f487234..ba81d61b4 100644 --- a/src/lib/pubkey/workfactor.h +++ b/src/lib/pubkey/workfactor.h @@ -26,12 +26,6 @@ size_t dl_work_factor(size_t prime_group_size); */ size_t ecp_work_factor(size_t prime_group_size); -/** -* Estimate work factor for McEliece -* @return estimated security level for this group -*/ -size_t mceliece_work_factor(size_t code_size, size_t t); - } #endif |