Crypto++ 8.9
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
22NAMESPACE_BEGIN(CryptoPP)
23
24/// \brief Polynomial with Coefficients in GF(2)
25/*! \nosubgrouping */
26class CRYPTOPP_DLL PolynomialMod2
27{
28public:
29 /// \name ENUMS, EXCEPTIONS, and TYPEDEFS
30 //@{
31 /// \brief Exception 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
45 /// Copy construct a PolynomialMod2
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
65 {Randomize(rng, bitcount);}
66
67 /// \brief Provides x^i
68 /// \return x^i
70 /// \brief Provides x^t0 + x^t1 + x^t2
71 /// \return x^t0 + x^t1 + x^t2
72 /// \pre The coefficients should be provided in descending order. That is, <pre>t0 > t1 > t2<pre>.
73 static PolynomialMod2 CRYPTOPP_API Trinomial(size_t t0, size_t t1, size_t t2);
74 /// \brief Provides x^t0 + x^t1 + x^t2 + x^t3 + x^t4
75 /// \return x^t0 + x^t1 + x^t2 + x^t3 + x^t4
76 /// \pre The coefficients should be provided in descending order. That is, <pre>t0 > t1 > t2 > t3 > t4<pre>.
77 static PolynomialMod2 CRYPTOPP_API Pentanomial(size_t t0, size_t t1, size_t t2, size_t t3, size_t t4);
78 /// \brief Provides x^(n-1) + ... + x + 1
79 /// \return x^(n-1) + ... + x + 1
81
82 /// \brief The Zero polinomial
83 /// \return the zero polynomial
85 /// \brief The One polinomial
86 /// \return the one polynomial
88 //@}
89
90 /// \name ENCODE/DECODE
91 //@{
92 /// minimum number of bytes to encode this polynomial
93 /*! MinEncodedSize of 0 is 1 */
94 unsigned int MinEncodedSize() const {return STDMAX(1U, ByteCount());}
95
96 /// encode in big-endian format
97 /// \details if outputLen < MinEncodedSize, the most significant bytes will be dropped
98 /// if outputLen > MinEncodedSize, the most significant bytes will be padded
99 void Encode(byte *output, size_t outputLen) const;
100 ///
101 void Encode(BufferedTransformation &bt, size_t outputLen) const;
102
103 ///
104 void Decode(const byte *input, size_t inputLen);
105 ///
106 //* Precondition: bt.MaxRetrievable() >= inputLen
107 void Decode(BufferedTransformation &bt, size_t inputLen);
108
109 /// encode value as big-endian octet string
110 void DEREncodeAsOctetString(BufferedTransformation &bt, size_t length) const;
111 /// decode value as big-endian octet string
113 //@}
114
115 /// \name ACCESSORS
116 //@{
117 /// number of significant bits = Degree() + 1
118 unsigned int BitCount() const;
119 /// number of significant bytes = ceiling(BitCount()/8)
120 unsigned int ByteCount() const;
121 /// number of significant words = ceiling(ByteCount()/sizeof(word))
122 unsigned int WordCount() const;
123
124 /// return the n-th bit, n=0 being the least significant bit
125 bool GetBit(size_t n) const {return GetCoefficient(n)!=0;}
126 /// return the n-th byte
127 byte GetByte(size_t n) const;
128
129 /// the zero polynomial will return a degree of -1
130 signed int Degree() const {return (signed int)(BitCount()-1U);}
131 /// degree + 1
132 unsigned int CoefficientCount() const {return BitCount();}
133 /// return coefficient for x^i
134 int GetCoefficient(size_t i) const
135 {return (i/WORD_BITS < reg.size()) ? int(reg[i/WORD_BITS] >> (i % WORD_BITS)) & 1 : 0;}
136 /// return coefficient for x^i
137 int operator[](unsigned int i) const {return GetCoefficient(i);}
138
139 ///
140 bool IsZero() const {return !*this;}
141 ///
142 bool Equals(const PolynomialMod2 &rhs) const;
143 //@}
144
145 /// \name MANIPULATORS
146 //@{
147 ///
148 PolynomialMod2& operator=(const PolynomialMod2& t);
149 ///
150 PolynomialMod2& operator&=(const PolynomialMod2& t);
151 ///
152 PolynomialMod2& operator^=(const PolynomialMod2& t);
153 ///
154 PolynomialMod2& operator+=(const PolynomialMod2& t) {return *this ^= t;}
155 ///
156 PolynomialMod2& operator-=(const PolynomialMod2& t) {return *this ^= t;}
157 ///
158 PolynomialMod2& operator*=(const PolynomialMod2& t);
159 ///
160 PolynomialMod2& operator/=(const PolynomialMod2& t);
161 ///
162 PolynomialMod2& operator%=(const PolynomialMod2& t);
163 ///
164 PolynomialMod2& operator<<=(unsigned int);
165 ///
166 PolynomialMod2& operator>>=(unsigned int);
167
168 ///
169 void Randomize(RandomNumberGenerator &rng, size_t bitcount);
170
171 ///
172 void SetBit(size_t i, int value = 1);
173 /// set the n-th byte to value
174 void SetByte(size_t n, byte value);
175
176 ///
177 void SetCoefficient(size_t i, int value) {SetBit(i, value);}
178
179 ///
180 void swap(PolynomialMod2 &a) {reg.swap(a.reg);}
181 //@}
182
183 /// \name UNARY OPERATORS
184 //@{
185 ///
186 bool operator!() const;
187 ///
188 PolynomialMod2 operator+() const {return *this;}
189 ///
190 PolynomialMod2 operator-() const {return *this;}
191 //@}
192
193 /// \name BINARY OPERATORS
194 //@{
195 ///
196 PolynomialMod2 And(const PolynomialMod2 &b) const;
197 ///
198 PolynomialMod2 Xor(const PolynomialMod2 &b) const;
199 ///
200 PolynomialMod2 Plus(const PolynomialMod2 &b) const {return Xor(b);}
201 ///
202 PolynomialMod2 Minus(const PolynomialMod2 &b) const {return Xor(b);}
203 ///
204 PolynomialMod2 Times(const PolynomialMod2 &b) const;
205 ///
206 PolynomialMod2 DividedBy(const PolynomialMod2 &b) const;
207 ///
208 PolynomialMod2 Modulo(const PolynomialMod2 &b) const;
209
210 ///
211 PolynomialMod2 operator>>(unsigned int n) const;
212 ///
213 PolynomialMod2 operator<<(unsigned int n) const;
214 //@}
215
216 /// \name OTHER ARITHMETIC FUNCTIONS
217 //@{
218 /// sum modulo 2 of all coefficients
219 unsigned int Parity() const;
220
221 /// check for irreducibility
222 bool IsIrreducible() const;
223
224 /// is always zero since we're working modulo 2
225 PolynomialMod2 Doubled() const {return Zero();}
226 ///
227 PolynomialMod2 Squared() const;
228
229 /// only 1 is a unit
230 bool IsUnit() const {return Equals(One());}
231 /// return inverse if *this is a unit, otherwise return 0
232 PolynomialMod2 MultiplicativeInverse() const {return IsUnit() ? One() : Zero();}
233
234 /// greatest common divisor
236 /// calculate multiplicative inverse of *this mod n
238
239 /// calculate r and q such that (a == d*q + r) && (deg(r) < deg(d))
241 //@}
242
243 /// \name INPUT/OUTPUT
244 //@{
245 ///
246 friend std::ostream& operator<<(std::ostream& out, const PolynomialMod2 &a);
247 //@}
248
249private:
250 friend class GF2NT;
251 friend class GF2NT233;
252
253 SecWordBlock reg;
254};
255
256///
257inline bool operator==(const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b)
258{return a.Equals(b);}
259///
260inline bool operator!=(const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b)
261{return !(a==b);}
262/// compares degree
263inline bool operator> (const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b)
264{return a.Degree() > b.Degree();}
265/// compares degree
266inline bool operator>=(const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b)
267{return a.Degree() >= b.Degree();}
268/// compares degree
269inline bool operator< (const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b)
270{return a.Degree() < b.Degree();}
271/// compares degree
272inline bool operator<=(const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b)
273{return a.Degree() <= b.Degree();}
274///
275inline CryptoPP::PolynomialMod2 operator&(const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b) {return a.And(b);}
276///
277inline CryptoPP::PolynomialMod2 operator^(const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b) {return a.Xor(b);}
278///
279inline CryptoPP::PolynomialMod2 operator+(const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b) {return a.Plus(b);}
280///
281inline CryptoPP::PolynomialMod2 operator-(const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b) {return a.Minus(b);}
282///
283inline CryptoPP::PolynomialMod2 operator*(const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b) {return a.Times(b);}
284///
285inline CryptoPP::PolynomialMod2 operator/(const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b) {return a.DividedBy(b);}
286///
287inline CryptoPP::PolynomialMod2 operator%(const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b) {return a.Modulo(b);}
288
289// CodeWarrior 8 workaround: put these template instantiations after overloaded operator declarations,
290// but before the use of QuotientRing<EuclideanDomainOf<PolynomialMod2> > for VC .NET 2003
296
297/// \brief GF(2^n) with Polynomial Basis
298class CRYPTOPP_DLL GF2NP : public QuotientRing<EuclideanDomainOf<PolynomialMod2> >
299{
300public:
301 GF2NP(const PolynomialMod2 &modulus);
302
303 virtual GF2NP * Clone() const {return new GF2NP(*this);}
304 virtual void DEREncode(BufferedTransformation &bt) const
305 {CRYPTOPP_UNUSED(bt); CRYPTOPP_ASSERT(false);} // no ASN.1 syntax yet for general polynomial basis
306
307 void DEREncodeElement(BufferedTransformation &out, const Element &a) const;
308 void BERDecodeElement(BufferedTransformation &in, Element &a) const;
309
310 bool Equal(const Element &a, const Element &b) const
311 {CRYPTOPP_ASSERT(a.Degree() < m_modulus.Degree() && b.Degree() < m_modulus.Degree()); return a.Equals(b);}
312
313 bool IsUnit(const Element &a) const
314 {CRYPTOPP_ASSERT(a.Degree() < m_modulus.Degree()); return !!a;}
315
316 unsigned int MaxElementBitLength() const
317 {return m;}
318
319 unsigned int MaxElementByteLength() const
320 {return (unsigned int)BitsToBytes(MaxElementBitLength());}
321
322 Element SquareRoot(const Element &a) const;
323
324 Element HalfTrace(const Element &a) const;
325
326 // returns z such that z^2 + z == a
327 Element SolveQuadraticEquation(const Element &a) const;
328
329protected:
330 unsigned int m;
331};
332
333/// \brief GF(2^n) with Trinomial Basis
334class CRYPTOPP_DLL GF2NT : public GF2NP
335{
336public:
337 // polynomial modulus = x^t0 + x^t1 + x^t2, t0 > t1 > t2
338 GF2NT(unsigned int t0, unsigned int t1, unsigned int t2);
339
340 GF2NP * Clone() const {return new GF2NT(*this);}
341 void DEREncode(BufferedTransformation &bt) const;
342
343 const Element& Multiply(const Element &a, const Element &b) const;
344
345 const Element& Square(const Element &a) const
346 {return Reduced(a.Squared());}
347
348 const Element& MultiplicativeInverse(const Element &a) const;
349
350protected:
351 const Element& Reduced(const Element &a) const;
352
353 unsigned int t0, t1;
354 mutable PolynomialMod2 result;
355};
356
357/// \brief GF(2^n) for b233 and k233
358/// \details GF2NT233 is a specialization of GF2NT that provides Multiply()
359/// and Square() operations when carryless multiplies is available.
360class CRYPTOPP_DLL GF2NT233 : public GF2NT
361{
362public:
363 // polynomial modulus = x^t0 + x^t1 + x^t2, t0 > t1 > t2
364 GF2NT233(unsigned int t0, unsigned int t1, unsigned int t2);
365
366 GF2NP * Clone() const {return new GF2NT233(*this);}
367
368 const Element& Multiply(const Element &a, const Element &b) const;
369
370 const Element& Square(const Element &a) const;
371};
372
373/// \brief GF(2^n) with Pentanomial Basis
374class CRYPTOPP_DLL GF2NPP : public GF2NP
375{
376public:
377 // polynomial modulus = x^t0 + x^t1 + x^t2 + x^t3 + x^t4, t0 > t1 > t2 > t3 > t4
378 GF2NPP(unsigned int t0, unsigned int t1, unsigned int t2, unsigned int t3, unsigned int t4)
379 : GF2NP(PolynomialMod2::Pentanomial(t0, t1, t2, t3, t4)), t1(t1), t2(t2), t3(t3) {}
380
381 GF2NP * Clone() const {return new GF2NPP(*this);}
382 void DEREncode(BufferedTransformation &bt) const;
383
384private:
385 unsigned int t1, t2, t3;
386};
387
388// construct new GF2NP from the ASN.1 sequence Characteristic-two
389CRYPTOPP_DLL GF2NP * CRYPTOPP_API BERDecodeGF2NP(BufferedTransformation &bt);
390
391NAMESPACE_END
392
393#ifndef __BORLANDC__
394NAMESPACE_BEGIN(std)
395template<> inline void swap(CryptoPP::PolynomialMod2 &a, CryptoPP::PolynomialMod2 &b)
396{
397 a.swap(b);
398}
399NAMESPACE_END
400#endif
401
402#if CRYPTOPP_MSC_VERSION
403# pragma warning(pop)
404#endif
405
406#endif
Classes for performing mathematics over different fields.
Classes and functions for working with ANS.1 objects.
std::ostream & operator<<(std::ostream &out, const OID &oid)
Print a OID value.
OID operator+(const OID &lhs, unsigned long rhs)
Append a value to an OID.
bool operator==(const OID &lhs, const OID &rhs)
Compare two OIDs for equality.
bool operator!=(const OID &lhs, const OID &rhs)
Compare two OIDs for inequality.
Abstract Euclidean domain.
Definition algebra.h:277
Abstract group.
Definition algebra.h:27
Abstract ring.
Definition algebra.h:119
Interface for buffered transformations.
Definition cryptlib.h:1657
Euclidean domain.
Definition algebra.h:316
Base class for all exceptions thrown by the library.
Definition cryptlib.h:164
GF(2^n) with Polynomial Basis.
Definition gf2n.h:299
GF(2^n) with Pentanomial Basis.
Definition gf2n.h:375
GF(2^n) for b233 and k233.
Definition gf2n.h:361
GF(2^n) with Trinomial Basis.
Definition gf2n.h:335
Exception thrown when divide by zero is encountered.
Definition gf2n.h:33
Polynomial with Coefficients in GF(2)
Definition gf2n.h:27
unsigned int MinEncodedSize() const
minimum number of bytes to encode this polynomial
Definition gf2n.h:94
void DEREncodeAsOctetString(BufferedTransformation &bt, size_t length) const
encode value as big-endian octet string
PolynomialMod2 MultiplicativeInverse() const
return inverse if *this is a unit, otherwise return 0
Definition gf2n.h:232
void Encode(byte *output, size_t outputLen) const
encode in big-endian format
static PolynomialMod2 Monomial(size_t i)
Provides x^i.
signed int Degree() const
the zero polynomial will return a degree of -1
Definition gf2n.h:130
static const PolynomialMod2 & One()
The One polinomial.
bool IsIrreducible() const
check for irreducibility
PolynomialMod2(RandomNumberGenerator &rng, size_t bitcount)
Create a uniformly distributed random polynomial.
Definition gf2n.h:64
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.
bool IsUnit() const
only 1 is a unit
Definition gf2n.h:230
PolynomialMod2(word value, size_t bitLength=WORD_BITS)
Construct a PolynomialMod2 from a word.
PolynomialMod2 Doubled() const
is always zero since we're working modulo 2
Definition gf2n.h:225
PolynomialMod2(const PolynomialMod2 &t)
Copy construct a PolynomialMod2.
void BERDecodeAsOctetString(BufferedTransformation &bt, size_t length)
decode value as big-endian octet string
byte GetByte(size_t n) const
return the n-th byte
unsigned int BitCount() const
number of significant bits = Degree() + 1
unsigned int WordCount() const
number of significant words = ceiling(ByteCount()/sizeof(word))
static PolynomialMod2 AllOnes(size_t n)
Provides x^(n-1) + ... + x + 1.
static PolynomialMod2 Trinomial(size_t t0, size_t t1, size_t t2)
Provides x^t0 + x^t1 + x^t2.
unsigned int CoefficientCount() const
degree + 1
Definition gf2n.h:132
PolynomialMod2 InverseMod(const PolynomialMod2 &) const
calculate multiplicative inverse of *this mod n
PolynomialMod2(BufferedTransformation &encodedPoly, size_t byteCount)
Construct a PolynomialMod2 from big-endian form stored in a BufferedTransformation.
Definition gf2n.h:59
int operator[](unsigned int i) const
return coefficient for x^i
Definition gf2n.h:137
unsigned int Parity() const
sum modulo 2 of all coefficients
PolynomialMod2()
Construct the zero polynomial.
static const PolynomialMod2 & Zero()
The Zero polinomial.
unsigned int ByteCount() const
number of significant bytes = ceiling(BitCount()/8)
static void Divide(PolynomialMod2 &r, PolynomialMod2 &q, const PolynomialMod2 &a, const PolynomialMod2 &d)
calculate r and q such that (a == d*q + r) && (deg(r) < deg(d))
static PolynomialMod2 Gcd(const PolynomialMod2 &a, const PolynomialMod2 &n)
greatest common divisor
PolynomialMod2(const byte *encodedPoly, size_t byteCount)
Construct a PolynomialMod2 from big-endian byte array.
Definition gf2n.h:55
void SetByte(size_t n, byte value)
set the n-th byte to value
int GetCoefficient(size_t i) const
return coefficient for x^i
Definition gf2n.h:134
bool GetBit(size_t n) const
return the n-th bit, n=0 being the least significant bit
Definition gf2n.h:125
Quotient ring.
Definition algebra.h:387
Interface for random number generators.
Definition cryptlib.h:1440
SecBlock typedef.
Definition secblock.h:1228
Square block cipher.
Definition square.h:25
#define CRYPTOPP_API
Win32 calling convention.
Definition config_dll.h:119
#define CRYPTOPP_DLL_TEMPLATE_CLASS
Instantiate templates in a dynamic library.
Definition config_dll.h:72
word64 word
Full word used for multiprecision integer arithmetic.
Definition config_int.h:192
const unsigned int WORD_BITS
Size of a platform word in bits.
Definition config_int.h:260
Abstract base classes that provide a uniform interface to this library.
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:266
bool operator<(const ::PolynomialMod2 &a, const ::PolynomialMod2 &b)
compares degree
Definition gf2n.h:269
bool operator<=(const ::PolynomialMod2 &a, const ::PolynomialMod2 &b)
compares degree
Definition gf2n.h:272
Utility functions for the Crypto++ library.
const T & STDMAX(const T &a, const T &b)
Replacement function for std::max.
Definition misc.h:668
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:1143
Crypto++ library namespace.
Classes and functions for secure memory allocations.
#define CRYPTOPP_ASSERT(exp)
Debugging and diagnostic assertion.
Definition trap.h:68