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