00001 #ifndef CRYPTOPP_GF2N_H
00002 #define CRYPTOPP_GF2N_H
00003
00004
00005
00006 #include "cryptlib.h"
00007 #include "secblock.h"
00008 #include "algebra.h"
00009 #include "misc.h"
00010 #include "asn.h"
00011
00012 #include <iosfwd>
00013
00014 NAMESPACE_BEGIN(CryptoPP)
00015
00016
00017
00018 class CRYPTOPP_DLL PolynomialMod2
00019 {
00020 public:
00021
00022
00023
00024 class DivideByZero : public Exception
00025 {
00026 public:
00027 DivideByZero() : Exception(OTHER_ERROR, "PolynomialMod2: division by zero") {}
00028 };
00029
00030 typedef unsigned int RandomizationParameter;
00031
00032
00033
00034
00035
00036 PolynomialMod2();
00037
00038 PolynomialMod2(const PolynomialMod2& t);
00039
00040
00041
00042
00043
00044
00045 PolynomialMod2(word value, size_t bitLength=WORD_BITS);
00046
00047
00048 PolynomialMod2(const byte *encodedPoly, size_t byteCount)
00049 {Decode(encodedPoly, byteCount);}
00050
00051
00052 PolynomialMod2(BufferedTransformation &encodedPoly, size_t byteCount)
00053 {Decode(encodedPoly, byteCount);}
00054
00055
00056 PolynomialMod2(RandomNumberGenerator &rng, size_t bitcount)
00057 {Randomize(rng, bitcount);}
00058
00059
00060 static PolynomialMod2 CRYPTOPP_API Monomial(size_t i);
00061
00062 static PolynomialMod2 CRYPTOPP_API Trinomial(size_t t0, size_t t1, size_t t2);
00063
00064 static PolynomialMod2 CRYPTOPP_API Pentanomial(size_t t0, size_t t1, size_t t2, size_t t3, size_t t4);
00065
00066 static PolynomialMod2 CRYPTOPP_API AllOnes(size_t n);
00067
00068
00069 static const PolynomialMod2 & CRYPTOPP_API Zero();
00070
00071 static const PolynomialMod2 & CRYPTOPP_API One();
00072
00073
00074
00075
00076
00077
00078 unsigned int MinEncodedSize() const {return STDMAX(1U, ByteCount());}
00079
00080
00081
00082
00083
00084 void Encode(byte *output, size_t outputLen) const;
00085
00086 void Encode(BufferedTransformation &bt, size_t outputLen) const;
00087
00088
00089 void Decode(const byte *input, size_t inputLen);
00090
00091
00092 void Decode(BufferedTransformation &bt, size_t inputLen);
00093
00094
00095 void DEREncodeAsOctetString(BufferedTransformation &bt, size_t length) const;
00096
00097 void BERDecodeAsOctetString(BufferedTransformation &bt, size_t length);
00098
00099
00100
00101
00102
00103 unsigned int BitCount() const;
00104
00105 unsigned int ByteCount() const;
00106
00107 unsigned int WordCount() const;
00108
00109
00110 bool GetBit(size_t n) const {return GetCoefficient(n)!=0;}
00111
00112 byte GetByte(size_t n) const;
00113
00114
00115 signed int Degree() const {return (signed int)(BitCount()-1U);}
00116
00117 unsigned int CoefficientCount() const {return BitCount();}
00118
00119 int GetCoefficient(size_t i) const
00120 {return (i/WORD_BITS < reg.size()) ? int(reg[i/WORD_BITS] >> (i % WORD_BITS)) & 1 : 0;}
00121
00122 int operator[](unsigned int i) const {return GetCoefficient(i);}
00123
00124
00125 bool IsZero() const {return !*this;}
00126
00127 bool Equals(const PolynomialMod2 &rhs) const;
00128
00129
00130
00131
00132
00133 PolynomialMod2& operator=(const PolynomialMod2& t);
00134
00135 PolynomialMod2& operator&=(const PolynomialMod2& t);
00136
00137 PolynomialMod2& operator^=(const PolynomialMod2& t);
00138
00139 PolynomialMod2& operator+=(const PolynomialMod2& t) {return *this ^= t;}
00140
00141 PolynomialMod2& operator-=(const PolynomialMod2& t) {return *this ^= t;}
00142
00143 PolynomialMod2& operator*=(const PolynomialMod2& t);
00144
00145 PolynomialMod2& operator/=(const PolynomialMod2& t);
00146
00147 PolynomialMod2& operator%=(const PolynomialMod2& t);
00148
00149 PolynomialMod2& operator<<=(unsigned int);
00150
00151 PolynomialMod2& operator>>=(unsigned int);
00152
00153
00154 void Randomize(RandomNumberGenerator &rng, size_t bitcount);
00155
00156
00157 void SetBit(size_t i, int value = 1);
00158
00159 void SetByte(size_t n, byte value);
00160
00161
00162 void SetCoefficient(size_t i, int value) {SetBit(i, value);}
00163
00164
00165 void swap(PolynomialMod2 &a) {reg.swap(a.reg);}
00166
00167
00168
00169
00170
00171 bool operator!() const;
00172
00173 PolynomialMod2 operator+() const {return *this;}
00174
00175 PolynomialMod2 operator-() const {return *this;}
00176
00177
00178
00179
00180
00181 PolynomialMod2 And(const PolynomialMod2 &b) const;
00182
00183 PolynomialMod2 Xor(const PolynomialMod2 &b) const;
00184
00185 PolynomialMod2 Plus(const PolynomialMod2 &b) const {return Xor(b);}
00186
00187 PolynomialMod2 Minus(const PolynomialMod2 &b) const {return Xor(b);}
00188
00189 PolynomialMod2 Times(const PolynomialMod2 &b) const;
00190
00191 PolynomialMod2 DividedBy(const PolynomialMod2 &b) const;
00192
00193 PolynomialMod2 Modulo(const PolynomialMod2 &b) const;
00194
00195
00196 PolynomialMod2 operator>>(unsigned int n) const;
00197
00198 PolynomialMod2 operator<<(unsigned int n) const;
00199
00200
00201
00202
00203
00204 unsigned int Parity() const;
00205
00206
00207 bool IsIrreducible() const;
00208
00209
00210 PolynomialMod2 Doubled() const {return Zero();}
00211
00212 PolynomialMod2 Squared() const;
00213
00214
00215 bool IsUnit() const {return Equals(One());}
00216
00217 PolynomialMod2 MultiplicativeInverse() const {return IsUnit() ? One() : Zero();}
00218
00219
00220 static PolynomialMod2 CRYPTOPP_API Gcd(const PolynomialMod2 &a, const PolynomialMod2 &n);
00221
00222 PolynomialMod2 InverseMod(const PolynomialMod2 &) const;
00223
00224
00225 static void CRYPTOPP_API Divide(PolynomialMod2 &r, PolynomialMod2 &q, const PolynomialMod2 &a, const PolynomialMod2 &d);
00226
00227
00228
00229
00230
00231 friend std::ostream& operator<<(std::ostream& out, const PolynomialMod2 &a);
00232
00233
00234 private:
00235 friend class GF2NT;
00236
00237 SecWordBlock reg;
00238 };
00239
00240
00241 inline bool operator==(const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b)
00242 {return a.Equals(b);}
00243
00244 inline bool operator!=(const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b)
00245 {return !(a==b);}
00246
00247 inline bool operator> (const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b)
00248 {return a.Degree() > b.Degree();}
00249
00250 inline bool operator>=(const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b)
00251 {return a.Degree() >= b.Degree();}
00252
00253 inline bool operator< (const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b)
00254 {return a.Degree() < b.Degree();}
00255
00256 inline bool operator<=(const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b)
00257 {return a.Degree() <= b.Degree();}
00258
00259 inline CryptoPP::PolynomialMod2 operator&(const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b) {return a.And(b);}
00260
00261 inline CryptoPP::PolynomialMod2 operator^(const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b) {return a.Xor(b);}
00262
00263 inline CryptoPP::PolynomialMod2 operator+(const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b) {return a.Plus(b);}
00264
00265 inline CryptoPP::PolynomialMod2 operator-(const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b) {return a.Minus(b);}
00266
00267 inline CryptoPP::PolynomialMod2 operator*(const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b) {return a.Times(b);}
00268
00269 inline CryptoPP::PolynomialMod2 operator/(const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b) {return a.DividedBy(b);}
00270
00271 inline CryptoPP::PolynomialMod2 operator%(const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b) {return a.Modulo(b);}
00272
00273
00274
00275 CRYPTOPP_DLL_TEMPLATE_CLASS AbstractGroup<PolynomialMod2>;
00276 CRYPTOPP_DLL_TEMPLATE_CLASS AbstractRing<PolynomialMod2>;
00277 CRYPTOPP_DLL_TEMPLATE_CLASS AbstractEuclideanDomain<PolynomialMod2>;
00278 CRYPTOPP_DLL_TEMPLATE_CLASS EuclideanDomainOf<PolynomialMod2>;
00279 CRYPTOPP_DLL_TEMPLATE_CLASS QuotientRing<EuclideanDomainOf<PolynomialMod2> >;
00280
00281
00282 class CRYPTOPP_DLL GF2NP : public QuotientRing<EuclideanDomainOf<PolynomialMod2> >
00283 {
00284 public:
00285 GF2NP(const PolynomialMod2 &modulus);
00286
00287 virtual GF2NP * Clone() const {return new GF2NP(*this);}
00288 virtual void DEREncode(BufferedTransformation &bt) const
00289 {CRYPTOPP_UNUSED(bt); assert(false);}
00290
00291 void DEREncodeElement(BufferedTransformation &out, const Element &a) const;
00292 void BERDecodeElement(BufferedTransformation &in, Element &a) const;
00293
00294 bool Equal(const Element &a, const Element &b) const
00295 {assert(a.Degree() < m_modulus.Degree() && b.Degree() < m_modulus.Degree()); return a.Equals(b);}
00296
00297 bool IsUnit(const Element &a) const
00298 {assert(a.Degree() < m_modulus.Degree()); return !!a;}
00299
00300 unsigned int MaxElementBitLength() const
00301 {return m;}
00302
00303 unsigned int MaxElementByteLength() const
00304 {return (unsigned int)BitsToBytes(MaxElementBitLength());}
00305
00306 Element SquareRoot(const Element &a) const;
00307
00308 Element HalfTrace(const Element &a) const;
00309
00310
00311 Element SolveQuadraticEquation(const Element &a) const;
00312
00313 protected:
00314 unsigned int m;
00315 };
00316
00317
00318 class CRYPTOPP_DLL GF2NT : public GF2NP
00319 {
00320 public:
00321
00322 GF2NT(unsigned int t0, unsigned int t1, unsigned int t2);
00323
00324 GF2NP * Clone() const {return new GF2NT(*this);}
00325 void DEREncode(BufferedTransformation &bt) const;
00326
00327 const Element& Multiply(const Element &a, const Element &b) const;
00328
00329 const Element& Square(const Element &a) const
00330 {return Reduced(a.Squared());}
00331
00332 const Element& MultiplicativeInverse(const Element &a) const;
00333
00334 private:
00335 const Element& Reduced(const Element &a) const;
00336
00337 unsigned int t0, t1;
00338 mutable PolynomialMod2 result;
00339 };
00340
00341
00342 class CRYPTOPP_DLL GF2NPP : public GF2NP
00343 {
00344 public:
00345
00346 GF2NPP(unsigned int t0, unsigned int t1, unsigned int t2, unsigned int t3, unsigned int t4)
00347 : GF2NP(PolynomialMod2::Pentanomial(t0, t1, t2, t3, t4)), t0(t0), t1(t1), t2(t2), t3(t3) {}
00348
00349 GF2NP * Clone() const {return new GF2NPP(*this);}
00350 void DEREncode(BufferedTransformation &bt) const;
00351
00352 private:
00353 unsigned int t0, t1, t2, t3;
00354 };
00355
00356
00357 CRYPTOPP_DLL GF2NP * CRYPTOPP_API BERDecodeGF2NP(BufferedTransformation &bt);
00358
00359 NAMESPACE_END
00360
00361 #ifndef __BORLANDC__
00362 NAMESPACE_BEGIN(std)
00363 template<> inline void swap(CryptoPP::PolynomialMod2 &a, CryptoPP::PolynomialMod2 &b)
00364 {
00365 a.swap(b);
00366 }
00367 NAMESPACE_END
00368 #endif
00369
00370 #endif