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
|
/*
* (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_POLYN_GF2M_H_
#define BOTAN_POLYN_GF2M_H_
#include <botan/secmem.h>
#include <utility>
#include <string>
// Currently must be visible for MSVC
//BOTAN_FUTURE_INTERNAL_HEADER(polyn_gf2m.h)
namespace Botan {
typedef uint16_t gf2m;
class GF2m_Field;
class RandomNumberGenerator;
class polyn_gf2m
{
public:
/**
* create a zero polynomial:
*/
explicit polyn_gf2m(std::shared_ptr<GF2m_Field> sp_field);
polyn_gf2m() : m_deg(-1) {}
polyn_gf2m(const secure_vector<uint8_t>& encoded, std::shared_ptr<GF2m_Field> sp_field);
polyn_gf2m& operator=(const polyn_gf2m&) = default;
/**
* create zero polynomial with reservation of space for a degree d polynomial
*/
polyn_gf2m(int d, std::shared_ptr<GF2m_Field> sp_field);
polyn_gf2m(polyn_gf2m const& other);
/**
* random irreducible polynomial of degree t
*/
polyn_gf2m(size_t t, RandomNumberGenerator& rng, std::shared_ptr<GF2m_Field> sp_field);
/** decode a polynomial from memory: **/
polyn_gf2m(const uint8_t* mem, uint32_t mem_len, std::shared_ptr<GF2m_Field> sp_field);
/**
* create a polynomial from memory area (encoded)
*/
polyn_gf2m(int degree, const uint8_t* mem, size_t mem_byte_len, std::shared_ptr<GF2m_Field> sp_field);
bool operator==(const polyn_gf2m & other) const ;
bool operator!=(const polyn_gf2m & other) const { return !(*this == other); }
polyn_gf2m(polyn_gf2m&& other)
{
this->swap(other);
}
polyn_gf2m & operator=(polyn_gf2m&& other)
{
if(this != &other)
{
this->swap(other);
}
return *this;
}
void swap(polyn_gf2m& other);
secure_vector<uint8_t> encode() const;
std::shared_ptr<GF2m_Field> get_sp_field() const
{ return m_sp_field; }
gf2m& operator[](size_t i) { return coeff[i]; }
gf2m operator[](size_t i) const { return coeff[i]; }
gf2m get_lead_coef() const { return coeff[m_deg]; }
gf2m get_coef(size_t i) const { return coeff[i]; }
inline void set_coef(size_t i, gf2m v)
{
coeff[i] = v;
}
inline void add_to_coef(size_t i, gf2m v)
{
coeff[i] ^= v;
}
std::string to_string() const;
void encode(uint32_t min_numo_coeffs, uint8_t* mem, uint32_t mem_len) const;
int get_degree() const;
/**
* determine the degree in a timing secure manner. the timing of this function
* only depends on the number of allocated coefficients, not on the actual
* degree
*/
int calc_degree_secure() const;
size_t degppf(const polyn_gf2m& g);
static std::vector<polyn_gf2m> sqmod_init(const polyn_gf2m & g);
static std::vector<polyn_gf2m> sqrt_mod_init(const polyn_gf2m & g);
polyn_gf2m sqmod(const std::vector<polyn_gf2m> & sq, int d);
void set_to_zero();
gf2m eval(gf2m a);
static std::pair<polyn_gf2m, polyn_gf2m> eea_with_coefficients(const polyn_gf2m & p,
const polyn_gf2m & g,
int break_deg);
void patchup_deg_secure( uint32_t trgt_deg, volatile gf2m patch_elem);
private:
void set_degree(int d) { m_deg = d; }
void poly_shiftmod( const polyn_gf2m & g);
void realloc(uint32_t new_size);
static polyn_gf2m gcd(polyn_gf2m const& p1, polyn_gf2m const& p2);
/**
* destructive:
*/
static void remainder(polyn_gf2m & p, const polyn_gf2m & g);
static polyn_gf2m gcd_aux(polyn_gf2m& p1, polyn_gf2m& p2);
public:
// public member variable:
int m_deg;
// public member variable:
secure_vector<gf2m> coeff;
// public member variable:
std::shared_ptr<GF2m_Field> m_sp_field;
};
gf2m random_gf2m(RandomNumberGenerator& rng);
gf2m random_code_element(uint16_t code_length, RandomNumberGenerator& rng);
std::vector<polyn_gf2m> syndrome_init(polyn_gf2m const& generator, std::vector<gf2m> const& support, int n);
/**
* Find the roots of a polynomial over GF(2^m) using the method by Federenko et al.
*/
secure_vector<gf2m> find_roots_gf2m_decomp(const polyn_gf2m & polyn, size_t code_length);
}
#endif
|
