Botan
1.11.15
|
00001 /** 00002 * (C) Copyright Projet SECRET, INRIA, Rocquencourt 00003 * (C) Bhaskar Biswas and Nicolas Sendrier 00004 * 00005 * (C) 2014 cryptosource GmbH 00006 * (C) 2014 Falko Strenzke fstrenzke@cryptosource.de 00007 * 00008 * Botan is released under the Simplified BSD License (see license.txt) 00009 * 00010 */ 00011 00012 #include <botan/polyn_gf2m.h> 00013 #include <botan/gf2m_rootfind_dcmp.h> 00014 #include <botan/code_based_util.h> 00015 #include <botan/gf2m_small_m.h> 00016 #include <botan/internal/bit_ops.h> 00017 00018 namespace Botan { 00019 00020 using namespace Botan::gf2m_small_m; 00021 00022 namespace { 00023 00024 gf2m generate_gf2m_mask(gf2m a) 00025 { 00026 gf2m result = (a != 0); 00027 return ~(result - 1); 00028 } 00029 00030 unsigned nlz_16bit(u16bit x) 00031 { 00032 unsigned n; 00033 if(x == 0) return 16; 00034 n = 0; 00035 if(x <= 0x00FF) {n = n + 8; x = x << 8;} 00036 if(x <= 0x0FFF) {n = n + 4; x = x << 4;} 00037 if(x <= 0x3FFF) {n = n + 2; x = x << 2;} 00038 if(x <= 0x7FFF) {n = n + 1;} 00039 return n; 00040 } 00041 } 00042 00043 using namespace Botan::gf2m_small_m; 00044 00045 int polyn_gf2m::calc_degree_secure() const 00046 { 00047 int i = this->coeff.size() - 1; 00048 int result = 0; 00049 u32bit found_mask = 0; 00050 u32bit tracker_mask = 0xffff; 00051 for( ; i >= 0; i--) 00052 { 00053 found_mask = expand_mask_16bit(this->coeff[i]); 00054 result |= i & found_mask & tracker_mask; 00055 // tracker mask shall become zero once found mask is set 00056 // it shall remain zero from then on 00057 tracker_mask = tracker_mask & ~found_mask; 00058 } 00059 const_cast<polyn_gf2m*>(this)->m_deg = result; 00060 return result; 00061 } 00062 /** 00063 * number of leading zeros 00064 */ 00065 00066 gf2m random_code_element(unsigned code_length, Botan::RandomNumberGenerator& rng) 00067 { 00068 if(code_length == 0) 00069 { 00070 throw Invalid_Argument("random_code_element() was supplied a code length of zero"); 00071 } 00072 unsigned nlz = nlz_16bit(code_length-1); 00073 gf2m mask = (1 << (16-nlz)) -1; 00074 gf2m result; 00075 do 00076 { 00077 rng.randomize(reinterpret_cast<byte*>(&result), sizeof(result)); 00078 result &= mask; 00079 } while(result >= code_length); // rejection sampling 00080 return result; 00081 } 00082 00083 polyn_gf2m::polyn_gf2m(polyn_gf2m const& other) 00084 :m_deg(other.m_deg), 00085 coeff(other.coeff), 00086 msp_field(other.msp_field) 00087 { } 00088 00089 polyn_gf2m::polyn_gf2m( int d, std::shared_ptr<gf2m_small_m::Gf2m_Field> sp_field) 00090 :m_deg(-1), 00091 coeff(d+1), 00092 msp_field(sp_field) 00093 { 00094 } 00095 00096 std::string polyn_gf2m::to_string() const 00097 { 00098 int d = get_degree(); 00099 std::string result; 00100 for(int i = 0; i <= d; i ++) 00101 { 00102 result += std::to_string(this->coeff[i]); 00103 if(i != d) 00104 { 00105 result += ", "; 00106 } 00107 } 00108 return result; 00109 } 00110 /** 00111 * doesn't save coefficients: 00112 */ 00113 void polyn_gf2m::realloc(u32bit new_size) 00114 { 00115 this->coeff = secure_vector<gf2m>(new_size); 00116 } 00117 00118 polyn_gf2m::polyn_gf2m(const byte* mem, u32bit mem_len, std::shared_ptr<gf2m_small_m::Gf2m_Field> sp_field) 00119 :msp_field(sp_field) 00120 { 00121 if(mem_len % sizeof(gf2m)) 00122 { 00123 throw new Botan::Decoding_Error("illegal length of memory to decode "); 00124 } 00125 00126 u32bit size = (mem_len / sizeof(this->coeff[0])) ; 00127 this->coeff = secure_vector<gf2m>(size); 00128 this->m_deg = -1; 00129 for(u32bit i = 0; i < size; i++) 00130 { 00131 this->coeff[i] = gf2m_small_m::decode_gf2m(mem); 00132 mem += sizeof(this->coeff[0]); 00133 } 00134 for(u32bit i = 0; i < size; i++) 00135 { 00136 if(this->coeff[i] >= (1 << sp_field->get_extension_degree())) 00137 { 00138 throw Botan::Decoding_Error("error decoding polynomial"); 00139 } 00140 } 00141 this->get_degree(); 00142 } 00143 00144 00145 polyn_gf2m::polyn_gf2m( std::shared_ptr<gf2m_small_m::Gf2m_Field> sp_field ) 00146 : m_deg(-1), 00147 coeff(1), 00148 msp_field(sp_field) 00149 {}; 00150 00151 polyn_gf2m::polyn_gf2m(int degree, const unsigned char* mem, u32bit mem_byte_len, std::shared_ptr<gf2m_small_m::Gf2m_Field> sp_field) 00152 :msp_field(sp_field) 00153 { 00154 u32bit j, k, l; 00155 gf2m a; 00156 u32bit polyn_size; 00157 polyn_size = degree + 1; 00158 if(polyn_size * sp_field->get_extension_degree() > 8 * mem_byte_len) 00159 { 00160 throw Botan::Decoding_Error("memory vector for polynomial has wrong size"); 00161 } 00162 this->coeff = secure_vector<gf2m>(degree+1); 00163 gf2m ext_deg = this->msp_field->get_extension_degree(); 00164 for (l = 0; l < polyn_size; l++) 00165 { 00166 k = (l * ext_deg) / 8; 00167 00168 j = (l * ext_deg) % 8; 00169 a = mem[k] >> j; 00170 if (j + ext_deg > 8) 00171 { 00172 a ^= mem[k + 1] << (8- j); 00173 } 00174 if(j + ext_deg > 16) 00175 { 00176 a ^= mem[k + 2] << (16- j); 00177 } 00178 a &= ((1 << ext_deg) - 1); 00179 (*this).set_coef( l, a); 00180 } 00181 00182 this->get_degree(); 00183 } 00184 00185 #if 0 00186 void polyn_gf2m::encode(u32bit min_numo_coeffs, byte* mem, u32bit mem_len) const 00187 { 00188 u32bit i; 00189 u32bit numo_coeffs, needed_size; 00190 this->get_degree(); 00191 numo_coeffs = (min_numo_coeffs > static_cast<u32bit>(this->m_deg+1)) ? min_numo_coeffs : this->m_deg+1; 00192 needed_size = sizeof(this->coeff[0]) * numo_coeffs; 00193 if(mem_len < needed_size) 00194 { 00195 Invalid_Argument("provided memory too small to encode polynomial"); 00196 } 00197 00198 for(i = 0; i < numo_coeffs; i++) 00199 { 00200 gf2m to_enc; 00201 if(i >= static_cast<u32bit>(this->m_deg+1)) 00202 { 00203 /* encode a zero */ 00204 to_enc = 0; 00205 } 00206 else 00207 { 00208 to_enc = this->coeff[i]; 00209 } 00210 mem += encode_gf2m(to_enc, mem); 00211 } 00212 } 00213 #endif 00214 00215 00216 void polyn_gf2m::set_to_zero() 00217 { 00218 clear_mem(&this->coeff[0], this->coeff.size()); 00219 this->m_deg = -1; 00220 } 00221 00222 int polyn_gf2m::get_degree() const 00223 { 00224 int d = this->coeff.size() - 1; 00225 while ((d >= 0) && (this->coeff[d] == 0)) 00226 --d; 00227 const_cast<polyn_gf2m*>(this)->m_deg = d; 00228 return d; 00229 } 00230 00231 00232 static gf2m eval_aux(const gf2m * /*restrict*/ coeff, gf2m a, int d, std::shared_ptr<gf2m_small_m::Gf2m_Field> sp_field) 00233 { 00234 gf2m b; 00235 b = coeff[d--]; 00236 for (; d >= 0; --d) 00237 if (b != 0) 00238 { 00239 b = sp_field->gf_mul(b, a) ^ coeff[d]; 00240 } 00241 else 00242 { 00243 b = coeff[d]; 00244 } 00245 return b; 00246 } 00247 00248 gf2m polyn_gf2m::eval(gf2m a) 00249 { 00250 return eval_aux(&this->coeff[0], a, this->m_deg, this->msp_field); 00251 } 00252 00253 00254 // p will contain it's remainder modulo g 00255 void polyn_gf2m::remainder(polyn_gf2m &p, const polyn_gf2m & g) 00256 { 00257 int i, j, d; 00258 std::shared_ptr<gf2m_small_m::Gf2m_Field> msp_field = g.msp_field; 00259 d = p.get_degree() - g.get_degree(); 00260 if (d >= 0) { 00261 gf2m la = msp_field->gf_inv_rn(g.get_lead_coef()); 00262 00263 for (i = p.get_degree(); d >= 0; --i, --d) { 00264 if (p[i] != 0) { 00265 gf2m lb = msp_field->gf_mul_rrn(la, p[i]); 00266 for (j = 0; j < g.get_degree(); ++j) 00267 { 00268 p[j+d] ^= msp_field->gf_mul_zrz(lb, g[j]); 00269 } 00270 (*&p).set_coef( i, 0); 00271 } 00272 } 00273 p.set_degree( g.get_degree() - 1); 00274 while ((p.get_degree() >= 0) && (p[p.get_degree()] == 0)) 00275 p.set_degree( p.get_degree() - 1); 00276 } 00277 } 00278 00279 std::vector<polyn_gf2m> polyn_gf2m::sqmod_init(const polyn_gf2m & g) 00280 { 00281 std::vector<polyn_gf2m> sq; 00282 const int signed_deg = g.get_degree(); 00283 if(signed_deg <= 0) 00284 throw Invalid_Argument("cannot compute sqmod for such low degree"); 00285 00286 const u32bit d = static_cast<u32bit>(signed_deg); 00287 u32bit t = g.m_deg; 00288 // create t zero polynomials 00289 u32bit i; 00290 for (i = 0; i < t; ++i) 00291 { 00292 sq.push_back(polyn_gf2m(t+1, g.get_sp_field())); 00293 } 00294 for (i = 0; i < d / 2; ++i) 00295 { 00296 sq[i].set_degree( 2 * i); 00297 (*&sq[i]).set_coef( 2 * i, 1); 00298 } 00299 00300 for (; i < d; ++i) 00301 { 00302 clear_mem(&sq[i].coeff[0], 2); 00303 copy_mem(&sq[i].coeff[0] + 2, &sq[i - 1].coeff[0], d); 00304 sq[i].set_degree( sq[i - 1].get_degree() + 2); 00305 polyn_gf2m::remainder(sq[i], g); 00306 } 00307 return sq; 00308 } 00309 00310 /*Modulo p square of a certain polynomial g, sq[] contains the square 00311 Modulo g of the base canonical polynomials of degree < d, where d is 00312 the degree of G. The table sq[] will be calculated by polyn_gf2m__sqmod_init*/ 00313 polyn_gf2m polyn_gf2m::sqmod( const std::vector<polyn_gf2m> & sq, int d) 00314 { 00315 int i, j; 00316 gf2m la; 00317 std::shared_ptr<gf2m_small_m::Gf2m_Field> sp_field = this->msp_field; 00318 00319 polyn_gf2m result(d - 1, sp_field); 00320 // terms of low degree 00321 for (i = 0; i < d / 2; ++i) 00322 { 00323 (*&result).set_coef( i * 2, sp_field->gf_square((*this)[i])); 00324 } 00325 00326 // terms of high degree 00327 for (; i < d; ++i) 00328 { 00329 gf2m lpi = (*this)[i]; 00330 if (lpi != 0) 00331 { 00332 lpi = sp_field->gf_log(lpi); 00333 la = sp_field->gf_mul_rrr(lpi, lpi); 00334 for (j = 0; j < d; ++j) 00335 { 00336 result[j] ^= sp_field->gf_mul_zrz(la, sq[i][j]); 00337 } 00338 } 00339 } 00340 00341 // Update degre 00342 result.set_degree( d - 1); 00343 while ((result.get_degree() >= 0) && (result[result.get_degree()] == 0)) 00344 result.set_degree( result.get_degree() - 1); 00345 return result; 00346 } 00347 00348 00349 // destructive 00350 polyn_gf2m polyn_gf2m::gcd_aux(polyn_gf2m& p1, polyn_gf2m& p2) 00351 { 00352 if (p2.get_degree() == -1) 00353 return p1; 00354 else { 00355 polyn_gf2m::remainder(p1, p2); 00356 return polyn_gf2m::gcd_aux(p2, p1); 00357 } 00358 } 00359 00360 00361 polyn_gf2m polyn_gf2m::gcd(polyn_gf2m const& p1, polyn_gf2m const& p2) 00362 { 00363 polyn_gf2m a(p1); 00364 polyn_gf2m b(p2); 00365 if (a.get_degree() < b.get_degree()) 00366 { 00367 return polyn_gf2m(polyn_gf2m::gcd_aux(b, a)); 00368 } 00369 else 00370 { 00371 return polyn_gf2m(polyn_gf2m::gcd_aux(a, b)); 00372 } 00373 } 00374 00375 00376 00377 00378 00379 // Returns the degree of the smallest factor 00380 void polyn_gf2m::degppf(const polyn_gf2m & g, int* p_result) 00381 { 00382 int i, d; 00383 polyn_gf2m s(g.get_sp_field()); 00384 00385 d = g.get_degree(); 00386 std::vector<polyn_gf2m> u = polyn_gf2m::sqmod_init(g); 00387 00388 polyn_gf2m p( d - 1, g.msp_field); 00389 00390 p.set_degree( 1); 00391 (*&p).set_coef( 1, 1); 00392 (*p_result) = d; 00393 for (i = 1; i <= (d / 2) * g.msp_field->get_extension_degree(); ++i) 00394 { 00395 polyn_gf2m r = p.sqmod(u, d); 00396 if ((i % g.msp_field->get_extension_degree()) == 0) 00397 { 00398 r[1] ^= 1; 00399 r.get_degree(); // The degree may change 00400 s = polyn_gf2m::gcd( g, r); 00401 00402 if (s.get_degree() > 0) 00403 { 00404 (*p_result) = i / g.msp_field->get_extension_degree(); 00405 break; 00406 } 00407 r[1] ^= 1; 00408 r.get_degree(); // The degree may change 00409 } 00410 // No need for the exchange s 00411 s = p; 00412 p = r; 00413 r = s; 00414 } 00415 00416 00417 } 00418 00419 void polyn_gf2m::patchup_deg_secure( u32bit trgt_deg, volatile gf2m patch_elem) 00420 { 00421 u32bit i; 00422 if(this->coeff.size() < trgt_deg) 00423 { 00424 return; 00425 } 00426 for(i = 0; i < this->coeff.size(); i++) 00427 { 00428 u32bit equal, equal_mask; 00429 this->coeff[i] |= patch_elem; 00430 equal = (i == trgt_deg); 00431 equal_mask = expand_mask_16bit(equal); 00432 patch_elem &= ~equal_mask; 00433 } 00434 this->calc_degree_secure(); 00435 } 00436 // We suppose m_deg(g) >= m_deg(p) 00437 // v is the problem 00438 std::pair<polyn_gf2m, polyn_gf2m> polyn_gf2m::eea_with_coefficients( const polyn_gf2m & p, const polyn_gf2m & g, int break_deg) 00439 { 00440 00441 std::shared_ptr<gf2m_small_m::Gf2m_Field> msp_field = g.msp_field; 00442 int i, j, dr, du, delta; 00443 gf2m a; 00444 polyn_gf2m aux; 00445 00446 // initialisation of the local variables 00447 // r0 <- g, r1 <- p, u0 <- 0, u1 <- 1 00448 dr = g.get_degree(); 00449 00450 polyn_gf2m r0(dr, g.msp_field); 00451 polyn_gf2m r1(dr - 1, g.msp_field); 00452 polyn_gf2m u0(dr - 1, g.msp_field); 00453 polyn_gf2m u1(dr - 1, g.msp_field); 00454 00455 r0 = g; 00456 r1 = p; 00457 u0.set_to_zero(); 00458 u1.set_to_zero(); 00459 (*&u1).set_coef( 0, 1); 00460 u1.set_degree( 0); 00461 00462 00463 // invariants: 00464 // r1 = u1 * p + v1 * g 00465 // r0 = u0 * p + v0 * g 00466 // and m_deg(u1) = m_deg(g) - m_deg(r0) 00467 // It stops when m_deg (r1) <t (m_deg (r0)> = t) 00468 // And therefore m_deg (u1) = m_deg (g) - m_deg (r0) <m_deg (g) - break_deg 00469 du = 0; 00470 dr = r1.get_degree(); 00471 delta = r0.get_degree() - dr; 00472 00473 00474 while (dr >= break_deg) 00475 { 00476 00477 for (j = delta; j >= 0; --j) 00478 { 00479 a = msp_field->gf_div(r0[dr + j], r1[dr]); 00480 if (a != 0) 00481 { 00482 gf2m la = msp_field->gf_log(a); 00483 // u0(z) <- u0(z) + a * u1(z) * z^j 00484 for (i = 0; i <= du; ++i) 00485 { 00486 u0[i + j] ^= msp_field->gf_mul_zrz(la, u1[i]); 00487 } 00488 // r0(z) <- r0(z) + a * r1(z) * z^j 00489 for (i = 0; i <= dr; ++i) 00490 { 00491 r0[i + j] ^= msp_field->gf_mul_zrz(la, r1[i]); 00492 } 00493 } 00494 } // end loop over j 00495 00496 if(break_deg != 1) /* key eq. solving */ 00497 { 00498 /* [ssms_icisc09] Countermeasure 00499 * d_break from paper equals break_deg - 1 00500 * */ 00501 00502 volatile gf2m fake_elem = 0x01; 00503 volatile gf2m cond1, cond2; 00504 int trgt_deg = r1.get_degree() - 1; 00505 r0.calc_degree_secure(); 00506 u0.calc_degree_secure(); 00507 if(!(g.get_degree() % 2)) 00508 { 00509 /* t even */ 00510 cond1 = r0.get_degree() < break_deg - 1; 00511 } 00512 else 00513 { 00514 /* t odd */ 00515 cond1 = r0.get_degree() <= break_deg - 1; 00516 cond2 = u0.get_degree() < break_deg - 1; 00517 cond1 &= cond2; 00518 } 00519 /* expand cond1 to a full mask */ 00520 //CSEC_MASK__GEN_MASK_16B(cond1, mask); 00521 gf2m mask = generate_gf2m_mask(cond1); 00522 fake_elem &= mask; 00523 r0.patchup_deg_secure(trgt_deg, fake_elem); 00524 } 00525 if(break_deg == 1) /* syndrome inversion */ 00526 { 00527 volatile gf2m fake_elem = 0x00; 00528 volatile u32bit trgt_deg = 0; 00529 r0.calc_degree_secure(); 00530 u0.calc_degree_secure(); 00531 /** 00532 * countermeasure against the low weight attacks for w=4, w=6 and w=8. 00533 * Higher values are not covered since for w=8 we already have a 00534 * probability for a positive of 1/n^3 from random ciphertexts with the 00535 * given weight. For w = 10 it would be 1/n^4 and so on. Thus attacks 00536 * based on such high values of w are considered impractical. 00537 * 00538 * The outer test for the degree of u ( Omega in the paper ) needs not to 00539 * be disguised. Each of the three is performed at most once per EEA 00540 * (syndrome inversion) execution, the attacker knows this already when 00541 * preparing the ciphertext with the given weight. Inside these three 00542 * cases however, we must use timing neutral (branch free) operations to 00543 * implement the condition detection and the counteractions. 00544 * 00545 */ 00546 if(u0.get_degree() == 4) 00547 { 00548 u32bit mask = 0; 00549 /** 00550 * Condition that the EEA would break now 00551 */ 00552 int cond_r = r0.get_degree() == 0; 00553 /** 00554 * Now come the conditions for all odd coefficients of this sigma 00555 * candiate. If they are all fulfilled, then we know that we have a low 00556 * weight error vector, since the key-equation solving EEA is skipped if 00557 * the degree of tau^2 is low (=m_deg(u0)) and all its odd cofficients are 00558 * zero (they would cause "full-lenght" contributions from the square 00559 * root computation). 00560 */ 00561 // Condition for the coefficient to Y to be cancelled out by the 00562 // addition of Y before the square root computation: 00563 int cond_u1 = msp_field->gf_mul(u0.coeff[1], msp_field->gf_inv(r0.coeff[0])) == 1; 00564 00565 // Condition sigma_3 = 0: 00566 int cond_u3 = u0.coeff[3] == 0; 00567 // combine the conditions: 00568 cond_r &= (cond_u1 & cond_u3); 00569 // mask generation: 00570 mask = expand_mask_16bit(cond_r); 00571 trgt_deg = 2 & mask; 00572 fake_elem = 1 & mask; 00573 } 00574 else if(u0.get_degree() == 6) 00575 { 00576 u32bit mask = 0; 00577 int cond_r= r0.get_degree() == 0; 00578 int cond_u1 = msp_field->gf_mul(u0.coeff[1], msp_field->gf_inv(r0.coeff[0])) == 1; 00579 int cond_u3 = u0.coeff[3] == 0; 00580 00581 int cond_u5 = u0.coeff[5] == 0; 00582 00583 cond_r &= (cond_u1 & cond_u3 & cond_u5); 00584 mask = expand_mask_16bit(cond_r); 00585 trgt_deg = 4 & mask; 00586 fake_elem = 1 & mask; 00587 } 00588 else if(u0.get_degree() == 8) 00589 { 00590 u32bit mask = 0; 00591 int cond_r= r0.get_degree() == 0; 00592 int cond_u1 = msp_field->gf_mul(u0[1], msp_field->gf_inv(r0[0])) == 1; 00593 int cond_u3 = u0.coeff[3] == 0; 00594 00595 int cond_u5 = u0.coeff[5] == 0; 00596 00597 int cond_u7 = u0.coeff[7] == 0; 00598 00599 cond_r &= (cond_u1 & cond_u3 & cond_u5 & cond_u7); 00600 mask = expand_mask_16bit(cond_r); 00601 trgt_deg = 6 & mask; 00602 fake_elem = 1 & mask; 00603 } 00604 r0.patchup_deg_secure(trgt_deg, fake_elem); 00605 } 00606 // exchange 00607 aux = r0; r0 = r1; r1 = aux; 00608 aux = u0; u0 = u1; u1 = aux; 00609 00610 du = du + delta; 00611 delta = 1; 00612 while (r1[dr - delta] == 0) 00613 { 00614 delta++; 00615 } 00616 00617 00618 dr -= delta; 00619 } /* end while loop (dr >= break_deg) */ 00620 00621 00622 u1.set_degree( du); 00623 r1.set_degree( dr); 00624 //return u1 and r1; 00625 return std::make_pair(u1,r1); // coefficients u,v 00626 } 00627 00628 polyn_gf2m::polyn_gf2m(int t, Botan::RandomNumberGenerator& rng, std::shared_ptr<gf2m_small_m::Gf2m_Field> sp_field) 00629 :m_deg(t), 00630 coeff(t+1), 00631 msp_field(sp_field) 00632 { 00633 int i; 00634 (*this).set_coef( t, 1); 00635 i = 0; 00636 int m_deg; 00637 do 00638 { 00639 for (i = 0; i < t; ++i) 00640 { 00641 (*this).set_coef( i, random_code_element(sp_field->get_cardinality(), rng)); 00642 } 00643 polyn_gf2m::degppf(*this, &m_deg); 00644 } 00645 while (m_deg < t); 00646 } 00647 00648 00649 void polyn_gf2m::poly_shiftmod( const polyn_gf2m & g) 00650 { 00651 int i, t; 00652 gf2m a; 00653 00654 if(g.get_degree() <= 0) 00655 { 00656 throw Invalid_Argument("shiftmod cannot be called on polynomials of degree 0 or less"); 00657 } 00658 std::shared_ptr<gf2m_small_m::Gf2m_Field> msp_field = g.msp_field; 00659 00660 t = g.get_degree(); 00661 a = msp_field->gf_div(this->coeff[t-1], g.coeff[t]); 00662 for (i = t - 1; i > 0; --i) 00663 { 00664 this->coeff[i] = this->coeff[i - 1] ^ this->msp_field->gf_mul(a, g.coeff[i]); 00665 } 00666 this->coeff[0] = msp_field->gf_mul(a, g.coeff[0]); 00667 } 00668 00669 std::vector<polyn_gf2m> polyn_gf2m::sqrt_mod_init(const polyn_gf2m & g) 00670 { 00671 u32bit i, t; 00672 u32bit nb_polyn_sqrt_mat; 00673 std::shared_ptr<gf2m_small_m::Gf2m_Field> msp_field = g.msp_field; 00674 std::vector<polyn_gf2m> result; 00675 t = g.get_degree(); 00676 nb_polyn_sqrt_mat = t/2; 00677 00678 std::vector<polyn_gf2m> sq_aux = polyn_gf2m::sqmod_init(g); 00679 00680 00681 polyn_gf2m p( t - 1, g.get_sp_field()); 00682 p.set_degree( 1); 00683 00684 (*&p).set_coef( 1, 1); 00685 // q(z) = 0, p(z) = z 00686 for (i = 0; i < t * msp_field->get_extension_degree() - 1; ++i) 00687 { 00688 // q(z) <- p(z)^2 mod g(z) 00689 polyn_gf2m q = p.sqmod(sq_aux, t); 00690 // q(z) <-> p(z) 00691 polyn_gf2m aux = q; 00692 q = p; 00693 p = aux; 00694 } 00695 // p(z) = z^(2^(tm-1)) mod g(z) = sqrt(z) mod g(z) 00696 00697 for (i = 0; i < nb_polyn_sqrt_mat; ++i) 00698 { 00699 result.push_back(polyn_gf2m(t - 1, g.get_sp_field())); 00700 } 00701 00702 result[0] = p; 00703 result[0].get_degree(); 00704 for(i = 1; i < nb_polyn_sqrt_mat; i++) 00705 { 00706 result[i] = result[i - 1]; 00707 result[i].poly_shiftmod(g), 00708 result[i].get_degree(); 00709 } 00710 00711 return result; 00712 } 00713 00714 std::vector<polyn_gf2m> syndrome_init(polyn_gf2m const& generator, std::vector<gf2m> const& support, int n) 00715 { 00716 int i,j,t; 00717 gf2m a; 00718 00719 00720 std::shared_ptr<gf2m_small_m::Gf2m_Field> msp_field = generator.msp_field; 00721 00722 std::vector<polyn_gf2m> result; 00723 t = generator.get_degree(); 00724 00725 //g(z)=g_t+g_(t-1).z^(t-1)+......+g_1.z+g_0 00726 //f(z)=f_(t-1).z^(t-1)+......+f_1.z+f_0 00727 00728 for(j=0;j<n;j++) 00729 { 00730 result.push_back(polyn_gf2m( t-1, msp_field)); 00731 00732 (*&result[j]).set_coef(t-1,1); 00733 for(i=t-2;i>=0;i--) 00734 { 00735 (*&result[j]).set_coef(i, (generator)[i+1] ^ 00736 msp_field->gf_mul(lex_to_gray(support[j]),result[j][i+1])); 00737 } 00738 a = ((generator)[0] ^ msp_field->gf_mul(lex_to_gray(support[j]),result[j][0])); 00739 for(i=0;i<t;i++) 00740 { 00741 (*&result[j]).set_coef(i, msp_field->gf_div(result[j][i],a)); 00742 } 00743 } 00744 return result; 00745 } 00746 00747 polyn_gf2m::polyn_gf2m(const secure_vector<byte>& encoded, std::shared_ptr<gf2m_small_m::Gf2m_Field> sp_field ) 00748 :msp_field(sp_field) 00749 { 00750 if(encoded.size() % 2) 00751 { 00752 throw Decoding_Error("encoded polynomial has odd length"); 00753 } 00754 for(u32bit i = 0; i < encoded.size(); i += 2) 00755 { 00756 gf2m el = (encoded[i] << 8) | encoded[i + 1]; 00757 coeff.push_back(el); 00758 } 00759 get_degree(); 00760 00761 } 00762 secure_vector<byte> polyn_gf2m::encode() const 00763 { 00764 secure_vector<byte> result; 00765 00766 if(m_deg < 1) 00767 { 00768 result.push_back(0); 00769 result.push_back(0); 00770 return result; 00771 } 00772 00773 u32bit len = m_deg+1; 00774 for(unsigned i = 0; i < len; i++) 00775 { 00776 // "big endian" encoding of the GF(2^m) elements 00777 result.push_back(coeff[i] >> 8); 00778 result.push_back(coeff[i]); 00779 } 00780 return result; 00781 } 00782 00783 void polyn_gf2m::swap(polyn_gf2m& other) 00784 { 00785 std::swap(this->m_deg, other.m_deg); 00786 std::swap(this->msp_field, other.msp_field); 00787 std::swap(this->coeff, other.coeff); 00788 } 00789 00790 bool polyn_gf2m::operator==(const polyn_gf2m & other) const 00791 { 00792 if(m_deg != other.m_deg || coeff != other.coeff) 00793 { 00794 return false; 00795 } 00796 return true; 00797 } 00798 00799 }