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

# gf2n.h

Go to the documentation of this file.

    00001 #ifndef CRYPTOPP_GF2N_H
    00002 #define CRYPTOPP_GF2N_H
    00003
    00004 /*! \file */
    00005
    00006 #include "cryptlib.h"
    00007 #include "secblock.h"
    00008 #include "misc.h"
    00009 #include "algebra.h"
    00010
    00011 #include <iosfwd>
    00012
    00013 NAMESPACE_BEGIN(CryptoPP)
    00014
    00015 //! Polynomial with Coefficients in GF(2)
    00016 /*!     \nosubgrouping */
    00017 class CRYPTOPP_DLL PolynomialMod2
    00018 {
    00019 public:
    00020         //! \name ENUMS, EXCEPTIONS, and TYPEDEFS
    00021         //@{
    00022                 //! divide by zero exception
    00023                 class DivideByZero : public Exception
    00024                 {
    00025                 public:
    00026                         DivideByZero() : Exception(OTHER_ERROR, "PolynomialMod2: division by zero") {}
    00027                 };
    00028
    00029                 typedef unsigned int RandomizationParameter;
    00030         //@}
    00031
    00032         //! \name CREATORS
    00033         //@{
    00034                 //! creates the zero polynomial
    00035                 PolynomialMod2();
    00036                 //! copy constructor
    00037                 PolynomialMod2(const PolynomialMod2& t);
    00038
    00039                 //! convert from word
    00040                 /*! value should be encoded with the least significant bit as coefficient to x^0
    00041                         and most significant bit as coefficient to x^(WORD_BITS-1)
    00042                         bitLength denotes how much memory to allocate initially
    00043                 */
    00044                 PolynomialMod2(word value, unsigned int bitLength=WORD_BITS);
    00045
    00046                 //! convert from big-endian byte array
    00047                 PolynomialMod2(const byte *encodedPoly, unsigned int byteCount)
    00048                         {Decode(encodedPoly, byteCount);}
    00049
    00050                 //! convert from big-endian form stored in a BufferedTransformation
    00051                 PolynomialMod2(BufferedTransformation &encodedPoly, unsigned int byteCount)
    00052                         {Decode(encodedPoly, byteCount);}
    00053
    00054                 //! create a random polynomial uniformly distributed over all polynomials with degree less than bitcount
    00055                 PolynomialMod2(RandomNumberGenerator &rng, unsigned int bitcount)
    00056                         {Randomize(rng, bitcount);}
    00057
    00058                 //! return x^i
    00059                 static PolynomialMod2 Monomial(unsigned i);
    00060                 //! return x^t0 + x^t1 + x^t2
    00061                 static PolynomialMod2 Trinomial(unsigned t0, unsigned t1, unsigned t2);
    00062                 //! return x^t0 + x^t1 + x^t2 + x^t3 + x^t4
    00063                 static PolynomialMod2 Pentanomial(unsigned t0, unsigned t1, unsigned t2, unsigned int t3, unsigned int t4);
    00064                 //! return x^(n-1) + ... + x + 1
    00065                 static PolynomialMod2 AllOnes(unsigned n);
    00066
    00067                 //!
    00068                 static const PolynomialMod2 &Zero();
    00069                 //!
    00070                 static const PolynomialMod2 &One();
    00071         //@}
    00072
    00073         //! \name ENCODE/DECODE
    00074         //@{
    00075                 //! minimum number of bytes to encode this polynomial
    00076                 /*! MinEncodedSize of 0 is 1 */
    00077                 unsigned int MinEncodedSize() const {return STDMAX(1U, ByteCount());}
    00078
    00079                 //! encode in big-endian format
    00080                 /*! if outputLen < MinEncodedSize, the most significant bytes will be dropped
    00081                         if outputLen > MinEncodedSize, the most significant bytes will be padded
    00082                 */
    00083                 unsigned int Encode(byte *output, unsigned int outputLen) const;
    00084                 //!
    00085                 unsigned int Encode(BufferedTransformation &bt, unsigned int outputLen) const;
    00086
    00087                 //!
    00088                 void Decode(const byte *input, unsigned int inputLen);
    00089                 //!
    00090                 //* Precondition: bt.MaxRetrievable() >= inputLen
    00091                 void Decode(BufferedTransformation &bt, unsigned int inputLen);
    00092
    00093                 //! encode value as big-endian octet string
    00094                 void DEREncodeAsOctetString(BufferedTransformation &bt, unsigned int length) const;
    00095                 //! decode value as big-endian octet string
    00096                 void BERDecodeAsOctetString(BufferedTransformation &bt, unsigned int length);
    00097         //@}
    00098
    00099         //! \name ACCESSORS
    00100         //@{
    00101                 //! number of significant bits = Degree() + 1
    00102                 unsigned int BitCount() const;
    00103                 //! number of significant bytes = ceiling(BitCount()/8)
    00104                 unsigned int ByteCount() const;
    00105                 //! number of significant words = ceiling(ByteCount()/sizeof(word))
    00106                 unsigned int WordCount() const;
    00107
    00108                 //! return the n-th bit, n=0 being the least significant bit
    00109                 bool GetBit(unsigned int n) const {return GetCoefficient(n)!=0;}
    00110                 //! return the n-th byte
    00111                 byte GetByte(unsigned int n) const;
    00112
    00113                 //! the zero polynomial will return a degree of -1
    00114                 signed int Degree() const {return BitCount()-1;}
    00115                 //! degree + 1
    00116                 unsigned int CoefficientCount() const {return BitCount();}
    00117                 //! return coefficient for x^i
    00118                 int GetCoefficient(unsigned int i) const
    00119                         {return (i/WORD_BITS < reg.size()) ? int(reg[i/WORD_BITS] >> (i % WORD_BITS)) & 1 : 0;}
    00120                 //! return coefficient for x^i
    00121                 int operator[](unsigned int i) const {return GetCoefficient(i);}
    00122
    00123                 //!
    00124                 bool IsZero() const {return !*this;}
    00125                 //!
    00126                 bool Equals(const PolynomialMod2 &rhs) const;
    00127         //@}
    00128
    00129         //! \name MANIPULATORS
    00130         //@{
    00131                 //!
    00132                 PolynomialMod2&  operator=(const PolynomialMod2& t);
    00133                 //!
    00134                 PolynomialMod2&  operator&=(const PolynomialMod2& t);
    00135                 //!
    00136                 PolynomialMod2&  operator^=(const PolynomialMod2& t);
    00137                 //!
    00138                 PolynomialMod2&  operator+=(const PolynomialMod2& t) {return *this ^= t;}
    00139                 //!
    00140                 PolynomialMod2&  operator-=(const PolynomialMod2& t) {return *this ^= t;}
    00141                 //!
    00142                 PolynomialMod2&  operator*=(const PolynomialMod2& t);
    00143                 //!
    00144                 PolynomialMod2&  operator/=(const PolynomialMod2& t);
    00145                 //!
    00146                 PolynomialMod2&  operator%=(const PolynomialMod2& t);
    00147                 //!
    00148                 PolynomialMod2&  operator<<=(unsigned int);
    00149                 //!
    00150                 PolynomialMod2&  operator>>=(unsigned int);
    00151
    00152                 //!
    00153                 void Randomize(RandomNumberGenerator &rng, unsigned int bitcount);
    00154
    00155                 //!
    00156                 void SetBit(unsigned int i, int value = 1);
    00157                 //! set the n-th byte to value
    00158                 void SetByte(unsigned int n, byte value);
    00159
    00160                 //!
    00161                 void SetCoefficient(unsigned int i, int value) {SetBit(i, value);}
    00162
    00163                 //!
    00164                 void swap(PolynomialMod2 &a) {reg.swap(a.reg);}
    00165         //@}
    00166
    00167         //! \name UNARY OPERATORS
    00168         //@{
    00169                 //!
    00170                 bool                    operator!() const;
    00171                 //!
    00172                 PolynomialMod2  operator+() const {return *this;}
    00173                 //!
    00174                 PolynomialMod2  operator-() const {return *this;}
    00175         //@}
    00176
    00177         //! \name BINARY OPERATORS
    00178         //@{
    00179                 //!
    00180                 PolynomialMod2 And(const PolynomialMod2 &b) const;
    00181                 //!
    00182                 PolynomialMod2 Xor(const PolynomialMod2 &b) const;
    00183                 //!
    00184                 PolynomialMod2 Plus(const PolynomialMod2 &b) const {return Xor(b);}
    00185                 //!
    00186                 PolynomialMod2 Minus(const PolynomialMod2 &b) const {return Xor(b);}
    00187                 //!
    00188                 PolynomialMod2 Times(const PolynomialMod2 &b) const;
    00189                 //!
    00190                 PolynomialMod2 DividedBy(const PolynomialMod2 &b) const;
    00191                 //!
    00192                 PolynomialMod2 Modulo(const PolynomialMod2 &b) const;
    00193
    00194                 //!
    00195                 PolynomialMod2 operator>>(unsigned int n) const;
    00196                 //!
    00197                 PolynomialMod2 operator<<(unsigned int n) const;
    00198         //@}
    00199
    00200         //! \name OTHER ARITHMETIC FUNCTIONS
    00201         //@{
    00202                 //! sum modulo 2 of all coefficients
    00203                 unsigned int Parity() const;
    00204
    00205                 //! check for irreducibility
    00206                 bool IsIrreducible() const;
    00207
    00208                 //! is always zero since we're working modulo 2
    00209                 PolynomialMod2 Doubled() const {return Zero();}
    00210                 //!
    00211                 PolynomialMod2 Squared() const;
    00212
    00213                 //! only 1 is a unit
    00214                 bool IsUnit() const {return Equals(One());}
    00215                 //! return inverse if *this is a unit, otherwise return 0
    00216                 PolynomialMod2 MultiplicativeInverse() const {return IsUnit() ? One() : Zero();}
    00217
    00218                 //! greatest common divisor
    00219                 static PolynomialMod2 Gcd(const PolynomialMod2 &a, const PolynomialMod2 &n);
    00220                 //! calculate multiplicative inverse of *this mod n
    00221                 PolynomialMod2 InverseMod(const PolynomialMod2 &) const;
    00222
    00223                 //! calculate r and q such that (a == d*q + r) && (deg(r) < deg(d))
    00224                 static void Divide(PolynomialMod2 &r, PolynomialMod2 &q, const PolynomialMod2 &a, const PolynomialMod2 &d);
    00225         //@}
    00226
    00227         //! \name INPUT/OUTPUT
    00228         //@{
    00229                 //!
    00230                 friend std::ostream& operator<<(std::ostream& out, const PolynomialMod2 &a);
    00231         //@}
    00232
    00233 private:
    00234         friend class GF2NT;
    00235
    00236         SecWordBlock reg;
    00237 };
    00238
    00239 //!
    00240 inline bool operator==(const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b)
    00241 {return a.Equals(b);}
    00242 //!
    00243 inline bool operator!=(const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b)
    00244 {return !(a==b);}
    00245 //! compares degree
    00246 inline bool operator> (const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b)
    00247 {return a.Degree() > b.Degree();}
    00248 //! compares degree
    00249 inline bool operator>=(const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b)
    00250 {return a.Degree() >= b.Degree();}
    00251 //! compares degree
    00252 inline bool operator< (const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b)
    00253 {return a.Degree() < b.Degree();}
    00254 //! compares degree
    00255 inline bool operator<=(const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b)
    00256 {return a.Degree() <= b.Degree();}
    00257 //!
    00258 inline CryptoPP::PolynomialMod2 operator&(const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b) {return a.And(b);}
    00259 //!
    00260 inline CryptoPP::PolynomialMod2 operator^(const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b) {return a.Xor(b);}
    00261 //!
    00262 inline CryptoPP::PolynomialMod2 operator+(const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b) {return a.Plus(b);}
    00263 //!
    00264 inline CryptoPP::PolynomialMod2 operator-(const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b) {return a.Minus(b);}
    00265 //!
    00266 inline CryptoPP::PolynomialMod2 operator*(const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b) {return a.Times(b);}
    00267 //!
    00268 inline CryptoPP::PolynomialMod2 operator/(const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b) {return a.DividedBy(b);}
    00269 //!
    00270 inline CryptoPP::PolynomialMod2 operator%(const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b) {return a.Modulo(b);}
    00271
    00272 // CodeWarrior 8 workaround: put these template instantiations after overloaded operator declarations,
    00273 // but before the use of QuotientRing<EuclideanDomainOf<PolynomialMod2> > for VC .NET 2003
    00274 CRYPTOPP_DLL_TEMPLATE_CLASS AbstractGroup<PolynomialMod2>;
    00275 CRYPTOPP_DLL_TEMPLATE_CLASS AbstractRing<PolynomialMod2>;
    00276 CRYPTOPP_DLL_TEMPLATE_CLASS AbstractEuclideanDomain<PolynomialMod2>;
    00277 CRYPTOPP_DLL_TEMPLATE_CLASS EuclideanDomainOf<PolynomialMod2>;
    00278 CRYPTOPP_DLL_TEMPLATE_CLASS QuotientRing<EuclideanDomainOf<PolynomialMod2> >;
    00279
    00280 //! GF(2^n) with Polynomial Basis
    00281 class CRYPTOPP_DLL GF2NP : public QuotientRing<EuclideanDomainOf<PolynomialMod2> >
    00282 {
    00283 public:
    00284         GF2NP(const PolynomialMod2 &modulus);
    00285
    00286         virtual GF2NP * Clone() const {return new GF2NP(*this);}
    00287         virtual void DEREncode(BufferedTransformation &bt) const
    00288                 {assert(false);}        // no ASN.1 syntax yet for general polynomial basis
    00289
    00290         void DEREncodeElement(BufferedTransformation &out, const Element &a) const;
    00291         void BERDecodeElement(BufferedTransformation &in, Element &a) const;
    00292
    00293         bool Equal(const Element &a, const Element &b) const
    00294                 {assert(a.Degree() < m_modulus.Degree() && b.Degree() < m_modulus.Degree()); return a.Equals(b);}
    00295
    00296         bool IsUnit(const Element &a) const
    00297                 {assert(a.Degree() < m_modulus.Degree()); return !!a;}
    00298
    00299         unsigned int MaxElementBitLength() const
    00300                 {return m;}
    00301
    00302         unsigned int MaxElementByteLength() const
    00303                 {return BitsToBytes(MaxElementBitLength());}
    00304
    00305         Element SquareRoot(const Element &a) const;
    00306
    00307         Element HalfTrace(const Element &a) const;
    00308
    00309         // returns z such that z^2 + z == a
    00310         Element SolveQuadraticEquation(const Element &a) const;
    00311
    00312 protected:
    00313         unsigned int m;
    00314 };
    00315
    00316 //! GF(2^n) with Trinomial Basis
    00317 class CRYPTOPP_DLL GF2NT : public GF2NP
    00318 {
    00319 public:
    00320         // polynomial modulus = x^t0 + x^t1 + x^t2, t0 > t1 > t2
    00321         GF2NT(unsigned int t0, unsigned int t1, unsigned int t2);
    00322
    00323         GF2NP * Clone() const {return new GF2NT(*this);}
    00324         void DEREncode(BufferedTransformation &bt) const;
    00325
    00326         const Element& Multiply(const Element &a, const Element &b) const;
    00327
    00328         const Element& Square(const Element &a) const
    00329                 {return Reduced(a.Squared());}
    00330
    00331         const Element& MultiplicativeInverse(const Element &a) const;
    00332
    00333 private:
    00334         const Element& Reduced(const Element &a) const;
    00335
    00336         unsigned int t0, t1;
    00337         mutable PolynomialMod2 result;
    00338 };
    00339
    00340 //! GF(2^n) with Pentanomial Basis
    00341 class CRYPTOPP_DLL GF2NPP : public GF2NP
    00342 {
    00343 public:
    00344         // polynomial modulus = x^t0 + x^t1 + x^t2 + x^t3 + x^t4, t0 > t1 > t2 > t3 > t4
    00345         GF2NPP(unsigned int t0, unsigned int t1, unsigned int t2, unsigned int t3, unsigned int t4)
    00346                 : GF2NP(PolynomialMod2::Pentanomial(t0, t1, t2, t3, t4)), t0(t0), t1(t1), t2(t2), t3(t3) {}
    00347
    00348         GF2NP * Clone() const {return new GF2NPP(*this);}
    00349         void DEREncode(BufferedTransformation &bt) const;
    00350
    00351 private:
    00352         unsigned int t0, t1, t2, t3;
    00353 };
    00354
    00355 // construct new GF2NP from the ASN.1 sequence Characteristic-two
    00356 CRYPTOPP_DLL GF2NP * CRYPTOPP_API BERDecodeGF2NP(BufferedTransformation &bt);
    00357
    00358 NAMESPACE_END
    00359
    00360 NAMESPACE_BEGIN(std)
    00361 template<> inline void swap(CryptoPP::PolynomialMod2 &a, CryptoPP::PolynomialMod2 &b)
    00362 {
    00363         a.swap(b);
    00364 }
    00365 NAMESPACE_END
    00366
    00367 #endif