aboutsummaryrefslogtreecommitdiffstats
path: root/src/lib/pubkey/mce/gf2m_small_m.cpp
diff options
context:
space:
mode:
authorJack Lloyd <[email protected]>2015-09-22 12:10:24 -0400
committerJack Lloyd <[email protected]>2015-09-29 17:57:50 -0400
commit2a6f5f10cc9713230bdd6204c57219451584f4a4 (patch)
tree804a78cbd34d69f01aed3a337fd4a693c59297bc /src/lib/pubkey/mce/gf2m_small_m.cpp
parentac9689990da914cd58788dab9d5e0d7bebb72e30 (diff)
McEliece cleanups
Remove and consolidate various headers Reduce memory usage of GF2m_Field by sharing the log and exponent tables across all instances of a particular word size. Remove McEliece_Public_Operation and McEliece_Private_Operation which were difficult to use safely. Instead only the KEM operations are exposed. Add McEliece_PublicKey::random_plaintext_element Add command line `mce` tool and some McEliece documentation Convert the speed program to check McEliece keys of the suggested size Add McEliece KATs for both key generation and KEM Fix HMAC_DRBG constructor which derefed a pointer before its time
Diffstat (limited to 'src/lib/pubkey/mce/gf2m_small_m.cpp')
-rw-r--r--src/lib/pubkey/mce/gf2m_small_m.cpp115
1 files changed, 63 insertions, 52 deletions
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);
}
}
}
-
-}