File indexing completed on 2025-01-18 09:55:03
0001
0002
0003
0004
0005
0006 #ifndef CRYPTOPP_GF2N_H
0007 #define CRYPTOPP_GF2N_H
0008
0009 #include "cryptlib.h"
0010 #include "secblock.h"
0011 #include "algebra.h"
0012 #include "misc.h"
0013 #include "asn.h"
0014
0015 #include <iosfwd>
0016
0017 #if CRYPTOPP_MSC_VERSION
0018 # pragma warning(push)
0019 # pragma warning(disable: 4231 4275)
0020 #endif
0021
0022 NAMESPACE_BEGIN(CryptoPP)
0023
0024
0025
0026 class CRYPTOPP_DLL PolynomialMod2
0027 {
0028 public:
0029
0030
0031
0032 class DivideByZero : public Exception
0033 {
0034 public:
0035 DivideByZero() : Exception(OTHER_ERROR, "PolynomialMod2: division by zero") {}
0036 };
0037
0038 typedef unsigned int RandomizationParameter;
0039
0040
0041
0042
0043
0044 PolynomialMod2();
0045
0046 PolynomialMod2(const PolynomialMod2& t);
0047
0048
0049
0050
0051
0052 PolynomialMod2(word value, size_t bitLength=WORD_BITS);
0053
0054
0055 PolynomialMod2(const byte *encodedPoly, size_t byteCount)
0056 {Decode(encodedPoly, byteCount);}
0057
0058
0059 PolynomialMod2(BufferedTransformation &encodedPoly, size_t byteCount)
0060 {Decode(encodedPoly, byteCount);}
0061
0062
0063
0064 PolynomialMod2(RandomNumberGenerator &rng, size_t bitcount)
0065 {Randomize(rng, bitcount);}
0066
0067
0068
0069 static PolynomialMod2 CRYPTOPP_API Monomial(size_t i);
0070
0071
0072 static PolynomialMod2 CRYPTOPP_API Trinomial(size_t t0, size_t t1, size_t t2);
0073
0074
0075 static PolynomialMod2 CRYPTOPP_API Pentanomial(size_t t0, size_t t1, size_t t2, size_t t3, size_t t4);
0076
0077
0078 static PolynomialMod2 CRYPTOPP_API AllOnes(size_t n);
0079
0080
0081
0082 static const PolynomialMod2 & CRYPTOPP_API Zero();
0083
0084
0085 static const PolynomialMod2 & CRYPTOPP_API One();
0086
0087
0088
0089
0090
0091
0092 unsigned int MinEncodedSize() const {return STDMAX(1U, ByteCount());}
0093
0094
0095
0096
0097 void Encode(byte *output, size_t outputLen) const;
0098
0099 void Encode(BufferedTransformation &bt, size_t outputLen) const;
0100
0101
0102 void Decode(const byte *input, size_t inputLen);
0103
0104
0105 void Decode(BufferedTransformation &bt, size_t inputLen);
0106
0107
0108 void DEREncodeAsOctetString(BufferedTransformation &bt, size_t length) const;
0109
0110 void BERDecodeAsOctetString(BufferedTransformation &bt, size_t length);
0111
0112
0113
0114
0115
0116 unsigned int BitCount() const;
0117
0118 unsigned int ByteCount() const;
0119
0120 unsigned int WordCount() const;
0121
0122
0123 bool GetBit(size_t n) const {return GetCoefficient(n)!=0;}
0124
0125 byte GetByte(size_t n) const;
0126
0127
0128 signed int Degree() const {return (signed int)(BitCount()-1U);}
0129
0130 unsigned int CoefficientCount() const {return BitCount();}
0131
0132 int GetCoefficient(size_t i) const
0133 {return (i/WORD_BITS < reg.size()) ? int(reg[i/WORD_BITS] >> (i % WORD_BITS)) & 1 : 0;}
0134
0135 int operator[](unsigned int i) const {return GetCoefficient(i);}
0136
0137
0138 bool IsZero() const {return !*this;}
0139
0140 bool Equals(const PolynomialMod2 &rhs) const;
0141
0142
0143
0144
0145
0146 PolynomialMod2& operator=(const PolynomialMod2& t);
0147
0148 PolynomialMod2& operator&=(const PolynomialMod2& t);
0149
0150 PolynomialMod2& operator^=(const PolynomialMod2& t);
0151
0152 PolynomialMod2& operator+=(const PolynomialMod2& t) {return *this ^= t;}
0153
0154 PolynomialMod2& operator-=(const PolynomialMod2& t) {return *this ^= t;}
0155
0156 PolynomialMod2& operator*=(const PolynomialMod2& t);
0157
0158 PolynomialMod2& operator/=(const PolynomialMod2& t);
0159
0160 PolynomialMod2& operator%=(const PolynomialMod2& t);
0161
0162 PolynomialMod2& operator<<=(unsigned int);
0163
0164 PolynomialMod2& operator>>=(unsigned int);
0165
0166
0167 void Randomize(RandomNumberGenerator &rng, size_t bitcount);
0168
0169
0170 void SetBit(size_t i, int value = 1);
0171
0172 void SetByte(size_t n, byte value);
0173
0174
0175 void SetCoefficient(size_t i, int value) {SetBit(i, value);}
0176
0177
0178 void swap(PolynomialMod2 &a) {reg.swap(a.reg);}
0179
0180
0181
0182
0183
0184 bool operator!() const;
0185
0186 PolynomialMod2 operator+() const {return *this;}
0187
0188 PolynomialMod2 operator-() const {return *this;}
0189
0190
0191
0192
0193
0194 PolynomialMod2 And(const PolynomialMod2 &b) const;
0195
0196 PolynomialMod2 Xor(const PolynomialMod2 &b) const;
0197
0198 PolynomialMod2 Plus(const PolynomialMod2 &b) const {return Xor(b);}
0199
0200 PolynomialMod2 Minus(const PolynomialMod2 &b) const {return Xor(b);}
0201
0202 PolynomialMod2 Times(const PolynomialMod2 &b) const;
0203
0204 PolynomialMod2 DividedBy(const PolynomialMod2 &b) const;
0205
0206 PolynomialMod2 Modulo(const PolynomialMod2 &b) const;
0207
0208
0209 PolynomialMod2 operator>>(unsigned int n) const;
0210
0211 PolynomialMod2 operator<<(unsigned int n) const;
0212
0213
0214
0215
0216
0217 unsigned int Parity() const;
0218
0219
0220 bool IsIrreducible() const;
0221
0222
0223 PolynomialMod2 Doubled() const {return Zero();}
0224
0225 PolynomialMod2 Squared() const;
0226
0227
0228 bool IsUnit() const {return Equals(One());}
0229
0230 PolynomialMod2 MultiplicativeInverse() const {return IsUnit() ? One() : Zero();}
0231
0232
0233 static PolynomialMod2 CRYPTOPP_API Gcd(const PolynomialMod2 &a, const PolynomialMod2 &n);
0234
0235 PolynomialMod2 InverseMod(const PolynomialMod2 &) const;
0236
0237
0238 static void CRYPTOPP_API Divide(PolynomialMod2 &r, PolynomialMod2 &q, const PolynomialMod2 &a, const PolynomialMod2 &d);
0239
0240
0241
0242
0243
0244 friend std::ostream& operator<<(std::ostream& out, const PolynomialMod2 &a);
0245
0246
0247 private:
0248 friend class GF2NT;
0249 friend class GF2NT233;
0250
0251 SecWordBlock reg;
0252 };
0253
0254
0255 inline bool operator==(const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b)
0256 {return a.Equals(b);}
0257
0258 inline bool operator!=(const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b)
0259 {return !(a==b);}
0260
0261 inline bool operator> (const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b)
0262 {return a.Degree() > b.Degree();}
0263
0264 inline bool operator>=(const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b)
0265 {return a.Degree() >= b.Degree();}
0266
0267 inline bool operator< (const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b)
0268 {return a.Degree() < b.Degree();}
0269
0270 inline bool operator<=(const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b)
0271 {return a.Degree() <= b.Degree();}
0272
0273 inline CryptoPP::PolynomialMod2 operator&(const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b) {return a.And(b);}
0274
0275 inline CryptoPP::PolynomialMod2 operator^(const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b) {return a.Xor(b);}
0276
0277 inline CryptoPP::PolynomialMod2 operator+(const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b) {return a.Plus(b);}
0278
0279 inline CryptoPP::PolynomialMod2 operator-(const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b) {return a.Minus(b);}
0280
0281 inline CryptoPP::PolynomialMod2 operator*(const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b) {return a.Times(b);}
0282
0283 inline CryptoPP::PolynomialMod2 operator/(const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b) {return a.DividedBy(b);}
0284
0285 inline CryptoPP::PolynomialMod2 operator%(const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b) {return a.Modulo(b);}
0286
0287
0288
0289 CRYPTOPP_DLL_TEMPLATE_CLASS AbstractGroup<PolynomialMod2>;
0290 CRYPTOPP_DLL_TEMPLATE_CLASS AbstractRing<PolynomialMod2>;
0291 CRYPTOPP_DLL_TEMPLATE_CLASS AbstractEuclideanDomain<PolynomialMod2>;
0292 CRYPTOPP_DLL_TEMPLATE_CLASS EuclideanDomainOf<PolynomialMod2>;
0293 CRYPTOPP_DLL_TEMPLATE_CLASS QuotientRing<EuclideanDomainOf<PolynomialMod2> >;
0294
0295
0296 class CRYPTOPP_DLL GF2NP : public QuotientRing<EuclideanDomainOf<PolynomialMod2> >
0297 {
0298 public:
0299 GF2NP(const PolynomialMod2 &modulus);
0300
0301 virtual GF2NP * Clone() const {return new GF2NP(*this);}
0302 virtual void DEREncode(BufferedTransformation &bt) const
0303 {CRYPTOPP_UNUSED(bt); CRYPTOPP_ASSERT(false);}
0304
0305 void DEREncodeElement(BufferedTransformation &out, const Element &a) const;
0306 void BERDecodeElement(BufferedTransformation &in, Element &a) const;
0307
0308 bool Equal(const Element &a, const Element &b) const
0309 {CRYPTOPP_ASSERT(a.Degree() < m_modulus.Degree() && b.Degree() < m_modulus.Degree()); return a.Equals(b);}
0310
0311 bool IsUnit(const Element &a) const
0312 {CRYPTOPP_ASSERT(a.Degree() < m_modulus.Degree()); return !!a;}
0313
0314 unsigned int MaxElementBitLength() const
0315 {return m;}
0316
0317 unsigned int MaxElementByteLength() const
0318 {return (unsigned int)BitsToBytes(MaxElementBitLength());}
0319
0320 Element SquareRoot(const Element &a) const;
0321
0322 Element HalfTrace(const Element &a) const;
0323
0324
0325 Element SolveQuadraticEquation(const Element &a) const;
0326
0327 protected:
0328 unsigned int m;
0329 };
0330
0331
0332 class CRYPTOPP_DLL GF2NT : public GF2NP
0333 {
0334 public:
0335
0336 GF2NT(unsigned int t0, unsigned int t1, unsigned int t2);
0337
0338 GF2NP * Clone() const {return new GF2NT(*this);}
0339 void DEREncode(BufferedTransformation &bt) const;
0340
0341 const Element& Multiply(const Element &a, const Element &b) const;
0342
0343 const Element& Square(const Element &a) const
0344 {return Reduced(a.Squared());}
0345
0346 const Element& MultiplicativeInverse(const Element &a) const;
0347
0348 protected:
0349 const Element& Reduced(const Element &a) const;
0350
0351 unsigned int t0, t1;
0352 mutable PolynomialMod2 result;
0353 };
0354
0355
0356
0357
0358 class CRYPTOPP_DLL GF2NT233 : public GF2NT
0359 {
0360 public:
0361
0362 GF2NT233(unsigned int t0, unsigned int t1, unsigned int t2);
0363
0364 GF2NP * Clone() const {return new GF2NT233(*this);}
0365
0366 const Element& Multiply(const Element &a, const Element &b) const;
0367
0368 const Element& Square(const Element &a) const;
0369 };
0370
0371
0372 class CRYPTOPP_DLL GF2NPP : public GF2NP
0373 {
0374 public:
0375
0376 GF2NPP(unsigned int t0, unsigned int t1, unsigned int t2, unsigned int t3, unsigned int t4)
0377 : GF2NP(PolynomialMod2::Pentanomial(t0, t1, t2, t3, t4)), t1(t1), t2(t2), t3(t3) {}
0378
0379 GF2NP * Clone() const {return new GF2NPP(*this);}
0380 void DEREncode(BufferedTransformation &bt) const;
0381
0382 private:
0383 unsigned int t1, t2, t3;
0384 };
0385
0386
0387 CRYPTOPP_DLL GF2NP * CRYPTOPP_API BERDecodeGF2NP(BufferedTransformation &bt);
0388
0389 NAMESPACE_END
0390
0391 #ifndef __BORLANDC__
0392 NAMESPACE_BEGIN(std)
0393 template<> inline void swap(CryptoPP::PolynomialMod2 &a, CryptoPP::PolynomialMod2 &b)
0394 {
0395 a.swap(b);
0396 }
0397 NAMESPACE_END
0398 #endif
0399
0400 #if CRYPTOPP_MSC_VERSION
0401 # pragma warning(pop)
0402 #endif
0403
0404 #endif