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"
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 
49 OID 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 
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 
97 {
98  AssignFromHelper(this, source)
99  CRYPTOPP_SET_FUNCTION_ENTRY(Modulus)
100  CRYPTOPP_SET_FUNCTION_ENTRY(PublicExponent)
101  ;
102 }
103 
104 // *****************************************************************************
105 
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  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 
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 
155 void 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 
160 void InvertibleRSAFunction::Initialize(const Integer &n, const Integer &e, const Integer &d)
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 
255 bool 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 
290 bool 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 
328 NAMESPACE_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 & Multiply(const Integer &a, const Integer &b) const
Multiplies elements in the ring.
Definition: modarith.h:174
const Integer & Square(const Integer &a) const
Square an element in the ring.
Definition: modarith.h:181
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:2142
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
RandomNumberGenerator & NullRNG()
Random Number Generator that does not produce random numbers.
Definition: cryptlib.cpp:400
Classes and functions for the FIPS 140-2 validated library.
bool FIPS_140_2_ComplianceEnabled()
Determines whether the library provides FIPS validated cryptography.
Definition: fips140.cpp:24
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 * 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:149
bool VerifyPrime(RandomNumberGenerator &rng, const Integer &p, unsigned int level=1)
Verifies a number is probably prime.
Definition: nbtheory.cpp:247
Integer ModularRoot(const Integer &a, const Integer &dp, const Integer &dq, const Integer &p, const Integer &q, const Integer &u)
Extract a modular root.
Definition: nbtheory.cpp:646
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