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

Generated on Fri Aug 13 09:56:53 2004 for Crypto++ by doxygen 1.3.7