Botan 3.0.0
Crypto and TLS for C&
Public Member Functions | Static Public Member Functions | 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
 
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_Field > get_sp_field () const
 
bool operator!= (const polyn_gf2m &other) const
 
polyn_gf2m & operator= (const polyn_gf2m &)=default
 
polyn_gf2m & operator= (polyn_gf2m &&other)
 
bool operator== (const polyn_gf2m &other) const
 
gf2m & operator[] (size_t i)
 
gf2m operator[] (size_t i) const
 
void patchup_deg_secure (uint32_t trgt_deg, gf2m patch_elem)
 
 polyn_gf2m ()
 
 polyn_gf2m (const secure_vector< uint8_t > &encoded, const std::shared_ptr< GF2m_Field > &sp_field)
 
 polyn_gf2m (const std::shared_ptr< GF2m_Field > &sp_field)
 
 polyn_gf2m (const uint8_t *mem, uint32_t mem_len, const std::shared_ptr< GF2m_Field > &sp_field)
 
 polyn_gf2m (int d, const std::shared_ptr< GF2m_Field > &sp_field)
 
 polyn_gf2m (int degree, const uint8_t *mem, size_t mem_byte_len, const 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, const 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)
 

Static Public Member Functions

static size_t degppf (const polyn_gf2m &g)
 
static std::pair< polyn_gf2m, polyn_gf2m > eea_with_coefficients (const polyn_gf2m &p, const polyn_gf2m &g, int break_deg)
 
static std::vector< polyn_gf2m > sqmod_init (const polyn_gf2m &g)
 
static std::vector< polyn_gf2m > sqrt_mod_init (const polyn_gf2m &g)
 

Detailed Description

Definition at line 26 of file polyn_gf2m.h.

Constructor & Destructor Documentation

◆ polyn_gf2m() [1/9]

Botan::polyn_gf2m::polyn_gf2m ( const std::shared_ptr< GF2m_Field > &  sp_field)
explicit

create a zero polynomial:

Definition at line 135 of file polyn_gf2m.cpp.

135 :
136 m_deg(-1), m_coeff(1), m_sp_field(sp_field)
137 {}

◆ polyn_gf2m() [2/9]

Botan::polyn_gf2m::polyn_gf2m ( )
inline

Definition at line 34 of file polyn_gf2m.h.

34: 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,
const std::shared_ptr< GF2m_Field > &  sp_field 
)

Definition at line 705 of file polyn_gf2m.cpp.

706 :
707 m_sp_field(sp_field)
708 {
709 if(encoded.size() % 2)
710 {
711 throw Decoding_Error("encoded polynomial has odd length");
712 }
713 for(uint32_t i = 0; i < encoded.size(); i += 2)
714 {
715 gf2m el = (encoded[i] << 8) | encoded[i + 1];
716 m_coeff.push_back(el);
717 }
718 get_degree();
719
720 }
Botan::polyn_gf2m::get_degree
int get_degree() const
Definition: polyn_gf2m.cpp:179
Botan::gf2m
uint16_t gf2m
Definition: gf2m_small_m.h:20

References get_degree().

◆ polyn_gf2m() [4/9]

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

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

Definition at line 93 of file polyn_gf2m.cpp.

94 :m_deg(-1),
95 m_coeff(d+1),
96 m_sp_field(sp_field)
97 {
98 }

◆ polyn_gf2m() [5/9]

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

◆ polyn_gf2m() [6/9]

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

random irreducible polynomial of degree t

Definition at line 590 of file polyn_gf2m.cpp.

591 :m_deg(static_cast<int>(t)),
592 m_coeff(t+1),
593 m_sp_field(sp_field)
594 {
595 this->set_coef(t, 1);
596 for(;;)
597 {
598 for(size_t i = 0; i < t; ++i)
599 {
600 this->set_coef(i, random_code_element(sp_field->get_cardinality(), rng));
601 }
602
603 const size_t degree = polyn_gf2m::degppf(*this);
604
605 if(degree >= t)
606 break;
607 }
608 }
Botan::polyn_gf2m::set_coef
void set_coef(size_t i, gf2m v)
Definition: polyn_gf2m.h:96
Botan::polyn_gf2m::degppf
static size_t degppf(const polyn_gf2m &g)
Definition: polyn_gf2m.cpp:341
Botan::random_code_element
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,
const std::shared_ptr< GF2m_Field > &  sp_field 
)

decode a polynomial from memory:

Definition at line 108 of file polyn_gf2m.cpp.

108 :
109 m_deg(-1), m_sp_field(sp_field)
110 {
111 if(mem_len % sizeof(gf2m))
112 {
113 throw Decoding_Error("illegal length of memory to decode ");
114 }
115
116 uint32_t size = (mem_len / sizeof(this->m_coeff[0])) ;
117 this->m_coeff = secure_vector<gf2m>(size);
118 this->m_deg = -1;
119 for(uint32_t i = 0; i < size; i++)
120 {
121 this->m_coeff[i] = decode_gf2m(mem);
122 mem += sizeof(this->m_coeff[0]);
123 }
124 for(uint32_t i = 0; i < size; i++)
125 {
126 if(this->m_coeff[i] >= (1 << sp_field->get_extension_degree()))
127 {
128 throw Decoding_Error("error decoding polynomial");
129 }
130 }
131 this->get_degree();
132 }
Botan::decode_gf2m
gf2m decode_gf2m(const uint8_t *mem)
Definition: gf2m_small_m.cpp:103

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

◆ polyn_gf2m() [8/9]

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

create a polynomial from memory area (encoded)

Definition at line 139 of file polyn_gf2m.cpp.

140 :m_sp_field(sp_field)
141 {
142 uint32_t j, k, l;
143 gf2m a;
144 uint32_t polyn_size;
145 polyn_size = degree + 1;
146 if(polyn_size * sp_field->get_extension_degree() > 8 * mem_byte_len)
147 {
148 throw Decoding_Error("memory vector for polynomial has wrong size");
149 }
150 this->m_coeff = secure_vector<gf2m>(degree+1);
151 gf2m ext_deg = static_cast<gf2m>(this->m_sp_field->get_extension_degree());
152 for (l = 0; l < polyn_size; l++)
153 {
154 k = (l * ext_deg) / 8;
155
156 j = (l * ext_deg) % 8;
157 a = mem[k] >> j;
158 if (j + ext_deg > 8)
159 {
160 a ^= mem[k + 1] << (8- j);
161 }
162 if(j + ext_deg > 16)
163 {
164 a ^= mem[k + 2] << (16- j);
165 }
166 a &= ((1 << ext_deg) - 1);
167 (*this).set_coef( l, a);
168 }
169
170 this->get_degree();
171 }

References get_degree().

◆ polyn_gf2m() [9/9]

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

Definition at line 67 of file polyn_gf2m.h.

68 {
69 this->swap(other);
70 }
Botan::polyn_gf2m::swap
void swap(polyn_gf2m &other)
Definition: polyn_gf2m.cpp:742

References swap().

Member Function Documentation

◆ add_to_coef()

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

Definition at line 101 of file polyn_gf2m.h.

102 {
103 m_coeff[i] ^= v;
104 }

◆ 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->m_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->m_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 }
Botan::polyn_gf2m::polyn_gf2m
polyn_gf2m()
Definition: polyn_gf2m.h:34
Botan::expand_mask_16bit
uint16_t expand_mask_16bit(T tst)
Definition: code_based_util.h:25

References Botan::expand_mask_16bit().

Referenced by eea_with_coefficients(), and patchup_deg_secure().

◆ degppf()

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

Definition at line 341 of file polyn_gf2m.cpp.

342 {
343 polyn_gf2m s(g.get_sp_field());
344
345 const size_t ext_deg = g.m_sp_field->get_extension_degree();
346 const int d = g.get_degree();
347 std::vector<polyn_gf2m> u = polyn_gf2m::sqmod_init(g);
348
349 polyn_gf2m p(d - 1, g.m_sp_field);
350
351 p.set_degree(1);
352 (*&p).set_coef(1, 1);
353 size_t result = static_cast<size_t>(d);
354 for(size_t i = 1; i <= (d / 2) * ext_deg; ++i)
355 {
356 polyn_gf2m r = p.sqmod(u, d);
357 if ((i % ext_deg) == 0)
358 {
359 r[1] ^= 1;
360 r.get_degree(); // The degree may change
361 s = polyn_gf2m::gcd( g, r);
362
363 if(s.get_degree() > 0)
364 {
365 result = i / ext_deg;
366 break;
367 }
368 r[1] ^= 1;
369 r.get_degree(); // The degree may change
370 }
371 // No need for the exchange s
372 s = p;
373 p = r;
374 r = s;
375 }
376
377 return result;
378 }
Botan::polyn_gf2m::sqmod_init
static std::vector< polyn_gf2m > sqmod_init(const polyn_gf2m &g)
Definition: polyn_gf2m.cpp:240

References get_degree(), get_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 399 of file polyn_gf2m.cpp.

400 {
401
402 std::shared_ptr<GF2m_Field> m_sp_field = g.m_sp_field;
403 int i, j, dr, du, delta;
404 gf2m a;
405 polyn_gf2m aux;
406
407 // initialisation of the local variables
408 // r0 <- g, r1 <- p, u0 <- 0, u1 <- 1
409 dr = g.get_degree();
410
411 BOTAN_ASSERT(dr > 3, "Valid polynomial");
412
413 polyn_gf2m r0(dr, g.m_sp_field);
414 polyn_gf2m r1(dr - 1, g.m_sp_field);
415 polyn_gf2m u0(dr - 1, g.m_sp_field);
416 polyn_gf2m u1(dr - 1, g.m_sp_field);
417
418 r0 = g;
419 r1 = p;
420 u0.set_to_zero();
421 u1.set_to_zero();
422 (*&u1).set_coef( 0, 1);
423 u1.set_degree( 0);
424
425
426 // invariants:
427 // r1 = u1 * p + v1 * g
428 // r0 = u0 * p + v0 * g
429 // and m_deg(u1) = m_deg(g) - m_deg(r0)
430 // It stops when m_deg (r1) <t (m_deg (r0)> = t)
431 // And therefore m_deg (u1) = m_deg (g) - m_deg (r0) <m_deg (g) - break_deg
432 du = 0;
433 dr = r1.get_degree();
434 delta = r0.get_degree() - dr;
435
436
437 while (dr >= break_deg)
438 {
439
440 for (j = delta; j >= 0; --j)
441 {
442 a = m_sp_field->gf_div(r0[dr + j], r1[dr]);
443 if (a != 0)
444 {
445 gf2m la = m_sp_field->gf_log(a);
446 // u0(z) <- u0(z) + a * u1(z) * z^j
447 for (i = 0; i <= du; ++i)
448 {
449 u0[i + j] ^= m_sp_field->gf_mul_zrz(la, u1[i]);
450 }
451 // r0(z) <- r0(z) + a * r1(z) * z^j
452 for (i = 0; i <= dr; ++i)
453 {
454 r0[i + j] ^= m_sp_field->gf_mul_zrz(la, r1[i]);
455 }
456 }
457 } // end loop over j
458
459 if(break_deg != 1) /* key eq. solving */
460 {
461 /* [ssms_icisc09] Countermeasure
462 * d_break from paper equals break_deg - 1
463 * */
464
465 volatile gf2m fake_elem = 0x01;
466 volatile gf2m cond1, cond2;
467 int trgt_deg = r1.get_degree() - 1;
468 r0.calc_degree_secure();
469 u0.calc_degree_secure();
470 if(!(g.get_degree() % 2))
471 {
472 /* t even */
473 cond1 = r0.get_degree() < break_deg - 1;
474 }
475 else
476 {
477 /* t odd */
478 cond1 = r0.get_degree() < break_deg;
479 cond2 = u0.get_degree() < break_deg - 1;
480 cond1 = cond1 & cond2;
481 }
482 /* expand cond1 to a full mask */
483 gf2m mask = generate_gf2m_mask(cond1);
484 fake_elem = fake_elem & mask;
485 r0.patchup_deg_secure(trgt_deg, fake_elem);
486 }
487 if(break_deg == 1) /* syndrome inversion */
488 {
489 volatile gf2m fake_elem = 0x00;
490 volatile uint32_t trgt_deg = 0;
491 r0.calc_degree_secure();
492 u0.calc_degree_secure();
493 /**
494 * countermeasure against the low weight attacks for w=4, w=6 and w=8.
495 * Higher values are not covered since for w=8 we already have a
496 * probability for a positive of 1/n^3 from random ciphertexts with the
497 * given weight. For w = 10 it would be 1/n^4 and so on. Thus attacks
498 * based on such high values of w are considered impractical.
499 *
500 * The outer test for the degree of u ( Omega in the paper ) needs not to
501 * be disguised. Each of the three is performed at most once per EEA
502 * (syndrome inversion) execution, the attacker knows this already when
503 * preparing the ciphertext with the given weight. Inside these three
504 * cases however, we must use timing neutral (branch free) operations to
505 * implement the condition detection and the counteractions.
506 *
507 */
508 if(u0.get_degree() == 4)
509 {
510 uint32_t mask = 0;
511 /**
512 * Condition that the EEA would break now
513 */
514 int cond_r = r0.get_degree() == 0;
515 /**
516 * Now come the conditions for all odd coefficients of this sigma
517 * candiate. If they are all fulfilled, then we know that we have a low
518 * weight error vector, since the key-equation solving EEA is skipped if
519 * the degree of tau^2 is low (=m_deg(u0)) and all its odd cofficients are
520 * zero (they would cause "full-length" contributions from the square
521 * root computation).
522 */
523 // Condition for the coefficient to Y to be cancelled out by the
524 // addition of Y before the square root computation:
525 int cond_u1 = m_sp_field->gf_mul(u0.m_coeff[1], m_sp_field->gf_inv(r0.m_coeff[0])) == 1;
526
527 // Condition sigma_3 = 0:
528 int cond_u3 = u0.m_coeff[3] == 0;
529 // combine the conditions:
530 cond_r &= (cond_u1 & cond_u3);
531 // mask generation:
532 mask = expand_mask_16bit(cond_r);
533 trgt_deg = 2 & mask;
534 fake_elem = 1 & mask;
535 }
536 else if(u0.get_degree() == 6)
537 {
538 uint32_t mask = 0;
539 int cond_r= r0.get_degree() == 0;
540 int cond_u1 = m_sp_field->gf_mul(u0.m_coeff[1], m_sp_field->gf_inv(r0.m_coeff[0])) == 1;
541 int cond_u3 = u0.m_coeff[3] == 0;
542
543 int cond_u5 = u0.m_coeff[5] == 0;
544
545 cond_r &= (cond_u1 & cond_u3 & cond_u5);
546 mask = expand_mask_16bit(cond_r);
547 trgt_deg = 4 & mask;
548 fake_elem = 1 & mask;
549 }
550 else if(u0.get_degree() == 8)
551 {
552 uint32_t mask = 0;
553 int cond_r= r0.get_degree() == 0;
554 int cond_u1 = m_sp_field->gf_mul(u0[1], m_sp_field->gf_inv(r0[0])) == 1;
555 int cond_u3 = u0.m_coeff[3] == 0;
556
557 int cond_u5 = u0.m_coeff[5] == 0;
558
559 int cond_u7 = u0.m_coeff[7] == 0;
560
561 cond_r &= (cond_u1 & cond_u3 & cond_u5 & cond_u7);
562 mask = expand_mask_16bit(cond_r);
563 trgt_deg = 6 & mask;
564 fake_elem = 1 & mask;
565 }
566 r0.patchup_deg_secure(trgt_deg, fake_elem);
567 }
568 // exchange
569 aux = r0; r0 = r1; r1 = aux;
570 aux = u0; u0 = u1; u1 = aux;
571
572 du = du + delta;
573 delta = 1;
574 while (r1[dr - delta] == 0)
575 {
576 delta++;
577 }
578
579
580 dr -= delta;
581 } /* end while loop (dr >= break_deg) */
582
583
584 u1.set_degree( du);
585 r1.set_degree( dr);
586 //return u1 and r1;
587 return std::make_pair(u1,r1); // coefficients u,v
588 }
BOTAN_ASSERT
#define BOTAN_ASSERT(expr, assertion_made)
Definition: assert.h:54

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

◆ encode() [1/2]

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

Definition at line 721 of file polyn_gf2m.cpp.

722 {
723 secure_vector<uint8_t> result;
724
725 if(m_deg < 1)
726 {
727 result.push_back(0);
728 result.push_back(0);
729 return result;
730 }
731
732 uint32_t len = m_deg+1;
733 for(unsigned i = 0; i < len; i++)
734 {
735 // "big endian" encoding of the GF(2^m) elements
736 result.push_back(get_byte<0>(m_coeff[i]));
737 result.push_back(get_byte<1>(m_coeff[i]));
738 }
739 return result;
740 }

◆ 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 205 of file polyn_gf2m.cpp.

206 {
207 return eval_aux(&this->m_coeff[0], a, this->m_deg, this->m_sp_field);
208 }

◆ get_coef()

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

Definition at line 94 of file polyn_gf2m.h.

94{ return m_coeff[i]; }

◆ get_degree()

int Botan::polyn_gf2m::get_degree ( ) const

Definition at line 179 of file polyn_gf2m.cpp.

180 {
181 int d = static_cast<int>(this->m_coeff.size()) - 1;
182 while ((d >= 0) && (this->m_coeff[d] == 0))
183 --d;
184 const_cast<polyn_gf2m*>(this)->m_deg = d;
185 return d;
186 }

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

◆ get_lead_coef()

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

Definition at line 92 of file polyn_gf2m.h.

92{ return m_coeff[m_deg]; }

◆ get_sp_field()

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

Definition at line 85 of file polyn_gf2m.h.

86 { return m_sp_field; }

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

◆ operator!=()

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

Definition at line 65 of file polyn_gf2m.h.

65{ 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 72 of file polyn_gf2m.h.

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

References swap().

◆ operator==()

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

Definition at line 749 of file polyn_gf2m.cpp.

750 {
751 if(m_deg != other.m_deg || m_coeff != other.m_coeff)
752 {
753 return false;
754 }
755 return true;
756 }

◆ operator[]() [1/2]

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

Definition at line 88 of file polyn_gf2m.h.

88{ return m_coeff[i]; }

◆ operator[]() [2/2]

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

Definition at line 90 of file polyn_gf2m.h.

90{ return m_coeff[i]; }

◆ patchup_deg_secure()

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

Definition at line 380 of file polyn_gf2m.cpp.

381 {
382 uint32_t i;
383 if(this->m_coeff.size() < trgt_deg)
384 {
385 return;
386 }
387 for(i = 0; i < this->m_coeff.size(); i++)
388 {
389 uint32_t equal, equal_mask;
390 this->m_coeff[i] |= patch_elem;
391 equal = (i == trgt_deg);
392 equal_mask = expand_mask_16bit(equal);
393 patch_elem &= ~equal_mask;
394 }
395 this->calc_degree_secure();
396 }
Botan::polyn_gf2m::calc_degree_secure
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 96 of file polyn_gf2m.h.

97 {
98 m_coeff[i] = v;
99 }

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 173 of file polyn_gf2m.cpp.

174 {
175 clear_mem(&this->m_coeff[0], this->m_coeff.size());
176 this->m_deg = -1;
177 }
Botan::clear_mem
constexpr void clear_mem(T *ptr, size_t n)
Definition: mem_ops.h:115

References Botan::clear_mem().

Referenced by eea_with_coefficients().

◆ sqmod()

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

Definition at line 274 of file polyn_gf2m.cpp.

275 {
276 int i, j;
277 gf2m la;
278 std::shared_ptr<GF2m_Field> sp_field = this->m_sp_field;
279
280 polyn_gf2m result(d - 1, sp_field);
281 // terms of low degree
282 for (i = 0; i < d / 2; ++i)
283 {
284 (*&result).set_coef( i * 2, sp_field->gf_square((*this)[i]));
285 }
286
287 // terms of high degree
288 for (; i < d; ++i)
289 {
290 gf2m lpi = (*this)[i];
291 if (lpi != 0)
292 {
293 lpi = sp_field->gf_log(lpi);
294 la = sp_field->gf_mul_rrr(lpi, lpi);
295 for (j = 0; j < d; ++j)
296 {
297 result[j] ^= sp_field->gf_mul_zrz(la, sq[i][j]);
298 }
299 }
300 }
301
302 // Update degre
303 result.set_degree( d - 1);
304 while ((result.get_degree() >= 0) && (result[result.get_degree()] == 0))
305 result.set_degree( result.get_degree() - 1);
306 return result;
307 }

References get_degree(), 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 240 of file polyn_gf2m.cpp.

241 {
242 std::vector<polyn_gf2m> sq;
243 const int signed_deg = g.get_degree();
244 if(signed_deg <= 0)
245 throw Invalid_Argument("cannot compute sqmod for such low degree");
246
247 const uint32_t d = static_cast<uint32_t>(signed_deg);
248 uint32_t t = g.m_deg;
249 // create t zero polynomials
250 uint32_t i;
251 for (i = 0; i < t; ++i)
252 {
253 sq.push_back(polyn_gf2m(t+1, g.get_sp_field()));
254 }
255 for (i = 0; i < d / 2; ++i)
256 {
257 sq[i].set_degree( 2 * i);
258 (*&sq[i]).set_coef( 2 * i, 1);
259 }
260
261 for (; i < d; ++i)
262 {
263 clear_mem(&sq[i].m_coeff[0], 2);
264 copy_mem(&sq[i].m_coeff[0] + 2, &sq[i - 1].m_coeff[0], d);
265 sq[i].set_degree( sq[i - 1].get_degree() + 2);
266 polyn_gf2m::remainder(sq[i], g);
267 }
268 return sq;
269 }
Botan::copy_mem
constexpr void copy_mem(T *out, const T *in, size_t n)
Definition: mem_ops.h:126

References Botan::clear_mem(), Botan::copy_mem(), get_degree(), get_sp_field(), 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 627 of file polyn_gf2m.cpp.

628 {
629 uint32_t i, t;
630 uint32_t nb_polyn_sqrt_mat;
631 std::shared_ptr<GF2m_Field> m_sp_field = g.m_sp_field;
632 std::vector<polyn_gf2m> result;
633 t = g.get_degree();
634 nb_polyn_sqrt_mat = t/2;
635
636 std::vector<polyn_gf2m> sq_aux = polyn_gf2m::sqmod_init(g);
637
638
639 polyn_gf2m p( t - 1, g.get_sp_field());
640 p.set_degree( 1);
641
642 (*&p).set_coef( 1, 1);
643 // q(z) = 0, p(z) = z
644 for (i = 0; i < t * m_sp_field->get_extension_degree() - 1; ++i)
645 {
646 // q(z) <- p(z)^2 mod g(z)
647 polyn_gf2m q = p.sqmod(sq_aux, t);
648 // q(z) <-> p(z)
649 polyn_gf2m aux = q;
650 q = p;
651 p = aux;
652 }
653 // p(z) = z^(2^(tm-1)) mod g(z) = sqrt(z) mod g(z)
654
655 for (i = 0; i < nb_polyn_sqrt_mat; ++i)
656 {
657 result.push_back(polyn_gf2m(t - 1, g.get_sp_field()));
658 }
659
660 result[0] = p;
661 result[0].get_degree();
662 for(i = 1; i < nb_polyn_sqrt_mat; i++)
663 {
664 result[i] = result[i - 1];
665 result[i].poly_shiftmod(g);
666 result[i].get_degree();
667 }
668
669 return result;
670 }

References get_degree(), get_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 742 of file polyn_gf2m.cpp.

743 {
744 std::swap(this->m_deg, other.m_deg);
745 std::swap(this->m_sp_field, other.m_sp_field);
746 std::swap(this->m_coeff, other.m_coeff);
747 }

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

The documentation for this class was generated from the following files:
Generated by doxygen 1.9.6