gf2n.cpp
// gf2n.cpp - originally written and placed in the public domain by Wei Dai
#include "pch.h"
#include "config.h"
#ifndef CRYPTOPP_IMPORTS
#include "cryptlib.h"
#include "algebra.h"
#include "randpool.h"
#include "filters.h"
#include "smartptr.h"
#include "words.h"
#include "misc.h"
#include "gf2n.h"
#include "oids.h"
#include "asn.h"
#include "cpu.h"
#include <iostream>
ANONYMOUS_NAMESPACE_BEGIN
using CryptoPP::PolynomialMod2;
#if defined(HAVE_GCC_INIT_PRIORITY)
const PolynomialMod2 g_zero __attribute__ ((init_priority (CRYPTOPP_INIT_PRIORITY + 60))) = PolynomialMod2();
const PolynomialMod2 g_one __attribute__ ((init_priority (CRYPTOPP_INIT_PRIORITY + 61))) = PolynomialMod2(1);
#elif defined(HAVE_MSC_INIT_PRIORITY)
#pragma warning(disable: 4075)
#pragma init_seg(".CRT$XCU")
const PolynomialMod2 g_zero;
const PolynomialMod2 g_one(1);
#pragma warning(default: 4075)
#elif defined(HAVE_XLC_INIT_PRIORITY)
#pragma priority(290)
const PolynomialMod2 g_zero;
const PolynomialMod2 g_one(1);
#endif
ANONYMOUS_NAMESPACE_END
NAMESPACE_BEGIN(CryptoPP)
#if (CRYPTOPP_CLMUL_AVAILABLE)
extern CRYPTOPP_DLL void GF2NT_233_Multiply_Reduce_CLMUL(const word* pA, const word* pB, word* pC);
extern CRYPTOPP_DLL void GF2NT_233_Square_Reduce_CLMUL(const word* pA, word* pC);
#endif
#if (CRYPTOPP_ARM_PMULL_AVAILABLE)
extern void GF2NT_233_Multiply_Reduce_ARMv8(const word* pA, const word* pB, word* pC);
extern void GF2NT_233_Square_Reduce_ARMv8(const word* pA, word* pC);
#endif
#if (CRYPTOPP_POWER8_VMULL_AVAILABLE) && 0
extern void GF2NT_233_Multiply_Reduce_POWER8(const word* pA, const word* pB, word* pC);
extern void GF2NT_233_Square_Reduce_POWER8(const word* pA, word* pC);
#endif
PolynomialMod2::PolynomialMod2()
{
}
PolynomialMod2::PolynomialMod2(word value, size_t bitLength)
: reg(BitsToWords(bitLength))
{
CRYPTOPP_ASSERT(value==0 || reg.size()>0);
if (reg.size() > 0)
{
reg[0] = value;
SetWords(reg+1, 0, reg.size()-1);
}
}
PolynomialMod2::PolynomialMod2(const PolynomialMod2& t)
: reg(t.reg.size())
{
CopyWords(reg, t.reg, reg.size());
}
void PolynomialMod2::Randomize(RandomNumberGenerator &rng, size_t nbits)
{
const size_t nbytes = nbits/8 + 1;
SecByteBlock buf(nbytes);
rng.GenerateBlock(buf, nbytes);
buf[0] = (byte)Crop(buf[0], nbits % 8);
Decode(buf, nbytes);
}
PolynomialMod2 PolynomialMod2::AllOnes(size_t bitLength)
{
PolynomialMod2 result((word)0, bitLength);
SetWords(result.reg, ~(word(0)), result.reg.size());
if (bitLength%WORD_BITS)
result.reg[result.reg.size()-1] = (word)Crop(result.reg[result.reg.size()-1], bitLength%WORD_BITS);
return result;
}
void PolynomialMod2::SetBit(size_t n, int value)
{
if (value)
{
reg.CleanGrow(n/WORD_BITS + 1);
reg[n/WORD_BITS] |= (word(1) << (n%WORD_BITS));
}
else
{
if (n/WORD_BITS < reg.size())
reg[n/WORD_BITS] &= ~(word(1) << (n%WORD_BITS));
}
}
byte PolynomialMod2::GetByte(size_t n) const
{
if (n/WORD_SIZE >= reg.size())
return 0;
else
return byte(reg[n/WORD_SIZE] >> ((n%WORD_SIZE)*8));
}
void PolynomialMod2::SetByte(size_t n, byte value)
{
reg.CleanGrow(BytesToWords(n+1));
reg[n/WORD_SIZE] &= ~(word(0xff) << 8*(n%WORD_SIZE));
reg[n/WORD_SIZE] |= (word(value) << 8*(n%WORD_SIZE));
}
PolynomialMod2 PolynomialMod2::Monomial(size_t i)
{
PolynomialMod2 r((word)0, i+1);
r.SetBit(i);
return r;
}
PolynomialMod2 PolynomialMod2::Trinomial(size_t t0, size_t t1, size_t t2)
{
// Asserts and checks due to Bing Shi
CRYPTOPP_ASSERT(t0 > t1);
CRYPTOPP_ASSERT(t1 > t2);
// The test is odd because of ECIES<EC2N>. The basis is t0, but the other coefficients are not in descending order.
if (t1 > t0 || t2 > t0)
throw InvalidArgument("PolynomialMod2: coefficients must be in descending order");
PolynomialMod2 r((word)0, t0+1);
r.SetBit(t0);
r.SetBit(t1);
r.SetBit(t2);
return r;
}
PolynomialMod2 PolynomialMod2::Pentanomial(size_t t0, size_t t1, size_t t2, size_t t3, size_t t4)
{
// Asserts and checks due to Bing Shi
CRYPTOPP_ASSERT(t0 > t1);
CRYPTOPP_ASSERT(t1 > t2);
CRYPTOPP_ASSERT(t2 > t3);
CRYPTOPP_ASSERT(t3 > t4);
// The test is odd because of ECIES<EC2N>. The basis is t0, but the other coefficients are not in descending order.
if (t1 > t0 || t2 > t0 || t3 > t0 || t4 > t0)
throw InvalidArgument("PolynomialMod2: coefficients must be in descending order");
PolynomialMod2 r((word)0, t0+1);
r.SetBit(t0);
r.SetBit(t1);
r.SetBit(t2);
r.SetBit(t3);
r.SetBit(t4);
return r;
}
template <word i>
struct NewPolynomialMod2
{
PolynomialMod2 * operator()() const
{
return new PolynomialMod2(i);
}
};
const PolynomialMod2 &PolynomialMod2::Zero()
{
#if defined(HAVE_GCC_INIT_PRIORITY) || defined(HAVE_MSC_INIT_PRIORITY) || defined(HAVE_XLC_INIT_PRIORITY)
return g_zero;
#elif defined(CRYPTOPP_CXX11_STATIC_INIT)
static const PolynomialMod2 g_zero;
return g_zero;
#else
return Singleton<PolynomialMod2>().Ref();
#endif
}
const PolynomialMod2 &PolynomialMod2::One()
{
#if defined(HAVE_GCC_INIT_PRIORITY) || defined(HAVE_MSC_INIT_PRIORITY) || defined(HAVE_XLC_INIT_PRIORITY)
return g_one;
#elif defined(CRYPTOPP_CXX11_STATIC_INIT)
static const PolynomialMod2 g_one(1);
return g_one;
#else
return Singleton<PolynomialMod2, NewPolynomialMod2<1> >().Ref();
#endif
}
void PolynomialMod2::Decode(const byte *input, size_t inputLen)
{
StringStore store(input, inputLen);
Decode(store, inputLen);
}
void PolynomialMod2::Encode(byte *output, size_t outputLen) const
{
ArraySink sink(output, outputLen);
Encode(sink, outputLen);
}
void PolynomialMod2::Decode(BufferedTransformation &bt, size_t inputLen)
{
CRYPTOPP_ASSERT(bt.MaxRetrievable() >= inputLen);
if (bt.MaxRetrievable() < inputLen)
throw InvalidArgument("PolynomialMod2: input length is too small");
reg.CleanNew(BytesToWords(inputLen));
for (size_t i=inputLen; i > 0; i--)
{
byte b;
(void)bt.Get(b);
reg[(i-1)/WORD_SIZE] |= word(b) << ((i-1)%WORD_SIZE)*8;
}
}
void PolynomialMod2::Encode(BufferedTransformation &bt, size_t outputLen) const
{
for (size_t i=outputLen; i > 0; i--)
bt.Put(GetByte(i-1));
}
void PolynomialMod2::DEREncodeAsOctetString(BufferedTransformation &bt, size_t length) const
{
DERGeneralEncoder enc(bt, OCTET_STRING);
Encode(enc, length);
enc.MessageEnd();
}
void PolynomialMod2::BERDecodeAsOctetString(BufferedTransformation &bt, size_t length)
{
BERGeneralDecoder dec(bt, OCTET_STRING);
if (!dec.IsDefiniteLength() || dec.RemainingLength() != length)
BERDecodeError();
Decode(dec, length);
dec.MessageEnd();
}
unsigned int PolynomialMod2::WordCount() const
{
return (unsigned int)CountWords(reg, reg.size());
}
unsigned int PolynomialMod2::ByteCount() const
{
unsigned wordCount = WordCount();
if (wordCount)
return (wordCount-1)*WORD_SIZE + BytePrecision(reg[wordCount-1]);
else
return 0;
}
unsigned int PolynomialMod2::BitCount() const
{
unsigned wordCount = WordCount();
if (wordCount)
return (wordCount-1)*WORD_BITS + BitPrecision(reg[wordCount-1]);
else
return 0;
}
unsigned int PolynomialMod2::Parity() const
{
unsigned i;
word temp=0;
for (i=0; i<reg.size(); i++)
temp ^= reg[i];
return CryptoPP::Parity(temp);
}
PolynomialMod2& PolynomialMod2::operator=(const PolynomialMod2& t)
{
reg.Assign(t.reg);
return *this;
}
PolynomialMod2& PolynomialMod2::operator^=(const PolynomialMod2& t)
{
reg.CleanGrow(t.reg.size());
XorWords(reg, t.reg, t.reg.size());
return *this;
}
PolynomialMod2 PolynomialMod2::Xor(const PolynomialMod2 &b) const
{
if (b.reg.size() >= reg.size())
{
PolynomialMod2 result((word)0, b.reg.size()*WORD_BITS);
XorWords(result.reg, reg, b.reg, reg.size());
CopyWords(result.reg+reg.size(), b.reg+reg.size(), b.reg.size()-reg.size());
return result;
}
else
{
PolynomialMod2 result((word)0, reg.size()*WORD_BITS);
XorWords(result.reg, reg, b.reg, b.reg.size());
CopyWords(result.reg+b.reg.size(), reg+b.reg.size(), reg.size()-b.reg.size());
return result;
}
}
PolynomialMod2 PolynomialMod2::And(const PolynomialMod2 &b) const
{
PolynomialMod2 result((word)0, WORD_BITS*STDMIN(reg.size(), b.reg.size()));
AndWords(result.reg, reg, b.reg, result.reg.size());
return result;
}
PolynomialMod2 PolynomialMod2::Times(const PolynomialMod2 &b) const
{
PolynomialMod2 result((word)0, BitCount() + b.BitCount());
for (int i=b.Degree(); i>=0; i--)
{
result <<= 1;
if (b[i])
XorWords(result.reg, reg, reg.size());
}
return result;
}
PolynomialMod2 PolynomialMod2::Squared() const
{
static const word map[16] = {0, 1, 4, 5, 16, 17, 20, 21, 64, 65, 68, 69, 80, 81, 84, 85};
PolynomialMod2 result((word)0, 2*reg.size()*WORD_BITS);
for (unsigned i=0; i<reg.size(); i++)
{
unsigned j;
for (j=0; j<WORD_BITS; j+=8)
result.reg[2*i] |= map[(reg[i] >> (j/2)) % 16] << j;
for (j=0; j<WORD_BITS; j+=8)
result.reg[2*i+1] |= map[(reg[i] >> (j/2 + WORD_BITS/2)) % 16] << j;
}
return result;
}
void PolynomialMod2::Divide(PolynomialMod2 &remainder, PolynomialMod2 &quotient,
const PolynomialMod2 &dividend, const PolynomialMod2 &divisor)
{
if (!divisor)
throw PolynomialMod2::DivideByZero();
int degree = divisor.Degree();
remainder.reg.CleanNew(BitsToWords(degree+1));
if (dividend.BitCount() >= divisor.BitCount())
quotient.reg.CleanNew(BitsToWords(dividend.BitCount() - divisor.BitCount() + 1));
else
quotient.reg.CleanNew(0);
for (int i=dividend.Degree(); i>=0; i--)
{
remainder <<= 1;
remainder.reg[0] |= dividend[i];
if (remainder[degree])
{
remainder -= divisor;
quotient.SetBit(i);
}
}
}
PolynomialMod2 PolynomialMod2::DividedBy(const PolynomialMod2 &b) const
{
PolynomialMod2 remainder, quotient;
PolynomialMod2::Divide(remainder, quotient, *this, b);
return quotient;
}
PolynomialMod2 PolynomialMod2::Modulo(const PolynomialMod2 &b) const
{
PolynomialMod2 remainder, quotient;
PolynomialMod2::Divide(remainder, quotient, *this, b);
return remainder;
}
PolynomialMod2& PolynomialMod2::operator<<=(unsigned int n)
{
#if defined(CRYPTOPP_DEBUG)
int x=0; CRYPTOPP_UNUSED(x);
CRYPTOPP_ASSERT(SafeConvert(n,x));
#endif
if (!reg.size())
return *this;
int i;
word u;
word carry=0;
word *r=reg;
if (n==1) // special case code for most frequent case
{
i = (int)reg.size();
while (i--)
{
u = *r;
*r = (u << 1) | carry;
carry = u >> (WORD_BITS-1);
r++;
}
if (carry)
{
reg.Grow(reg.size()+1);
reg[reg.size()-1] = carry;
}
return *this;
}
const int shiftWords = n / WORD_BITS;
const int shiftBits = n % WORD_BITS;
if (shiftBits)
{
i = (int)reg.size();
while (i--)
{
u = *r;
*r = (u << shiftBits) | carry;
carry = u >> (WORD_BITS-shiftBits);
r++;
}
}
if (carry)
{
// Thanks to Apatryda, http://github.com/weidai11/cryptopp/issues/64
const size_t carryIndex = reg.size();
reg.Grow(reg.size()+shiftWords+!!shiftBits);
reg[carryIndex] = carry;
}
else
reg.Grow(reg.size()+shiftWords);
if (shiftWords)
{
for (i = (int)reg.size()-1; i>=shiftWords; i--)
reg[i] = reg[i-shiftWords];
for (; i>=0; i--)
reg[i] = 0;
}
return *this;
}
PolynomialMod2& PolynomialMod2::operator>>=(unsigned int n)
{
if (!reg.size())
return *this;
int shiftWords = n / WORD_BITS;
int shiftBits = n % WORD_BITS;
size_t i;
word u;
word carry=0;
word *r=reg+reg.size()-1;
if (shiftBits)
{
i = reg.size();
while (i--)
{
u = *r;
*r = (u >> shiftBits) | carry;
carry = u << (WORD_BITS-shiftBits);
r--;
}
}
if (shiftWords)
{
for (i=0; i<reg.size()-shiftWords; i++)
reg[i] = reg[i+shiftWords];
for (; i<reg.size(); i++)
reg[i] = 0;
}
return *this;
}
PolynomialMod2 PolynomialMod2::operator<<(unsigned int n) const
{
PolynomialMod2 result(*this);
return result<<=n;
}
PolynomialMod2 PolynomialMod2::operator>>(unsigned int n) const
{
PolynomialMod2 result(*this);
return result>>=n;
}
bool PolynomialMod2::operator!() const
{
for (unsigned i=0; i<reg.size(); i++)
if (reg[i]) return false;
return true;
}
bool PolynomialMod2::Equals(const PolynomialMod2 &rhs) const
{
size_t i, smallerSize = STDMIN(reg.size(), rhs.reg.size());
for (i=0; i<smallerSize; i++)
if (reg[i] != rhs.reg[i]) return false;
for (i=smallerSize; i<reg.size(); i++)
if (reg[i] != 0) return false;
for (i=smallerSize; i<rhs.reg.size(); i++)
if (rhs.reg[i] != 0) return false;
return true;
}
std::ostream& operator<<(std::ostream& out, const PolynomialMod2 &a)
{
// Get relevant conversion specifications from ostream.
long f = out.flags() & std::ios::basefield; // Get base digits.
int bits, block;
char suffix;
switch(f)
{
case std::ios::oct :
bits = 3;
block = 4;
suffix = 'o';
break;
case std::ios::hex :
bits = 4;
block = 2;
suffix = 'h';
break;
default :
bits = 1;
block = 8;
suffix = 'b';
}
if (!a)
return out << '0' << suffix;
SecBlock<char> s(a.BitCount()/bits+1);
unsigned i;
static const char upper[]="0123456789ABCDEF";
static const char lower[]="0123456789abcdef";
const char* const vec = (out.flags() & std::ios::uppercase) ? upper : lower;
for (i=0; i*bits < a.BitCount(); i++)
{
int digit=0;
for (int j=0; j<bits; j++)
digit |= a[i*bits+j] << j;
s[i]=vec[digit];
}
while (i--)
{
out << s[i];
if (i && (i%block)==0)
out << ',';
}
return out << suffix;
}
PolynomialMod2 PolynomialMod2::Gcd(const PolynomialMod2 &a, const PolynomialMod2 &b)
{
return EuclideanDomainOf<PolynomialMod2>().Gcd(a, b);
}
PolynomialMod2 PolynomialMod2::InverseMod(const PolynomialMod2 &modulus) const
{
typedef EuclideanDomainOf<PolynomialMod2> Domain;
return QuotientRing<Domain>(Domain(), modulus).MultiplicativeInverse(*this);
}
bool PolynomialMod2::IsIrreducible() const
{
signed int d = Degree();
if (d <= 0)
return false;
PolynomialMod2 t(2), u(t);
for (int i=1; i<=d/2; i++)
{
u = u.Squared()%(*this);
if (!Gcd(u+t, *this).IsUnit())
return false;
}
return true;
}
// ********************************************************
GF2NP::GF2NP(const PolynomialMod2 &modulus)
: QuotientRing<EuclideanDomainOf<PolynomialMod2> >(EuclideanDomainOf<PolynomialMod2>(), modulus), m(modulus.Degree())
{
}
GF2NP::Element GF2NP::SquareRoot(const Element &a) const
{
Element r = a;
for (unsigned int i=1; i<m; i++)
r = Square(r);
return r;
}
GF2NP::Element GF2NP::HalfTrace(const Element &a) const
{
CRYPTOPP_ASSERT(m%2 == 1);
Element h = a;
for (unsigned int i=1; i<=(m-1)/2; i++)
h = Add(Square(Square(h)), a);
return h;
}
GF2NP::Element GF2NP::SolveQuadraticEquation(const Element &a) const
{
if (m%2 == 0)
{
Element z, w;
RandomPool rng;
do
{
Element p((RandomNumberGenerator &)rng, m);
z = PolynomialMod2::Zero();
w = p;
for (unsigned int i=1; i<=m-1; i++)
{
w = Square(w);
z = Square(z);
Accumulate(z, Multiply(w, a));
Accumulate(w, p);
}
} while (w.IsZero());
return z;
}
else
return HalfTrace(a);
}
// ********************************************************
GF2NT::GF2NT(unsigned int c0, unsigned int c1, unsigned int c2)
: GF2NP(PolynomialMod2::Trinomial(c0, c1, c2))
, t0(c0), t1(c1)
, result((word)0, m)
{
// Asserts and checks due to Bing Shi
CRYPTOPP_ASSERT(c0 > c1 && c1 > c2 && c2==0);
// The test is odd because of ECIES<EC2N>. The basis is c0, but the other coefficients are not in descending order.
if (c1 > c0 || c2 > c0)
throw InvalidArgument("GF2NT: coefficients must be in descending order");
}
const GF2NT::Element& GF2NT::MultiplicativeInverse(const Element &a) const
{
if (t0-t1 < WORD_BITS)
return GF2NP::MultiplicativeInverse(a);
SecWordBlock T(m_modulus.reg.size() * 4);
word *b = T;
word *c = T+m_modulus.reg.size();
word *f = T+2*m_modulus.reg.size();
word *g = T+3*m_modulus.reg.size();
size_t bcLen=1, fgLen=m_modulus.reg.size();
unsigned int k=0;
SetWords(T, 0, 3*m_modulus.reg.size());
b[0]=1;
CRYPTOPP_ASSERT(a.reg.size() <= m_modulus.reg.size());
CopyWords(f, a.reg, a.reg.size());
CopyWords(g, m_modulus.reg, m_modulus.reg.size());
while (1)
{
word t=f[0];
while (!t)
{
ShiftWordsRightByWords(f, fgLen, 1);
if (c[bcLen-1])
bcLen++;
CRYPTOPP_ASSERT(bcLen <= m_modulus.reg.size());
ShiftWordsLeftByWords(c, bcLen, 1);
k+=WORD_BITS;
t=f[0];
}
unsigned int i=0;
while (t%2 == 0)
{
t>>=1;
i++;
}
k+=i;
if (t==1 && CountWords(f, fgLen)==1)
break;
if (i==1)
{
ShiftWordsRightByBits(f, fgLen, 1);
t=ShiftWordsLeftByBits(c, bcLen, 1);
}
else
{
ShiftWordsRightByBits(f, fgLen, i);
t=ShiftWordsLeftByBits(c, bcLen, i);
}
if (t)
{
c[bcLen] = t;
bcLen++;
CRYPTOPP_ASSERT(bcLen <= m_modulus.reg.size());
}
if (f[fgLen-1]==0 && g[fgLen-1]==0)
fgLen--;
if (f[fgLen-1] < g[fgLen-1])
{
std::swap(f, g);
std::swap(b, c);
}
XorWords(f, g, fgLen);
XorWords(b, c, bcLen);
}
while (k >= WORD_BITS)
{
word temp = b[0];
// right shift b
for (unsigned i=0; i+1<BitsToWords(m); i++)
b[i] = b[i+1];
b[BitsToWords(m)-1] = 0;
if (t1 < WORD_BITS)
for (unsigned int j=0; j<WORD_BITS-t1; j++)
{
// Coverity finding on shift amount of 'word x << (t1+j)'.
// temp ^= ((temp >> j) & 1) << (t1 + j);
const unsigned int shift = t1 + j;
CRYPTOPP_ASSERT(shift < WORD_BITS);
temp ^= (shift < WORD_BITS) ? (((temp >> j) & 1) << shift) : 0;
}
else
b[t1/WORD_BITS-1] ^= temp << t1%WORD_BITS;
if (t1 % WORD_BITS)
b[t1/WORD_BITS] ^= temp >> (WORD_BITS - t1%WORD_BITS);
if (t0%WORD_BITS)
{
b[t0/WORD_BITS-1] ^= temp << t0%WORD_BITS;
b[t0/WORD_BITS] ^= temp >> (WORD_BITS - t0%WORD_BITS);
}
else
b[t0/WORD_BITS-1] ^= temp;
k -= WORD_BITS;
}
if (k)
{
word temp = b[0] << (WORD_BITS - k);
ShiftWordsRightByBits(b, BitsToWords(m), k);
if (t1 < WORD_BITS)
{
for (unsigned int j=0; j<WORD_BITS-t1; j++)
{
// Coverity finding on shift amount of 'word x << (t1+j)'.
// temp ^= ((temp >> j) & 1) << (t1 + j);
const unsigned int shift = t1 + j;
CRYPTOPP_ASSERT(shift < WORD_BITS);
temp ^= (shift < WORD_BITS) ? (((temp >> j) & 1) << shift) : 0;
}
}
else
{
b[t1/WORD_BITS-1] ^= temp << t1%WORD_BITS;
}
if (t1 % WORD_BITS)
b[t1/WORD_BITS] ^= temp >> (WORD_BITS - t1%WORD_BITS);
if (t0%WORD_BITS)
{
b[t0/WORD_BITS-1] ^= temp << t0%WORD_BITS;
b[t0/WORD_BITS] ^= temp >> (WORD_BITS - t0%WORD_BITS);
}
else
b[t0/WORD_BITS-1] ^= temp;
}
CopyWords(result.reg.begin(), b, result.reg.size());
return result;
}
const GF2NT::Element& GF2NT::Multiply(const Element &a, const Element &b) const
{
size_t aSize = STDMIN(a.reg.size(), result.reg.size());
Element r((word)0, m);
for (int i=m-1; i>=0; i--)
{
if (r[m-1])
{
ShiftWordsLeftByBits(r.reg.begin(), r.reg.size(), 1);
XorWords(r.reg.begin(), m_modulus.reg, r.reg.size());
}
else
ShiftWordsLeftByBits(r.reg.begin(), r.reg.size(), 1);
if (b[i])
XorWords(r.reg.begin(), a.reg, aSize);
}
if (m%WORD_BITS)
r.reg.begin()[r.reg.size()-1] = (word)Crop(r.reg[r.reg.size()-1], m%WORD_BITS);
CopyWords(result.reg.begin(), r.reg.begin(), result.reg.size());
return result;
}
const GF2NT::Element& GF2NT::Reduced(const Element &a) const
{
if (t0-t1 < WORD_BITS)
return m_domain.Mod(a, m_modulus);
SecWordBlock b(a.reg);
size_t i;
for (i=b.size()-1; i>=BitsToWords(t0); i--)
{
word temp = b[i];
if (t0%WORD_BITS)
{
b[i-t0/WORD_BITS] ^= temp >> t0%WORD_BITS;
b[i-t0/WORD_BITS-1] ^= temp << (WORD_BITS - t0%WORD_BITS);
}
else
b[i-t0/WORD_BITS] ^= temp;
if ((t0-t1)%WORD_BITS)
{
b[i-(t0-t1)/WORD_BITS] ^= temp >> (t0-t1)%WORD_BITS;
b[i-(t0-t1)/WORD_BITS-1] ^= temp << (WORD_BITS - (t0-t1)%WORD_BITS);
}
else
b[i-(t0-t1)/WORD_BITS] ^= temp;
}
if (i==BitsToWords(t0)-1 && t0%WORD_BITS)
{
word mask = ((word)1<<(t0%WORD_BITS))-1;
word temp = b[i] & ~mask;
b[i] &= mask;
b[i-t0/WORD_BITS] ^= temp >> t0%WORD_BITS;
if ((t0-t1)%WORD_BITS)
{
b[i-(t0-t1)/WORD_BITS] ^= temp >> (t0-t1)%WORD_BITS;
if ((t0-t1)%WORD_BITS > t0%WORD_BITS)
b[i-(t0-t1)/WORD_BITS-1] ^= temp << (WORD_BITS - (t0-t1)%WORD_BITS);
else
CRYPTOPP_ASSERT(temp << (WORD_BITS - (t0-t1)%WORD_BITS) == 0);
}
else
b[i-(t0-t1)/WORD_BITS] ^= temp;
}
SetWords(result.reg.begin(), 0, result.reg.size());
CopyWords(result.reg.begin(), b, STDMIN(b.size(), result.reg.size()));
return result;
}
void GF2NP::DEREncodeElement(BufferedTransformation &out, const Element &a) const
{
a.DEREncodeAsOctetString(out, MaxElementByteLength());
}
void GF2NP::BERDecodeElement(BufferedTransformation &in, Element &a) const
{
a.BERDecodeAsOctetString(in, MaxElementByteLength());
}
void GF2NT::DEREncode(BufferedTransformation &bt) const
{
DERSequenceEncoder seq(bt);
ASN1::characteristic_two_field().DEREncode(seq);
DERSequenceEncoder parameters(seq);
DEREncodeUnsigned(parameters, m);
ASN1::tpBasis().DEREncode(parameters);
DEREncodeUnsigned(parameters, t1);
parameters.MessageEnd();
seq.MessageEnd();
}
void GF2NPP::DEREncode(BufferedTransformation &bt) const
{
DERSequenceEncoder seq(bt);
ASN1::characteristic_two_field().DEREncode(seq);
DERSequenceEncoder parameters(seq);
DEREncodeUnsigned(parameters, m);
ASN1::ppBasis().DEREncode(parameters);
DERSequenceEncoder pentanomial(parameters);
DEREncodeUnsigned(pentanomial, t3);
DEREncodeUnsigned(pentanomial, t2);
DEREncodeUnsigned(pentanomial, t1);
pentanomial.MessageEnd();
parameters.MessageEnd();
seq.MessageEnd();
}
GF2NP * BERDecodeGF2NP(BufferedTransformation &bt)
{
member_ptr<GF2NP> result;
BERSequenceDecoder seq(bt);
if (OID(seq) != ASN1::characteristic_two_field())
BERDecodeError();
BERSequenceDecoder parameters(seq);
unsigned int m;
BERDecodeUnsigned(parameters, m);
OID oid(parameters);
if (oid == ASN1::tpBasis())
{
unsigned int t1;
BERDecodeUnsigned(parameters, t1);
result.reset(new GF2NT(m, t1, 0));
}
else if (oid == ASN1::ppBasis())
{
unsigned int t1, t2, t3;
BERSequenceDecoder pentanomial(parameters);
BERDecodeUnsigned(pentanomial, t3);
BERDecodeUnsigned(pentanomial, t2);
BERDecodeUnsigned(pentanomial, t1);
pentanomial.MessageEnd();
result.reset(new GF2NPP(m, t3, t2, t1, 0));
}
else
{
BERDecodeError();
return NULLPTR;
}
parameters.MessageEnd();
seq.MessageEnd();
return result.release();
}
// ********************************************************
GF2NT233::GF2NT233(unsigned int c0, unsigned int c1, unsigned int c2)
: GF2NT(c0, c1, c2)
{
// Asserts and checks due to Bing Shi
CRYPTOPP_ASSERT(c0 > c1 && c1 > c2 && c2==0);
// The test is odd because of ECIES<EC2N>. The basis is c0, but the other coefficients are not in descending order.
if (c1 > c0 || c2 > c0)
throw InvalidArgument("GF2NT: coefficients must be in descending order");
}
const GF2NT::Element& GF2NT233::Multiply(const Element &a, const Element &b) const
{
#if (CRYPTOPP_CLMUL_AVAILABLE)
if (HasCLMUL())
{
CRYPTOPP_ASSERT(a.reg.size()*WORD_BITS == 256);
CRYPTOPP_ASSERT(b.reg.size()*WORD_BITS == 256);
CRYPTOPP_ASSERT(result.reg.size()*WORD_BITS == 256);
const word* pA = a.reg.begin();
const word* pB = b.reg.begin();
word* pR = result.reg.begin();
GF2NT_233_Multiply_Reduce_CLMUL(pA, pB, pR);
return result;
}
else
#elif (CRYPTOPP_ARM_PMULL_AVAILABLE)
if (HasPMULL())
{
CRYPTOPP_ASSERT(a.reg.size()*WORD_BITS == 256);
CRYPTOPP_ASSERT(b.reg.size()*WORD_BITS == 256);
CRYPTOPP_ASSERT(result.reg.size()*WORD_BITS == 256);
const word* pA = a.reg.begin();
const word* pB = b.reg.begin();
word* pR = result.reg.begin();
GF2NT_233_Multiply_Reduce_ARMv8(pA, pB, pR);
return result;
}
else
#elif (CRYPTOPP_POWER8_VMULL_AVAILABLE) && 0
if (HasPMULL())
{
CRYPTOPP_ASSERT(a.reg.size()*WORD_BITS == 256);
CRYPTOPP_ASSERT(b.reg.size()*WORD_BITS == 256);
CRYPTOPP_ASSERT(result.reg.size()*WORD_BITS == 256);
const word* pA = a.reg.begin();
const word* pB = b.reg.begin();
word* pR = result.reg.begin();
GF2NT_233_Multiply_Reduce_POWER8(pA, pB, pR);
return result;
}
else
#endif
return GF2NT::Multiply(a, b);
}
const GF2NT::Element& GF2NT233::Square(const Element &a) const
{
#if (CRYPTOPP_CLMUL_AVAILABLE)
if (HasCLMUL())
{
CRYPTOPP_ASSERT(a.reg.size()*WORD_BITS == 256);
CRYPTOPP_ASSERT(result.reg.size()*WORD_BITS == 256);
const word* pA = a.reg.begin();
word* pR = result.reg.begin();
GF2NT_233_Square_Reduce_CLMUL(pA, pR);
return result;
}
else
#elif (CRYPTOPP_ARM_PMULL_AVAILABLE)
if (HasPMULL())
{
CRYPTOPP_ASSERT(a.reg.size()*WORD_BITS == 256);
CRYPTOPP_ASSERT(result.reg.size()*WORD_BITS == 256);
const word* pA = a.reg.begin();
word* pR = result.reg.begin();
GF2NT_233_Square_Reduce_ARMv8(pA, pR);
return result;
}
else
#elif (CRYPTOPP_POWER8_VMULL_AVAILABLE) && 0
if (HasPMULL())
{
CRYPTOPP_ASSERT(a.reg.size()*WORD_BITS == 256);
CRYPTOPP_ASSERT(result.reg.size()*WORD_BITS == 256);
const word* pA = a.reg.begin();
word* pR = result.reg.begin();
GF2NT_233_Square_Reduce_POWER8(pA, pR);
return result;
}
else
#endif
return GF2NT::Square(a);
}
NAMESPACE_END
#endif
algebra.h
Classes for performing mathematics over different fields.
asn.h
Classes and functions for working with ANS.1 objects.
operator<<
std::ostream & operator<<(std::ostream &out, const OID &oid)
Print a OID value.
Definition asn.h:939
BERDecodeUnsigned
void BERDecodeUnsigned(BufferedTransformation &in, T &w, byte asnTag=INTEGER, T minValue=0, T maxValue=T(0xffffffff))
BER Decode unsigned value.
Definition asn.h:856
DEREncodeUnsigned
size_t DEREncodeUnsigned(BufferedTransformation &out, T w, byte asnTag=INTEGER)
DER Encode unsigned value.
Definition asn.h:820
OCTET_STRING
@ OCTET_STRING
ASN.1 Octet string.
Definition asn.h:38
BERDecodeError
void BERDecodeError()
Raises a BERDecodeErr.
Definition asn.h:104
AbstractGroup< EuclideanDomainOf< PolynomialMod2 >::Element >::Add
virtual const Element & Add(const Element &a, const Element &b) const=0
AbstractGroup< EuclideanDomainOf< PolynomialMod2 >::Element >::Accumulate
virtual Element & Accumulate(Element &a, const Element &b) const
Definition algebra.cpp:27
AbstractRing< EuclideanDomainOf< PolynomialMod2 >::Element >::Multiply
virtual const Element & Multiply(const Element &a, const Element &b) const=0
AbstractRing< EuclideanDomainOf< PolynomialMod2 >::Element >::Square
virtual const Element & Square(const Element &a) const
Definition algebra.cpp:37
AbstractRing< EuclideanDomainOf< PolynomialMod2 >::Element >::MultiplicativeInverse
virtual const Element & MultiplicativeInverse(const Element &a) const=0
BERSequenceDecoder
BER Sequence Decoder.
Definition asn.h:525
BufferedTransformation
Interface for buffered transformations.
Definition cryptlib.h:1657
BufferedTransformation::Get
virtual size_t Get(byte &outByte)
Retrieve a 8-bit byte.
BufferedTransformation::Put
size_t Put(byte inByte, bool blocking=true)
Input a byte for processing.
Definition cryptlib.h:1678
BufferedTransformation::MaxRetrievable
virtual lword MaxRetrievable() const
Provides the number of bytes ready for retrieval.
Element
EuclideanDomainOf
Euclidean domain.
Definition algebra.h:316
GF2NP
GF(2^n) with Polynomial Basis.
Definition gf2n.h:299
GF2NPP
GF(2^n) with Pentanomial Basis.
Definition gf2n.h:375
GF2NT233::Multiply
const Element & Multiply(const Element &a, const Element &b) const
Multiplies elements in the group.
GF2NT233::Square
const Element & Square(const Element &a) const
Square an element in the group.
GF2NT
GF(2^n) with Trinomial Basis.
Definition gf2n.h:335
GF2NT::MultiplicativeInverse
const Element & MultiplicativeInverse(const Element &a) const
Calculate the multiplicative inverse of an element in the group.
GF2NT::Square
const Element & Square(const Element &a) const
Square an element in the group.
Definition gf2n.h:345
GF2NT::Multiply
const Element & Multiply(const Element &a, const Element &b) const
Multiplies elements in the group.
InvalidArgument
An invalid argument was detected.
Definition cryptlib.h:208
OID
Object Identifier.
Definition asn.h:265
PolynomialMod2
Polynomial with Coefficients in GF(2).
Definition gf2n.h:27
PolynomialMod2::DEREncodeAsOctetString
void DEREncodeAsOctetString(BufferedTransformation &bt, size_t length) const
encode value as big-endian octet string
PolynomialMod2::MultiplicativeInverse
PolynomialMod2 MultiplicativeInverse() const
return inverse if *this is a unit, otherwise return 0
Definition gf2n.h:232
PolynomialMod2::Encode
void Encode(byte *output, size_t outputLen) const
encode in big-endian format
PolynomialMod2::Monomial
static PolynomialMod2 Monomial(size_t i)
Provides x^i.
PolynomialMod2::Degree
signed int Degree() const
the zero polynomial will return a degree of -1
Definition gf2n.h:130
PolynomialMod2::One
static const PolynomialMod2 & One()
The One polinomial.
PolynomialMod2::IsIrreducible
bool IsIrreducible() const
check for irreducibility
PolynomialMod2::Pentanomial
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.
PolynomialMod2::IsUnit
bool IsUnit() const
only 1 is a unit
Definition gf2n.h:230
PolynomialMod2::BERDecodeAsOctetString
void BERDecodeAsOctetString(BufferedTransformation &bt, size_t length)
decode value as big-endian octet string
PolynomialMod2::GetByte
byte GetByte(size_t n) const
return the n-th byte
PolynomialMod2::BitCount
unsigned int BitCount() const
number of significant bits = Degree() + 1
PolynomialMod2::WordCount
unsigned int WordCount() const
number of significant words = ceiling(ByteCount()/sizeof(word))
PolynomialMod2::AllOnes
static PolynomialMod2 AllOnes(size_t n)
Provides x^(n-1) + ... + x + 1.
PolynomialMod2::Trinomial
static PolynomialMod2 Trinomial(size_t t0, size_t t1, size_t t2)
Provides x^t0 + x^t1 + x^t2.
PolynomialMod2::InverseMod
PolynomialMod2 InverseMod(const PolynomialMod2 &) const
calculate multiplicative inverse of *this mod n
PolynomialMod2::Parity
unsigned int Parity() const
sum modulo 2 of all coefficients
PolynomialMod2::PolynomialMod2
PolynomialMod2()
Construct the zero polynomial.
PolynomialMod2::Zero
static const PolynomialMod2 & Zero()
The Zero polinomial.
PolynomialMod2::ByteCount
unsigned int ByteCount() const
number of significant bytes = ceiling(BitCount()/8)
PolynomialMod2::Divide
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))
PolynomialMod2::Gcd
static PolynomialMod2 Gcd(const PolynomialMod2 &a, const PolynomialMod2 &n)
greatest common divisor
PolynomialMod2::SetByte
void SetByte(size_t n, byte value)
set the n-th byte to value
QuotientRing
Quotient ring.
Definition algebra.h:387
RandomNumberGenerator
Interface for random number generators.
Definition cryptlib.h:1440
RandomNumberGenerator::GenerateBlock
virtual void GenerateBlock(byte *output, size_t size)
Generate random array of bytes.
SecBlock
Secure memory block with allocator and cleanup.
Definition secblock.h:731
SecBlock::CleanNew
void CleanNew(size_type newSize)
Change size without preserving contents.
Definition secblock.h:1143
SecBlock::size
size_type size() const
Provides the count of elements in the SecBlock.
Definition secblock.h:867
member_ptr
Pointer that overloads operator ->.
Definition smartptr.h:38
config.h
Library configuration file.
byte
unsigned char byte
8-bit unsigned datatype
Definition config_int.h:66
word
word64 word
Full word used for multiprecision integer arithmetic.
Definition config_int.h:192
WORD_BITS
const unsigned int WORD_BITS
Size of a platform word in bits.
Definition config_int.h:260
WORD_SIZE
const unsigned int WORD_SIZE
Size of a platform word in bytes.
Definition config_int.h:255
cpu.h
Functions for CPU features and intrinsics.
cryptlib.h
Abstract base classes that provide a uniform interface to this library.
filters.h
Implementation of BufferedTransformation's attachment interface.
gf2n.h
Classes and functions for schemes over GF(2^n).
misc.h
Utility functions for the Crypto++ library.
BitPrecision
unsigned int BitPrecision(const T &value)
Returns the number of bits required for a value.
Definition misc.h:1047
BytePrecision
unsigned int BytePrecision(const T &value)
Returns the number of 8-bit bytes or octets required for a value.
Definition misc.h:1024
BitsToWords
size_t BitsToWords(size_t bitCount)
Returns the number of words required for the specified number of bits.
Definition misc.h:1163
Crop
T Crop(T value, size_t bits)
Truncates the value to the specified number of bits.
Definition misc.h:1131
STDMIN
const T & STDMIN(const T &a, const T &b)
Replacement function for std::min.
Definition misc.h:657
BytesToWords
size_t BytesToWords(size_t byteCount)
Returns the number of words required for the specified number of bytes.
Definition misc.h:1153
SafeConvert
bool SafeConvert(T1 from, T2 &to)
Perform a conversion from from to to.
Definition misc.h:718
CryptoPP
Crypto++ library namespace.
oids.h
ASN.1 object identifiers for algorithms and schemes.
pch.h
Precompiled header file.
randpool.h
Class file for Randomness Pool.
smartptr.h
Classes for automatic resource management.
CRYPTOPP_ASSERT
#define CRYPTOPP_ASSERT(exp)
Debugging and diagnostic assertion.
Definition trap.h:68
words.h
Support functions for word operations.
ShiftWordsRightByWords
void ShiftWordsRightByWords(word *r, size_t n, size_t shiftWords)
Right shift word array.
Definition words.h:212
XorWords
void XorWords(word *r, const word *a, const word *b, size_t n)
XOR word arrays.
Definition words.h:66
SetWords
void SetWords(word *r, word a, size_t n)
Set the value of words.
Definition words.h:35
ShiftWordsLeftByBits
word ShiftWordsLeftByBits(word *r, size_t n, unsigned int shiftBits)
Left shift word array.
Definition words.h:149
ShiftWordsLeftByWords
void ShiftWordsLeftByWords(word *r, size_t n, size_t shiftWords)
Left shift word array.
Definition words.h:194
CountWords
size_t CountWords(const word *x, size_t n)
Count the number of words.
Definition words.h:21
ShiftWordsRightByBits
word ShiftWordsRightByBits(word *r, size_t n, unsigned int shiftBits)
Right shift word array.
Definition words.h:172
CopyWords
void CopyWords(word *r, const word *a, size_t n)
Copy word array.
Definition words.h:48
AndWords
void AndWords(word *r, const word *a, const word *b, size_t n)
AND word arrays.
Definition words.h:93