← Back to branch summary

~ubuntu-branches/debian/sid/botan/sid

« back to all changes in this revision

Viewing changes to src/lib/pubkey/rsa/rsa.cpp

  • Committer: Package Import Robot
  • Author(s): Laszlo Boszormenyi (GCS)
  • Date: 2018-03-01 22:23:25 UTC
  • mfrom: (1.2.2)
  • Revision ID: package-import@ubuntu.com-20180301222325-7p7vc45gu3hta34d
Tags: 2.4.0-2
* Don't remove .doctrees from the manual if it doesn't exist.
* Don't specify parallel to debhelper.

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/lib/pubkey/rsa/rsa.cpp
 
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
 
 
28
size_t RSA_PublicKey::key_length() const
 
29
   {
 
30
   return m_n.bits();
 
31
   }
 
32
 
 
33
size_t RSA_PublicKey::estimated_strength() const
 
34
   {
 
35
   return if_work_factor(key_length());
 
36
   }
 
37
 
 
38
AlgorithmIdentifier RSA_PublicKey::algorithm_identifier() const
 
39
   {
 
40
   return AlgorithmIdentifier(get_oid(),
 
41
                              AlgorithmIdentifier::USE_NULL_PARAM);
 
42
   }
 
43
 
 
44
std::vector<uint8_t> RSA_PublicKey::public_key_bits() const
 
45
   {
 
46
   return DER_Encoder()
 
47
      .start_cons(SEQUENCE)
 
48
         .encode(m_n)
 
49
         .encode(m_e)
 
50
      .end_cons()
 
51
      .get_contents_unlocked();
 
52
   }
 
53
 
 
54
RSA_PublicKey::RSA_PublicKey(const AlgorithmIdentifier&,
 
55
                             const std::vector<uint8_t>& key_bits)
 
56
   {
 
57
   BER_Decoder(key_bits)
 
58
      .start_cons(SEQUENCE)
 
59
        .decode(m_n)
 
60
        .decode(m_e)
 
61
      .end_cons();
 
62
   }
 
63
 
 
64
/*
 
65
* Check RSA Public Parameters
 
66
*/
 
67
bool RSA_PublicKey::check_key(RandomNumberGenerator&, bool) const
 
68
   {
 
69
   if(m_n < 35 || m_n.is_even() || m_e < 2)
 
70
      return false;
 
71
   return true;
 
72
   }
 
73
 
 
74
secure_vector<uint8_t> RSA_PrivateKey::private_key_bits() const
 
75
   {
 
76
   return DER_Encoder()
 
77
      .start_cons(SEQUENCE)
 
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
 
 
91
RSA_PrivateKey::RSA_PrivateKey(const AlgorithmIdentifier&,
 
92
                               const secure_vector<uint8_t>& key_bits)
 
93
   {
 
94
   BER_Decoder(key_bits)
 
95
      .start_cons(SEQUENCE)
 
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
 
 
108
RSA_PrivateKey::RSA_PrivateKey(const BigInt& prime1,
 
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
*/
 
134
RSA_PrivateKey::RSA_PrivateKey(RandomNumberGenerator& rng,
 
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
*/
 
161
bool RSA_PrivateKey::check_key(RandomNumberGenerator& rng, bool strong) const
 
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>
 
407
RSA_PublicKey::create_encryption_op(RandomNumberGenerator& /*rng*/,
 
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>
 
437
RSA_PublicKey::create_kem_encryption_op(RandomNumberGenerator& /*rng*/,
 
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>
 
466
RSA_PrivateKey::create_decryption_op(RandomNumberGenerator& rng,
 
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>
 
492
RSA_PrivateKey::create_kem_decryption_op(RandomNumberGenerator& rng,
 
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>
 
503
RSA_PrivateKey::create_signature_op(RandomNumberGenerator& rng,
 
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
}