13#include <botan/internal/polyn_gf2m.h>
15#include <botan/exceptn.h>
17#include <botan/internal/bit_ops.h>
18#include <botan/internal/code_based_util.h>
19#include <botan/internal/loadstor.h>
28 gf2m result = (a != 0);
35unsigned nlz_16bit(uint16_t x) {
61 int i =
static_cast<int>(this->m_coeff.size()) - 1;
63 uint32_t found_mask = 0;
64 uint32_t tracker_mask = 0xffff;
67 result |= i & found_mask & tracker_mask;
70 tracker_mask = tracker_mask & ~found_mask;
83 if(code_length == 0) {
84 throw Invalid_Argument(
"random_code_element() was supplied a code length of zero");
86 const unsigned nlz = nlz_16bit(code_length - 1);
87 const gf2m mask = (1 << (16 - nlz)) - 1;
91 while(result >= code_length) {
102 m_deg(-1), m_coeff(d + 1), m_sp_field(sp_field) {}
107void polyn_gf2m::realloc(uint32_t new_size) {
112 m_deg(-1), m_sp_field(sp_field) {
113 if(mem_len %
sizeof(
gf2m)) {
117 uint32_t size = (mem_len /
sizeof(this->m_coeff[0]));
120 for(uint32_t i = 0; i < size; i++) {
122 mem +=
sizeof(this->m_coeff[0]);
124 for(uint32_t i = 0; i < size; i++) {
125 if(this->m_coeff[i] >= (1 << sp_field->get_extension_degree())) {
137 const std::shared_ptr<GF2m_Field>& sp_field) :
138 m_sp_field(sp_field) {
139 const uint32_t polyn_size = degree + 1;
140 if(polyn_size * sp_field->get_extension_degree() > 8 * mem_byte_len) {
141 throw Decoding_Error(
"memory vector for polynomial has wrong size");
144 const gf2m ext_deg =
static_cast<gf2m>(this->m_sp_field->get_extension_degree());
145 for(uint32_t l = 0; l < polyn_size; l++) {
146 uint32_t k = (l * ext_deg) / 8;
148 uint32_t j = (l * ext_deg) % 8;
149 gf2m a = mem[k] >> j;
150 if(j + ext_deg > 8) {
151 a ^= mem[k + 1] << (8 - j);
153 if(j + ext_deg > 16) {
154 a ^= mem[k + 2] << (16 - j);
156 a &= ((1 << ext_deg) - 1);
157 (*this).set_coef(l, a);
164 clear_mem(this->m_coeff.data(), this->m_coeff.size());
169 int d =
static_cast<int>(this->m_coeff.size()) - 1;
170 while((d >= 0) && (this->m_coeff[d] == 0)) {
179gf2m eval_aux(
const gf2m* coeff,
gf2m a,
int d,
const std::shared_ptr<GF2m_Field>& sp_field) {
183 b = sp_field->gf_mul(b, a) ^ coeff[d];
194 return eval_aux(this->m_coeff.data(), a, this->m_deg, this->m_sp_field);
201 std::shared_ptr<GF2m_Field> m_sp_field = g.m_sp_field;
210 for(i = p_degree; d >= 0; --i, --d) {
212 gf2m lb = m_sp_field->gf_mul_rrn(la, p[i]);
214 p[j + d] ^= m_sp_field->gf_mul_zrz(lb, g[j]);
216 (*&p).set_coef(i, 0);
227 std::vector<polyn_gf2m> sq;
229 if(signed_deg <= 0) {
233 const uint32_t d =
static_cast<uint32_t
>(signed_deg);
234 uint32_t t = g.m_deg;
237 for(i = 0; i < t; ++i) {
240 for(i = 0; i < d / 2; ++i) {
241 sq[i].set_degree(2 * i);
247 copy_mem(sq[i].m_coeff.data() + 2, sq[i - 1].m_coeff.data(), d);
249 polyn_gf2m::remainder(sq[i], g);
259 std::shared_ptr<GF2m_Field> sp_field = this->m_sp_field;
263 for(i = 0; i < d / 2; ++i) {
264 (*&result).
set_coef(i * 2, sp_field->gf_square((*
this)[i]));
269 gf2m lpi = (*this)[i];
271 lpi = sp_field->gf_log(lpi);
272 gf2m la = sp_field->gf_mul_rrr(lpi, lpi);
273 for(
int j = 0; j < d; ++j) {
274 result[j] ^= sp_field->gf_mul_zrz(la, sq[i][j]);
280 result.set_degree(d - 1);
292 polyn_gf2m::remainder(p1, p2);
293 return polyn_gf2m::gcd_aux(p2, p1);
297polyn_gf2m polyn_gf2m::gcd(
const polyn_gf2m& p1,
const polyn_gf2m& p2) {
300 if(a.get_degree() < b.get_degree()) {
301 return polyn_gf2m(polyn_gf2m::gcd_aux(b, a));
303 return polyn_gf2m(polyn_gf2m::gcd_aux(a, b));
311 const size_t ext_deg = g.m_sp_field->get_extension_degree();
319 size_t result =
static_cast<size_t>(d);
320 for(
size_t i = 1; i <= (d / 2) * ext_deg; ++i) {
322 if((i % ext_deg) == 0) {
325 s = polyn_gf2m::gcd(g, r);
328 result = i / ext_deg;
344 if(this->m_coeff.size() < trgt_deg) {
347 for(uint32_t i = 0; i < this->m_coeff.size(); i++) {
348 this->m_coeff[i] |= patch_elem;
349 uint32_t equal = (i == trgt_deg);
351 patch_elem &= ~equal_mask;
361 std::shared_ptr<GF2m_Field> m_sp_field = g.m_sp_field;
394 while(dr >= break_deg) {
395 for(j = delta; j >= 0; --j) {
396 gf2m a = m_sp_field->gf_div(r0[dr + j], r1[dr]);
398 gf2m la = m_sp_field->gf_log(a);
400 for(i = 0; i <= du; ++i) {
401 u0[i + j] ^= m_sp_field->gf_mul_zrz(la, u1[i]);
404 for(i = 0; i <= dr; ++i) {
405 r0[i + j] ^= m_sp_field->gf_mul_zrz(la, r1[i]);
416 volatile gf2m fake_elem = 0x01;
417 volatile gf2m cond1 = 0;
418 volatile gf2m cond2 = 0;
429 cond1 = cond1 & cond2;
432 gf2m mask = generate_gf2m_mask(cond1);
433 fake_elem = fake_elem & mask;
438 volatile gf2m fake_elem = 0x00;
439 volatile uint32_t trgt_deg = 0;
473 int cond_u1 = m_sp_field->gf_mul(u0.m_coeff[1], m_sp_field->gf_inv(r0.m_coeff[0])) == 1;
476 int cond_u3 = u0.m_coeff[3] == 0;
478 cond_r &= (cond_u1 & cond_u3);
482 fake_elem = 1 & mask;
486 int cond_u1 = m_sp_field->gf_mul(u0.m_coeff[1], m_sp_field->gf_inv(r0.m_coeff[0])) == 1;
487 int cond_u3 = u0.m_coeff[3] == 0;
489 int cond_u5 = u0.m_coeff[5] == 0;
491 cond_r &= (cond_u1 & cond_u3 & cond_u5);
494 fake_elem = 1 & mask;
498 int cond_u1 = m_sp_field->gf_mul(u0[1], m_sp_field->gf_inv(r0[0])) == 1;
499 int cond_u3 = u0.m_coeff[3] == 0;
501 int cond_u5 = u0.m_coeff[5] == 0;
503 int cond_u7 = u0.m_coeff[7] == 0;
505 cond_r &= (cond_u1 & cond_u3 & cond_u5 & cond_u7);
508 fake_elem = 1 & mask;
522 while(r1[dr - delta] == 0) {
532 return std::make_pair(u1, r1);
536 m_deg(static_cast<int>(t)), m_coeff(t + 1), m_sp_field(sp_field) {
539 for(
size_t i = 0; i < t; ++i) {
551void polyn_gf2m::poly_shiftmod(
const polyn_gf2m& g) {
553 throw Invalid_Argument(
"shiftmod cannot be called on polynomials of degree 1 or less");
555 std::shared_ptr<GF2m_Field> field = g.m_sp_field;
558 gf2m a = field->gf_div(this->m_coeff[t - 1], g.m_coeff[t]);
559 for(
int i = t - 1; i > 0; --i) {
560 this->m_coeff[i] = this->m_coeff[i - 1] ^ this->m_sp_field->gf_mul(a, g.m_coeff[i]);
562 this->m_coeff[0] = field->gf_mul(a, g.m_coeff[0]);
568 uint32_t nb_polyn_sqrt_mat = 0;
569 std::shared_ptr<GF2m_Field> m_sp_field = g.m_sp_field;
570 std::vector<polyn_gf2m> result;
572 nb_polyn_sqrt_mat = t / 2;
581 for(i = 0; i < t * m_sp_field->get_extension_degree() - 1; ++i) {
591 for(i = 0; i < nb_polyn_sqrt_mat; ++i) {
597 for(i = 1; i < nb_polyn_sqrt_mat; i++) {
598 result[i] = result[i - 1];
599 result[i].poly_shiftmod(g);
600 result[i].get_degree();
612 std::shared_ptr<GF2m_Field> m_sp_field = generator.
get_sp_field();
614 std::vector<polyn_gf2m> result;
620 for(j = 0; j < n; j++) {
621 result.push_back(
polyn_gf2m(t - 1, m_sp_field));
623 (*&result[j]).set_coef(t - 1, 1);
624 for(i = t - 2; i >= 0; i--) {
625 (*&result[j]).set_coef(i, (generator)[i + 1] ^ m_sp_field->gf_mul(
lex_to_gray(support[j]), result[j][i + 1]));
627 a = ((generator)[0] ^ m_sp_field->gf_mul(
lex_to_gray(support[j]), result[j][0]));
628 for(i = 0; i < t; i++) {
629 (*&result[j]).set_coef(i, m_sp_field->gf_div(result[j][i], a));
636 m_sp_field(sp_field) {
637 if(encoded.size() % 2) {
638 throw Decoding_Error(
"encoded polynomial has odd length");
640 for(uint32_t i = 0; i < encoded.size(); i += 2) {
641 gf2m el = (encoded[i] << 8) | encoded[i + 1];
642 m_coeff.push_back(el);
656 uint32_t len = m_deg + 1;
657 for(
unsigned i = 0; i < len; i++) {
666 std::swap(this->m_deg, other.m_deg);
667 std::swap(this->m_sp_field, other.m_sp_field);
668 std::swap(this->m_coeff, other.m_coeff);
672 return m_deg == other.m_deg && m_coeff == other.m_coeff;
#define BOTAN_ASSERT(expr, assertion_made)
void randomize(std::span< uint8_t > output)
secure_vector< uint8_t > encode() const
std::shared_ptr< GF2m_Field > get_sp_field() const
static std::pair< polyn_gf2m, polyn_gf2m > eea_with_coefficients(const polyn_gf2m &p, const polyn_gf2m &g, int break_deg)
void set_coef(size_t i, gf2m v)
polyn_gf2m(const std::shared_ptr< GF2m_Field > &sp_field)
void swap(polyn_gf2m &other) noexcept
gf2m get_lead_coef() const
void patchup_deg_secure(uint32_t trgt_deg, gf2m patch_elem)
static std::vector< polyn_gf2m > sqmod_init(const polyn_gf2m &g)
static std::vector< polyn_gf2m > sqrt_mod_init(const polyn_gf2m &g)
int calc_degree_secure() const
bool operator==(const polyn_gf2m &other) const
polyn_gf2m sqmod(const std::vector< polyn_gf2m > &sq, int d)
static size_t degppf(const polyn_gf2m &g)
constexpr uint8_t get_byte(T input)
gf2m lex_to_gray(gf2m lex)
constexpr void copy_mem(T *out, const T *in, size_t n)
uint16_t expand_mask_16bit(T tst)
gf2m random_code_element(uint16_t code_length, RandomNumberGenerator &rng)
std::vector< polyn_gf2m > syndrome_init(const polyn_gf2m &generator, const std::vector< gf2m > &support, int n)
gf2m random_gf2m(RandomNumberGenerator &rng)
std::vector< T, secure_allocator< T > > secure_vector
gf2m decode_gf2m(const uint8_t *mem)
constexpr void clear_mem(T *ptr, size_t n)
constexpr uint16_t make_uint16(uint8_t i0, uint8_t i1)