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