- Main Page
- Namespaces
- Classes
- Files

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