Security Scol plugin
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{
21 RSASS<PKCS1v15, SHA1>::Signer x2(NullRNG(), 1);
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
38 RSASS<PKCS1v15, SHA3_256>::Signer x11(NullRNG(), 1);
41}
42NAMESPACE_END
43#endif
44
45#ifndef CRYPTOPP_IMPORTS
46
47NAMESPACE_BEGIN(CryptoPP)
48
49OID RSAFunction::GetAlgorithmID() const
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
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
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
160void 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
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
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
virtual Element Exponentiate(const Element &a, const Integer &e) const
Raises a base to an exponent in the group.
Definition algebra.cpp:316
An object that implements NameValuePairs.
Definition algparam.h:426
void MessageEnd()
Signals the end of messages to the object.
Definition asn.cpp:553
BER Sequence Decoder.
Definition asn.h:525
Interface for buffered transformations.
Definition cryptlib.h:1652
void DoQuickSanityCheck() const
Perform a quick sanity check.
Definition cryptlib.h:2493
void MessageEnd()
Signals the end of messages to the object.
Definition asn.cpp:624
DER Sequence Encoder.
Definition asn.h:557
Base class for all exceptions thrown by the library.
Definition cryptlib.h:159
@ OTHER_ERROR
Some other error occurred not belonging to other categories.
Definition cryptlib.h:177
Multiple precision integer with arithmetic operations.
Definition integer.h:50
void DEREncode(BufferedTransformation &bt) const
Encode in DER format.
Definition integer.cpp:3449
void GenerateRandom(RandomNumberGenerator &rng, const NameValuePairs &params=g_nullNameValuePairs)
Generate a random number.
Definition integer.h:508
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.
Definition integer.cpp:3520
void BERDecode(const byte *input, size_t inputLen)
Decode from BER format.
Definition integer.cpp:3456
static const Integer &CRYPTOPP_API One()
Integer representing 1.
Definition integer.cpp:4920
bool IsZero() const
Determines if the Integer is 0.
Definition integer.h:335
bool IsOdd() const
Determines if the Integer is odd parity.
Definition integer.h:356
Integer InverseMod(const Integer &n) const
Calculate multiplicative inverse.
Definition integer.cpp:4473
bool IsEven() const
Determines if the Integer is even parity.
Definition integer.h:353
An invalid argument was detected.
Definition cryptlib.h:203
Integer CalculateInverse(RandomNumberGenerator &rng, const Integer &x) const
Calculates the inverse of an element.
Definition rsa.cpp:327
bool Validate(RandomNumberGenerator &rng, unsigned int level) const
Check this object for errors.
Definition rsa.cpp:260
void Initialize(RandomNumberGenerator &rng, unsigned int modulusBits, const Integer &e=17)
Create a RSA private key.
Definition rsa.cpp:160
void GenerateRandom(RandomNumberGenerator &rng, const NameValuePairs &alg)
Generate a random key or crypto parameters.
Definition rsa.cpp:114
void AssignFrom(const NameValuePairs &source)
Assign values to this object.
Definition rsa.cpp:307
void DEREncodePrivateKey(BufferedTransformation &bt) const
Encode privateKey part of privateKeyInfo.
Definition rsa.cpp:225
bool GetVoidValue(const char *name, const std::type_info &valueType, void *pValue) const
Get a named value.
Definition rsa.cpp:295
Integer CalculateInverse(RandomNumberGenerator &rng, const Integer &x) const
Calculates the inverse of an element.
Definition rsa.cpp:240
void BERDecodePrivateKey(BufferedTransformation &bt, bool parametersPresent, size_t size)
Decode privateKey part of privateKeyInfo.
Definition rsa.cpp:209
Ring of congruence classes modulo n.
Definition modarith.h:44
const Integer & MultiplicativeInverse(const Integer &a) const
Calculate the multiplicative inverse of an element in the ring.
Definition modarith.h:210
const Integer & Square(const Integer &a) const
Square an element in the ring.
Definition modarith.h:197
const Integer & Multiply(const Integer &a, const Integer &b) const
Multiplies elements in the ring.
Definition modarith.h:190
Interface for retrieving values given their names.
Definition cryptlib.h:322
T GetValueWithDefault(const char *name, T defaultValue) const
Get a named value.
Definition cryptlib.h:392
CRYPTOPP_DLL bool GetIntValue(const char *name, int &value) const
Get a named value with type int.
Definition cryptlib.h:415
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 cabdidate prime.
Definition nbtheory.h:114
Integer ApplyFunction(const Integer &x) const
Applies the trapdoor.
Definition rsa.cpp:321
RSA trapdoor function using the public key.
Definition rsa.h:24
bool Validate(RandomNumberGenerator &rng, unsigned int level) const
Check this object for errors.
Definition rsa.cpp:76
Integer ApplyFunction(const Integer &x) const
Applies the trapdoor.
Definition rsa.cpp:70
void BERDecodePublicKey(BufferedTransformation &bt, bool parametersPresent, size_t size)
Decode subjectPublicKey part of subjectPublicKeyInfo.
Definition rsa.cpp:54
bool GetVoidValue(const char *name, const std::type_info &valueType, void *pValue) const
Get a named value.
Definition rsa.cpp:88
void DEREncodePublicKey(BufferedTransformation &bt) const
Encode subjectPublicKey part of subjectPublicKeyInfo.
Definition rsa.cpp:62
void AssignFrom(const NameValuePairs &source)
Assign values to this object.
Definition rsa.cpp:96
Interface for random number generators.
Definition cryptlib.h:1435
unsigned int word32
32-bit unsigned datatype
Definition config_int.h:62
Classes and functions for the FIPS 140-2 validated library.
const T & STDMIN(const T &a, const T &b)
Replacement function for std::min.
Definition misc.h:655
Class file for performing modular arithmetic.
Classes and functions for number theoretic operations.
bool RelativelyPrime(const Integer &a, const Integer &b)
Determine relative primality.
Definition nbtheory.h:150
Integer GCD(const Integer &a, const Integer &b)
Calculate the greatest common divisor.
Definition nbtheory.h:143
Integer LCM(const Integer &a, const Integer &b)
Calculate the least common multiple.
Definition nbtheory.h:157
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