Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | File List | 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