Crypto++

- Main Page
- Namespaces
- Classes
- Files

- File List
- 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, size_t bitLength=WORD_BITS);
    00045
    00046         //! convert from big-endian byte array
    00047         PolynomialMod2(const byte *encodedPoly, size_t byteCount)
    00048             {Decode(encodedPoly, byteCount);}
    00049
    00050         //! convert from big-endian form stored in a BufferedTransformation
    00051         PolynomialMod2(BufferedTransformation &encodedPoly, size_t 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, size_t bitcount)
    00056             {Randomize(rng, bitcount);}
    00057
    00058         //! return x^i
    00059         static PolynomialMod2 CRYPTOPP_API Monomial(size_t i);
    00060         //! return x^t0 + x^t1 + x^t2
    00061         static PolynomialMod2 CRYPTOPP_API Trinomial(size_t t0, size_t t1, size_t t2);
    00062         //! return x^t0 + x^t1 + x^t2 + x^t3 + x^t4
    00063         static PolynomialMod2 CRYPTOPP_API Pentanomial(size_t t0, size_t t1, size_t t2, size_t t3, size_t t4);
    00064         //! return x^(n-1) + ... + x + 1
    00065         static PolynomialMod2 CRYPTOPP_API AllOnes(size_t n);
    00066
    00067         //!
    00068         static const PolynomialMod2 & CRYPTOPP_API Zero();
    00069         //!
    00070         static const PolynomialMod2 & CRYPTOPP_API 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         void Encode(byte *output, size_t outputLen) const;
    00084         //!
    00085         void Encode(BufferedTransformation &bt, size_t outputLen) const;
    00086
    00087         //!
    00088         void Decode(const byte *input, size_t inputLen);
    00089         //!
    00090         //* Precondition: bt.MaxRetrievable() >= inputLen
    00091         void Decode(BufferedTransformation &bt, size_t inputLen);
    00092
    00093         //! encode value as big-endian octet string
    00094         void DEREncodeAsOctetString(BufferedTransformation &bt, size_t length) const;
    00095         //! decode value as big-endian octet string
    00096         void BERDecodeAsOctetString(BufferedTransformation &bt, size_t 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(size_t n) const {return GetCoefficient(n)!=0;}
    00110         //! return the n-th byte
    00111         byte GetByte(size_t 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(size_t 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, size_t bitcount);
    00154
    00155         //!
    00156         void SetBit(size_t i, int value = 1);
    00157         //! set the n-th byte to value
    00158         void SetByte(size_t n, byte value);
    00159
    00160         //!
    00161         void SetCoefficient(size_t 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 CRYPTOPP_API 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 CRYPTOPP_API 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 (unsigned int)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 #ifndef __BORLANDC__
    00361 NAMESPACE_BEGIN(std)
    00362 template<> inline void swap(CryptoPP::PolynomialMod2 &a, CryptoPP::PolynomialMod2 &b)
    00363 {
    00364     a.swap(b);
    00365 }
    00366 NAMESPACE_END
    00367 #endif
    00368
    00369 #endif