dsa.cpp

各种加密算法的集合

#include "pch.h" 
#include "dsa.h" 
#include "asn.h" 
#include "nbtheory.h" 
#include "sha.h" 
 
NAMESPACE_BEGIN(CryptoPP) 
 
bool GenerateDSAPrimes(byte *seed, unsigned int g, int &counter, 
						  Integer &p, unsigned int L, Integer &q) 
{ 
	assert(L >= MIN_DSA_PRIME_LENGTH && L <= MAX_DSA_PRIME_LENGTH); 
 
	SHA sha; 
	SecByteBlock U(SHA::DIGESTSIZE); 
	SecByteBlock temp(SHA::DIGESTSIZE); 
	SecByteBlock W(((L-1)/160+1) * SHA::DIGESTSIZE); 
	const int n = (L-1) / 160; 
	const int b = (L-1) % 160; 
	Integer X; 
 
	sha.CalculateDigest(U, seed, g/8); 
 
	for (int i=g/8-1, carry=true; i>=0 && carry; i--) 
		carry=!++seed[i]; 
 
	sha.CalculateDigest(temp, seed, g/8); 
	xorbuf(U, temp, SHA::DIGESTSIZE); 
 
	U[0] |= 0x80; 
	U[SHA::DIGESTSIZE-1] |= 1; 
	q.Decode(U, SHA::DIGESTSIZE); 
 
	if (!IsPrime(q)) 
		return false; 
 
	for (counter = 0; counter < 4096; counter++) 
	{ 
		for (int k=0; k<=n; k++) 
		{ 
			for (int i=g/8-1, carry=true; i>=0 && carry; i--) 
				carry=!++seed[i]; 
			sha.CalculateDigest(W+(n-k)*SHA::DIGESTSIZE, seed, g/8); 
		} 
		W[SHA::DIGESTSIZE - 1 - b/8] |= 0x80; 
		X.Decode(W + SHA::DIGESTSIZE - 1 - b/8, L/8); 
		p = X-((X % (2*q))-1); 
 
		if (p.GetBit(L-1) && IsPrime(p)) 
			return true; 
	} 
	return false; 
} 
 
DSABase::DSABase(const Integer &p, const Integer &q, 
				   const Integer &g, const Integer &y) 
	: p(p), q(q), g(g), y(y),  
	  gpc(p, g, q.BitCount(), 1), ypc(p, y, q.BitCount(), 1) 
{ 
} 
 
void DSABase::Precompute(unsigned int precomputationStorage) 
{ 
	gpc.Precompute(p, g, q.BitCount(), precomputationStorage); 
	ypc.Precompute(p, y, q.BitCount(), precomputationStorage); 
} 
 
void DSABase::LoadPrecomputation(BufferedTransformation &bt) 
{ 
	gpc.Load(p, bt); 
	ypc.Load(p, bt); 
} 
 
void DSABase::SavePrecomputation(BufferedTransformation &bt) const 
{ 
	gpc.Save(bt); 
	ypc.Save(bt); 
} 
 
Integer DSABase::EncodeDigest(const byte *digest, unsigned int digestLen) const 
{ 
	Integer h; 
	if (digestLen*8 <= q.BitCount()) 
		h.Decode(digest, digestLen); 
	else 
	{ 
		h.Decode(digest, q.ByteCount()); 
		h >>= q.ByteCount()*8 - q.BitCount(); 
	} 
	return h; 
} 
 
// *********************************************************** 
 
DSAPrivateKey::DSAPrivateKey(const Integer &p, const Integer &q, 
							 const Integer &g, const Integer &y, const Integer &x) 
	: DSABase(p, q, g, y), x(x) 
{ 
} 
 
DSAPrivateKey::DSAPrivateKey(RandomNumberGenerator &rng, unsigned int keybits) 
{ 
	SecByteBlock seed(SHA::DIGESTSIZE); 
	Integer h; 
	int c; 
 
	do 
	{ 
		rng.GetBlock(seed, SHA::DIGESTSIZE); 
	} while (!GenerateDSAPrimes(seed, SHA::DIGESTSIZE*8, c, p, keybits, q)); 
 
	do 
	{ 
		h.Randomize(rng, 2, p-2); 
		g = a_exp_b_mod_c(h, (p-1)/q, p); 
	} while (g <= 1); 
 
	x.Randomize(rng, 2, q-2); 
	gpc.Precompute(p, g, q.BitCount(), 1); 
	y = gpc.Exponentiate(x); 
	ypc.Precompute(p, y, q.BitCount(), 1); 
} 
 
DSAPrivateKey::DSAPrivateKey(RandomNumberGenerator &rng, const Integer &pIn, const Integer &qIn, const Integer &gIn) 
{ 
	p = pIn; 
	q = qIn; 
	g = gIn; 
 
	x.Randomize(rng, 2, q-2); 
	gpc.Precompute(p, g, q.BitCount(), 1); 
	y = gpc.Exponentiate(x); 
	ypc.Precompute(p, y, q.BitCount(), 1); 
} 
 
DSAPrivateKey::DSAPrivateKey(BufferedTransformation &bt) 
{ 
	BERSequenceDecoder seq(bt); 
	p.BERDecode(seq); 
	q.BERDecode(seq); 
	g.BERDecode(seq); 
	y.BERDecode(seq); 
	x.BERDecode(seq); 
	gpc.Precompute(p, g, q.BitCount(), 1); 
	ypc.Precompute(p, y, q.BitCount(), 1); 
} 
 
void DSAPrivateKey::DEREncode(BufferedTransformation &bt) const 
{ 
	DERSequenceEncoder seq(bt); 
	p.DEREncode(seq); 
	q.DEREncode(seq); 
	g.DEREncode(seq); 
	y.DEREncode(seq); 
	x.DEREncode(seq); 
} 
 
void DSAPrivateKey::SignDigest(RandomNumberGenerator &rng, const byte *digest, unsigned int digestLen, byte *signature) const 
{ 
	Integer h = EncodeDigest(digest, digestLen); 
	Integer k(rng, 2, q-2); 
	Integer r, s; 
 
	RawSign(k, h, r, s); 
	r.Encode(signature, q.ByteCount()); 
	s.Encode(signature+q.ByteCount(), q.ByteCount()); 
} 
 
void DSAPrivateKey::RawSign(const Integer &k, const Integer &h, Integer &r, Integer &s) const 
{ 
//    r = a_exp_b_mod_c(g, k, p) % q; 
	r = gpc.Exponentiate(k) % q; 
	Integer kInv = EuclideanMultiplicativeInverse(k, q); 
	s = (kInv * (x*r + h)) % q; 
} 
 
// *********************************************************** 
 
DSAPublicKey::DSAPublicKey(const Integer &p, const Integer &q, 
							const Integer &g, const Integer &y) 
	: DSABase(p, q, g, y) 
{ 
} 
 
DSAPublicKey::DSAPublicKey(const DSAPrivateKey &priv) 
	: DSABase(priv) 
{ 
} 
 
DSAPublicKey::DSAPublicKey(BufferedTransformation &bt) 
{ 
	BERSequenceDecoder seq(bt); 
	p.BERDecode(seq); 
	q.BERDecode(seq); 
	g.BERDecode(seq); 
	y.BERDecode(seq); 
	gpc.Precompute(p, g, q.BitCount(), 1); 
	ypc.Precompute(p, y, q.BitCount(), 1); 
} 
 
void DSAPublicKey::DEREncode(BufferedTransformation &bt) const 
{ 
	DERSequenceEncoder seq(bt); 
	p.DEREncode(seq); 
	q.DEREncode(seq); 
	g.DEREncode(seq); 
	y.DEREncode(seq); 
} 
 
bool DSAPublicKey::VerifyDigest(const byte *digest, unsigned int digestLen, const byte *signature) const 
{ 
	Integer h = EncodeDigest(digest, digestLen); 
	Integer r(signature, q.ByteCount()); 
	Integer s(signature+q.ByteCount(), q.ByteCount()); 
 
	return RawVerify(h, r, s); 
} 
 
bool DSAPublicKey::RawVerify(const Integer &h, const Integer &r, const Integer &s) const 
{ 
	if (r>=q || r<1 || s>=q || s<1) 
		return false; 
 
	Integer w = EuclideanMultiplicativeInverse(s, q); 
	Integer u1 = (h * w) % q; 
	Integer u2 = (r * w) % q; 
	// verify r == (g^u1 * y^u2 mod p) mod q 
//	return r == ModularArithmetic(p).CascadeExponentiate(g, u1, y, u2) % q; 
	return r == gpc.CascadeExponentiate(u1, ypc, u2) % q; 
} 
 
NAMESPACE_END