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 #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 }