Crypto++ 8.2 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 /// \return x^i
69 static PolynomialMod2 CRYPTOPP_API Monomial(size_t i);
70 /// \brief Provides x^t0 + x^t1 + x^t2
71 /// \return 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 /// \return 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 /// \return x^(n-1) + ... + x + 1
78 static PolynomialMod2 CRYPTOPP_API AllOnes(size_t n);
79
80 /// \brief The Zero polinomial
81 /// \return the zero polynomial
82 static const PolynomialMod2 & CRYPTOPP_API Zero();
83 /// \brief The One polinomial
84 /// \return 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 friend class GF2NT233;
250
251 SecWordBlock reg;
252 };
253
254 ///
255 inline bool operator==(const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b)
256 {return a.Equals(b);}
257 ///
258 inline bool operator!=(const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b)
259 {return !(a==b);}
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 /// compares degree
267 inline bool operator< (const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b)
268 {return a.Degree() < b.Degree();}
269 /// compares degree
270 inline bool operator<=(const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b)
271 {return a.Degree() <= b.Degree();}
272 ///
273 inline CryptoPP::PolynomialMod2 operator&(const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b) {return a.And(b);}
274 ///
275 inline CryptoPP::PolynomialMod2 operator^(const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b) {return a.Xor(b);}
276 ///
277 inline CryptoPP::PolynomialMod2 operator+(const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b) {return a.Plus(b);}
278 ///
279 inline CryptoPP::PolynomialMod2 operator-(const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b) {return a.Minus(b);}
280 ///
281 inline CryptoPP::PolynomialMod2 operator*(const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b) {return a.Times(b);}
282 ///
283 inline CryptoPP::PolynomialMod2 operator/(const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b) {return a.DividedBy(b);}
284 ///
285 inline CryptoPP::PolynomialMod2 operator%(const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b) {return a.Modulo(b);}
286
287 // CodeWarrior 8 workaround: put these template instantiations after overloaded operator declarations,
288 // but before the use of QuotientRing<EuclideanDomainOf<PolynomialMod2> > for VC .NET 2003
289 CRYPTOPP_DLL_TEMPLATE_CLASS AbstractGroup<PolynomialMod2>;
290 CRYPTOPP_DLL_TEMPLATE_CLASS AbstractRing<PolynomialMod2>;
291 CRYPTOPP_DLL_TEMPLATE_CLASS AbstractEuclideanDomain<PolynomialMod2>;
292 CRYPTOPP_DLL_TEMPLATE_CLASS EuclideanDomainOf<PolynomialMod2>;
293 CRYPTOPP_DLL_TEMPLATE_CLASS QuotientRing<EuclideanDomainOf<PolynomialMod2> >;
294
295 /// \brief GF(2^n) with Polynomial Basis
296 class CRYPTOPP_DLL GF2NP : public QuotientRing<EuclideanDomainOf<PolynomialMod2> >
297 {
298 public:
299 GF2NP(const PolynomialMod2 &modulus);
300
301 virtual GF2NP * Clone() const {return new GF2NP(*this);}
302 virtual void DEREncode(BufferedTransformation &bt) const
303 {CRYPTOPP_UNUSED(bt); CRYPTOPP_ASSERT(false);} // no ASN.1 syntax yet for general polynomial basis
304
305 void DEREncodeElement(BufferedTransformation &out, const Element &a) const;
306 void BERDecodeElement(BufferedTransformation &in, Element &a) const;
307
308 bool Equal(const Element &a, const Element &b) const
309 {CRYPTOPP_ASSERT(a.Degree() < m_modulus.Degree() && b.Degree() < m_modulus.Degree()); return a.Equals(b);}
310
311 bool IsUnit(const Element &a) const
312 {CRYPTOPP_ASSERT(a.Degree() < m_modulus.Degree()); return !!a;}
313
314 unsigned int MaxElementBitLength() const
315 {return m;}
316
317 unsigned int MaxElementByteLength() const
318 {return (unsigned int)BitsToBytes(MaxElementBitLength());}
319
320 Element SquareRoot(const Element &a) const;
321
322 Element HalfTrace(const Element &a) const;
323
324 // returns z such that z^2 + z == a
325 Element SolveQuadraticEquation(const Element &a) const;
326
327 protected:
328 unsigned int m;
329 };
330
331 /// \brief GF(2^n) with Trinomial Basis
332 class CRYPTOPP_DLL GF2NT : public GF2NP
333 {
334 public:
335 // polynomial modulus = x^t0 + x^t1 + x^t2, t0 > t1 > t2
336 GF2NT(unsigned int t0, unsigned int t1, unsigned int t2);
337
338 GF2NP * Clone() const {return new GF2NT(*this);}
339 void DEREncode(BufferedTransformation &bt) const;
340
341 const Element& Multiply(const Element &a, const Element &b) const;
342
343 const Element& Square(const Element &a) const
344 {return Reduced(a.Squared());}
345
346 const Element& MultiplicativeInverse(const Element &a) const;
347
348 protected:
349 const Element& Reduced(const Element &a) const;
350
351 unsigned int t0, t1;
352 mutable PolynomialMod2 result;
353 };
354
355 /// \brief GF(2^n) for b233 and k233
356 /// \details GF2NT233 is a specialization of GF2NT that provides Multiply()
357 /// and Square() operations when carryless multiplies is available.
358 class CRYPTOPP_DLL GF2NT233 : public GF2NT
359 {
360 public:
361 // polynomial modulus = x^t0 + x^t1 + x^t2, t0 > t1 > t2
362 GF2NT233(unsigned int t0, unsigned int t1, unsigned int t2);
363
364 GF2NP * Clone() const {return new GF2NT233(*this);}
365
366 const Element& Multiply(const Element &a, const Element &b) const;
367
368 const Element& Square(const Element &a) const;
369 };
370
371 /// \brief GF(2^n) with Pentanomial Basis
372 class CRYPTOPP_DLL GF2NPP : public GF2NP
373 {
374 public:
375 // polynomial modulus = x^t0 + x^t1 + x^t2 + x^t3 + x^t4, t0 > t1 > t2 > t3 > t4
376 GF2NPP(unsigned int t0, unsigned int t1, unsigned int t2, unsigned int t3, unsigned int t4)
377 : GF2NP(PolynomialMod2::Pentanomial(t0, t1, t2, t3, t4)), t1(t1), t2(t2), t3(t3) {}
378
379 GF2NP * Clone() const {return new GF2NPP(*this);}
380 void DEREncode(BufferedTransformation &bt) const;
381
382 private:
383 unsigned int t1, t2, t3;
384 };
385
386 // construct new GF2NP from the ASN.1 sequence Characteristic-two
387 CRYPTOPP_DLL GF2NP * CRYPTOPP_API BERDecodeGF2NP(BufferedTransformation &bt);
388
389 NAMESPACE_END
390
391 #ifndef __BORLANDC__
392 NAMESPACE_BEGIN(std)
393 template<> inline void swap(CryptoPP::PolynomialMod2 &a, CryptoPP::PolynomialMod2 &b)
394 {
395 a.swap(b);
396 }
397 NAMESPACE_END
398 #endif
399
400 #if CRYPTOPP_MSC_VERSION
401 # pragma warning(pop)
402 #endif
403
404 #endif
Exception
Base class for all exceptions thrown by the library.
Definition: cryptlib.h:158
operator>=
bool operator>=(const ::PolynomialMod2 &a, const ::PolynomialMod2 &b)
compares degree
Definition: gf2n.h:264
operator>
bool operator>(const ::PolynomialMod2 &a, const ::PolynomialMod2 &b)
compares degree
Definition: gf2n.h:261
GF2NP::Equal
bool Equal(const Element &a, const Element &b) const
Compare two elements for equality.
Definition: gf2n.h:308
operator*
inline ::Integer operator*(const ::Integer &a, const ::Integer &b)
Multiplication.
Definition: integer.h:772
misc.h
Utility functions for the Crypto++ library.
PolynomialMod2::GetCoefficient
int GetCoefficient(size_t i) const
return coefficient for x^i
Definition: gf2n.h:132
BitsToBytes
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:918
PolynomialMod2::IsUnit
bool IsUnit() const
only 1 is a unit
Definition: gf2n.h:228
GF2NT
GF(2^n) with Trinomial Basis.
Definition: gf2n.h:332
cryptlib.h
Abstract base classes that provide a uniform interface to this library.
AbstractEuclideanDomain< PolynomialMod2 >
PolynomialMod2::GetBit
bool GetBit(size_t n) const
return the n-th bit, n=0 being the least significant bit
Definition: gf2n.h:123
Square
Square block cipher.
Definition: square.h:24
std
STL namespace.
RandomNumberGenerator
Interface for random number generators.
Definition: cryptlib.h:1413
GF2NT::Square
const Element & Square(const Element &a) const
Square an element in the group.
Definition: gf2n.h:343
algebra.h
Classes for performing mathematics over different fields.
BufferedTransformation
Interface for buffered transformations.
Definition: cryptlib.h:1630
QuotientRing
Quotient ring.
Definition: algebra.h:386
GF2NT233
GF(2^n) for b233 and k233.
Definition: gf2n.h:358
operator==
bool operator==(const OID &lhs, const OID &rhs)
Compare two OIDs for equality.
AbstractRing< PolynomialMod2 >
PolynomialMod2
Polynomial with Coefficients in GF(2)
Definition: gf2n.h:26
PolynomialMod2::CoefficientCount
unsigned int CoefficientCount() const
degree + 1
Definition: gf2n.h:130
PolynomialMod2::DivideByZero
Excpetion thrown when divide by zero is encountered.
Definition: gf2n.h:32
PolynomialMod2::PolynomialMod2
PolynomialMod2(BufferedTransformation &encodedPoly, size_t byteCount)
Construct a PolynomialMod2 from big-endian form stored in a BufferedTransformation.
Definition: gf2n.h:59
secblock.h
Classes and functions for secure memory allocations.
operator!=
bool operator!=(const OID &lhs, const OID &rhs)
Compare two OIDs for inequality.
operator-
inline ::Integer operator-(const ::Integer &a, const ::Integer &b)
Subtraction.
Definition: integer.h:769
operator &
inline ::Integer operator &(const ::Integer &a, const ::Integer &b)
Bitwise AND.
Definition: integer.h:796
operator+
OID operator+(const OID &lhs, unsigned long rhs)
Append a value to an OID.
PolynomialMod2::MinEncodedSize
unsigned int MinEncodedSize() const
minimum number of bytes to encode this polynomial
Definition: gf2n.h:92
PolynomialMod2::PolynomialMod2
PolynomialMod2(const byte *encodedPoly, size_t byteCount)
Construct a PolynomialMod2 from big-endian byte array.
Definition: gf2n.h:55
operator<
bool operator<(const ::PolynomialMod2 &a, const ::PolynomialMod2 &b)
compares degree
Definition: gf2n.h:267
Parity
unsigned int Parity(T value)
Returns the parity of a value.
Definition: misc.h:787
PolynomialMod2::Doubled
PolynomialMod2 Doubled() const
is always zero since we&#39;re working modulo 2
Definition: gf2n.h:223
CRYPTOPP_ASSERT
#define CRYPTOPP_ASSERT(exp)
Debugging and diagnostic assertion.
Definition: trap.h:68
AbstractGroup< PolynomialMod2 >
operator^
inline ::Integer operator^(const ::Integer &a, const ::Integer &b)
Bitwise XOR.
Definition: integer.h:824
asn.h
Classes and functions for working with ANS.1 objects.
GF2NP::IsUnit
bool IsUnit(const Element &a) const
Determines whether an element is a unit in the group.
Definition: gf2n.h:311
GF2NPP
GF(2^n) with Pentanomial Basis.
Definition: gf2n.h:372
GF2NP
GF(2^n) with Polynomial Basis.
Definition: gf2n.h:296
PolynomialMod2::MultiplicativeInverse
PolynomialMod2 MultiplicativeInverse() const
return inverse if *this is a unit, otherwise return 0
Definition: gf2n.h:230
PolynomialMod2::operator[]
int operator[](unsigned int i) const
return coefficient for x^i
Definition: gf2n.h:135
PolynomialMod2::PolynomialMod2
PolynomialMod2(RandomNumberGenerator &rng, size_t bitcount)
Create a uniformly distributed random polynomial.
Definition: gf2n.h:64
STDMAX
const T & STDMAX(const T &a, const T &b)
Replacement function for std::max.
Definition: misc.h:646
EuclideanDomainOf< PolynomialMod2 >
PolynomialMod2::Degree
signed int Degree() const
the zero polynomial will return a degree of -1
Definition: gf2n.h:128
CryptoPP
Crypto++ library namespace.
swap
void swap(::SecBlock< T, A > &a, ::SecBlock< T, A > &b)
Swap two SecBlocks.
Definition: secblock.h:1159
GetByte
unsigned int GetByte(ByteOrder order, T value, unsigned int index)
Gets a byte from a value.
Definition: misc.h:1990
operator<<
std::ostream & operator<<(std::ostream &out, const OID &oid)
Print a OID value.
Definition: asn.h:939
PolynomialMod2::Pentanomial
static PolynomialMod2 CRYPTOPP_API 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:145
SecWordBlock
SecBlock<word> typedef.
Definition: secblock.h:1099
operator<=
bool operator<=(const ::PolynomialMod2 &a, const ::PolynomialMod2 &b)
compares degree
Definition: gf2n.h:270