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

Generated on Fri Aug 27 15:51:06 2004 for Crypto++ by doxygen 1.3.8