Добавил:
Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
Скачиваний:
28
Добавлен:
16.04.2013
Размер:
5.77 Кб
Скачать
// dsa.cpp - written and placed in the public domain by Wei Dai

#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
Соседние файлы в папке CRYPTO30