13#include <botan/internal/polyn_gf2m.h>
14#include <botan/internal/code_based_util.h>
15#include <botan/internal/bit_ops.h>
17#include <botan/exceptn.h>
18#include <botan/internal/loadstor.h>
26 gf2m result = (a != 0);
33unsigned nlz_16bit(uint16_t x)
38 if(x <= 0x00FF) {n = n + 8; x = x << 8;}
39 if(x <= 0x0FFF) {n = n + 4; x = x << 4;}
40 if(x <= 0x3FFF) {n = n + 2; x = x << 2;}
41 if(x <= 0x7FFF) {n = n + 1;}
48 int i =
static_cast<int>(this->
coeff.size()) - 1;
50 uint32_t found_mask = 0;
51 uint32_t tracker_mask = 0xffff;
55 result |= i & found_mask & tracker_mask;
58 tracker_mask = tracker_mask & ~found_mask;
75 throw Invalid_Argument(
"random_code_element() was supplied a code length of zero");
77 const unsigned nlz = nlz_16bit(code_length-1);
78 const gf2m mask = (1 << (16-nlz)) - 1;
86 }
while(result >= code_length);
94 m_sp_field(other.m_sp_field)
108 for(
int i = 0; i <= d; i ++)
121void polyn_gf2m::realloc(uint32_t new_size)
127 m_deg(-1), m_sp_field(sp_field)
129 if(mem_len %
sizeof(
gf2m))
134 uint32_t size = (mem_len /
sizeof(this->
coeff[0])) ;
137 for(uint32_t i = 0; i < size; i++)
140 mem +=
sizeof(this->
coeff[0]);
142 for(uint32_t i = 0; i < size; i++)
144 if(this->
coeff[i] >= (1 << sp_field->get_extension_degree()))
154 m_deg(-1), coeff(1), m_sp_field(sp_field)
158 :m_sp_field(sp_field)
163 polyn_size = degree + 1;
164 if(polyn_size * sp_field->get_extension_degree() > 8 * mem_byte_len)
166 throw Decoding_Error(
"memory vector for polynomial has wrong size");
170 for (l = 0; l < polyn_size; l++)
172 k = (l * ext_deg) / 8;
174 j = (l * ext_deg) % 8;
178 a ^= mem[k + 1] << (8- j);
182 a ^= mem[k + 2] << (16- j);
184 a &= ((1 << ext_deg) - 1);
185 (*this).set_coef( l, a);
192void polyn_gf2m::encode(uint32_t min_numo_coeffs, uint8_t* mem, uint32_t mem_len)
const
195 uint32_t numo_coeffs, needed_size;
197 numo_coeffs = (min_numo_coeffs >
static_cast<uint32_t
>(this->
m_deg+1)) ? min_numo_coeffs : this->
m_deg+1;
198 needed_size =
sizeof(this->
coeff[0]) * numo_coeffs;
199 if(mem_len < needed_size)
204 for(i = 0; i < numo_coeffs; i++)
207 if(i >=
static_cast<uint32_t
>(this->
m_deg+1))
214 to_enc = this->
coeff[i];
230 int d =
static_cast<int>(this->
coeff.size()) - 1;
231 while ((d >= 0) && (this->
coeff[d] == 0))
238static gf2m eval_aux(
const gf2m * coeff,
gf2m a,
int d,
const std::shared_ptr<GF2m_Field>& sp_field)
245 b = sp_field->gf_mul(
b, a) ^ coeff[d];
273 for (i = p_degree; d >= 0; --i, --d) {
291 std::vector<polyn_gf2m> sq;
296 const uint32_t d =
static_cast<uint32_t
>(signed_deg);
297 uint32_t t = g.
m_deg;
300 for (i = 0; i < t; ++i)
304 for (i = 0; i < d / 2; ++i)
306 sq[i].set_degree( 2 * i);
314 sq[i].set_degree( sq[i - 1].
get_degree() + 2);
315 polyn_gf2m::remainder(sq[i], g);
327 std::shared_ptr<GF2m_Field> sp_field = this->
m_sp_field;
331 for (i = 0; i < d / 2; ++i)
333 (*&result).
set_coef( i * 2, sp_field->gf_square((*
this)[i]));
339 gf2m lpi = (*this)[i];
342 lpi = sp_field->gf_log(lpi);
343 la = sp_field->gf_mul_rrr(lpi, lpi);
344 for (j = 0; j < d; ++j)
346 result[j] ^= sp_field->gf_mul_zrz(la, sq[i][j]);
352 result.set_degree( d - 1);
365 polyn_gf2m::remainder(p1, p2);
366 return polyn_gf2m::gcd_aux(p2, p1);
371polyn_gf2m polyn_gf2m::gcd(polyn_gf2m
const& p1, polyn_gf2m
const& p2)
375 if (a.get_degree() <
b.get_degree())
394 const size_t ext_deg = g.
m_sp_field->get_extension_degree();
402 size_t result =
static_cast<size_t>(d);
403 for(
size_t i = 1; i <= (d / 2) * ext_deg; ++i)
406 if ((i % ext_deg) == 0)
410 s = polyn_gf2m::gcd( g, r);
414 result = i / ext_deg;
432 if(this->coeff.size() < trgt_deg)
436 for(i = 0; i < this->coeff.size(); i++)
438 uint32_t equal, equal_mask;
439 this->coeff[i] |= patch_elem;
440 equal = (i == trgt_deg);
442 patch_elem &= ~equal_mask;
452 int i, j, dr, du, delta;
486 while (dr >= break_deg)
489 for (j = delta; j >= 0; --j)
496 for (i = 0; i <= du; ++i)
498 u0[i + j] ^=
m_sp_field->gf_mul_zrz(la, u1[i]);
501 for (i = 0; i <= dr; ++i)
503 r0[i + j] ^=
m_sp_field->gf_mul_zrz(la, r1[i]);
514 volatile gf2m fake_elem = 0x01;
515 volatile gf2m cond1, cond2;
529 cond1 = cond1 & cond2;
532 gf2m mask = generate_gf2m_mask(cond1);
533 fake_elem = fake_elem & mask;
538 volatile gf2m fake_elem = 0x00;
539 volatile uint32_t trgt_deg = 0;
577 int cond_u3 = u0.
coeff[3] == 0;
579 cond_r &= (cond_u1 & cond_u3);
583 fake_elem = 1 & mask;
590 int cond_u3 = u0.
coeff[3] == 0;
592 int cond_u5 = u0.
coeff[5] == 0;
594 cond_r &= (cond_u1 & cond_u3 & cond_u5);
597 fake_elem = 1 & mask;
604 int cond_u3 = u0.
coeff[3] == 0;
606 int cond_u5 = u0.
coeff[5] == 0;
608 int cond_u7 = u0.
coeff[7] == 0;
610 cond_r &= (cond_u1 & cond_u3 & cond_u5 & cond_u7);
613 fake_elem = 1 & mask;
618 aux = r0; r0 = r1; r1 = aux;
619 aux = u0; u0 = u1; u1 = aux;
623 while (r1[dr - delta] == 0)
636 return std::make_pair(u1,r1);
640 :m_deg(static_cast<int>(t)),
647 for(
size_t i = 0; i < t; ++i)
659void polyn_gf2m::poly_shiftmod(
const polyn_gf2m & g)
663 throw Invalid_Argument(
"shiftmod cannot be called on polynomials of degree 1 or less");
665 std::shared_ptr<GF2m_Field> field = g.
m_sp_field;
668 gf2m a = field->gf_div(this->coeff[t-1], g.
coeff[t]);
669 for (
int i = t - 1; i > 0; --i)
671 this->coeff[i] = this->coeff[i - 1] ^ this->m_sp_field->gf_mul(a, g.
coeff[i]);
673 this->coeff[0] = field->gf_mul(a, g.
coeff[0]);
679 uint32_t nb_polyn_sqrt_mat;
681 std::vector<polyn_gf2m> result;
683 nb_polyn_sqrt_mat = t/2;
693 for (i = 0; i < t *
m_sp_field->get_extension_degree() - 1; ++i)
704 for (i = 0; i < nb_polyn_sqrt_mat; ++i)
711 for(i = 1; i < nb_polyn_sqrt_mat; i++)
713 result[i] = result[i - 1];
714 result[i].poly_shiftmod(g);
715 result[i].get_degree();
727 std::shared_ptr<GF2m_Field> m_sp_field = generator.
m_sp_field;
729 std::vector<polyn_gf2m> result;
737 result.push_back(
polyn_gf2m( t-1, m_sp_field));
739 (*&result[j]).set_coef(t-1,1);
742 (*&result[j]).set_coef(i, (generator)[i+1] ^
743 m_sp_field->gf_mul(
lex_to_gray(support[j]),result[j][i+1]));
745 a = ((generator)[0] ^ m_sp_field->gf_mul(
lex_to_gray(support[j]),result[j][0]));
748 (*&result[j]).set_coef(i, m_sp_field->gf_div(result[j][i],a));
755 const std::shared_ptr<GF2m_Field>& sp_field) :
758 if(encoded.size() % 2)
762 for(uint32_t i = 0; i < encoded.size(); i += 2)
764 gf2m el = (encoded[i] << 8) | encoded[i + 1];
781 uint32_t len =
m_deg+1;
782 for(
unsigned i = 0; i < len; i++)
785 result.push_back(get_byte<0>(
coeff[i]));
786 result.push_back(get_byte<1>(
coeff[i]));
794 std::swap(this->m_sp_field, other.
m_sp_field);
795 std::swap(this->coeff, other.
coeff);
#define BOTAN_ASSERT(expr, assertion_made)
virtual void randomize(uint8_t output[], size_t length)=0
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)
std::string to_string() const
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)
void swap(polyn_gf2m &other)
static std::vector< polyn_gf2m > sqrt_mod_init(const polyn_gf2m &g)
secure_vector< gf2m > coeff
int calc_degree_secure() const
bool operator==(const polyn_gf2m &other) const
polyn_gf2m sqmod(const std::vector< polyn_gf2m > &sq, int d)
size_t degppf(const polyn_gf2m &g)
std::shared_ptr< GF2m_Field > m_sp_field
std::string to_string(const BER_Object &obj)
gf2m lex_to_gray(gf2m lex)
std::vector< polyn_gf2m > syndrome_init(polyn_gf2m const &generator, std::vector< gf2m > const &support, int n)
uint16_t expand_mask_16bit(T tst)
gf2m random_code_element(uint16_t code_length, RandomNumberGenerator &rng)
constexpr void copy_mem(T *out, const T *in, size_t n)
gf2m random_gf2m(RandomNumberGenerator &rng)
gf2m decode_gf2m(const uint8_t *mem)
uint32_t encode_gf2m(gf2m to_enc, uint8_t *mem)
std::vector< T, secure_allocator< T > > secure_vector
constexpr void clear_mem(T *ptr, size_t n)
constexpr uint16_t make_uint16(uint8_t i0, uint8_t i1)