gf2n.cpp

各种加密算法的集合

			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 operator==(const PolynomialMod2 &a, const PolynomialMod2 &b) 
{ 
	unsigned i, smallerSize = STDMIN(a.reg.size, b.reg.size); 
 
	for (i=0; i<smallerSize; i++) 
		if (a.reg[i] != b.reg[i]) return false; 
 
	for (i=smallerSize; i<a.reg.size; i++) 
		if (a.reg[i] != 0) return false; 
 
	for (i=smallerSize; i<b.reg.size; i++) 
		if (b.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; 
	const char vec[]="0123456789ABCDEF"; 
 
	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); 
} 
 
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; 
} 
 
// ******************************************************** 
 
static EuclideanDomainOf<PolynomialMod2>& PolynomialMod2Domain() 
{ 
	static EuclideanDomainOf<PolynomialMod2> domain; 
	return domain; 
} 
 
GF2NP::GF2NP(const PolynomialMod2 &modulus) 
	: QuotientRing<EuclideanDomainOf<PolynomialMod2> >(PolynomialMod2Domain(), modulus), m(modulus.Degree())  
{ 
} 
 
// ******************************************************** 
 
GF2NT::GF2NT(unsigned int t0, unsigned int t1, unsigned int t2) 
	: GF2NP(PolynomialMod2::Trinomial(t0, t1, t2)) 
	, t0(t0), t1(t1) 
	, result((word)0, m) 
{ 
	assert(t0 > t1 && t1 > t2 && t2==0); 
} 
 
GF2NT::Element GF2NT::MultiplicativeInverse(const Element &a) const 
{ 
	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; 
	unsigned int bcLen=1, fgLen=m_modulus.reg.size; 
	unsigned int k=0; 
 
	SetWords(T, 0, 3*m_modulus.reg.size); 
	b[0]=1; 
	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++; 
			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++; 
			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 (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; 
 
		if (t1%WORD_BITS) 
		{ 
			b[t1/WORD_BITS-1] ^= temp << t1%WORD_BITS; 
			b[t1/WORD_BITS] ^= temp >> (WORD_BITS - t1%WORD_BITS); 
		} 
		else 
			b[t1/WORD_BITS-1] ^= temp; 
 
		k -= WORD_BITS; 
	} 
 
	if (k) 
	{ 
		word temp = b[0] << (WORD_BITS - k); 
		ShiftWordsRightByBits(b, bitsToWords(m), k); 
 
		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; 
 
		if (t1%WORD_BITS) 
		{ 
			b[t1/WORD_BITS-1] ^= temp << t1%WORD_BITS; 
			b[t1/WORD_BITS] ^= temp >> (WORD_BITS - t1%WORD_BITS); 
		} 
		else 
			b[t1/WORD_BITS-1] ^= temp; 
	} 
 
//	Element result((word)0, m); 
	CopyWords(result.reg.ptr, b, result.reg.size); 
	return result; 
} 
 
GF2NT::Element GF2NT::Multiply(const Element &a, const Element &b) const 
{ 
//	Element result((word)0, m); 
	unsigned int aSize = STDMIN(a.reg.size, result.reg.size); 
	SetWords(result.reg.ptr, 0, result.reg.size); 
 
	for (int i=m-1; i>=0; i--) 
	{ 
		if (result[m-1]) 
		{ 
			ShiftWordsLeftByBits(result.reg.ptr, result.reg.size, 1); 
			XorWords(result.reg.ptr, m_modulus.reg, result.reg.size); 
		} 
		else 
			ShiftWordsLeftByBits(result.reg.ptr, result.reg.size, 1); 
 
		if (b[i]) 
			XorWords(result.reg.ptr, a.reg, aSize); 
	} 
 
	if (m%WORD_BITS) 
		result.reg.ptr[result.reg.size-1] = (word)Crop(result.reg[result.reg.size-1], m%WORD_BITS); 
	return result; 
} 
 
GF2NT::Element GF2NT::Reduced(const Element &a) const 
{ 
	SecBlock<word> b(a.reg.size); 
	CopyWords(b, a.reg, a.reg.size); 
 
	unsigned i; 
	for (i=b.size-1; i>=bitsToWords(m); 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(m)-1 && m%WORD_BITS) 
	{ 
		word mask = ((word)1<<(m%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; 
			b[i-(t0-t1)/WORD_BITS-1] ^= temp << (WORD_BITS - (t0-t1)%WORD_BITS); 
		} 
		else 
			b[i-(t0-t1)/WORD_BITS] ^= temp; 
	} 
 
	SetWords(result.reg.ptr, 0, result.reg.size); 
//	Element result((word)0, m); 
	CopyWords(result.reg.ptr, b, STDMIN(b.size, result.reg.size)); 
	return result; 
} 
 
NAMESPACE_END