gf2n.h
Go to the documentation of this file.
// gf2n.h - originally written and placed in the public domain by Wei Dai
/// \file gf2n.h
/// \brief Classes and functions for schemes over GF(2^n)
#ifndef CRYPTOPP_GF2N_H
#define CRYPTOPP_GF2N_H
#include "cryptlib.h"
#include "secblock.h"
#include "algebra.h"
#include "misc.h"
#include "asn.h"
#include <iosfwd>
#if CRYPTOPP_MSC_VERSION
# pragma warning(push)
# pragma warning(disable: 4231 4275)
#endif
NAMESPACE_BEGIN(CryptoPP)
/// \brief Polynomial with Coefficients in GF(2)
/*! \nosubgrouping */
class CRYPTOPP_DLL PolynomialMod2
{
public:
/// \name ENUMS, EXCEPTIONS, and TYPEDEFS
//@{
/// \brief Exception thrown when divide by zero is encountered
class DivideByZero : public Exception
{
public:
DivideByZero() : Exception(OTHER_ERROR, "PolynomialMod2: division by zero") {}
};
typedef unsigned int RandomizationParameter;
//@}
/// \name CREATORS
//@{
/// \brief Construct the zero polynomial
PolynomialMod2();
/// Copy construct a PolynomialMod2
PolynomialMod2(const PolynomialMod2& t);
/// \brief Construct a PolynomialMod2 from a word
/// \details value should be encoded with the least significant bit as coefficient to x^0
/// and most significant bit as coefficient to x^(WORD_BITS-1)
/// bitLength denotes how much memory to allocate initially
PolynomialMod2(word value, size_t bitLength=WORD_BITS);
/// \brief Construct a PolynomialMod2 from big-endian byte array
PolynomialMod2(const byte *encodedPoly, size_t byteCount)
{Decode(encodedPoly, byteCount);}
/// \brief Construct a PolynomialMod2 from big-endian form stored in a BufferedTransformation
PolynomialMod2(BufferedTransformation &encodedPoly, size_t byteCount)
{Decode(encodedPoly, byteCount);}
/// \brief Create a uniformly distributed random polynomial
/// \details Create a random polynomial uniformly distributed over all polynomials with degree less than bitcount
PolynomialMod2(RandomNumberGenerator &rng, size_t bitcount)
{Randomize(rng, bitcount);}
/// \brief Provides x^i
/// \return x^i
static PolynomialMod2 CRYPTOPP_API Monomial(size_t i);
/// \brief Provides x^t0 + x^t1 + x^t2
/// \return x^t0 + x^t1 + x^t2
static PolynomialMod2 CRYPTOPP_API Trinomial(size_t t0, size_t t1, size_t t2);
/// \brief Provides x^t0 + x^t1 + x^t2 + x^t3 + x^t4
/// \return x^t0 + x^t1 + x^t2 + x^t3 + x^t4
static PolynomialMod2 CRYPTOPP_API Pentanomial(size_t t0, size_t t1, size_t t2, size_t t3, size_t t4);
/// \brief Provides x^(n-1) + ... + x + 1
/// \return x^(n-1) + ... + x + 1
static PolynomialMod2 CRYPTOPP_API AllOnes(size_t n);
/// \brief The Zero polinomial
/// \return the zero polynomial
static const PolynomialMod2 & CRYPTOPP_API Zero();
/// \brief The One polinomial
/// \return the one polynomial
static const PolynomialMod2 & CRYPTOPP_API One();
//@}
/// \name ENCODE/DECODE
//@{
/// minimum number of bytes to encode this polynomial
/*! MinEncodedSize of 0 is 1 */
unsigned int MinEncodedSize() const {return STDMAX(1U, ByteCount());}
/// encode in big-endian format
/// \details if outputLen < MinEncodedSize, the most significant bytes will be dropped
/// if outputLen > MinEncodedSize, the most significant bytes will be padded
void Encode(byte *output, size_t outputLen) const;
///
void Encode(BufferedTransformation &bt, size_t outputLen) const;
///
void Decode(const byte *input, size_t inputLen);
///
//* Precondition: bt.MaxRetrievable() >= inputLen
void Decode(BufferedTransformation &bt, size_t inputLen);
/// encode value as big-endian octet string
void DEREncodeAsOctetString(BufferedTransformation &bt, size_t length) const;
/// decode value as big-endian octet string
void BERDecodeAsOctetString(BufferedTransformation &bt, size_t length);
//@}
/// \name ACCESSORS
//@{
/// number of significant bits = Degree() + 1
unsigned int BitCount() const;
/// number of significant bytes = ceiling(BitCount()/8)
unsigned int ByteCount() const;
/// number of significant words = ceiling(ByteCount()/sizeof(word))
unsigned int WordCount() const;
/// return the n-th bit, n=0 being the least significant bit
bool GetBit(size_t n) const {return GetCoefficient(n)!=0;}
/// return the n-th byte
byte GetByte(size_t n) const;
/// the zero polynomial will return a degree of -1
signed int Degree() const {return (signed int)(BitCount()-1U);}
/// degree + 1
unsigned int CoefficientCount() const {return BitCount();}
/// return coefficient for x^i
int GetCoefficient(size_t i) const
{return (i/WORD_BITS < reg.size()) ? int(reg[i/WORD_BITS] >> (i % WORD_BITS)) & 1 : 0;}
/// return coefficient for x^i
int operator[](unsigned int i) const {return GetCoefficient(i);}
///
bool IsZero() const {return !*this;}
///
bool Equals(const PolynomialMod2 &rhs) const;
//@}
/// \name MANIPULATORS
//@{
///
PolynomialMod2& operator=(const PolynomialMod2& t);
///
PolynomialMod2& operator&=(const PolynomialMod2& t);
///
PolynomialMod2& operator^=(const PolynomialMod2& t);
///
PolynomialMod2& operator+=(const PolynomialMod2& t) {return *this ^= t;}
///
PolynomialMod2& operator-=(const PolynomialMod2& t) {return *this ^= t;}
///
PolynomialMod2& operator*=(const PolynomialMod2& t);
///
PolynomialMod2& operator/=(const PolynomialMod2& t);
///
PolynomialMod2& operator%=(const PolynomialMod2& t);
///
PolynomialMod2& operator<<=(unsigned int);
///
PolynomialMod2& operator>>=(unsigned int);
///
void Randomize(RandomNumberGenerator &rng, size_t bitcount);
///
void SetBit(size_t i, int value = 1);
/// set the n-th byte to value
void SetByte(size_t n, byte value);
///
void SetCoefficient(size_t i, int value) {SetBit(i, value);}
///
void swap(PolynomialMod2 &a) {reg.swap(a.reg);}
//@}
/// \name UNARY OPERATORS
//@{
///
bool operator!() const;
///
PolynomialMod2 operator+() const {return *this;}
///
PolynomialMod2 operator-() const {return *this;}
//@}
/// \name BINARY OPERATORS
//@{
///
PolynomialMod2 And(const PolynomialMod2 &b) const;
///
PolynomialMod2 Xor(const PolynomialMod2 &b) const;
///
PolynomialMod2 Plus(const PolynomialMod2 &b) const {return Xor(b);}
///
PolynomialMod2 Minus(const PolynomialMod2 &b) const {return Xor(b);}
///
PolynomialMod2 Times(const PolynomialMod2 &b) const;
///
PolynomialMod2 DividedBy(const PolynomialMod2 &b) const;
///
PolynomialMod2 Modulo(const PolynomialMod2 &b) const;
///
PolynomialMod2 operator>>(unsigned int n) const;
///
PolynomialMod2 operator<<(unsigned int n) const;
//@}
/// \name OTHER ARITHMETIC FUNCTIONS
//@{
/// sum modulo 2 of all coefficients
unsigned int Parity() const;
/// check for irreducibility
bool IsIrreducible() const;
/// is always zero since we're working modulo 2
PolynomialMod2 Doubled() const {return Zero();}
///
PolynomialMod2 Squared() const;
/// only 1 is a unit
bool IsUnit() const {return Equals(One());}
/// return inverse if *this is a unit, otherwise return 0
PolynomialMod2 MultiplicativeInverse() const {return IsUnit() ? One() : Zero();}
/// greatest common divisor
static PolynomialMod2 CRYPTOPP_API Gcd(const PolynomialMod2 &a, const PolynomialMod2 &n);
/// calculate multiplicative inverse of *this mod n
PolynomialMod2 InverseMod(const PolynomialMod2 &) const;
/// calculate r and q such that (a == d*q + r) && (deg(r) < deg(d))
static void CRYPTOPP_API Divide(PolynomialMod2 &r, PolynomialMod2 &q, const PolynomialMod2 &a, const PolynomialMod2 &d);
//@}
/// \name INPUT/OUTPUT
//@{
///
friend std::ostream& operator<<(std::ostream& out, const PolynomialMod2 &a);
//@}
private:
friend class GF2NT;
friend class GF2NT233;
SecWordBlock reg;
};
///
inline bool operator==(const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b)
{return a.Equals(b);}
///
inline bool operator!=(const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b)
{return !(a==b);}
/// compares degree
inline bool operator> (const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b)
{return a.Degree() > b.Degree();}
/// compares degree
inline bool operator>=(const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b)
{return a.Degree() >= b.Degree();}
/// compares degree
inline bool operator< (const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b)
{return a.Degree() < b.Degree();}
/// compares degree
inline bool operator<=(const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b)
{return a.Degree() <= b.Degree();}
///
inline CryptoPP::PolynomialMod2 operator&(const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b) {return a.And(b);}
///
inline CryptoPP::PolynomialMod2 operator^(const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b) {return a.Xor(b);}
///
inline CryptoPP::PolynomialMod2 operator+(const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b) {return a.Plus(b);}
///
inline CryptoPP::PolynomialMod2 operator-(const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b) {return a.Minus(b);}
///
inline CryptoPP::PolynomialMod2 operator*(const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b) {return a.Times(b);}
///
inline CryptoPP::PolynomialMod2 operator/(const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b) {return a.DividedBy(b);}
///
inline CryptoPP::PolynomialMod2 operator%(const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b) {return a.Modulo(b);}
// CodeWarrior 8 workaround: put these template instantiations after overloaded operator declarations,
// but before the use of QuotientRing<EuclideanDomainOf<PolynomialMod2> > for VC .NET 2003
CRYPTOPP_DLL_TEMPLATE_CLASS AbstractGroup<PolynomialMod2>;
CRYPTOPP_DLL_TEMPLATE_CLASS AbstractRing<PolynomialMod2>;
CRYPTOPP_DLL_TEMPLATE_CLASS AbstractEuclideanDomain<PolynomialMod2>;
CRYPTOPP_DLL_TEMPLATE_CLASS EuclideanDomainOf<PolynomialMod2>;
CRYPTOPP_DLL_TEMPLATE_CLASS QuotientRing<EuclideanDomainOf<PolynomialMod2> >;
/// \brief GF(2^n) with Polynomial Basis
class CRYPTOPP_DLL GF2NP : public QuotientRing<EuclideanDomainOf<PolynomialMod2> >
{
public:
GF2NP(const PolynomialMod2 &modulus);
virtual GF2NP * Clone() const {return new GF2NP(*this);}
virtual void DEREncode(BufferedTransformation &bt) const
{CRYPTOPP_UNUSED(bt); CRYPTOPP_ASSERT(false);} // no ASN.1 syntax yet for general polynomial basis
void DEREncodeElement(BufferedTransformation &out, const Element &a) const;
void BERDecodeElement(BufferedTransformation &in, Element &a) const;
bool Equal(const Element &a, const Element &b) const
{CRYPTOPP_ASSERT(a.Degree() < m_modulus.Degree() && b.Degree() < m_modulus.Degree()); return a.Equals(b);}
bool IsUnit(const Element &a) const
{CRYPTOPP_ASSERT(a.Degree() < m_modulus.Degree()); return !!a;}
unsigned int MaxElementBitLength() const
{return m;}
unsigned int MaxElementByteLength() const
{return (unsigned int)BitsToBytes(MaxElementBitLength());}
Element SquareRoot(const Element &a) const;
Element HalfTrace(const Element &a) const;
// returns z such that z^2 + z == a
Element SolveQuadraticEquation(const Element &a) const;
protected:
unsigned int m;
};
/// \brief GF(2^n) with Trinomial Basis
class CRYPTOPP_DLL GF2NT : public GF2NP
{
public:
// polynomial modulus = x^t0 + x^t1 + x^t2, t0 > t1 > t2
GF2NT(unsigned int t0, unsigned int t1, unsigned int t2);
GF2NP * Clone() const {return new GF2NT(*this);}
void DEREncode(BufferedTransformation &bt) const;
const Element& Multiply(const Element &a, const Element &b) const;
const Element& Square(const Element &a) const
{return Reduced(a.Squared());}
const Element& MultiplicativeInverse(const Element &a) const;
protected:
const Element& Reduced(const Element &a) const;
unsigned int t0, t1;
mutable PolynomialMod2 result;
};
/// \brief GF(2^n) for b233 and k233
/// \details GF2NT233 is a specialization of GF2NT that provides Multiply()
/// and Square() operations when carryless multiplies is available.
class CRYPTOPP_DLL GF2NT233 : public GF2NT
{
public:
// polynomial modulus = x^t0 + x^t1 + x^t2, t0 > t1 > t2
GF2NT233(unsigned int t0, unsigned int t1, unsigned int t2);
GF2NP * Clone() const {return new GF2NT233(*this);}
const Element& Multiply(const Element &a, const Element &b) const;
const Element& Square(const Element &a) const;
};
/// \brief GF(2^n) with Pentanomial Basis
class CRYPTOPP_DLL GF2NPP : public GF2NP
{
public:
// polynomial modulus = x^t0 + x^t1 + x^t2 + x^t3 + x^t4, t0 > t1 > t2 > t3 > t4
GF2NPP(unsigned int t0, unsigned int t1, unsigned int t2, unsigned int t3, unsigned int t4)
: GF2NP(PolynomialMod2::Pentanomial(t0, t1, t2, t3, t4)), t1(t1), t2(t2), t3(t3) {}
GF2NP * Clone() const {return new GF2NPP(*this);}
void DEREncode(BufferedTransformation &bt) const;
private:
unsigned int t1, t2, t3;
};
// construct new GF2NP from the ASN.1 sequence Characteristic-two
CRYPTOPP_DLL GF2NP * CRYPTOPP_API BERDecodeGF2NP(BufferedTransformation &bt);
NAMESPACE_END
#ifndef __BORLANDC__
NAMESPACE_BEGIN(std)
template<> inline void swap(CryptoPP::PolynomialMod2 &a, CryptoPP::PolynomialMod2 &b)
{
a.swap(b);
}
NAMESPACE_END
#endif
#if CRYPTOPP_MSC_VERSION
# pragma warning(pop)
#endif
#endif
algebra.h
Classes for performing mathematics over different fields.
asn.h
Classes and functions for working with ANS.1 objects.
operator<<
std::ostream & operator<<(std::ostream &out, const OID &oid)
Print a OID value.
Definition asn.h:939
operator+
OID operator+(const OID &lhs, unsigned long rhs)
Append a value to an OID.
operator==
bool operator==(const OID &lhs, const OID &rhs)
Compare two OIDs for equality.
operator!=
bool operator!=(const OID &lhs, const OID &rhs)
Compare two OIDs for inequality.
AbstractEuclideanDomain
Abstract Euclidean domain.
Definition algebra.h:277
AbstractGroup
Abstract group.
Definition algebra.h:27
AbstractRing
Abstract ring.
Definition algebra.h:119
BufferedTransformation
Interface for buffered transformations.
Definition cryptlib.h:1657
EuclideanDomainOf
Euclidean domain.
Definition algebra.h:316
Exception
Base class for all exceptions thrown by the library.
Definition cryptlib.h:164
GF2NP
GF(2^n) with Polynomial Basis.
Definition gf2n.h:297
GF2NPP
GF(2^n) with Pentanomial Basis.
Definition gf2n.h:373
GF2NT233
GF(2^n) for b233 and k233.
Definition gf2n.h:359
GF2NT
GF(2^n) with Trinomial Basis.
Definition gf2n.h:333
PolynomialMod2::DivideByZero
Exception thrown when divide by zero is encountered.
Definition gf2n.h:33
PolynomialMod2
Polynomial with Coefficients in GF(2)
Definition gf2n.h:27
PolynomialMod2::MinEncodedSize
unsigned int MinEncodedSize() const
minimum number of bytes to encode this polynomial
Definition gf2n.h:92
PolynomialMod2::DEREncodeAsOctetString
void DEREncodeAsOctetString(BufferedTransformation &bt, size_t length) const
encode value as big-endian octet string
PolynomialMod2::MultiplicativeInverse
PolynomialMod2 MultiplicativeInverse() const
return inverse if *this is a unit, otherwise return 0
Definition gf2n.h:230
PolynomialMod2::Encode
void Encode(byte *output, size_t outputLen) const
encode in big-endian format
PolynomialMod2::Monomial
static PolynomialMod2 Monomial(size_t i)
Provides x^i.
PolynomialMod2::Degree
signed int Degree() const
the zero polynomial will return a degree of -1
Definition gf2n.h:128
PolynomialMod2::One
static const PolynomialMod2 & One()
The One polinomial.
PolynomialMod2::IsIrreducible
bool IsIrreducible() const
check for irreducibility
PolynomialMod2::PolynomialMod2
PolynomialMod2(RandomNumberGenerator &rng, size_t bitcount)
Create a uniformly distributed random polynomial.
Definition gf2n.h:64
PolynomialMod2::Pentanomial
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.
PolynomialMod2::IsUnit
bool IsUnit() const
only 1 is a unit
Definition gf2n.h:228
PolynomialMod2::PolynomialMod2
PolynomialMod2(word value, size_t bitLength=WORD_BITS)
Construct a PolynomialMod2 from a word.
PolynomialMod2::Doubled
PolynomialMod2 Doubled() const
is always zero since we're working modulo 2
Definition gf2n.h:223
PolynomialMod2::PolynomialMod2
PolynomialMod2(const PolynomialMod2 &t)
Copy construct a PolynomialMod2.
PolynomialMod2::BERDecodeAsOctetString
void BERDecodeAsOctetString(BufferedTransformation &bt, size_t length)
decode value as big-endian octet string
PolynomialMod2::GetByte
byte GetByte(size_t n) const
return the n-th byte
PolynomialMod2::BitCount
unsigned int BitCount() const
number of significant bits = Degree() + 1
PolynomialMod2::WordCount
unsigned int WordCount() const
number of significant words = ceiling(ByteCount()/sizeof(word))
PolynomialMod2::AllOnes
static PolynomialMod2 AllOnes(size_t n)
Provides x^(n-1) + ... + x + 1.
PolynomialMod2::Trinomial
static PolynomialMod2 Trinomial(size_t t0, size_t t1, size_t t2)
Provides x^t0 + x^t1 + x^t2.
PolynomialMod2::CoefficientCount
unsigned int CoefficientCount() const
degree + 1
Definition gf2n.h:130
PolynomialMod2::InverseMod
PolynomialMod2 InverseMod(const PolynomialMod2 &) const
calculate multiplicative inverse of *this mod n
PolynomialMod2::PolynomialMod2
PolynomialMod2(BufferedTransformation &encodedPoly, size_t byteCount)
Construct a PolynomialMod2 from big-endian form stored in a BufferedTransformation.
Definition gf2n.h:59
PolynomialMod2::operator[]
int operator[](unsigned int i) const
return coefficient for x^i
Definition gf2n.h:135
PolynomialMod2::Parity
unsigned int Parity() const
sum modulo 2 of all coefficients
PolynomialMod2::PolynomialMod2
PolynomialMod2()
Construct the zero polynomial.
PolynomialMod2::Zero
static const PolynomialMod2 & Zero()
The Zero polinomial.
PolynomialMod2::ByteCount
unsigned int ByteCount() const
number of significant bytes = ceiling(BitCount()/8)
PolynomialMod2::Divide
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))
PolynomialMod2::Gcd
static PolynomialMod2 Gcd(const PolynomialMod2 &a, const PolynomialMod2 &n)
greatest common divisor
PolynomialMod2::PolynomialMod2
PolynomialMod2(const byte *encodedPoly, size_t byteCount)
Construct a PolynomialMod2 from big-endian byte array.
Definition gf2n.h:55
PolynomialMod2::SetByte
void SetByte(size_t n, byte value)
set the n-th byte to value
PolynomialMod2::GetCoefficient
int GetCoefficient(size_t i) const
return coefficient for x^i
Definition gf2n.h:132
PolynomialMod2::GetBit
bool GetBit(size_t n) const
return the n-th bit, n=0 being the least significant bit
Definition gf2n.h:123
QuotientRing
Quotient ring.
Definition algebra.h:387
RandomNumberGenerator
Interface for random number generators.
Definition cryptlib.h:1440
SecWordBlock
SecBlock<word> typedef.
Definition secblock.h:1228
Square
Square block cipher.
Definition square.h:25
CRYPTOPP_API
#define CRYPTOPP_API
Win32 calling convention.
Definition config_dll.h:119
CRYPTOPP_DLL_TEMPLATE_CLASS
#define CRYPTOPP_DLL_TEMPLATE_CLASS
Instantiate templates in a dynamic library.
Definition config_dll.h:72
word
word64 word
Full word used for multiprecision integer arithmetic.
Definition config_int.h:192
WORD_BITS
const unsigned int WORD_BITS
Size of a platform word in bits.
Definition config_int.h:260
cryptlib.h
Abstract base classes that provide a uniform interface to this library.
operator>
bool operator>(const ::PolynomialMod2 &a, const ::PolynomialMod2 &b)
compares degree
Definition gf2n.h:261
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:267
operator<=
bool operator<=(const ::PolynomialMod2 &a, const ::PolynomialMod2 &b)
compares degree
Definition gf2n.h:270
misc.h
Utility functions for the Crypto++ library.
STDMAX
const T & STDMAX(const T &a, const T &b)
Replacement function for std::max.
Definition misc.h:668
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:1143
CryptoPP
Crypto++ library namespace.
secblock.h
Classes and functions for secure memory allocations.
CRYPTOPP_ASSERT
#define CRYPTOPP_ASSERT(exp)
Debugging and diagnostic assertion.
Definition trap.h:68