00001
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 "ient,
00276 const PolynomialMod2 ÷nd, 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)
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
00452 long f = out.flags() & std::ios::basefield;
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
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
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