Botan 2.19.1
Crypto and TLS for C&
Public Member Functions | Static Public Member Functions | Public Attributes | List of all members
Botan::polyn_gf2m Class Reference

#include <polyn_gf2m.h>

Public Member Functions

void add_to_coef (size_t i, gf2m v)
 
int calc_degree_secure () const
 
size_t degppf (const polyn_gf2m &g)
 
secure_vector< uint8_t > encode () const
 
void encode (uint32_t min_numo_coeffs, uint8_t *mem, uint32_t mem_len) const
 
gf2m eval (gf2m a)
 
gf2m get_coef (size_t i) const
 
int get_degree () const
 
gf2m get_lead_coef () const
 
std::shared_ptr< GF2m_Fieldget_sp_field () const
 
bool operator!= (const polyn_gf2m &other) const
 
polyn_gf2moperator= (const polyn_gf2m &)=default
 
polyn_gf2moperator= (polyn_gf2m &&other)
 
bool operator== (const polyn_gf2m &other) const
 
gf2moperator[] (size_t i)
 
gf2m operator[] (size_t i) const
 
void patchup_deg_secure (uint32_t trgt_deg, volatile gf2m patch_elem)
 
 polyn_gf2m ()
 
 polyn_gf2m (const secure_vector< uint8_t > &encoded, std::shared_ptr< GF2m_Field > sp_field)
 
 polyn_gf2m (const uint8_t *mem, uint32_t mem_len, std::shared_ptr< GF2m_Field > sp_field)
 
 polyn_gf2m (int d, std::shared_ptr< GF2m_Field > sp_field)
 
 polyn_gf2m (int degree, const uint8_t *mem, size_t mem_byte_len, std::shared_ptr< GF2m_Field > sp_field)
 
 polyn_gf2m (polyn_gf2m &&other)
 
 polyn_gf2m (polyn_gf2m const &other)
 
 polyn_gf2m (size_t t, RandomNumberGenerator &rng, std::shared_ptr< GF2m_Field > sp_field)
 
 polyn_gf2m (std::shared_ptr< GF2m_Field > sp_field)
 
void set_coef (size_t i, gf2m v)
 
void set_to_zero ()
 
polyn_gf2m sqmod (const std::vector< polyn_gf2m > &sq, int d)
 
void swap (polyn_gf2m &other)
 
std::string to_string () const
 

Static Public Member Functions

static std::pair< polyn_gf2m, polyn_gf2meea_with_coefficients (const polyn_gf2m &p, const polyn_gf2m &g, int break_deg)
 
static std::vector< polyn_gf2msqmod_init (const polyn_gf2m &g)
 
static std::vector< polyn_gf2msqrt_mod_init (const polyn_gf2m &g)
 

Public Attributes

secure_vector< gf2mcoeff
 
int m_deg
 
std::shared_ptr< GF2m_Fieldm_sp_field
 

Detailed Description

Definition at line 30 of file polyn_gf2m.h.

Constructor & Destructor Documentation

◆ polyn_gf2m() [1/9]

Botan::polyn_gf2m::polyn_gf2m ( std::shared_ptr< GF2m_Field sp_field)
explicit

create a zero polynomial:

Definition at line 153 of file polyn_gf2m.cpp.

153 :
154 m_deg(-1), coeff(1), m_sp_field(sp_field)
155 {}
secure_vector< gf2m > coeff
Definition: polyn_gf2m.h:156
std::shared_ptr< GF2m_Field > m_sp_field
Definition: polyn_gf2m.h:159

◆ polyn_gf2m() [2/9]

Botan::polyn_gf2m::polyn_gf2m ( )
inline

Definition at line 38 of file polyn_gf2m.h.

38: m_deg(-1) {}

Referenced by sqmod_init(), and sqrt_mod_init().

◆ polyn_gf2m() [3/9]

Botan::polyn_gf2m::polyn_gf2m ( const secure_vector< uint8_t > &  encoded,
std::shared_ptr< GF2m_Field sp_field 
)

Definition at line 754 of file polyn_gf2m.cpp.

755 :m_sp_field(sp_field)
756 {
757 if(encoded.size() % 2)
758 {
759 throw Decoding_Error("encoded polynomial has odd length");
760 }
761 for(uint32_t i = 0; i < encoded.size(); i += 2)
762 {
763 gf2m el = (encoded[i] << 8) | encoded[i + 1];
764 coeff.push_back(el);
765 }
766 get_degree();
767
768 }
int get_degree() const
Definition: polyn_gf2m.cpp:228
uint16_t gf2m
Definition: gf2m_small_m.h:22

References coeff, and get_degree().

◆ polyn_gf2m() [4/9]

Botan::polyn_gf2m::polyn_gf2m ( int  d,
std::shared_ptr< GF2m_Field sp_field 
)

create zero polynomial with reservation of space for a degree d polynomial

Definition at line 97 of file polyn_gf2m.cpp.

98 :m_deg(-1),
99 coeff(d+1),
100 m_sp_field(sp_field)
101 {
102 }

◆ polyn_gf2m() [5/9]

Botan::polyn_gf2m::polyn_gf2m ( polyn_gf2m const &  other)

Definition at line 91 of file polyn_gf2m.cpp.

92 :m_deg(other.m_deg),
93 coeff(other.coeff),
94 m_sp_field(other.m_sp_field)
95 { }

◆ polyn_gf2m() [6/9]

Botan::polyn_gf2m::polyn_gf2m ( size_t  t,
RandomNumberGenerator rng,
std::shared_ptr< GF2m_Field sp_field 
)

random irreducible polynomial of degree t

Definition at line 639 of file polyn_gf2m.cpp.

640 :m_deg(static_cast<int>(t)),
641 coeff(t+1),
642 m_sp_field(sp_field)
643 {
644 this->set_coef(t, 1);
645 for(;;)
646 {
647 for(size_t i = 0; i < t; ++i)
648 {
649 this->set_coef(i, random_code_element(sp_field->get_cardinality(), rng));
650 }
651
652 const size_t degree = polyn_gf2m::degppf(*this);
653
654 if(degree >= t)
655 break;
656 }
657 }
void set_coef(size_t i, gf2m v)
Definition: polyn_gf2m.h:97
size_t degppf(const polyn_gf2m &g)
Definition: polyn_gf2m.cpp:390
gf2m random_code_element(uint16_t code_length, RandomNumberGenerator &rng)
Definition: polyn_gf2m.cpp:71

References degppf(), Botan::random_code_element(), and set_coef().

◆ polyn_gf2m() [7/9]

Botan::polyn_gf2m::polyn_gf2m ( const uint8_t *  mem,
uint32_t  mem_len,
std::shared_ptr< GF2m_Field sp_field 
)

decode a polynomial from memory:

Definition at line 126 of file polyn_gf2m.cpp.

126 :
127 m_deg(-1), m_sp_field(sp_field)
128 {
129 if(mem_len % sizeof(gf2m))
130 {
131 throw Decoding_Error("illegal length of memory to decode ");
132 }
133
134 uint32_t size = (mem_len / sizeof(this->coeff[0])) ;
135 this->coeff = secure_vector<gf2m>(size);
136 this->m_deg = -1;
137 for(uint32_t i = 0; i < size; i++)
138 {
139 this->coeff[i] = decode_gf2m(mem);
140 mem += sizeof(this->coeff[0]);
141 }
142 for(uint32_t i = 0; i < size; i++)
143 {
144 if(this->coeff[i] >= (1 << sp_field->get_extension_degree()))
145 {
146 throw Decoding_Error("error decoding polynomial");
147 }
148 }
149 this->get_degree();
150 }
gf2m decode_gf2m(const uint8_t *mem)

References coeff, Botan::decode_gf2m(), get_degree(), and m_deg.

◆ polyn_gf2m() [8/9]

Botan::polyn_gf2m::polyn_gf2m ( int  degree,
const uint8_t *  mem,
size_t  mem_byte_len,
std::shared_ptr< GF2m_Field sp_field 
)

create a polynomial from memory area (encoded)

Definition at line 157 of file polyn_gf2m.cpp.

158 :m_sp_field(sp_field)
159 {
160 uint32_t j, k, l;
161 gf2m a;
162 uint32_t polyn_size;
163 polyn_size = degree + 1;
164 if(polyn_size * sp_field->get_extension_degree() > 8 * mem_byte_len)
165 {
166 throw Decoding_Error("memory vector for polynomial has wrong size");
167 }
168 this->coeff = secure_vector<gf2m>(degree+1);
169 gf2m ext_deg = static_cast<gf2m>(this->m_sp_field->get_extension_degree());
170 for (l = 0; l < polyn_size; l++)
171 {
172 k = (l * ext_deg) / 8;
173
174 j = (l * ext_deg) % 8;
175 a = mem[k] >> j;
176 if (j + ext_deg > 8)
177 {
178 a ^= mem[k + 1] << (8- j);
179 }
180 if(j + ext_deg > 16)
181 {
182 a ^= mem[k + 2] << (16- j);
183 }
184 a &= ((1 << ext_deg) - 1);
185 (*this).set_coef( l, a);
186 }
187
188 this->get_degree();
189 }

References coeff, get_degree(), and m_sp_field.

◆ polyn_gf2m() [9/9]

Botan::polyn_gf2m::polyn_gf2m ( polyn_gf2m &&  other)
inline

Definition at line 68 of file polyn_gf2m.h.

69 {
70 this->swap(other);
71 }
void swap(polyn_gf2m &other)
Definition: polyn_gf2m.cpp:790

References swap().

Member Function Documentation

◆ add_to_coef()

void Botan::polyn_gf2m::add_to_coef ( size_t  i,
gf2m  v 
)
inline

Definition at line 102 of file polyn_gf2m.h.

103 {
104 coeff[i] ^= v;
105 }

References coeff.

◆ calc_degree_secure()

int Botan::polyn_gf2m::calc_degree_secure ( ) const

determine the degree in a timing secure manner. the timing of this function only depends on the number of allocated coefficients, not on the actual degree

Definition at line 46 of file polyn_gf2m.cpp.

47 {
48 int i = static_cast<int>(this->coeff.size()) - 1;
49 int result = 0;
50 uint32_t found_mask = 0;
51 uint32_t tracker_mask = 0xffff;
52 for( ; i >= 0; i--)
53 {
54 found_mask = expand_mask_16bit(this->coeff[i]);
55 result |= i & found_mask & tracker_mask;
56 // tracker mask shall become zero once found mask is set
57 // it shall remain zero from then on
58 tracker_mask = tracker_mask & ~found_mask;
59 }
60 const_cast<polyn_gf2m*>(this)->m_deg = result;
61 return result;
62 }
uint16_t expand_mask_16bit(T tst)

References coeff, Botan::expand_mask_16bit(), and m_deg.

Referenced by eea_with_coefficients(), and patchup_deg_secure().

◆ degppf()

size_t Botan::polyn_gf2m::degppf ( const polyn_gf2m g)

Definition at line 390 of file polyn_gf2m.cpp.

391 {
392 polyn_gf2m s(g.get_sp_field());
393
394 const size_t ext_deg = g.m_sp_field->get_extension_degree();
395 const int d = g.get_degree();
396 std::vector<polyn_gf2m> u = polyn_gf2m::sqmod_init(g);
397
398 polyn_gf2m p(d - 1, g.m_sp_field);
399
400 p.set_degree(1);
401 (*&p).set_coef(1, 1);
402 size_t result = static_cast<size_t>(d);
403 for(size_t i = 1; i <= (d / 2) * ext_deg; ++i)
404 {
405 polyn_gf2m r = p.sqmod(u, d);
406 if ((i % ext_deg) == 0)
407 {
408 r[1] ^= 1;
409 r.get_degree(); // The degree may change
410 s = polyn_gf2m::gcd( g, r);
411
412 if(s.get_degree() > 0)
413 {
414 result = i / ext_deg;
415 break;
416 }
417 r[1] ^= 1;
418 r.get_degree(); // The degree may change
419 }
420 // No need for the exchange s
421 s = p;
422 p = r;
423 r = s;
424 }
425
426 return result;
427 }
static std::vector< polyn_gf2m > sqmod_init(const polyn_gf2m &g)
Definition: polyn_gf2m.cpp:289

References get_degree(), get_sp_field(), m_sp_field, set_coef(), sqmod(), and sqmod_init().

Referenced by polyn_gf2m().

◆ eea_with_coefficients()

std::pair< polyn_gf2m, polyn_gf2m > Botan::polyn_gf2m::eea_with_coefficients ( const polyn_gf2m p,
const polyn_gf2m g,
int  break_deg 
)
static

countermeasure against the low weight attacks for w=4, w=6 and w=8. Higher values are not covered since for w=8 we already have a probability for a positive of 1/n^3 from random ciphertexts with the given weight. For w = 10 it would be 1/n^4 and so on. Thus attacks based on such high values of w are considered impractical.

The outer test for the degree of u ( Omega in the paper ) needs not to be disguised. Each of the three is performed at most once per EEA (syndrome inversion) execution, the attacker knows this already when preparing the ciphertext with the given weight. Inside these three cases however, we must use timing neutral (branch free) operations to implement the condition detection and the counteractions.

Condition that the EEA would break now

Now come the conditions for all odd coefficients of this sigma candiate. If they are all fulfilled, then we know that we have a low weight error vector, since the key-equation solving EEA is skipped if the degree of tau^2 is low (=m_deg(u0)) and all its odd cofficients are zero (they would cause "full-length" contributions from the square root computation).

Definition at line 448 of file polyn_gf2m.cpp.

449 {
450
451 std::shared_ptr<GF2m_Field> m_sp_field = g.m_sp_field;
452 int i, j, dr, du, delta;
453 gf2m a;
454 polyn_gf2m aux;
455
456 // initialisation of the local variables
457 // r0 <- g, r1 <- p, u0 <- 0, u1 <- 1
458 dr = g.get_degree();
459
460 BOTAN_ASSERT(dr > 3, "Valid polynomial");
461
462 polyn_gf2m r0(dr, g.m_sp_field);
463 polyn_gf2m r1(dr - 1, g.m_sp_field);
464 polyn_gf2m u0(dr - 1, g.m_sp_field);
465 polyn_gf2m u1(dr - 1, g.m_sp_field);
466
467 r0 = g;
468 r1 = p;
469 u0.set_to_zero();
470 u1.set_to_zero();
471 (*&u1).set_coef( 0, 1);
472 u1.set_degree( 0);
473
474
475 // invariants:
476 // r1 = u1 * p + v1 * g
477 // r0 = u0 * p + v0 * g
478 // and m_deg(u1) = m_deg(g) - m_deg(r0)
479 // It stops when m_deg (r1) <t (m_deg (r0)> = t)
480 // And therefore m_deg (u1) = m_deg (g) - m_deg (r0) <m_deg (g) - break_deg
481 du = 0;
482 dr = r1.get_degree();
483 delta = r0.get_degree() - dr;
484
485
486 while (dr >= break_deg)
487 {
488
489 for (j = delta; j >= 0; --j)
490 {
491 a = m_sp_field->gf_div(r0[dr + j], r1[dr]);
492 if (a != 0)
493 {
494 gf2m la = m_sp_field->gf_log(a);
495 // u0(z) <- u0(z) + a * u1(z) * z^j
496 for (i = 0; i <= du; ++i)
497 {
498 u0[i + j] ^= m_sp_field->gf_mul_zrz(la, u1[i]);
499 }
500 // r0(z) <- r0(z) + a * r1(z) * z^j
501 for (i = 0; i <= dr; ++i)
502 {
503 r0[i + j] ^= m_sp_field->gf_mul_zrz(la, r1[i]);
504 }
505 }
506 } // end loop over j
507
508 if(break_deg != 1) /* key eq. solving */
509 {
510 /* [ssms_icisc09] Countermeasure
511 * d_break from paper equals break_deg - 1
512 * */
513
514 volatile gf2m fake_elem = 0x01;
515 volatile gf2m cond1, cond2;
516 int trgt_deg = r1.get_degree() - 1;
517 r0.calc_degree_secure();
518 u0.calc_degree_secure();
519 if(!(g.get_degree() % 2))
520 {
521 /* t even */
522 cond1 = r0.get_degree() < break_deg - 1;
523 }
524 else
525 {
526 /* t odd */
527 cond1 = r0.get_degree() < break_deg;
528 cond2 = u0.get_degree() < break_deg - 1;
529 cond1 &= cond2;
530 }
531 /* expand cond1 to a full mask */
532 gf2m mask = generate_gf2m_mask(cond1);
533 fake_elem &= mask;
534 r0.patchup_deg_secure(trgt_deg, fake_elem);
535 }
536 if(break_deg == 1) /* syndrome inversion */
537 {
538 volatile gf2m fake_elem = 0x00;
539 volatile uint32_t trgt_deg = 0;
540 r0.calc_degree_secure();
541 u0.calc_degree_secure();
542 /**
543 * countermeasure against the low weight attacks for w=4, w=6 and w=8.
544 * Higher values are not covered since for w=8 we already have a
545 * probability for a positive of 1/n^3 from random ciphertexts with the
546 * given weight. For w = 10 it would be 1/n^4 and so on. Thus attacks
547 * based on such high values of w are considered impractical.
548 *
549 * The outer test for the degree of u ( Omega in the paper ) needs not to
550 * be disguised. Each of the three is performed at most once per EEA
551 * (syndrome inversion) execution, the attacker knows this already when
552 * preparing the ciphertext with the given weight. Inside these three
553 * cases however, we must use timing neutral (branch free) operations to
554 * implement the condition detection and the counteractions.
555 *
556 */
557 if(u0.get_degree() == 4)
558 {
559 uint32_t mask = 0;
560 /**
561 * Condition that the EEA would break now
562 */
563 int cond_r = r0.get_degree() == 0;
564 /**
565 * Now come the conditions for all odd coefficients of this sigma
566 * candiate. If they are all fulfilled, then we know that we have a low
567 * weight error vector, since the key-equation solving EEA is skipped if
568 * the degree of tau^2 is low (=m_deg(u0)) and all its odd cofficients are
569 * zero (they would cause "full-length" contributions from the square
570 * root computation).
571 */
572 // Condition for the coefficient to Y to be cancelled out by the
573 // addition of Y before the square root computation:
574 int cond_u1 = m_sp_field->gf_mul(u0.coeff[1], m_sp_field->gf_inv(r0.coeff[0])) == 1;
575
576 // Condition sigma_3 = 0:
577 int cond_u3 = u0.coeff[3] == 0;
578 // combine the conditions:
579 cond_r &= (cond_u1 & cond_u3);
580 // mask generation:
581 mask = expand_mask_16bit(cond_r);
582 trgt_deg = 2 & mask;
583 fake_elem = 1 & mask;
584 }
585 else if(u0.get_degree() == 6)
586 {
587 uint32_t mask = 0;
588 int cond_r= r0.get_degree() == 0;
589 int cond_u1 = m_sp_field->gf_mul(u0.coeff[1], m_sp_field->gf_inv(r0.coeff[0])) == 1;
590 int cond_u3 = u0.coeff[3] == 0;
591
592 int cond_u5 = u0.coeff[5] == 0;
593
594 cond_r &= (cond_u1 & cond_u3 & cond_u5);
595 mask = expand_mask_16bit(cond_r);
596 trgt_deg = 4 & mask;
597 fake_elem = 1 & mask;
598 }
599 else if(u0.get_degree() == 8)
600 {
601 uint32_t mask = 0;
602 int cond_r= r0.get_degree() == 0;
603 int cond_u1 = m_sp_field->gf_mul(u0[1], m_sp_field->gf_inv(r0[0])) == 1;
604 int cond_u3 = u0.coeff[3] == 0;
605
606 int cond_u5 = u0.coeff[5] == 0;
607
608 int cond_u7 = u0.coeff[7] == 0;
609
610 cond_r &= (cond_u1 & cond_u3 & cond_u5 & cond_u7);
611 mask = expand_mask_16bit(cond_r);
612 trgt_deg = 6 & mask;
613 fake_elem = 1 & mask;
614 }
615 r0.patchup_deg_secure(trgt_deg, fake_elem);
616 }
617 // exchange
618 aux = r0; r0 = r1; r1 = aux;
619 aux = u0; u0 = u1; u1 = aux;
620
621 du = du + delta;
622 delta = 1;
623 while (r1[dr - delta] == 0)
624 {
625 delta++;
626 }
627
628
629 dr -= delta;
630 } /* end while loop (dr >= break_deg) */
631
632
633 u1.set_degree( du);
634 r1.set_degree( dr);
635 //return u1 and r1;
636 return std::make_pair(u1,r1); // coefficients u,v
637 }
#define BOTAN_ASSERT(expr, assertion_made)
Definition: assert.h:55

References BOTAN_ASSERT, calc_degree_secure(), coeff, Botan::expand_mask_16bit(), get_degree(), m_sp_field, patchup_deg_secure(), set_coef(), and set_to_zero().

◆ encode() [1/2]

secure_vector< uint8_t > Botan::polyn_gf2m::encode ( ) const

Definition at line 769 of file polyn_gf2m.cpp.

770 {
771 secure_vector<uint8_t> result;
772
773 if(m_deg < 1)
774 {
775 result.push_back(0);
776 result.push_back(0);
777 return result;
778 }
779
780 uint32_t len = m_deg+1;
781 for(unsigned i = 0; i < len; i++)
782 {
783 // "big endian" encoding of the GF(2^m) elements
784 result.push_back(get_byte(0, coeff[i]));
785 result.push_back(get_byte(1, coeff[i]));
786 }
787 return result;
788 }
constexpr uint8_t get_byte(size_t byte_num, T input)
Definition: loadstor.h:41

References coeff, Botan::get_byte(), and m_deg.

◆ encode() [2/2]

void Botan::polyn_gf2m::encode ( uint32_t  min_numo_coeffs,
uint8_t *  mem,
uint32_t  mem_len 
) const

◆ eval()

gf2m Botan::polyn_gf2m::eval ( gf2m  a)

Definition at line 254 of file polyn_gf2m.cpp.

255 {
256 return eval_aux(&this->coeff[0], a, this->m_deg, this->m_sp_field);
257 }

References m_deg, and m_sp_field.

◆ get_coef()

gf2m Botan::polyn_gf2m::get_coef ( size_t  i) const
inline

Definition at line 95 of file polyn_gf2m.h.

95{ return coeff[i]; }

References coeff.

◆ get_degree()

int Botan::polyn_gf2m::get_degree ( ) const

Definition at line 228 of file polyn_gf2m.cpp.

229 {
230 int d = static_cast<int>(this->coeff.size()) - 1;
231 while ((d >= 0) && (this->coeff[d] == 0))
232 --d;
233 const_cast<polyn_gf2m*>(this)->m_deg = d;
234 return d;
235 }

References coeff, and m_deg.

Referenced by degppf(), eea_with_coefficients(), Botan::mceliece_decrypt(), polyn_gf2m(), sqmod(), sqmod_init(), sqrt_mod_init(), Botan::syndrome_init(), and to_string().

◆ get_lead_coef()

gf2m Botan::polyn_gf2m::get_lead_coef ( ) const
inline

Definition at line 93 of file polyn_gf2m.h.

93{ return coeff[m_deg]; }

References coeff, and m_deg.

◆ get_sp_field()

std::shared_ptr< GF2m_Field > Botan::polyn_gf2m::get_sp_field ( ) const
inline

Definition at line 86 of file polyn_gf2m.h.

87 { return m_sp_field; }

References m_sp_field.

Referenced by degppf(), Botan::mceliece_decrypt(), sqmod_init(), and sqrt_mod_init().

◆ operator!=()

bool Botan::polyn_gf2m::operator!= ( const polyn_gf2m other) const
inline

Definition at line 66 of file polyn_gf2m.h.

66{ return !(*this == other); }

◆ operator=() [1/2]

polyn_gf2m & Botan::polyn_gf2m::operator= ( const polyn_gf2m )
default

◆ operator=() [2/2]

polyn_gf2m & Botan::polyn_gf2m::operator= ( polyn_gf2m &&  other)
inline

Definition at line 73 of file polyn_gf2m.h.

74 {
75 if(this != &other)
76 {
77 this->swap(other);
78 }
79 return *this;
80 }

References swap().

◆ operator==()

bool Botan::polyn_gf2m::operator== ( const polyn_gf2m other) const

Definition at line 797 of file polyn_gf2m.cpp.

798 {
799 if(m_deg != other.m_deg || coeff != other.coeff)
800 {
801 return false;
802 }
803 return true;
804 }

References coeff, and m_deg.

◆ operator[]() [1/2]

gf2m & Botan::polyn_gf2m::operator[] ( size_t  i)
inline

Definition at line 89 of file polyn_gf2m.h.

89{ return coeff[i]; }

References coeff.

◆ operator[]() [2/2]

gf2m Botan::polyn_gf2m::operator[] ( size_t  i) const
inline

Definition at line 91 of file polyn_gf2m.h.

91{ return coeff[i]; }

References coeff.

◆ patchup_deg_secure()

void Botan::polyn_gf2m::patchup_deg_secure ( uint32_t  trgt_deg,
volatile gf2m  patch_elem 
)

Definition at line 429 of file polyn_gf2m.cpp.

430 {
431 uint32_t i;
432 if(this->coeff.size() < trgt_deg)
433 {
434 return;
435 }
436 for(i = 0; i < this->coeff.size(); i++)
437 {
438 uint32_t equal, equal_mask;
439 this->coeff[i] |= patch_elem;
440 equal = (i == trgt_deg);
441 equal_mask = expand_mask_16bit(equal);
442 patch_elem &= ~equal_mask;
443 }
444 this->calc_degree_secure();
445 }
int calc_degree_secure() const
Definition: polyn_gf2m.cpp:46

References calc_degree_secure(), and Botan::expand_mask_16bit().

Referenced by eea_with_coefficients().

◆ set_coef()

void Botan::polyn_gf2m::set_coef ( size_t  i,
gf2m  v 
)
inline

Definition at line 97 of file polyn_gf2m.h.

98 {
99 coeff[i] = v;
100 }

References coeff.

Referenced by degppf(), eea_with_coefficients(), polyn_gf2m(), sqmod(), sqmod_init(), and sqrt_mod_init().

◆ set_to_zero()

void Botan::polyn_gf2m::set_to_zero ( )

Definition at line 222 of file polyn_gf2m.cpp.

223 {
224 clear_mem(&this->coeff[0], this->coeff.size());
225 this->m_deg = -1;
226 }
void clear_mem(T *ptr, size_t n)
Definition: mem_ops.h:115

References Botan::clear_mem(), coeff, and m_deg.

Referenced by eea_with_coefficients().

◆ sqmod()

polyn_gf2m Botan::polyn_gf2m::sqmod ( const std::vector< polyn_gf2m > &  sq,
int  d 
)

Definition at line 323 of file polyn_gf2m.cpp.

324 {
325 int i, j;
326 gf2m la;
327 std::shared_ptr<GF2m_Field> sp_field = this->m_sp_field;
328
329 polyn_gf2m result(d - 1, sp_field);
330 // terms of low degree
331 for (i = 0; i < d / 2; ++i)
332 {
333 (*&result).set_coef( i * 2, sp_field->gf_square((*this)[i]));
334 }
335
336 // terms of high degree
337 for (; i < d; ++i)
338 {
339 gf2m lpi = (*this)[i];
340 if (lpi != 0)
341 {
342 lpi = sp_field->gf_log(lpi);
343 la = sp_field->gf_mul_rrr(lpi, lpi);
344 for (j = 0; j < d; ++j)
345 {
346 result[j] ^= sp_field->gf_mul_zrz(la, sq[i][j]);
347 }
348 }
349 }
350
351 // Update degre
352 result.set_degree( d - 1);
353 while ((result.get_degree() >= 0) && (result[result.get_degree()] == 0))
354 result.set_degree( result.get_degree() - 1);
355 return result;
356 }

References get_degree(), m_sp_field, and set_coef().

Referenced by degppf(), and sqrt_mod_init().

◆ sqmod_init()

std::vector< polyn_gf2m > Botan::polyn_gf2m::sqmod_init ( const polyn_gf2m g)
static

Definition at line 289 of file polyn_gf2m.cpp.

290 {
291 std::vector<polyn_gf2m> sq;
292 const int signed_deg = g.get_degree();
293 if(signed_deg <= 0)
294 throw Invalid_Argument("cannot compute sqmod for such low degree");
295
296 const uint32_t d = static_cast<uint32_t>(signed_deg);
297 uint32_t t = g.m_deg;
298 // create t zero polynomials
299 uint32_t i;
300 for (i = 0; i < t; ++i)
301 {
302 sq.push_back(polyn_gf2m(t+1, g.get_sp_field()));
303 }
304 for (i = 0; i < d / 2; ++i)
305 {
306 sq[i].set_degree( 2 * i);
307 (*&sq[i]).set_coef( 2 * i, 1);
308 }
309
310 for (; i < d; ++i)
311 {
312 clear_mem(&sq[i].coeff[0], 2);
313 copy_mem(&sq[i].coeff[0] + 2, &sq[i - 1].coeff[0], d);
314 sq[i].set_degree( sq[i - 1].get_degree() + 2);
315 polyn_gf2m::remainder(sq[i], g);
316 }
317 return sq;
318 }
void copy_mem(T *out, const T *in, size_t n)
Definition: mem_ops.h:133

References Botan::clear_mem(), coeff, Botan::copy_mem(), get_degree(), get_sp_field(), m_deg, polyn_gf2m(), and set_coef().

Referenced by degppf(), and sqrt_mod_init().

◆ sqrt_mod_init()

std::vector< polyn_gf2m > Botan::polyn_gf2m::sqrt_mod_init ( const polyn_gf2m g)
static

Definition at line 676 of file polyn_gf2m.cpp.

677 {
678 uint32_t i, t;
679 uint32_t nb_polyn_sqrt_mat;
680 std::shared_ptr<GF2m_Field> m_sp_field = g.m_sp_field;
681 std::vector<polyn_gf2m> result;
682 t = g.get_degree();
683 nb_polyn_sqrt_mat = t/2;
684
685 std::vector<polyn_gf2m> sq_aux = polyn_gf2m::sqmod_init(g);
686
687
688 polyn_gf2m p( t - 1, g.get_sp_field());
689 p.set_degree( 1);
690
691 (*&p).set_coef( 1, 1);
692 // q(z) = 0, p(z) = z
693 for (i = 0; i < t * m_sp_field->get_extension_degree() - 1; ++i)
694 {
695 // q(z) <- p(z)^2 mod g(z)
696 polyn_gf2m q = p.sqmod(sq_aux, t);
697 // q(z) <-> p(z)
698 polyn_gf2m aux = q;
699 q = p;
700 p = aux;
701 }
702 // p(z) = z^(2^(tm-1)) mod g(z) = sqrt(z) mod g(z)
703
704 for (i = 0; i < nb_polyn_sqrt_mat; ++i)
705 {
706 result.push_back(polyn_gf2m(t - 1, g.get_sp_field()));
707 }
708
709 result[0] = p;
710 result[0].get_degree();
711 for(i = 1; i < nb_polyn_sqrt_mat; i++)
712 {
713 result[i] = result[i - 1];
714 result[i].poly_shiftmod(g),
715 result[i].get_degree();
716 }
717
718 return result;
719 }

References get_degree(), get_sp_field(), m_sp_field, polyn_gf2m(), set_coef(), sqmod(), and sqmod_init().

Referenced by Botan::generate_mceliece_key().

◆ swap()

void Botan::polyn_gf2m::swap ( polyn_gf2m other)

Definition at line 790 of file polyn_gf2m.cpp.

791 {
792 std::swap(this->m_deg, other.m_deg);
793 std::swap(this->m_sp_field, other.m_sp_field);
794 std::swap(this->coeff, other.coeff);
795 }

References coeff, m_deg, and m_sp_field.

Referenced by operator=(), and polyn_gf2m().

◆ to_string()

std::string Botan::polyn_gf2m::to_string ( ) const

Definition at line 104 of file polyn_gf2m.cpp.

105 {
106 int d = get_degree();
107 std::string result;
108 for(int i = 0; i <= d; i ++)
109 {
110 result += std::to_string(this->coeff[i]);
111 if(i != d)
112 {
113 result += ", ";
114 }
115 }
116 return result;
117 }
std::string to_string(const BER_Object &obj)
Definition: asn1_obj.cpp:213

References coeff, get_degree(), and Botan::ASN1::to_string().

Member Data Documentation

◆ coeff

secure_vector<gf2m> Botan::polyn_gf2m::coeff

◆ m_deg

int Botan::polyn_gf2m::m_deg

◆ m_sp_field

std::shared_ptr<GF2m_Field> Botan::polyn_gf2m::m_sp_field

The documentation for this class was generated from the following files: