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"
17 NAMESPACE_BEGIN(CryptoPP)
18 void RSA_TestInstantiations()
19 {
20 RSASS<PKCS1v15, SHA1>::Verifier x1(1, 1);
21 RSASS<PKCS1v15, SHA1>::Signer x2(NullRNG(), 1);
22 RSASS<PKCS1v15, SHA1>::Verifier x3(x2);
23 RSASS<PKCS1v15, SHA1>::Verifier x4(x2.GetKey());
24 RSASS<PSS, SHA1>::Verifier x5(x3);
25 #ifndef __MWERKS__
26 RSASS<PSSR, SHA1>::Signer x6 = x2;
27 x3 = x2;
28 x6 = x2;
29 #endif
30 RSAES<PKCS1v15>::Encryptor x7(x2);
31 #ifndef __GNUC__
32 RSAES<PKCS1v15>::Encryptor x8(x3);
33 #endif
34 RSAES<OAEP<SHA1> >::Encryptor x9(x2);
35 x4 = x2.GetKey();
36
37 RSASS<PKCS1v15, SHA3_256>::Verifier x10(1, 1);
38 RSASS<PKCS1v15, SHA3_256>::Signer x11(NullRNG(), 1);
39 RSASS<PKCS1v15, SHA3_256>::Verifier x12(x11);
40 RSASS<PKCS1v15, SHA3_256>::Verifier x13(x11.GetKey());
41 }
42 NAMESPACE_END
43 #endif
44
45 #ifndef CRYPTOPP_IMPORTS
46
47 NAMESPACE_BEGIN(CryptoPP)
48
49 OID RSAFunction::GetAlgorithmID() const
50 {
51 return ASN1::rsaEncryption();
52 }
53
54 void RSAFunction::BERDecodePublicKey(BufferedTransformation &bt, bool, size_t)
55 {
56 BERSequenceDecoder seq(bt);
57 m_n.BERDecode(seq);
58 m_e.BERDecode(seq);
59 seq.MessageEnd();
60 }
61
62 void RSAFunction::DEREncodePublicKey(BufferedTransformation &bt) const
63 {
64 DERSequenceEncoder seq(bt);
65 m_n.DEREncode(seq);
66 m_e.DEREncode(seq);
67 seq.MessageEnd();
68 }
69
70 Integer RSAFunction::ApplyFunction(const Integer &x) const
71 {
72 DoQuickSanityCheck();
73 return a_exp_b_mod_c(x, m_e, m_n);
74 }
75
76 bool 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
88 bool 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
96 void RSAFunction::AssignFrom(const NameValuePairs &source)
97 {
98 AssignFromHelper(this, source)
99 CRYPTOPP_SET_FUNCTION_ENTRY(Modulus)
100 CRYPTOPP_SET_FUNCTION_ENTRY(PublicExponent)
101 ;
102 }
103
104 // *****************************************************************************
105
106 class RSAPrimeSelector : public PrimeSelector
107 {
108 public:
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
114 void InvertibleRSAFunction::GenerateRandom(RandomNumberGenerator &rng, const NameValuePairs &alg)
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
123 m_e = alg.GetValueWithDefault(Name::PublicExponent(), Integer(17));
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));
140 CRYPTOPP_ASSERT(m_d.IsPositive());
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
148 if (FIPS_140_2_ComplianceEnabled())
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
160 void InvertibleRSAFunction::Initialize(RandomNumberGenerator &rng, unsigned int keybits, const Integer &e)
161 {
162 GenerateRandom(rng, MakeParameters(Name::ModulusSize(), (int)keybits)(Name::PublicExponent(), e+e.IsEven()));
163 }
164
165 void 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
209 void InvertibleRSAFunction::BERDecodePrivateKey(BufferedTransformation &bt, bool, size_t)
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
225 void InvertibleRSAFunction::DEREncodePrivateKey(BufferedTransformation &bt) const
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
240 Integer InvertibleRSAFunction::CalculateInverse(RandomNumberGenerator &rng, const Integer &x) const
241 {
242 DoQuickSanityCheck();
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
260 bool 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
295 bool 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
307 void InvertibleRSAFunction::AssignFrom(const NameValuePairs &source)
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
321 Integer RSAFunction_ISO::ApplyFunction(const Integer &x) const
322 {
323 Integer t = RSAFunction::ApplyFunction(x);
324 return t % 16 == 12 ? t : m_n - t;
325 }
326
327 Integer InvertibleRSAFunction_ISO::CalculateInverse(RandomNumberGenerator &rng, const Integer &x) const
328 {
329 Integer t = InvertibleRSAFunction::CalculateInverse(rng, x);
330 return STDMIN(t, m_n-t);
331 }
332
333 NAMESPACE_END
334
335 #endif
algparam.h
Classes for working with NameValuePairs.
MakeParameters
AlgorithmParameters MakeParameters(const char *name, const T &value, bool throwIfNotUsed=true)
Create an object that implements NameValuePairs.
Definition: algparam.h:508
asn.h
Classes and functions for working with ANS.1 objects.
INTEGER
@ INTEGER
ASN.1 Integer.
Definition: asn.h:34
AlgorithmParameters
An object that implements NameValuePairs.
Definition: algparam.h:426
BERSequenceDecoder
BER Sequence Decoder.
Definition: asn.h:526
BufferedTransformation
Interface for buffered transformations.
Definition: cryptlib.h:1657
CryptoMaterial::DoQuickSanityCheck
void DoQuickSanityCheck() const
Perform a quick sanity check.
Definition: cryptlib.h:2498
DERSequenceEncoder
DER Sequence Encoder.
Definition: asn.h:558
Exception
Base class for all exceptions thrown by the library.
Definition: cryptlib.h:164
Exception::OTHER_ERROR
@ OTHER_ERROR
Some other error occurred not belonging to other categories.
Definition: cryptlib.h:182
Integer
Multiple precision integer with arithmetic operations.
Definition: integer.h:50
Integer::DEREncode
void DEREncode(BufferedTransformation &bt) const
Encode in DER format.
Integer::GenerateRandom
void GenerateRandom(RandomNumberGenerator &rng, const NameValuePairs &params=g_nullNameValuePairs)
Generate a random number.
Definition: integer.h:509
Integer::IsPositive
bool IsPositive() const
Determines if the Integer is positive.
Definition: integer.h:347
Integer::Randomize
void Randomize(RandomNumberGenerator &rng, size_t bitCount)
Set this Integer to random integer.
Integer::BERDecode
void BERDecode(const byte *input, size_t inputLen)
Decode from BER format.
Integer::One
static const Integer & One()
Integer representing 1.
Integer::IsZero
bool IsZero() const
Determines if the Integer is 0.
Definition: integer.h:335
Integer::MultiplicativeInverse
Integer MultiplicativeInverse() const
Calculate multiplicative inverse.
Integer::IsOdd
bool IsOdd() const
Determines if the Integer is odd parity.
Definition: integer.h:356
Integer::InverseMod
Integer InverseMod(const Integer &n) const
Calculate multiplicative inverse.
Integer::IsEven
bool IsEven() const
Determines if the Integer is even parity.
Definition: integer.h:353
InvalidArgument
An invalid argument was detected.
Definition: cryptlib.h:208
InvertibleRSAFunction_ISO::CalculateInverse
Integer CalculateInverse(RandomNumberGenerator &rng, const Integer &x) const
Calculates the inverse of an element.
InvertibleRSAFunction::Validate
bool Validate(RandomNumberGenerator &rng, unsigned int level) const
Check this object for errors.
InvertibleRSAFunction::Initialize
void Initialize(RandomNumberGenerator &rng, unsigned int modulusBits, const Integer &e=17)
Create a RSA private key.
InvertibleRSAFunction::GenerateRandom
void GenerateRandom(RandomNumberGenerator &rng, const NameValuePairs &alg)
Generate a random key or crypto parameters.
InvertibleRSAFunction::AssignFrom
void AssignFrom(const NameValuePairs &source)
Assign values to this object.
InvertibleRSAFunction::DEREncodePrivateKey
void DEREncodePrivateKey(BufferedTransformation &bt) const
Encode privateKey part of privateKeyInfo.
InvertibleRSAFunction::GetVoidValue
bool GetVoidValue(const char *name, const std::type_info &valueType, void *pValue) const
Get a named value.
InvertibleRSAFunction::CalculateInverse
Integer CalculateInverse(RandomNumberGenerator &rng, const Integer &x) const
Calculates the inverse of an element.
InvertibleRSAFunction::BERDecodePrivateKey
void BERDecodePrivateKey(BufferedTransformation &bt, bool parametersPresent, size_t size)
Decode privateKey part of privateKeyInfo.
ModularArithmetic
Ring of congruence classes modulo n.
Definition: modarith.h:44
NameValuePairs
Interface for retrieving values given their names.
Definition: cryptlib.h:327
NameValuePairs::GetValueWithDefault
T GetValueWithDefault(const char *name, T defaultValue) const
Get a named value.
Definition: cryptlib.h:397
NameValuePairs::GetIntValue
CRYPTOPP_DLL bool GetIntValue(const char *name, int &value) const
Get a named value with type int.
Definition: cryptlib.h:420
OID
Object Identifier.
Definition: asn.h:265
PK_FinalTemplate
Template implementing constructors for public key algorithm classes.
Definition: pubkey.h:2198
PrimeSelector
Application callback to signal suitability of a candidate prime.
Definition: nbtheory.h:117
RSAFunction_ISO::ApplyFunction
Integer ApplyFunction(const Integer &x) const
Applies the trapdoor.
RSAFunction::Validate
bool Validate(RandomNumberGenerator &rng, unsigned int level) const
Check this object for errors.
RSAFunction::GetAlgorithmID
OID GetAlgorithmID() const
Retrieves the OID of the algorithm.
RSAFunction::ApplyFunction
Integer ApplyFunction(const Integer &x) const
Applies the trapdoor.
RSAFunction::BERDecodePublicKey
void BERDecodePublicKey(BufferedTransformation &bt, bool parametersPresent, size_t size)
Decode subjectPublicKey part of subjectPublicKeyInfo.
RSAFunction::GetVoidValue
bool GetVoidValue(const char *name, const std::type_info &valueType, void *pValue) const
Get a named value.
RSAFunction::DEREncodePublicKey
void DEREncodePublicKey(BufferedTransformation &bt) const
Encode subjectPublicKey part of subjectPublicKeyInfo.
RSAFunction::AssignFrom
void AssignFrom(const NameValuePairs &source)
Assign values to this object.
RandomNumberGenerator
Interface for random number generators.
Definition: cryptlib.h:1440
word32
unsigned int word32
32-bit unsigned datatype
Definition: config_int.h:72
NullRNG
CRYPTOPP_DLL RandomNumberGenerator & NullRNG()
Random Number Generator that does not produce random numbers.
fips140.h
Classes and functions for the FIPS 140-2 validated library.
FIPS_140_2_ComplianceEnabled
CRYPTOPP_DLL bool FIPS_140_2_ComplianceEnabled()
Determines whether the library provides FIPS validated cryptography.
STDMIN
const T & STDMIN(const T &a, const T &b)
Replacement function for std::min.
Definition: misc.h:657
modarith.h
Class file for performing modular arithmetic.
CryptoPP
Crypto++ library namespace.
Name::PrivateExponent
const char * PrivateExponent()
Integer.
Definition: argnames.h:35
Name::PointerToPrimeSelector
const char * PointerToPrimeSelector()
const PrimeSelector *
Definition: argnames.h:42
Name::ModPrime1PrivateExponent
const char * ModPrime1PrivateExponent()
Integer.
Definition: argnames.h:45
Name::Prime1
const char * Prime1()
Integer.
Definition: argnames.h:43
Name::KeySize
const char * KeySize()
int, in bits
Definition: argnames.h:29
Name::Modulus
const char * Modulus()
Integer.
Definition: argnames.h:33
Name::MultiplicativeInverseOfPrime2ModPrime1
const char * MultiplicativeInverseOfPrime2ModPrime1()
Integer.
Definition: argnames.h:47
Name::PublicExponent
const char * PublicExponent()
Integer.
Definition: argnames.h:34
Name::ModulusSize
const char * ModulusSize()
int, in bits
Definition: argnames.h:30
Name::ModPrime2PrivateExponent
const char * ModPrime2PrivateExponent()
Integer.
Definition: argnames.h:46
Name::Prime2
const char * Prime2()
Integer.
Definition: argnames.h:44
nbtheory.h
Classes and functions for number theoretic operations.
RelativelyPrime
bool RelativelyPrime(const Integer &a, const Integer &b)
Determine relative primality.
Definition: nbtheory.h:153
VerifyPrime
CRYPTOPP_DLL bool VerifyPrime(RandomNumberGenerator &rng, const Integer &p, unsigned int level=1)
Verifies a number is probably prime.
ModularRoot
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.
GCD
Integer GCD(const Integer &a, const Integer &b)
Calculate the greatest common divisor.
Definition: nbtheory.h:146
LCM
Integer LCM(const Integer &a, const Integer &b)
Calculate the least common multiple.
Definition: nbtheory.h:160
oids.h
ASN.1 object identifiers for algorithms and schemes.
pch.h
Precompiled header file.
pkcspad.h
Classes for PKCS padding schemes.
pssr.h
Classes for probabilistic signature schemes.
rsa.h
Classes for the RSA cryptosystem.
sha3.h
Classes for SHA3 message digests.
sha.h
Classes for SHA-1 and SHA-2 family of message digests.
RSAES
RSA encryption algorithm.
Definition: rsa.h:173
CRYPTOPP_ASSERT
#define CRYPTOPP_ASSERT(exp)
Debugging and diagnostic assertion.
Definition: trap.h:68