Botan  2.4.0
Crypto and TLS for C++11
rsa.cpp
Go to the documentation of this file.
1 /*
2 * RSA
3 * (C) 1999-2010,2015,2016 Jack Lloyd
4 *
5 * Botan is released under the Simplified BSD License (see license.txt)
6 */
7 
8 #include <botan/rsa.h>
9 #include <botan/internal/pk_ops_impl.h>
10 #include <botan/keypair.h>
11 #include <botan/blinding.h>
12 #include <botan/reducer.h>
13 #include <botan/workfactor.h>
14 #include <botan/der_enc.h>
15 #include <botan/ber_dec.h>
16 #include <botan/pow_mod.h>
17 
18 #if defined(BOTAN_HAS_OPENSSL)
19  #include <botan/internal/openssl.h>
20 #endif
21 
22 #if defined(BOTAN_TARGET_OS_HAS_THREADS)
23  #include <future>
24 #endif
25 
26 namespace Botan {
27 
29  {
30  return m_n.bits();
31  }
32 
34  {
35  return if_work_factor(key_length());
36  }
37 
39  {
42  }
43 
44 std::vector<uint8_t> RSA_PublicKey::public_key_bits() const
45  {
46  return DER_Encoder()
48  .encode(m_n)
49  .encode(m_e)
50  .end_cons()
52  }
53 
55  const std::vector<uint8_t>& key_bits)
56  {
57  BER_Decoder(key_bits)
59  .decode(m_n)
60  .decode(m_e)
61  .end_cons();
62  }
63 
64 /*
65 * Check RSA Public Parameters
66 */
68  {
69  if(m_n < 35 || m_n.is_even() || m_e < 2)
70  return false;
71  return true;
72  }
73 
75  {
76  return DER_Encoder()
78  .encode(static_cast<size_t>(0))
79  .encode(m_n)
80  .encode(m_e)
81  .encode(m_d)
82  .encode(m_p)
83  .encode(m_q)
84  .encode(m_d1)
85  .encode(m_d2)
86  .encode(m_c)
87  .end_cons()
88  .get_contents();
89  }
90 
92  const secure_vector<uint8_t>& key_bits)
93  {
94  BER_Decoder(key_bits)
96  .decode_and_check<size_t>(0, "Unknown PKCS #1 key format version")
97  .decode(m_n)
98  .decode(m_e)
99  .decode(m_d)
100  .decode(m_p)
101  .decode(m_q)
102  .decode(m_d1)
103  .decode(m_d2)
104  .decode(m_c)
105  .end_cons();
106  }
107 
109  const BigInt& prime2,
110  const BigInt& exp,
111  const BigInt& d_exp,
112  const BigInt& mod) :
113  m_d{ d_exp }, m_p{ prime1 }, m_q{ prime2 }, m_d1{}, m_d2{}, m_c{ inverse_mod( m_q, m_p ) }
114  {
115  m_n = mod.is_nonzero() ? mod : m_p * m_q;
116  m_e = exp;
117 
118  if(m_d == 0)
119  {
120  BigInt inv_for_d = lcm(m_p - 1, m_q - 1);
121  if(m_e.is_even())
122  inv_for_d >>= 1;
123 
124  m_d = inverse_mod(m_e, inv_for_d);
125  }
126 
127  m_d1 = m_d % (m_p - 1);
128  m_d2 = m_d % (m_q - 1);
129  }
130 
131 /*
132 * Create a RSA private key
133 */
135  size_t bits, size_t exp)
136  {
137  if(bits < 1024)
138  throw Invalid_Argument(algo_name() + ": Can't make a key that is only " +
139  std::to_string(bits) + " bits long");
140  if(exp < 3 || exp % 2 == 0)
141  throw Invalid_Argument(algo_name() + ": Invalid encryption exponent");
142 
143  m_e = exp;
144 
145  do
146  {
147  m_p = random_prime(rng, (bits + 1) / 2, m_e);
148  m_q = random_prime(rng, bits - m_p.bits(), m_e);
149  m_n = m_p * m_q;
150  } while(m_n.bits() != bits);
151 
152  m_d = inverse_mod(m_e, lcm(m_p - 1, m_q - 1));
153  m_d1 = m_d % (m_p - 1);
154  m_d2 = m_d % (m_q - 1);
155  m_c = inverse_mod(m_q, m_p);
156  }
157 
158 /*
159 * Check Private RSA Parameters
160 */
162  {
163  if(m_n < 35 || m_n.is_even() || m_e < 2 || m_d < 2 || m_p < 3 || m_q < 3 || m_p*m_q != m_n)
164  return false;
165 
166  if(m_d1 != m_d % (m_p - 1) || m_d2 != m_d % (m_q - 1) || m_c != inverse_mod(m_q, m_p))
167  return false;
168 
169  const size_t prob = (strong) ? 128 : 12;
170 
171  if(!is_prime(m_p, rng, prob) || !is_prime(m_q, rng, prob))
172  return false;
173 
174  if(strong)
175  {
176  if((m_e * m_d) % lcm(m_p - 1, m_q - 1) != 1)
177  return false;
178 
179  return KeyPair::signature_consistency_check(rng, *this, "EMSA4(SHA-256)");
180  }
181 
182  return true;
183  }
184 
185 namespace {
186 
187 /**
188 * RSA private (decrypt/sign) operation
189 */
190 class RSA_Private_Operation
191  {
192  protected:
193  size_t get_max_input_bits() const { return (m_n.bits() - 1); }
194 
195  explicit RSA_Private_Operation(const RSA_PrivateKey& rsa, RandomNumberGenerator& rng) :
196  m_n(rsa.get_n()),
197  m_q(rsa.get_q()),
198  m_c(rsa.get_c()),
199  m_powermod_e_n(rsa.get_e(), rsa.get_n()),
200  m_powermod_d1_p(rsa.get_d1(), rsa.get_p()),
201  m_powermod_d2_q(rsa.get_d2(), rsa.get_q()),
202  m_mod_p(rsa.get_p()),
203  m_blinder(m_n,
204  rng,
205  [this](const BigInt& k) { return m_powermod_e_n(k); },
206  [this](const BigInt& k) { return inverse_mod(k, m_n); })
207  {
208  }
209 
210  BigInt blinded_private_op(const BigInt& m) const
211  {
212  if(m >= m_n)
213  throw Invalid_Argument("RSA private op - input is too large");
214 
215  return m_blinder.unblind(private_op(m_blinder.blind(m)));
216  }
217 
218  BigInt private_op(const BigInt& m) const
219  {
220 #if defined(BOTAN_TARGET_OS_HAS_THREADS)
221  auto future_j1 = std::async(std::launch::async, m_powermod_d1_p, m);
222  BigInt j2 = m_powermod_d2_q(m);
223  BigInt j1 = future_j1.get();
224 #else
225  BigInt j1 = m_powermod_d1_p(m);
226  BigInt j2 = m_powermod_d2_q(m);
227 #endif
228 
229  j1 = m_mod_p.reduce(sub_mul(j1, j2, m_c));
230 
231  return mul_add(j1, m_q, j2);
232  }
233 
234  const BigInt& m_n;
235  const BigInt& m_q;
236  const BigInt& m_c;
237  Fixed_Exponent_Power_Mod m_powermod_e_n, m_powermod_d1_p, m_powermod_d2_q;
238  Modular_Reducer m_mod_p;
239  Blinder m_blinder;
240  };
241 
242 class RSA_Signature_Operation final : public PK_Ops::Signature_with_EMSA,
243  private RSA_Private_Operation
244  {
245  public:
246 
247  size_t max_input_bits() const override { return get_max_input_bits(); }
248 
249  RSA_Signature_Operation(const RSA_PrivateKey& rsa, const std::string& emsa, RandomNumberGenerator& rng) :
250  PK_Ops::Signature_with_EMSA(emsa),
251  RSA_Private_Operation(rsa, rng)
252  {
253  }
254 
255  secure_vector<uint8_t> raw_sign(const uint8_t msg[], size_t msg_len,
256  RandomNumberGenerator&) override
257  {
258  const BigInt m(msg, msg_len);
259  const BigInt x = blinded_private_op(m);
260  const BigInt c = m_powermod_e_n(x);
261  BOTAN_ASSERT(m == c, "RSA sign consistency check");
262  return BigInt::encode_1363(x, m_n.bytes());
263  }
264  };
265 
266 class RSA_Decryption_Operation final : public PK_Ops::Decryption_with_EME,
267  private RSA_Private_Operation
268  {
269  public:
270 
271  size_t max_raw_input_bits() const override { return get_max_input_bits(); }
272 
273  RSA_Decryption_Operation(const RSA_PrivateKey& rsa, const std::string& eme, RandomNumberGenerator& rng) :
274  PK_Ops::Decryption_with_EME(eme),
275  RSA_Private_Operation(rsa, rng)
276  {
277  }
278 
279  secure_vector<uint8_t> raw_decrypt(const uint8_t msg[], size_t msg_len) override
280  {
281  const BigInt m(msg, msg_len);
282  const BigInt x = blinded_private_op(m);
283  const BigInt c = m_powermod_e_n(x);
284  BOTAN_ASSERT(m == c, "RSA decrypt consistency check");
285  return BigInt::encode_1363(x, m_n.bytes());
286  }
287  };
288 
289 class RSA_KEM_Decryption_Operation final : public PK_Ops::KEM_Decryption_with_KDF,
290  private RSA_Private_Operation
291  {
292  public:
293 
294  RSA_KEM_Decryption_Operation(const RSA_PrivateKey& key,
295  const std::string& kdf,
296  RandomNumberGenerator& rng) :
297  PK_Ops::KEM_Decryption_with_KDF(kdf),
298  RSA_Private_Operation(key, rng)
299  {}
300 
301  secure_vector<uint8_t>
302  raw_kem_decrypt(const uint8_t encap_key[], size_t len) override
303  {
304  const BigInt m(encap_key, len);
305  const BigInt x = blinded_private_op(m);
306  const BigInt c = m_powermod_e_n(x);
307  BOTAN_ASSERT(m == c, "RSA KEM consistency check");
308  return BigInt::encode_1363(x, m_n.bytes());
309  }
310  };
311 
312 /**
313 * RSA public (encrypt/verify) operation
314 */
315 class RSA_Public_Operation
316  {
317  public:
318  explicit RSA_Public_Operation(const RSA_PublicKey& rsa) :
319  m_n(rsa.get_n()), m_powermod_e_n(rsa.get_e(), rsa.get_n())
320  {}
321 
322  size_t get_max_input_bits() const { return (m_n.bits() - 1); }
323 
324  protected:
325  BigInt public_op(const BigInt& m) const
326  {
327  if(m >= m_n)
328  throw Invalid_Argument("RSA public op - input is too large");
329  return m_powermod_e_n(m);
330  }
331 
332  const BigInt& get_n() const { return m_n; }
333 
334  const BigInt& m_n;
335  Fixed_Exponent_Power_Mod m_powermod_e_n;
336  };
337 
338 class RSA_Encryption_Operation final : public PK_Ops::Encryption_with_EME,
339  private RSA_Public_Operation
340  {
341  public:
342 
343  RSA_Encryption_Operation(const RSA_PublicKey& rsa, const std::string& eme) :
344  PK_Ops::Encryption_with_EME(eme),
345  RSA_Public_Operation(rsa)
346  {
347  }
348 
349  size_t max_raw_input_bits() const override { return get_max_input_bits(); }
350 
351  secure_vector<uint8_t> raw_encrypt(const uint8_t msg[], size_t msg_len,
352  RandomNumberGenerator&) override
353  {
354  BigInt m(msg, msg_len);
355  return BigInt::encode_1363(public_op(m), m_n.bytes());
356  }
357  };
358 
359 class RSA_Verify_Operation final : public PK_Ops::Verification_with_EMSA,
360  private RSA_Public_Operation
361  {
362  public:
363 
364  size_t max_input_bits() const override { return get_max_input_bits(); }
365 
366  RSA_Verify_Operation(const RSA_PublicKey& rsa, const std::string& emsa) :
367  PK_Ops::Verification_with_EMSA(emsa),
368  RSA_Public_Operation(rsa)
369  {
370  }
371 
372  bool with_recovery() const override { return true; }
373 
374  secure_vector<uint8_t> verify_mr(const uint8_t msg[], size_t msg_len) override
375  {
376  BigInt m(msg, msg_len);
377  return BigInt::encode_locked(public_op(m));
378  }
379  };
380 
381 class RSA_KEM_Encryption_Operation final : public PK_Ops::KEM_Encryption_with_KDF,
382  private RSA_Public_Operation
383  {
384  public:
385 
386  RSA_KEM_Encryption_Operation(const RSA_PublicKey& key,
387  const std::string& kdf) :
388  PK_Ops::KEM_Encryption_with_KDF(kdf),
389  RSA_Public_Operation(key) {}
390 
391  private:
392  void raw_kem_encrypt(secure_vector<uint8_t>& out_encapsulated_key,
393  secure_vector<uint8_t>& raw_shared_key,
394  Botan::RandomNumberGenerator& rng) override
395  {
396  const BigInt r = BigInt::random_integer(rng, 1, get_n());
397  const BigInt c = public_op(r);
398 
399  out_encapsulated_key = BigInt::encode_locked(c);
400  raw_shared_key = BigInt::encode_locked(r);
401  }
402  };
403 
404 }
405 
406 std::unique_ptr<PK_Ops::Encryption>
408  const std::string& params,
409  const std::string& provider) const
410  {
411 #if defined(BOTAN_HAS_OPENSSL)
412  if(provider == "openssl" || provider.empty())
413  {
414  try
415  {
416  return make_openssl_rsa_enc_op(*this, params);
417  }
418  catch(Exception& e)
419  {
420  /*
421  * If OpenSSL for some reason could not handle this (eg due to OAEP params),
422  * throw if openssl was specifically requested but otherwise just fall back
423  * to the normal version.
424  */
425  if(provider == "openssl")
426  throw Exception("OpenSSL RSA provider rejected key:", e.what());
427  }
428  }
429 #endif
430 
431  if(provider == "base" || provider.empty())
432  return std::unique_ptr<PK_Ops::Encryption>(new RSA_Encryption_Operation(*this, params));
433  throw Provider_Not_Found(algo_name(), provider);
434  }
435 
436 std::unique_ptr<PK_Ops::KEM_Encryption>
438  const std::string& params,
439  const std::string& provider) const
440  {
441  if(provider == "base" || provider.empty())
442  return std::unique_ptr<PK_Ops::KEM_Encryption>(new RSA_KEM_Encryption_Operation(*this, params));
443  throw Provider_Not_Found(algo_name(), provider);
444  }
445 
446 std::unique_ptr<PK_Ops::Verification>
447 RSA_PublicKey::create_verification_op(const std::string& params,
448  const std::string& provider) const
449  {
450 #if defined(BOTAN_HAS_OPENSSL)
451  if(provider == "openssl" || provider.empty())
452  {
453  std::unique_ptr<PK_Ops::Verification> res = make_openssl_rsa_ver_op(*this, params);
454  if(res)
455  return res;
456  }
457 #endif
458 
459  if(provider == "base" || provider.empty())
460  return std::unique_ptr<PK_Ops::Verification>(new RSA_Verify_Operation(*this, params));
461 
462  throw Provider_Not_Found(algo_name(), provider);
463  }
464 
465 std::unique_ptr<PK_Ops::Decryption>
467  const std::string& params,
468  const std::string& provider) const
469  {
470 #if defined(BOTAN_HAS_OPENSSL)
471  if(provider == "openssl" || provider.empty())
472  {
473  try
474  {
475  return make_openssl_rsa_dec_op(*this, params);
476  }
477  catch(Exception& e)
478  {
479  if(provider == "openssl")
480  throw Exception("OpenSSL RSA provider rejected key:", e.what());
481  }
482  }
483 #endif
484 
485  if(provider == "base" || provider.empty())
486  return std::unique_ptr<PK_Ops::Decryption>(new RSA_Decryption_Operation(*this, params, rng));
487 
488  throw Provider_Not_Found(algo_name(), provider);
489  }
490 
491 std::unique_ptr<PK_Ops::KEM_Decryption>
493  const std::string& params,
494  const std::string& provider) const
495  {
496  if(provider == "base" || provider.empty())
497  return std::unique_ptr<PK_Ops::KEM_Decryption>(new RSA_KEM_Decryption_Operation(*this, params, rng));
498 
499  throw Provider_Not_Found(algo_name(), provider);
500  }
501 
502 std::unique_ptr<PK_Ops::Signature>
504  const std::string& params,
505  const std::string& provider) const
506  {
507 #if defined(BOTAN_HAS_OPENSSL)
508  if(provider == "openssl" || provider.empty())
509  {
510  std::unique_ptr<PK_Ops::Signature> res = make_openssl_rsa_sig_op(*this, params);
511  if(res)
512  return res;
513  }
514 #endif
515 
516  if(provider == "base" || provider.empty())
517  return std::unique_ptr<PK_Ops::Signature>(new RSA_Signature_Operation(*this, params, rng));
518 
519  throw Provider_Not_Found(algo_name(), provider);
520  }
521 
522 }
BigInt mul_add(const BigInt &a, const BigInt &b, const BigInt &c)
Definition: mp_numth.cpp:35
std::unique_ptr< PK_Ops::Decryption > create_decryption_op(RandomNumberGenerator &rng, const std::string &params, const std::string &provider) const override
Definition: rsa.cpp:466
size_t if_work_factor(size_t bits)
Definition: workfactor.cpp:19
const BigInt & m_c
Definition: rsa.cpp:236
bool check_key(RandomNumberGenerator &rng, bool) const override
Definition: rsa.cpp:67
size_t estimated_strength() const override
Definition: rsa.cpp:33
std::vector< uint8_t > get_contents_unlocked()
Definition: der_enc.h:27
size_t key_length() const override
Definition: rsa.cpp:28
std::unique_ptr< PK_Ops::KEM_Encryption > create_kem_encryption_op(RandomNumberGenerator &rng, const std::string &params, const std::string &provider) const override
Definition: rsa.cpp:437
secure_vector< uint8_t > private_key_bits() const override
Definition: rsa.cpp:74
size_t bits() const
Definition: bigint.cpp:183
BER_Decoder & decode_and_check(const T &expected, const std::string &error_msg)
Definition: ber_dec.h:163
Fixed_Exponent_Power_Mod m_powermod_d1_p
Definition: rsa.cpp:237
std::unique_ptr< PK_Ops::KEM_Decryption > create_kem_decryption_op(RandomNumberGenerator &rng, const std::string &params, const std::string &provider) const override
Definition: rsa.cpp:492
secure_vector< uint8_t > get_contents()
Definition: der_enc.cpp:123
const BigInt & get_n() const
Definition: rsa.h:49
const BigInt & m_q
Definition: rsa.cpp:235
bool is_prime(const BigInt &n, RandomNumberGenerator &rng, size_t prob, bool is_random)
Definition: numthry.cpp:455
bool is_even() const
Definition: bigint.h:237
BER_Decoder & decode(bool &v)
Definition: ber_dec.cpp:355
std::string to_string(const BER_Object &obj)
Definition: asn1_obj.cpp:108
Fixed_Exponent_Power_Mod m_powermod_e_n
Definition: rsa.cpp:237
bool is_nonzero() const
Definition: bigint.h:249
Fixed_Exponent_Power_Mod m_powermod_d2_q
Definition: rsa.cpp:237
static BigInt random_integer(RandomNumberGenerator &rng, const BigInt &min, const BigInt &max)
Definition: big_rand.cpp:45
DER_Encoder & end_cons()
Definition: der_enc.cpp:146
BigInt m_e
Definition: rsa.h:76
static secure_vector< uint8_t > encode_locked(const BigInt &n, Base base=Binary)
Definition: big_code.cpp:68
#define BOTAN_ASSERT(expr, assertion_made)
Definition: assert.h:29
BigInt sub_mul(const BigInt &a, const BigInt &b, const BigInt &c)
Definition: mp_numth.cpp:57
DER_Encoder & encode(bool b)
Definition: der_enc.cpp:202
bool signature_consistency_check(RandomNumberGenerator &rng, const Private_Key &private_key, const Public_Key &public_key, const std::string &padding)
Definition: keypair.cpp:49
const BigInt & get_c() const
Definition: rsa.h:137
virtual OID get_oid() const
Definition: pk_keys.cpp:51
BigInt random_prime(RandomNumberGenerator &rng, size_t bits, const BigInt &coprime, size_t equiv, size_t modulo)
Definition: make_prm.cpp:17
BER_Decoder & end_cons()
Definition: ber_dec.cpp:265
const BigInt & get_d1() const
Definition: rsa.h:138
const BigInt & get_e() const
Definition: rsa.h:54
BigInt lcm(const BigInt &a, const BigInt &b)
Definition: numthry.cpp:74
std::vector< uint8_t > public_key_bits() const override
Definition: rsa.cpp:44
BigInt inverse_mod(const BigInt &n, const BigInt &mod)
Definition: numthry.cpp:277
const BigInt & get_q() const
Definition: rsa.h:129
std::string algo_name() const override
Definition: rsa.h:38
const char * what() const BOTAN_NOEXCEPT override
Definition: exceptn.h:25
secure_vector< uint8_t > decode(DataSource &source, std::string &label)
Definition: pem.cpp:68
BER_Decoder start_cons(ASN1_Tag type_tag, ASN1_Tag class_tag=UNIVERSAL)
Definition: ber_dec.cpp:251
Definition: alg_id.cpp:13
size_t bytes() const
Definition: bigint.cpp:175
AlgorithmIdentifier algorithm_identifier() const override
Definition: rsa.cpp:38
std::unique_ptr< PK_Ops::Verification > create_verification_op(const std::string &params, const std::string &provider) const override
Definition: rsa.cpp:447
RSA_PrivateKey(const AlgorithmIdentifier &alg_id, const secure_vector< uint8_t > &key_bits)
Definition: rsa.cpp:91
const BigInt & get_d2() const
Definition: rsa.h:139
Blinder m_blinder
Definition: rsa.cpp:239
const BigInt & get_p() const
Definition: rsa.h:123
DER_Encoder & start_cons(ASN1_Tag type_tag, ASN1_Tag class_tag=UNIVERSAL)
Definition: der_enc.cpp:136
static secure_vector< uint8_t > encode_1363(const BigInt &n, size_t bytes)
Definition: big_code.cpp:82
std::unique_ptr< PK_Ops::Encryption > create_encryption_op(RandomNumberGenerator &rng, const std::string &params, const std::string &provider) const override
Definition: rsa.cpp:407
std::vector< T, secure_allocator< T > > secure_vector
Definition: secmem.h:88
bool check_key(RandomNumberGenerator &rng, bool) const override
Definition: rsa.cpp:161
BigInt m_n
Definition: rsa.h:76
std::unique_ptr< PK_Ops::Signature > create_signature_op(RandomNumberGenerator &rng, const std::string &params, const std::string &provider) const override
Definition: rsa.cpp:503
Modular_Reducer m_mod_p
Definition: rsa.cpp:238