Botan  2.19.1
Crypto and TLS for C++11
polyn_gf2m.h
Go to the documentation of this file.
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_POLYN_GF2M_H_
13 #define BOTAN_POLYN_GF2M_H_
14 
15 #include <botan/secmem.h>
16 #include <utility>
17 #include <string>
18 
19 // Currently must be visible for MSVC
20 //BOTAN_FUTURE_INTERNAL_HEADER(polyn_gf2m.h)
21 
22 namespace Botan {
23 
24 typedef uint16_t gf2m;
25 
26 class GF2m_Field;
27 
28 class RandomNumberGenerator;
29 
31  {
32  public:
33  /**
34  * create a zero polynomial:
35  */
36  explicit polyn_gf2m(std::shared_ptr<GF2m_Field> sp_field);
37 
38  polyn_gf2m() : m_deg(-1) {}
39 
40  polyn_gf2m(const secure_vector<uint8_t>& encoded, std::shared_ptr<GF2m_Field> sp_field);
41 
42  polyn_gf2m& operator=(const polyn_gf2m&) = default;
43 
44  /**
45  * create zero polynomial with reservation of space for a degree d polynomial
46  */
47  polyn_gf2m(int d, std::shared_ptr<GF2m_Field> sp_field);
48 
49  polyn_gf2m(polyn_gf2m const& other);
50 
51  /**
52  * random irreducible polynomial of degree t
53  */
54  polyn_gf2m(size_t t, RandomNumberGenerator& rng, std::shared_ptr<GF2m_Field> sp_field);
55 
56  /** decode a polynomial from memory: **/
57  polyn_gf2m(const uint8_t* mem, uint32_t mem_len, std::shared_ptr<GF2m_Field> sp_field);
58 
59  /**
60  * create a polynomial from memory area (encoded)
61  */
62  polyn_gf2m(int degree, const uint8_t* mem, size_t mem_byte_len, std::shared_ptr<GF2m_Field> sp_field);
63 
64  bool operator==(const polyn_gf2m & other) const ;
65 
66  bool operator!=(const polyn_gf2m & other) const { return !(*this == other); }
67 
69  {
70  this->swap(other);
71  }
72 
74  {
75  if(this != &other)
76  {
77  this->swap(other);
78  }
79  return *this;
80  }
81 
82  void swap(polyn_gf2m& other);
83 
85 
86  std::shared_ptr<GF2m_Field> get_sp_field() const
87  { return m_sp_field; }
88 
89  gf2m& operator[](size_t i) { return coeff[i]; }
90 
91  gf2m operator[](size_t i) const { return coeff[i]; }
92 
93  gf2m get_lead_coef() const { return coeff[m_deg]; }
94 
95  gf2m get_coef(size_t i) const { return coeff[i]; }
96 
97  inline void set_coef(size_t i, gf2m v)
98  {
99  coeff[i] = v;
100  }
101 
102  inline void add_to_coef(size_t i, gf2m v)
103  {
104  coeff[i] ^= v;
105  }
106 
107  std::string to_string() const;
108 
109  void encode(uint32_t min_numo_coeffs, uint8_t* mem, uint32_t mem_len) const;
110 
111  int get_degree() const;
112 
113  /**
114  * determine the degree in a timing secure manner. the timing of this function
115  * only depends on the number of allocated coefficients, not on the actual
116  * degree
117  */
118  int calc_degree_secure() const;
119 
120  size_t degppf(const polyn_gf2m& g);
121 
122  static std::vector<polyn_gf2m> sqmod_init(const polyn_gf2m & g);
123 
124  static std::vector<polyn_gf2m> sqrt_mod_init(const polyn_gf2m & g);
125 
126 
127  polyn_gf2m sqmod(const std::vector<polyn_gf2m> & sq, int d);
128  void set_to_zero();
129  gf2m eval(gf2m a);
130 
131  static std::pair<polyn_gf2m, polyn_gf2m> eea_with_coefficients(const polyn_gf2m & p,
132  const polyn_gf2m & g,
133  int break_deg);
134 
135  void patchup_deg_secure( uint32_t trgt_deg, volatile gf2m patch_elem);
136 
137  private:
138 
139  void set_degree(int d) { m_deg = d; }
140 
141  void poly_shiftmod( const polyn_gf2m & g);
142  void realloc(uint32_t new_size);
143  static polyn_gf2m gcd(polyn_gf2m const& p1, polyn_gf2m const& p2);
144 
145  /**
146  * destructive:
147  */
148  static void remainder(polyn_gf2m & p, const polyn_gf2m & g);
149 
150  static polyn_gf2m gcd_aux(polyn_gf2m& p1, polyn_gf2m& p2);
151  public:
152  // public member variable:
153  int m_deg;
154 
155  // public member variable:
157 
158  // public member variable:
159  std::shared_ptr<GF2m_Field> m_sp_field;
160  };
161 
163 gf2m random_code_element(uint16_t code_length, RandomNumberGenerator& rng);
164 
165 std::vector<polyn_gf2m> syndrome_init(polyn_gf2m const& generator, std::vector<gf2m> const& support, int n);
166 
167 /**
168 * Find the roots of a polynomial over GF(2^m) using the method by Federenko et al.
169 */
170 secure_vector<gf2m> find_roots_gf2m_decomp(const polyn_gf2m & polyn, size_t code_length);
171 
172 }
173 
174 #endif
size_t degppf(const polyn_gf2m &g)
Definition: polyn_gf2m.cpp:390
gf2m & operator[](size_t i)
Definition: polyn_gf2m.h:89
gf2m operator[](size_t i) const
Definition: polyn_gf2m.h:91
bool operator!=(const polyn_gf2m &other) const
Definition: polyn_gf2m.h:66
polyn_gf2m sqmod(const std::vector< polyn_gf2m > &sq, int d)
Definition: polyn_gf2m.cpp:323
gf2m get_lead_coef() const
Definition: polyn_gf2m.h:93
secure_vector< uint8_t > encode() const
Definition: polyn_gf2m.cpp:769
static std::vector< polyn_gf2m > sqrt_mod_init(const polyn_gf2m &g)
Definition: polyn_gf2m.cpp:676
int calc_degree_secure() const
Definition: polyn_gf2m.cpp:46
polyn_gf2m & operator=(polyn_gf2m &&other)
Definition: polyn_gf2m.h:73
std::vector< T, secure_allocator< T >> secure_vector
Definition: secmem.h:65
void patchup_deg_secure(uint32_t trgt_deg, volatile gf2m patch_elem)
Definition: polyn_gf2m.cpp:429
int get_degree() const
Definition: polyn_gf2m.cpp:228
uint16_t gf2m
Definition: gf2m_small_m.h:22
Definition: alg_id.cpp:13
polyn_gf2m(polyn_gf2m &&other)
Definition: polyn_gf2m.h:68
std::shared_ptr< GF2m_Field > get_sp_field() const
Definition: polyn_gf2m.h:86
static std::vector< polyn_gf2m > sqmod_init(const polyn_gf2m &g)
Definition: polyn_gf2m.cpp:289
secure_vector< gf2m > coeff
Definition: polyn_gf2m.h:156
bool operator==(const polyn_gf2m &other) const
Definition: polyn_gf2m.cpp:797
void add_to_coef(size_t i, gf2m v)
Definition: polyn_gf2m.h:102
gf2m random_code_element(uint16_t code_length, RandomNumberGenerator &rng)
Definition: polyn_gf2m.cpp:71
std::vector< polyn_gf2m > syndrome_init(polyn_gf2m const &generator, std::vector< gf2m > const &support, int n)
Definition: polyn_gf2m.cpp:721
static std::pair< polyn_gf2m, polyn_gf2m > eea_with_coefficients(const polyn_gf2m &p, const polyn_gf2m &g, int break_deg)
Definition: polyn_gf2m.cpp:448
std::string to_string() const
Definition: polyn_gf2m.cpp:104
polyn_gf2m & operator=(const polyn_gf2m &)=default
secure_vector< gf2m > find_roots_gf2m_decomp(const polyn_gf2m &polyn, size_t code_length)
gf2m get_coef(size_t i) const
Definition: polyn_gf2m.h:95
gf2m random_gf2m(RandomNumberGenerator &rng)
Definition: polyn_gf2m.cpp:64
void swap(polyn_gf2m &other)
Definition: polyn_gf2m.cpp:790
std::shared_ptr< GF2m_Field > m_sp_field
Definition: polyn_gf2m.h:159
gf2m eval(gf2m a)
Definition: polyn_gf2m.cpp:254
void set_coef(size_t i, gf2m v)
Definition: polyn_gf2m.h:97