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

Generated on Tue Jul 8 23:34:15 2003 for Crypto++ by doxygen 1.3.2