Botan  1.11.15
src/lib/pubkey/mce/gf2m_small_m.h
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 
00012 #ifndef BOTAN_GF2M_SMALL_M_H__
00013 #define BOTAN_GF2M_SMALL_M_H__
00014 
00015 #include <vector>
00016 #include <botan/types.h>
00017 
00018 namespace Botan {
00019 
00020 namespace gf2m_small_m {
00021 
00022 typedef u16bit gf2m;
00023 
00024 class Gf2m_Field
00025    {
00026    public:
00027       Gf2m_Field(size_t extdeg);
00028 
00029       gf2m gf_mul(gf2m x, gf2m y)
00030          {
00031          return ((x) ? gf_mul_fast(x, y) : 0);
00032          }
00033 
00034       gf2m gf_square(gf2m x)
00035          {
00036          return ((x) ? m_gf_exp_table[_gf_modq_1(m_gf_log_table[x] << 1)] : 0);
00037          }
00038 
00039       gf2m square_rr(gf2m x)
00040          {
00041          return _gf_modq_1(x << 1);
00042          }
00043 
00044       // naming convention of GF(2^m) field operations:
00045       // l logarithmic, unreduced
00046       // r logarithmic, reduced
00047       // n normal, non-zero
00048       // z normal, might be zero
00049       //
00050       inline gf2m gf_mul_lll(gf2m a, gf2m b);
00051       inline gf2m gf_mul_rrr(gf2m a, gf2m b);
00052       inline gf2m gf_mul_nrr(gf2m a, gf2m b);
00053       inline gf2m gf_mul_rrn(gf2m a, gf2m y);
00054       inline gf2m gf_mul_lnn(gf2m x, gf2m y);
00055       inline gf2m gf_mul_rnn(gf2m x, gf2m y);
00056       inline gf2m gf_mul_nrn(gf2m a, gf2m y);
00057       inline gf2m gf_mul_rnr(gf2m y, gf2m a);
00058       inline gf2m gf_mul_zrz(gf2m a, gf2m y);
00059       inline gf2m gf_mul_zzr(gf2m a, gf2m y);
00060       inline gf2m gf_mul_nnr(gf2m y, gf2m a);
00061       inline gf2m gf_sqrt(gf2m x) ;
00062       gf2m gf_div(gf2m x, gf2m y);
00063       inline gf2m gf_div_rnn(gf2m x, gf2m y);
00064       inline gf2m gf_div_rnr(gf2m x, gf2m b);
00065       inline gf2m gf_div_nrr(gf2m a, gf2m b);
00066       inline gf2m gf_div_zzr(gf2m x, gf2m b);
00067       inline gf2m gf_inv(gf2m x);
00068       inline gf2m gf_inv_rn(gf2m x);
00069       inline gf2m gf_square_ln(gf2m x);
00070       inline gf2m gf_square_rr(gf2m a) ;
00071       inline gf2m gf_l_from_n(gf2m x);
00072 
00073       inline gf2m gf_mul_fast(gf2m a, gf2m b);
00074 
00075       gf2m gf_exp(gf2m i)
00076          {
00077          return m_gf_exp_table[i]; /* alpha^i */
00078          }
00079 
00080       gf2m gf_log(gf2m i)
00081          {
00082          return m_gf_log_table[i]; /* return i when x=alpha^i */
00083          }
00084 
00085       inline gf2m gf_ord() const
00086          {
00087          return m_gf_multiplicative_order;
00088          }
00089 
00090       inline gf2m get_extension_degree() const
00091          {
00092          return m_gf_extension_degree;
00093          }
00094 
00095       inline gf2m get_cardinality() const
00096          {
00097          return m_gf_cardinality;
00098          }
00099 
00100       gf2m gf_pow(gf2m x, int i) ;
00101 
00102    private:
00103       gf2m m_gf_extension_degree, m_gf_cardinality, m_gf_multiplicative_order;
00104       std::vector<gf2m> m_gf_log_table;
00105       std::vector<gf2m> m_gf_exp_table;
00106 
00107       inline gf2m _gf_modq_1(s32bit d);
00108       void init_log();
00109       void init_exp();
00110    };
00111 
00112 gf2m Gf2m_Field::_gf_modq_1(s32bit d)
00113    {
00114    return  (((d) & gf_ord()) + ((d) >> m_gf_extension_degree));
00115    }
00116 
00117 gf2m Gf2m_Field::gf_mul_fast(gf2m x, gf2m y)
00118    {
00119    return ((y) ? m_gf_exp_table[_gf_modq_1(m_gf_log_table[x] + m_gf_log_table[y])] : 0);
00120    }
00121 
00122 gf2m Gf2m_Field::gf_mul_lll(gf2m a, gf2m b)
00123    {
00124    return  (a + b);
00125    }
00126 
00127 gf2m Gf2m_Field::gf_mul_rrr(gf2m a, gf2m b)
00128    {
00129    return (_gf_modq_1(gf_mul_lll(a, b)));
00130    }
00131 
00132 gf2m Gf2m_Field::gf_mul_nrr(gf2m a, gf2m b)
00133    {
00134    return (gf_exp(gf_mul_rrr(a, b)));
00135    }
00136 
00137 gf2m Gf2m_Field::gf_mul_rrn(gf2m a, gf2m y)
00138    {
00139    return _gf_modq_1(gf_mul_lll(a, gf_log(y)));
00140    }
00141 
00142 gf2m Gf2m_Field::gf_mul_rnr(gf2m y, gf2m a)
00143    {
00144    return gf_mul_rrn(a, y);
00145    }
00146 
00147 gf2m Gf2m_Field::gf_mul_lnn(gf2m x, gf2m y)
00148    {
00149    return (m_gf_log_table[x] + m_gf_log_table[y]);
00150    }
00151 gf2m Gf2m_Field::gf_mul_rnn(gf2m x, gf2m y)
00152    {
00153    return _gf_modq_1(gf_mul_lnn(x, y));
00154    }
00155 
00156 gf2m Gf2m_Field::gf_mul_nrn(gf2m a, gf2m y)
00157    {
00158    return m_gf_exp_table[_gf_modq_1((a) + m_gf_log_table[y])];
00159    }
00160 
00161 /**
00162 * zero operand allowed
00163 */
00164 gf2m Gf2m_Field::gf_mul_zrz(gf2m a, gf2m y)
00165    {
00166    return ( (y == 0) ? 0 : gf_mul_nrn(a, y) );
00167    }
00168 
00169 gf2m Gf2m_Field::gf_mul_zzr(gf2m a, gf2m y)
00170    {
00171    return gf_mul_zrz(y, a);
00172    }
00173 /**
00174 * non-zero operand
00175 */
00176 gf2m Gf2m_Field::gf_mul_nnr(gf2m y, gf2m a)
00177    {
00178    return gf_mul_nrn( a, y);
00179    }
00180 
00181 gf2m Gf2m_Field::gf_sqrt(gf2m x)
00182    {
00183    return ((x) ? m_gf_exp_table[_gf_modq_1(m_gf_log_table[x] << (m_gf_extension_degree-1))] : 0);
00184    }
00185 
00186 gf2m Gf2m_Field::gf_div_rnn(gf2m x, gf2m y)
00187    {
00188    return _gf_modq_1(m_gf_log_table[x] - m_gf_log_table[y]);
00189    }
00190 gf2m Gf2m_Field::gf_div_rnr(gf2m x, gf2m b)
00191    {
00192    return _gf_modq_1(m_gf_log_table[x] - b);
00193    }
00194 gf2m Gf2m_Field::gf_div_nrr(gf2m a, gf2m b)
00195    {
00196    return m_gf_exp_table[_gf_modq_1(a - b)];
00197    }
00198 
00199 gf2m Gf2m_Field::gf_div_zzr(gf2m x, gf2m b)
00200    {
00201    return ((x) ? m_gf_exp_table[_gf_modq_1(m_gf_log_table[x] - b)] : 0);
00202    }
00203 
00204 gf2m Gf2m_Field::gf_inv(gf2m x)
00205    {
00206    return m_gf_exp_table[gf_ord() - m_gf_log_table[x]];
00207    }
00208 gf2m Gf2m_Field::gf_inv_rn(gf2m x)
00209    {
00210    return (gf_ord() - m_gf_log_table[x]);
00211    }
00212 
00213 gf2m Gf2m_Field::gf_square_ln(gf2m x)
00214    {
00215    return m_gf_log_table[x] << 1;
00216    }
00217 
00218 gf2m Gf2m_Field::gf_square_rr(gf2m a)
00219    {
00220    return a << 1;
00221    }
00222 
00223 gf2m Gf2m_Field::gf_l_from_n(gf2m x)
00224    {
00225    return m_gf_log_table[x];
00226    }
00227 
00228 u32bit encode_gf2m(gf2m to_enc, byte* mem);
00229 
00230 gf2m decode_gf2m(const byte* mem);
00231 
00232 }
00233 
00234 }
00235 
00236 #endif