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