1// esign.cpp - written and placed in the public domain by Wei Dai
2
3#include "pch.h"
4#include "esign.h"
5#include "asn.h"
6#include "modarith.h"
7#include "nbtheory.h"
8#include "sha.h"
9#include "algparam.h"
10
11NAMESPACE_BEGIN(CryptoPP)
12
13void ESIGN_TestInstantiations()
14{
15	ESIGN<SHA>::Verifier x1(1, 1);
16	ESIGN<SHA>::Signer x2(NullRNG(), 1);
17	ESIGN<SHA>::Verifier x3(x2);
18	ESIGN<SHA>::Verifier x4(x2.GetKey());
19	ESIGN<SHA>::Verifier x5(x3);
20	ESIGN<SHA>::Signer x6 = x2;
21
22	x6 = x2;
23	x3 = ESIGN<SHA>::Verifier(x2);
24	x4 = x2.GetKey();
25}
26
27void ESIGNFunction::BERDecode(BufferedTransformation &bt)
28{
29	BERSequenceDecoder seq(bt);
30		m_n.BERDecode(seq);
31		m_e.BERDecode(seq);
32	seq.MessageEnd();
33}
34
35void ESIGNFunction::DEREncode(BufferedTransformation &bt) const
36{
37	DERSequenceEncoder seq(bt);
38		m_n.DEREncode(seq);
39		m_e.DEREncode(seq);
40	seq.MessageEnd();
41}
42
43Integer ESIGNFunction::ApplyFunction(const Integer &x) const
44{
45	DoQuickSanityCheck();
46	return STDMIN(a_exp_b_mod_c(x, m_e, m_n) >> (2*GetK()+2), MaxImage());
47}
48
49bool ESIGNFunction::Validate(RandomNumberGenerator &rng, unsigned int level) const
50{
51	bool pass = true;
52	pass = pass && m_n > Integer::One() && m_n.IsOdd();
53	pass = pass && m_e >= 8 && m_e < m_n;
54	return pass;
55}
56
57bool ESIGNFunction::GetVoidValue(const char *name, const std::type_info &valueType, void *pValue) const
58{
59	return GetValueHelper(this, name, valueType, pValue).Assignable()
60		CRYPTOPP_GET_FUNCTION_ENTRY(Modulus)
61		CRYPTOPP_GET_FUNCTION_ENTRY(PublicExponent)
62		;
63}
64
65void ESIGNFunction::AssignFrom(const NameValuePairs &source)
66{
67	AssignFromHelper(this, source)
68		CRYPTOPP_SET_FUNCTION_ENTRY(Modulus)
69		CRYPTOPP_SET_FUNCTION_ENTRY(PublicExponent)
70		;
71}
72
73// *****************************************************************************
74
75void InvertibleESIGNFunction::GenerateRandom(RandomNumberGenerator &rng, const NameValuePairs &param)
76{
77	int modulusSize = 1023*2;
78	param.GetIntValue("ModulusSize", modulusSize) || param.GetIntValue("KeySize", modulusSize);
79
80	if (modulusSize < 24)
81		throw InvalidArgument("InvertibleESIGNFunction: specified modulus size is too small");
82
83	if (modulusSize % 3 != 0)
84		throw InvalidArgument("InvertibleESIGNFunction: modulus size must be divisible by 3");
85
86	m_e = param.GetValueWithDefault("PublicExponent", Integer(32));
87
88	if (m_e < 8)
89		throw InvalidArgument("InvertibleESIGNFunction: public exponents less than 8 may not be secure");
90
91	// VC70 workaround: putting these after primeParam causes overlapped stack allocation
92	ConstByteArrayParameter seedParam;
93	SecByteBlock seed;
94
95	const Integer minP = Integer(204) << (modulusSize/3-8);
96	const Integer maxP = Integer::Power2(modulusSize/3)-1;
97	AlgorithmParameters primeParam = MakeParameters("Min", minP)("Max", maxP)("RandomNumberType", Integer::PRIME);
98
99	if (param.GetValue("Seed", seedParam))
100	{
101		seed.resize(seedParam.size() + 4);
102		memcpy(seed + 4, seedParam.begin(), seedParam.size());
103
104		PutWord(false, BIG_ENDIAN_ORDER, seed, (word32)0);
105		m_p.GenerateRandom(rng, CombinedNameValuePairs(primeParam, MakeParameters("Seed", ConstByteArrayParameter(seed))));
106		PutWord(false, BIG_ENDIAN_ORDER, seed, (word32)1);
107		m_q.GenerateRandom(rng, CombinedNameValuePairs(primeParam, MakeParameters("Seed", ConstByteArrayParameter(seed))));
108	}
109	else
110	{
111		m_p.GenerateRandom(rng, primeParam);
112		m_q.GenerateRandom(rng, primeParam);
113	}
114
115	m_n = m_p * m_p * m_q;
116
117	assert(m_n.BitCount() == modulusSize);
118}
119
120void InvertibleESIGNFunction::BERDecode(BufferedTransformation &bt)
121{
122	BERSequenceDecoder privateKey(bt);
123		m_n.BERDecode(privateKey);
124		m_e.BERDecode(privateKey);
125		m_p.BERDecode(privateKey);
126		m_q.BERDecode(privateKey);
127	privateKey.MessageEnd();
128}
129
130void InvertibleESIGNFunction::DEREncode(BufferedTransformation &bt) const
131{
132	DERSequenceEncoder privateKey(bt);
133		m_n.DEREncode(privateKey);
134		m_e.DEREncode(privateKey);
135		m_p.DEREncode(privateKey);
136		m_q.DEREncode(privateKey);
137	privateKey.MessageEnd();
138}
139
140Integer InvertibleESIGNFunction::CalculateRandomizedInverse(RandomNumberGenerator &rng, const Integer &x) const
141{
142	DoQuickSanityCheck();
143
144	Integer pq = m_p * m_q;
145	Integer p2 = m_p * m_p;
146	Integer r, z, re, a, w0, w1;
147
148	do
149	{
150		r.Randomize(rng, Integer::Zero(), pq);
151		z = x << (2*GetK()+2);
152		re = a_exp_b_mod_c(r, m_e, m_n);
153		a = (z - re) % m_n;
154		Integer::Divide(w1, w0, a, pq);
155		if (w1.NotZero())
156		{
157			++w0;
158			w1 = pq - w1;
159		}
160	}
161	while ((w1 >> 2*GetK()+1).IsPositive());
162
163	ModularArithmetic modp(m_p);
164	Integer t = modp.Divide(w0 * r % m_p, m_e * re % m_p);
165	Integer s = r + t*pq;
166	assert(s < m_n);
167/*
168	using namespace std;
169	cout << "f = " << x << endl;
170	cout << "r = " << r << endl;
171	cout << "z = " << z << endl;
172	cout << "a = " << a << endl;
173	cout << "w0 = " << w0 << endl;
174	cout << "w1 = " << w1 << endl;
175	cout << "t = " << t << endl;
176	cout << "s = " << s << endl;
177*/
178	return s;
179}
180
181bool InvertibleESIGNFunction::Validate(RandomNumberGenerator &rng, unsigned int level) const
182{
183	bool pass = ESIGNFunction::Validate(rng, level);
184	pass = pass && m_p > Integer::One() && m_p.IsOdd() && m_p < m_n;
185	pass = pass && m_q > Integer::One() && m_q.IsOdd() && m_q < m_n;
186	pass = pass && m_p.BitCount() == m_q.BitCount();
187	if (level >= 1)
188		pass = pass && m_p * m_p * m_q == m_n;
189	if (level >= 2)
190		pass = pass && VerifyPrime(rng, m_p, level-2) && VerifyPrime(rng, m_q, level-2);
191	return pass;
192}
193
194bool InvertibleESIGNFunction::GetVoidValue(const char *name, const std::type_info &valueType, void *pValue) const
195{
196	return GetValueHelper<ESIGNFunction>(this, name, valueType, pValue).Assignable()
197		CRYPTOPP_GET_FUNCTION_ENTRY(Prime1)
198		CRYPTOPP_GET_FUNCTION_ENTRY(Prime2)
199		;
200}
201
202void InvertibleESIGNFunction::AssignFrom(const NameValuePairs &source)
203{
204	AssignFromHelper<ESIGNFunction>(this, source)
205		CRYPTOPP_SET_FUNCTION_ENTRY(Prime1)
206		CRYPTOPP_SET_FUNCTION_ENTRY(Prime2)
207		;
208}
209
210NAMESPACE_END
211