Crypto++
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