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