include/cryptopp/gf2n.h

0001 // gf2n.h - originally written and placed in the public domain by Wei Dai

0002
0003 /// \file gf2n.h

0004 /// \brief Classes and functions for schemes over GF(2^n)

0005
0006 #ifndef CRYPTOPP_GF2N_H
0007 #define CRYPTOPP_GF2N_H
0008
0009 #include "cryptlib.h"
0010 #include "secblock.h"
0011 #include "algebra.h"
0012 #include "misc.h"
0013 #include "asn.h"
0014
0015 #include <iosfwd>
0016
0017 #if CRYPTOPP_MSC_VERSION
0018 # pragma warning(push)
0019 # pragma warning(disable: 4231 4275)
0020 #endif
0021
0022 NAMESPACE_BEGIN(CryptoPP)
0023
0024 /// \brief Polynomial with Coefficients in GF(2)

0025 /*! \nosubgrouping */
0026 class CRYPTOPP_DLL PolynomialMod2
0027 {
0028 public:
0029     /// \name ENUMS, EXCEPTIONS, and TYPEDEFS

0030     //@{

0031         /// \brief Exception thrown when divide by zero is encountered

0032         class DivideByZero : public Exception
0033         {
0034         public:
0035             DivideByZero() : Exception(OTHER_ERROR, "PolynomialMod2: division by zero") {}
0036         };
0037
0038         typedef unsigned int RandomizationParameter;
0039     //@}

0040
0041     /// \name CREATORS

0042     //@{

0043         /// \brief Construct the zero polynomial

0044         PolynomialMod2();
0045         /// Copy construct a PolynomialMod2

0046         PolynomialMod2(const PolynomialMod2& t);
0047
0048         /// \brief Construct a PolynomialMod2 from a word

0049         /// \details value should be encoded with the least significant bit as coefficient to x^0

0050         ///   and most significant bit as coefficient to x^(WORD_BITS-1)

0051         ///   bitLength denotes how much memory to allocate initially

0052         PolynomialMod2(word value, size_t bitLength=WORD_BITS);
0053
0054         /// \brief Construct a PolynomialMod2 from big-endian byte array

0055         PolynomialMod2(const byte *encodedPoly, size_t byteCount)
0056             {Decode(encodedPoly, byteCount);}
0057
0058         /// \brief Construct a PolynomialMod2 from big-endian form stored in a BufferedTransformation

0059         PolynomialMod2(BufferedTransformation &encodedPoly, size_t byteCount)
0060             {Decode(encodedPoly, byteCount);}
0061
0062         /// \brief Create a uniformly distributed random polynomial

0063         /// \details Create a random polynomial uniformly distributed over all polynomials with degree less than bitcount

0064         PolynomialMod2(RandomNumberGenerator &rng, size_t bitcount)
0065             {Randomize(rng, bitcount);}
0066
0067         /// \brief Provides x^i

0068         /// \return x^i

0069         static PolynomialMod2 CRYPTOPP_API Monomial(size_t i);
0070         /// \brief Provides x^t0 + x^t1 + x^t2

0071         /// \return x^t0 + x^t1 + x^t2

0072         static PolynomialMod2 CRYPTOPP_API Trinomial(size_t t0, size_t t1, size_t t2);
0073         /// \brief Provides x^t0 + x^t1 + x^t2 + x^t3 + x^t4

0074         /// \return x^t0 + x^t1 + x^t2 + x^t3 + x^t4

0075         static PolynomialMod2 CRYPTOPP_API Pentanomial(size_t t0, size_t t1, size_t t2, size_t t3, size_t t4);
0076         /// \brief Provides x^(n-1) + ... + x + 1

0077         /// \return x^(n-1) + ... + x + 1

0078         static PolynomialMod2 CRYPTOPP_API AllOnes(size_t n);
0079
0080         /// \brief The Zero polinomial

0081         /// \return the zero polynomial

0082         static const PolynomialMod2 & CRYPTOPP_API Zero();
0083         /// \brief The One polinomial

0084         /// \return the one polynomial

0085         static const PolynomialMod2 & CRYPTOPP_API One();
0086     //@}

0087
0088     /// \name ENCODE/DECODE

0089     //@{

0090         /// minimum number of bytes to encode this polynomial

0091         /*! MinEncodedSize of 0 is 1 */
0092         unsigned int MinEncodedSize() const {return STDMAX(1U, ByteCount());}
0093
0094         /// encode in big-endian format

0095         /// \details if outputLen < MinEncodedSize, the most significant bytes will be dropped

0096         ///   if outputLen > MinEncodedSize, the most significant bytes will be padded

0097         void Encode(byte *output, size_t outputLen) const;
0098         ///

0099         void Encode(BufferedTransformation &bt, size_t outputLen) const;
0100
0101         ///

0102         void Decode(const byte *input, size_t inputLen);
0103         ///

0104         //* Precondition: bt.MaxRetrievable() >= inputLen

0105         void Decode(BufferedTransformation &bt, size_t inputLen);
0106
0107         /// encode value as big-endian octet string

0108         void DEREncodeAsOctetString(BufferedTransformation &bt, size_t length) const;
0109         /// decode value as big-endian octet string

0110         void BERDecodeAsOctetString(BufferedTransformation &bt, size_t length);
0111     //@}

0112
0113     /// \name ACCESSORS

0114     //@{

0115         /// number of significant bits = Degree() + 1

0116         unsigned int BitCount() const;
0117         /// number of significant bytes = ceiling(BitCount()/8)

0118         unsigned int ByteCount() const;
0119         /// number of significant words = ceiling(ByteCount()/sizeof(word))

0120         unsigned int WordCount() const;
0121
0122         /// return the n-th bit, n=0 being the least significant bit

0123         bool GetBit(size_t n) const {return GetCoefficient(n)!=0;}
0124         /// return the n-th byte

0125         byte GetByte(size_t n) const;
0126
0127         /// the zero polynomial will return a degree of -1

0128         signed int Degree() const {return (signed int)(BitCount()-1U);}
0129         /// degree + 1

0130         unsigned int CoefficientCount() const {return BitCount();}
0131         /// return coefficient for x^i

0132         int GetCoefficient(size_t i) const
0133             {return (i/WORD_BITS < reg.size()) ? int(reg[i/WORD_BITS] >> (i % WORD_BITS)) & 1 : 0;}
0134         /// return coefficient for x^i

0135         int operator[](unsigned int i) const {return GetCoefficient(i);}
0136
0137         ///

0138         bool IsZero() const {return !*this;}
0139         ///

0140         bool Equals(const PolynomialMod2 &rhs) const;
0141     //@}

0142
0143     /// \name MANIPULATORS

0144     //@{

0145         ///

0146         PolynomialMod2&  operator=(const PolynomialMod2& t);
0147         ///

0148         PolynomialMod2&  operator&=(const PolynomialMod2& t);
0149         ///

0150         PolynomialMod2&  operator^=(const PolynomialMod2& t);
0151         ///

0152         PolynomialMod2&  operator+=(const PolynomialMod2& t) {return *this ^= t;}
0153         ///

0154         PolynomialMod2&  operator-=(const PolynomialMod2& t) {return *this ^= t;}
0155         ///

0156         PolynomialMod2&  operator*=(const PolynomialMod2& t);
0157         ///

0158         PolynomialMod2&  operator/=(const PolynomialMod2& t);
0159         ///

0160         PolynomialMod2&  operator%=(const PolynomialMod2& t);
0161         ///

0162         PolynomialMod2&  operator<<=(unsigned int);
0163         ///

0164         PolynomialMod2&  operator>>=(unsigned int);
0165
0166         ///

0167         void Randomize(RandomNumberGenerator &rng, size_t bitcount);
0168
0169         ///

0170         void SetBit(size_t i, int value = 1);
0171         /// set the n-th byte to value

0172         void SetByte(size_t n, byte value);
0173
0174         ///

0175         void SetCoefficient(size_t i, int value) {SetBit(i, value);}
0176
0177         ///

0178         void swap(PolynomialMod2 &a) {reg.swap(a.reg);}
0179     //@}

0180
0181     /// \name UNARY OPERATORS

0182     //@{

0183         ///

0184         bool            operator!() const;
0185         ///

0186         PolynomialMod2  operator+() const {return *this;}
0187         ///

0188         PolynomialMod2  operator-() const {return *this;}
0189     //@}

0190
0191     /// \name BINARY OPERATORS

0192     //@{

0193         ///

0194         PolynomialMod2 And(const PolynomialMod2 &b) const;
0195         ///

0196         PolynomialMod2 Xor(const PolynomialMod2 &b) const;
0197         ///

0198         PolynomialMod2 Plus(const PolynomialMod2 &b) const {return Xor(b);}
0199         ///

0200         PolynomialMod2 Minus(const PolynomialMod2 &b) const {return Xor(b);}
0201         ///

0202         PolynomialMod2 Times(const PolynomialMod2 &b) const;
0203         ///

0204         PolynomialMod2 DividedBy(const PolynomialMod2 &b) const;
0205         ///

0206         PolynomialMod2 Modulo(const PolynomialMod2 &b) const;
0207
0208         ///

0209         PolynomialMod2 operator>>(unsigned int n) const;
0210         ///

0211         PolynomialMod2 operator<<(unsigned int n) const;
0212     //@}

0213
0214     /// \name OTHER ARITHMETIC FUNCTIONS

0215     //@{

0216         /// sum modulo 2 of all coefficients

0217         unsigned int Parity() const;
0218
0219         /// check for irreducibility

0220         bool IsIrreducible() const;
0221
0222         /// is always zero since we're working modulo 2

0223         PolynomialMod2 Doubled() const {return Zero();}
0224         ///

0225         PolynomialMod2 Squared() const;
0226
0227         /// only 1 is a unit

0228         bool IsUnit() const {return Equals(One());}
0229         /// return inverse if *this is a unit, otherwise return 0

0230         PolynomialMod2 MultiplicativeInverse() const {return IsUnit() ? One() : Zero();}
0231
0232         /// greatest common divisor

0233         static PolynomialMod2 CRYPTOPP_API Gcd(const PolynomialMod2 &a, const PolynomialMod2 &n);
0234         /// calculate multiplicative inverse of *this mod n

0235         PolynomialMod2 InverseMod(const PolynomialMod2 &) const;
0236
0237         /// calculate r and q such that (a == d*q + r) && (deg(r) < deg(d))

0238         static void CRYPTOPP_API Divide(PolynomialMod2 &r, PolynomialMod2 &q, const PolynomialMod2 &a, const PolynomialMod2 &d);
0239     //@}

0240
0241     /// \name INPUT/OUTPUT

0242     //@{

0243         ///

0244         friend std::ostream& operator<<(std::ostream& out, const PolynomialMod2 &a);
0245     //@}

0246
0247 private:
0248     friend class GF2NT;
0249     friend class GF2NT233;
0250
0251     SecWordBlock reg;
0252 };
0253
0254 ///

0255 inline bool operator==(const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b)
0256 {return a.Equals(b);}
0257 ///

0258 inline bool operator!=(const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b)
0259 {return !(a==b);}
0260 /// compares degree

0261 inline bool operator> (const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b)
0262 {return a.Degree() > b.Degree();}
0263 /// compares degree

0264 inline bool operator>=(const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b)
0265 {return a.Degree() >= b.Degree();}
0266 /// compares degree

0267 inline bool operator< (const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b)
0268 {return a.Degree() < b.Degree();}
0269 /// compares degree

0270 inline bool operator<=(const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b)
0271 {return a.Degree() <= b.Degree();}
0272 ///

0273 inline CryptoPP::PolynomialMod2 operator&(const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b) {return a.And(b);}
0274 ///

0275 inline CryptoPP::PolynomialMod2 operator^(const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b) {return a.Xor(b);}
0276 ///

0277 inline CryptoPP::PolynomialMod2 operator+(const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b) {return a.Plus(b);}
0278 ///

0279 inline CryptoPP::PolynomialMod2 operator-(const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b) {return a.Minus(b);}
0280 ///

0281 inline CryptoPP::PolynomialMod2 operator*(const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b) {return a.Times(b);}
0282 ///

0283 inline CryptoPP::PolynomialMod2 operator/(const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b) {return a.DividedBy(b);}
0284 ///

0285 inline CryptoPP::PolynomialMod2 operator%(const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b) {return a.Modulo(b);}
0286
0287 // CodeWarrior 8 workaround: put these template instantiations after overloaded operator declarations,

0288 // but before the use of QuotientRing<EuclideanDomainOf<PolynomialMod2> > for VC .NET 2003

0289 CRYPTOPP_DLL_TEMPLATE_CLASS AbstractGroup<PolynomialMod2>;
0290 CRYPTOPP_DLL_TEMPLATE_CLASS AbstractRing<PolynomialMod2>;
0291 CRYPTOPP_DLL_TEMPLATE_CLASS AbstractEuclideanDomain<PolynomialMod2>;
0292 CRYPTOPP_DLL_TEMPLATE_CLASS EuclideanDomainOf<PolynomialMod2>;
0293 CRYPTOPP_DLL_TEMPLATE_CLASS QuotientRing<EuclideanDomainOf<PolynomialMod2> >;
0294
0295 /// \brief GF(2^n) with Polynomial Basis

0296 class CRYPTOPP_DLL GF2NP : public QuotientRing<EuclideanDomainOf<PolynomialMod2> >
0297 {
0298 public:
0299     GF2NP(const PolynomialMod2 &modulus);
0300
0301     virtual GF2NP * Clone() const {return new GF2NP(*this);}
0302     virtual void DEREncode(BufferedTransformation &bt) const
0303         {CRYPTOPP_UNUSED(bt); CRYPTOPP_ASSERT(false);}  // no ASN.1 syntax yet for general polynomial basis

0304
0305     void DEREncodeElement(BufferedTransformation &out, const Element &a) const;
0306     void BERDecodeElement(BufferedTransformation &in, Element &a) const;
0307
0308     bool Equal(const Element &a, const Element &b) const
0309         {CRYPTOPP_ASSERT(a.Degree() < m_modulus.Degree() && b.Degree() < m_modulus.Degree()); return a.Equals(b);}
0310
0311     bool IsUnit(const Element &a) const
0312         {CRYPTOPP_ASSERT(a.Degree() < m_modulus.Degree()); return !!a;}
0313
0314     unsigned int MaxElementBitLength() const
0315         {return m;}
0316
0317     unsigned int MaxElementByteLength() const
0318         {return (unsigned int)BitsToBytes(MaxElementBitLength());}
0319
0320     Element SquareRoot(const Element &a) const;
0321
0322     Element HalfTrace(const Element &a) const;
0323
0324     // returns z such that z^2 + z == a

0325     Element SolveQuadraticEquation(const Element &a) const;
0326
0327 protected:
0328     unsigned int m;
0329 };
0330
0331 /// \brief GF(2^n) with Trinomial Basis

0332 class CRYPTOPP_DLL GF2NT : public GF2NP
0333 {
0334 public:
0335     // polynomial modulus = x^t0 + x^t1 + x^t2, t0 > t1 > t2

0336     GF2NT(unsigned int t0, unsigned int t1, unsigned int t2);
0337
0338     GF2NP * Clone() const {return new GF2NT(*this);}
0339     void DEREncode(BufferedTransformation &bt) const;
0340
0341     const Element& Multiply(const Element &a, const Element &b) const;
0342
0343     const Element& Square(const Element &a) const
0344         {return Reduced(a.Squared());}
0345
0346     const Element& MultiplicativeInverse(const Element &a) const;
0347
0348 protected:
0349     const Element& Reduced(const Element &a) const;
0350
0351     unsigned int t0, t1;
0352     mutable PolynomialMod2 result;
0353 };
0354
0355 /// \brief GF(2^n) for b233 and k233

0356 /// \details GF2NT233 is a specialization of GF2NT that provides Multiply()

0357 ///   and Square() operations when carryless multiplies is available.

0358 class CRYPTOPP_DLL GF2NT233 : public GF2NT
0359 {
0360 public:
0361     // polynomial modulus = x^t0 + x^t1 + x^t2, t0 > t1 > t2

0362     GF2NT233(unsigned int t0, unsigned int t1, unsigned int t2);
0363
0364     GF2NP * Clone() const {return new GF2NT233(*this);}
0365
0366     const Element& Multiply(const Element &a, const Element &b) const;
0367
0368     const Element& Square(const Element &a) const;
0369 };
0370
0371 /// \brief GF(2^n) with Pentanomial Basis

0372 class CRYPTOPP_DLL GF2NPP : public GF2NP
0373 {
0374 public:
0375     // polynomial modulus = x^t0 + x^t1 + x^t2 + x^t3 + x^t4, t0 > t1 > t2 > t3 > t4

0376     GF2NPP(unsigned int t0, unsigned int t1, unsigned int t2, unsigned int t3, unsigned int t4)
0377         : GF2NP(PolynomialMod2::Pentanomial(t0, t1, t2, t3, t4)), t1(t1), t2(t2), t3(t3) {}
0378
0379     GF2NP * Clone() const {return new GF2NPP(*this);}
0380     void DEREncode(BufferedTransformation &bt) const;
0381
0382 private:
0383     unsigned int t1, t2, t3;
0384 };
0385
0386 // construct new GF2NP from the ASN.1 sequence Characteristic-two

0387 CRYPTOPP_DLL GF2NP * CRYPTOPP_API BERDecodeGF2NP(BufferedTransformation &bt);
0388
0389 NAMESPACE_END
0390
0391 #ifndef __BORLANDC__
0392 NAMESPACE_BEGIN(std)
0393 template<> inline void swap(CryptoPP::PolynomialMod2 &a, CryptoPP::PolynomialMod2 &b)
0394 {
0395     a.swap(b);
0396 }
0397 NAMESPACE_END
0398 #endif
0399
0400 #if CRYPTOPP_MSC_VERSION
0401 # pragma warning(pop)
0402 #endif
0403
0404 #endif