6#ifndef CRYPTOPP_IMPORTS
22ANONYMOUS_NAMESPACE_BEGIN
24using CryptoPP::PolynomialMod2;
26#if defined(HAVE_GCC_INIT_PRIORITY)
29#elif defined(HAVE_MSC_INIT_PRIORITY)
30 #pragma warning(disable: 4075)
31 #pragma init_seg(".CRT$XCU")
34 #pragma warning(default: 4075)
35#elif defined(HAVE_XLC_INIT_PRIORITY)
41ANONYMOUS_NAMESPACE_END
43NAMESPACE_BEGIN(CryptoPP)
45#if (CRYPTOPP_CLMUL_AVAILABLE)
46extern CRYPTOPP_DLL
void GF2NT_233_Multiply_Reduce_CLMUL(
const word* pA,
const word* pB, word* pC);
47extern CRYPTOPP_DLL
void GF2NT_233_Square_Reduce_CLMUL(
const word* pA, word* pC);
50#if (CRYPTOPP_ARM_PMULL_AVAILABLE)
51extern void GF2NT_233_Multiply_Reduce_ARMv8(
const word* pA,
const word* pB, word* pC);
52extern void GF2NT_233_Square_Reduce_ARMv8(
const word* pA, word* pC);
55#if (CRYPTOPP_POWER8_VMULL_AVAILABLE) && 0
56extern void GF2NT_233_Multiply_Reduce_POWER8(
const word* pA,
const word* pB, word* pC);
57extern void GF2NT_233_Square_Reduce_POWER8(
const word* pA, word* pC);
67 CRYPTOPP_ASSERT(value==0 || reg.
size()>0);
84 const size_t nbytes = nbits/8 + 1;
87 buf[0] = (
byte)
Crop(buf[0], nbits % 8);
100void PolynomialMod2::SetBit(
size_t n,
int value)
159 PolynomialMod2 * operator()()
const
161 return new PolynomialMod2(i);
167#if defined(HAVE_GCC_INIT_PRIORITY) || defined(HAVE_MSC_INIT_PRIORITY) || defined(HAVE_XLC_INIT_PRIORITY)
169#elif defined(CRYPTOPP_CXX11_STATIC_INIT)
179#if defined(HAVE_GCC_INIT_PRIORITY) || defined(HAVE_MSC_INIT_PRIORITY) || defined(HAVE_XLC_INIT_PRIORITY)
181#elif defined(CRYPTOPP_CXX11_STATIC_INIT)
189void PolynomialMod2::Decode(
const byte *input,
size_t inputLen)
192 Decode(store, inputLen);
209 for (
size_t i=inputLen; i > 0; i--)
219 for (
size_t i=outputLen; i > 0; i--)
266 for (i=0; i<reg.
size(); i++)
268 return CryptoPP::Parity(temp);
286 if (b.reg.size() >= reg.
size())
296 XorWords(result.reg, reg, b.reg, b.reg.size());
297 CopyWords(result.reg+b.reg.size(), reg+b.reg.size(), reg.
size()-b.reg.size());
305 AndWords(result.reg, reg, b.reg, result.reg.size());
313 for (
int i=b.Degree(); i>=0; i--)
324 static const word map[16] = {0, 1, 4, 5, 16, 17, 20, 21, 64, 65, 68, 69, 80, 81, 84, 85};
328 for (
unsigned i=0; i<reg.
size(); i++)
333 result.reg[2*i] |= map[(reg[i] >> (j/2)) % 16] << j;
336 result.reg[2*i+1] |= map[(reg[i] >> (j/2 +
WORD_BITS/2)) % 16] << j;
348 int degree = divisor.
Degree();
355 for (
int i=dividend.
Degree(); i>=0; i--)
358 remainder.reg[0] |= dividend[i];
359 if (remainder[degree])
361 remainder -= divisor;
383#if defined(CRYPTOPP_DEBUG)
384 int x=0; CRYPTOPP_UNUSED(x);
402 *r = (u << 1) | carry;
410 reg[reg.
size()-1] = carry;
425 *r = (u << shiftBits) | carry;
434 const size_t carryIndex = reg.
size();
435 reg.
Grow(reg.
size()+shiftWords+!!shiftBits);
436 reg[carryIndex] = carry;
443 for (i = (
int)reg.
size()-1; i>=shiftWords; i--)
444 reg[i] = reg[i-shiftWords];
463 word *r=reg+reg.
size()-1;
471 *r = (u >> shiftBits) | carry;
479 for (i=0; i<reg.
size()-shiftWords; i++)
480 reg[i] = reg[i+shiftWords];
481 for (; i<reg.
size(); i++)
500bool PolynomialMod2::operator!()
const
502 for (
unsigned i=0; i<reg.
size(); i++)
503 if (reg[i])
return false;
511 for (i=0; i<smallerSize; i++)
512 if (reg[i] != rhs.reg[i])
return false;
514 for (i=smallerSize; i<reg.
size(); i++)
515 if (reg[i] != 0)
return false;
517 for (i=smallerSize; i<rhs.reg.
size(); i++)
518 if (rhs.reg[i] != 0)
return false;
523std::ostream& operator<<(std::ostream& out,
const PolynomialMod2 &a)
526 long f = out.flags() & std::ios::basefield;
548 return out <<
'0' << suffix;
553 static const char upper[]=
"0123456789ABCDEF";
554 static const char lower[]=
"0123456789abcdef";
555 const char*
const vec = (out.flags() & std::ios::uppercase) ? upper : lower;
557 for (i=0; i*bits < a.BitCount(); i++)
560 for (
int j=0; j<bits; j++)
561 digit |= a[i*bits+j] << j;
568 if (i && (i%block)==0)
572 return out << suffix;
593 for (
int i=1; i<=d/2; i++)
595 u = u.Squared()%(*this);
609GF2NP::Element GF2NP::SquareRoot(
const Element &a)
const
612 for (
unsigned int i=1; i<m; i++)
617GF2NP::Element GF2NP::HalfTrace(
const Element &a)
const
619 CRYPTOPP_ASSERT(m%2 == 1);
621 for (
unsigned int i=1; i<=(m-1)/2; i++)
626GF2NP::Element GF2NP::SolveQuadraticEquation(
const Element &a)
const
637 for (
unsigned int i=1; i<=m-1; i++)
641 Accumulate(z, Multiply(w, a));
644 }
while (w.IsZero());
653GF2NT::GF2NT(
unsigned int c0,
unsigned int c1,
unsigned int c2)
658 CRYPTOPP_ASSERT(c0 > c1 && c1 > c2 && c2==0);
668 word *c = T+m_modulus.reg.size();
669 word *f = T+2*m_modulus.reg.size();
670 word *g = T+3*m_modulus.reg.size();
671 size_t bcLen=1, fgLen=m_modulus.reg.size();
674 SetWords(T, 0, 3*m_modulus.reg.size());
676 CRYPTOPP_ASSERT(a.reg.size() <= m_modulus.reg.size());
678 CopyWords(g, m_modulus.reg, m_modulus.reg.size());
688 CRYPTOPP_ASSERT(bcLen <= m_modulus.reg.size());
719 CRYPTOPP_ASSERT(bcLen <= m_modulus.reg.size());
722 if (f[fgLen-1]==0 && g[fgLen-1]==0)
725 if (f[fgLen-1] < g[fgLen-1])
744 for (
unsigned int j=0; j<
WORD_BITS-t1; j++)
748 const unsigned int shift = t1 + j;
750 temp ^= (shift <
WORD_BITS) ? (((temp >> j) & 1) << shift) : 0;
776 for (
unsigned int j=0; j<
WORD_BITS-t1; j++)
780 const unsigned int shift = t1 + j;
782 temp ^= (shift <
WORD_BITS) ? (((temp >> j) & 1) << shift) : 0;
808 size_t aSize =
STDMIN(a.reg.size(), result.reg.
size());
809 Element r((word)0, m);
811 for (
int i=m-1; i>=0; i--)
816 XorWords(r.reg.begin(), m_modulus.reg, r.reg.size());
822 XorWords(r.reg.begin(), a.reg, aSize);
826 r.reg.begin()[r.reg.size()-1] = (word)
Crop(r.reg[r.reg.size()-1], m%
WORD_BITS);
832const GF2NT::Element& GF2NT::Reduced(
const Element &a)
const
835 return m_domain.
Mod(a, m_modulus);
864 word temp = b[i] & ~mask;
888 a.DEREncodeAsOctetString(out, MaxElementByteLength());
893 a.BERDecodeAsOctetString(in, MaxElementByteLength());
899 ASN1::characteristic_two_field().DEREncode(seq);
902 ASN1::tpBasis().DEREncode(parameters);
904 parameters.MessageEnd();
911 ASN1::characteristic_two_field().DEREncode(seq);
914 ASN1::ppBasis().DEREncode(parameters);
919 pentanomial.MessageEnd();
920 parameters.MessageEnd();
929 if (
OID(seq) != ASN1::characteristic_two_field())
935 if (oid == ASN1::tpBasis())
939 result.reset(
new GF2NT(m, t1, 0));
941 else if (oid == ASN1::ppBasis())
943 unsigned int t1, t2, t3;
948 pentanomial.MessageEnd();
949 result.reset(
new GF2NPP(m, t3, t2, t1, 0));
956 parameters.MessageEnd();
959 return result.release();
964GF2NT233::GF2NT233(
unsigned int c0,
unsigned int c1,
unsigned int c2)
967 CRYPTOPP_ASSERT(c0 > c1 && c1 > c2 && c2==0);
972#if (CRYPTOPP_CLMUL_AVAILABLE)
975 CRYPTOPP_ASSERT(a.reg.size()*
WORD_BITS == 256);
976 CRYPTOPP_ASSERT(b.reg.size()*
WORD_BITS == 256);
977 CRYPTOPP_ASSERT(result.reg.size()*
WORD_BITS == 256);
979 const word* pA = a.reg.begin();
980 const word* pB = b.reg.begin();
981 word* pR = result.reg.begin();
983 GF2NT_233_Multiply_Reduce_CLMUL(pA, pB, pR);
987#elif (CRYPTOPP_ARM_PMULL_AVAILABLE)
990 CRYPTOPP_ASSERT(a.reg.size()*
WORD_BITS == 256);
991 CRYPTOPP_ASSERT(b.reg.size()*
WORD_BITS == 256);
992 CRYPTOPP_ASSERT(result.reg.size()*
WORD_BITS == 256);
994 const word* pA = a.reg.begin();
995 const word* pB = b.reg.begin();
996 word* pR = result.reg.begin();
998 GF2NT_233_Multiply_Reduce_ARMv8(pA, pB, pR);
1002#elif (CRYPTOPP_POWER8_VMULL_AVAILABLE) && 0
1005 CRYPTOPP_ASSERT(a.reg.size()*
WORD_BITS == 256);
1006 CRYPTOPP_ASSERT(b.reg.size()*
WORD_BITS == 256);
1007 CRYPTOPP_ASSERT(result.reg.size()*
WORD_BITS == 256);
1009 const word* pA = a.reg.begin();
1010 const word* pB = b.reg.begin();
1011 word* pR = result.reg.begin();
1013 GF2NT_233_Multiply_Reduce_POWER8(pA, pB, pR);
1024#if (CRYPTOPP_CLMUL_AVAILABLE)
1027 CRYPTOPP_ASSERT(a.reg.size()*
WORD_BITS == 256);
1028 CRYPTOPP_ASSERT(result.reg.size()*
WORD_BITS == 256);
1030 const word* pA = a.reg.begin();
1031 word* pR = result.reg.begin();
1033 GF2NT_233_Square_Reduce_CLMUL(pA, pR);
1037#elif (CRYPTOPP_ARM_PMULL_AVAILABLE)
1040 CRYPTOPP_ASSERT(a.reg.size()*
WORD_BITS == 256);
1041 CRYPTOPP_ASSERT(result.reg.size()*
WORD_BITS == 256);
1043 const word* pA = a.reg.begin();
1044 word* pR = result.reg.begin();
1046 GF2NT_233_Square_Reduce_ARMv8(pA, pR);
1050#elif (CRYPTOPP_POWER8_VMULL_AVAILABLE) && 0
1053 CRYPTOPP_ASSERT(a.reg.size()*
WORD_BITS == 256);
1054 CRYPTOPP_ASSERT(result.reg.size()*
WORD_BITS == 256);
1056 const word* pA = a.reg.begin();
1057 word* pR = result.reg.begin();
1059 GF2NT_233_Square_Reduce_POWER8(pA, pR);
Classes for performing mathematics over different fields.
Classes and functions for working with ANS.1 objects.
void BERDecodeUnsigned(BufferedTransformation &in, T &w, byte asnTag=INTEGER, T minValue=0, T maxValue=T(0xffffffff))
BER Decode unsigned value.
size_t DEREncodeUnsigned(BufferedTransformation &out, T w, byte asnTag=INTEGER)
DER Encode unsigned value.
@ OCTET_STRING
ASN.1 Octet string.
void BERDecodeError()
Raises a BERDecodeErr.
virtual const Element & Gcd(const Element &a, const Element &b) const
Calculates the greatest common denominator in the ring.
virtual const Element & MultiplicativeInverse(const Element &a) const=0
Calculate the multiplicative inverse of an element in the group.
Copy input to a memory buffer.
lword RemainingLength() const
Determine remaining length.
bool IsDefiniteLength() const
Determine length encoding.
void MessageEnd()
Signals the end of messages to the object.
void MessageEnd()
Signals the end of messages to the object.
const Element & Mod(const Element &a, const Element &b) const
Performs a modular reduction in the ring.
GF(2^n) with Polynomial Basis.
GF(2^n) with Pentanomial Basis.
const Element & Square(const Element &a) const
Square an element in the group.
const Element & Multiply(const Element &a, const Element &b) const
Multiplies elements in the group.
GF(2^n) with Trinomial Basis.
const Element & MultiplicativeInverse(const Element &a) const
Calculate the multiplicative inverse of an element in the group.
const Element & Square(const Element &a) const
Square an element in the group.
const Element & Multiply(const Element &a, const Element &b) const
Multiplies elements in the group.
An invalid argument was detected.
Exception thrown when divide by zero is encountered.
Polynomial with Coefficients in GF(2)
static const PolynomialMod2 &CRYPTOPP_API Zero()
The Zero polinomial.
void DEREncodeAsOctetString(BufferedTransformation &bt, size_t length) const
encode value as big-endian octet string
void Encode(byte *output, size_t outputLen) const
signed int Degree() const
the zero polynomial will return a degree of -1
static PolynomialMod2 CRYPTOPP_API Gcd(const PolynomialMod2 &a, const PolynomialMod2 &n)
greatest common divisor
bool IsIrreducible() const
check for irreducibility
bool IsUnit() const
only 1 is a unit
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.
void BERDecodeAsOctetString(BufferedTransformation &bt, size_t length)
decode value as big-endian octet string
static PolynomialMod2 CRYPTOPP_API Trinomial(size_t t0, size_t t1, size_t t2)
Provides x^t0 + x^t1 + x^t2.
static const PolynomialMod2 &CRYPTOPP_API One()
The One polinomial.
static void CRYPTOPP_API 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))
byte GetByte(size_t n) const
return the n-th byte
unsigned int BitCount() const
number of significant bits = Degree() + 1
static PolynomialMod2 CRYPTOPP_API Monomial(size_t i)
Provides x^i.
unsigned int WordCount() const
number of significant words = ceiling(ByteCount()/sizeof(word))
PolynomialMod2 InverseMod(const PolynomialMod2 &) const
calculate multiplicative inverse of *this mod n
static PolynomialMod2 CRYPTOPP_API AllOnes(size_t n)
Provides x^(n-1) + ... + x + 1.
unsigned int Parity() const
sum modulo 2 of all coefficients
unsigned int ByteCount() const
number of significant bytes = ceiling(BitCount()/8)
PolynomialMod2()
Construct the zero polynomial.
void SetByte(size_t n, byte value)
set the n-th byte to value
Interface for random number generators.
virtual void GenerateBlock(byte *output, size_t size)
Generate random array of bytes.
Randomness Pool based on AES-256.
iterator begin()
Provides an iterator pointing to the first element in the memory block.
void CleanNew(size_type newSize)
Change size without preserving contents.
void CleanGrow(size_type newSize)
Change size and preserve contents.
void Grow(size_type newSize)
Change size and preserve contents.
void Assign(const T *ptr, size_type len)
Set contents and size from an array.
size_type size() const
Provides the count of elements in the SecBlock.
Restricts the instantiation of a class to one static object without locks.
CRYPTOPP_NOINLINE const T & Ref(CRYPTOPP_NOINLINE_DOTDOTDOT) const
Return a reference to the inner Singleton object.
String-based implementation of Store interface.
Pointer that overloads operator ->
Library configuration file.
unsigned char byte
8-bit unsigned datatype
const unsigned int WORD_BITS
Size of a platform word in bits.
const unsigned int WORD_SIZE
Size of a platform word in bytes.
Functions for CPU features and intrinsics.
Abstract base classes that provide a uniform interface to this library.
Implementation of BufferedTransformation's attachment interface.
Classes and functions for schemes over GF(2^n)
Utility functions for the Crypto++ library.
unsigned int BitPrecision(const T &value)
Returns the number of bits required for a value.
unsigned int BytePrecision(const T &value)
Returns the number of 8-bit bytes or octets required for a value.
size_t BitsToWords(size_t bitCount)
Returns the number of words required for the specified number of bits.
T Crop(T value, size_t bits)
Truncates the value to the specified number of bits.
const T & STDMIN(const T &a, const T &b)
Replacement function for std::min.
size_t BytesToWords(size_t byteCount)
Returns the number of words required for the specified number of bytes.
bool SafeConvert(T1 from, T2 &to)
Tests whether a conversion from -> to is safe to perform.
ASN.1 object identifiers for algorithms and schemes.
Class file for Randomness Pool.
Classes for automatic resource management.
Support functions for word operations.
void ShiftWordsRightByWords(word *r, size_t n, size_t shiftWords)
Right shift word array.
void XorWords(word *r, const word *a, const word *b, size_t n)
XOR word arrays.
void SetWords(word *r, word a, size_t n)
Set the value of words.
word ShiftWordsLeftByBits(word *r, size_t n, unsigned int shiftBits)
Left shift word array.
void ShiftWordsLeftByWords(word *r, size_t n, size_t shiftWords)
Left shift word array.
size_t CountWords(const word *x, size_t n)
Count the number of words.
word ShiftWordsRightByBits(word *r, size_t n, unsigned int shiftBits)
Right shift word array.
void CopyWords(word *r, const word *a, size_t n)
Copy word array.
void AndWords(word *r, const word *a, const word *b, size_t n)
AND word arrays.