Crypto++  8.8
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 {
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 
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 
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 
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 
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 
160 void InvertibleRSAFunction::Initialize(RandomNumberGenerator &rng, unsigned int keybits, const Integer &e)
161 {
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 
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 
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 
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 
333 NAMESPACE_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:525
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:557
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.
static const Integer & One()
Integer representing 1.
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.
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 cabdidate prime.
Definition: nbtheory.h:114
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 * PrivateExponent()
Integer.
Definition: argnames.h:35
const char * PointerToPrimeSelector()
const PrimeSelector *
Definition: argnames.h:42
const char * ModPrime1PrivateExponent()
Integer.
Definition: argnames.h:45
const char * Prime1()
Integer.
Definition: argnames.h:43
const char * KeySize()
int, in bits
Definition: argnames.h:29
const char * Modulus()
Integer.
Definition: argnames.h:33
const char * MultiplicativeInverseOfPrime2ModPrime1()
Integer.
Definition: argnames.h:47
const char * PublicExponent()
Integer.
Definition: argnames.h:34
const char * ModulusSize()
int, in bits
Definition: argnames.h:30
const char * ModPrime2PrivateExponent()
Integer.
Definition: argnames.h:46
const char * Prime2()
Integer.
Definition: argnames.h:44
Classes and functions for number theoretic operations.
bool RelativelyPrime(const Integer &a, const Integer &b)
Determine relative primality.
Definition: nbtheory.h:150
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: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
#define CRYPTOPP_ASSERT(exp)
Debugging and diagnostic assertion.
Definition: trap.h:68