1// dsa.cpp - written and placed in the public domain by Wei Dai
2
3#include "pch.h"
4
5#ifndef CRYPTOPP_IMPORTS
6
7#include "gfpcrypt.h"
8#include "asn.h"
9#include "oids.h"
10#include "nbtheory.h"
11
12NAMESPACE_BEGIN(CryptoPP)
13
14void TestInstantiations_gfpcrypt()
15{
16	GDSA<SHA>::Signer test;
17	GDSA<SHA>::Verifier test1;
18	DSA::Signer test5(NullRNG(), 100);
19	DSA::Signer test2(test5);
20	NR<SHA>::Signer test3;
21	NR<SHA>::Verifier test4;
22	DLIES<>::Encryptor test6;
23	DLIES<>::Decryptor test7;
24}
25
26void DL_GroupParameters_DSA::GenerateRandom(RandomNumberGenerator &rng, const NameValuePairs &alg)
27{
28	Integer p, q, g;
29
30	if (alg.GetValue("Modulus", p) && alg.GetValue("SubgroupGenerator", g))
31	{
32		q = alg.GetValueWithDefault("SubgroupOrder", ComputeGroupOrder(p)/2);
33	}
34	else
35	{
36		int modulusSize = 1024;
37		alg.GetIntValue("ModulusSize", modulusSize) || alg.GetIntValue("KeySize", modulusSize);
38
39		if (!DSA::IsValidPrimeLength(modulusSize))
40			throw InvalidArgument("DSA: not a valid prime length");
41
42		SecByteBlock seed(SHA::DIGESTSIZE);
43		Integer h;
44		int c;
45
46		do
47		{
48			rng.GenerateBlock(seed, SHA::DIGESTSIZE);
49		} while (!DSA::GeneratePrimes(seed, SHA::DIGESTSIZE*8, c, p, modulusSize, q));
50
51		do
52		{
53			h.Randomize(rng, 2, p-2);
54			g = a_exp_b_mod_c(h, (p-1)/q, p);
55		} while (g <= 1);
56	}
57
58	Initialize(p, q, g);
59}
60
61bool DL_GroupParameters_DSA::ValidateGroup(RandomNumberGenerator &rng, unsigned int level) const
62{
63	bool pass = DL_GroupParameters_GFP::ValidateGroup(rng, level);
64	pass = pass && DSA::IsValidPrimeLength(GetModulus().BitCount());
65	pass = pass && GetSubgroupOrder().BitCount() == 160;
66	return pass;
67}
68
69void DL_SignatureMessageEncodingMethod_DSA::ComputeMessageRepresentative(RandomNumberGenerator &rng,
70	const byte *recoverableMessage, size_t recoverableMessageLength,
71	HashTransformation &hash, HashIdentifier hashIdentifier, bool messageEmpty,
72	byte *representative, size_t representativeBitLength) const
73{
74	assert(recoverableMessageLength == 0);
75	assert(hashIdentifier.second == 0);
76	const size_t representativeByteLength = BitsToBytes(representativeBitLength);
77	const size_t digestSize = hash.DigestSize();
78	const size_t paddingLength = SaturatingSubtract(representativeByteLength, digestSize);
79
80	memset(representative, 0, paddingLength);
81	hash.TruncatedFinal(representative+paddingLength, STDMIN(representativeByteLength, digestSize));
82
83	if (digestSize*8 > representativeBitLength)
84	{
85		Integer h(representative, representativeByteLength);
86		h >>= representativeByteLength*8 - representativeBitLength;
87		h.Encode(representative, representativeByteLength);
88	}
89}
90
91void DL_SignatureMessageEncodingMethod_NR::ComputeMessageRepresentative(RandomNumberGenerator &rng,
92	const byte *recoverableMessage, size_t recoverableMessageLength,
93	HashTransformation &hash, HashIdentifier hashIdentifier, bool messageEmpty,
94	byte *representative, size_t representativeBitLength) const
95{
96	assert(recoverableMessageLength == 0);
97	assert(hashIdentifier.second == 0);
98	const size_t representativeByteLength = BitsToBytes(representativeBitLength);
99	const size_t digestSize = hash.DigestSize();
100	const size_t paddingLength = SaturatingSubtract(representativeByteLength, digestSize);
101
102	memset(representative, 0, paddingLength);
103	hash.TruncatedFinal(representative+paddingLength, STDMIN(representativeByteLength, digestSize));
104
105	if (digestSize*8 >= representativeBitLength)
106	{
107		Integer h(representative, representativeByteLength);
108		h >>= representativeByteLength*8 - representativeBitLength + 1;
109		h.Encode(representative, representativeByteLength);
110	}
111}
112
113bool DL_GroupParameters_IntegerBased::ValidateGroup(RandomNumberGenerator &rng, unsigned int level) const
114{
115	const Integer &p = GetModulus(), &q = GetSubgroupOrder();
116
117	bool pass = true;
118	pass = pass && p > Integer::One() && p.IsOdd();
119	pass = pass && q > Integer::One() && q.IsOdd();
120
121	if (level >= 1)
122		pass = pass && GetCofactor() > Integer::One() && GetGroupOrder() % q == Integer::Zero();
123	if (level >= 2)
124		pass = pass && VerifyPrime(rng, q, level-2) && VerifyPrime(rng, p, level-2);
125
126	return pass;
127}
128
129bool DL_GroupParameters_IntegerBased::ValidateElement(unsigned int level, const Integer &g, const DL_FixedBasePrecomputation<Integer> *gpc) const
130{
131	const Integer &p = GetModulus(), &q = GetSubgroupOrder();
132
133	bool pass = true;
134	pass = pass && GetFieldType() == 1 ? g.IsPositive() : g.NotNegative();
135	pass = pass && g < p && !IsIdentity(g);
136
137	if (level >= 1)
138	{
139		if (gpc)
140			pass = pass && gpc->Exponentiate(GetGroupPrecomputation(), Integer::One()) == g;
141	}
142	if (level >= 2)
143	{
144		if (GetFieldType() == 2)
145			pass = pass && Jacobi(g*g-4, p)==-1;
146
147		// verifying that Lucas((p+1)/2, w, p)==2 is omitted because it's too costly
148		// and at most 1 bit is leaked if it's false
149		bool fullValidate = (GetFieldType() == 2 && level >= 3) || !FastSubgroupCheckAvailable();
150
151		if (fullValidate && pass)
152		{
153			Integer gp = gpc ? gpc->Exponentiate(GetGroupPrecomputation(), q) : ExponentiateElement(g, q);
154			pass = pass && IsIdentity(gp);
155		}
156		else if (GetFieldType() == 1)
157			pass = pass && Jacobi(g, p) == 1;
158	}
159
160	return pass;
161}
162
163void DL_GroupParameters_IntegerBased::GenerateRandom(RandomNumberGenerator &rng, const NameValuePairs &alg)
164{
165	Integer p, q, g;
166
167	if (alg.GetValue("Modulus", p) && alg.GetValue("SubgroupGenerator", g))
168	{
169		q = alg.GetValueWithDefault("SubgroupOrder", ComputeGroupOrder(p)/2);
170	}
171	else
172	{
173		int modulusSize, subgroupOrderSize;
174
175		if (!alg.GetIntValue("ModulusSize", modulusSize))
176			modulusSize = alg.GetIntValueWithDefault("KeySize", 2048);
177
178		if (!alg.GetIntValue("SubgroupOrderSize", subgroupOrderSize))
179			subgroupOrderSize = GetDefaultSubgroupOrderSize(modulusSize);
180
181		PrimeAndGenerator pg;
182		pg.Generate(GetFieldType() == 1 ? 1 : -1, rng, modulusSize, subgroupOrderSize);
183		p = pg.Prime();
184		q = pg.SubPrime();
185		g = pg.Generator();
186	}
187
188	Initialize(p, q, g);
189}
190
191Integer DL_GroupParameters_IntegerBased::DecodeElement(const byte *encoded, bool checkForGroupMembership) const
192{
193	Integer g(encoded, GetModulus().ByteCount());
194	if (!ValidateElement(1, g, NULL))
195		throw DL_BadElement();
196	return g;
197}
198
199void DL_GroupParameters_IntegerBased::BERDecode(BufferedTransformation &bt)
200{
201	BERSequenceDecoder parameters(bt);
202		Integer p(parameters);
203		Integer q(parameters);
204		Integer g;
205		if (parameters.EndReached())
206		{
207			g = q;
208			q = ComputeGroupOrder(p) / 2;
209		}
210		else
211			g.BERDecode(parameters);
212	parameters.MessageEnd();
213
214	SetModulusAndSubgroupGenerator(p, g);
215	SetSubgroupOrder(q);
216}
217
218void DL_GroupParameters_IntegerBased::DEREncode(BufferedTransformation &bt) const
219{
220	DERSequenceEncoder parameters(bt);
221		GetModulus().DEREncode(parameters);
222		m_q.DEREncode(parameters);
223		GetSubgroupGenerator().DEREncode(parameters);
224	parameters.MessageEnd();
225}
226
227bool DL_GroupParameters_IntegerBased::GetVoidValue(const char *name, const std::type_info &valueType, void *pValue) const
228{
229	return GetValueHelper<DL_GroupParameters<Element> >(this, name, valueType, pValue)
230		CRYPTOPP_GET_FUNCTION_ENTRY(Modulus);
231}
232
233void DL_GroupParameters_IntegerBased::AssignFrom(const NameValuePairs &source)
234{
235	AssignFromHelper(this, source)
236		CRYPTOPP_SET_FUNCTION_ENTRY2(Modulus, SubgroupGenerator)
237		CRYPTOPP_SET_FUNCTION_ENTRY(SubgroupOrder)
238		;
239}
240
241OID DL_GroupParameters_IntegerBased::GetAlgorithmID() const
242{
243	return ASN1::id_dsa();
244}
245
246void DL_GroupParameters_GFP::SimultaneousExponentiate(Element *results, const Element &base, const Integer *exponents, unsigned int exponentsCount) const
247{
248	ModularArithmetic ma(GetModulus());
249	ma.SimultaneousExponentiate(results, base, exponents, exponentsCount);
250}
251
252DL_GroupParameters_GFP::Element DL_GroupParameters_GFP::MultiplyElements(const Element &a, const Element &b) const
253{
254	return a_times_b_mod_c(a, b, GetModulus());
255}
256
257DL_GroupParameters_GFP::Element DL_GroupParameters_GFP::CascadeExponentiate(const Element &element1, const Integer &exponent1, const Element &element2, const Integer &exponent2) const
258{
259	ModularArithmetic ma(GetModulus());
260	return ma.CascadeExponentiate(element1, exponent1, element2, exponent2);
261}
262
263Integer DL_GroupParameters_IntegerBased::GetMaxExponent() const
264{
265	return STDMIN(GetSubgroupOrder()-1, Integer::Power2(2*DiscreteLogWorkFactor(GetFieldType()*GetModulus().BitCount())));
266}
267
268unsigned int DL_GroupParameters_IntegerBased::GetDefaultSubgroupOrderSize(unsigned int modulusSize) const
269{
270	return 2*DiscreteLogWorkFactor(GetFieldType()*modulusSize);
271}
272
273NAMESPACE_END
274
275#endif
276