Crypto++
|
00001 // gf2n.cpp - written and placed in the public domain by Wei Dai 00002 00003 #include "pch.h" 00004 00005 #ifndef CRYPTOPP_IMPORTS 00006 00007 #include "gf2n.h" 00008 #include "algebra.h" 00009 #include "words.h" 00010 #include "randpool.h" 00011 #include "asn.h" 00012 #include "oids.h" 00013 00014 #include <iostream> 00015 00016 NAMESPACE_BEGIN(CryptoPP) 00017 00018 PolynomialMod2::PolynomialMod2() 00019 { 00020 } 00021 00022 PolynomialMod2::PolynomialMod2(word value, size_t bitLength) 00023 : reg(BitsToWords(bitLength)) 00024 { 00025 assert(value==0 || reg.size()>0); 00026 00027 if (reg.size() > 0) 00028 { 00029 reg[0] = value; 00030 SetWords(reg+1, 0, reg.size()-1); 00031 } 00032 } 00033 00034 PolynomialMod2::PolynomialMod2(const PolynomialMod2& t) 00035 : reg(t.reg.size()) 00036 { 00037 CopyWords(reg, t.reg, reg.size()); 00038 } 00039 00040 void PolynomialMod2::Randomize(RandomNumberGenerator &rng, size_t nbits) 00041 { 00042 const size_t nbytes = nbits/8 + 1; 00043 SecByteBlock buf(nbytes); 00044 rng.GenerateBlock(buf, nbytes); 00045 buf[0] = (byte)Crop(buf[0], nbits % 8); 00046 Decode(buf, nbytes); 00047 } 00048 00049 PolynomialMod2 PolynomialMod2::AllOnes(size_t bitLength) 00050 { 00051 PolynomialMod2 result((word)0, bitLength); 00052 SetWords(result.reg, ~(word)0, result.reg.size()); 00053 if (bitLength%WORD_BITS) 00054 result.reg[result.reg.size()-1] = (word)Crop(result.reg[result.reg.size()-1], bitLength%WORD_BITS); 00055 return result; 00056 } 00057 00058 void PolynomialMod2::SetBit(size_t n, int value) 00059 { 00060 if (value) 00061 { 00062 reg.CleanGrow(n/WORD_BITS + 1); 00063 reg[n/WORD_BITS] |= (word(1) << (n%WORD_BITS)); 00064 } 00065 else 00066 { 00067 if (n/WORD_BITS < reg.size()) 00068 reg[n/WORD_BITS] &= ~(word(1) << (n%WORD_BITS)); 00069 } 00070 } 00071 00072 byte PolynomialMod2::GetByte(size_t n) const 00073 { 00074 if (n/WORD_SIZE >= reg.size()) 00075 return 0; 00076 else 00077 return byte(reg[n/WORD_SIZE] >> ((n%WORD_SIZE)*8)); 00078 } 00079 00080 void PolynomialMod2::SetByte(size_t n, byte value) 00081 { 00082 reg.CleanGrow(BytesToWords(n+1)); 00083 reg[n/WORD_SIZE] &= ~(word(0xff) << 8*(n%WORD_SIZE)); 00084 reg[n/WORD_SIZE] |= (word(value) << 8*(n%WORD_SIZE)); 00085 } 00086 00087 PolynomialMod2 PolynomialMod2::Monomial(size_t i) 00088 { 00089 PolynomialMod2 r((word)0, i+1); 00090 r.SetBit(i); 00091 return r; 00092 } 00093 00094 PolynomialMod2 PolynomialMod2::Trinomial(size_t t0, size_t t1, size_t t2) 00095 { 00096 PolynomialMod2 r((word)0, t0+1); 00097 r.SetBit(t0); 00098 r.SetBit(t1); 00099 r.SetBit(t2); 00100 return r; 00101 } 00102 00103 PolynomialMod2 PolynomialMod2::Pentanomial(size_t t0, size_t t1, size_t t2, size_t t3, size_t t4) 00104 { 00105 PolynomialMod2 r((word)0, t0+1); 00106 r.SetBit(t0); 00107 r.SetBit(t1); 00108 r.SetBit(t2); 00109 r.SetBit(t3); 00110 r.SetBit(t4); 00111 return r; 00112 } 00113 00114 template <word i> 00115 struct NewPolynomialMod2 00116 { 00117 PolynomialMod2 * operator()() const 00118 { 00119 return new PolynomialMod2(i); 00120 } 00121 }; 00122 00123 const PolynomialMod2 &PolynomialMod2::Zero() 00124 { 00125 return Singleton<PolynomialMod2>().Ref(); 00126 } 00127 00128 const PolynomialMod2 &PolynomialMod2::One() 00129 { 00130 return Singleton<PolynomialMod2, NewPolynomialMod2<1> >().Ref(); 00131 } 00132 00133 void PolynomialMod2::Decode(const byte *input, size_t inputLen) 00134 { 00135 StringStore store(input, inputLen); 00136 Decode(store, inputLen); 00137 } 00138 00139 void PolynomialMod2::Encode(byte *output, size_t outputLen) const 00140 { 00141 ArraySink sink(output, outputLen); 00142 Encode(sink, outputLen); 00143 } 00144 00145 void PolynomialMod2::Decode(BufferedTransformation &bt, size_t inputLen) 00146 { 00147 reg.CleanNew(BytesToWords(inputLen)); 00148 00149 for (size_t i=inputLen; i > 0; i--) 00150 { 00151 byte b; 00152 bt.Get(b); 00153 reg[(i-1)/WORD_SIZE] |= word(b) << ((i-1)%WORD_SIZE)*8; 00154 } 00155 } 00156 00157 void PolynomialMod2::Encode(BufferedTransformation &bt, size_t outputLen) const 00158 { 00159 for (size_t i=outputLen; i > 0; i--) 00160 bt.Put(GetByte(i-1)); 00161 } 00162 00163 void PolynomialMod2::DEREncodeAsOctetString(BufferedTransformation &bt, size_t length) const 00164 { 00165 DERGeneralEncoder enc(bt, OCTET_STRING); 00166 Encode(enc, length); 00167 enc.MessageEnd(); 00168 } 00169 00170 void PolynomialMod2::BERDecodeAsOctetString(BufferedTransformation &bt, size_t length) 00171 { 00172 BERGeneralDecoder dec(bt, OCTET_STRING); 00173 if (!dec.IsDefiniteLength() || dec.RemainingLength() != length) 00174 BERDecodeError(); 00175 Decode(dec, length); 00176 dec.MessageEnd(); 00177 } 00178 00179 unsigned int PolynomialMod2::WordCount() const 00180 { 00181 return (unsigned int)CountWords(reg, reg.size()); 00182 } 00183 00184 unsigned int PolynomialMod2::ByteCount() const 00185 { 00186 unsigned wordCount = WordCount(); 00187 if (wordCount) 00188 return (wordCount-1)*WORD_SIZE + BytePrecision(reg[wordCount-1]); 00189 else 00190 return 0; 00191 } 00192 00193 unsigned int PolynomialMod2::BitCount() const 00194 { 00195 unsigned wordCount = WordCount(); 00196 if (wordCount) 00197 return (wordCount-1)*WORD_BITS + BitPrecision(reg[wordCount-1]); 00198 else 00199 return 0; 00200 } 00201 00202 unsigned int PolynomialMod2::Parity() const 00203 { 00204 unsigned i; 00205 word temp=0; 00206 for (i=0; i<reg.size(); i++) 00207 temp ^= reg[i]; 00208 return CryptoPP::Parity(temp); 00209 } 00210 00211 PolynomialMod2& PolynomialMod2::operator=(const PolynomialMod2& t) 00212 { 00213 reg.Assign(t.reg); 00214 return *this; 00215 } 00216 00217 PolynomialMod2& PolynomialMod2::operator^=(const PolynomialMod2& t) 00218 { 00219 reg.CleanGrow(t.reg.size()); 00220 XorWords(reg, t.reg, t.reg.size()); 00221 return *this; 00222 } 00223 00224 PolynomialMod2 PolynomialMod2::Xor(const PolynomialMod2 &b) const 00225 { 00226 if (b.reg.size() >= reg.size()) 00227 { 00228 PolynomialMod2 result((word)0, b.reg.size()*WORD_BITS); 00229 XorWords(result.reg, reg, b.reg, reg.size()); 00230 CopyWords(result.reg+reg.size(), b.reg+reg.size(), b.reg.size()-reg.size()); 00231 return result; 00232 } 00233 else 00234 { 00235 PolynomialMod2 result((word)0, reg.size()*WORD_BITS); 00236 XorWords(result.reg, reg, b.reg, b.reg.size()); 00237 CopyWords(result.reg+b.reg.size(), reg+b.reg.size(), reg.size()-b.reg.size()); 00238 return result; 00239 } 00240 } 00241 00242 PolynomialMod2 PolynomialMod2::And(const PolynomialMod2 &b) const 00243 { 00244 PolynomialMod2 result((word)0, WORD_BITS*STDMIN(reg.size(), b.reg.size())); 00245 AndWords(result.reg, reg, b.reg, result.reg.size()); 00246 return result; 00247 } 00248 00249 PolynomialMod2 PolynomialMod2::Times(const PolynomialMod2 &b) const 00250 { 00251 PolynomialMod2 result((word)0, BitCount() + b.BitCount()); 00252 00253 for (int i=b.Degree(); i>=0; i--) 00254 { 00255 result <<= 1; 00256 if (b[i]) 00257 XorWords(result.reg, reg, reg.size()); 00258 } 00259 return result; 00260 } 00261 00262 PolynomialMod2 PolynomialMod2::Squared() const 00263 { 00264 static const word map[16] = {0, 1, 4, 5, 16, 17, 20, 21, 64, 65, 68, 69, 80, 81, 84, 85}; 00265 00266 PolynomialMod2 result((word)0, 2*reg.size()*WORD_BITS); 00267 00268 for (unsigned i=0; i<reg.size(); i++) 00269 { 00270 unsigned j; 00271 00272 for (j=0; j<WORD_BITS; j+=8) 00273 result.reg[2*i] |= map[(reg[i] >> (j/2)) % 16] << j; 00274 00275 for (j=0; j<WORD_BITS; j+=8) 00276 result.reg[2*i+1] |= map[(reg[i] >> (j/2 + WORD_BITS/2)) % 16] << j; 00277 } 00278 00279 return result; 00280 } 00281 00282 void PolynomialMod2::Divide(PolynomialMod2 &remainder, PolynomialMod2 "ient, 00283 const PolynomialMod2 ÷nd, const PolynomialMod2 &divisor) 00284 { 00285 if (!divisor) 00286 throw PolynomialMod2::DivideByZero(); 00287 00288 int degree = divisor.Degree(); 00289 remainder.reg.CleanNew(BitsToWords(degree+1)); 00290 if (dividend.BitCount() >= divisor.BitCount()) 00291 quotient.reg.CleanNew(BitsToWords(dividend.BitCount() - divisor.BitCount() + 1)); 00292 else 00293 quotient.reg.CleanNew(0); 00294 00295 for (int i=dividend.Degree(); i>=0; i--) 00296 { 00297 remainder <<= 1; 00298 remainder.reg[0] |= dividend[i]; 00299 if (remainder[degree]) 00300 { 00301 remainder -= divisor; 00302 quotient.SetBit(i); 00303 } 00304 } 00305 } 00306 00307 PolynomialMod2 PolynomialMod2::DividedBy(const PolynomialMod2 &b) const 00308 { 00309 PolynomialMod2 remainder, quotient; 00310 PolynomialMod2::Divide(remainder, quotient, *this, b); 00311 return quotient; 00312 } 00313 00314 PolynomialMod2 PolynomialMod2::Modulo(const PolynomialMod2 &b) const 00315 { 00316 PolynomialMod2 remainder, quotient; 00317 PolynomialMod2::Divide(remainder, quotient, *this, b); 00318 return remainder; 00319 } 00320 00321 PolynomialMod2& PolynomialMod2::operator<<=(unsigned int n) 00322 { 00323 if (!reg.size()) 00324 return *this; 00325 00326 int i; 00327 word u; 00328 word carry=0; 00329 word *r=reg; 00330 00331 if (n==1) // special case code for most frequent case 00332 { 00333 i = (int)reg.size(); 00334 while (i--) 00335 { 00336 u = *r; 00337 *r = (u << 1) | carry; 00338 carry = u >> (WORD_BITS-1); 00339 r++; 00340 } 00341 00342 if (carry) 00343 { 00344 reg.Grow(reg.size()+1); 00345 reg[reg.size()-1] = carry; 00346 } 00347 00348 return *this; 00349 } 00350 00351 int shiftWords = n / WORD_BITS; 00352 int shiftBits = n % WORD_BITS; 00353 00354 if (shiftBits) 00355 { 00356 i = (int)reg.size(); 00357 while (i--) 00358 { 00359 u = *r; 00360 *r = (u << shiftBits) | carry; 00361 carry = u >> (WORD_BITS-shiftBits); 00362 r++; 00363 } 00364 } 00365 00366 if (carry) 00367 { 00368 reg.Grow(reg.size()+shiftWords+1); 00369 reg[reg.size()-1] = carry; 00370 } 00371 else 00372 reg.Grow(reg.size()+shiftWords); 00373 00374 if (shiftWords) 00375 { 00376 for (i = (int)reg.size()-1; i>=shiftWords; i--) 00377 reg[i] = reg[i-shiftWords]; 00378 for (; i>=0; i--) 00379 reg[i] = 0; 00380 } 00381 00382 return *this; 00383 } 00384 00385 PolynomialMod2& PolynomialMod2::operator>>=(unsigned int n) 00386 { 00387 if (!reg.size()) 00388 return *this; 00389 00390 int shiftWords = n / WORD_BITS; 00391 int shiftBits = n % WORD_BITS; 00392 00393 size_t i; 00394 word u; 00395 word carry=0; 00396 word *r=reg+reg.size()-1; 00397 00398 if (shiftBits) 00399 { 00400 i = reg.size(); 00401 while (i--) 00402 { 00403 u = *r; 00404 *r = (u >> shiftBits) | carry; 00405 carry = u << (WORD_BITS-shiftBits); 00406 r--; 00407 } 00408 } 00409 00410 if (shiftWords) 00411 { 00412 for (i=0; i<reg.size()-shiftWords; i++) 00413 reg[i] = reg[i+shiftWords]; 00414 for (; i<reg.size(); i++) 00415 reg[i] = 0; 00416 } 00417 00418 return *this; 00419 } 00420 00421 PolynomialMod2 PolynomialMod2::operator<<(unsigned int n) const 00422 { 00423 PolynomialMod2 result(*this); 00424 return result<<=n; 00425 } 00426 00427 PolynomialMod2 PolynomialMod2::operator>>(unsigned int n) const 00428 { 00429 PolynomialMod2 result(*this); 00430 return result>>=n; 00431 } 00432 00433 bool PolynomialMod2::operator!() const 00434 { 00435 for (unsigned i=0; i<reg.size(); i++) 00436 if (reg[i]) return false; 00437 return true; 00438 } 00439 00440 bool PolynomialMod2::Equals(const PolynomialMod2 &rhs) const 00441 { 00442 size_t i, smallerSize = STDMIN(reg.size(), rhs.reg.size()); 00443 00444 for (i=0; i<smallerSize; i++) 00445 if (reg[i] != rhs.reg[i]) return false; 00446 00447 for (i=smallerSize; i<reg.size(); i++) 00448 if (reg[i] != 0) return false; 00449 00450 for (i=smallerSize; i<rhs.reg.size(); i++) 00451 if (rhs.reg[i] != 0) return false; 00452 00453 return true; 00454 } 00455 00456 std::ostream& operator<<(std::ostream& out, const PolynomialMod2 &a) 00457 { 00458 // Get relevant conversion specifications from ostream. 00459 long f = out.flags() & std::ios::basefield; // Get base digits. 00460 int bits, block; 00461 char suffix; 00462 switch(f) 00463 { 00464 case std::ios::oct : 00465 bits = 3; 00466 block = 4; 00467 suffix = 'o'; 00468 break; 00469 case std::ios::hex : 00470 bits = 4; 00471 block = 2; 00472 suffix = 'h'; 00473 break; 00474 default : 00475 bits = 1; 00476 block = 8; 00477 suffix = 'b'; 00478 } 00479 00480 if (!a) 00481 return out << '0' << suffix; 00482 00483 SecBlock<char> s(a.BitCount()/bits+1); 00484 unsigned i; 00485 00486 static const char upper[]="0123456789ABCDEF"; 00487 static const char lower[]="0123456789abcdef"; 00488 const char* vec = (out.flags() & std::ios::uppercase) ? upper : lower; 00489 00490 for (i=0; i*bits < a.BitCount(); i++) 00491 { 00492 int digit=0; 00493 for (int j=0; j<bits; j++) 00494 digit |= a[i*bits+j] << j; 00495 s[i]=vec[digit]; 00496 } 00497 00498 while (i--) 00499 { 00500 out << s[i]; 00501 if (i && (i%block)==0) 00502 out << ','; 00503 } 00504 00505 return out << suffix; 00506 } 00507 00508 PolynomialMod2 PolynomialMod2::Gcd(const PolynomialMod2 &a, const PolynomialMod2 &b) 00509 { 00510 return EuclideanDomainOf<PolynomialMod2>().Gcd(a, b); 00511 } 00512 00513 PolynomialMod2 PolynomialMod2::InverseMod(const PolynomialMod2 &modulus) const 00514 { 00515 typedef EuclideanDomainOf<PolynomialMod2> Domain; 00516 return QuotientRing<Domain>(Domain(), modulus).MultiplicativeInverse(*this); 00517 } 00518 00519 bool PolynomialMod2::IsIrreducible() const 00520 { 00521 signed int d = Degree(); 00522 if (d <= 0) 00523 return false; 00524 00525 PolynomialMod2 t(2), u(t); 00526 for (int i=1; i<=d/2; i++) 00527 { 00528 u = u.Squared()%(*this); 00529 if (!Gcd(u+t, *this).IsUnit()) 00530 return false; 00531 } 00532 return true; 00533 } 00534 00535 // ******************************************************** 00536 00537 GF2NP::GF2NP(const PolynomialMod2 &modulus) 00538 : QuotientRing<EuclideanDomainOf<PolynomialMod2> >(EuclideanDomainOf<PolynomialMod2>(), modulus), m(modulus.Degree()) 00539 { 00540 } 00541 00542 GF2NP::Element GF2NP::SquareRoot(const Element &a) const 00543 { 00544 Element r = a; 00545 for (unsigned int i=1; i<m; i++) 00546 r = Square(r); 00547 return r; 00548 } 00549 00550 GF2NP::Element GF2NP::HalfTrace(const Element &a) const 00551 { 00552 assert(m%2 == 1); 00553 Element h = a; 00554 for (unsigned int i=1; i<=(m-1)/2; i++) 00555 h = Add(Square(Square(h)), a); 00556 return h; 00557 } 00558 00559 GF2NP::Element GF2NP::SolveQuadraticEquation(const Element &a) const 00560 { 00561 if (m%2 == 0) 00562 { 00563 Element z, w; 00564 RandomPool rng; 00565 do 00566 { 00567 Element p((RandomNumberGenerator &)rng, m); 00568 z = PolynomialMod2::Zero(); 00569 w = p; 00570 for (unsigned int i=1; i<=m-1; i++) 00571 { 00572 w = Square(w); 00573 z = Square(z); 00574 Accumulate(z, Multiply(w, a)); 00575 Accumulate(w, p); 00576 } 00577 } while (w.IsZero()); 00578 return z; 00579 } 00580 else 00581 return HalfTrace(a); 00582 } 00583 00584 // ******************************************************** 00585 00586 GF2NT::GF2NT(unsigned int t0, unsigned int t1, unsigned int t2) 00587 : GF2NP(PolynomialMod2::Trinomial(t0, t1, t2)) 00588 , t0(t0), t1(t1) 00589 , result((word)0, m) 00590 { 00591 assert(t0 > t1 && t1 > t2 && t2==0); 00592 } 00593 00594 const GF2NT::Element& GF2NT::MultiplicativeInverse(const Element &a) const 00595 { 00596 if (t0-t1 < WORD_BITS) 00597 return GF2NP::MultiplicativeInverse(a); 00598 00599 SecWordBlock T(m_modulus.reg.size() * 4); 00600 word *b = T; 00601 word *c = T+m_modulus.reg.size(); 00602 word *f = T+2*m_modulus.reg.size(); 00603 word *g = T+3*m_modulus.reg.size(); 00604 size_t bcLen=1, fgLen=m_modulus.reg.size(); 00605 unsigned int k=0; 00606 00607 SetWords(T, 0, 3*m_modulus.reg.size()); 00608 b[0]=1; 00609 assert(a.reg.size() <= m_modulus.reg.size()); 00610 CopyWords(f, a.reg, a.reg.size()); 00611 CopyWords(g, m_modulus.reg, m_modulus.reg.size()); 00612 00613 while (1) 00614 { 00615 word t=f[0]; 00616 while (!t) 00617 { 00618 ShiftWordsRightByWords(f, fgLen, 1); 00619 if (c[bcLen-1]) 00620 bcLen++; 00621 assert(bcLen <= m_modulus.reg.size()); 00622 ShiftWordsLeftByWords(c, bcLen, 1); 00623 k+=WORD_BITS; 00624 t=f[0]; 00625 } 00626 00627 unsigned int i=0; 00628 while (t%2 == 0) 00629 { 00630 t>>=1; 00631 i++; 00632 } 00633 k+=i; 00634 00635 if (t==1 && CountWords(f, fgLen)==1) 00636 break; 00637 00638 if (i==1) 00639 { 00640 ShiftWordsRightByBits(f, fgLen, 1); 00641 t=ShiftWordsLeftByBits(c, bcLen, 1); 00642 } 00643 else 00644 { 00645 ShiftWordsRightByBits(f, fgLen, i); 00646 t=ShiftWordsLeftByBits(c, bcLen, i); 00647 } 00648 if (t) 00649 { 00650 c[bcLen] = t; 00651 bcLen++; 00652 assert(bcLen <= m_modulus.reg.size()); 00653 } 00654 00655 if (f[fgLen-1]==0 && g[fgLen-1]==0) 00656 fgLen--; 00657 00658 if (f[fgLen-1] < g[fgLen-1]) 00659 { 00660 std::swap(f, g); 00661 std::swap(b, c); 00662 } 00663 00664 XorWords(f, g, fgLen); 00665 XorWords(b, c, bcLen); 00666 } 00667 00668 while (k >= WORD_BITS) 00669 { 00670 word temp = b[0]; 00671 // right shift b 00672 for (unsigned i=0; i+1<BitsToWords(m); i++) 00673 b[i] = b[i+1]; 00674 b[BitsToWords(m)-1] = 0; 00675 00676 if (t1 < WORD_BITS) 00677 for (unsigned int j=0; j<WORD_BITS-t1; j++) 00678 temp ^= ((temp >> j) & 1) << (t1 + j); 00679 else 00680 b[t1/WORD_BITS-1] ^= temp << t1%WORD_BITS; 00681 00682 if (t1 % WORD_BITS) 00683 b[t1/WORD_BITS] ^= temp >> (WORD_BITS - t1%WORD_BITS); 00684 00685 if (t0%WORD_BITS) 00686 { 00687 b[t0/WORD_BITS-1] ^= temp << t0%WORD_BITS; 00688 b[t0/WORD_BITS] ^= temp >> (WORD_BITS - t0%WORD_BITS); 00689 } 00690 else 00691 b[t0/WORD_BITS-1] ^= temp; 00692 00693 k -= WORD_BITS; 00694 } 00695 00696 if (k) 00697 { 00698 word temp = b[0] << (WORD_BITS - k); 00699 ShiftWordsRightByBits(b, BitsToWords(m), k); 00700 00701 if (t1 < WORD_BITS) 00702 for (unsigned int j=0; j<WORD_BITS-t1; j++) 00703 temp ^= ((temp >> j) & 1) << (t1 + j); 00704 else 00705 b[t1/WORD_BITS-1] ^= temp << t1%WORD_BITS; 00706 00707 if (t1 % WORD_BITS) 00708 b[t1/WORD_BITS] ^= temp >> (WORD_BITS - t1%WORD_BITS); 00709 00710 if (t0%WORD_BITS) 00711 { 00712 b[t0/WORD_BITS-1] ^= temp << t0%WORD_BITS; 00713 b[t0/WORD_BITS] ^= temp >> (WORD_BITS - t0%WORD_BITS); 00714 } 00715 else 00716 b[t0/WORD_BITS-1] ^= temp; 00717 } 00718 00719 CopyWords(result.reg.begin(), b, result.reg.size()); 00720 return result; 00721 } 00722 00723 const GF2NT::Element& GF2NT::Multiply(const Element &a, const Element &b) const 00724 { 00725 size_t aSize = STDMIN(a.reg.size(), result.reg.size()); 00726 Element r((word)0, m); 00727 00728 for (int i=m-1; i>=0; i--) 00729 { 00730 if (r[m-1]) 00731 { 00732 ShiftWordsLeftByBits(r.reg.begin(), r.reg.size(), 1); 00733 XorWords(r.reg.begin(), m_modulus.reg, r.reg.size()); 00734 } 00735 else 00736 ShiftWordsLeftByBits(r.reg.begin(), r.reg.size(), 1); 00737 00738 if (b[i]) 00739 XorWords(r.reg.begin(), a.reg, aSize); 00740 } 00741 00742 if (m%WORD_BITS) 00743 r.reg.begin()[r.reg.size()-1] = (word)Crop(r.reg[r.reg.size()-1], m%WORD_BITS); 00744 00745 CopyWords(result.reg.begin(), r.reg.begin(), result.reg.size()); 00746 return result; 00747 } 00748 00749 const GF2NT::Element& GF2NT::Reduced(const Element &a) const 00750 { 00751 if (t0-t1 < WORD_BITS) 00752 return m_domain.Mod(a, m_modulus); 00753 00754 SecWordBlock b(a.reg); 00755 00756 size_t i; 00757 for (i=b.size()-1; i>=BitsToWords(t0); i--) 00758 { 00759 word temp = b[i]; 00760 00761 if (t0%WORD_BITS) 00762 { 00763 b[i-t0/WORD_BITS] ^= temp >> t0%WORD_BITS; 00764 b[i-t0/WORD_BITS-1] ^= temp << (WORD_BITS - t0%WORD_BITS); 00765 } 00766 else 00767 b[i-t0/WORD_BITS] ^= temp; 00768 00769 if ((t0-t1)%WORD_BITS) 00770 { 00771 b[i-(t0-t1)/WORD_BITS] ^= temp >> (t0-t1)%WORD_BITS; 00772 b[i-(t0-t1)/WORD_BITS-1] ^= temp << (WORD_BITS - (t0-t1)%WORD_BITS); 00773 } 00774 else 00775 b[i-(t0-t1)/WORD_BITS] ^= temp; 00776 } 00777 00778 if (i==BitsToWords(t0)-1 && t0%WORD_BITS) 00779 { 00780 word mask = ((word)1<<(t0%WORD_BITS))-1; 00781 word temp = b[i] & ~mask; 00782 b[i] &= mask; 00783 00784 b[i-t0/WORD_BITS] ^= temp >> t0%WORD_BITS; 00785 00786 if ((t0-t1)%WORD_BITS) 00787 { 00788 b[i-(t0-t1)/WORD_BITS] ^= temp >> (t0-t1)%WORD_BITS; 00789 if ((t0-t1)%WORD_BITS > t0%WORD_BITS) 00790 b[i-(t0-t1)/WORD_BITS-1] ^= temp << (WORD_BITS - (t0-t1)%WORD_BITS); 00791 else 00792 assert(temp << (WORD_BITS - (t0-t1)%WORD_BITS) == 0); 00793 } 00794 else 00795 b[i-(t0-t1)/WORD_BITS] ^= temp; 00796 } 00797 00798 SetWords(result.reg.begin(), 0, result.reg.size()); 00799 CopyWords(result.reg.begin(), b, STDMIN(b.size(), result.reg.size())); 00800 return result; 00801 } 00802 00803 void GF2NP::DEREncodeElement(BufferedTransformation &out, const Element &a) const 00804 { 00805 a.DEREncodeAsOctetString(out, MaxElementByteLength()); 00806 } 00807 00808 void GF2NP::BERDecodeElement(BufferedTransformation &in, Element &a) const 00809 { 00810 a.BERDecodeAsOctetString(in, MaxElementByteLength()); 00811 } 00812 00813 void GF2NT::DEREncode(BufferedTransformation &bt) const 00814 { 00815 DERSequenceEncoder seq(bt); 00816 ASN1::characteristic_two_field().DEREncode(seq); 00817 DERSequenceEncoder parameters(seq); 00818 DEREncodeUnsigned(parameters, m); 00819 ASN1::tpBasis().DEREncode(parameters); 00820 DEREncodeUnsigned(parameters, t1); 00821 parameters.MessageEnd(); 00822 seq.MessageEnd(); 00823 } 00824 00825 void GF2NPP::DEREncode(BufferedTransformation &bt) const 00826 { 00827 DERSequenceEncoder seq(bt); 00828 ASN1::characteristic_two_field().DEREncode(seq); 00829 DERSequenceEncoder parameters(seq); 00830 DEREncodeUnsigned(parameters, m); 00831 ASN1::ppBasis().DEREncode(parameters); 00832 DERSequenceEncoder pentanomial(parameters); 00833 DEREncodeUnsigned(pentanomial, t3); 00834 DEREncodeUnsigned(pentanomial, t2); 00835 DEREncodeUnsigned(pentanomial, t1); 00836 pentanomial.MessageEnd(); 00837 parameters.MessageEnd(); 00838 seq.MessageEnd(); 00839 } 00840 00841 GF2NP * BERDecodeGF2NP(BufferedTransformation &bt) 00842 { 00843 // VC60 workaround: auto_ptr lacks reset() 00844 member_ptr<GF2NP> result; 00845 00846 BERSequenceDecoder seq(bt); 00847 if (OID(seq) != ASN1::characteristic_two_field()) 00848 BERDecodeError(); 00849 BERSequenceDecoder parameters(seq); 00850 unsigned int m; 00851 BERDecodeUnsigned(parameters, m); 00852 OID oid(parameters); 00853 if (oid == ASN1::tpBasis()) 00854 { 00855 unsigned int t1; 00856 BERDecodeUnsigned(parameters, t1); 00857 result.reset(new GF2NT(m, t1, 0)); 00858 } 00859 else if (oid == ASN1::ppBasis()) 00860 { 00861 unsigned int t1, t2, t3; 00862 BERSequenceDecoder pentanomial(parameters); 00863 BERDecodeUnsigned(pentanomial, t3); 00864 BERDecodeUnsigned(pentanomial, t2); 00865 BERDecodeUnsigned(pentanomial, t1); 00866 pentanomial.MessageEnd(); 00867 result.reset(new GF2NPP(m, t3, t2, t1, 0)); 00868 } 00869 else 00870 { 00871 BERDecodeError(); 00872 return NULL; 00873 } 00874 parameters.MessageEnd(); 00875 seq.MessageEnd(); 00876 00877 return result.release(); 00878 } 00879 00880 NAMESPACE_END 00881 00882 #endif