Botan
1.11.15
|
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