1// rsa.cpp - written and placed in the public domain by Wei Dai
2
3#include "pch.h"
4#include "rsa.h"
5#include "asn.h"
6#include "oids.h"
7#include "modarith.h"
8#include "nbtheory.h"
9#include "sha.h"
10#include "algparam.h"
11#include "fips140.h"
12
13#if !defined(NDEBUG) && !defined(CRYPTOPP_IS_DLL)
14#include "pssr.h"
15NAMESPACE_BEGIN(CryptoPP)
16void RSA_TestInstantiations()
17{
18	RSASS<PKCS1v15, SHA>::Verifier x1(1, 1);
19	RSASS<PKCS1v15, SHA>::Signer x2(NullRNG(), 1);
20	RSASS<PKCS1v15, SHA>::Verifier x3(x2);
21	RSASS<PKCS1v15, SHA>::Verifier x4(x2.GetKey());
22	RSASS<PSS, SHA>::Verifier x5(x3);
23#ifndef __MWERKS__
24	RSASS<PSSR, SHA>::Signer x6 = x2;
25	x3 = x2;
26	x6 = x2;
27#endif
28	RSAES<PKCS1v15>::Encryptor x7(x2);
29#ifndef __GNUC__
30	RSAES<PKCS1v15>::Encryptor x8(x3);
31#endif
32	RSAES<OAEP<SHA> >::Encryptor x9(x2);
33
34	x4 = x2.GetKey();
35}
36NAMESPACE_END
37#endif
38
39#ifndef CRYPTOPP_IMPORTS
40
41NAMESPACE_BEGIN(CryptoPP)
42
43OID RSAFunction::GetAlgorithmID() const
44{
45	return ASN1::rsaEncryption();
46}
47
48void RSAFunction::BERDecodePublicKey(BufferedTransformation &bt, bool, size_t)
49{
50	BERSequenceDecoder seq(bt);
51		m_n.BERDecode(seq);
52		m_e.BERDecode(seq);
53	seq.MessageEnd();
54}
55
56void RSAFunction::DEREncodePublicKey(BufferedTransformation &bt) const
57{
58	DERSequenceEncoder seq(bt);
59		m_n.DEREncode(seq);
60		m_e.DEREncode(seq);
61	seq.MessageEnd();
62}
63
64Integer RSAFunction::ApplyFunction(const Integer &x) const
65{
66	DoQuickSanityCheck();
67	return a_exp_b_mod_c(x, m_e, m_n);
68}
69
70bool RSAFunction::Validate(RandomNumberGenerator &rng, unsigned int level) const
71{
72	bool pass = true;
73	pass = pass && m_n > Integer::One() && m_n.IsOdd();
74	pass = pass && m_e > Integer::One() && m_e.IsOdd() && m_e < m_n;
75	return pass;
76}
77
78bool RSAFunction::GetVoidValue(const char *name, const std::type_info &valueType, void *pValue) const
79{
80	return GetValueHelper(this, name, valueType, pValue).Assignable()
81		CRYPTOPP_GET_FUNCTION_ENTRY(Modulus)
82		CRYPTOPP_GET_FUNCTION_ENTRY(PublicExponent)
83		;
84}
85
86void RSAFunction::AssignFrom(const NameValuePairs &source)
87{
88	AssignFromHelper(this, source)
89		CRYPTOPP_SET_FUNCTION_ENTRY(Modulus)
90		CRYPTOPP_SET_FUNCTION_ENTRY(PublicExponent)
91		;
92}
93
94// *****************************************************************************
95
96class RSAPrimeSelector : public PrimeSelector
97{
98public:
99	RSAPrimeSelector(const Integer &e) : m_e(e) {}
100	bool IsAcceptable(const Integer &candidate) const {return RelativelyPrime(m_e, candidate-Integer::One());}
101	Integer m_e;
102};
103
104void InvertibleRSAFunction::GenerateRandom(RandomNumberGenerator &rng, const NameValuePairs &alg)
105{
106	int modulusSize = 2048;
107	alg.GetIntValue(Name::ModulusSize(), modulusSize) || alg.GetIntValue(Name::KeySize(), modulusSize);
108
109	if (modulusSize < 16)
110		throw InvalidArgument("InvertibleRSAFunction: specified modulus size is too small");
111
112	m_e = alg.GetValueWithDefault(Name::PublicExponent(), Integer(17));
113
114	if (m_e < 3 || m_e.IsEven())
115		throw InvalidArgument("InvertibleRSAFunction: invalid public exponent");
116
117	RSAPrimeSelector selector(m_e);
118	AlgorithmParameters primeParam = MakeParametersForTwoPrimesOfEqualSize(modulusSize)
119		(Name::PointerToPrimeSelector(), selector.GetSelectorPointer());
120	m_p.GenerateRandom(rng, primeParam);
121	m_q.GenerateRandom(rng, primeParam);
122
123	m_d = m_e.InverseMod(LCM(m_p-1, m_q-1));
124	assert(m_d.IsPositive());
125
126	m_dp = m_d % (m_p-1);
127	m_dq = m_d % (m_q-1);
128	m_n = m_p * m_q;
129	m_u = m_q.InverseMod(m_p);
130
131	if (FIPS_140_2_ComplianceEnabled())
132	{
133		RSASS<PKCS1v15, SHA>::Signer signer(*this);
134		RSASS<PKCS1v15, SHA>::Verifier verifier(signer);
135		SignaturePairwiseConsistencyTest_FIPS_140_Only(signer, verifier);
136
137		RSAES<OAEP<SHA> >::Decryptor decryptor(*this);
138		RSAES<OAEP<SHA> >::Encryptor encryptor(decryptor);
139		EncryptionPairwiseConsistencyTest_FIPS_140_Only(encryptor, decryptor);
140	}
141}
142
143void InvertibleRSAFunction::Initialize(RandomNumberGenerator &rng, unsigned int keybits, const Integer &e)
144{
145	GenerateRandom(rng, MakeParameters(Name::ModulusSize(), (int)keybits)(Name::PublicExponent(), e+e.IsEven()));
146}
147
148void InvertibleRSAFunction::Initialize(const Integer &n, const Integer &e, const Integer &d)
149{
150	if (n.IsEven() || e.IsEven() | d.IsEven())
151		throw InvalidArgument("InvertibleRSAFunction: input is not a valid RSA private key");
152
153	m_n = n;
154	m_e = e;
155	m_d = d;
156
157	Integer r = --(d*e);
158	unsigned int s = 0;
159	while (r.IsEven())
160	{
161		r >>= 1;
162		s++;
163	}
164
165	ModularArithmetic modn(n);
166	for (Integer i = 2; ; ++i)
167	{
168		Integer a = modn.Exponentiate(i, r);
169		if (a == 1)
170			continue;
171		Integer b;
172		unsigned int j = 0;
173		while (a != n-1)
174		{
175			b = modn.Square(a);
176			if (b == 1)
177			{
178				m_p = GCD(a-1, n);
179				m_q = n/m_p;
180				m_dp = m_d % (m_p-1);
181				m_dq = m_d % (m_q-1);
182				m_u = m_q.InverseMod(m_p);
183				return;
184			}
185			if (++j == s)
186				throw InvalidArgument("InvertibleRSAFunction: input is not a valid RSA private key");
187			a = b;
188		}
189	}
190}
191
192void InvertibleRSAFunction::BERDecodePrivateKey(BufferedTransformation &bt, bool, size_t)
193{
194	BERSequenceDecoder privateKey(bt);
195		word32 version;
196		BERDecodeUnsigned<word32>(privateKey, version, INTEGER, 0, 0);	// check version
197		m_n.BERDecode(privateKey);
198		m_e.BERDecode(privateKey);
199		m_d.BERDecode(privateKey);
200		m_p.BERDecode(privateKey);
201		m_q.BERDecode(privateKey);
202		m_dp.BERDecode(privateKey);
203		m_dq.BERDecode(privateKey);
204		m_u.BERDecode(privateKey);
205	privateKey.MessageEnd();
206}
207
208void InvertibleRSAFunction::DEREncodePrivateKey(BufferedTransformation &bt) const
209{
210	DERSequenceEncoder privateKey(bt);
211		DEREncodeUnsigned<word32>(privateKey, 0);	// version
212		m_n.DEREncode(privateKey);
213		m_e.DEREncode(privateKey);
214		m_d.DEREncode(privateKey);
215		m_p.DEREncode(privateKey);
216		m_q.DEREncode(privateKey);
217		m_dp.DEREncode(privateKey);
218		m_dq.DEREncode(privateKey);
219		m_u.DEREncode(privateKey);
220	privateKey.MessageEnd();
221}
222
223Integer InvertibleRSAFunction::CalculateInverse(RandomNumberGenerator &rng, const Integer &x) const
224{
225	DoQuickSanityCheck();
226	ModularArithmetic modn(m_n);
227	Integer r, rInv;
228	do {	// do this in a loop for people using small numbers for testing
229		r.Randomize(rng, Integer::One(), m_n - Integer::One());
230		rInv = modn.MultiplicativeInverse(r);
231	} while (rInv.IsZero());
232	Integer re = modn.Exponentiate(r, m_e);
233	re = modn.Multiply(re, x);			// blind
234	// here we follow the notation of PKCS #1 and let u=q inverse mod p
235	// but in ModRoot, u=p inverse mod q, so we reverse the order of p and q
236	Integer y = ModularRoot(re, m_dq, m_dp, m_q, m_p, m_u);
237	y = modn.Multiply(y, rInv);				// unblind
238	if (modn.Exponentiate(y, m_e) != x)		// check
239		throw Exception(Exception::OTHER_ERROR, "InvertibleRSAFunction: computational error during private key operation");
240	return y;
241}
242
243bool InvertibleRSAFunction::Validate(RandomNumberGenerator &rng, unsigned int level) const
244{
245	bool pass = RSAFunction::Validate(rng, level);
246	pass = pass && m_p > Integer::One() && m_p.IsOdd() && m_p < m_n;
247	pass = pass && m_q > Integer::One() && m_q.IsOdd() && m_q < m_n;
248	pass = pass && m_d > Integer::One() && m_d.IsOdd() && m_d < m_n;
249	pass = pass && m_dp > Integer::One() && m_dp.IsOdd() && m_dp < m_p;
250	pass = pass && m_dq > Integer::One() && m_dq.IsOdd() && m_dq < m_q;
251	pass = pass && m_u.IsPositive() && m_u < m_p;
252	if (level >= 1)
253	{
254		pass = pass && m_p * m_q == m_n;
255		pass = pass && m_e*m_d % LCM(m_p-1, m_q-1) == 1;
256		pass = pass && m_dp == m_d%(m_p-1) && m_dq == m_d%(m_q-1);
257		pass = pass && m_u * m_q % m_p == 1;
258	}
259	if (level >= 2)
260		pass = pass && VerifyPrime(rng, m_p, level-2) && VerifyPrime(rng, m_q, level-2);
261	return pass;
262}
263
264bool InvertibleRSAFunction::GetVoidValue(const char *name, const std::type_info &valueType, void *pValue) const
265{
266	return GetValueHelper<RSAFunction>(this, name, valueType, pValue).Assignable()
267		CRYPTOPP_GET_FUNCTION_ENTRY(Prime1)
268		CRYPTOPP_GET_FUNCTION_ENTRY(Prime2)
269		CRYPTOPP_GET_FUNCTION_ENTRY(PrivateExponent)
270		CRYPTOPP_GET_FUNCTION_ENTRY(ModPrime1PrivateExponent)
271		CRYPTOPP_GET_FUNCTION_ENTRY(ModPrime2PrivateExponent)
272		CRYPTOPP_GET_FUNCTION_ENTRY(MultiplicativeInverseOfPrime2ModPrime1)
273		;
274}
275
276void InvertibleRSAFunction::AssignFrom(const NameValuePairs &source)
277{
278	AssignFromHelper<RSAFunction>(this, source)
279		CRYPTOPP_SET_FUNCTION_ENTRY(Prime1)
280		CRYPTOPP_SET_FUNCTION_ENTRY(Prime2)
281		CRYPTOPP_SET_FUNCTION_ENTRY(PrivateExponent)
282		CRYPTOPP_SET_FUNCTION_ENTRY(ModPrime1PrivateExponent)
283		CRYPTOPP_SET_FUNCTION_ENTRY(ModPrime2PrivateExponent)
284		CRYPTOPP_SET_FUNCTION_ENTRY(MultiplicativeInverseOfPrime2ModPrime1)
285		;
286}
287
288// *****************************************************************************
289
290Integer RSAFunction_ISO::ApplyFunction(const Integer &x) const
291{
292	Integer t = RSAFunction::ApplyFunction(x);
293	return t % 16 == 12 ? t : m_n - t;
294}
295
296Integer InvertibleRSAFunction_ISO::CalculateInverse(RandomNumberGenerator &rng, const Integer &x) const
297{
298	Integer t = InvertibleRSAFunction::CalculateInverse(rng, x);
299	return STDMIN(t, m_n-t);
300}
301
302NAMESPACE_END
303
304#endif
305