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) && 0 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);
84 const size_t nbytes = nbits/8 + 1;
87 buf[0] = (
byte)
Crop(buf[0], nbits % 8);
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)
157 struct NewPolynomialMod2
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) 189 void 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--)
233 if (!dec.IsDefiniteLength() || dec.RemainingLength() != length)
266 for (i=0; i<reg.
size(); i++)
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];
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++)
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;
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)
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());
678 CopyWords(g, m_modulus.reg, 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;
806 const GF2NT::Element&
GF2NT::Multiply(
const Element &a,
const Element &b)
const 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);
832 const 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();
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) && 0 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) && 0 1056 const word* pA = a.reg.begin();
1057 word* pR = result.reg.begin();
1059 GF2NT_233_Square_Reduce_POWER8(pA, pR);
const Element & MultiplicativeInverse(const Element &a) const
Calculate the multiplicative inverse of an element in the group.
Element & Accumulate(Element &a, const Element &b) const
const Element & Add(const Element &a, const Element &b) const
An invalid argument was detected.
Randomness Pool based on AES-256.
void CopyWords(word *r, const word *a, size_t n)
Copy word array.
bool SafeConvert(T1 from, T2 &to)
Tests whether a conversion from -> to is safe to perform.
static PolynomialMod2 Gcd(const PolynomialMod2 &a, const PolynomialMod2 &n)
greatest common divisor
Utility functions for the Crypto++ library.
PolynomialMod2()
Construct the zero polynomial.
Restricts the instantiation of a class to one static object without locks.
void CleanNew(size_type newSize)
Change size without preserving contents.
Class file for Randomness Pool.
const unsigned int WORD_BITS
Size of a platform word in bits.
size_t DEREncodeUnsigned(BufferedTransformation &out, T w, byte asnTag=INTEGER)
DER Encode unsigned value.
bool IsUnit() const
only 1 is a unit
GF(2^n) with Trinomial Basis.
size_t BitsToWords(size_t bitCount)
Returns the number of words required for the specified number of bits.
unsigned int BytePrecision(const T &value)
Returns the number of 8-bit bytes or octets required for a value.
void CleanGrow(size_type newSize)
Change size and preserve contents.
Secure memory block with allocator and cleanup.
Abstract base classes that provide a uniform interface to this library.
void BERDecodeUnsigned(BufferedTransformation &in, T &w, byte asnTag=INTEGER, T minValue=0, T maxValue=T(0xffffffff))
BER Decode unsigned value.
void Encode(byte *output, size_t outputLen) const
encode in big-endian format
ASN.1 object identifiers for algorthms and schemes.
Classes for automatic resource management.
Library configuration file.
Interface for random number generators.
size_t BytesToWords(size_t byteCount)
Returns the number of words required for the specified number of bytes.
const Element & Square(const Element &a) const
Square an element in the group.
const Element & Square(const Element &a) const
Classes for performing mathematics over different fields.
bool IsIrreducible() const
check for irreducibility
Support functions for word operations.
unsigned int WordCount() const
number of significant words = ceiling(ByteCount()/sizeof(word))
const Element & Multiply(const Element &a, const Element &b) const
Multiplies elements in the group.
Polynomial with Coefficients in GF(2)
unsigned int BitCount() const
number of significant bits = Degree() + 1
Excpetion thrown when divide by zero is encountered.
Copy input to a memory buffer.
void ShiftWordsLeftByWords(word *r, size_t n, size_t shiftWords)
Left shift word array.
static const PolynomialMod2 & Zero()
The Zero 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))
word64 word
Full word used for multiprecision integer arithmetic.
const Element & Multiply(const Element &a, const Element &b) const
T Crop(T value, size_t bits)
Truncates the value to the specified number of bits.
void Assign(const T *ptr, size_type len)
Set contents and size from an array.
void SetWords(word *r, word a, size_t n)
Set the value of words.
static PolynomialMod2 Trinomial(size_t t0, size_t t1, size_t t2)
Provides x^t0 + x^t1 + x^t2.
virtual void GenerateBlock(byte *output, size_t size)
Generate random array of bytes.
Classes and functions for schemes over GF(2^n)
void ShiftWordsRightByWords(word *r, size_t n, size_t shiftWords)
Right shift word array.
unsigned int Parity(T value)
Returns the parity of a value.
const T & STDMIN(const T &a, const T &b)
Replacement function for std::min.
String-based implementation of Store interface.
#define CRYPTOPP_ASSERT(exp)
Debugging and diagnostic assertion.
static PolynomialMod2 AllOnes(size_t n)
Provides x^(n-1) + ...
void SetByte(size_t n, byte value)
set the n-th byte to value
void BERDecodeError()
Raises a BERDecodeErr.
Functions for CPU features and intrinsics.
Classes and functions for working with ANS.1 objects.
iterator begin()
Provides an iterator pointing to the first element in the memory block.
Implementation of BufferedTransformation's attachment interface.
GF(2^n) with Pentanomial Basis.
unsigned char byte
8-bit unsigned datatype
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 XorWords(word *r, const word *a, const word *b, size_t n)
XOR word arrays.
GF(2^n) with Polynomial Basis.
PolynomialMod2 InverseMod(const PolynomialMod2 &) const
calculate multiplicative inverse of *this mod n
static const PolynomialMod2 & One()
The One polinomial.
PolynomialMod2 MultiplicativeInverse() const
return inverse if *this is a unit, otherwise return 0
void DEREncodeAsOctetString(BufferedTransformation &bt, size_t length) const
encode value as big-endian octet string
unsigned int ByteCount() const
number of significant bytes = ceiling(BitCount()/8)
word ShiftWordsRightByBits(word *r, size_t n, unsigned int shiftBits)
Right shift word array.
byte GetByte(size_t n) const
return the n-th byte
signed int Degree() const
the zero polynomial will return a degree of -1
void Grow(size_type newSize)
Change size and preserve contents.
void BERDecodeAsOctetString(BufferedTransformation &bt, size_t length)
decode value as big-endian octet string
Crypto++ library namespace.
const Element & MultiplicativeInverse(const Element &a) const
const Element & Square(const Element &a) const
Square an element in the group.
static PolynomialMod2 Monomial(size_t i)
Provides x^i.
void swap(::SecBlock< T, A > &a, ::SecBlock< T, A > &b)
Swap two SecBlocks.
unsigned int Parity() const
sum modulo 2 of all coefficients
size_t CountWords(const word *x, size_t n)
Count the number of words.
word ShiftWordsLeftByBits(word *r, size_t n, unsigned int shiftBits)
Left shift word array.
std::ostream & operator<<(std::ostream &out, const OID &oid)
Print a OID value.
const Element & Multiply(const Element &a, const Element &b) const
Multiplies elements in the group.
unsigned int BitPrecision(const T &value)
Returns the number of bits required for a value.
size_type size() const
Provides the count of elements in the SecBlock.
const unsigned int WORD_SIZE
Size of a platform word in bytes.
void AndWords(word *r, const word *a, const word *b, size_t n)
AND word arrays.