Botan 2.1.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 Struct Reference

`#include <polyn_gf2m.h>`

## Public Member Functions
void | add_to_coef (uint32_t i, gf2m v)
int | calc_degree_secure () const
void | degppf (const polyn_gf2m &g, int *p_result)
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 (uint32_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 (polyn_gf2m &&other)
| polyn_gf2m (int d, std::shared_ptr< GF2m_Field > sp_field)
| polyn_gf2m (polyn_gf2m const &other)
| polyn_gf2m (int 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 unsigned char *mem, uint32_t mem_byte_len, std::shared_ptr< GF2m_Field > sp_field)
void | set_coef (uint32_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 > | msp_field

## Detailed Description

Definition at line 24 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.

154 : m_deg(-1),
155 coeff(1),
156 msp_field(sp_field)
157 {}
Botan::polyn_gf2m::m_deg
int m_deg
Definition: polyn_gf2m.h:150
Botan::polyn_gf2m::coeff
secure_vector< gf2m > coeff
Definition: polyn_gf2m.h:153
Botan::polyn_gf2m::msp_field
std::shared_ptr< GF2m_Field > msp_field
Definition: polyn_gf2m.h:156

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

Definition at line 32 of file polyn_gf2m.h.

Referenced by sqmod_init(), and sqrt_mod_init().

33 :m_deg(-1) {}
Botan::polyn_gf2m::m_deg
int m_deg
Definition: polyn_gf2m.h:150

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

Definition at line 756 of file polyn_gf2m.cpp.

References get_degree().

757 :msp_field(sp_field)
758 {
759 if(encoded.size() % 2)
760 {
761 throw Decoding_Error("encoded polynomial has odd length");
762 }
763 for(uint32_t i = 0; i < encoded.size(); i += 2)
764 {
765 gf2m el = (encoded[i] << 8) | encoded[i + 1];
766 coeff.push_back(el);
767 }
768 get_degree();
769
770 }
Botan::polyn_gf2m::get_degree
int get_degree() const
Definition: polyn_gf2m.cpp:230
Botan::polyn_gf2m::coeff
secure_vector< gf2m > coeff
Definition: polyn_gf2m.h:153
Botan::gf2m
uint16_t gf2m
Definition: gf2m_small_m.h:20
Botan::polyn_gf2m::msp_field
std::shared_ptr< GF2m_Field > msp_field
Definition: polyn_gf2m.h:156

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

Definition at line 43 of file polyn_gf2m.h.

References swap().

44 {
45 this->swap(other);
46 }
Botan::polyn_gf2m::swap
void swap(polyn_gf2m &other)
Definition: polyn_gf2m.cpp:792

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 msp_field(sp_field)
101 {
102 }
Botan::polyn_gf2m::m_deg
int m_deg
Definition: polyn_gf2m.h:150
Botan::polyn_gf2m::coeff
secure_vector< gf2m > coeff
Definition: polyn_gf2m.h:153
Botan::polyn_gf2m::msp_field
std::shared_ptr< GF2m_Field > msp_field
Definition: polyn_gf2m.h:156

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 msp_field(other.msp_field)
95 { }
Botan::polyn_gf2m::m_deg
int m_deg
Definition: polyn_gf2m.h:150
Botan::polyn_gf2m::coeff
secure_vector< gf2m > coeff
Definition: polyn_gf2m.h:153
Botan::polyn_gf2m::msp_field
std::shared_ptr< GF2m_Field > msp_field
Definition: polyn_gf2m.h:156

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

create zero polynomial with allocated size determined by specified degree d: random irreducible polynomial of degree t

Definition at line 642 of file polyn_gf2m.cpp.

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

643 :m_deg(t),
644 coeff(t+1),
645 msp_field(sp_field)
646 {
647 (*this).set_coef( t, 1);
648 int degree = 0;
649 do
650 {
651 for (int i = 0; i < t; ++i)
652 {
653 (*this).set_coef( i, random_code_element(sp_field->get_cardinality(), rng));
654 }
655 polyn_gf2m::degppf(*this, &degree);
656 }
657 while (degree < t);
658 }
Botan::polyn_gf2m::m_deg
int m_deg
Definition: polyn_gf2m.h:150
Botan::polyn_gf2m::degppf
void degppf(const polyn_gf2m &g, int *p_result)
Definition: polyn_gf2m.cpp:392
Botan::polyn_gf2m::coeff
secure_vector< gf2m > coeff
Definition: polyn_gf2m.h:153
Botan::random_code_element
gf2m random_code_element(unsigned code_length, RandomNumberGenerator &rng)
Definition: polyn_gf2m.cpp:71
Botan::polyn_gf2m::msp_field
std::shared_ptr< GF2m_Field > msp_field
Definition: polyn_gf2m.h:156

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.

127 :msp_field(sp_field)
128 {
129 if(mem_len % sizeof(gf2m))
130 {
131 throw new Botan::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 Botan::Decoding_Error("error decoding polynomial");
147 }
148 }
149 this->get_degree();
150 }
Botan::polyn_gf2m::m_deg
int m_deg
Definition: polyn_gf2m.h:150
Botan::polyn_gf2m::get_degree
int get_degree() const
Definition: polyn_gf2m.cpp:230
Botan::decode_gf2m
gf2m decode_gf2m(const uint8_t *mem)
Definition: gf2m_small_m.cpp:104
Botan::polyn_gf2m::coeff
secure_vector< gf2m > coeff
Definition: polyn_gf2m.h:153
Botan::Decoding_Error
Definition: exceptn.h:189
Botan::gf2m
uint16_t gf2m
Definition: gf2m_small_m.h:20
Botan::polyn_gf2m::msp_field
std::shared_ptr< GF2m_Field > msp_field
Definition: polyn_gf2m.h:156

Botan::polyn_gf2m::polyn_gf2m | ( | int | degree,
|  | const unsigned char * | mem,
|  | uint32_t | mem_byte_len,
|  | std::shared_ptr< GF2m_Field > | sp_field
| ) |  |

create a polynomial from memory area (encoded)

Definition at line 159 of file polyn_gf2m.cpp.

References coeff, get_degree(), and msp_field.

160 :msp_field(sp_field)
161 {
162 uint32_t j, k, l;
163 gf2m a;
164 uint32_t polyn_size;
165 polyn_size = degree + 1;
166 if(polyn_size * sp_field->get_extension_degree() > 8 * mem_byte_len)
167 {
168 throw Botan::Decoding_Error("memory vector for polynomial has wrong size");
169 }
170 this->coeff = secure_vector<gf2m>(degree+1);
171 gf2m ext_deg = this->msp_field->get_extension_degree();
172 for (l = 0; l < polyn_size; l++)
173 {
174 k = (l * ext_deg) / 8;
175
176 j = (l * ext_deg) % 8;
177 a = mem[k] >> j;
178 if (j + ext_deg > 8)
179 {
180 a ^= mem[k + 1] << (8- j);
181 }
182 if(j + ext_deg > 16)
183 {
184 a ^= mem[k + 2] << (16- j);
185 }
186 a &= ((1 << ext_deg) - 1);
187 (*this).set_coef( l, a);
188 }
189
190 this->get_degree();
191 }
Botan::polyn_gf2m::get_degree
int get_degree() const
Definition: polyn_gf2m.cpp:230
Botan::polyn_gf2m::coeff
secure_vector< gf2m > coeff
Definition: polyn_gf2m.h:153
Botan::Decoding_Error
Definition: exceptn.h:189
Botan::gf2m
uint16_t gf2m
Definition: gf2m_small_m.h:20
Botan::polyn_gf2m::msp_field
std::shared_ptr< GF2m_Field > msp_field
Definition: polyn_gf2m.h:156

## Member Function Documentation

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

Definition at line 91 of file polyn_gf2m.h.

References coeff.

92 {
93 coeff[i] = coeff[i] ^ v;
94 }
Botan::polyn_gf2m::coeff
secure_vector< gf2m > coeff
Definition: polyn_gf2m.h:153

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 = 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:150
Botan::polyn_gf2m::polyn_gf2m
polyn_gf2m()
Definition: polyn_gf2m.h:32
Botan::polyn_gf2m::coeff
secure_vector< gf2m > coeff
Definition: polyn_gf2m.h:153
Botan::expand_mask_16bit
uint16_t expand_mask_16bit(T tst)
Definition: code_based_util.h:25

void Botan::polyn_gf2m::degppf | ( | const polyn_gf2m & | g,
|  | int * | p_result
| ) |  |

Definition at line 392 of file polyn_gf2m.cpp.

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

Referenced by polyn_gf2m().

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

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

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

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

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

Definition at line 771 of file polyn_gf2m.cpp.

References m_deg.

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

772 {
773 secure_vector<uint8_t> result;
774
775 if(m_deg < 1)
776 {
777 result.push_back(0);
778 result.push_back(0);
779 return result;
780 }
781
782 uint32_t len = m_deg+1;
783 for(unsigned i = 0; i < len; i++)
784 {
785 // "big endian" encoding of the GF(2^m) elements
786 result.push_back(coeff[i] >> 8);
787 result.push_back(coeff[i]);
788 }
789 return result;
790 }
Botan::polyn_gf2m::m_deg
int m_deg
Definition: polyn_gf2m.h:150
Botan::polyn_gf2m::coeff
secure_vector< gf2m > coeff
Definition: polyn_gf2m.h:153

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

References m_deg, and msp_field.

257 {
258 return eval_aux(&this->coeff[0], a, this->m_deg, this->msp_field);
259 }
Botan::polyn_gf2m::m_deg
int m_deg
Definition: polyn_gf2m.h:150
Botan::polyn_gf2m::coeff
secure_vector< gf2m > coeff
Definition: polyn_gf2m.h:153
Botan::polyn_gf2m::msp_field
std::shared_ptr< GF2m_Field > msp_field
Definition: polyn_gf2m.h:156

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

Definition at line 84 of file polyn_gf2m.h.

References coeff.

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

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

Definition at line 230 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().

231 {
232 int d = this->coeff.size() - 1;
233 while ((d >= 0) && (this->coeff[d] == 0))
234 --d;
235 const_cast<polyn_gf2m*>(this)->m_deg = d;
236 return d;
237 }
Botan::polyn_gf2m::m_deg
int m_deg
Definition: polyn_gf2m.h:150
Botan::polyn_gf2m::polyn_gf2m
polyn_gf2m()
Definition: polyn_gf2m.h:32
Botan::polyn_gf2m::coeff
secure_vector< gf2m > coeff
Definition: polyn_gf2m.h:153

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

Definition at line 82 of file polyn_gf2m.h.

References coeff, and m_deg.

82 { return coeff[m_deg]; }
Botan::polyn_gf2m::m_deg
int m_deg
Definition: polyn_gf2m.h:150
Botan::polyn_gf2m::coeff
secure_vector< gf2m > coeff
Definition: polyn_gf2m.h:153

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

Definition at line 75 of file polyn_gf2m.h.

References msp_field.

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

76 { return msp_field; }
Botan::polyn_gf2m::msp_field
std::shared_ptr< GF2m_Field > msp_field
Definition: polyn_gf2m.h:156

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

Definition at line 41 of file polyn_gf2m.h.

41 { 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 48 of file polyn_gf2m.h.

References swap().

49 {
50 if(this != &other)
51 {
52 this->swap(other);
53 }
54 return *this;
55 }
Botan::polyn_gf2m::swap
void swap(polyn_gf2m &other)
Definition: polyn_gf2m.cpp:792

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

Definition at line 799 of file polyn_gf2m.cpp.

References coeff, and m_deg.

800 {
801 if(m_deg != other.m_deg || coeff != other.coeff)
802 {
803 return false;
804 }
805 return true;
806 }
Botan::polyn_gf2m::m_deg
int m_deg
Definition: polyn_gf2m.h:150
Botan::polyn_gf2m::coeff
secure_vector< gf2m > coeff
Definition: polyn_gf2m.h:153

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

Definition at line 78 of file polyn_gf2m.h.

References coeff.

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

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

Definition at line 80 of file polyn_gf2m.h.

References coeff.

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

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

Definition at line 431 of file polyn_gf2m.cpp.

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

Referenced by eea_with_coefficients().

432 {
433 uint32_t i;
434 if(this->coeff.size() < trgt_deg)
435 {
436 return;
437 }
438 for(i = 0; i < this->coeff.size(); i++)
439 {
440 uint32_t equal, equal_mask;
441 this->coeff[i] |= patch_elem;
442 equal = (i == trgt_deg);
443 equal_mask = expand_mask_16bit(equal);
444 patch_elem &= ~equal_mask;
445 }
446 this->calc_degree_secure();
447 }
Botan::polyn_gf2m::calc_degree_secure
int calc_degree_secure() const
Definition: polyn_gf2m.cpp:46
Botan::polyn_gf2m::coeff
secure_vector< gf2m > coeff
Definition: polyn_gf2m.h:153
Botan::expand_mask_16bit
uint16_t expand_mask_16bit(T tst)
Definition: code_based_util.h:25

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

Definition at line 86 of file polyn_gf2m.h.

References coeff.

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

87 {
88 coeff[i] = v;
89 }
Botan::polyn_gf2m::coeff
secure_vector< gf2m > coeff
Definition: polyn_gf2m.h:153

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

Definition at line 224 of file polyn_gf2m.cpp.

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

Referenced by eea_with_coefficients().

225 {
226 clear_mem(&this->coeff[0], this->coeff.size());
227 this->m_deg = -1;
228 }
Botan::polyn_gf2m::m_deg
int m_deg
Definition: polyn_gf2m.h:150
Botan::clear_mem
void clear_mem(T *ptr, size_t n)
Definition: mem_ops.h:57
Botan::polyn_gf2m::coeff
secure_vector< gf2m > coeff
Definition: polyn_gf2m.h:153

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

Definition at line 325 of file polyn_gf2m.cpp.

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

Referenced by degppf(), and sqrt_mod_init().

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

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

Definition at line 291 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().

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

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

Definition at line 678 of file polyn_gf2m.cpp.

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

Referenced by Botan::generate_mceliece_key().

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

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

Definition at line 792 of file polyn_gf2m.cpp.

References coeff, m_deg, and msp_field.

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

793 {
794 std::swap(this->m_deg, other.m_deg);
795 std::swap(this->msp_field, other.msp_field);
796 std::swap(this->coeff, other.coeff);
797 }
Botan::polyn_gf2m::m_deg
int m_deg
Definition: polyn_gf2m.h:150
Botan::polyn_gf2m::coeff
secure_vector< gf2m > coeff
Definition: polyn_gf2m.h:153
Botan::polyn_gf2m::msp_field
std::shared_ptr< GF2m_Field > msp_field
Definition: polyn_gf2m.h:156

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

## Member Data Documentation

secure_vector<gf2m> Botan::polyn_gf2m::coeff

Definition at line 153 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 150 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::msp_field

Definition at line 156 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 struct was generated from the following files:

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