Botan  1.11.15
src/lib/pubkey/mce/gf2m_small_m.cpp
Go to the documentation of this file.
00001 /*
00002 * (C) Copyright Projet SECRET, INRIA, Rocquencourt
00003 * (C) Bhaskar Biswas and  Nicolas Sendrier
00004 *
00005 * (C) 2014 cryptosource GmbH
00006 * (C) 2014 Falko Strenzke fstrenzke@cryptosource.de
00007 *
00008 * Botan is released under the Simplified BSD License (see license.txt)
00009 */
00010 
00011 #include <botan/gf2m_small_m.h>
00012 #include <botan/code_based_util.h>
00013 #include <string>
00014 
00015 namespace Botan {
00016 
00017 namespace gf2m_small_m {
00018 
00019 #define MAX_EXT_DEG 16
00020 
00021 namespace {
00022 
00023 unsigned int prim_poly[MAX_EXT_DEG + 1] = {
00024    01,          /* extension degree 0 (!) never used */
00025    03,          /* extension degree 1 (!) never used */
00026    07,          /* extension degree 2 */
00027    013,                 /* extension degree 3 */
00028    023,                 /* extension degree 4 */
00029    045,                 /* extension degree 5 */
00030    0103,                /* extension degree 6 */
00031    0203,                /* extension degree 7 */
00032    0435,                /* extension degree 8 */
00033    01041,               /* extension degree 9 */
00034    02011,               /* extension degree 10 */
00035    04005,               /* extension degree 11 */
00036    010123,              /* extension degree 12 */
00037    020033,              /* extension degree 13 */
00038    042103,              /* extension degree 14 */
00039    0100003,             /* extension degree 15 */
00040    0210013              /* extension degree 16 */
00041 };
00042 
00043 }
00044 
00045 u32bit encode_gf2m(gf2m to_enc, byte* mem)
00046    {
00047    mem[0] = to_enc >> 8;
00048    mem[1] = to_enc & 0xFF;
00049    return sizeof(to_enc);
00050    }
00051 
00052 gf2m decode_gf2m(const byte* mem)
00053    {
00054    gf2m result;
00055    result = mem[0] << 8;
00056    result |= mem[1];
00057    return result;
00058    }
00059 
00060 // construct the table gf_exp[i]=alpha^i
00061 void Gf2m_Field::init_exp()
00062    {
00063    m_gf_exp_table.resize(1 << get_extension_degree());
00064 
00065    m_gf_exp_table[0] = 1;
00066    for(size_t i = 1; i < gf_ord(); ++i)
00067       {
00068       m_gf_exp_table[i] = m_gf_exp_table[i - 1] << 1;
00069       if (m_gf_exp_table[i - 1] & (1 << (get_extension_degree()-1)))
00070          {
00071          m_gf_exp_table[i] ^= prim_poly[get_extension_degree()];
00072          }
00073       }
00074 
00075    // hack for the multiplication
00076    m_gf_exp_table[gf_ord()] = 1;
00077    }
00078 
00079 // construct the table gf_log[alpha^i]=i
00080 void Gf2m_Field::init_log()
00081    {
00082    m_gf_log_table.resize(1 << get_extension_degree());
00083 
00084    m_gf_log_table[0] = gf_ord(); // log of 0 par convention
00085    for (size_t i = 0; i < gf_ord() ; ++i)
00086       {
00087       m_gf_log_table[m_gf_exp_table[i]] = i;
00088       }
00089    }
00090 
00091 
00092 Gf2m_Field::Gf2m_Field(size_t extdeg)
00093    {
00094    if(extdeg < 2 || extdeg > MAX_EXT_DEG)
00095       throw std::runtime_error("Gf2m_Field does not support degree " + std::to_string(extdeg));
00096 
00097    m_gf_extension_degree = extdeg;
00098    m_gf_cardinality = 1 << extdeg;
00099    m_gf_multiplicative_order = m_gf_cardinality - 1;
00100 
00101    init_exp();
00102    init_log();
00103    }
00104 
00105 gf2m Gf2m_Field::gf_div(gf2m x, gf2m y)
00106    {
00107    s32bit sub_res = static_cast<s32bit>(m_gf_log_table[x]) - static_cast<s32bit>( m_gf_log_table[y]);
00108    s32bit modq_res = static_cast<s32bit>(_gf_modq_1(sub_res));
00109    s32bit div_res = static_cast<s32bit>(x) ? static_cast<s32bit>(m_gf_exp_table[modq_res]) : 0;
00110    return static_cast<gf2m>(div_res);
00111    }
00112 
00113 // we suppose i >= 0. Par convention 0^0 = 1
00114 gf2m Gf2m_Field::gf_pow(gf2m x, int i)
00115    {
00116    if (i == 0)
00117       return 1;
00118    else if (x == 0)
00119       return 0;
00120    else
00121       {
00122       // i mod (q-1)
00123       while (i >> get_extension_degree())
00124          i = (i & (gf_ord())) + (i >> get_extension_degree());
00125       i *= m_gf_log_table[x];
00126       while (i >> get_extension_degree())
00127          i = (i & (gf_ord())) + (i >> get_extension_degree());
00128       return m_gf_exp_table[i];
00129       }
00130    }
00131 
00132 }
00133 
00134 }