Coverage Report

Created: 2021-02-21 07:20

/src/botan/src/lib/pubkey/mce/polyn_gf2m.cpp
Line
Count
Source (jump to first uncovered line)
1
/*
2
 * (C) Copyright Projet SECRET, INRIA, Rocquencourt
3
 * (C) Bhaskar Biswas and  Nicolas Sendrier
4
 *
5
 * (C) 2014 cryptosource GmbH
6
 * (C) 2014 Falko Strenzke fstrenzke@cryptosource.de
7
 * (C) 2015 Jack Lloyd
8
 *
9
 * Botan is released under the Simplified BSD License (see license.txt)
10
 *
11
 */
12
13
#include <botan/internal/polyn_gf2m.h>
14
#include <botan/internal/code_based_util.h>
15
#include <botan/internal/bit_ops.h>
16
#include <botan/rng.h>
17
#include <botan/exceptn.h>
18
#include <botan/internal/loadstor.h>
19
20
namespace Botan {
21
22
namespace {
23
24
gf2m generate_gf2m_mask(gf2m a)
25
0
   {
26
0
   gf2m result =  (a != 0);
27
0
   return ~(result - 1);
28
0
   }
29
30
/**
31
* number of leading zeros
32
*/
33
unsigned nlz_16bit(uint16_t x)
34
0
   {
35
0
   unsigned n;
36
0
   if(x == 0) return 16;
37
0
   n = 0;
38
0
   if(x <= 0x00FF) {n = n + 8; x = x << 8;}
39
0
   if(x <= 0x0FFF) {n = n + 4; x = x << 4;}
40
0
   if(x <= 0x3FFF) {n = n + 2; x = x << 2;}
41
0
   if(x <= 0x7FFF) {n = n + 1;}
42
0
   return n;
43
0
   }
44
}
45
46
int polyn_gf2m::calc_degree_secure() const
47
0
   {
48
0
   int i = static_cast<int>(this->coeff.size()) - 1;
49
0
   int result = 0;
50
0
   uint32_t found_mask = 0;
51
0
   uint32_t tracker_mask = 0xffff;
52
0
   for( ; i >= 0; i--)
53
0
      {
54
0
      found_mask = expand_mask_16bit(this->coeff[i]);
55
0
      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
0
      tracker_mask = tracker_mask & ~found_mask;
59
0
      }
60
0
   const_cast<polyn_gf2m*>(this)->m_deg = result;
61
0
   return result;
62
0
   }
63
64
gf2m random_gf2m(RandomNumberGenerator& rng)
65
0
   {
66
0
   uint8_t b[2];
67
0
   rng.randomize(b, sizeof(b));
68
0
   return make_uint16(b[1], b[0]);
69
0
   }
70
71
gf2m random_code_element(uint16_t code_length, RandomNumberGenerator& rng)
72
0
   {
73
0
   if(code_length == 0)
74
0
      {
75
0
      throw Invalid_Argument("random_code_element() was supplied a code length of zero");
76
0
      }
77
0
   const unsigned nlz = nlz_16bit(code_length-1);
78
0
   const gf2m mask = (1 << (16-nlz)) - 1;
79
80
0
   gf2m result;
81
82
0
   do
83
0
      {
84
0
      result = random_gf2m(rng);
85
0
      result &= mask;
86
0
      } while(result >= code_length); // rejection sampling
87
88
0
   return result;
89
0
   }
90
91
polyn_gf2m::polyn_gf2m(polyn_gf2m const& other)
92
   :m_deg(other.m_deg),
93
    coeff(other.coeff),
94
    m_sp_field(other.m_sp_field)
95
0
   { }
96
97
polyn_gf2m::polyn_gf2m(int d, std::shared_ptr<GF2m_Field> sp_field)
98
   :m_deg(-1),
99
    coeff(d+1),
100
    m_sp_field(sp_field)
101
0
   {
102
0
   }
103
104
std::string polyn_gf2m::to_string() const
105
0
   {
106
0
   int d = get_degree();
107
0
   std::string result;
108
0
   for(int i = 0; i <= d; i ++)
109
0
      {
110
0
      result += std::to_string(this->coeff[i]);
111
0
      if(i != d)
112
0
         {
113
0
         result += ", ";
114
0
         }
115
0
      }
116
0
   return result;
117
0
   }
118
/**
119
* doesn't save coefficients:
120
*/
121
void polyn_gf2m::realloc(uint32_t new_size)
122
0
   {
123
0
   this->coeff = secure_vector<gf2m>(new_size);
124
0
   }
125
126
polyn_gf2m::polyn_gf2m(const uint8_t* mem, uint32_t mem_len, std::shared_ptr<GF2m_Field> sp_field) :
127
   m_deg(-1), m_sp_field(sp_field)
128
0
   {
129
0
   if(mem_len % sizeof(gf2m))
130
0
      {
131
0
      throw Decoding_Error("illegal length of memory to decode ");
132
0
      }
133
134
0
   uint32_t size = (mem_len / sizeof(this->coeff[0])) ;
135
0
   this->coeff = secure_vector<gf2m>(size);
136
0
   this->m_deg = -1;
137
0
   for(uint32_t i = 0; i < size; i++)
138
0
      {
139
0
      this->coeff[i] = decode_gf2m(mem);
140
0
      mem += sizeof(this->coeff[0]);
141
0
      }
142
0
   for(uint32_t i = 0; i < size; i++)
143
0
      {
144
0
      if(this->coeff[i] >= (1 << sp_field->get_extension_degree()))
145
0
         {
146
0
         throw Decoding_Error("error decoding polynomial");
147
0
         }
148
0
      }
149
0
   this->get_degree();
150
0
   }
151
152
153
polyn_gf2m::polyn_gf2m( std::shared_ptr<GF2m_Field> sp_field) :
154
   m_deg(-1), coeff(1), m_sp_field(sp_field)
155
0
   {}
156
157
polyn_gf2m::polyn_gf2m(int degree, const uint8_t* mem, size_t mem_byte_len, std::shared_ptr<GF2m_Field> sp_field)
158
   :m_sp_field(sp_field)
159
0
   {
160
0
   uint32_t j, k, l;
161
0
   gf2m a;
162
0
   uint32_t polyn_size;
163
0
   polyn_size = degree + 1;
164
0
   if(polyn_size * sp_field->get_extension_degree() > 8 * mem_byte_len)
165
0
      {
166
0
      throw Decoding_Error("memory vector for polynomial has wrong size");
167
0
      }
168
0
   this->coeff = secure_vector<gf2m>(degree+1);
169
0
   gf2m ext_deg = static_cast<gf2m>(this->m_sp_field->get_extension_degree());
170
0
   for (l = 0; l < polyn_size; l++)
171
0
      {
172
0
      k = (l * ext_deg) / 8;
173
174
0
      j = (l * ext_deg) % 8;
175
0
      a = mem[k] >> j;
176
0
      if (j + ext_deg > 8)
177
0
         {
178
0
         a ^= mem[k + 1] << (8- j);
179
0
         }
180
0
      if(j + ext_deg > 16)
181
0
         {
182
0
         a ^= mem[k + 2] << (16- j);
183
0
         }
184
0
      a &= ((1 << ext_deg) - 1);
185
0
      (*this).set_coef( l, a);
186
0
      }
187
188
0
   this->get_degree();
189
0
   }
190
191
#if 0
192
void polyn_gf2m::encode(uint32_t min_numo_coeffs, uint8_t* mem, uint32_t mem_len) const
193
   {
194
   uint32_t i;
195
   uint32_t numo_coeffs, needed_size;
196
   this->get_degree();
197
   numo_coeffs = (min_numo_coeffs > static_cast<uint32_t>(this->m_deg+1)) ? min_numo_coeffs : this->m_deg+1;
198
   needed_size = sizeof(this->coeff[0]) * numo_coeffs;
199
   if(mem_len < needed_size)
200
      {
201
      Invalid_Argument("provided memory too small to encode polynomial");
202
      }
203
204
   for(i = 0; i < numo_coeffs; i++)
205
      {
206
      gf2m to_enc;
207
      if(i >= static_cast<uint32_t>(this->m_deg+1))
208
         {
209
         /* encode a zero */
210
         to_enc = 0;
211
         }
212
      else
213
         {
214
         to_enc = this->coeff[i];
215
         }
216
      mem += encode_gf2m(to_enc, mem);
217
      }
218
   }
219
#endif
220
221
222
void polyn_gf2m::set_to_zero()
223
0
   {
224
0
   clear_mem(&this->coeff[0], this->coeff.size());
225
0
   this->m_deg = -1;
226
0
   }
227
228
int polyn_gf2m::get_degree() const
229
0
   {
230
0
   int d = static_cast<int>(this->coeff.size()) - 1;
231
0
   while ((d >= 0) && (this->coeff[d] == 0))
232
0
      --d;
233
0
   const_cast<polyn_gf2m*>(this)->m_deg = d;
234
0
   return d;
235
0
   }
236
237
238
static gf2m eval_aux(const gf2m * /*restrict*/ coeff, gf2m a, int d, std::shared_ptr<GF2m_Field> sp_field)
239
0
   {
240
0
   gf2m b;
241
0
   b = coeff[d--];
242
0
   for (; d >= 0; --d)
243
0
      if (b != 0)
244
0
         {
245
0
         b = sp_field->gf_mul(b, a) ^ coeff[d];
246
0
         }
247
0
      else
248
0
         {
249
0
         b = coeff[d];
250
0
         }
251
0
   return b;
252
0
   }
253
254
gf2m polyn_gf2m::eval(gf2m a)
255
0
   {
256
0
   return eval_aux(&this->coeff[0], a, this->m_deg, this->m_sp_field);
257
0
   }
258
259
260
// p will contain it's remainder modulo g
261
void polyn_gf2m::remainder(polyn_gf2m &p, const polyn_gf2m & g)
262
0
   {
263
0
   int i, j, d;
264
0
   std::shared_ptr<GF2m_Field> m_sp_field = g.m_sp_field;
265
0
   d = p.get_degree() - g.get_degree();
266
0
   if (d >= 0) {
267
0
   gf2m la = m_sp_field->gf_inv_rn(g.get_lead_coef());
268
269
0
   const int p_degree = p.get_degree();
270
271
0
   BOTAN_ASSERT(p_degree > 0, "Valid polynomial");
272
273
0
   for (i = p_degree; d >= 0; --i, --d) {
274
0
   if (p[i] != 0) {
275
0
   gf2m lb = m_sp_field->gf_mul_rrn(la, p[i]);
276
0
   for (j = 0; j < g.get_degree(); ++j)
277
0
      {
278
0
      p[j+d] ^= m_sp_field->gf_mul_zrz(lb, g[j]);
279
0
      }
280
0
   (*&p).set_coef( i, 0);
281
0
   }
282
0
   }
283
0
   p.set_degree( g.get_degree() - 1);
284
0
   while ((p.get_degree() >= 0) && (p[p.get_degree()] == 0))
285
0
      p.set_degree( p.get_degree() - 1);
286
0
   }
287
0
   }
288
289
std::vector<polyn_gf2m> polyn_gf2m::sqmod_init(const polyn_gf2m & g)
290
0
   {
291
0
   std::vector<polyn_gf2m> sq;
292
0
   const int signed_deg = g.get_degree();
293
0
   if(signed_deg <= 0)
294
0
      throw Invalid_Argument("cannot compute sqmod for such low degree");
295
296
0
   const uint32_t d = static_cast<uint32_t>(signed_deg);
297
0
   uint32_t t = g.m_deg;
298
   // create t zero polynomials
299
0
   uint32_t i;
300
0
   for (i = 0; i < t; ++i)
301
0
      {
302
0
      sq.push_back(polyn_gf2m(t+1, g.get_sp_field()));
303
0
      }
304
0
   for (i = 0; i < d / 2; ++i)
305
0
      {
306
0
      sq[i].set_degree( 2 * i);
307
0
      (*&sq[i]).set_coef( 2 * i, 1);
308
0
      }
309
310
0
   for (; i < d; ++i)
311
0
      {
312
0
      clear_mem(&sq[i].coeff[0], 2);
313
0
      copy_mem(&sq[i].coeff[0] + 2, &sq[i - 1].coeff[0], d);
314
0
      sq[i].set_degree( sq[i - 1].get_degree() + 2);
315
0
      polyn_gf2m::remainder(sq[i], g);
316
0
      }
317
0
   return sq;
318
0
   }
319
320
/*Modulo p square of a certain polynomial g, sq[] contains the square
321
Modulo g of the base canonical polynomials of degree < d, where d is
322
the degree of G. The table sq[] will be calculated by polyn_gf2m_sqmod_init*/
323
polyn_gf2m polyn_gf2m::sqmod( const std::vector<polyn_gf2m> & sq, int d)
324
0
   {
325
0
   int i, j;
326
0
   gf2m la;
327
0
   std::shared_ptr<GF2m_Field> sp_field = this->m_sp_field;
328
329
0
   polyn_gf2m result(d - 1, sp_field);
330
   // terms of low degree
331
0
   for (i = 0; i < d / 2; ++i)
332
0
      {
333
0
      (*&result).set_coef( i * 2, sp_field->gf_square((*this)[i]));
334
0
      }
335
336
   // terms of high degree
337
0
   for (; i < d; ++i)
338
0
      {
339
0
      gf2m lpi = (*this)[i];
340
0
      if (lpi != 0)
341
0
         {
342
0
         lpi = sp_field->gf_log(lpi);
343
0
         la = sp_field->gf_mul_rrr(lpi, lpi);
344
0
         for (j = 0; j < d; ++j)
345
0
            {
346
0
            result[j] ^= sp_field->gf_mul_zrz(la, sq[i][j]);
347
0
            }
348
0
         }
349
0
      }
350
351
   // Update degre
352
0
   result.set_degree( d - 1);
353
0
   while ((result.get_degree() >= 0) && (result[result.get_degree()] == 0))
354
0
      result.set_degree( result.get_degree() - 1);
355
0
   return result;
356
0
   }
357
358
359
// destructive
360
polyn_gf2m polyn_gf2m::gcd_aux(polyn_gf2m& p1, polyn_gf2m& p2)
361
0
   {
362
0
   if (p2.get_degree() == -1)
363
0
      return p1;
364
0
   else {
365
0
   polyn_gf2m::remainder(p1, p2);
366
0
   return polyn_gf2m::gcd_aux(p2, p1);
367
0
   }
368
0
   }
369
370
371
polyn_gf2m polyn_gf2m::gcd(polyn_gf2m const& p1, polyn_gf2m const& p2)
372
0
   {
373
0
   polyn_gf2m a(p1);
374
0
   polyn_gf2m b(p2);
375
0
   if (a.get_degree() < b.get_degree())
376
0
      {
377
0
      return polyn_gf2m(polyn_gf2m::gcd_aux(b, a));
378
0
      }
379
0
   else
380
0
      {
381
0
      return polyn_gf2m(polyn_gf2m::gcd_aux(a, b));
382
0
      }
383
0
   }
384
385
386
387
388
389
// Returns the degree of the smallest factor
390
size_t polyn_gf2m::degppf(const polyn_gf2m& g)
391
0
   {
392
0
   polyn_gf2m s(g.get_sp_field());
393
394
0
   const size_t ext_deg = g.m_sp_field->get_extension_degree();
395
0
   const int d = g.get_degree();
396
0
   std::vector<polyn_gf2m> u = polyn_gf2m::sqmod_init(g);
397
398
0
   polyn_gf2m p(d - 1, g.m_sp_field);
399
400
0
   p.set_degree(1);
401
0
   (*&p).set_coef(1, 1);
402
0
   size_t result = static_cast<size_t>(d);
403
0
   for(size_t i = 1; i <= (d / 2) * ext_deg; ++i)
404
0
      {
405
0
      polyn_gf2m r = p.sqmod(u, d);
406
0
      if ((i % ext_deg) == 0)
407
0
         {
408
0
         r[1] ^= 1;
409
0
         r.get_degree(); // The degree may change
410
0
         s = polyn_gf2m::gcd( g, r);
411
412
0
         if(s.get_degree() > 0)
413
0
            {
414
0
            result = i / ext_deg;
415
0
            break;
416
0
            }
417
0
         r[1] ^= 1;
418
0
         r.get_degree(); // The degree may change
419
0
         }
420
      // No need for the exchange s
421
0
      s = p;
422
0
      p = r;
423
0
      r = s;
424
0
      }
425
426
0
   return result;
427
0
   }
428
429
void polyn_gf2m::patchup_deg_secure( uint32_t trgt_deg, volatile gf2m patch_elem)
430
0
   {
431
0
   uint32_t i;
432
0
   if(this->coeff.size() < trgt_deg)
433
0
      {
434
0
      return;
435
0
      }
436
0
   for(i = 0; i < this->coeff.size(); i++)
437
0
      {
438
0
      uint32_t equal, equal_mask;
439
0
      this->coeff[i] |= patch_elem;
440
0
      equal = (i == trgt_deg);
441
0
      equal_mask = expand_mask_16bit(equal);
442
0
      patch_elem &= ~equal_mask;
443
0
      }
444
0
   this->calc_degree_secure();
445
0
   }
446
// We suppose m_deg(g) >= m_deg(p)
447
// v is the problem
448
std::pair<polyn_gf2m, polyn_gf2m> polyn_gf2m::eea_with_coefficients( const polyn_gf2m & p, const polyn_gf2m & g, int break_deg)
449
0
   {
450
451
0
   std::shared_ptr<GF2m_Field> m_sp_field = g.m_sp_field;
452
0
   int i, j, dr, du, delta;
453
0
   gf2m a;
454
0
   polyn_gf2m aux;
455
456
   // initialisation of the local variables
457
   // r0 <- g, r1 <- p, u0 <- 0, u1 <- 1
458
0
   dr = g.get_degree();
459
460
0
   BOTAN_ASSERT(dr > 3, "Valid polynomial");
461
462
0
   polyn_gf2m r0(dr, g.m_sp_field);
463
0
   polyn_gf2m r1(dr - 1, g.m_sp_field);
464
0
   polyn_gf2m u0(dr - 1, g.m_sp_field);
465
0
   polyn_gf2m u1(dr - 1, g.m_sp_field);
466
467
0
   r0 = g;
468
0
   r1 = p;
469
0
   u0.set_to_zero();
470
0
   u1.set_to_zero();
471
0
   (*&u1).set_coef( 0, 1);
472
0
   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
0
   du = 0;
482
0
   dr = r1.get_degree();
483
0
   delta = r0.get_degree() - dr;
484
485
486
0
   while (dr >= break_deg)
487
0
      {
488
489
0
      for (j = delta; j >= 0; --j)
490
0
         {
491
0
         a = m_sp_field->gf_div(r0[dr + j], r1[dr]);
492
0
         if (a != 0)
493
0
            {
494
0
            gf2m la = m_sp_field->gf_log(a);
495
            // u0(z) <- u0(z) + a * u1(z) * z^j
496
0
            for (i = 0; i <= du; ++i)
497
0
               {
498
0
               u0[i + j] ^= m_sp_field->gf_mul_zrz(la, u1[i]);
499
0
               }
500
            // r0(z) <- r0(z) + a * r1(z) * z^j
501
0
            for (i = 0; i <= dr; ++i)
502
0
               {
503
0
               r0[i + j] ^= m_sp_field->gf_mul_zrz(la, r1[i]);
504
0
               }
505
0
            }
506
0
         } // end loop over j
507
508
0
      if(break_deg != 1) /* key eq. solving */
509
0
         {
510
         /* [ssms_icisc09] Countermeasure
511
         * d_break from paper equals break_deg - 1
512
         * */
513
514
0
         volatile gf2m fake_elem = 0x01;
515
0
         volatile gf2m cond1, cond2;
516
0
         int trgt_deg = r1.get_degree() - 1;
517
0
         r0.calc_degree_secure();
518
0
         u0.calc_degree_secure();
519
0
         if(!(g.get_degree() % 2))
520
0
            {
521
            /* t even */
522
0
            cond1 = r0.get_degree() < break_deg - 1;
523
0
            }
524
0
         else
525
0
            {
526
            /* t odd */
527
0
            cond1 =  r0.get_degree() < break_deg;
528
0
            cond2 =  u0.get_degree() < break_deg - 1;
529
0
            cond1 &= cond2;
530
0
            }
531
         /* expand cond1 to a full mask */
532
0
         gf2m mask = generate_gf2m_mask(cond1);
533
0
         fake_elem &= mask;
534
0
         r0.patchup_deg_secure(trgt_deg, fake_elem);
535
0
         }
536
0
      if(break_deg == 1) /* syndrome inversion */
537
0
         {
538
0
         volatile gf2m fake_elem = 0x00;
539
0
         volatile uint32_t trgt_deg = 0;
540
0
         r0.calc_degree_secure();
541
0
         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
0
         if(u0.get_degree() == 4)
558
0
            {
559
0
            uint32_t mask = 0;
560
            /**
561
            * Condition that the EEA would break now
562
            */
563
0
            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
0
            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
0
            int cond_u3 = u0.coeff[3] == 0;
578
            // combine the conditions:
579
0
            cond_r &= (cond_u1 & cond_u3);
580
            // mask generation:
581
0
            mask = expand_mask_16bit(cond_r);
582
0
            trgt_deg = 2 & mask;
583
0
            fake_elem = 1 & mask;
584
0
            }
585
0
         else if(u0.get_degree() == 6)
586
0
            {
587
0
            uint32_t mask = 0;
588
0
            int cond_r= r0.get_degree() == 0;
589
0
            int cond_u1 = m_sp_field->gf_mul(u0.coeff[1], m_sp_field->gf_inv(r0.coeff[0])) == 1;
590
0
            int cond_u3 = u0.coeff[3] == 0;
591
592
0
            int cond_u5 = u0.coeff[5] == 0;
593
594
0
            cond_r &= (cond_u1 & cond_u3 & cond_u5);
595
0
            mask = expand_mask_16bit(cond_r);
596
0
            trgt_deg = 4 & mask;
597
0
            fake_elem = 1 & mask;
598
0
            }
599
0
         else if(u0.get_degree() == 8)
600
0
            {
601
0
            uint32_t mask = 0;
602
0
            int cond_r= r0.get_degree() == 0;
603
0
            int cond_u1 = m_sp_field->gf_mul(u0[1], m_sp_field->gf_inv(r0[0])) == 1;
604
0
            int cond_u3 = u0.coeff[3] == 0;
605
606
0
            int cond_u5 = u0.coeff[5] == 0;
607
608
0
            int cond_u7 = u0.coeff[7] == 0;
609
610
0
            cond_r &= (cond_u1 & cond_u3 & cond_u5 & cond_u7);
611
0
            mask = expand_mask_16bit(cond_r);
612
0
            trgt_deg = 6 & mask;
613
0
            fake_elem = 1 & mask;
614
0
            }
615
0
         r0.patchup_deg_secure(trgt_deg, fake_elem);
616
0
         }
617
      // exchange
618
0
      aux = r0; r0 = r1; r1 = aux;
619
0
      aux = u0; u0 = u1; u1 = aux;
620
621
0
      du = du + delta;
622
0
      delta = 1;
623
0
      while (r1[dr - delta] == 0)
624
0
         {
625
0
         delta++;
626
0
         }
627
628
629
0
      dr -= delta;
630
0
      } /* end  while loop (dr >= break_deg) */
631
632
633
0
   u1.set_degree( du);
634
0
   r1.set_degree( dr);
635
   //return u1 and r1;
636
0
   return std::make_pair(u1,r1); // coefficients u,v
637
0
   }
638
639
polyn_gf2m::polyn_gf2m(size_t t, RandomNumberGenerator& rng, std::shared_ptr<GF2m_Field> sp_field)
640
   :m_deg(static_cast<int>(t)),
641
    coeff(t+1),
642
    m_sp_field(sp_field)
643
0
   {
644
0
   this->set_coef(t, 1);
645
0
   for(;;)
646
0
      {
647
0
      for(size_t i = 0; i < t; ++i)
648
0
         {
649
0
         this->set_coef(i, random_code_element(sp_field->get_cardinality(), rng));
650
0
         }
651
652
0
      const size_t degree = polyn_gf2m::degppf(*this);
653
654
0
      if(degree >= t)
655
0
         break;
656
0
      }
657
0
   }
658
659
void polyn_gf2m::poly_shiftmod( const polyn_gf2m & g)
660
0
   {
661
0
   if(g.get_degree() <= 1)
662
0
      {
663
0
      throw Invalid_Argument("shiftmod cannot be called on polynomials of degree 1 or less");
664
0
      }
665
0
   std::shared_ptr<GF2m_Field> field = g.m_sp_field;
666
667
0
   int t = g.get_degree();
668
0
   gf2m a = field->gf_div(this->coeff[t-1], g.coeff[t]);
669
0
   for (int i = t - 1; i > 0; --i)
670
0
      {
671
0
      this->coeff[i] = this->coeff[i - 1] ^ this->m_sp_field->gf_mul(a, g.coeff[i]);
672
0
      }
673
0
   this->coeff[0] = field->gf_mul(a, g.coeff[0]);
674
0
   }
675
676
std::vector<polyn_gf2m> polyn_gf2m::sqrt_mod_init(const polyn_gf2m & g)
677
0
   {
678
0
   uint32_t i, t;
679
0
   uint32_t nb_polyn_sqrt_mat;
680
0
   std::shared_ptr<GF2m_Field> m_sp_field = g.m_sp_field;
681
0
   std::vector<polyn_gf2m> result;
682
0
   t = g.get_degree();
683
0
   nb_polyn_sqrt_mat = t/2;
684
685
0
   std::vector<polyn_gf2m> sq_aux = polyn_gf2m::sqmod_init(g);
686
687
688
0
   polyn_gf2m p( t - 1, g.get_sp_field());
689
0
   p.set_degree( 1);
690
691
0
   (*&p).set_coef( 1, 1);
692
   // q(z) = 0, p(z) = z
693
0
   for (i = 0; i < t * m_sp_field->get_extension_degree() - 1; ++i)
694
0
      {
695
      // q(z) <- p(z)^2 mod g(z)
696
0
      polyn_gf2m q = p.sqmod(sq_aux, t);
697
      // q(z) <-> p(z)
698
0
      polyn_gf2m aux = q;
699
0
      q = p;
700
0
      p = aux;
701
0
      }
702
   // p(z) = z^(2^(tm-1)) mod g(z) = sqrt(z) mod g(z)
703
704
0
   for (i = 0; i < nb_polyn_sqrt_mat; ++i)
705
0
      {
706
0
      result.push_back(polyn_gf2m(t - 1, g.get_sp_field()));
707
0
      }
708
709
0
   result[0] = p;
710
0
   result[0].get_degree();
711
0
   for(i = 1; i < nb_polyn_sqrt_mat; i++)
712
0
      {
713
0
      result[i] = result[i - 1];
714
0
      result[i].poly_shiftmod(g),
715
0
         result[i].get_degree();
716
0
      }
717
718
0
   return result;
719
0
   }
720
721
std::vector<polyn_gf2m> syndrome_init(polyn_gf2m const& generator, std::vector<gf2m> const& support, int n)
722
0
   {
723
0
   int i,j,t;
724
0
   gf2m a;
725
726
727
0
   std::shared_ptr<GF2m_Field> m_sp_field = generator.m_sp_field;
728
729
0
   std::vector<polyn_gf2m> result;
730
0
   t = generator.get_degree();
731
732
   //g(z)=g_t+g_(t-1).z^(t-1)+......+g_1.z+g_0
733
   //f(z)=f_(t-1).z^(t-1)+......+f_1.z+f_0
734
735
0
   for(j=0;j<n;j++)
736
0
      {
737
0
      result.push_back(polyn_gf2m( t-1, m_sp_field));
738
739
0
      (*&result[j]).set_coef(t-1,1);
740
0
      for(i=t-2;i>=0;i--)
741
0
         {
742
0
         (*&result[j]).set_coef(i, (generator)[i+1]  ^
743
0
                                m_sp_field->gf_mul(lex_to_gray(support[j]),result[j][i+1]));
744
0
         }
745
0
      a = ((generator)[0] ^ m_sp_field->gf_mul(lex_to_gray(support[j]),result[j][0]));
746
0
      for(i=0;i<t;i++)
747
0
         {
748
0
         (*&result[j]).set_coef(i, m_sp_field->gf_div(result[j][i],a));
749
0
         }
750
0
      }
751
0
   return result;
752
0
   }
753
754
polyn_gf2m::polyn_gf2m(const secure_vector<uint8_t>& encoded, std::shared_ptr<GF2m_Field> sp_field )
755
   :m_sp_field(sp_field)
756
0
   {
757
0
   if(encoded.size() % 2)
758
0
      {
759
0
      throw Decoding_Error("encoded polynomial has odd length");
760
0
      }
761
0
   for(uint32_t i = 0; i < encoded.size(); i += 2)
762
0
      {
763
0
      gf2m el = (encoded[i] << 8) | encoded[i + 1];
764
0
      coeff.push_back(el);
765
0
      }
766
0
   get_degree();
767
768
0
   }
769
secure_vector<uint8_t> polyn_gf2m::encode() const
770
0
   {
771
0
   secure_vector<uint8_t> result;
772
773
0
   if(m_deg < 1)
774
0
      {
775
0
      result.push_back(0);
776
0
      result.push_back(0);
777
0
      return result;
778
0
      }
779
780
0
   uint32_t len = m_deg+1;
781
0
   for(unsigned i = 0; i < len; i++)
782
0
      {
783
      // "big endian" encoding of the GF(2^m) elements
784
0
      result.push_back(get_byte(0, coeff[i]));
785
0
      result.push_back(get_byte(1, coeff[i]));
786
0
      }
787
0
   return result;
788
0
   }
789
790
void polyn_gf2m::swap(polyn_gf2m& other)
791
0
   {
792
0
   std::swap(this->m_deg, other.m_deg);
793
0
   std::swap(this->m_sp_field, other.m_sp_field);
794
0
   std::swap(this->coeff, other.coeff);
795
0
   }
796
797
bool polyn_gf2m::operator==(const polyn_gf2m & other) const
798
0
   {
799
0
   if(m_deg != other.m_deg || coeff != other.coeff)
800
0
      {
801
0
      return false;
802
0
      }
803
0
   return true;
804
0
   }
805
806
}