Botan 2.13.0 Crypto and TLS for C++11

- Main Page
- Namespaces
- Classes
- Files

- Class List
- Class Index
- Class Hierarchy
- Class Members

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_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, volatile gf2m patch_elem)
| polyn_gf2m (std::shared_ptr< GF2m_Field > sp_field)
| polyn_gf2m ()
| polyn_gf2m (const secure_vector< uint8_t > &encoded, std::shared_ptr< GF2m_Field > sp_field)
| polyn_gf2m (int d, std::shared_ptr< GF2m_Field > sp_field)
| polyn_gf2m (polyn_gf2m const &other)
| polyn_gf2m (size_t t, RandomNumberGenerator &rng, 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 degree, const uint8_t *mem, size_t mem_byte_len, std::shared_ptr< GF2m_Field > sp_field)
| polyn_gf2m (polyn_gf2m &&other)
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_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)

## Public Attributes
secure_vector< gf2m > | coeff
int | m_deg
std::shared_ptr< GF2m_Field > | m_sp_field

## Detailed Description

Definition at line 26 of file polyn_gf2m.h.

## Constructor & Destructor Documentation

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 {}
Botan::polyn_gf2m::m_deg
int m_deg
Definition: polyn_gf2m.h:149
Botan::polyn_gf2m::coeff
secure_vector< gf2m > coeff
Definition: polyn_gf2m.h:152
Botan::polyn_gf2m::m_sp_field
std::shared_ptr< GF2m_Field > m_sp_field
Definition: polyn_gf2m.h:155

Botan::polyn_gf2m::polyn_gf2m | ( |  | ) |
| inline

Definition at line 34 of file polyn_gf2m.h.

Referenced by sqmod_init(), and sqrt_mod_init().

34 : m_deg(-1) {}
Botan::polyn_gf2m::m_deg
int m_deg
Definition: polyn_gf2m.h:149

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.

References get_degree().

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 }
Botan::polyn_gf2m::get_degree
int get_degree() const
Definition: polyn_gf2m.cpp:228
Botan::gf2m
uint16_t gf2m
Definition: gf2m_small_m.h:23
Botan::polyn_gf2m::coeff
secure_vector< gf2m > coeff
Definition: polyn_gf2m.h:152
Botan::polyn_gf2m::m_sp_field
std::shared_ptr< GF2m_Field > m_sp_field
Definition: polyn_gf2m.h:155

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 }
Botan::polyn_gf2m::m_deg
int m_deg
Definition: polyn_gf2m.h:149
Botan::polyn_gf2m::coeff
secure_vector< gf2m > coeff
Definition: polyn_gf2m.h:152
Botan::polyn_gf2m::m_sp_field
std::shared_ptr< GF2m_Field > m_sp_field
Definition: polyn_gf2m.h:155

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 { }
Botan::polyn_gf2m::m_deg
int m_deg
Definition: polyn_gf2m.h:149
Botan::polyn_gf2m::coeff
secure_vector< gf2m > coeff
Definition: polyn_gf2m.h:152
Botan::polyn_gf2m::m_sp_field
std::shared_ptr< GF2m_Field > m_sp_field
Definition: polyn_gf2m.h:155

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.

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

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 }
Botan::polyn_gf2m::m_deg
int m_deg
Definition: polyn_gf2m.h:149
Botan::polyn_gf2m::degppf
size_t degppf(const polyn_gf2m &g)
Definition: polyn_gf2m.cpp:390
Botan::polyn_gf2m::coeff
secure_vector< gf2m > coeff
Definition: polyn_gf2m.h:152
Botan::random_code_element
gf2m random_code_element(uint16_t code_length, RandomNumberGenerator &rng)
Definition: polyn_gf2m.cpp:71
Botan::polyn_gf2m::m_sp_field
std::shared_ptr< GF2m_Field > m_sp_field
Definition: polyn_gf2m.h:155
Botan::polyn_gf2m::set_coef
void set_coef(size_t i, gf2m v)
Definition: polyn_gf2m.h:93

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.

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

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 }
Botan::polyn_gf2m::m_deg
int m_deg
Definition: polyn_gf2m.h:149
Botan::decode_gf2m
gf2m decode_gf2m(const uint8_t *mem)
Definition: gf2m_small_m.cpp:103
Botan::polyn_gf2m::get_degree
int get_degree() const
Definition: polyn_gf2m.cpp:228
Botan::gf2m
uint16_t gf2m
Definition: gf2m_small_m.h:23
Botan::polyn_gf2m::coeff
secure_vector< gf2m > coeff
Definition: polyn_gf2m.h:152
Botan::polyn_gf2m::m_sp_field
std::shared_ptr< GF2m_Field > m_sp_field
Definition: polyn_gf2m.h:155

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.

References coeff, get_degree(), and m_sp_field.

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 }
Botan::polyn_gf2m::get_degree
int get_degree() const
Definition: polyn_gf2m.cpp:228
Botan::gf2m
uint16_t gf2m
Definition: gf2m_small_m.h:23
Botan::polyn_gf2m::coeff
secure_vector< gf2m > coeff
Definition: polyn_gf2m.h:152
Botan::polyn_gf2m::m_sp_field
std::shared_ptr< GF2m_Field > m_sp_field
Definition: polyn_gf2m.h:155

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

Definition at line 64 of file polyn_gf2m.h.

References swap().

65 {
66 this->swap(other);
67 }
Botan::polyn_gf2m::swap
void swap(polyn_gf2m &other)
Definition: polyn_gf2m.cpp:790

## Member Function Documentation

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

Definition at line 98 of file polyn_gf2m.h.

References coeff.

99 {
100 coeff[i] ^= v;
101 }
Botan::polyn_gf2m::coeff
secure_vector< gf2m > coeff
Definition: polyn_gf2m.h:152

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.

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

Referenced by eea_with_coefficients(), and patchup_deg_secure().

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 }
Botan::polyn_gf2m::m_deg
int m_deg
Definition: polyn_gf2m.h:149
Botan::expand_mask_16bit
uint16_t expand_mask_16bit(T tst)
Definition: code_based_util.h:25
Botan::polyn_gf2m::coeff
secure_vector< gf2m > coeff
Definition: polyn_gf2m.h:152
Botan::polyn_gf2m::polyn_gf2m
polyn_gf2m()
Definition: polyn_gf2m.h:34

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

Definition at line 390 of file polyn_gf2m.cpp.

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

Referenced by polyn_gf2m().

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 }
Botan::polyn_gf2m::sqmod_init
static std::vector< polyn_gf2m > sqmod_init(const polyn_gf2m &g)
Definition: polyn_gf2m.cpp:289
Botan::polyn_gf2m::polyn_gf2m
polyn_gf2m()
Definition: polyn_gf2m.h:34
Botan::polyn_gf2m::set_coef
void set_coef(size_t i, gf2m v)
Definition: polyn_gf2m.h:93

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.

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().

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 }
BOTAN_ASSERT
#define BOTAN_ASSERT(expr, assertion_made)
Definition: assert.h:55
Botan::expand_mask_16bit
uint16_t expand_mask_16bit(T tst)
Definition: code_based_util.h:25
Botan::gf2m
uint16_t gf2m
Definition: gf2m_small_m.h:23
Botan::polyn_gf2m::polyn_gf2m
polyn_gf2m()
Definition: polyn_gf2m.h:34
Botan::polyn_gf2m::m_sp_field
std::shared_ptr< GF2m_Field > m_sp_field
Definition: polyn_gf2m.h:155
Botan::polyn_gf2m::set_coef
void set_coef(size_t i, gf2m v)
Definition: polyn_gf2m.h:93

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

Definition at line 769 of file polyn_gf2m.cpp.

References Botan::get_byte(), and m_deg.

Referenced by Botan::McEliece_PrivateKey::private_key_bits().

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 }
Botan::polyn_gf2m::m_deg
int m_deg
Definition: polyn_gf2m.h:149
Botan::get_byte
constexpr uint8_t get_byte(size_t byte_num, T input)
Definition: loadstor.h:41
Botan::polyn_gf2m::coeff
secure_vector< gf2m > coeff
Definition: polyn_gf2m.h:152

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

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

Definition at line 254 of file polyn_gf2m.cpp.

References m_deg, and m_sp_field.

255 {
256 return eval_aux(&this->coeff[0], a, this->m_deg, this->m_sp_field);
257 }
Botan::polyn_gf2m::m_deg
int m_deg
Definition: polyn_gf2m.h:149
Botan::polyn_gf2m::coeff
secure_vector< gf2m > coeff
Definition: polyn_gf2m.h:152
Botan::polyn_gf2m::m_sp_field
std::shared_ptr< GF2m_Field > m_sp_field
Definition: polyn_gf2m.h:155

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

Definition at line 91 of file polyn_gf2m.h.

References coeff.

91 { return coeff[i]; }
Botan::polyn_gf2m::coeff
secure_vector< gf2m > coeff
Definition: polyn_gf2m.h:152

int Botan::polyn_gf2m::get_degree | ( |  | ) | const

Definition at line 228 of file polyn_gf2m.cpp.

References coeff, and m_deg.

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

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 }
Botan::polyn_gf2m::m_deg
int m_deg
Definition: polyn_gf2m.h:149
Botan::polyn_gf2m::coeff
secure_vector< gf2m > coeff
Definition: polyn_gf2m.h:152
Botan::polyn_gf2m::polyn_gf2m
polyn_gf2m()
Definition: polyn_gf2m.h:34

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

Definition at line 89 of file polyn_gf2m.h.

References coeff, and m_deg.

89 { return coeff[m_deg]; }
Botan::polyn_gf2m::m_deg
int m_deg
Definition: polyn_gf2m.h:149
Botan::polyn_gf2m::coeff
secure_vector< gf2m > coeff
Definition: polyn_gf2m.h:152

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

Definition at line 82 of file polyn_gf2m.h.

References m_sp_field.

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

83 { return m_sp_field; }
Botan::polyn_gf2m::m_sp_field
std::shared_ptr< GF2m_Field > m_sp_field
Definition: polyn_gf2m.h:155

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

Definition at line 62 of file polyn_gf2m.h.

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

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

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

Definition at line 69 of file polyn_gf2m.h.

References swap().

70 {
71 if(this != &other)
72 {
73 this->swap(other);
74 }
75 return *this;
76 }
Botan::polyn_gf2m::swap
void swap(polyn_gf2m &other)
Definition: polyn_gf2m.cpp:790

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

Definition at line 797 of file polyn_gf2m.cpp.

References coeff, and m_deg.

798 {
799 if(m_deg != other.m_deg || coeff != other.coeff)
800 {
801 return false;
802 }
803 return true;
804 }
Botan::polyn_gf2m::m_deg
int m_deg
Definition: polyn_gf2m.h:149
Botan::polyn_gf2m::coeff
secure_vector< gf2m > coeff
Definition: polyn_gf2m.h:152

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

Definition at line 85 of file polyn_gf2m.h.

References coeff.

85 { return coeff[i]; }
Botan::polyn_gf2m::coeff
secure_vector< gf2m > coeff
Definition: polyn_gf2m.h:152

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

Definition at line 87 of file polyn_gf2m.h.

References coeff.

87 { return coeff[i]; }
Botan::polyn_gf2m::coeff
secure_vector< gf2m > coeff
Definition: polyn_gf2m.h:152

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

Definition at line 429 of file polyn_gf2m.cpp.

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

Referenced by eea_with_coefficients().

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 }
Botan::polyn_gf2m::calc_degree_secure
int calc_degree_secure() const
Definition: polyn_gf2m.cpp:46
Botan::expand_mask_16bit
uint16_t expand_mask_16bit(T tst)
Definition: code_based_util.h:25
Botan::polyn_gf2m::coeff
secure_vector< gf2m > coeff
Definition: polyn_gf2m.h:152

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

Definition at line 93 of file polyn_gf2m.h.

References coeff.

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

94 {
95 coeff[i] = v;
96 }
Botan::polyn_gf2m::coeff
secure_vector< gf2m > coeff
Definition: polyn_gf2m.h:152

void Botan::polyn_gf2m::set_to_zero | ( |  | ) |

Definition at line 222 of file polyn_gf2m.cpp.

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

Referenced by eea_with_coefficients().

223 {
224 clear_mem(&this->coeff[0], this->coeff.size());
225 this->m_deg = -1;
226 }
Botan::polyn_gf2m::m_deg
int m_deg
Definition: polyn_gf2m.h:149
Botan::clear_mem
void clear_mem(T *ptr, size_t n)
Definition: mem_ops.h:112
Botan::polyn_gf2m::coeff
secure_vector< gf2m > coeff
Definition: polyn_gf2m.h:152

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

Definition at line 323 of file polyn_gf2m.cpp.

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

Referenced by degppf(), and sqrt_mod_init().

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 }
Botan::gf2m
uint16_t gf2m
Definition: gf2m_small_m.h:23
Botan::polyn_gf2m::polyn_gf2m
polyn_gf2m()
Definition: polyn_gf2m.h:34
Botan::polyn_gf2m::m_sp_field
std::shared_ptr< GF2m_Field > m_sp_field
Definition: polyn_gf2m.h:155
Botan::polyn_gf2m::set_coef
void set_coef(size_t i, gf2m v)
Definition: polyn_gf2m.h:93

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

Definition at line 289 of file polyn_gf2m.cpp.

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

Referenced by degppf(), and sqrt_mod_init().

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 }
Botan::clear_mem
void clear_mem(T *ptr, size_t n)
Definition: mem_ops.h:112
Botan::polyn_gf2m::get_degree
int get_degree() const
Definition: polyn_gf2m.cpp:228
Botan::copy_mem
void copy_mem(T *out, const T *in, size_t n)
Definition: mem_ops.h:132
Botan::polyn_gf2m::coeff
secure_vector< gf2m > coeff
Definition: polyn_gf2m.h:152
Botan::polyn_gf2m::polyn_gf2m
polyn_gf2m()
Definition: polyn_gf2m.h:34
Botan::polyn_gf2m::set_coef
void set_coef(size_t i, gf2m v)
Definition: polyn_gf2m.h:93

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

Definition at line 676 of file polyn_gf2m.cpp.

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

Referenced by Botan::generate_mceliece_key().

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 }
Botan::polyn_gf2m::sqmod_init
static std::vector< polyn_gf2m > sqmod_init(const polyn_gf2m &g)
Definition: polyn_gf2m.cpp:289
Botan::polyn_gf2m::polyn_gf2m
polyn_gf2m()
Definition: polyn_gf2m.h:34
Botan::polyn_gf2m::m_sp_field
std::shared_ptr< GF2m_Field > m_sp_field
Definition: polyn_gf2m.h:155
Botan::polyn_gf2m::set_coef
void set_coef(size_t i, gf2m v)
Definition: polyn_gf2m.h:93

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

Definition at line 790 of file polyn_gf2m.cpp.

References coeff, m_deg, and m_sp_field.

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

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 }
Botan::polyn_gf2m::m_deg
int m_deg
Definition: polyn_gf2m.h:149
Botan::polyn_gf2m::coeff
secure_vector< gf2m > coeff
Definition: polyn_gf2m.h:152
Botan::polyn_gf2m::m_sp_field
std::shared_ptr< GF2m_Field > m_sp_field
Definition: polyn_gf2m.h:155

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

Definition at line 104 of file polyn_gf2m.cpp.

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

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 }
Botan::ASN1::to_string
std::string to_string(const BER_Object &obj)
Definition: asn1_obj.cpp:213
Botan::polyn_gf2m::get_degree
int get_degree() const
Definition: polyn_gf2m.cpp:228
Botan::polyn_gf2m::coeff
secure_vector< gf2m > coeff
Definition: polyn_gf2m.h:152

## Member Data Documentation

secure_vector<gf2m> Botan::polyn_gf2m::coeff

Definition at line 152 of file polyn_gf2m.h.

Referenced by add_to_coef(), calc_degree_secure(), eea_with_coefficients(), get_coef(), get_degree(), get_lead_coef(), operator==(), operator[](), polyn_gf2m(), set_coef(), set_to_zero(), swap(), and to_string().

int Botan::polyn_gf2m::m_deg

Definition at line 149 of file polyn_gf2m.h.

Referenced by calc_degree_secure(), encode(), eval(), get_degree(), get_lead_coef(), operator==(), polyn_gf2m(), set_to_zero(), sqmod_init(), and swap().

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

Definition at line 155 of file polyn_gf2m.h.

Referenced by degppf(), eea_with_coefficients(), eval(), get_sp_field(), polyn_gf2m(), sqmod(), sqrt_mod_init(), swap(), and Botan::syndrome_init().

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

- src/lib/pubkey/mce/polyn_gf2m.h
- src/lib/pubkey/mce/polyn_gf2m.cpp