Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | File List | Namespace Members | Class Members | File Members

gf2n.cpp

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

Generated on Fri Aug 27 13:57:09 2004 for Crypto++ by doxygen 1.3.8