6 #ifndef CRYPTOPP_IMPORTS
22 ANONYMOUS_NAMESPACE_BEGIN
24 using 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)
41 ANONYMOUS_NAMESPACE_END
45 #if (CRYPTOPP_CLMUL_AVAILABLE)
46 extern CRYPTOPP_DLL
void GF2NT_233_Multiply_Reduce_CLMUL(
const word* pA,
const word* pB, word* pC);
47 extern CRYPTOPP_DLL
void GF2NT_233_Square_Reduce_CLMUL(
const word* pA, word* pC);
50 #if (CRYPTOPP_ARM_PMULL_AVAILABLE)
51 extern void GF2NT_233_Multiply_Reduce_ARMv8(
const word* pA,
const word* pB, word* pC);
52 extern void GF2NT_233_Square_Reduce_ARMv8(
const word* pA, word* pC);
55 #if (CRYPTOPP_POWER8_VMULL_AVAILABLE)
56 extern void GF2NT_233_Multiply_Reduce_POWER8(
const word* pA,
const word* pB, word* pC);
57 extern void GF2NT_233_Square_Reduce_POWER8(
const word* pA, word* pC);
72 SetWords(reg+1, 0, reg.
size()-1);
79 CopyWords(reg, t.reg, reg.
size());
84 const size_t nbytes = nbits/8 + 1;
87 buf[0] = (byte)
Crop(buf[0], nbits % 8);
94 SetWords(result.reg, ~(word(0)), result.reg.
size());
95 if (bitLength%WORD_BITS)
96 result.reg[result.reg.
size()-1] = (word)
Crop(result.reg[result.reg.
size()-1], bitLength%WORD_BITS);
100 void PolynomialMod2::SetBit(
size_t n,
int value)
105 reg[n/WORD_BITS] |= (word(1) << (n%WORD_BITS));
109 if (n/WORD_BITS < reg.
size())
110 reg[n/WORD_BITS] &= ~(word(1) << (n%WORD_BITS));
116 if (n/WORD_SIZE >= reg.
size())
119 return byte(reg[n/WORD_SIZE] >> ((n%WORD_SIZE)*8));
125 reg[n/WORD_SIZE] &= ~(word(0xff) << 8*(n%WORD_SIZE));
126 reg[n/WORD_SIZE] |= (word(value) << 8*(n%WORD_SIZE));
167 #if defined(HAVE_GCC_INIT_PRIORITY) || defined(HAVE_MSC_INIT_PRIORITY) || defined(HAVE_XLC_INIT_PRIORITY)
169 #elif defined(CRYPTOPP_CXX11_DYNAMIC_INIT)
179 #if defined(HAVE_GCC_INIT_PRIORITY) || defined(HAVE_MSC_INIT_PRIORITY) || defined(HAVE_XLC_INIT_PRIORITY)
181 #elif defined(CRYPTOPP_CXX11_DYNAMIC_INIT)
189 void PolynomialMod2::Decode(
const byte *input,
size_t inputLen)
192 Decode(store, inputLen);
209 for (
size_t i=inputLen; i > 0; i--)
213 reg[(i-1)/WORD_SIZE] |= word(b) << ((i-1)%WORD_SIZE)*8;
219 for (
size_t i=outputLen; i > 0; i--)
233 if (!dec.IsDefiniteLength() || dec.RemainingLength() != length)
241 return (
unsigned int)CountWords(reg, reg.
size());
248 return (wordCount-1)*WORD_SIZE +
BytePrecision(reg[wordCount-1]);
257 return (wordCount-1)*WORD_BITS +
BitPrecision(reg[wordCount-1]);
266 for (i=0; i<reg.
size(); i++)
280 XorWords(reg, t.reg, t.reg.
size());
286 if (b.reg.size() >= reg.
size())
289 XorWords(result.reg, reg, b.reg, reg.
size());
290 CopyWords(result.reg+reg.
size(), b.reg+reg.
size(), 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--)
317 XorWords(result.reg, reg, reg.
size());
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++)
332 for (j=0; j<WORD_BITS; j+=8)
333 result.reg[2*i] |= map[(reg[i] >> (j/2)) % 16] << j;
335 for (j=0; j<WORD_BITS; j+=8)
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;
403 carry = u >> (WORD_BITS-1);
410 reg[reg.
size()-1] = carry;
416 const int shiftWords = n / WORD_BITS;
417 const int shiftBits = n % WORD_BITS;
425 *r = (u << shiftBits) | carry;
426 carry = u >> (WORD_BITS-shiftBits);
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];
457 int shiftWords = n / WORD_BITS;
458 int shiftBits = n % WORD_BITS;
463 word *r=reg+reg.
size()-1;
471 *r = (u >> shiftBits) | carry;
472 carry = u << (WORD_BITS-shiftBits);
479 for (i=0; i<reg.
size()-shiftWords; i++)
480 reg[i] = reg[i+shiftWords];
481 for (; i<reg.
size(); i++)
500 bool 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;
523 std::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);
609 GF2NP::Element GF2NP::SquareRoot(
const Element &a)
const
612 for (
unsigned int i=1; i<m; i++)
617 GF2NP::Element GF2NP::HalfTrace(
const Element &a)
const
621 for (
unsigned int i=1; i<=(m-1)/2; i++)
626 GF2NP::Element GF2NP::SolveQuadraticEquation(
const Element &a)
const
637 for (
unsigned int i=1; i<=m-1; i++)
644 }
while (w.IsZero());
653 GF2NT::GF2NT(
unsigned int c0,
unsigned int c1,
unsigned int c2)
663 if (t0-t1 < WORD_BITS)
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());
677 CopyWords(f, a.reg, a.reg.size());
678 CopyWords(g, m_modulus.reg, m_modulus.reg.size());
685 ShiftWordsRightByWords(f, fgLen, 1);
689 ShiftWordsLeftByWords(c, bcLen, 1);
702 if (t==1 && CountWords(f, fgLen)==1)
707 ShiftWordsRightByBits(f, fgLen, 1);
708 t=ShiftWordsLeftByBits(c, bcLen, 1);
712 ShiftWordsRightByBits(f, fgLen, i);
713 t=ShiftWordsLeftByBits(c, bcLen, i);
722 if (f[fgLen-1]==0 && g[fgLen-1]==0)
725 if (f[fgLen-1] < g[fgLen-1])
731 XorWords(f, g, fgLen);
732 XorWords(b, c, bcLen);
735 while (k >= WORD_BITS)
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;
753 b[t1/WORD_BITS-1] ^= temp << t1%WORD_BITS;
756 b[t1/WORD_BITS] ^= temp >> (WORD_BITS - t1%WORD_BITS);
760 b[t0/WORD_BITS-1] ^= temp << t0%WORD_BITS;
761 b[t0/WORD_BITS] ^= temp >> (WORD_BITS - t0%WORD_BITS);
764 b[t0/WORD_BITS-1] ^= temp;
771 word temp = b[0] << (WORD_BITS - k);
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;
787 b[t1/WORD_BITS-1] ^= temp << t1%WORD_BITS;
791 b[t1/WORD_BITS] ^= temp >> (WORD_BITS - t1%WORD_BITS);
795 b[t0/WORD_BITS-1] ^= temp << t0%WORD_BITS;
796 b[t0/WORD_BITS] ^= temp >> (WORD_BITS - t0%WORD_BITS);
799 b[t0/WORD_BITS-1] ^= temp;
802 CopyWords(result.reg.
begin(), b, result.reg.
size());
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--)
815 ShiftWordsLeftByBits(r.reg.begin(), r.reg.size(), 1);
816 XorWords(r.reg.begin(), m_modulus.reg, r.reg.size());
819 ShiftWordsLeftByBits(r.reg.begin(), r.reg.size(), 1);
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);
828 CopyWords(result.reg.
begin(), r.reg.begin(), result.reg.
size());
832 const GF2NT::Element& GF2NT::Reduced(
const Element &a)
const
834 if (t0-t1 < WORD_BITS)
835 return m_domain.Mod(a, m_modulus);
846 b[i-t0/WORD_BITS] ^= temp >> t0%WORD_BITS;
847 b[i-t0/WORD_BITS-1] ^= temp << (WORD_BITS - t0%WORD_BITS);
850 b[i-t0/WORD_BITS] ^= temp;
852 if ((t0-t1)%WORD_BITS)
854 b[i-(t0-t1)/WORD_BITS] ^= temp >> (t0-t1)%WORD_BITS;
855 b[i-(t0-t1)/WORD_BITS-1] ^= temp << (WORD_BITS - (t0-t1)%WORD_BITS);
858 b[i-(t0-t1)/WORD_BITS] ^= temp;
863 word mask = ((word)1<<(t0%WORD_BITS))-1;
864 word temp = b[i] & ~mask;
867 b[i-t0/WORD_BITS] ^= temp >> t0%WORD_BITS;
869 if ((t0-t1)%WORD_BITS)
871 b[i-(t0-t1)/WORD_BITS] ^= temp >> (t0-t1)%WORD_BITS;
872 if ((t0-t1)%WORD_BITS > t0%WORD_BITS)
873 b[i-(t0-t1)/WORD_BITS-1] ^= temp << (WORD_BITS - (t0-t1)%WORD_BITS);
878 b[i-(t0-t1)/WORD_BITS] ^= temp;
881 SetWords(result.reg.
begin(), 0, result.reg.
size());
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();
964 GF2NT233::GF2NT233(
unsigned int c0,
unsigned int c1,
unsigned int c2)
972 #if (CRYPTOPP_CLMUL_AVAILABLE)
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)
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)
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)
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)
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)
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.
void BERDecodeError()
Raises a BERDecodeErr.
virtual const Element & Gcd(const Element &a, const Element &b) const
Calculates the greatest common denominator in the ring.
Copy input to a memory buffer.
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 & Square(const Element &a) const
Square an element in the group.
const Element & MultiplicativeInverse(const Element &a) const
Calculate the multiplicative inverse of 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.
Excpetion thrown when divide by zero is encountered.
Polynomial with Coefficients in GF(2)
static const PolynomialMod2 & 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
encode in big-endian format
signed int Degree() const
the zero polynomial will return a degree of -1
static PolynomialMod2 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 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 Trinomial(size_t t0, size_t t1, size_t t2)
Provides x^t0 + x^t1 + x^t2.
static const PolynomialMod2 & One()
The One polinomial.
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))
byte GetByte(size_t n) const
return the n-th byte
unsigned int BitCount() const
number of significant bits = Degree() + 1
static PolynomialMod2 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 AllOnes(size_t n)
Provides x^(n-1) + ...
unsigned int Parity() const
sum modulo 2 of all coefficients
PolynomialMod2()
Construct the zero polynomial.
unsigned int ByteCount() const
number of significant bytes = ceiling(BitCount()/8)
void SetByte(size_t n, byte value)
set the n-th byte to value
const Element & Square(const Element &a) const
Element & Accumulate(Element &a, const Element &b) const
const Element & MultiplicativeInverse(const Element &a) const
Calculate the multiplicative inverse of an element in the group.
const Element & Add(const Element &a, const Element &b) const
const Element & Multiply(const Element &a, const Element &b) const
Interface for random number generators.
virtual void GenerateBlock(byte *output, size_t size)
Generate random array of bytes.
Randomness Pool based on AES-256.
Secure memory block with allocator and cleanup.
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.
const T & Ref(...) const
Return a reference to the inner Singleton object.
String-based implementation of Store interface.
Pointer that overloads operator ->
Library configuration file.
Functions for CPU features and intrinsics.
bool HasCLMUL()
Determines Carryless Multiply availability.
bool HasPMULL()
Determine if an ARM processor provides Polynomial Multiplication.
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.
unsigned int Parity(T value)
Returns the parity of a value.
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.
const T & STDMIN(const T &a, const T &b)
Replacement function for std::min.
Crypto++ library namespace.
ASN.1 object identifiers for algorthms and schemes.
Class file for Randomness Pool.
Classes for automatic resource management.
#define CRYPTOPP_ASSERT(exp)
Debugging and diagnostic assertion.