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 Tue Oct 26 18:51:38 2004 for Crypto++ by  doxygen 1.3.9.1