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