Crypto++ 8.9
Free C++ class library of cryptographic schemes
rsa.cpp
1// rsa.cpp - originally 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 "sha.h"
7#include "oids.h"
8#include "modarith.h"
9#include "nbtheory.h"
10#include "algparam.h"
11#include "fips140.h"
12#include "pkcspad.h"
13
14#if defined(CRYPTOPP_DEBUG) && !defined(CRYPTOPP_DOXYGEN_PROCESSING) && !defined(CRYPTOPP_IS_DLL)
15#include "sha3.h"
16#include "pssr.h"
17NAMESPACE_BEGIN(CryptoPP)
18void RSA_TestInstantiations()
19{
23 RSASS<PKCS1v15, SHA1>::Verifier x4(x2.GetKey());
25#ifndef __MWERKS__
27 x3 = x2;
28 x6 = x2;
29#endif
31#ifndef __GNUC__
33#endif
34 RSAES<OAEP<SHA1> >::Encryptor x9(x2);
35 x4 = x2.GetKey();
36
41}
42NAMESPACE_END
43#endif
44
45#ifndef CRYPTOPP_IMPORTS
46
47NAMESPACE_BEGIN(CryptoPP)
48
50{
51 return ASN1::rsaEncryption();
52}
53
55{
56 BERSequenceDecoder seq(bt);
57 m_n.BERDecode(seq);
58 m_e.BERDecode(seq);
59 seq.MessageEnd();
60}
61
63{
64 DERSequenceEncoder seq(bt);
65 m_n.DEREncode(seq);
66 m_e.DEREncode(seq);
67 seq.MessageEnd();
68}
69
71{
73 return a_exp_b_mod_c(x, m_e, m_n);
74}
75
76bool RSAFunction::Validate(RandomNumberGenerator& rng, unsigned int level) const
77{
78 CRYPTOPP_UNUSED(rng), CRYPTOPP_UNUSED(level);
79
80 bool pass = true;
81 pass = pass && m_n > Integer::One() && m_n.IsOdd();
82 CRYPTOPP_ASSERT(pass);
83 pass = pass && m_e > Integer::One() && m_e.IsOdd() && m_e < m_n;
84 CRYPTOPP_ASSERT(pass);
85 return pass;
86}
87
88bool RSAFunction::GetVoidValue(const char *name, const std::type_info &valueType, void *pValue) const
89{
90 return GetValueHelper(this, name, valueType, pValue).Assignable()
91 CRYPTOPP_GET_FUNCTION_ENTRY(Modulus)
92 CRYPTOPP_GET_FUNCTION_ENTRY(PublicExponent)
93 ;
94}
95
97{
98 AssignFromHelper(this, source)
99 CRYPTOPP_SET_FUNCTION_ENTRY(Modulus)
100 CRYPTOPP_SET_FUNCTION_ENTRY(PublicExponent)
101 ;
102}
103
104// *****************************************************************************
105
106class RSAPrimeSelector : public PrimeSelector
107{
108public:
109 RSAPrimeSelector(const Integer &e) : m_e(e) {}
110 bool IsAcceptable(const Integer &candidate) const {return RelativelyPrime(m_e, candidate-Integer::One());}
111 Integer m_e;
112};
113
115{
116 int modulusSize = 2048;
117 alg.GetIntValue(Name::ModulusSize(), modulusSize) || alg.GetIntValue(Name::KeySize(), modulusSize);
118
119 CRYPTOPP_ASSERT(modulusSize >= 16);
120 if (modulusSize < 16)
121 throw InvalidArgument("InvertibleRSAFunction: specified modulus size is too small");
122
124
125 CRYPTOPP_ASSERT(m_e >= 3); CRYPTOPP_ASSERT(!m_e.IsEven());
126 if (m_e < 3 || m_e.IsEven())
127 throw InvalidArgument("InvertibleRSAFunction: invalid public exponent");
128
129 // Do this in a loop for small moduli. For small moduli, u' == 0 when p == q.
130 // https://github.com/weidai11/cryptopp/issues/1136
131 do
132 {
133 RSAPrimeSelector selector(m_e);
134 AlgorithmParameters primeParam = MakeParametersForTwoPrimesOfEqualSize(modulusSize)
135 (Name::PointerToPrimeSelector(), selector.GetSelectorPointer());
136 m_p.GenerateRandom(rng, primeParam);
137 m_q.GenerateRandom(rng, primeParam);
138
139 m_d = m_e.InverseMod(LCM(m_p-1, m_q-1));
141
142 m_dp = m_d % (m_p-1);
143 m_dq = m_d % (m_q-1);
144 m_n = m_p * m_q;
145 m_u = m_q.InverseMod(m_p);
146 } while (m_u.IsZero());
147
149 {
150 RSASS<PKCS1v15, SHA1>::Signer signer(*this);
151 RSASS<PKCS1v15, SHA1>::Verifier verifier(signer);
152 SignaturePairwiseConsistencyTest_FIPS_140_Only(signer, verifier);
153
154 RSAES<OAEP<SHA1> >::Decryptor decryptor(*this);
155 RSAES<OAEP<SHA1> >::Encryptor encryptor(decryptor);
156 EncryptionPairwiseConsistencyTest_FIPS_140_Only(encryptor, decryptor);
157 }
158}
159
160void InvertibleRSAFunction::Initialize(RandomNumberGenerator &rng, unsigned int keybits, const Integer &e)
161{
163}
164
165void InvertibleRSAFunction::Initialize(const Integer &n, const Integer &e, const Integer &d)
166{
167 if (n.IsEven() || e.IsEven() || d.IsEven())
168 throw InvalidArgument("InvertibleRSAFunction: input is not a valid RSA private key");
169
170 m_n = n;
171 m_e = e;
172 m_d = d;
173
174 Integer r = --(d*e);
175 unsigned int s = 0;
176 while (r.IsEven())
177 {
178 r >>= 1;
179 s++;
180 }
181
182 ModularArithmetic modn(n);
183 for (Integer i = 2; ; ++i)
184 {
185 Integer a = modn.Exponentiate(i, r);
186 if (a == 1)
187 continue;
188 Integer b;
189 unsigned int j = 0;
190 while (a != n-1)
191 {
192 b = modn.Square(a);
193 if (b == 1)
194 {
195 m_p = GCD(a-1, n);
196 m_q = n/m_p;
197 m_dp = m_d % (m_p-1);
198 m_dq = m_d % (m_q-1);
199 m_u = m_q.InverseMod(m_p);
200 return;
201 }
202 if (++j == s)
203 throw InvalidArgument("InvertibleRSAFunction: input is not a valid RSA private key");
204 a = b;
205 }
206 }
207}
208
210{
211 BERSequenceDecoder privateKey(bt);
212 word32 version;
213 BERDecodeUnsigned<word32>(privateKey, version, INTEGER, 0, 0); // check version
214 m_n.BERDecode(privateKey);
215 m_e.BERDecode(privateKey);
216 m_d.BERDecode(privateKey);
217 m_p.BERDecode(privateKey);
218 m_q.BERDecode(privateKey);
219 m_dp.BERDecode(privateKey);
220 m_dq.BERDecode(privateKey);
221 m_u.BERDecode(privateKey);
222 privateKey.MessageEnd();
223}
224
226{
227 DERSequenceEncoder privateKey(bt);
228 DEREncodeUnsigned<word32>(privateKey, 0); // version
229 m_n.DEREncode(privateKey);
230 m_e.DEREncode(privateKey);
231 m_d.DEREncode(privateKey);
232 m_p.DEREncode(privateKey);
233 m_q.DEREncode(privateKey);
234 m_dp.DEREncode(privateKey);
235 m_dq.DEREncode(privateKey);
236 m_u.DEREncode(privateKey);
237 privateKey.MessageEnd();
238}
239
241{
243 ModularArithmetic modn(m_n);
244 Integer r, rInv;
245 do { // do this in a loop for people using small numbers for testing
246 r.Randomize(rng, Integer::One(), m_n - Integer::One());
247 rInv = modn.MultiplicativeInverse(r);
248 } while (rInv.IsZero());
249 Integer re = modn.Exponentiate(r, m_e);
250 re = modn.Multiply(re, x); // blind
251 // here we follow the notation of PKCS #1 and let u=q inverse mod p
252 // but in ModRoot, u=p inverse mod q, so we reverse the order of p and q
253 Integer y = ModularRoot(re, m_dq, m_dp, m_q, m_p, m_u);
254 y = modn.Multiply(y, rInv); // unblind
255 if (modn.Exponentiate(y, m_e) != x) // check
256 throw Exception(Exception::OTHER_ERROR, "InvertibleRSAFunction: computational error during private key operation");
257 return y;
258}
259
260bool InvertibleRSAFunction::Validate(RandomNumberGenerator &rng, unsigned int level) const
261{
262 bool pass = RSAFunction::Validate(rng, level);
263 CRYPTOPP_ASSERT(pass);
264 pass = pass && m_p > Integer::One() && m_p.IsOdd() && m_p < m_n;
265 CRYPTOPP_ASSERT(pass);
266 pass = pass && m_q > Integer::One() && m_q.IsOdd() && m_q < m_n;
267 CRYPTOPP_ASSERT(pass);
268 pass = pass && m_d > Integer::One() && m_d.IsOdd() && m_d < m_n;
269 CRYPTOPP_ASSERT(pass);
270 pass = pass && m_dp > Integer::One() && m_dp.IsOdd() && m_dp < m_p;
271 CRYPTOPP_ASSERT(pass);
272 pass = pass && m_dq > Integer::One() && m_dq.IsOdd() && m_dq < m_q;
273 CRYPTOPP_ASSERT(pass);
274 pass = pass && m_u.IsPositive() && m_u < m_p;
275 CRYPTOPP_ASSERT(pass);
276 if (level >= 1)
277 {
278 pass = pass && m_p * m_q == m_n;
279 CRYPTOPP_ASSERT(pass);
280 pass = pass && m_e*m_d % LCM(m_p-1, m_q-1) == 1;
281 CRYPTOPP_ASSERT(pass);
282 pass = pass && m_dp == m_d%(m_p-1) && m_dq == m_d%(m_q-1);
283 CRYPTOPP_ASSERT(pass);
284 pass = pass && m_u * m_q % m_p == 1;
285 CRYPTOPP_ASSERT(pass);
286 }
287 if (level >= 2)
288 {
289 pass = pass && VerifyPrime(rng, m_p, level-2) && VerifyPrime(rng, m_q, level-2);
290 CRYPTOPP_ASSERT(pass);
291 }
292 return pass;
293}
294
295bool InvertibleRSAFunction::GetVoidValue(const char *name, const std::type_info &valueType, void *pValue) const
296{
297 return GetValueHelper<RSAFunction>(this, name, valueType, pValue).Assignable()
298 CRYPTOPP_GET_FUNCTION_ENTRY(Prime1)
299 CRYPTOPP_GET_FUNCTION_ENTRY(Prime2)
300 CRYPTOPP_GET_FUNCTION_ENTRY(PrivateExponent)
301 CRYPTOPP_GET_FUNCTION_ENTRY(ModPrime1PrivateExponent)
302 CRYPTOPP_GET_FUNCTION_ENTRY(ModPrime2PrivateExponent)
303 CRYPTOPP_GET_FUNCTION_ENTRY(MultiplicativeInverseOfPrime2ModPrime1)
304 ;
305}
306
308{
309 AssignFromHelper<RSAFunction>(this, source)
310 CRYPTOPP_SET_FUNCTION_ENTRY(Prime1)
311 CRYPTOPP_SET_FUNCTION_ENTRY(Prime2)
312 CRYPTOPP_SET_FUNCTION_ENTRY(PrivateExponent)
313 CRYPTOPP_SET_FUNCTION_ENTRY(ModPrime1PrivateExponent)
314 CRYPTOPP_SET_FUNCTION_ENTRY(ModPrime2PrivateExponent)
315 CRYPTOPP_SET_FUNCTION_ENTRY(MultiplicativeInverseOfPrime2ModPrime1)
316 ;
317}
318
319// *****************************************************************************
320
322{
324 return t % 16 == 12 ? t : m_n - t;
325}
326
328{
330 return STDMIN(t, m_n-t);
331}
332
333NAMESPACE_END
334
335#endif
Classes for working with NameValuePairs.
AlgorithmParameters MakeParameters(const char *name, const T &value, bool throwIfNotUsed=true)
Create an object that implements NameValuePairs.
Definition algparam.h:508
Classes and functions for working with ANS.1 objects.
@ INTEGER
ASN.1 Integer.
Definition asn.h:34
An object that implements NameValuePairs.
Definition algparam.h:426
BER Sequence Decoder.
Definition asn.h:526
Interface for buffered transformations.
Definition cryptlib.h:1657
void DoQuickSanityCheck() const
Perform a quick sanity check.
Definition cryptlib.h:2498
DER Sequence Encoder.
Definition asn.h:558
Base class for all exceptions thrown by the library.
Definition cryptlib.h:164
@ OTHER_ERROR
Some other error occurred not belonging to other categories.
Definition cryptlib.h:182
Multiple precision integer with arithmetic operations.
Definition integer.h:50
void DEREncode(BufferedTransformation &bt) const
Encode in DER format.
void GenerateRandom(RandomNumberGenerator &rng, const NameValuePairs &params=g_nullNameValuePairs)
Generate a random number.
Definition integer.h:509
bool IsPositive() const
Determines if the Integer is positive.
Definition integer.h:347
void Randomize(RandomNumberGenerator &rng, size_t bitCount)
Set this Integer to random integer.
void BERDecode(const byte *input, size_t inputLen)
Decode from BER format.
bool IsZero() const
Determines if the Integer is 0.
Definition integer.h:335
Integer MultiplicativeInverse() const
Calculate multiplicative inverse.
bool IsOdd() const
Determines if the Integer is odd parity.
Definition integer.h:356
Integer InverseMod(const Integer &n) const
Calculate multiplicative inverse.
static const Integer & One()
Integer representing 1.
bool IsEven() const
Determines if the Integer is even parity.
Definition integer.h:353
An invalid argument was detected.
Definition cryptlib.h:208
Integer CalculateInverse(RandomNumberGenerator &rng, const Integer &x) const
Calculates the inverse of an element.
bool Validate(RandomNumberGenerator &rng, unsigned int level) const
Check this object for errors.
void Initialize(RandomNumberGenerator &rng, unsigned int modulusBits, const Integer &e=17)
Create a RSA private key.
void GenerateRandom(RandomNumberGenerator &rng, const NameValuePairs &alg)
Generate a random key or crypto parameters.
void AssignFrom(const NameValuePairs &source)
Assign values to this object.
void DEREncodePrivateKey(BufferedTransformation &bt) const
Encode privateKey part of privateKeyInfo.
bool GetVoidValue(const char *name, const std::type_info &valueType, void *pValue) const
Get a named value.
Integer CalculateInverse(RandomNumberGenerator &rng, const Integer &x) const
Calculates the inverse of an element.
void BERDecodePrivateKey(BufferedTransformation &bt, bool parametersPresent, size_t size)
Decode privateKey part of privateKeyInfo.
Ring of congruence classes modulo n.
Definition modarith.h:44
Interface for retrieving values given their names.
Definition cryptlib.h:327
T GetValueWithDefault(const char *name, T defaultValue) const
Get a named value.
Definition cryptlib.h:397
CRYPTOPP_DLL bool GetIntValue(const char *name, int &value) const
Get a named value with type int.
Definition cryptlib.h:420
Object Identifier.
Definition asn.h:265
Template implementing constructors for public key algorithm classes.
Definition pubkey.h:2198
Application callback to signal suitability of a candidate prime.
Definition nbtheory.h:117
Integer ApplyFunction(const Integer &x) const
Applies the trapdoor.
bool Validate(RandomNumberGenerator &rng, unsigned int level) const
Check this object for errors.
OID GetAlgorithmID() const
Retrieves the OID of the algorithm.
Integer ApplyFunction(const Integer &x) const
Applies the trapdoor.
void BERDecodePublicKey(BufferedTransformation &bt, bool parametersPresent, size_t size)
Decode subjectPublicKey part of subjectPublicKeyInfo.
bool GetVoidValue(const char *name, const std::type_info &valueType, void *pValue) const
Get a named value.
void DEREncodePublicKey(BufferedTransformation &bt) const
Encode subjectPublicKey part of subjectPublicKeyInfo.
void AssignFrom(const NameValuePairs &source)
Assign values to this object.
Interface for random number generators.
Definition cryptlib.h:1440
unsigned int word32
32-bit unsigned datatype
Definition config_int.h:72
CRYPTOPP_DLL RandomNumberGenerator & NullRNG()
Random Number Generator that does not produce random numbers.
Classes and functions for the FIPS 140-2 validated library.
CRYPTOPP_DLL bool FIPS_140_2_ComplianceEnabled()
Determines whether the library provides FIPS validated cryptography.
const T & STDMIN(const T &a, const T &b)
Replacement function for std::min.
Definition misc.h:657
Class file for performing modular arithmetic.
Crypto++ library namespace.
const char * PointerToPrimeSelector()
const PrimeSelector *
Definition argnames.h:42
const char * KeySize()
int, in bits
Definition argnames.h:29
const char * PublicExponent()
Integer.
Definition argnames.h:34
const char * ModulusSize()
int, in bits
Definition argnames.h:30
Classes and functions for number theoretic operations.
bool RelativelyPrime(const Integer &a, const Integer &b)
Determine relative primality.
Definition nbtheory.h:153
CRYPTOPP_DLL bool VerifyPrime(RandomNumberGenerator &rng, const Integer &p, unsigned int level=1)
Verifies a number is probably prime.
CRYPTOPP_DLL Integer ModularRoot(const Integer &a, const Integer &dp, const Integer &dq, const Integer &p, const Integer &q, const Integer &u)
Extract a modular root.
Integer GCD(const Integer &a, const Integer &b)
Calculate the greatest common divisor.
Definition nbtheory.h:146
Integer LCM(const Integer &a, const Integer &b)
Calculate the least common multiple.
Definition nbtheory.h:160
ASN.1 object identifiers for algorithms and schemes.
Precompiled header file.
Classes for PKCS padding schemes.
Classes for probabilistic signature schemes.
Classes for the RSA cryptosystem.
Classes for SHA3 message digests.
Classes for SHA-1 and SHA-2 family of message digests.
RSA encryption algorithm.
Definition rsa.h:173
#define CRYPTOPP_ASSERT(exp)
Debugging and diagnostic assertion.
Definition trap.h:68