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 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 //! GF(2^n) with Polynomial Basis 00240 class GF2NP : public QuotientRing<EuclideanDomainOf<PolynomialMod2> > 00241 { 00242 public: 00243 GF2NP(const PolynomialMod2 &modulus); 00244 00245 virtual GF2NP * Clone() const {return new GF2NP(*this);} 00246 virtual void DEREncode(BufferedTransformation &bt) const 00247 {assert(false);} // no ASN.1 syntax yet for general polynomial basis 00248 00249 void DEREncodeElement(BufferedTransformation &out, const Element &a) const; 00250 void BERDecodeElement(BufferedTransformation &in, Element &a) const; 00251 00252 bool Equal(const Element &a, const Element &b) const 00253 {assert(a.Degree() < m_modulus.Degree() && b.Degree() < m_modulus.Degree()); return a.Equals(b);} 00254 00255 bool IsUnit(const Element &a) const 00256 {assert(a.Degree() < m_modulus.Degree()); return !!a;} 00257 00258 unsigned int MaxElementBitLength() const 00259 {return m;} 00260 00261 unsigned int MaxElementByteLength() const 00262 {return BitsToBytes(MaxElementBitLength());} 00263 00264 Element SquareRoot(const Element &a) const; 00265 00266 Element HalfTrace(const Element &a) const; 00267 00268 // returns z such that z^2 + z == a 00269 Element SolveQuadraticEquation(const Element &a) const; 00270 00271 protected: 00272 unsigned int m; 00273 }; 00274 00275 //! GF(2^n) with Trinomial Basis 00276 class GF2NT : public GF2NP 00277 { 00278 public: 00279 // polynomial modulus = x^t0 + x^t1 + x^t2, t0 > t1 > t2 00280 GF2NT(unsigned int t0, unsigned int t1, unsigned int t2); 00281 00282 GF2NP * Clone() const {return new GF2NT(*this);} 00283 void DEREncode(BufferedTransformation &bt) const; 00284 00285 const Element& Multiply(const Element &a, const Element &b) const; 00286 00287 const Element& Square(const Element &a) const 00288 {return Reduced(a.Squared());} 00289 00290 const Element& MultiplicativeInverse(const Element &a) const; 00291 00292 private: 00293 const Element& Reduced(const Element &a) const; 00294 00295 unsigned int t0, t1; 00296 mutable PolynomialMod2 result; 00297 }; 00298 00299 //! GF(2^n) with Pentanomial Basis 00300 class GF2NPP : public GF2NP 00301 { 00302 public: 00303 // polynomial modulus = x^t0 + x^t1 + x^t2 + x^t3 + x^t4, t0 > t1 > t2 > t3 > t4 00304 GF2NPP(unsigned int t0, unsigned int t1, unsigned int t2, unsigned int t3, unsigned int t4) 00305 : GF2NP(PolynomialMod2::Pentanomial(t0, t1, t2, t3, t4)), t0(t0), t1(t1), t2(t2), t3(t3) {} 00306 00307 GF2NP * Clone() const {return new GF2NPP(*this);} 00308 void DEREncode(BufferedTransformation &bt) const; 00309 00310 private: 00311 unsigned int t0, t1, t2, t3; 00312 }; 00313 00314 // construct new GF2NP from the ASN.1 sequence Characteristic-two 00315 GF2NP * BERDecodeGF2NP(BufferedTransformation &bt); 00316 00317 //! 00318 inline bool operator==(const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b) 00319 {return a.Equals(b);} 00320 //! 00321 inline bool operator!=(const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b) 00322 {return !(a==b);} 00323 //! compares degree 00324 inline bool operator> (const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b) 00325 {return a.Degree() > b.Degree();} 00326 //! compares degree 00327 inline bool operator>=(const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b) 00328 {return a.Degree() >= b.Degree();} 00329 //! compares degree 00330 inline bool operator< (const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b) 00331 {return a.Degree() < b.Degree();} 00332 //! compares degree 00333 inline bool operator<=(const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b) 00334 {return a.Degree() <= b.Degree();} 00335 //! 00336 inline CryptoPP::PolynomialMod2 operator&(const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b) {return a.And(b);} 00337 //! 00338 inline CryptoPP::PolynomialMod2 operator^(const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b) {return a.Xor(b);} 00339 //! 00340 inline CryptoPP::PolynomialMod2 operator+(const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b) {return a.Plus(b);} 00341 //! 00342 inline CryptoPP::PolynomialMod2 operator-(const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b) {return a.Minus(b);} 00343 //! 00344 inline CryptoPP::PolynomialMod2 operator*(const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b) {return a.Times(b);} 00345 //! 00346 inline CryptoPP::PolynomialMod2 operator/(const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b) {return a.DividedBy(b);} 00347 //! 00348 inline CryptoPP::PolynomialMod2 operator%(const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b) {return a.Modulo(b);} 00349 00350 NAMESPACE_END 00351 00352 NAMESPACE_BEGIN(std) 00353 template<> inline void swap(CryptoPP::PolynomialMod2 &a, CryptoPP::PolynomialMod2 &b) 00354 { 00355 a.swap(b); 00356 } 00357 NAMESPACE_END 00358 00359 #endif

Generated on Fri Aug 13 09:56:53 2004 for Crypto++ by doxygen 1.3.7