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