Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | File List | Namespace Members | Class Members | File Members

gf2n.cpp

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

Generated on Mon Apr 19 18:12:30 2004 for Crypto++ by doxygen 1.3.6-20040222