6 #ifndef CRYPTOPP_IMPORTS 22 #if CRYPTOPP_GCC_DIAGNOSTIC_AVAILABLE 23 # pragma GCC diagnostic ignored "-Wconversion" 24 # pragma GCC diagnostic ignored "-Wsign-conversion" 41 SetWords(reg+1, 0, reg.
size()-1);
48 CopyWords(reg, t.reg, reg.
size());
53 const size_t nbytes = nbits/8 + 1;
56 buf[0] = (byte)
Crop(buf[0], nbits % 8);
64 if (bitLength%WORD_BITS)
65 result.reg[result.reg.
size()-1] = (word)
Crop(result.reg[result.reg.
size()-1], bitLength%WORD_BITS);
69 void PolynomialMod2::SetBit(
size_t n,
int value)
74 reg[n/WORD_BITS] |= (word(1) << (n%WORD_BITS));
78 if (n/WORD_BITS < reg.
size())
79 reg[n/WORD_BITS] &= ~(word(1) << (n%WORD_BITS));
85 if (n/WORD_SIZE >= reg.
size())
88 return byte(reg[n/WORD_SIZE] >> ((n%WORD_SIZE)*8));
94 reg[n/WORD_SIZE] &= ~(word(0xff) << 8*(n%WORD_SIZE));
95 reg[n/WORD_SIZE] |= (word(value) << 8*(n%WORD_SIZE));
144 void PolynomialMod2::Decode(
const byte *input,
size_t inputLen)
147 Decode(store, inputLen);
164 for (
size_t i=inputLen; i > 0; i--)
168 reg[(i-1)/WORD_SIZE] |= word(b) << ((i-1)%WORD_SIZE)*8;
174 for (
size_t i=outputLen; i > 0; i--)
188 if (!dec.IsDefiniteLength() || dec.RemainingLength() != length)
196 return (
unsigned int)CountWords(reg, reg.
size());
203 return (wordCount-1)*WORD_SIZE +
BytePrecision(reg[wordCount-1]);
212 return (wordCount-1)*WORD_BITS +
BitPrecision(reg[wordCount-1]);
221 for (i=0; i<reg.
size(); i++)
235 XorWords(reg, t.reg, t.reg.
size());
241 if (b.reg.size() >= reg.
size())
244 XorWords(result.reg, reg, b.reg, reg.
size());
245 CopyWords(result.reg+reg.
size(), b.reg+reg.
size(), b.reg.size()-reg.
size());
251 XorWords(result.reg, reg, b.reg, b.reg.size());
252 CopyWords(result.reg+b.reg.size(), reg+b.reg.size(), reg.
size()-b.reg.size());
260 AndWords(result.reg, reg, b.reg, result.reg.size());
268 for (
int i=b.Degree(); i>=0; i--)
272 XorWords(result.reg, reg, reg.
size());
279 static const word map[16] = {0, 1, 4, 5, 16, 17, 20, 21, 64, 65, 68, 69, 80, 81, 84, 85};
283 for (
unsigned i=0; i<reg.
size(); i++)
287 for (j=0; j<WORD_BITS; j+=8)
288 result.reg[2*i] |= map[(reg[i] >> (j/2)) % 16] << j;
290 for (j=0; j<WORD_BITS; j+=8)
291 result.reg[2*i+1] |= map[(reg[i] >> (j/2 + WORD_BITS/2)) % 16] << j;
303 int degree = divisor.
Degree();
310 for (
int i=dividend.
Degree(); i>=0; i--)
313 remainder.reg[0] |= dividend[i];
314 if (remainder[degree])
316 remainder -= divisor;
338 #if defined(CRYPTOPP_DEBUG) 339 int x; CRYPTOPP_UNUSED(x);
357 *r = (u << 1) | carry;
358 carry = u >> (WORD_BITS-1);
365 reg[reg.
size()-1] = carry;
371 const int shiftWords = n / WORD_BITS;
372 const int shiftBits = n % WORD_BITS;
380 *r = (u << shiftBits) | carry;
381 carry = u >> (WORD_BITS-shiftBits);
389 const size_t carryIndex = reg.
size();
390 reg.
Grow(reg.
size()+shiftWords+!!shiftBits);
391 reg[carryIndex] = carry;
398 for (i = (
int)reg.
size()-1; i>=shiftWords; i--)
399 reg[i] = reg[i-shiftWords];
412 int shiftWords = n / WORD_BITS;
413 int shiftBits = n % WORD_BITS;
418 word *r=reg+reg.
size()-1;
426 *r = (u >> shiftBits) | carry;
427 carry = u << (WORD_BITS-shiftBits);
434 for (i=0; i<reg.
size()-shiftWords; i++)
435 reg[i] = reg[i+shiftWords];
436 for (; i<reg.
size(); i++)
455 bool PolynomialMod2::operator!()
const 457 for (
unsigned i=0; i<reg.
size(); i++)
458 if (reg[i])
return false;
466 for (i=0; i<smallerSize; i++)
467 if (reg[i] != rhs.reg[i])
return false;
469 for (i=smallerSize; i<reg.
size(); i++)
470 if (reg[i] != 0)
return false;
472 for (i=smallerSize; i<rhs.reg.
size(); i++)
473 if (rhs.reg[i] != 0)
return false;
478 std::ostream& operator<<(std::ostream& out,
const PolynomialMod2 &a)
481 long f = out.flags() & std::ios::basefield;
503 return out <<
'0' << suffix;
508 static const char upper[]=
"0123456789ABCDEF";
509 static const char lower[]=
"0123456789abcdef";
510 const char*
const vec = (out.flags() & std::ios::uppercase) ? upper : lower;
512 for (i=0; i*bits < a.BitCount(); i++)
515 for (
int j=0; j<bits; j++)
516 digit |= a[i*bits+j] << j;
523 if (i && (i%block)==0)
527 return out << suffix;
548 for (
int i=1; i<=d/2; i++)
550 u = u.Squared()%(*this);
564 GF2NP::Element GF2NP::SquareRoot(
const Element &a)
const 567 for (
unsigned int i=1; i<m; i++)
572 GF2NP::Element GF2NP::HalfTrace(
const Element &a)
const 576 for (
unsigned int i=1; i<=(m-1)/2; i++)
581 GF2NP::Element GF2NP::SolveQuadraticEquation(
const Element &a)
const 592 for (
unsigned int i=1; i<=m-1; i++)
599 }
while (w.IsZero());
608 GF2NT::GF2NT(
unsigned int c0,
unsigned int c1,
unsigned int c2)
616 const GF2NT::Element& GF2NT::MultiplicativeInverse(
const Element &a)
const 618 if (t0-t1 < WORD_BITS)
623 word *c = T+m_modulus.reg.size();
624 word *f = T+2*m_modulus.reg.size();
625 word *g = T+3*m_modulus.reg.size();
626 size_t bcLen=1, fgLen=m_modulus.reg.size();
629 SetWords(T, 0, 3*m_modulus.reg.size());
632 CopyWords(f, a.reg, a.reg.size());
633 CopyWords(g, m_modulus.reg, m_modulus.reg.size());
640 ShiftWordsRightByWords(f, fgLen, 1);
644 ShiftWordsLeftByWords(c, bcLen, 1);
657 if (t==1 && CountWords(f, fgLen)==1)
662 ShiftWordsRightByBits(f, fgLen, 1);
663 t=ShiftWordsLeftByBits(c, bcLen, 1);
667 ShiftWordsRightByBits(f, fgLen, i);
668 t=ShiftWordsLeftByBits(c, bcLen, i);
677 if (f[fgLen-1]==0 && g[fgLen-1]==0)
680 if (f[fgLen-1] < g[fgLen-1])
686 XorWords(f, g, fgLen);
687 XorWords(b, c, bcLen);
690 while (k >= WORD_BITS)
699 for (
unsigned int j=0; j<WORD_BITS-t1; j++)
703 const unsigned int shift = t1 + j;
705 temp ^= (shift < WORD_BITS) ? (((temp >> j) & 1) << shift) : 0;
708 b[t1/WORD_BITS-1] ^= temp << t1%WORD_BITS;
711 b[t1/WORD_BITS] ^= temp >> (WORD_BITS - t1%WORD_BITS);
715 b[t0/WORD_BITS-1] ^= temp << t0%WORD_BITS;
716 b[t0/WORD_BITS] ^= temp >> (WORD_BITS - t0%WORD_BITS);
719 b[t0/WORD_BITS-1] ^= temp;
726 word temp = b[0] << (WORD_BITS - k);
731 for (
unsigned int j=0; j<WORD_BITS-t1; j++)
735 const unsigned int shift = t1 + j;
737 temp ^= (shift < WORD_BITS) ? (((temp >> j) & 1) << shift) : 0;
742 b[t1/WORD_BITS-1] ^= temp << t1%WORD_BITS;
746 b[t1/WORD_BITS] ^= temp >> (WORD_BITS - t1%WORD_BITS);
750 b[t0/WORD_BITS-1] ^= temp << t0%WORD_BITS;
751 b[t0/WORD_BITS] ^= temp >> (WORD_BITS - t0%WORD_BITS);
754 b[t0/WORD_BITS-1] ^= temp;
757 CopyWords(result.reg.
begin(), b, result.reg.
size());
761 const GF2NT::Element& GF2NT::Multiply(
const Element &a,
const Element &b)
const 763 size_t aSize =
STDMIN(a.reg.size(), result.reg.
size());
764 Element r((word)0, m);
766 for (
int i=m-1; i>=0; i--)
770 ShiftWordsLeftByBits(r.reg.begin(), r.reg.size(), 1);
771 XorWords(r.reg.begin(), m_modulus.reg, r.reg.size());
774 ShiftWordsLeftByBits(r.reg.begin(), r.reg.size(), 1);
777 XorWords(r.reg.begin(), a.reg, aSize);
781 r.reg.begin()[r.reg.size()-1] = (word)
Crop(r.reg[r.reg.size()-1], m%WORD_BITS);
783 CopyWords(result.reg.
begin(), r.reg.begin(), result.reg.
size());
787 const GF2NT::Element& GF2NT::Reduced(
const Element &a)
const 789 if (t0-t1 < WORD_BITS)
790 return m_domain.Mod(a, m_modulus);
801 b[i-t0/WORD_BITS] ^= temp >> t0%WORD_BITS;
802 b[i-t0/WORD_BITS-1] ^= temp << (WORD_BITS - t0%WORD_BITS);
805 b[i-t0/WORD_BITS] ^= temp;
807 if ((t0-t1)%WORD_BITS)
809 b[i-(t0-t1)/WORD_BITS] ^= temp >> (t0-t1)%WORD_BITS;
810 b[i-(t0-t1)/WORD_BITS-1] ^= temp << (WORD_BITS - (t0-t1)%WORD_BITS);
813 b[i-(t0-t1)/WORD_BITS] ^= temp;
818 word mask = ((word)1<<(t0%WORD_BITS))-1;
819 word temp = b[i] & ~mask;
822 b[i-t0/WORD_BITS] ^= temp >> t0%WORD_BITS;
824 if ((t0-t1)%WORD_BITS)
826 b[i-(t0-t1)/WORD_BITS] ^= temp >> (t0-t1)%WORD_BITS;
827 if ((t0-t1)%WORD_BITS > t0%WORD_BITS)
828 b[i-(t0-t1)/WORD_BITS-1] ^= temp << (WORD_BITS - (t0-t1)%WORD_BITS);
833 b[i-(t0-t1)/WORD_BITS] ^= temp;
836 SetWords(result.reg.
begin(), 0, result.reg.
size());
843 a.DEREncodeAsOctetString(out, MaxElementByteLength());
848 a.BERDecodeAsOctetString(in, MaxElementByteLength());
854 ASN1::characteristic_two_field().DEREncode(seq);
857 ASN1::tpBasis().DEREncode(parameters);
859 parameters.MessageEnd();
866 ASN1::characteristic_two_field().DEREncode(seq);
869 ASN1::ppBasis().DEREncode(parameters);
874 pentanomial.MessageEnd();
875 parameters.MessageEnd();
884 if (
OID(seq) != ASN1::characteristic_two_field())
890 if (oid == ASN1::tpBasis())
894 result.reset(
new GF2NT(m, t1, 0));
896 else if (oid == ASN1::ppBasis())
898 unsigned int t1, t2, t3;
903 pentanomial.MessageEnd();
904 result.reset(
new GF2NPP(m, t3, t2, t1, 0));
911 parameters.MessageEnd();
914 return result.release();
Element & Accumulate(Element &a, const Element &b) const
const Element & Add(const Element &a, const Element &b) const
An invalid argument was detected.
static const PolynomialMod2 & Zero()
The Zero polinomial.
Randomness Pool based on AES-256.
bool SafeConvert(T1 from, T2 &to)
Tests whether a conversion from -> to is safe to perform.
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.
size_t DEREncodeUnsigned(BufferedTransformation &out, T w, byte asnTag=INTEGER)
DER Encode unsigned value.
virtual void GenerateBlock(byte *output, size_t size)
Generate random array of bytes.
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.
static const PolynomialMod2 & One()
The One polinomial.
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.
static PolynomialMod2 Monomial(size_t i)
Provides x^i.
const Element & Square(const Element &a) const
Classes for performing mathematics over different fields.
bool IsIrreducible() const
check for irreducibility
unsigned int WordCount() const
number of significant words = ceiling(ByteCount()/sizeof(word))
Polynomial with Coefficients in GF(2)
unsigned int BitCount() const
number of significant bits = Degree() + 1
Excpetion thrown when divide by zero is encountered.
static PolynomialMod2 Gcd(const PolynomialMod2 &a, const PolynomialMod2 &n)
greatest common divisor
Copy input to a memory buffer.
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.
Classes and functions for schemes over GF(2^n)
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.
void SetByte(size_t n, byte value)
set the n-th byte to 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.
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.
static PolynomialMod2 AllOnes(size_t n)
Provides x^(n-1) + ...
GF(2^n) with Polynomial Basis.
PolynomialMod2 InverseMod(const PolynomialMod2 &) const
calculate multiplicative inverse of *this mod n
void DEREncodeAsOctetString(BufferedTransformation &bt, size_t length) const
encode value as big-endian octet string
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))
unsigned int ByteCount() const
number of significant bytes = ceiling(BitCount()/8)
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
Calculate the multiplicative inverse of an element in the group.
static PolynomialMod2 Trinomial(size_t t0, size_t t1, size_t t2)
Provides x^t0 + x^t1 + x^t2.
unsigned int Parity() const
sum modulo 2 of all coefficients
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.
unsigned int BitPrecision(const T &value)
Returns the number of bits required for a value.
const T & Ref(...) const
Return a reference to the inner Singleton object.
size_type size() const
Provides the count of elements in the SecBlock.
#define SIZE_MAX
The maximum value of a machine word.