/src/botan/build/include/botan/gf2m_small_m.h
Line | Count | Source (jump to first uncovered line) |
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 | | |
12 | | #ifndef BOTAN_GF2M_SMALL_M_H_ |
13 | | #define BOTAN_GF2M_SMALL_M_H_ |
14 | | |
15 | | #include <botan/types.h> |
16 | | #include <vector> |
17 | | |
18 | | // fixme - still used in mceliece.h |
19 | | //BOTAN_FUTURE_INTERNAL_HEADER(gf2m_small_m.h) |
20 | | |
21 | | namespace Botan { |
22 | | |
23 | | typedef uint16_t gf2m; |
24 | | |
25 | | /** |
26 | | * GF(2^m) field for m = [2...16] |
27 | | */ |
28 | | class BOTAN_PUBLIC_API(2,0) GF2m_Field |
29 | | { |
30 | | public: |
31 | | explicit GF2m_Field(size_t extdeg); |
32 | | |
33 | | gf2m gf_mul(gf2m x, gf2m y) const |
34 | 0 | { |
35 | 0 | return ((x) ? gf_mul_fast(x, y) : 0); |
36 | 0 | } |
37 | | |
38 | | gf2m gf_square(gf2m x) const |
39 | 0 | { |
40 | 0 | return ((x) ? gf_exp(_gf_modq_1(gf_log(x) << 1)) : 0); |
41 | 0 | } |
42 | | |
43 | | gf2m square_rr(gf2m x) const |
44 | 0 | { |
45 | 0 | return _gf_modq_1(x << 1); |
46 | 0 | } |
47 | | |
48 | | gf2m gf_mul_fast(gf2m x, gf2m y) const |
49 | 0 | { |
50 | 0 | return ((y) ? gf_exp(_gf_modq_1(gf_log(x) + gf_log(y))) : 0); |
51 | 0 | } |
52 | | |
53 | | /* |
54 | | naming convention of GF(2^m) field operations: |
55 | | l logarithmic, unreduced |
56 | | r logarithmic, reduced |
57 | | n normal, non-zero |
58 | | z normal, might be zero |
59 | | */ |
60 | | |
61 | | gf2m gf_mul_lll(gf2m a, gf2m b) const |
62 | 0 | { |
63 | 0 | return (a + b); |
64 | 0 | } |
65 | | |
66 | | gf2m gf_mul_rrr(gf2m a, gf2m b) const |
67 | 0 | { |
68 | 0 | return (_gf_modq_1(gf_mul_lll(a, b))); |
69 | 0 | } |
70 | | |
71 | | gf2m gf_mul_nrr(gf2m a, gf2m b) const |
72 | 0 | { |
73 | 0 | return (gf_exp(gf_mul_rrr(a, b))); |
74 | 0 | } |
75 | | |
76 | | gf2m gf_mul_rrn(gf2m a, gf2m y) const |
77 | 0 | { |
78 | 0 | return _gf_modq_1(gf_mul_lll(a, gf_log(y))); |
79 | 0 | } |
80 | | |
81 | | gf2m gf_mul_rnr(gf2m y, gf2m a) const |
82 | 0 | { |
83 | 0 | return gf_mul_rrn(a, y); |
84 | 0 | } |
85 | | |
86 | | gf2m gf_mul_lnn(gf2m x, gf2m y) const |
87 | 0 | { |
88 | 0 | return (gf_log(x) + gf_log(y)); |
89 | 0 | } |
90 | | |
91 | | gf2m gf_mul_rnn(gf2m x, gf2m y) const |
92 | 0 | { |
93 | 0 | return _gf_modq_1(gf_mul_lnn(x, y)); |
94 | 0 | } |
95 | | |
96 | | gf2m gf_mul_nrn(gf2m a, gf2m y) const |
97 | 0 | { |
98 | 0 | return gf_exp(_gf_modq_1((a) + gf_log(y))); |
99 | 0 | } |
100 | | |
101 | | /** |
102 | | * zero operand allowed |
103 | | */ |
104 | | gf2m gf_mul_zrz(gf2m a, gf2m y) const |
105 | 0 | { |
106 | 0 | return ( (y == 0) ? 0 : gf_mul_nrn(a, y) ); |
107 | 0 | } |
108 | | |
109 | | gf2m gf_mul_zzr(gf2m a, gf2m y) const |
110 | 0 | { |
111 | 0 | return gf_mul_zrz(y, a); |
112 | 0 | } |
113 | | |
114 | | /** |
115 | | * non-zero operand |
116 | | */ |
117 | | gf2m gf_mul_nnr(gf2m y, gf2m a) const |
118 | 0 | { |
119 | 0 | return gf_mul_nrn(a, y); |
120 | 0 | } |
121 | | |
122 | | gf2m gf_sqrt(gf2m x) const |
123 | 0 | { |
124 | 0 | return ((x) ? gf_exp(_gf_modq_1(gf_log(x) << (get_extension_degree()-1))) : 0); |
125 | 0 | } |
126 | | |
127 | | gf2m gf_div_rnn(gf2m x, gf2m y) const |
128 | 0 | { |
129 | 0 | return _gf_modq_1(gf_log(x) - gf_log(y)); |
130 | 0 | } |
131 | | |
132 | | gf2m gf_div_rnr(gf2m x, gf2m b) const |
133 | 0 | { |
134 | 0 | return _gf_modq_1(gf_log(x) - b); |
135 | 0 | } |
136 | | |
137 | | gf2m gf_div_nrr(gf2m a, gf2m b) const |
138 | 0 | { |
139 | 0 | return gf_exp(_gf_modq_1(a - b)); |
140 | 0 | } |
141 | | |
142 | | gf2m gf_div_zzr(gf2m x, gf2m b) const |
143 | 0 | { |
144 | 0 | return ((x) ? gf_exp(_gf_modq_1(gf_log(x) - b)) : 0); |
145 | 0 | } |
146 | | |
147 | | gf2m gf_inv(gf2m x) const |
148 | 0 | { |
149 | 0 | return gf_exp(gf_ord() - gf_log(x)); |
150 | 0 | } |
151 | | |
152 | | gf2m gf_inv_rn(gf2m x) const |
153 | 0 | { |
154 | 0 | return (gf_ord() - gf_log(x)); |
155 | 0 | } |
156 | | |
157 | | gf2m gf_square_ln(gf2m x) const |
158 | 0 | { |
159 | 0 | return gf_log(x) << 1; |
160 | 0 | } |
161 | | |
162 | | gf2m gf_square_rr(gf2m a) const |
163 | 0 | { |
164 | 0 | return a << 1; |
165 | 0 | } |
166 | | |
167 | | gf2m gf_l_from_n(gf2m x) const |
168 | 0 | { |
169 | 0 | return gf_log(x); |
170 | 0 | } |
171 | | |
172 | | gf2m gf_div(gf2m x, gf2m y) const; |
173 | | |
174 | | gf2m gf_exp(gf2m i) const |
175 | 0 | { |
176 | 0 | return m_gf_exp_table.at(i); /* alpha^i */ |
177 | 0 | } |
178 | | |
179 | | gf2m gf_log(gf2m i) const |
180 | 0 | { |
181 | 0 | return m_gf_log_table.at(i); /* return i when x=alpha^i */ |
182 | 0 | } |
183 | | |
184 | | gf2m gf_ord() const |
185 | 0 | { |
186 | 0 | return m_gf_multiplicative_order; |
187 | 0 | } |
188 | | |
189 | | size_t get_extension_degree() const |
190 | 0 | { |
191 | 0 | return m_gf_extension_degree; |
192 | 0 | } |
193 | | |
194 | | gf2m get_cardinality() const |
195 | 0 | { |
196 | 0 | return static_cast<gf2m>(1 << get_extension_degree()); |
197 | 0 | } |
198 | | |
199 | | private: |
200 | | gf2m _gf_modq_1(int32_t d) const |
201 | 0 | { |
202 | | /* residual modulo q-1 |
203 | | when -q < d < 0, we get (q-1+d) |
204 | | when 0 <= d < q, we get (d) |
205 | | when q <= d < 2q-1, we get (d-q+1) |
206 | | */ |
207 | 0 | return static_cast<gf2m>(((d) & gf_ord()) + ((d) >> get_extension_degree())); |
208 | 0 | } |
209 | | |
210 | | const size_t m_gf_extension_degree; |
211 | | const gf2m m_gf_multiplicative_order; |
212 | | const std::vector<gf2m>& m_gf_log_table; |
213 | | const std::vector<gf2m>& m_gf_exp_table; |
214 | | }; |
215 | | |
216 | | uint32_t encode_gf2m(gf2m to_enc, uint8_t* mem); |
217 | | |
218 | | gf2m decode_gf2m(const uint8_t* mem); |
219 | | |
220 | | } |
221 | | |
222 | | #endif |