1 /*
2 * (C) Copyright Projet SECRET, INRIA, Rocquencourt
3 * (C) Bhaskar Biswas and Nicolas Sendrier
4 *
5 * (C) 2014 cryptosource GmbH
6 * (C) 2014 Falko Strenzke fstrenzke@cryptosource.de
7 *
8 * Botan is released under the Simplified BSD License (see license.txt)
9 */
10
11 #include <botan/gf2m_small_m.h>
12 #include <botan/exceptn.h>
13 #include <string>
14
15 namespace Botan {
16
17 #define MAX_EXT_DEG 16
18
19 namespace {
20
21 gf2m prim_poly[MAX_EXT_DEG + 1] = {
22 01, /* extension degree 0 (!) never used */
23 03, /* extension degree 1 (!) never used */
24 07, /* extension degree 2 */
25 013, /* extension degree 3 */
26 023, /* extension degree 4 */
27 045, /* extension degree 5 */
28 0103, /* extension degree 6 */
29 0203, /* extension degree 7 */
30 0435, /* extension degree 8 */
31 01041, /* extension degree 9 */
32 02011, /* extension degree 10 */
33 04005, /* extension degree 11 */
34 010123, /* extension degree 12 */
35 020033, /* extension degree 13 */
36 042103, /* extension degree 14 */
37 0100003, /* extension degree 15 */
38 };
39
gf_exp_table(size_t deg,gf2m prime_poly)40 std::vector<gf2m> gf_exp_table(size_t deg, gf2m prime_poly)
41 {
42 // construct the table gf_exp[i]=alpha^i
43
44 std::vector<gf2m> tab((static_cast<size_t>(1) << deg) + 1);
45
46 tab[0] = 1;
47 for(size_t i = 1; i < tab.size(); ++i)
48 {
49 const gf2m overflow = tab[i-1] >> (deg - 1);
50 tab[i] = (tab[i-1] << 1) ^ (overflow * prime_poly);
51 }
52
53 return tab;
54 }
55
exp_table(size_t deg)56 const std::vector<gf2m>& exp_table(size_t deg)
57 {
58 static std::vector<gf2m> tabs[MAX_EXT_DEG + 1];
59
60 if(deg < 2 || deg > MAX_EXT_DEG)
61 throw Invalid_Argument("GF2m_Field does not support degree " + std::to_string(deg));
62
63 if(tabs[deg].empty())
64 tabs[deg] = gf_exp_table(deg, prim_poly[deg]);
65
66 return tabs[deg];
67 }
68
gf_log_table(size_t deg,const std::vector<gf2m> & exp)69 std::vector<gf2m> gf_log_table(size_t deg, const std::vector<gf2m>& exp)
70 {
71 std::vector<gf2m> tab(static_cast<size_t>(1) << deg);
72
73 tab[0] = static_cast<gf2m>((static_cast<gf2m>(1) << deg) - 1); // log of 0 is the order by convention
74 for(size_t i = 0; i < tab.size(); ++i)
75 {
76 tab[exp[i]] = static_cast<gf2m>(i);
77 }
78 return tab;
79 }
80
log_table(size_t deg)81 const std::vector<gf2m>& log_table(size_t deg)
82 {
83 static std::vector<gf2m> tabs[MAX_EXT_DEG + 1];
84
85 if(deg < 2 || deg > MAX_EXT_DEG)
86 throw Invalid_Argument("GF2m_Field does not support degree " + std::to_string(deg));
87
88 if(tabs[deg].empty())
89 tabs[deg] = gf_log_table(deg, exp_table(deg));
90
91 return tabs[deg];
92 }
93
94 }
95
encode_gf2m(gf2m to_enc,uint8_t * mem)96 uint32_t encode_gf2m(gf2m to_enc, uint8_t* mem)
97 {
98 mem[0] = to_enc >> 8;
99 mem[1] = to_enc & 0xFF;
100 return sizeof(to_enc);
101 }
102
decode_gf2m(const uint8_t * mem)103 gf2m decode_gf2m(const uint8_t* mem)
104 {
105 gf2m result;
106 result = mem[0] << 8;
107 result |= mem[1];
108 return result;
109 }
110
GF2m_Field(size_t extdeg)111 GF2m_Field::GF2m_Field(size_t extdeg) : m_gf_extension_degree(extdeg),
112 m_gf_multiplicative_order((1 << extdeg) - 1),
113 m_gf_log_table(log_table(m_gf_extension_degree)),
114 m_gf_exp_table(exp_table(m_gf_extension_degree))
115 {
116 }
117
gf_div(gf2m x,gf2m y) const118 gf2m GF2m_Field::gf_div(gf2m x, gf2m y) const
119 {
120 const int32_t sub_res = static_cast<int32_t>(gf_log(x) - static_cast<int32_t>(gf_log(y)));
121 const gf2m modq_res = _gf_modq_1(sub_res);
122 const int32_t div_res = static_cast<int32_t>(x) ? static_cast<int32_t>(gf_exp(modq_res)) : 0;
123 return static_cast<gf2m>(div_res);
124 }
125
126 }
127