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