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
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
|
/*
* (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)
*
*/
#ifndef BOTAN_GF2M_SMALL_M_H_
#define BOTAN_GF2M_SMALL_M_H_
#include <botan/types.h>
#include <vector>
namespace Botan {
typedef uint16_t gf2m;
/**
* GF(2^m) field for m = [2...16]
*/
class BOTAN_TEST_API GF2m_Field
{
public:
explicit GF2m_Field(size_t extdeg);
gf2m gf_mul(gf2m x, gf2m y) const
{
return ((x) ? gf_mul_fast(x, y) : 0);
}
gf2m gf_square(gf2m x) const
{
return ((x) ? gf_exp(_gf_modq_1(gf_log(x) << 1)) : 0);
}
gf2m square_rr(gf2m x) const
{
return _gf_modq_1(x << 1);
}
gf2m gf_mul_fast(gf2m x, gf2m y) const
{
return ((y) ? gf_exp(_gf_modq_1(gf_log(x) + gf_log(y))) : 0);
}
/*
naming convention of GF(2^m) field operations:
l logarithmic, unreduced
r logarithmic, reduced
n normal, non-zero
z normal, might be zero
*/
gf2m gf_mul_lll(gf2m a, gf2m b) const
{
return (a + b);
}
gf2m gf_mul_rrr(gf2m a, gf2m b) const
{
return (_gf_modq_1(gf_mul_lll(a, b)));
}
gf2m gf_mul_nrr(gf2m a, gf2m b) const
{
return (gf_exp(gf_mul_rrr(a, b)));
}
gf2m gf_mul_rrn(gf2m a, gf2m y) const
{
return _gf_modq_1(gf_mul_lll(a, gf_log(y)));
}
gf2m gf_mul_rnr(gf2m y, gf2m a) const
{
return gf_mul_rrn(a, y);
}
gf2m gf_mul_lnn(gf2m x, gf2m y) const
{
return (gf_log(x) + gf_log(y));
}
gf2m gf_mul_rnn(gf2m x, gf2m y) const
{
return _gf_modq_1(gf_mul_lnn(x, y));
}
gf2m gf_mul_nrn(gf2m a, gf2m y) const
{
return gf_exp(_gf_modq_1((a) + gf_log(y)));
}
/**
* zero operand allowed
*/
gf2m gf_mul_zrz(gf2m a, gf2m y) const
{
return ( (y == 0) ? 0 : gf_mul_nrn(a, y) );
}
gf2m gf_mul_zzr(gf2m a, gf2m y) const
{
return gf_mul_zrz(y, a);
}
/**
* non-zero operand
*/
gf2m gf_mul_nnr(gf2m y, gf2m a) const
{
return gf_mul_nrn(a, y);
}
gf2m gf_sqrt(gf2m x) const
{
return ((x) ? gf_exp(_gf_modq_1(gf_log(x) << (get_extension_degree()-1))) : 0);
}
gf2m gf_div_rnn(gf2m x, gf2m y) const
{
return _gf_modq_1(gf_log(x) - gf_log(y));
}
gf2m gf_div_rnr(gf2m x, gf2m b) const
{
return _gf_modq_1(gf_log(x) - b);
}
gf2m gf_div_nrr(gf2m a, gf2m b) const
{
return gf_exp(_gf_modq_1(a - b));
}
gf2m gf_div_zzr(gf2m x, gf2m b) const
{
return ((x) ? gf_exp(_gf_modq_1(gf_log(x) - b)) : 0);
}
gf2m gf_inv(gf2m x) const
{
return gf_exp(gf_ord() - gf_log(x));
}
gf2m gf_inv_rn(gf2m x) const
{
return (gf_ord() - gf_log(x));
}
gf2m gf_square_ln(gf2m x) const
{
return gf_log(x) << 1;
}
gf2m gf_square_rr(gf2m a) const
{
return a << 1;
}
gf2m gf_l_from_n(gf2m x) const
{
return gf_log(x);
}
gf2m gf_div(gf2m x, gf2m y) const;
gf2m gf_exp(gf2m i) const
{
return m_gf_exp_table.at(i); /* alpha^i */
}
gf2m gf_log(gf2m i) const
{
return m_gf_log_table.at(i); /* return i when x=alpha^i */
}
gf2m gf_ord() const
{
return m_gf_multiplicative_order;
}
size_t get_extension_degree() const
{
return m_gf_extension_degree;
}
gf2m get_cardinality() const
{
return static_cast<gf2m>(1 << get_extension_degree());
}
private:
gf2m _gf_modq_1(int32_t d) const
{
/* residual modulo q-1
when -q < d < 0, we get (q-1+d)
when 0 <= d < q, we get (d)
when q <= d < 2q-1, we get (d-q+1)
*/
return static_cast<gf2m>(((d) & gf_ord()) + ((d) >> get_extension_degree()));
}
const size_t m_gf_extension_degree;
const gf2m m_gf_multiplicative_order;
const std::vector<gf2m>& m_gf_log_table;
const std::vector<gf2m>& m_gf_exp_table;
};
uint32_t encode_gf2m(gf2m to_enc, uint8_t* mem);
gf2m decode_gf2m(const uint8_t* mem);
}
#endif
|
