Crypto++  5.6.5
Free C++ class library of cryptographic schemes
gf2n.h
Go to the documentation of this file.
1 // gf2n.h - originally written and placed in the public domain by Wei Dai
2 
3 /// \file gf2n.h
4 /// \brief Classes and functions for schemes over GF(2^n)
5 
6 #ifndef CRYPTOPP_GF2N_H
7 #define CRYPTOPP_GF2N_H
8 
9 #include "cryptlib.h"
10 #include "secblock.h"
11 #include "algebra.h"
12 #include "misc.h"
13 #include "asn.h"
14 
15 #include <iosfwd>
16 
17 #if CRYPTOPP_MSC_VERSION
18 # pragma warning(push)
19 # pragma warning(disable: 4231 4275)
20 #endif
21 
22 NAMESPACE_BEGIN(CryptoPP)
23 
24 /// \brief Polynomial with Coefficients in GF(2)
25 /*! \nosubgrouping */
26 class CRYPTOPP_DLL PolynomialMod2
27 {
28 public:
29  /// \name ENUMS, EXCEPTIONS, and TYPEDEFS
30  //@{
31  /// \brief Excpetion thrown when divide by zero is encountered
32  class DivideByZero : public Exception
33  {
34  public:
35  DivideByZero() : Exception(OTHER_ERROR, "PolynomialMod2: division by zero") {}
36  };
37 
38  typedef unsigned int RandomizationParameter;
39  //@}
40 
41  /// \name CREATORS
42  //@{
43  /// \brief Construct the zero polynomial
44  PolynomialMod2();
45  /// Copy construct a PolynomialMod2
46  PolynomialMod2(const PolynomialMod2& t);
47 
48  /// \brief Construct a PolynomialMod2 from a word
49  /// \details value should be encoded with the least significant bit as coefficient to x^0
50  /// and most significant bit as coefficient to x^(WORD_BITS-1)
51  /// bitLength denotes how much memory to allocate initially
52  PolynomialMod2(word value, size_t bitLength=WORD_BITS);
53 
54  /// \brief Construct a PolynomialMod2 from big-endian byte array
55  PolynomialMod2(const byte *encodedPoly, size_t byteCount)
56  {Decode(encodedPoly, byteCount);}
57 
58  /// \brief Construct a PolynomialMod2 from big-endian form stored in a BufferedTransformation
59  PolynomialMod2(BufferedTransformation &encodedPoly, size_t byteCount)
60  {Decode(encodedPoly, byteCount);}
61 
62  /// \brief Create a uniformly distributed random polynomial
63  /// \details Create a random polynomial uniformly distributed over all polynomials with degree less than bitcount
64  PolynomialMod2(RandomNumberGenerator &rng, size_t bitcount)
65  {Randomize(rng, bitcount);}
66 
67  /// \brief Provides x^i
68  /// \returns x^i
69  static PolynomialMod2 CRYPTOPP_API Monomial(size_t i);
70  /// \brief Provides x^t0 + x^t1 + x^t2
71  /// \returns x^t0 + x^t1 + x^t2
72  static PolynomialMod2 CRYPTOPP_API Trinomial(size_t t0, size_t t1, size_t t2);
73  /// \brief Provides x^t0 + x^t1 + x^t2 + x^t3 + x^t4
74  /// \returns x^t0 + x^t1 + x^t2 + x^t3 + x^t4
75  static PolynomialMod2 CRYPTOPP_API Pentanomial(size_t t0, size_t t1, size_t t2, size_t t3, size_t t4);
76  /// \brief Provides x^(n-1) + ... + x + 1
77  /// \returns x^(n-1) + ... + x + 1
78  static PolynomialMod2 CRYPTOPP_API AllOnes(size_t n);
79 
80  /// \brief The Zero polinomial
81  /// \returns the zero polynomial
82  static const PolynomialMod2 & CRYPTOPP_API Zero();
83  /// \brief The One polinomial
84  /// \returns the one polynomial
85  static const PolynomialMod2 & CRYPTOPP_API One();
86  //@}
87 
88  /// \name ENCODE/DECODE
89  //@{
90  /// minimum number of bytes to encode this polynomial
91  /*! MinEncodedSize of 0 is 1 */
92  unsigned int MinEncodedSize() const {return STDMAX(1U, ByteCount());}
93 
94  /// encode in big-endian format
95  /// \details if outputLen < MinEncodedSize, the most significant bytes will be dropped
96  /// if outputLen > MinEncodedSize, the most significant bytes will be padded
97  void Encode(byte *output, size_t outputLen) const;
98  ///
99  void Encode(BufferedTransformation &bt, size_t outputLen) const;
100 
101  ///
102  void Decode(const byte *input, size_t inputLen);
103  ///
104  //* Precondition: bt.MaxRetrievable() >= inputLen
105  void Decode(BufferedTransformation &bt, size_t inputLen);
106 
107  /// encode value as big-endian octet string
108  void DEREncodeAsOctetString(BufferedTransformation &bt, size_t length) const;
109  /// decode value as big-endian octet string
110  void BERDecodeAsOctetString(BufferedTransformation &bt, size_t length);
111  //@}
112 
113  /// \name ACCESSORS
114  //@{
115  /// number of significant bits = Degree() + 1
116  unsigned int BitCount() const;
117  /// number of significant bytes = ceiling(BitCount()/8)
118  unsigned int ByteCount() const;
119  /// number of significant words = ceiling(ByteCount()/sizeof(word))
120  unsigned int WordCount() const;
121 
122  /// return the n-th bit, n=0 being the least significant bit
123  bool GetBit(size_t n) const {return GetCoefficient(n)!=0;}
124  /// return the n-th byte
125  byte GetByte(size_t n) const;
126 
127  /// the zero polynomial will return a degree of -1
128  signed int Degree() const {return (signed int)(BitCount()-1U);}
129  /// degree + 1
130  unsigned int CoefficientCount() const {return BitCount();}
131  /// return coefficient for x^i
132  int GetCoefficient(size_t i) const
133  {return (i/WORD_BITS < reg.size()) ? int(reg[i/WORD_BITS] >> (i % WORD_BITS)) & 1 : 0;}
134  /// return coefficient for x^i
135  int operator[](unsigned int i) const {return GetCoefficient(i);}
136 
137  ///
138  bool IsZero() const {return !*this;}
139  ///
140  bool Equals(const PolynomialMod2 &rhs) const;
141  //@}
142 
143  /// \name MANIPULATORS
144  //@{
145  ///
146  PolynomialMod2& operator=(const PolynomialMod2& t);
147  ///
148  PolynomialMod2& operator&=(const PolynomialMod2& t);
149  ///
150  PolynomialMod2& operator^=(const PolynomialMod2& t);
151  ///
152  PolynomialMod2& operator+=(const PolynomialMod2& t) {return *this ^= t;}
153  ///
154  PolynomialMod2& operator-=(const PolynomialMod2& t) {return *this ^= t;}
155  ///
156  PolynomialMod2& operator*=(const PolynomialMod2& t);
157  ///
158  PolynomialMod2& operator/=(const PolynomialMod2& t);
159  ///
160  PolynomialMod2& operator%=(const PolynomialMod2& t);
161  ///
162  PolynomialMod2& operator<<=(unsigned int);
163  ///
164  PolynomialMod2& operator>>=(unsigned int);
165 
166  ///
167  void Randomize(RandomNumberGenerator &rng, size_t bitcount);
168 
169  ///
170  void SetBit(size_t i, int value = 1);
171  /// set the n-th byte to value
172  void SetByte(size_t n, byte value);
173 
174  ///
175  void SetCoefficient(size_t i, int value) {SetBit(i, value);}
176 
177  ///
178  void swap(PolynomialMod2 &a) {reg.swap(a.reg);}
179  //@}
180 
181  /// \name UNARY OPERATORS
182  //@{
183  ///
184  bool operator!() const;
185  ///
186  PolynomialMod2 operator+() const {return *this;}
187  ///
188  PolynomialMod2 operator-() const {return *this;}
189  //@}
190 
191  /// \name BINARY OPERATORS
192  //@{
193  ///
194  PolynomialMod2 And(const PolynomialMod2 &b) const;
195  ///
196  PolynomialMod2 Xor(const PolynomialMod2 &b) const;
197  ///
198  PolynomialMod2 Plus(const PolynomialMod2 &b) const {return Xor(b);}
199  ///
200  PolynomialMod2 Minus(const PolynomialMod2 &b) const {return Xor(b);}
201  ///
202  PolynomialMod2 Times(const PolynomialMod2 &b) const;
203  ///
204  PolynomialMod2 DividedBy(const PolynomialMod2 &b) const;
205  ///
206  PolynomialMod2 Modulo(const PolynomialMod2 &b) const;
207 
208  ///
209  PolynomialMod2 operator>>(unsigned int n) const;
210  ///
211  PolynomialMod2 operator<<(unsigned int n) const;
212  //@}
213 
214  /// \name OTHER ARITHMETIC FUNCTIONS
215  //@{
216  /// sum modulo 2 of all coefficients
217  unsigned int Parity() const;
218 
219  /// check for irreducibility
220  bool IsIrreducible() const;
221 
222  /// is always zero since we're working modulo 2
223  PolynomialMod2 Doubled() const {return Zero();}
224  ///
225  PolynomialMod2 Squared() const;
226 
227  /// only 1 is a unit
228  bool IsUnit() const {return Equals(One());}
229  /// return inverse if *this is a unit, otherwise return 0
230  PolynomialMod2 MultiplicativeInverse() const {return IsUnit() ? One() : Zero();}
231 
232  /// greatest common divisor
233  static PolynomialMod2 CRYPTOPP_API Gcd(const PolynomialMod2 &a, const PolynomialMod2 &n);
234  /// calculate multiplicative inverse of *this mod n
235  PolynomialMod2 InverseMod(const PolynomialMod2 &) const;
236 
237  /// calculate r and q such that (a == d*q + r) && (deg(r) < deg(d))
238  static void CRYPTOPP_API Divide(PolynomialMod2 &r, PolynomialMod2 &q, const PolynomialMod2 &a, const PolynomialMod2 &d);
239  //@}
240 
241  /// \name INPUT/OUTPUT
242  //@{
243  ///
244  friend std::ostream& operator<<(std::ostream& out, const PolynomialMod2 &a);
245  //@}
246 
247 private:
248  friend class GF2NT;
249 
250  SecWordBlock reg;
251 };
252 
253 ///
254 inline bool operator==(const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b)
255 {return a.Equals(b);}
256 ///
257 inline bool operator!=(const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b)
258 {return !(a==b);}
259 /// compares degree
260 inline bool operator> (const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b)
261 {return a.Degree() > b.Degree();}
262 /// compares degree
263 inline bool operator>=(const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b)
264 {return a.Degree() >= b.Degree();}
265 /// compares degree
266 inline bool operator< (const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b)
267 {return a.Degree() < b.Degree();}
268 /// compares degree
269 inline bool operator<=(const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b)
270 {return a.Degree() <= b.Degree();}
271 ///
272 inline CryptoPP::PolynomialMod2 operator&(const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b) {return a.And(b);}
273 ///
274 inline CryptoPP::PolynomialMod2 operator^(const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b) {return a.Xor(b);}
275 ///
276 inline CryptoPP::PolynomialMod2 operator+(const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b) {return a.Plus(b);}
277 ///
278 inline CryptoPP::PolynomialMod2 operator-(const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b) {return a.Minus(b);}
279 ///
280 inline CryptoPP::PolynomialMod2 operator*(const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b) {return a.Times(b);}
281 ///
282 inline CryptoPP::PolynomialMod2 operator/(const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b) {return a.DividedBy(b);}
283 ///
284 inline CryptoPP::PolynomialMod2 operator%(const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b) {return a.Modulo(b);}
285 
286 // CodeWarrior 8 workaround: put these template instantiations after overloaded operator declarations,
287 // but before the use of QuotientRing<EuclideanDomainOf<PolynomialMod2> > for VC .NET 2003
288 CRYPTOPP_DLL_TEMPLATE_CLASS AbstractGroup<PolynomialMod2>;
289 CRYPTOPP_DLL_TEMPLATE_CLASS AbstractRing<PolynomialMod2>;
290 CRYPTOPP_DLL_TEMPLATE_CLASS AbstractEuclideanDomain<PolynomialMod2>;
291 CRYPTOPP_DLL_TEMPLATE_CLASS EuclideanDomainOf<PolynomialMod2>;
292 CRYPTOPP_DLL_TEMPLATE_CLASS QuotientRing<EuclideanDomainOf<PolynomialMod2> >;
293 
294 /// \brief GF(2^n) with Polynomial Basis
295 class CRYPTOPP_DLL GF2NP : public QuotientRing<EuclideanDomainOf<PolynomialMod2> >
296 {
297 public:
298  GF2NP(const PolynomialMod2 &modulus);
299 
300  virtual GF2NP * Clone() const {return new GF2NP(*this);}
301  virtual void DEREncode(BufferedTransformation &bt) const
302  {CRYPTOPP_UNUSED(bt); CRYPTOPP_ASSERT(false);} // no ASN.1 syntax yet for general polynomial basis
303 
304  void DEREncodeElement(BufferedTransformation &out, const Element &a) const;
305  void BERDecodeElement(BufferedTransformation &in, Element &a) const;
306 
307  bool Equal(const Element &a, const Element &b) const
308  {CRYPTOPP_ASSERT(a.Degree() < m_modulus.Degree() && b.Degree() < m_modulus.Degree()); return a.Equals(b);}
309 
310  bool IsUnit(const Element &a) const
311  {CRYPTOPP_ASSERT(a.Degree() < m_modulus.Degree()); return !!a;}
312 
313  unsigned int MaxElementBitLength() const
314  {return m;}
315 
316  unsigned int MaxElementByteLength() const
317  {return (unsigned int)BitsToBytes(MaxElementBitLength());}
318 
319  Element SquareRoot(const Element &a) const;
320 
321  Element HalfTrace(const Element &a) const;
322 
323  // returns z such that z^2 + z == a
324  Element SolveQuadraticEquation(const Element &a) const;
325 
326 protected:
327  unsigned int m;
328 };
329 
330 /// \brief GF(2^n) with Trinomial Basis
331 class CRYPTOPP_DLL GF2NT : public GF2NP
332 {
333 public:
334  // polynomial modulus = x^t0 + x^t1 + x^t2, t0 > t1 > t2
335  GF2NT(unsigned int t0, unsigned int t1, unsigned int t2);
336 
337  GF2NP * Clone() const {return new GF2NT(*this);}
338  void DEREncode(BufferedTransformation &bt) const;
339 
340  const Element& Multiply(const Element &a, const Element &b) const;
341 
342  const Element& Square(const Element &a) const
343  {return Reduced(a.Squared());}
344 
345  const Element& MultiplicativeInverse(const Element &a) const;
346 
347 private:
348  const Element& Reduced(const Element &a) const;
349 
350  unsigned int t0, t1;
351  mutable PolynomialMod2 result;
352 };
353 
354 /// \brief GF(2^n) with Pentanomial Basis
355 class CRYPTOPP_DLL GF2NPP : public GF2NP
356 {
357 public:
358  // polynomial modulus = x^t0 + x^t1 + x^t2 + x^t3 + x^t4, t0 > t1 > t2 > t3 > t4
359  GF2NPP(unsigned int t0, unsigned int t1, unsigned int t2, unsigned int t3, unsigned int t4)
360  : GF2NP(PolynomialMod2::Pentanomial(t0, t1, t2, t3, t4)), t0(t0), t1(t1), t2(t2), t3(t3) {}
361 
362  GF2NP * Clone() const {return new GF2NPP(*this);}
363  void DEREncode(BufferedTransformation &bt) const;
364 
365 private:
366  unsigned int t0, t1, t2, t3;
367 };
368 
369 // construct new GF2NP from the ASN.1 sequence Characteristic-two
370 CRYPTOPP_DLL GF2NP * CRYPTOPP_API BERDecodeGF2NP(BufferedTransformation &bt);
371 
372 NAMESPACE_END
373 
374 #ifndef __BORLANDC__
375 NAMESPACE_BEGIN(std)
376 template<> inline void swap(CryptoPP::PolynomialMod2 &a, CryptoPP::PolynomialMod2 &b)
377 {
378  a.swap(b);
379 }
380 NAMESPACE_END
381 #endif
382 
383 #if CRYPTOPP_MSC_VERSION
384 # pragma warning(pop)
385 #endif
386 
387 #endif
Base class for all exceptions thrown by the library.
Definition: cryptlib.h:156
bool operator>=(const ::PolynomialMod2 &a, const ::PolynomialMod2 &b)
compares degree
Definition: gf2n.h:263
bool operator>(const ::PolynomialMod2 &a, const ::PolynomialMod2 &b)
compares degree
Definition: gf2n.h:260
bool Equal(const Element &a, const Element &b) const
Compare two elements for equality.
Definition: gf2n.h:307
inline ::Integer operator*(const ::Integer &a, const ::Integer &b)
Multiplication.
Definition: integer.h:671
Utility functions for the Crypto++ library.
int GetCoefficient(size_t i) const
return coefficient for x^i
Definition: gf2n.h:132
size_t BitsToBytes(size_t bitCount)
Returns the number of 8-bit bytes or octets required for the specified number of bits.
Definition: misc.h:785
bool IsUnit() const
only 1 is a unit
Definition: gf2n.h:228
GF(2^n) with Trinomial Basis.
Definition: gf2n.h:331
Abstract base classes that provide a uniform interface to this library.
bool GetBit(size_t n) const
return the n-th bit, n=0 being the least significant bit
Definition: gf2n.h:123
STL namespace.
Interface for random number generators.
Definition: cryptlib.h:1327
const Element & Square(const Element &a) const
Square an element in the group.
Definition: gf2n.h:342
Classes for performing mathematics over different fields.
Interface for buffered transformations.
Definition: cryptlib.h:1472
Quotient ring.
Definition: algebra.h:386
bool operator==(const OID &lhs, const OID &rhs)
Compare two OIDs for equality.
Polynomial with Coefficients in GF(2)
Definition: gf2n.h:26
unsigned int CoefficientCount() const
degree + 1
Definition: gf2n.h:130
Excpetion thrown when divide by zero is encountered.
Definition: gf2n.h:32
PolynomialMod2(BufferedTransformation &encodedPoly, size_t byteCount)
Construct a PolynomialMod2 from big-endian form stored in a BufferedTransformation.
Definition: gf2n.h:59
Classes and functions for secure memory allocations.
bool operator!=(const OID &lhs, const OID &rhs)
Compare two OIDs for inequality.
inline ::Integer operator-(const ::Integer &a, const ::Integer &b)
Subtraction.
Definition: integer.h:668
inline ::Integer operator &(const ::Integer &a, const ::Integer &b)
Bitwise AND.
Definition: integer.h:695
OID operator+(const OID &lhs, unsigned long rhs)
Append a value to an OID.
unsigned int MinEncodedSize() const
minimum number of bytes to encode this polynomial
Definition: gf2n.h:92
PolynomialMod2(const byte *encodedPoly, size_t byteCount)
Construct a PolynomialMod2 from big-endian byte array.
Definition: gf2n.h:55
bool operator<(const ::PolynomialMod2 &a, const ::PolynomialMod2 &b)
compares degree
Definition: gf2n.h:266
unsigned int Parity(T value)
Returns the parity of a value.
Definition: misc.h:654
PolynomialMod2 Doubled() const
is always zero since we&#39;re working modulo 2
Definition: gf2n.h:223
#define CRYPTOPP_ASSERT(exp)
Debugging and diagnostic assertion.
Definition: trap.h:60
inline ::Integer operator^(const ::Integer &a, const ::Integer &b)
Bitwise XOR.
Definition: integer.h:723
Classes and functions for working with ANS.1 objects.
bool IsUnit(const Element &a) const
Determines whether an element is a unit in the group.
Definition: gf2n.h:310
GF(2^n) with Pentanomial Basis.
Definition: gf2n.h:355
GF(2^n) with Polynomial Basis.
Definition: gf2n.h:295
PolynomialMod2 MultiplicativeInverse() const
return inverse if *this is a unit, otherwise return 0
Definition: gf2n.h:230
int operator[](unsigned int i) const
return coefficient for x^i
Definition: gf2n.h:135
PolynomialMod2(RandomNumberGenerator &rng, size_t bitcount)
Create a uniformly distributed random polynomial.
Definition: gf2n.h:64
const T & STDMAX(const T &a, const T &b)
Replacement function for std::max.
Definition: misc.h:514
signed int Degree() const
the zero polynomial will return a degree of -1
Definition: gf2n.h:128
Crypto++ library namespace.
unsigned int GetByte(ByteOrder order, T value, unsigned int index)
Gets a byte from a value.
Definition: misc.h:1822
static PolynomialMod2 Pentanomial(size_t t0, size_t t1, size_t t2, size_t t3, size_t t4)
Provides x^t0 + x^t1 + x^t2 + x^t3 + x^t4.
Definition: gf2n.cpp:114
SecBlock<word> typedef.
Definition: secblock.h:824
bool operator<=(const ::PolynomialMod2 &a, const ::PolynomialMod2 &b)
compares degree
Definition: gf2n.h:269