Botan 2.19.5 Crypto and TLS for C&

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
30 class polyn_gf2m
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
68 polyn_gf2m(polyn_gf2m&& other)
69 {
70 this->swap(other);
71 }
72
73 polyn_gf2m & operator=(polyn_gf2m&& other)
74 {
75 if(this != &other)
76 {
77 this->swap(other);
78 }
79 return *this;
80 }
81
82 void swap(polyn_gf2m& other);
83
84 secure_vector<uint8_t> encode() const;
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:
156 secure_vector<gf2m> coeff;
157
158 // public member variable:
159 std::shared_ptr<GF2m_Field> m_sp_field;
160 };
161
162 gf2m random_gf2m(RandomNumberGenerator& rng);
163 gf2m random_code_element(uint16_t code_length, RandomNumberGenerator& rng);
164
165std::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
Botan::RandomNumberGenerator
Definition: rng.h:26
Botan::polyn_gf2m
Definition: polyn_gf2m.h:31
Botan::polyn_gf2m::set_to_zero
void set_to_zero()
Definition: polyn_gf2m.cpp:222
Botan::polyn_gf2m::encode
secure_vector< uint8_t > encode() const
Definition: polyn_gf2m.cpp:769
Botan::polyn_gf2m::m_deg
int m_deg
Definition: polyn_gf2m.h:153
Botan::polyn_gf2m::get_degree
int get_degree() const
Definition: polyn_gf2m.cpp:228
Botan::polyn_gf2m::get_sp_field
std::shared_ptr< GF2m_Field > get_sp_field() const
Definition: polyn_gf2m.h:86
Botan::polyn_gf2m::operator!=
bool operator!=(const polyn_gf2m &other) const
Definition: polyn_gf2m.h:66
Botan::polyn_gf2m::eea_with_coefficients
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
Botan::polyn_gf2m::set_coef
void set_coef(size_t i, gf2m v)
Definition: polyn_gf2m.h:97
Botan::polyn_gf2m::polyn_gf2m
polyn_gf2m(polyn_gf2m &&other)
Definition: polyn_gf2m.h:68
Botan::polyn_gf2m::get_coef
gf2m get_coef(size_t i) const
Definition: polyn_gf2m.h:95
Botan::polyn_gf2m::to_string
std::string to_string() const
Definition: polyn_gf2m.cpp:104
Botan::polyn_gf2m::get_lead_coef
gf2m get_lead_coef() const
Definition: polyn_gf2m.h:93
Botan::polyn_gf2m::operator=
polyn_gf2m & operator=(const polyn_gf2m &)=default
Botan::polyn_gf2m::sqmod_init
static std::vector< polyn_gf2m > sqmod_init(const polyn_gf2m &g)
Definition: polyn_gf2m.cpp:289
Botan::polyn_gf2m::swap
void swap(polyn_gf2m &other)
Definition: polyn_gf2m.cpp:790
Botan::polyn_gf2m::sqrt_mod_init
static std::vector< polyn_gf2m > sqrt_mod_init(const polyn_gf2m &g)
Definition: polyn_gf2m.cpp:676
Botan::polyn_gf2m::operator=
polyn_gf2m & operator=(polyn_gf2m &&other)
Definition: polyn_gf2m.h:73
Botan::polyn_gf2m::encode
void encode(uint32_t min_numo_coeffs, uint8_t *mem, uint32_t mem_len) const
Botan::polyn_gf2m::operator[]
gf2m operator[](size_t i) const
Definition: polyn_gf2m.h:91
Botan::polyn_gf2m::polyn_gf2m
polyn_gf2m()
Definition: polyn_gf2m.h:38
Botan::polyn_gf2m::add_to_coef
void add_to_coef(size_t i, gf2m v)
Definition: polyn_gf2m.h:102
Botan::polyn_gf2m::coeff
secure_vector< gf2m > coeff
Definition: polyn_gf2m.h:156
Botan::polyn_gf2m::calc_degree_secure
int calc_degree_secure() const
Definition: polyn_gf2m.cpp:46
Botan::polyn_gf2m::patchup_deg_secure
void patchup_deg_secure(uint32_t trgt_deg, volatile gf2m patch_elem)
Definition: polyn_gf2m.cpp:429
Botan::polyn_gf2m::operator==
bool operator==(const polyn_gf2m &other) const
Definition: polyn_gf2m.cpp:797
Botan::polyn_gf2m::operator[]
gf2m & operator[](size_t i)
Definition: polyn_gf2m.h:89
Botan::polyn_gf2m::sqmod
polyn_gf2m sqmod(const std::vector< polyn_gf2m > &sq, int d)
Definition: polyn_gf2m.cpp:323
Botan::polyn_gf2m::eval
gf2m eval(gf2m a)
Definition: polyn_gf2m.cpp:254
Botan::polyn_gf2m::degppf
size_t degppf(const polyn_gf2m &g)
Definition: polyn_gf2m.cpp:390
Botan::polyn_gf2m::m_sp_field
std::shared_ptr< GF2m_Field > m_sp_field
Definition: polyn_gf2m.h:159
Botan
Definition: alg_id.cpp:13
Botan::syndrome_init
std::vector< polyn_gf2m > syndrome_init(polyn_gf2m const &generator, std::vector< gf2m > const &support, int n)
Definition: polyn_gf2m.cpp:721
Botan::random_code_element
gf2m random_code_element(uint16_t code_length, RandomNumberGenerator &rng)
Definition: polyn_gf2m.cpp:71
Botan::random_gf2m
gf2m random_gf2m(RandomNumberGenerator &rng)
Definition: polyn_gf2m.cpp:64
Botan::find_roots_gf2m_decomp
secure_vector< gf2m > find_roots_gf2m_decomp(const polyn_gf2m &polyn, size_t code_length)
Definition: gf2m_rootfind_dcmp.cpp:308
Botan::secure_vector
std::vector< T, secure_allocator< T > > secure_vector
Definition: secmem.h:65
Botan::gf2m
uint16_t gf2m
Definition: gf2m_small_m.h:22