Crypto++ 8.2
Free C&
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
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 RSAPrimeSelector selector(m_e);
130 AlgorithmParameters primeParam = MakeParametersForTwoPrimesOfEqualSize(modulusSize)
131 (Name::PointerToPrimeSelector(), selector.GetSelectorPointer());
132 m_p.GenerateRandom(rng, primeParam);
133 m_q.GenerateRandom(rng, primeParam);
134
135 m_d = m_e.InverseMod(LCM(m_p-1, m_q-1));
137
138 m_dp = m_d % (m_p-1);
139 m_dq = m_d % (m_q-1);
140 m_n = m_p * m_q;
141 m_u = m_q.InverseMod(m_p);
142
143 if (FIPS_140_2_ComplianceEnabled())
144 {
145 RSASS<PKCS1v15, SHA1>::Signer signer(*this);
146 RSASS<PKCS1v15, SHA1>::Verifier verifier(signer);
147 SignaturePairwiseConsistencyTest_FIPS_140_Only(signer, verifier);
148
149 RSAES<OAEP<SHA1> >::Decryptor decryptor(*this);
150 RSAES<OAEP<SHA1> >::Encryptor encryptor(decryptor);
151 EncryptionPairwiseConsistencyTest_FIPS_140_Only(encryptor, decryptor);
152 }
153}
154
155void InvertibleRSAFunction::Initialize(RandomNumberGenerator &rng, unsigned int keybits, const Integer &e)
156{
157 GenerateRandom(rng, MakeParameters(Name::ModulusSize(), (int)keybits)(Name::PublicExponent(), e+e.IsEven()));
158}
159
161{
162 if (n.IsEven() || e.IsEven() | d.IsEven())
163 throw InvalidArgument("InvertibleRSAFunction: input is not a valid RSA private key");
164
165 m_n = n;
166 m_e = e;
167 m_d = d;
168
169 Integer r = --(d*e);
170 unsigned int s = 0;
171 while (r.IsEven())
172 {
173 r >>= 1;
174 s++;
175 }
176
177 ModularArithmetic modn(n);
178 for (Integer i = 2; ; ++i)
179 {
180 Integer a = modn.Exponentiate(i, r);
181 if (a == 1)
182 continue;
183 Integer b;
184 unsigned int j = 0;
185 while (a != n-1)
186 {
187 b = modn.Square(a);
188 if (b == 1)
189 {
190 m_p = GCD(a-1, n);
191 m_q = n/m_p;
192 m_dp = m_d % (m_p-1);
193 m_dq = m_d % (m_q-1);
194 m_u = m_q.InverseMod(m_p);
195 return;
196 }
197 if (++j == s)
198 throw InvalidArgument("InvertibleRSAFunction: input is not a valid RSA private key");
199 a = b;
200 }
201 }
202}
203
205{
206 BERSequenceDecoder privateKey(bt);
207 word32 version;
208 BERDecodeUnsigned<word32>(privateKey, version, INTEGER, 0, 0); // check version
209 m_n.BERDecode(privateKey);
210 m_e.BERDecode(privateKey);
211 m_d.BERDecode(privateKey);
212 m_p.BERDecode(privateKey);
213 m_q.BERDecode(privateKey);
214 m_dp.BERDecode(privateKey);
215 m_dq.BERDecode(privateKey);
216 m_u.BERDecode(privateKey);
217 privateKey.MessageEnd();
218}
219
221{
222 DERSequenceEncoder privateKey(bt);
223 DEREncodeUnsigned<word32>(privateKey, 0); // version
224 m_n.DEREncode(privateKey);
225 m_e.DEREncode(privateKey);
226 m_d.DEREncode(privateKey);
227 m_p.DEREncode(privateKey);
228 m_q.DEREncode(privateKey);
229 m_dp.DEREncode(privateKey);
230 m_dq.DEREncode(privateKey);
231 m_u.DEREncode(privateKey);
232 privateKey.MessageEnd();
233}
234
236{
238 ModularArithmetic modn(m_n);
239 Integer r, rInv;
240 do { // do this in a loop for people using small numbers for testing
241 r.Randomize(rng, Integer::One(), m_n - Integer::One());
242 rInv = modn.MultiplicativeInverse(r);
243 } while (rInv.IsZero());
244 Integer re = modn.Exponentiate(r, m_e);
245 re = modn.Multiply(re, x); // blind
246 // here we follow the notation of PKCS #1 and let u=q inverse mod p
247 // but in ModRoot, u=p inverse mod q, so we reverse the order of p and q
248 Integer y = ModularRoot(re, m_dq, m_dp, m_q, m_p, m_u);
249 y = modn.Multiply(y, rInv); // unblind
250 if (modn.Exponentiate(y, m_e) != x) // check
251 throw Exception(Exception::OTHER_ERROR, "InvertibleRSAFunction: computational error during private key operation");
252 return y;
253}
254
255bool InvertibleRSAFunction::Validate(RandomNumberGenerator &rng, unsigned int level) const
256{
257 bool pass = RSAFunction::Validate(rng, level);
258 CRYPTOPP_ASSERT(pass);
259 pass = pass && m_p > Integer::One() && m_p.IsOdd() && m_p < m_n;
260 CRYPTOPP_ASSERT(pass);
261 pass = pass && m_q > Integer::One() && m_q.IsOdd() && m_q < m_n;
262 CRYPTOPP_ASSERT(pass);
263 pass = pass && m_d > Integer::One() && m_d.IsOdd() && m_d < m_n;
264 CRYPTOPP_ASSERT(pass);
265 pass = pass && m_dp > Integer::One() && m_dp.IsOdd() && m_dp < m_p;
266 CRYPTOPP_ASSERT(pass);
267 pass = pass && m_dq > Integer::One() && m_dq.IsOdd() && m_dq < m_q;
268 CRYPTOPP_ASSERT(pass);
269 pass = pass && m_u.IsPositive() && m_u < m_p;
270 CRYPTOPP_ASSERT(pass);
271 if (level >= 1)
272 {
273 pass = pass && m_p * m_q == m_n;
274 CRYPTOPP_ASSERT(pass);
275 pass = pass && m_e*m_d % LCM(m_p-1, m_q-1) == 1;
276 CRYPTOPP_ASSERT(pass);
277 pass = pass && m_dp == m_d%(m_p-1) && m_dq == m_d%(m_q-1);
278 CRYPTOPP_ASSERT(pass);
279 pass = pass && m_u * m_q % m_p == 1;
280 CRYPTOPP_ASSERT(pass);
281 }
282 if (level >= 2)
283 {
284 pass = pass && VerifyPrime(rng, m_p, level-2) && VerifyPrime(rng, m_q, level-2);
285 CRYPTOPP_ASSERT(pass);
286 }
287 return pass;
288}
289
290bool InvertibleRSAFunction::GetVoidValue(const char *name, const std::type_info &valueType, void *pValue) const
291{
292 return GetValueHelper<RSAFunction>(this, name, valueType, pValue).Assignable()
293 CRYPTOPP_GET_FUNCTION_ENTRY(Prime1)
294 CRYPTOPP_GET_FUNCTION_ENTRY(Prime2)
295 CRYPTOPP_GET_FUNCTION_ENTRY(PrivateExponent)
296 CRYPTOPP_GET_FUNCTION_ENTRY(ModPrime1PrivateExponent)
297 CRYPTOPP_GET_FUNCTION_ENTRY(ModPrime2PrivateExponent)
298 CRYPTOPP_GET_FUNCTION_ENTRY(MultiplicativeInverseOfPrime2ModPrime1)
299 ;
300}
301
303{
304 AssignFromHelper<RSAFunction>(this, source)
305 CRYPTOPP_SET_FUNCTION_ENTRY(Prime1)
306 CRYPTOPP_SET_FUNCTION_ENTRY(Prime2)
307 CRYPTOPP_SET_FUNCTION_ENTRY(PrivateExponent)
308 CRYPTOPP_SET_FUNCTION_ENTRY(ModPrime1PrivateExponent)
309 CRYPTOPP_SET_FUNCTION_ENTRY(ModPrime2PrivateExponent)
310 CRYPTOPP_SET_FUNCTION_ENTRY(MultiplicativeInverseOfPrime2ModPrime1)
311 ;
312}
313
314// *****************************************************************************
315
317{
319 return t % 16 == 12 ? t : m_n - t;
320}
321
323{
325 return STDMIN(t, m_n-t);
326}
327
328NAMESPACE_END
329
330#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:502
Classes and functions for working with ANS.1 objects.
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:420
BER Sequence Decoder.
Definition: asn.h:310
Interface for buffered transformations.
Definition: cryptlib.h:1599
void DoQuickSanityCheck() const
Perform a quick sanity check.
Definition: cryptlib.h:2387
DER Sequence Encoder.
Definition: asn.h:320
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:3432
void GenerateRandom(RandomNumberGenerator &rng, const NameValuePairs &params=g_nullNameValuePairs)
Generate a random number.
Definition: integer.h:484
bool IsPositive() const
Determines if the Integer is positive.
Definition: integer.h:342
void Randomize(RandomNumberGenerator &rng, size_t bitCount)
Set this Integer to random integer.
Definition: integer.cpp:3503
void BERDecode(const byte *input, size_t inputLen)
Decode from BER format.
Definition: integer.cpp:3439
static const Integer & One()
Integer representing 1.
Definition: integer.cpp:4877
bool IsZero() const
Determines if the Integer is 0.
Definition: integer.h:330
bool IsOdd() const
Determines if the Integer is odd parity.
Definition: integer.h:351
Integer InverseMod(const Integer &n) const
Calculate multiplicative inverse.
Definition: integer.cpp:4430
bool IsEven() const
Determines if the Integer is even parity.
Definition: integer.h:348
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:322
bool Validate(RandomNumberGenerator &rng, unsigned int level) const
Check this object for errors.
Definition: rsa.cpp:255
void Initialize(RandomNumberGenerator &rng, unsigned int modulusBits, const Integer &e=17)
Create a RSA private key.
Definition: rsa.cpp:155
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:302
void DEREncodePrivateKey(BufferedTransformation &bt) const
encode privateKey part of privateKeyInfo, without the OCTET STRING header
Definition: rsa.cpp:220
bool GetVoidValue(const char *name, const std::type_info &valueType, void *pValue) const
Get a named value.
Definition: rsa.cpp:290
Integer CalculateInverse(RandomNumberGenerator &rng, const Integer &x) const
Calculates the inverse of an element.
Definition: rsa.cpp:235
void BERDecodePrivateKey(BufferedTransformation &bt, bool parametersPresent, size_t size)
decode privateKey part of privateKeyInfo, without the OCTET STRING header
Definition: rsa.cpp:204
Ring of congruence classes modulo n.
Definition: modarith.h:39
const Integer & MultiplicativeInverse(const Integer &a) const
Calculate the multiplicative inverse of an element in the ring.
Definition: modarith.h:194
const Integer & Square(const Integer &a) const
Square an element in the ring.
Definition: modarith.h:181
const Integer & Multiply(const Integer &a, const Integer &b) const
Multiplies elements in the ring.
Definition: modarith.h:174
Interface for retrieving values given their names.
Definition: cryptlib.h:294
T GetValueWithDefault(const char *name, T defaultValue) const
Get a named value.
Definition: cryptlib.h:363
bool GetIntValue(const char *name, int &value) const
Get a named value with type int.
Definition: cryptlib.h:386
Object Identifier.
Definition: asn.h:167
Template implementing constructors for public key algorithm classes.
Definition: pubkey.h:2135
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:316
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, without the BIT STRING header
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, without the BIT STRING header
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:1384
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:567
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:149
Integer GCD(const Integer &a, const Integer &b)
Calculate the greatest common divisor.
Definition: nbtheory.h:142
Integer LCM(const Integer &a, const Integer &b)
Calculate the least common multiple.
Definition: nbtheory.h:156
ASN.1 object identifiers for algorthms and schemes.
Precompiled header file.
Classes for PKCS padding schemes.
Classes for probablistic 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:69