6 #ifndef CRYPTOPP_IMPORTS
21 NAMESPACE_BEGIN(CryptoPP)
35 SetWords(reg+1, 0, reg.
size()-1);
42 CopyWords(reg, t.reg, reg.
size());
47 const size_t nbytes = nbits/8 + 1;
50 buf[0] = (byte)
Crop(buf[0], nbits % 8);
58 if (bitLength%WORD_BITS)
59 result.reg[result.reg.
size()-1] = (word)
Crop(result.reg[result.reg.
size()-1], bitLength%WORD_BITS);
63 void PolynomialMod2::SetBit(
size_t n,
int value)
68 reg[n/WORD_BITS] |= (word(1) << (n%WORD_BITS));
72 if (n/WORD_BITS < reg.
size())
73 reg[n/WORD_BITS] &= ~(word(1) << (n%WORD_BITS));
79 if (n/WORD_SIZE >= reg.
size())
82 return byte(reg[n/WORD_SIZE] >> ((n%WORD_SIZE)*8));
88 reg[n/WORD_SIZE] &= ~(word(0xff) << 8*(n%WORD_SIZE));
89 reg[n/WORD_SIZE] |= (word(value) << 8*(n%WORD_SIZE));
138 void PolynomialMod2::Decode(
const byte *input,
size_t inputLen)
141 Decode(store, inputLen);
154 for (
size_t i=inputLen; i > 0; i--)
158 reg[(i-1)/WORD_SIZE] |= word(b) << ((i-1)%WORD_SIZE)*8;
164 for (
size_t i=outputLen; i > 0; i--)
178 if (!dec.IsDefiniteLength() || dec.RemainingLength() != length)
186 return (
unsigned int)CountWords(reg, reg.
size());
193 return (wordCount-1)*WORD_SIZE +
BytePrecision(reg[wordCount-1]);
202 return (wordCount-1)*WORD_BITS +
BitPrecision(reg[wordCount-1]);
211 for (i=0; i<reg.
size(); i++)
225 XorWords(reg, t.reg, t.reg.
size());
234 XorWords(result.reg, reg, b.reg, reg.
size());
235 CopyWords(result.reg+reg.
size(), b.reg+reg.
size(), b.reg.
size()-reg.
size());
241 XorWords(result.reg, reg, b.reg, b.reg.
size());
242 CopyWords(result.reg+b.reg.
size(), reg+b.reg.
size(), reg.
size()-b.reg.
size());
250 AndWords(result.reg, reg, b.reg, result.reg.
size());
258 for (
int i=b.
Degree(); i>=0; i--)
262 XorWords(result.reg, reg, reg.
size());
269 static const word map[16] = {0, 1, 4, 5, 16, 17, 20, 21, 64, 65, 68, 69, 80, 81, 84, 85};
273 for (
unsigned i=0; i<reg.
size(); i++)
277 for (j=0; j<WORD_BITS; j+=8)
278 result.reg[2*i] |= map[(reg[i] >> (j/2)) % 16] << j;
280 for (j=0; j<WORD_BITS; j+=8)
281 result.reg[2*i+1] |= map[(reg[i] >> (j/2 + WORD_BITS/2)) % 16] << j;
293 int degree = divisor.
Degree();
300 for (
int i=dividend.
Degree(); i>=0; i--)
303 remainder.reg[0] |= dividend[i];
304 if (remainder[degree])
306 remainder -= divisor;
329 int x; CRYPTOPP_UNUSED(x);
347 *r = (u << 1) | carry;
348 carry = u >> (WORD_BITS-1);
355 reg[reg.
size()-1] = carry;
361 const int shiftWords = n / WORD_BITS;
362 const int shiftBits = n % WORD_BITS;
370 *r = (u << shiftBits) | carry;
371 carry = u >> (WORD_BITS-shiftBits);
379 const size_t carryIndex = reg.
size();
380 reg.
Grow(reg.
size()+shiftWords+!!shiftBits);
381 reg[carryIndex] = carry;
388 for (i = (
int)reg.
size()-1; i>=shiftWords; i--)
389 reg[i] = reg[i-shiftWords];
402 int shiftWords = n / WORD_BITS;
403 int shiftBits = n % WORD_BITS;
408 word *r=reg+reg.
size()-1;
416 *r = (u >> shiftBits) | carry;
417 carry = u << (WORD_BITS-shiftBits);
424 for (i=0; i<reg.
size()-shiftWords; i++)
425 reg[i] = reg[i+shiftWords];
426 for (; i<reg.
size(); i++)
445 bool PolynomialMod2::operator!()
const
447 for (
unsigned i=0; i<reg.
size(); i++)
448 if (reg[i])
return false;
456 for (i=0; i<smallerSize; i++)
457 if (reg[i] != rhs.reg[i])
return false;
459 for (i=smallerSize; i<reg.
size(); i++)
460 if (reg[i] != 0)
return false;
462 for (i=smallerSize; i<rhs.reg.
size(); i++)
463 if (rhs.reg[i] != 0)
return false;
468 std::ostream& operator<<(std::ostream& out,
const PolynomialMod2 &a)
471 long f = out.flags() & std::ios::basefield;
493 return out <<
'0' << suffix;
498 static const char upper[]=
"0123456789ABCDEF";
499 static const char lower[]=
"0123456789abcdef";
500 const char* vec = (out.flags() & std::ios::uppercase) ? upper : lower;
502 for (i=0; i*bits < a.
BitCount(); i++)
505 for (
int j=0; j<bits; j++)
506 digit |= a[i*bits+j] << j;
513 if (i && (i%block)==0)
517 return out << suffix;
538 for (
int i=1; i<=d/2; i++)
540 u = u.Squared()%(*this);
554 GF2NP::Element GF2NP::SquareRoot(
const Element &a)
const
557 for (
unsigned int i=1; i<m; i++)
562 GF2NP::Element GF2NP::HalfTrace(
const Element &a)
const
566 for (
unsigned int i=1; i<=(m-1)/2; i++)
571 GF2NP::Element GF2NP::SolveQuadraticEquation(
const Element &a)
const
580 z = PolynomialMod2::Zero();
582 for (
unsigned int i=1; i<=m-1; i++)
589 }
while (w.IsZero());
598 GF2NT::GF2NT(
unsigned int c0,
unsigned int c1,
unsigned int c2)
608 if (t0-t1 < WORD_BITS)
613 word *c = T+m_modulus.reg.size();
614 word *f = T+2*m_modulus.reg.size();
615 word *g = T+3*m_modulus.reg.size();
616 size_t bcLen=1, fgLen=m_modulus.reg.size();
619 SetWords(T, 0, 3*m_modulus.reg.size());
622 CopyWords(f, a.reg, a.reg.size());
623 CopyWords(g, m_modulus.reg, m_modulus.reg.size());
630 ShiftWordsRightByWords(f, fgLen, 1);
634 ShiftWordsLeftByWords(c, bcLen, 1);
647 if (t==1 && CountWords(f, fgLen)==1)
652 ShiftWordsRightByBits(f, fgLen, 1);
653 t=ShiftWordsLeftByBits(c, bcLen, 1);
657 ShiftWordsRightByBits(f, fgLen, i);
658 t=ShiftWordsLeftByBits(c, bcLen, i);
667 if (f[fgLen-1]==0 && g[fgLen-1]==0)
670 if (f[fgLen-1] < g[fgLen-1])
676 XorWords(f, g, fgLen);
677 XorWords(b, c, bcLen);
680 while (k >= WORD_BITS)
689 for (
unsigned int j=0; j<WORD_BITS-t1; j++)
693 const unsigned int shift = t1 + j;
695 temp ^= (shift < WORD_BITS) ? (((temp >> j) & 1) << shift) : 0;
698 b[t1/WORD_BITS-1] ^= temp << t1%WORD_BITS;
701 b[t1/WORD_BITS] ^= temp >> (WORD_BITS - t1%WORD_BITS);
705 b[t0/WORD_BITS-1] ^= temp << t0%WORD_BITS;
706 b[t0/WORD_BITS] ^= temp >> (WORD_BITS - t0%WORD_BITS);
709 b[t0/WORD_BITS-1] ^= temp;
716 word temp = b[0] << (WORD_BITS - k);
721 for (
unsigned int j=0; j<WORD_BITS-t1; j++)
725 const unsigned int shift = t1 + j;
727 temp ^= (shift < WORD_BITS) ? (((temp >> j) & 1) << shift) : 0;
732 b[t1/WORD_BITS-1] ^= temp << t1%WORD_BITS;
736 b[t1/WORD_BITS] ^= temp >> (WORD_BITS - t1%WORD_BITS);
740 b[t0/WORD_BITS-1] ^= temp << t0%WORD_BITS;
741 b[t0/WORD_BITS] ^= temp >> (WORD_BITS - t0%WORD_BITS);
744 b[t0/WORD_BITS-1] ^= temp;
747 CopyWords(result.reg.
begin(), b, result.reg.
size());
753 size_t aSize =
STDMIN(a.reg.size(), result.reg.
size());
754 Element r((word)0, m);
756 for (
int i=m-1; i>=0; i--)
760 ShiftWordsLeftByBits(r.reg.begin(), r.reg.size(), 1);
761 XorWords(r.reg.begin(), m_modulus.reg, r.reg.size());
764 ShiftWordsLeftByBits(r.reg.begin(), r.reg.size(), 1);
767 XorWords(r.reg.begin(), a.reg, aSize);
771 r.reg.begin()[r.reg.size()-1] = (word)
Crop(r.reg[r.reg.size()-1], m%WORD_BITS);
773 CopyWords(result.reg.
begin(), r.reg.begin(), result.reg.
size());
777 const GF2NT::Element& GF2NT::Reduced(
const Element &a)
const
779 if (t0-t1 < WORD_BITS)
780 return m_domain.Mod(a, m_modulus);
791 b[i-t0/WORD_BITS] ^= temp >> t0%WORD_BITS;
792 b[i-t0/WORD_BITS-1] ^= temp << (WORD_BITS - t0%WORD_BITS);
795 b[i-t0/WORD_BITS] ^= temp;
797 if ((t0-t1)%WORD_BITS)
799 b[i-(t0-t1)/WORD_BITS] ^= temp >> (t0-t1)%WORD_BITS;
800 b[i-(t0-t1)/WORD_BITS-1] ^= temp << (WORD_BITS - (t0-t1)%WORD_BITS);
803 b[i-(t0-t1)/WORD_BITS] ^= temp;
808 word mask = ((word)1<<(t0%WORD_BITS))-1;
809 word temp = b[i] & ~mask;
812 b[i-t0/WORD_BITS] ^= temp >> t0%WORD_BITS;
814 if ((t0-t1)%WORD_BITS)
816 b[i-(t0-t1)/WORD_BITS] ^= temp >> (t0-t1)%WORD_BITS;
817 if ((t0-t1)%WORD_BITS > t0%WORD_BITS)
818 b[i-(t0-t1)/WORD_BITS-1] ^= temp << (WORD_BITS - (t0-t1)%WORD_BITS);
823 b[i-(t0-t1)/WORD_BITS] ^= temp;
826 SetWords(result.reg.
begin(), 0, result.reg.
size());
833 a.DEREncodeAsOctetString(out, MaxElementByteLength());
838 a.BERDecodeAsOctetString(in, MaxElementByteLength());
844 ASN1::characteristic_two_field().DEREncode(seq);
847 ASN1::tpBasis().DEREncode(parameters);
849 parameters.MessageEnd();
856 ASN1::characteristic_two_field().DEREncode(seq);
859 ASN1::ppBasis().DEREncode(parameters);
864 pentanomial.MessageEnd();
865 parameters.MessageEnd();
874 if (
OID(seq) != ASN1::characteristic_two_field())
880 if (oid == ASN1::tpBasis())
884 result.reset(
new GF2NT(m, t1, 0));
886 else if (oid == ASN1::ppBasis())
888 unsigned int t1, t2, t3;
893 pentanomial.MessageEnd();
894 result.reset(
new GF2NPP(m, t3, t2, t1, 0));
901 parameters.MessageEnd();
904 return result.release();
bool IsIrreducible() const
check for irreducibility
Randomness Pool based on AES-256.
bool SafeConvert(T1 from, T2 &to)
Tests whether a conversion from -> to is safe to perform.
void DEREncodeAsOctetString(BufferedTransformation &bt, size_t length) const
encode value as big-endian octet string
Utility functions for the Crypto++ library.
PolynomialMod2()
creates the zero polynomial
Restricts the instantiation of a class to one static object without locks.
const Element & MultiplicativeInverse(const Element &a) const
Calculate the multiplicative inverse of an element in the group.
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.
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.
const Element & Square(const Element &a) const
Square an element in the group.
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.
unsigned int ByteCount() const
number of significant bytes = ceiling(BitCount()/8)
signed int Degree() const
the zero polynomial will return a degree of -1
const Element & Multiply(const Element &a, const Element &b) const
Multiplies elements in the group.
size_type size() const
Provides the count of elements in the SecBlock.
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.
byte GetByte(size_t n) const
return the n-th byte
static PolynomialMod2 Monomial(size_t i)
return x^i
SecBlock<byte> typedef.
Element & Accumulate(Element &a, const Element &b) const
TODO.
Classes for performing mathematics over different fields.
Polynomial with Coefficients in GF(2)
PolynomialMod2 MultiplicativeInverse() const
return inverse if *this is a unit, otherwise return 0
unsigned int BitCount() const
number of significant bits = Degree() + 1
static PolynomialMod2 Gcd(const PolynomialMod2 &a, const PolynomialMod2 &n)
greatest common divisor
Copy input to a memory buffer.
const Element & Add(const Element &a, const Element &b) const
Adds elements in the group.
bool IsUnit() const
only 1 is a unit
T Crop(T value, size_t bits)
Truncates the value to the specified number of bits.
const Element & Multiply(const Element &a, const Element &b) const
Multiplies elements in the group.
void Assign(const T *ptr, size_type len)
Set contents and size from an array.
void Encode(byte *output, size_t outputLen) const
encode in big-endian format
const Element & MultiplicativeInverse(const Element &a) const
Calculate the multiplicative inverse of an element in the group.
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
unsigned int WordCount() const
number of significant words = ceiling(ByteCount()/sizeof(word))
void BERDecodeError()
Raises a BERDecodeErr.
void BERDecodeUnsigned(BufferedTransformation &in, T &w, byte asnTag=INTEGER, T minValue=0, T maxValue=((std::numeric_limits< T >::max)()))
BER Decode unsigned value.
Classes and functions for working with ANS.1 objects.
PolynomialMod2 InverseMod(const PolynomialMod2 &) const
calculate multiplicative inverse of *this mod n
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)
return x^(n-1) + ... + x + 1
GF(2^n) with Polynomial Basis.
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))
void Grow(size_type newSize)
Change size and preserve contents.
void BERDecodeAsOctetString(BufferedTransformation &bt, size_t length)
decode value as big-endian octet string
unsigned int Parity() const
sum modulo 2 of all coefficients
static PolynomialMod2 Trinomial(size_t t0, size_t t1, size_t t2)
return x^t0 + x^t1 + x^t2
static PolynomialMod2 Pentanomial(size_t t0, size_t t1, size_t t2, size_t t3, size_t t4)
return x^t0 + x^t1 + x^t2 + x^t3 + x^t4
SecBlock<word> typedef.
unsigned int BitPrecision(const T &value)
Returns the number of bits required for a value.
#define SIZE_MAX
The maximum value of a machine word.