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
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
|
/**
* (C) Copyright Projet SECRET, INRIA, Rocquencourt
* (C) Bhaskar Biswas and Nicolas Sendrier
*
* (C) 2014 cryptosource GmbH
* (C) 2014 Falko Strenzke fstrenzke@cryptosource.de
*
* Distributed under the terms of the Botan license
*
*/
#ifndef BOTAN_GF2M_SMALL_M_H__
#define BOTAN_GF2M_SMALL_M_H__
#include <vector>
#include <botan/types.h>
namespace Botan {
namespace gf2m_small_m {
typedef u16bit gf2m;
class Gf2m_Field
{
public:
Gf2m_Field(size_t extdeg);
gf2m gf_mul(gf2m x, gf2m y)
{
return ((x) ? gf_mul_fast(x, y) : 0);
}
gf2m gf_square(gf2m x)
{
return ((x) ? m_gf_exp_table[_gf_modq_1(m_gf_log_table[x] << 1)] : 0);
}
gf2m square_rr(gf2m x)
{
return _gf_modq_1(x << 1);
}
// naming convention of GF(2^m) field operations:
// l logarithmic, unreduced
// r logarithmic, reduced
// n normal, non-zero
// z normal, might be zero
//
inline gf2m gf_mul_lll(gf2m a, gf2m b);
inline gf2m gf_mul_rrr(gf2m a, gf2m b);
inline gf2m gf_mul_nrr(gf2m a, gf2m b);
inline gf2m gf_mul_rrn(gf2m a, gf2m y);
inline gf2m gf_mul_lnn(gf2m x, gf2m y);
inline gf2m gf_mul_rnn(gf2m x, gf2m y);
inline gf2m gf_mul_nrn(gf2m a, gf2m y);
inline gf2m gf_mul_rnr(gf2m y, gf2m a);
inline gf2m gf_mul_zrz(gf2m a, gf2m y);
inline gf2m gf_mul_zzr(gf2m a, gf2m y);
inline gf2m gf_mul_nnr(gf2m y, gf2m a);
inline gf2m gf_sqrt(gf2m x) ;
gf2m gf_div(gf2m x, gf2m y);
inline gf2m gf_div_rnn(gf2m x, gf2m y);
inline gf2m gf_div_rnr(gf2m x, gf2m b);
inline gf2m gf_div_nrr(gf2m a, gf2m b);
inline gf2m gf_div_zzr(gf2m x, gf2m b);
inline gf2m gf_inv(gf2m x);
inline gf2m gf_inv_rn(gf2m x);
inline gf2m gf_square_ln(gf2m x);
inline gf2m gf_square_rr(gf2m a) ;
inline gf2m gf_l_from_n(gf2m x);
inline gf2m gf_mul_fast(gf2m a, gf2m b);
gf2m gf_exp(gf2m i)
{
return m_gf_exp_table[i]; /* alpha^i */
}
gf2m gf_log(gf2m i)
{
return m_gf_log_table[i]; /* return i when x=alpha^i */
}
inline gf2m gf_ord() const
{
return m_gf_multiplicative_order;
}
inline gf2m get_extension_degree() const
{
return m_gf_extension_degree;
}
inline gf2m get_cardinality() const
{
return m_gf_cardinality;
}
gf2m gf_pow(gf2m x, int i) ;
private:
gf2m m_gf_extension_degree, m_gf_cardinality, m_gf_multiplicative_order;
std::vector<gf2m> m_gf_log_table;
std::vector<gf2m> m_gf_exp_table;
inline gf2m _gf_modq_1(s32bit d);
void init_log();
void init_exp();
};
gf2m Gf2m_Field::_gf_modq_1(s32bit d)
{
return (((d) & gf_ord()) + ((d) >> m_gf_extension_degree));
}
gf2m Gf2m_Field::gf_mul_fast(gf2m x, gf2m y)
{
return ((y) ? m_gf_exp_table[_gf_modq_1(m_gf_log_table[x] + m_gf_log_table[y])] : 0);
}
gf2m Gf2m_Field::gf_mul_lll(gf2m a, gf2m b)
{
return (a + b);
}
gf2m Gf2m_Field::gf_mul_rrr(gf2m a, gf2m b)
{
return (_gf_modq_1(gf_mul_lll(a, b)));
}
gf2m Gf2m_Field::gf_mul_nrr(gf2m a, gf2m b)
{
return (gf_exp(gf_mul_rrr(a, b)));
}
gf2m Gf2m_Field::gf_mul_rrn(gf2m a, gf2m y)
{
return _gf_modq_1(gf_mul_lll(a, gf_log(y)));
}
gf2m Gf2m_Field::gf_mul_rnr(gf2m y, gf2m a)
{
return gf_mul_rrn(a, y);
}
gf2m Gf2m_Field::gf_mul_lnn(gf2m x, gf2m y)
{
return (m_gf_log_table[x] + m_gf_log_table[y]);
}
gf2m Gf2m_Field::gf_mul_rnn(gf2m x, gf2m y)
{
return _gf_modq_1(gf_mul_lnn(x, y));
}
gf2m Gf2m_Field::gf_mul_nrn(gf2m a, gf2m y)
{
return m_gf_exp_table[_gf_modq_1((a) + m_gf_log_table[y])];
}
/**
* zero operand allowed
*/
gf2m Gf2m_Field::gf_mul_zrz(gf2m a, gf2m y)
{
return ( (y == 0) ? 0 : gf_mul_nrn(a, y) );
}
gf2m Gf2m_Field::gf_mul_zzr(gf2m a, gf2m y)
{
return gf_mul_zrz(y, a);
}
/**
* non-zero operand
*/
gf2m Gf2m_Field::gf_mul_nnr(gf2m y, gf2m a)
{
return gf_mul_nrn( a, y);
}
gf2m Gf2m_Field::gf_sqrt(gf2m x)
{
return ((x) ? m_gf_exp_table[_gf_modq_1(m_gf_log_table[x] << (m_gf_extension_degree-1))] : 0);
}
gf2m Gf2m_Field::gf_div_rnn(gf2m x, gf2m y)
{
return _gf_modq_1(m_gf_log_table[x] - m_gf_log_table[y]);
}
gf2m Gf2m_Field::gf_div_rnr(gf2m x, gf2m b)
{
return _gf_modq_1(m_gf_log_table[x] - b);
}
gf2m Gf2m_Field::gf_div_nrr(gf2m a, gf2m b)
{
return m_gf_exp_table[_gf_modq_1(a - b)];
}
gf2m Gf2m_Field::gf_div_zzr(gf2m x, gf2m b)
{
return ((x) ? m_gf_exp_table[_gf_modq_1(m_gf_log_table[x] - b)] : 0);
}
gf2m Gf2m_Field::gf_inv(gf2m x)
{
return m_gf_exp_table[gf_ord() - m_gf_log_table[x]];
}
gf2m Gf2m_Field::gf_inv_rn(gf2m x)
{
return (gf_ord() - m_gf_log_table[x]);
}
gf2m Gf2m_Field::gf_square_ln(gf2m x)
{
return m_gf_log_table[x] << 1;
}
gf2m Gf2m_Field::gf_square_rr(gf2m a)
{
return a << 1;
}
gf2m Gf2m_Field::gf_l_from_n(gf2m x)
{
return m_gf_log_table[x];
}
u32bit encode_gf2m(gf2m to_enc, byte* mem);
gf2m decode_gf2m(const byte* mem);
}
}
#endif
|
