1#ifndef CRYPTOPP_GF2N_H 2#define CRYPTOPP_GF2N_H 3 4/*! \file */ 5 6#include "cryptlib.h" 7#include "secblock.h" 8#include "misc.h" 9#include "algebra.h" 10 11#include <iosfwd> 12 13NAMESPACE_BEGIN(CryptoPP) 14 15//! Polynomial with Coefficients in GF(2) 16/*! \nosubgrouping */ 17class CRYPTOPP_DLL PolynomialMod2 18{ 19public: 20 //! \name ENUMS, EXCEPTIONS, and TYPEDEFS 21 //@{ 22 //! divide by zero exception 23 class DivideByZero : public Exception 24 { 25 public: 26 DivideByZero() : Exception(OTHER_ERROR, "PolynomialMod2: division by zero") {} 27 }; 28 29 typedef unsigned int RandomizationParameter; 30 //@} 31 32 //! \name CREATORS 33 //@{ 34 //! creates the zero polynomial 35 PolynomialMod2(); 36 //! copy constructor 37 PolynomialMod2(const PolynomialMod2& t); 38 39 //! convert from word 40 /*! value should be encoded with the least significant bit as coefficient to x^0 41 and most significant bit as coefficient to x^(WORD_BITS-1) 42 bitLength denotes how much memory to allocate initially 43 */ 44 PolynomialMod2(word value, size_t bitLength=WORD_BITS); 45 46 //! convert from big-endian byte array 47 PolynomialMod2(const byte *encodedPoly, size_t byteCount) 48 {Decode(encodedPoly, byteCount);} 49 50 //! convert from big-endian form stored in a BufferedTransformation 51 PolynomialMod2(BufferedTransformation &encodedPoly, size_t byteCount) 52 {Decode(encodedPoly, byteCount);} 53 54 //! create a random polynomial uniformly distributed over all polynomials with degree less than bitcount 55 PolynomialMod2(RandomNumberGenerator &rng, size_t bitcount) 56 {Randomize(rng, bitcount);} 57 58 //! return x^i 59 static PolynomialMod2 CRYPTOPP_API Monomial(size_t i); 60 //! return x^t0 + x^t1 + x^t2 61 static PolynomialMod2 CRYPTOPP_API Trinomial(size_t t0, size_t t1, size_t t2); 62 //! return x^t0 + x^t1 + x^t2 + x^t3 + x^t4 63 static PolynomialMod2 CRYPTOPP_API Pentanomial(size_t t0, size_t t1, size_t t2, size_t t3, size_t t4); 64 //! return x^(n-1) + ... + x + 1 65 static PolynomialMod2 CRYPTOPP_API AllOnes(size_t n); 66 67 //! 68 static const PolynomialMod2 & CRYPTOPP_API Zero(); 69 //! 70 static const PolynomialMod2 & CRYPTOPP_API One(); 71 //@} 72 73 //! \name ENCODE/DECODE 74 //@{ 75 //! minimum number of bytes to encode this polynomial 76 /*! MinEncodedSize of 0 is 1 */ 77 unsigned int MinEncodedSize() const {return STDMAX(1U, ByteCount());} 78 79 //! encode in big-endian format 80 /*! if outputLen < MinEncodedSize, the most significant bytes will be dropped 81 if outputLen > MinEncodedSize, the most significant bytes will be padded 82 */ 83 void Encode(byte *output, size_t outputLen) const; 84 //! 85 void Encode(BufferedTransformation &bt, size_t outputLen) const; 86 87 //! 88 void Decode(const byte *input, size_t inputLen); 89 //! 90 //* Precondition: bt.MaxRetrievable() >= inputLen 91 void Decode(BufferedTransformation &bt, size_t inputLen); 92 93 //! encode value as big-endian octet string 94 void DEREncodeAsOctetString(BufferedTransformation &bt, size_t length) const; 95 //! decode value as big-endian octet string 96 void BERDecodeAsOctetString(BufferedTransformation &bt, size_t length); 97 //@} 98 99 //! \name ACCESSORS 100 //@{ 101 //! number of significant bits = Degree() + 1 102 unsigned int BitCount() const; 103 //! number of significant bytes = ceiling(BitCount()/8) 104 unsigned int ByteCount() const; 105 //! number of significant words = ceiling(ByteCount()/sizeof(word)) 106 unsigned int WordCount() const; 107 108 //! return the n-th bit, n=0 being the least significant bit 109 bool GetBit(size_t n) const {return GetCoefficient(n)!=0;} 110 //! return the n-th byte 111 byte GetByte(size_t n) const; 112 113 //! the zero polynomial will return a degree of -1 114 signed int Degree() const {return BitCount()-1;} 115 //! degree + 1 116 unsigned int CoefficientCount() const {return BitCount();} 117 //! return coefficient for x^i 118 int GetCoefficient(size_t i) const 119 {return (i/WORD_BITS < reg.size()) ? int(reg[i/WORD_BITS] >> (i % WORD_BITS)) & 1 : 0;} 120 //! return coefficient for x^i 121 int operator[](unsigned int i) const {return GetCoefficient(i);} 122 123 //! 124 bool IsZero() const {return !*this;} 125 //! 126 bool Equals(const PolynomialMod2 &rhs) const; 127 //@} 128 129 //! \name MANIPULATORS 130 //@{ 131 //! 132 PolynomialMod2& operator=(const PolynomialMod2& t); 133 //! 134 PolynomialMod2& operator&=(const PolynomialMod2& t); 135 //! 136 PolynomialMod2& operator^=(const PolynomialMod2& t); 137 //! 138 PolynomialMod2& operator+=(const PolynomialMod2& t) {return *this ^= t;} 139 //! 140 PolynomialMod2& operator-=(const PolynomialMod2& t) {return *this ^= t;} 141 //! 142 PolynomialMod2& operator*=(const PolynomialMod2& t); 143 //! 144 PolynomialMod2& operator/=(const PolynomialMod2& t); 145 //! 146 PolynomialMod2& operator%=(const PolynomialMod2& t); 147 //! 148 PolynomialMod2& operator<<=(unsigned int); 149 //! 150 PolynomialMod2& operator>>=(unsigned int); 151 152 //! 153 void Randomize(RandomNumberGenerator &rng, size_t bitcount); 154 155 //! 156 void SetBit(size_t i, int value = 1); 157 //! set the n-th byte to value 158 void SetByte(size_t n, byte value); 159 160 //! 161 void SetCoefficient(size_t i, int value) {SetBit(i, value);} 162 163 //! 164 void swap(PolynomialMod2 &a) {reg.swap(a.reg);} 165 //@} 166 167 //! \name UNARY OPERATORS 168 //@{ 169 //! 170 bool operator!() const; 171 //! 172 PolynomialMod2 operator+() const {return *this;} 173 //! 174 PolynomialMod2 operator-() const {return *this;} 175 //@} 176 177 //! \name BINARY OPERATORS 178 //@{ 179 //! 180 PolynomialMod2 And(const PolynomialMod2 &b) const; 181 //! 182 PolynomialMod2 Xor(const PolynomialMod2 &b) const; 183 //! 184 PolynomialMod2 Plus(const PolynomialMod2 &b) const {return Xor(b);} 185 //! 186 PolynomialMod2 Minus(const PolynomialMod2 &b) const {return Xor(b);} 187 //! 188 PolynomialMod2 Times(const PolynomialMod2 &b) const; 189 //! 190 PolynomialMod2 DividedBy(const PolynomialMod2 &b) const; 191 //! 192 PolynomialMod2 Modulo(const PolynomialMod2 &b) const; 193 194 //! 195 PolynomialMod2 operator>>(unsigned int n) const; 196 //! 197 PolynomialMod2 operator<<(unsigned int n) const; 198 //@} 199 200 //! \name OTHER ARITHMETIC FUNCTIONS 201 //@{ 202 //! sum modulo 2 of all coefficients 203 unsigned int Parity() const; 204 205 //! check for irreducibility 206 bool IsIrreducible() const; 207 208 //! is always zero since we're working modulo 2 209 PolynomialMod2 Doubled() const {return Zero();} 210 //! 211 PolynomialMod2 Squared() const; 212 213 //! only 1 is a unit 214 bool IsUnit() const {return Equals(One());} 215 //! return inverse if *this is a unit, otherwise return 0 216 PolynomialMod2 MultiplicativeInverse() const {return IsUnit() ? One() : Zero();} 217 218 //! greatest common divisor 219 static PolynomialMod2 CRYPTOPP_API Gcd(const PolynomialMod2 &a, const PolynomialMod2 &n); 220 //! calculate multiplicative inverse of *this mod n 221 PolynomialMod2 InverseMod(const PolynomialMod2 &) const; 222 223 //! calculate r and q such that (a == d*q + r) && (deg(r) < deg(d)) 224 static void CRYPTOPP_API Divide(PolynomialMod2 &r, PolynomialMod2 &q, const PolynomialMod2 &a, const PolynomialMod2 &d); 225 //@} 226 227 //! \name INPUT/OUTPUT 228 //@{ 229 //! 230 friend std::ostream& operator<<(std::ostream& out, const PolynomialMod2 &a); 231 //@} 232 233private: 234 friend class GF2NT; 235 236 SecWordBlock reg; 237}; 238 239//! 240inline bool operator==(const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b) 241{return a.Equals(b);} 242//! 243inline bool operator!=(const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b) 244{return !(a==b);} 245//! compares degree 246inline bool operator> (const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b) 247{return a.Degree() > b.Degree();} 248//! compares degree 249inline bool operator>=(const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b) 250{return a.Degree() >= b.Degree();} 251//! compares degree 252inline bool operator< (const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b) 253{return a.Degree() < b.Degree();} 254//! compares degree 255inline bool operator<=(const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b) 256{return a.Degree() <= b.Degree();} 257//! 258inline CryptoPP::PolynomialMod2 operator&(const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b) {return a.And(b);} 259//! 260inline CryptoPP::PolynomialMod2 operator^(const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b) {return a.Xor(b);} 261//! 262inline CryptoPP::PolynomialMod2 operator+(const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b) {return a.Plus(b);} 263//! 264inline CryptoPP::PolynomialMod2 operator-(const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b) {return a.Minus(b);} 265//! 266inline CryptoPP::PolynomialMod2 operator*(const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b) {return a.Times(b);} 267//! 268inline CryptoPP::PolynomialMod2 operator/(const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b) {return a.DividedBy(b);} 269//! 270inline CryptoPP::PolynomialMod2 operator%(const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b) {return a.Modulo(b);} 271 272// CodeWarrior 8 workaround: put these template instantiations after overloaded operator declarations, 273// but before the use of QuotientRing<EuclideanDomainOf<PolynomialMod2> > for VC .NET 2003 274CRYPTOPP_DLL_TEMPLATE_CLASS AbstractGroup<PolynomialMod2>; 275CRYPTOPP_DLL_TEMPLATE_CLASS AbstractRing<PolynomialMod2>; 276CRYPTOPP_DLL_TEMPLATE_CLASS AbstractEuclideanDomain<PolynomialMod2>; 277CRYPTOPP_DLL_TEMPLATE_CLASS EuclideanDomainOf<PolynomialMod2>; 278CRYPTOPP_DLL_TEMPLATE_CLASS QuotientRing<EuclideanDomainOf<PolynomialMod2> >; 279 280//! GF(2^n) with Polynomial Basis 281class CRYPTOPP_DLL GF2NP : public QuotientRing<EuclideanDomainOf<PolynomialMod2> > 282{ 283public: 284 GF2NP(const PolynomialMod2 &modulus); 285 286 virtual GF2NP * Clone() const {return new GF2NP(*this);} 287 virtual void DEREncode(BufferedTransformation &bt) const 288 {assert(false);} // no ASN.1 syntax yet for general polynomial basis 289 290 void DEREncodeElement(BufferedTransformation &out, const Element &a) const; 291 void BERDecodeElement(BufferedTransformation &in, Element &a) const; 292 293 bool Equal(const Element &a, const Element &b) const 294 {assert(a.Degree() < m_modulus.Degree() && b.Degree() < m_modulus.Degree()); return a.Equals(b);} 295 296 bool IsUnit(const Element &a) const 297 {assert(a.Degree() < m_modulus.Degree()); return !!a;} 298 299 unsigned int MaxElementBitLength() const 300 {return m;} 301 302 unsigned int MaxElementByteLength() const 303 {return (unsigned int)BitsToBytes(MaxElementBitLength());} 304 305 Element SquareRoot(const Element &a) const; 306 307 Element HalfTrace(const Element &a) const; 308 309 // returns z such that z^2 + z == a 310 Element SolveQuadraticEquation(const Element &a) const; 311 312protected: 313 unsigned int m; 314}; 315 316//! GF(2^n) with Trinomial Basis 317class CRYPTOPP_DLL GF2NT : public GF2NP 318{ 319public: 320 // polynomial modulus = x^t0 + x^t1 + x^t2, t0 > t1 > t2 321 GF2NT(unsigned int t0, unsigned int t1, unsigned int t2); 322 323 GF2NP * Clone() const {return new GF2NT(*this);} 324 void DEREncode(BufferedTransformation &bt) const; 325 326 const Element& Multiply(const Element &a, const Element &b) const; 327 328 const Element& Square(const Element &a) const 329 {return Reduced(a.Squared());} 330 331 const Element& MultiplicativeInverse(const Element &a) const; 332 333private: 334 const Element& Reduced(const Element &a) const; 335 336 unsigned int t0, t1; 337 mutable PolynomialMod2 result; 338}; 339 340//! GF(2^n) with Pentanomial Basis 341class CRYPTOPP_DLL GF2NPP : public GF2NP 342{ 343public: 344 // polynomial modulus = x^t0 + x^t1 + x^t2 + x^t3 + x^t4, t0 > t1 > t2 > t3 > t4 345 GF2NPP(unsigned int t0, unsigned int t1, unsigned int t2, unsigned int t3, unsigned int t4) 346 : GF2NP(PolynomialMod2::Pentanomial(t0, t1, t2, t3, t4)), t0(t0), t1(t1), t2(t2), t3(t3) {} 347 348 GF2NP * Clone() const {return new GF2NPP(*this);} 349 void DEREncode(BufferedTransformation &bt) const; 350 351private: 352 unsigned int t0, t1, t2, t3; 353}; 354 355// construct new GF2NP from the ASN.1 sequence Characteristic-two 356CRYPTOPP_DLL GF2NP * CRYPTOPP_API BERDecodeGF2NP(BufferedTransformation &bt); 357 358NAMESPACE_END 359 360#ifndef __BORLANDC__ 361NAMESPACE_BEGIN(std) 362template<> inline void swap(CryptoPP::PolynomialMod2 &a, CryptoPP::PolynomialMod2 &b) 363{ 364 a.swap(b); 365} 366NAMESPACE_END 367#endif 368 369#endif 370