gf2n.h Source File

00001 #ifndef CRYPTOPP_GF2N_H
00002 #define CRYPTOPP_GF2N_H
00003 
00006 #include "cryptlib.h"
00007 #include "misc.h"
00008 #include "algebra.h"
00009 
00010 #include <iosfwd>
00011 
00012 NAMESPACE_BEGIN(CryptoPP)
00013 
00015 
00016 class PolynomialMod2
00017 {
00018 public:
00020 
00021 
00022                 class DivideByZero : public Exception
00023                 {
00024                 public:
00025                         DivideByZero() : Exception("PolynomialMod2: division by zero") {}
00026                 };
00027 
00028                 typedef unsigned int RandomizationParameter;
00030 
00032 
00033 
00034                 PolynomialMod2();
00036                 PolynomialMod2(const PolynomialMod2& t);
00037 
00039 
00043                 PolynomialMod2(word value, unsigned int bitLength=WORD_BITS);
00044 
00046                 PolynomialMod2(const byte *encodedPoly, unsigned int byteCount)
00047                         {Decode(encodedPoly, byteCount);}
00048 
00050                 PolynomialMod2(BufferedTransformation &encodedPoly, unsigned int byteCount)
00051                         {Decode(encodedPoly, byteCount);}
00052 
00054                 PolynomialMod2(RandomNumberGenerator &rng, unsigned int bitcount)
00055                         {Randomize(rng, bitcount);}
00056 
00058                 static PolynomialMod2 Monomial(unsigned i);
00060                 static PolynomialMod2 Trinomial(unsigned t0, unsigned t1, unsigned t2);
00062                 static PolynomialMod2 Pentanomial(unsigned t0, unsigned t1, unsigned t2, unsigned int t3, unsigned int t4);
00064                 static PolynomialMod2 AllOnes(unsigned n);
00065 
00067                 static const PolynomialMod2 &Zero();
00069                 static const PolynomialMod2 &One();
00071 
00073 
00074 
00075 
00076                 unsigned int MinEncodedSize() const {return STDMAX(1U, ByteCount());}
00077 
00079 
00082                 unsigned int Encode(byte *output, unsigned int outputLen) const;
00084                 unsigned int Encode(BufferedTransformation &bt, unsigned int outputLen) const;
00085 
00087                 void Decode(const byte *input, unsigned int inputLen);
00089                 //* Precondition: bt.MaxRetrievable() >= inputLen
00090                 void Decode(BufferedTransformation &bt, unsigned int inputLen);
00091 
00093                 void DEREncodeAsOctetString(BufferedTransformation &bt, unsigned int length) const;
00095                 void BERDecodeAsOctetString(BufferedTransformation &bt, unsigned int length);
00097 
00099 
00100 
00101                 unsigned int BitCount() const;
00103                 unsigned int ByteCount() const;
00105                 unsigned int WordCount() const;
00106 
00108                 bool GetBit(unsigned int n) const {return GetCoefficient(n)!=0;}
00110                 byte GetByte(unsigned int n) const;
00111 
00113                 signed int Degree() const {return BitCount()-1;}
00115                 unsigned int CoefficientCount() const {return BitCount();}
00117                 int GetCoefficient(unsigned int i) const
00118                         {return (i/WORD_BITS < reg.size) ? int(reg[i/WORD_BITS] >> (i % WORD_BITS)) & 1 : 0;}
00120                 int operator[](unsigned int i) const {return GetCoefficient(i);}
00121 
00123                 bool IsZero() const {return !*this;}
00125                 bool Equals(const PolynomialMod2 &rhs) const;
00127 
00129 
00130 
00131                 PolynomialMod2&  operator=(const PolynomialMod2& t);
00133                 PolynomialMod2&  operator&=(const PolynomialMod2& t);
00135                 PolynomialMod2&  operator^=(const PolynomialMod2& t);
00137                 PolynomialMod2&  operator+=(const PolynomialMod2& t) {return *this ^= t;}
00139                 PolynomialMod2&  operator-=(const PolynomialMod2& t) {return *this ^= t;}
00141                 PolynomialMod2&  operator*=(const PolynomialMod2& t);
00143                 PolynomialMod2&  operator/=(const PolynomialMod2& t);
00145                 PolynomialMod2&  operator%=(const PolynomialMod2& t);
00147                 PolynomialMod2&  operator<<=(unsigned int);
00149                 PolynomialMod2&  operator>>=(unsigned int);
00150 
00152                 void Randomize(RandomNumberGenerator &rng, unsigned int bitcount);
00153 
00155                 void SetBit(unsigned int i, int value = 1);
00157                 void SetByte(unsigned int n, byte value);
00158 
00160                 void SetCoefficient(unsigned int i, int value) {SetBit(i, value);}
00161 
00163                 void swap(PolynomialMod2 &a) {reg.swap(a.reg);}
00165 
00167 
00168 
00169                 bool                    operator!() const;
00171                 PolynomialMod2  operator+() const {return *this;}
00173                 PolynomialMod2  operator-() const {return *this;}
00175 
00177 
00178 
00179                 PolynomialMod2 And(const PolynomialMod2 &b) const;
00181                 PolynomialMod2 Xor(const PolynomialMod2 &b) const;
00183                 PolynomialMod2 Plus(const PolynomialMod2 &b) const {return Xor(b);}
00185                 PolynomialMod2 Minus(const PolynomialMod2 &b) const {return Xor(b);}
00187                 PolynomialMod2 Times(const PolynomialMod2 &b) const;
00189                 PolynomialMod2 DividedBy(const PolynomialMod2 &b) const;
00191                 PolynomialMod2 Modulo(const PolynomialMod2 &b) const;
00192 
00194                 PolynomialMod2 operator>>(unsigned int n) const;
00196                 PolynomialMod2 operator<<(unsigned int n) const;
00198 
00200 
00201 
00202                 unsigned int Parity() const;
00203 
00205                 bool IsIrreducible() const;
00206 
00208                 PolynomialMod2 Doubled() const {return Zero();}
00210                 PolynomialMod2 Squared() const;
00211 
00213                 bool IsUnit() const {return Equals(One());}
00215                 PolynomialMod2 MultiplicativeInverse() const {return IsUnit() ? One() : Zero();}
00216 
00218                 static PolynomialMod2 Gcd(const PolynomialMod2 &a, const PolynomialMod2 &n);
00220                 PolynomialMod2 InverseMod(const PolynomialMod2 &) const;
00221 
00223                 static void Divide(PolynomialMod2 &r, PolynomialMod2 &q, const PolynomialMod2 &a, const PolynomialMod2 &d);
00225 
00227 
00228 
00229                 friend std::ostream& operator<<(std::ostream& out, const PolynomialMod2 &a);
00231 
00232 private:
00233         friend class GF2NT;
00234 
00235         SecWordBlock reg;
00236 };
00237 
00239 class GF2NP : public QuotientRing<EuclideanDomainOf<PolynomialMod2> >
00240 {
00241 public:
00242         GF2NP(const PolynomialMod2 &modulus);
00243 
00244         virtual GF2NP * Clone() const {return new GF2NP(*this);}
00245         virtual void DEREncode(BufferedTransformation &bt) const
00246                 {assert(false);}        // no ASN.1 syntax yet for general polynomial basis
00247 
00248         void DEREncodeElement(BufferedTransformation &out, const Element &a) const;
00249         void BERDecodeElement(BufferedTransformation &in, Element &a) const;
00250 
00251         bool Equal(const Element &a, const Element &b) const
00252                 {assert(a.Degree() < m_modulus.Degree() && b.Degree() < m_modulus.Degree()); return a.Equals(b);}
00253 
00254         bool IsUnit(const Element &a) const
00255                 {assert(a.Degree() < m_modulus.Degree()); return !!a;}
00256 
00257         unsigned int MaxElementBitLength() const
00258                 {return m;}
00259 
00260         unsigned int MaxElementByteLength() const
00261                 {return bitsToBytes(MaxElementBitLength());}
00262 
00263         Element SquareRoot(const Element &a) const;
00264 
00265         Element HalfTrace(const Element &a) const;
00266 
00267         // returns z such that z^2 + z == a
00268         Element SolveQuadraticEquation(const Element &a) const;
00269 
00270 protected:
00271         unsigned int m;
00272 };
00273 
00275 class GF2NT : public GF2NP
00276 {
00277 public:
00278         // polynomial modulus = x^t0 + x^t1 + x^t2, t0 > t1 > t2
00279         GF2NT(unsigned int t0, unsigned int t1, unsigned int t2);
00280 
00281         GF2NP * Clone() const {return new GF2NT(*this);}
00282         void DEREncode(BufferedTransformation &bt) const;
00283 
00284         const Element& Multiply(const Element &a, const Element &b) const;
00285 
00286         const Element& Square(const Element &a) const
00287                 {return Reduced(a.Squared());}
00288 
00289         const Element& MultiplicativeInverse(const Element &a) const;
00290 
00291 private:
00292         const Element& Reduced(const Element &a) const;
00293 
00294         unsigned int t0, t1;
00295         PolynomialMod2 result;
00296 };
00297 
00299 class GF2NPP : public GF2NP
00300 {
00301 public:
00302         // polynomial modulus = x^t0 + x^t1 + x^t2 + x^t3 + x^t4, t0 > t1 > t2 > t3 > t4
00303         GF2NPP(unsigned int t0, unsigned int t1, unsigned int t2, unsigned int t3, unsigned int t4)
00304                 : GF2NP(PolynomialMod2::Pentanomial(t0, t1, t2, t3, t4)), t0(t0), t1(t1), t2(t2), t3(t3) {}
00305 
00306         GF2NP * Clone() const {return new GF2NPP(*this);}
00307         void DEREncode(BufferedTransformation &bt) const;
00308 
00309 private:
00310         unsigned int t0, t1, t2, t3;
00311 };
00312 
00313 // construct new GF2NP from the ASN.1 sequence Characteristic-two
00314 GF2NP * BERDecodeGF2NP(BufferedTransformation &bt);
00315 
00316 NAMESPACE_END
00317 
00318 // declaring these overloaded operators inside the CryptoPP namespace
00319 // causes problems with GCC 2.95.2
00320 
00322 inline bool operator==(const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b)
00323         {return a.Equals(b);}
00325 inline bool operator!=(const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b)
00326         {return !(a==b);}
00328 inline bool operator> (const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b)
00329         {return a.Degree() > b.Degree();}
00331 inline bool operator>=(const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b)
00332         {return a.Degree() >= b.Degree();}
00334 inline bool operator< (const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b)
00335         {return a.Degree() < b.Degree();}
00337 inline bool operator<=(const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b)
00338         {return a.Degree() <= b.Degree();}
00340 inline CryptoPP::PolynomialMod2 operator&(const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b) {return a.And(b);}
00342 inline CryptoPP::PolynomialMod2 operator^(const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b) {return a.Xor(b);}
00344 inline CryptoPP::PolynomialMod2 operator+(const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b) {return a.Plus(b);}
00346 inline CryptoPP::PolynomialMod2 operator-(const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b) {return a.Minus(b);}
00348 inline CryptoPP::PolynomialMod2 operator*(const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b) {return a.Times(b);}
00350 inline CryptoPP::PolynomialMod2 operator/(const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b) {return a.DividedBy(b);}
00352 inline CryptoPP::PolynomialMod2 operator%(const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b) {return a.Modulo(b);}
00353 
00354 NAMESPACE_BEGIN(std)
00355 template<> inline void swap(CryptoPP::PolynomialMod2 &a, CryptoPP::PolynomialMod2 &b)
00356 {
00357         a.swap(b);
00358 }
00359 NAMESPACE_END
00360 
00361 #endif