00001 #ifndef CRYPTOPP_GF2N_H
00002 #define CRYPTOPP_GF2N_H
00003
00004
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
00016
00017 class CRYPTOPP_DLL PolynomialMod2
00018 {
00019 public:
00020
00021
00022
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
00033
00034
00035 PolynomialMod2();
00036
00037 PolynomialMod2(const PolynomialMod2& t);
00038
00039
00040
00041
00042
00043
00044 PolynomialMod2(word value, unsigned int bitLength=WORD_BITS);
00045
00046
00047 PolynomialMod2(const byte *encodedPoly, unsigned int byteCount)
00048 {Decode(encodedPoly, byteCount);}
00049
00050
00051 PolynomialMod2(BufferedTransformation &encodedPoly, unsigned int byteCount)
00052 {Decode(encodedPoly, byteCount);}
00053
00054
00055 PolynomialMod2(RandomNumberGenerator &rng, unsigned int bitcount)
00056 {Randomize(rng, bitcount);}
00057
00058
00059 static PolynomialMod2 Monomial(unsigned i);
00060
00061 static PolynomialMod2 Trinomial(unsigned t0, unsigned t1, unsigned t2);
00062
00063 static PolynomialMod2 Pentanomial(unsigned t0, unsigned t1, unsigned t2, unsigned int t3, unsigned int t4);
00064
00065 static PolynomialMod2 AllOnes(unsigned n);
00066
00067
00068 static const PolynomialMod2 & Zero();
00069
00070 static const PolynomialMod2 & One();
00071
00072
00073
00074
00075
00076
00077 unsigned int MinEncodedSize() const {return STDMAX(1U, ByteCount());}
00078
00079
00080
00081
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
00091 void Decode(BufferedTransformation &bt, unsigned int inputLen);
00092
00093
00094 void DEREncodeAsOctetString(BufferedTransformation &bt, unsigned int length) const;
00095
00096 void BERDecodeAsOctetString(BufferedTransformation &bt, unsigned int length);
00097
00098
00099
00100
00101
00102 unsigned int BitCount() const;
00103
00104 unsigned int ByteCount() const;
00105
00106 unsigned int WordCount() const;
00107
00108
00109 bool GetBit(unsigned int n) const {return GetCoefficient(n)!=0;}
00110
00111 byte GetByte(unsigned int n) const;
00112
00113
00114 signed int Degree() const {return BitCount()-1;}
00115
00116 unsigned int CoefficientCount() const {return BitCount();}
00117
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
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
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
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
00168
00169
00170 bool operator!() const;
00171
00172 PolynomialMod2 operator+() const {return *this;}
00173
00174 PolynomialMod2 operator-() const {return *this;}
00175
00176
00177
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
00201
00202
00203 unsigned int Parity() const;
00204
00205
00206 bool IsIrreducible() const;
00207
00208
00209 PolynomialMod2 Doubled() const {return Zero();}
00210
00211 PolynomialMod2 Squared() const;
00212
00213
00214 bool IsUnit() const {return Equals(One());}
00215
00216 PolynomialMod2 MultiplicativeInverse() const {return IsUnit() ? One() : Zero();}
00217
00218
00219 static PolynomialMod2 Gcd(const PolynomialMod2 &a, const PolynomialMod2 &n);
00220
00221 PolynomialMod2 InverseMod(const PolynomialMod2 &) const;
00222
00223
00224 static void Divide(PolynomialMod2 &r, PolynomialMod2 &q, const PolynomialMod2 &a, const PolynomialMod2 &d);
00225
00226
00227
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 CRYPTOPP_DLL_TEMPLATE_CLASS AbstractGroup<PolynomialMod2>;
00240 CRYPTOPP_DLL_TEMPLATE_CLASS AbstractRing<PolynomialMod2>;
00241 CRYPTOPP_DLL_TEMPLATE_CLASS EuclideanDomainOf<PolynomialMod2>;
00242 CRYPTOPP_DLL_TEMPLATE_CLASS QuotientRing<EuclideanDomainOf<PolynomialMod2> >;
00243
00244
00245 class CRYPTOPP_DLL GF2NP : public QuotientRing<EuclideanDomainOf<PolynomialMod2> >
00246 {
00247 public:
00248 GF2NP(const PolynomialMod2 &modulus);
00249
00250 virtual GF2NP * Clone() const {return new GF2NP(*this);}
00251 virtual void DEREncode(BufferedTransformation &bt) const
00252 {assert(false);}
00253
00254 void DEREncodeElement(BufferedTransformation &out, const Element &a) const;
00255 void BERDecodeElement(BufferedTransformation &in, Element &a) const;
00256
00257 bool Equal(const Element &a, const Element &b) const
00258 {assert(a.Degree() < m_modulus.Degree() && b.Degree() < m_modulus.Degree()); return a.Equals(b);}
00259
00260 bool IsUnit(const Element &a) const
00261 {assert(a.Degree() < m_modulus.Degree()); return !!a;}
00262
00263 unsigned int MaxElementBitLength() const
00264 {return m;}
00265
00266 unsigned int MaxElementByteLength() const
00267 {return BitsToBytes(MaxElementBitLength());}
00268
00269 Element SquareRoot(const Element &a) const;
00270
00271 Element HalfTrace(const Element &a) const;
00272
00273
00274 Element SolveQuadraticEquation(const Element &a) const;
00275
00276 protected:
00277 unsigned int m;
00278 };
00279
00280
00281 class CRYPTOPP_DLL GF2NT : public GF2NP
00282 {
00283 public:
00284
00285 GF2NT(unsigned int t0, unsigned int t1, unsigned int t2);
00286
00287 GF2NP * Clone() const {return new GF2NT(*this);}
00288 void DEREncode(BufferedTransformation &bt) const;
00289
00290 const Element& Multiply(const Element &a, const Element &b) const;
00291
00292 const Element& Square(const Element &a) const
00293 {return Reduced(a.Squared());}
00294
00295 const Element& MultiplicativeInverse(const Element &a) const;
00296
00297 private:
00298 const Element& Reduced(const Element &a) const;
00299
00300 unsigned int t0, t1;
00301 mutable PolynomialMod2 result;
00302 };
00303
00304
00305 class CRYPTOPP_DLL GF2NPP : public GF2NP
00306 {
00307 public:
00308
00309 GF2NPP(unsigned int t0, unsigned int t1, unsigned int t2, unsigned int t3, unsigned int t4)
00310 : GF2NP(PolynomialMod2::Pentanomial(t0, t1, t2, t3, t4)), t0(t0), t1(t1), t2(t2), t3(t3) {}
00311
00312 GF2NP * Clone() const {return new GF2NPP(*this);}
00313 void DEREncode(BufferedTransformation &bt) const;
00314
00315 private:
00316 unsigned int t0, t1, t2, t3;
00317 };
00318
00319
00320 CRYPTOPP_DLL GF2NP * BERDecodeGF2NP(BufferedTransformation &bt);
00321
00322
00323 inline bool operator==(const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b)
00324 {return a.Equals(b);}
00325
00326 inline bool operator!=(const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b)
00327 {return !(a==b);}
00328
00329 inline bool operator> (const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b)
00330 {return a.Degree() > b.Degree();}
00331
00332 inline bool operator>=(const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b)
00333 {return a.Degree() >= b.Degree();}
00334
00335 inline bool operator< (const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b)
00336 {return a.Degree() < b.Degree();}
00337
00338 inline bool operator<=(const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b)
00339 {return a.Degree() <= b.Degree();}
00340
00341 inline CryptoPP::PolynomialMod2 operator&(const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b) {return a.And(b);}
00342
00343 inline CryptoPP::PolynomialMod2 operator^(const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b) {return a.Xor(b);}
00344
00345 inline CryptoPP::PolynomialMod2 operator+(const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b) {return a.Plus(b);}
00346
00347 inline CryptoPP::PolynomialMod2 operator-(const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b) {return a.Minus(b);}
00348
00349 inline CryptoPP::PolynomialMod2 operator*(const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b) {return a.Times(b);}
00350
00351 inline CryptoPP::PolynomialMod2 operator/(const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b) {return a.DividedBy(b);}
00352
00353 inline CryptoPP::PolynomialMod2 operator%(const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b) {return a.Modulo(b);}
00354
00355 NAMESPACE_END
00356
00357 NAMESPACE_BEGIN(std)
00358 template<> inline void swap(CryptoPP::PolynomialMod2 &a, CryptoPP::PolynomialMod2 &b)
00359 {
00360 a.swap(b);
00361 }
00362 NAMESPACE_END
00363
00364 #endif