Coverage Report

Created: 2024-11-21 07:03

/src/libgcrypt/cipher/rsa.c
Line
Count
Source (jump to first uncovered line)
1
/* rsa.c - RSA implementation
2
 * Copyright (C) 1997, 1998, 1999 by Werner Koch (dd9jn)
3
 * Copyright (C) 2000, 2001, 2002, 2003, 2008 Free Software Foundation, Inc.
4
 *
5
 * This file is part of Libgcrypt.
6
 *
7
 * Libgcrypt is free software; you can redistribute it and/or modify
8
 * it under the terms of the GNU Lesser General Public License as
9
 * published by the Free Software Foundation; either version 2.1 of
10
 * the License, or (at your option) any later version.
11
 *
12
 * Libgcrypt is distributed in the hope that it will be useful,
13
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15
 * GNU Lesser General Public License for more details.
16
 *
17
 * You should have received a copy of the GNU Lesser General Public
18
 * License along with this program; if not, see <http://www.gnu.org/licenses/>.
19
 */
20
21
/* This code uses an algorithm protected by U.S. Patent #4,405,829
22
   which expired on September 20, 2000.  The patent holder placed that
23
   patent into the public domain on Sep 6th, 2000.
24
*/
25
26
#include <config.h>
27
#include <stdio.h>
28
#include <stdlib.h>
29
#include <string.h>
30
#include <errno.h>
31
32
#include "g10lib.h"
33
#include "mpi.h"
34
#include "cipher.h"
35
#include "pubkey-internal.h"
36
#include "const-time.h"
37
38
39
typedef struct
40
{
41
  gcry_mpi_t n;     /* modulus */
42
  gcry_mpi_t e;     /* exponent */
43
} RSA_public_key;
44
45
46
typedef struct
47
{
48
  gcry_mpi_t n;     /* public modulus */
49
  gcry_mpi_t e;     /* public exponent */
50
  gcry_mpi_t d;     /* exponent */
51
  gcry_mpi_t p;     /* prime  p. */
52
  gcry_mpi_t q;     /* prime  q. */
53
  gcry_mpi_t u;     /* inverse of p mod q. */
54
} RSA_secret_key;
55
56
57
static const char *rsa_names[] =
58
  {
59
    "rsa",
60
    "openpgp-rsa",
61
    "oid.1.2.840.113549.1.1.1",
62
    NULL,
63
  };
64
65
66
/* A sample 2048 bit RSA key used for the selftests.  */
67
static const char sample_secret_key[] =
68
" (private-key"
69
"  (rsa"
70
"  (n #009F56231A3D82E3E7D613D59D53E9AB921BEF9F08A782AED0B6E46ADBC853EC"
71
"      7C71C422435A3CD8FA0DB9EFD55CD3295BADC4E8E2E2B94E15AE82866AB8ADE8"
72
"      7E469FAE76DC3577DE87F1F419C4EB41123DFAF8D16922D5EDBAD6E9076D5A1C"
73
"      958106F0AE5E2E9193C6B49124C64C2A241C4075D4AF16299EB87A6585BAE917"
74
"      DEF27FCDD165764D069BC18D16527B29DAAB549F7BBED4A7C6A842D203ED6613"
75
"      6E2411744E432CD26D940132F25874483DCAEECDFD95744819CBCF1EA810681C"
76
"      42907EBCB1C7EAFBE75C87EC32C5413EA10476545D3FC7B2ADB1B66B7F200918"
77
"      664B0E5261C2895AA28B0DE321E921B3F877172CCCAB81F43EF98002916156F6CB#)"
78
"   (e #010001#)"
79
"   (d #07EF82500C403899934FE993AC5A36F14FF2DF38CF1EF315F205EE4C83EDAA19"
80
"       8890FC23DE9AA933CAFB37B6A8A8DBA675411958337287310D3FF2F1DDC0CB93"
81
"       7E70F57F75F833C021852B631D2B9A520E4431A03C5C3FCB5742DCD841D9FB12"
82
"       771AA1620DCEC3F1583426066ED9DC3F7028C5B59202C88FDF20396E2FA0EC4F"
83
"       5A22D9008F3043673931BC14A5046D6327398327900867E39CC61B2D1AFE2F48"
84
"       EC8E1E3861C68D257D7425F4E6F99ABD77D61F10CA100EFC14389071831B33DD"
85
"       69CC8EABEF860D1DC2AAA84ABEAE5DFC91BC124DAF0F4C8EF5BBEA436751DE84"
86
"       3A8063E827A024466F44C28614F93B0732A100D4A0D86D532FE1E22C7725E401#)"
87
"   (p #00C29D438F115825779631CD665A5739367F3E128ADC29766483A46CA80897E0"
88
"       79B32881860B8F9A6A04C2614A904F6F2578DAE13EA67CD60AE3D0AA00A1FF9B"
89
"       441485E44B2DC3D0B60260FBFE073B5AC72FAF67964DE15C8212C389D20DB9CF"
90
"       54AF6AEF5C4196EAA56495DD30CF709F499D5AB30CA35E086C2A1589D6283F1783#)"
91
"   (q #00D1984135231CB243FE959C0CBEF551EDD986AD7BEDF71EDF447BE3DA27AF46"
92
"       79C974A6FA69E4D52FE796650623DE70622862713932AA2FD9F2EC856EAEAA77"
93
"       88B4EA6084DC81C902F014829B18EA8B2666EC41586818E0589E18876065F97E"
94
"       8D22CE2DA53A05951EC132DCEF41E70A9C35F4ACC268FFAC2ADF54FA1DA110B919#)"
95
"   (u #67CF0FD7635205DD80FA814EE9E9C267C17376BF3209FB5D1BC42890D2822A04"
96
"       479DAF4D5B6ED69D0F8D1AF94164D07F8CD52ECEFE880641FA0F41DDAB1785E4"
97
"       A37A32F997A516480B4CD4F6482B9466A1765093ED95023CA32D5EDC1E34CEE9"
98
"       AF595BC51FE43C4BF810FA225AF697FB473B83815966188A4312C048B885E3F7#)))";
99
100
/* A sample 2048 bit RSA key used for the selftests (public only).  */
101
static const char sample_public_key[] =
102
" (public-key"
103
"  (rsa"
104
"   (n #009F56231A3D82E3E7D613D59D53E9AB921BEF9F08A782AED0B6E46ADBC853EC"
105
"       7C71C422435A3CD8FA0DB9EFD55CD3295BADC4E8E2E2B94E15AE82866AB8ADE8"
106
"       7E469FAE76DC3577DE87F1F419C4EB41123DFAF8D16922D5EDBAD6E9076D5A1C"
107
"       958106F0AE5E2E9193C6B49124C64C2A241C4075D4AF16299EB87A6585BAE917"
108
"       DEF27FCDD165764D069BC18D16527B29DAAB549F7BBED4A7C6A842D203ED6613"
109
"       6E2411744E432CD26D940132F25874483DCAEECDFD95744819CBCF1EA810681C"
110
"       42907EBCB1C7EAFBE75C87EC32C5413EA10476545D3FC7B2ADB1B66B7F200918"
111
"       664B0E5261C2895AA28B0DE321E921B3F877172CCCAB81F43EF98002916156F6CB#)"
112
"   (e #010001#)))";
113
114

115
static int test_keys (RSA_secret_key *sk, unsigned nbits);
116
static int  check_secret_key (RSA_secret_key *sk);
117
static void public (gcry_mpi_t output, gcry_mpi_t input, RSA_public_key *skey);
118
static void secret (gcry_mpi_t output, gcry_mpi_t input, RSA_secret_key *skey);
119
static unsigned int rsa_get_nbits (gcry_sexp_t parms);
120
121
122
/* Check that a freshly generated key actually works.  Returns 0 on success. */
123
static int
124
test_keys (RSA_secret_key *sk, unsigned int nbits)
125
0
{
126
0
  int result = -1; /* Default to failure.  */
127
0
  RSA_public_key pk;
128
0
  gcry_mpi_t plaintext = mpi_new (nbits);
129
0
  gcry_mpi_t ciphertext = mpi_new (nbits);
130
0
  gcry_mpi_t decr_plaintext = mpi_new (nbits);
131
0
  gcry_mpi_t signature = mpi_new (nbits);
132
133
  /* Put the relevant parameters into a public key structure.  */
134
0
  pk.n = sk->n;
135
0
  pk.e = sk->e;
136
137
  /* Create a random plaintext.  */
138
0
  _gcry_mpi_randomize (plaintext, nbits, GCRY_WEAK_RANDOM);
139
140
  /* Encrypt using the public key.  */
141
0
  public (ciphertext, plaintext, &pk);
142
143
  /* Check that the cipher text does not match the plaintext.  */
144
0
  if (!mpi_cmp (ciphertext, plaintext))
145
0
    goto leave; /* Ciphertext is identical to the plaintext.  */
146
147
  /* Decrypt using the secret key.  */
148
0
  secret (decr_plaintext, ciphertext, sk);
149
150
  /* Check that the decrypted plaintext matches the original plaintext.  */
151
0
  if (mpi_cmp (decr_plaintext, plaintext))
152
0
    goto leave; /* Plaintext does not match.  */
153
154
  /* Create another random plaintext as data for signature checking.  */
155
0
  _gcry_mpi_randomize (plaintext, nbits, GCRY_WEAK_RANDOM);
156
157
  /* Use the RSA secret function to create a signature of the plaintext.  */
158
0
  secret (signature, plaintext, sk);
159
160
  /* Use the RSA public function to verify this signature.  */
161
0
  public (decr_plaintext, signature, &pk);
162
0
  if (mpi_cmp (decr_plaintext, plaintext))
163
0
    goto leave; /* Signature does not match.  */
164
165
  /* Modify the signature and check that the signing fails.  */
166
0
  mpi_add_ui (signature, signature, 1);
167
0
  public (decr_plaintext, signature, &pk);
168
0
  if (!mpi_cmp (decr_plaintext, plaintext))
169
0
    goto leave; /* Signature matches but should not.  */
170
171
0
  result = 0; /* All tests succeeded.  */
172
173
0
 leave:
174
0
  _gcry_mpi_release (signature);
175
0
  _gcry_mpi_release (decr_plaintext);
176
0
  _gcry_mpi_release (ciphertext);
177
0
  _gcry_mpi_release (plaintext);
178
0
  return result;
179
0
}
180
181
static int
182
test_keys_fips (gcry_sexp_t skey)
183
0
{
184
0
  int result = -1; /* Default to failure.  */
185
0
  char plaintext[128];
186
0
  gcry_sexp_t sig = NULL;
187
0
  const char *data_tmpl = "(data (flags pkcs1) (hash %s %b))";
188
0
  gcry_md_hd_t hd = NULL;
189
0
  int ec;
190
191
  /* Create a random plaintext.  */
192
0
  _gcry_randomize (plaintext, sizeof plaintext, GCRY_WEAK_RANDOM);
193
194
  /* Open MD context and feed the random data in */
195
0
  ec = _gcry_md_open (&hd, GCRY_MD_SHA256, 0);
196
0
  if (ec)
197
0
    goto leave;
198
0
  _gcry_md_write (hd, plaintext, sizeof(plaintext));
199
200
  /* Use the RSA secret function to create a signature of the plaintext.  */
201
0
  ec = _gcry_pk_sign_md (&sig, data_tmpl, hd, skey, NULL);
202
0
  if (ec)
203
0
    goto leave;
204
205
  /* Use the RSA public function to verify this signature.  */
206
0
  ec = _gcry_pk_verify_md (sig, data_tmpl, hd, skey, NULL);
207
0
  if (ec)
208
0
    goto leave;
209
210
  /* Modify the data and check that the signing fails.  */
211
0
  _gcry_md_reset(hd);
212
0
  plaintext[sizeof plaintext / 2] ^= 1;
213
0
  _gcry_md_write (hd, plaintext, sizeof(plaintext));
214
0
  ec = _gcry_pk_verify_md (sig, data_tmpl, hd, skey, NULL);
215
0
  if (ec != GPG_ERR_BAD_SIGNATURE)
216
0
    goto leave; /* Signature verification worked on modified data  */
217
218
0
  result = 0; /* All tests succeeded.  */
219
0
 leave:
220
0
  sexp_release (sig);
221
0
  _gcry_md_close (hd);
222
0
  return result;
223
0
}
224
225
/* Callback used by the prime generation to test whether the exponent
226
   is suitable. Returns 0 if the test has been passed. */
227
static int
228
check_exponent (void *arg, gcry_mpi_t a)
229
0
{
230
0
  gcry_mpi_t e = arg;
231
0
  gcry_mpi_t tmp;
232
0
  int result;
233
234
0
  mpi_sub_ui (a, a, 1);
235
0
  tmp = _gcry_mpi_alloc_like (a);
236
0
  result = !mpi_gcd(tmp, e, a); /* GCD is not 1. */
237
0
  _gcry_mpi_release (tmp);
238
0
  mpi_add_ui (a, a, 1);
239
0
  return result;
240
0
}
241
242
/****************
243
 * Generate a key pair with a key of size NBITS.
244
 * USE_E = 0 let Libcgrypt decide what exponent to use.
245
 *       = 1 request the use of a "secure" exponent; this is required by some
246
 *           specification to be 65537.
247
 *       > 2 Use this public exponent.  If the given exponent
248
 *           is not odd one is internally added to it.
249
 * TRANSIENT_KEY:  If true, generate the primes using the standard RNG.
250
 * Returns: 2 structures filled with all needed values
251
 */
252
static gpg_err_code_t
253
generate_std (RSA_secret_key *sk, unsigned int nbits, unsigned long use_e,
254
              int transient_key)
255
0
{
256
0
  gcry_mpi_t p, q; /* the two primes */
257
0
  gcry_mpi_t d;    /* the private key */
258
0
  gcry_mpi_t u;
259
0
  gcry_mpi_t t1, t2;
260
0
  gcry_mpi_t n;    /* the public key */
261
0
  gcry_mpi_t e;    /* the exponent */
262
0
  gcry_mpi_t phi;  /* helper: (p-1)(q-1) */
263
0
  gcry_mpi_t g;
264
0
  gcry_mpi_t f;
265
0
  gcry_random_level_t random_level;
266
267
  /* The random quality depends on the transient_key flag.  */
268
0
  random_level = transient_key ? GCRY_STRONG_RANDOM : GCRY_VERY_STRONG_RANDOM;
269
270
  /* Make sure that nbits is even so that we generate p, q of equal size. */
271
0
  if ( (nbits&1) )
272
0
    nbits++;
273
274
0
  if (use_e == 1)   /* Alias for a secure value */
275
0
    use_e = 65537;  /* as demanded by Sphinx. */
276
277
  /* Public exponent:
278
     In general we use 41 as this is quite fast and more secure than the
279
     commonly used 17.  Benchmarking the RSA verify function
280
     with a 1024 bit key yields (2001-11-08):
281
     e=17    0.54 ms
282
     e=41    0.75 ms
283
     e=257   0.95 ms
284
     e=65537 1.80 ms
285
  */
286
0
  e = mpi_alloc( (32+BITS_PER_MPI_LIMB-1)/BITS_PER_MPI_LIMB );
287
0
  if (!use_e)
288
0
    mpi_set_ui (e, 41);     /* This is a reasonable secure and fast value */
289
0
  else
290
0
    {
291
0
      use_e |= 1; /* make sure this is odd */
292
0
      mpi_set_ui (e, use_e);
293
0
    }
294
295
0
  n = mpi_new (nbits);
296
297
0
  p = q = NULL;
298
0
  do
299
0
    {
300
      /* select two (very secret) primes */
301
0
      if (p)
302
0
        _gcry_mpi_release (p);
303
0
      if (q)
304
0
        _gcry_mpi_release (q);
305
0
      if (use_e)
306
0
        { /* Do an extra test to ensure that the given exponent is
307
             suitable. */
308
0
          p = _gcry_generate_secret_prime (nbits/2, random_level,
309
0
                                           check_exponent, e);
310
0
          q = _gcry_generate_secret_prime (nbits/2, random_level,
311
0
                                           check_exponent, e);
312
0
        }
313
0
      else
314
0
        { /* We check the exponent later. */
315
0
          p = _gcry_generate_secret_prime (nbits/2, random_level, NULL, NULL);
316
0
          q = _gcry_generate_secret_prime (nbits/2, random_level, NULL, NULL);
317
0
        }
318
0
      if (mpi_cmp (p, q) > 0 ) /* p shall be smaller than q (for calc of u)*/
319
0
        mpi_swap(p,q);
320
      /* calculate the modulus */
321
0
      mpi_mul( n, p, q );
322
0
    }
323
0
  while ( mpi_get_nbits(n) != nbits );
324
325
  /* calculate Euler totient: phi = (p-1)(q-1) */
326
0
  t1 = mpi_alloc_secure( mpi_get_nlimbs(p) );
327
0
  t2 = mpi_alloc_secure( mpi_get_nlimbs(p) );
328
0
  phi   = mpi_snew ( nbits );
329
0
  g = mpi_snew ( nbits );
330
0
  f = mpi_snew ( nbits );
331
0
  mpi_sub_ui( t1, p, 1 );
332
0
  mpi_sub_ui( t2, q, 1 );
333
0
  mpi_mul( phi, t1, t2 );
334
0
  mpi_gcd (g, t1, t2);
335
0
  mpi_fdiv_q(f, phi, g);
336
337
0
  while (!mpi_gcd(t1, e, phi)) /* (while gcd is not 1) */
338
0
    {
339
0
      if (use_e)
340
0
        BUG (); /* The prime generator already made sure that we
341
                   never can get to here. */
342
0
      mpi_add_ui (e, e, 2);
343
0
    }
344
345
  /* calculate the secret key d = e^-1 mod phi */
346
0
  d = mpi_snew ( nbits );
347
0
  mpi_invm (d, e, f );
348
  /* calculate the inverse of p and q (used for chinese remainder theorem)*/
349
0
  u = mpi_snew ( nbits );
350
0
  mpi_invm(u, p, q );
351
352
0
  if( DBG_CIPHER )
353
0
    {
354
0
      log_mpidump("  p= ", p );
355
0
      log_mpidump("  q= ", q );
356
0
      log_mpidump("phi= ", phi );
357
0
      log_mpidump("  g= ", g );
358
0
      log_mpidump("  f= ", f );
359
0
      log_mpidump("  n= ", n );
360
0
      log_mpidump("  e= ", e );
361
0
      log_mpidump("  d= ", d );
362
0
      log_mpidump("  u= ", u );
363
0
    }
364
365
0
  _gcry_mpi_release (t1);
366
0
  _gcry_mpi_release (t2);
367
0
  _gcry_mpi_release (phi);
368
0
  _gcry_mpi_release (f);
369
0
  _gcry_mpi_release (g);
370
371
0
  sk->n = n;
372
0
  sk->e = e;
373
0
  sk->p = p;
374
0
  sk->q = q;
375
0
  sk->d = d;
376
0
  sk->u = u;
377
378
  /* Now we can test our keys. */
379
0
  if (test_keys (sk, nbits - 64))
380
0
    {
381
0
      _gcry_mpi_release (sk->n); sk->n = NULL;
382
0
      _gcry_mpi_release (sk->e); sk->e = NULL;
383
0
      _gcry_mpi_release (sk->p); sk->p = NULL;
384
0
      _gcry_mpi_release (sk->q); sk->q = NULL;
385
0
      _gcry_mpi_release (sk->d); sk->d = NULL;
386
0
      _gcry_mpi_release (sk->u); sk->u = NULL;
387
0
      fips_signal_error ("self-test after key generation failed");
388
0
      return GPG_ERR_SELFTEST_FAILED;
389
0
    }
390
391
0
  return 0;
392
0
}
393
394
395
/* Check the RSA key length is acceptable for key generation or usage */
396
static gpg_err_code_t
397
rsa_check_keysize (unsigned int nbits)
398
0
{
399
0
  if (fips_mode () && nbits < 2048)
400
0
    return GPG_ERR_INV_VALUE;
401
402
0
  return GPG_ERR_NO_ERROR;
403
0
}
404
405
406
/* Check the RSA key length is acceptable for signature verification
407
 *
408
 * FIPS allows signature verification with RSA keys of size
409
 * 1024, 1280, 1536 and 1792 in legacy mode, but this is up to the
410
 * calling application to decide if the signature is legacy and
411
 * should be accepted.
412
 */
413
static gpg_err_code_t
414
rsa_check_verify_keysize (unsigned int nbits)
415
0
{
416
0
  if (fips_mode ())
417
0
    {
418
0
      if ((nbits >= 1024 && (nbits % 256) == 0) || nbits >= 2048)
419
0
        return GPG_ERR_NO_ERROR;
420
421
0
      return GPG_ERR_INV_VALUE;
422
0
    }
423
424
0
  return GPG_ERR_NO_ERROR;
425
0
}
426
427
428
/****************
429
 * Generate a key pair with a key of size NBITS.
430
 * USE_E = 0 let Libcgrypt decide what exponent to use.
431
 *       = 1 request the use of a "secure" exponent; this is required by some
432
 *           specification to be 65537.
433
 *       > 2 Use this public exponent.  If the given exponent
434
 *           is not odd one is internally added to it.
435
 * TESTPARMS: If set, do not generate but test whether the p,q is probably prime
436
 *            Returns key with zeroes to not break code calling this function.
437
 * TRANSIENT_KEY:  If true, generate the primes using the standard RNG.
438
 * Returns: 2 structures filled with all needed values
439
 */
440
static gpg_err_code_t
441
generate_fips (RSA_secret_key *sk, unsigned int nbits, unsigned long use_e,
442
               gcry_sexp_t testparms, int transient_key)
443
0
{
444
0
  gcry_mpi_t p, q; /* the two primes */
445
0
  gcry_mpi_t d;    /* the private key */
446
0
  gcry_mpi_t u;
447
0
  gcry_mpi_t p1, q1;
448
0
  gcry_mpi_t n;    /* the public key */
449
0
  gcry_mpi_t e;    /* the exponent */
450
0
  gcry_mpi_t g;
451
0
  gcry_mpi_t minp;
452
0
  gcry_mpi_t diff, mindiff;
453
0
  gcry_random_level_t random_level;
454
0
  unsigned int pbits = nbits/2;
455
0
  unsigned int i;
456
0
  int pqswitch;
457
0
  gpg_err_code_t ec;
458
459
0
  if (nbits <= 1024 || (nbits & 0x1FF))
460
0
    return GPG_ERR_INV_VALUE;
461
0
  ec = rsa_check_keysize (nbits);
462
0
  if (ec)
463
0
    return ec;
464
465
  /* Set default error code.  */
466
0
  ec = GPG_ERR_NO_PRIME;
467
468
  /* The random quality depends on the transient_key flag.  */
469
0
  random_level = transient_key ? GCRY_STRONG_RANDOM : GCRY_VERY_STRONG_RANDOM;
470
471
0
  if (testparms)
472
0
    {
473
      /* Parameters to derive the key are given.  */
474
      /* Note that we explicitly need to setup the values of tbl
475
         because some compilers (e.g. OpenWatcom, IRIX) don't allow to
476
         initialize a structure with automatic variables.  */
477
0
      struct { const char *name; gcry_mpi_t *value; } tbl[] = {
478
0
        { "e" },
479
0
        { "p" },
480
0
        { "q" },
481
0
        { NULL }
482
0
      };
483
0
      int idx;
484
0
      gcry_sexp_t oneparm;
485
486
0
      tbl[0].value = &e;
487
0
      tbl[1].value = &p;
488
0
      tbl[2].value = &q;
489
490
0
      for (idx=0; tbl[idx].name; idx++)
491
0
        {
492
0
          oneparm = sexp_find_token (testparms, tbl[idx].name, 0);
493
0
          if (oneparm)
494
0
            {
495
0
              *tbl[idx].value = sexp_nth_mpi (oneparm, 1, GCRYMPI_FMT_USG);
496
0
              sexp_release (oneparm);
497
0
            }
498
0
        }
499
0
      for (idx=0; tbl[idx].name; idx++)
500
0
        if (!*tbl[idx].value)
501
0
          break;
502
0
      if (tbl[idx].name)
503
0
        {
504
          /* At least one parameter is missing.  */
505
0
          for (idx=0; tbl[idx].name; idx++)
506
0
            _gcry_mpi_release (*tbl[idx].value);
507
0
          return GPG_ERR_MISSING_VALUE;
508
0
        }
509
0
    }
510
0
  else
511
0
    {
512
0
      if (use_e < 65537)
513
0
        use_e = 65537;  /* This is the smallest value allowed by FIPS */
514
515
0
      e = mpi_alloc ((32+BITS_PER_MPI_LIMB-1)/BITS_PER_MPI_LIMB);
516
517
0
      use_e |= 1; /* make sure this is odd */
518
0
      mpi_set_ui (e, use_e);
519
520
0
      p = mpi_snew (pbits);
521
0
      q = mpi_snew (pbits);
522
0
    }
523
524
0
  n = mpi_new (nbits);
525
0
  d = mpi_snew (nbits);
526
0
  u = mpi_snew (nbits);
527
528
  /* prepare approximate minimum p and q */
529
0
  minp = mpi_new (pbits);
530
0
  mpi_set_ui (minp, 0xB504F334);
531
0
  mpi_lshift (minp, minp, pbits - 32);
532
533
  /* prepare minimum p and q difference */
534
0
  diff = mpi_new (pbits);
535
0
  mindiff = mpi_new (pbits - 99);
536
0
  mpi_set_ui (mindiff, 1);
537
0
  mpi_lshift (mindiff, mindiff, pbits - 100);
538
539
0
  p1 = mpi_snew (pbits);
540
0
  q1 = mpi_snew (pbits);
541
0
  g  = mpi_snew (pbits);
542
543
0
 retry:
544
  /* generate p and q */
545
0
  for (i = 0; i < 10 * pbits; i++)
546
0
    {
547
0
    ploop:
548
0
      if (!testparms)
549
0
        {
550
0
          _gcry_mpi_randomize (p, pbits, random_level);
551
0
          mpi_set_bit (p, 0);
552
0
        }
553
0
      if (mpi_cmp (p, minp) < 0)
554
0
        {
555
0
          if (testparms)
556
0
            goto err;
557
0
          goto ploop;
558
0
        }
559
560
0
      mpi_sub_ui (p1, p, 1);
561
0
      if (mpi_gcd (g, p1, e))
562
0
        {
563
0
          if (_gcry_fips186_4_prime_check (p, pbits) != GPG_ERR_NO_ERROR)
564
0
            {
565
              /* not a prime */
566
0
              if (testparms)
567
0
                goto err;
568
0
            }
569
0
          else
570
0
            break;
571
0
        }
572
0
      else if (testparms)
573
0
        goto err;
574
0
    }
575
0
  if (i >= 10 * pbits)
576
0
    goto err;
577
578
0
  for (i = 0; i < 20 * pbits; i++)
579
0
    {
580
0
    qloop:
581
0
      if (!testparms)
582
0
        {
583
0
          _gcry_mpi_randomize (q, pbits, random_level);
584
0
          mpi_set_bit (q, 0);
585
0
        }
586
0
      if (mpi_cmp (q, minp) < 0)
587
0
        {
588
0
          if (testparms)
589
0
            goto err;
590
0
          goto qloop;
591
0
        }
592
0
      if (mpi_cmp (p, q) > 0)
593
0
        {
594
0
          pqswitch = 1;
595
0
          mpi_sub (diff, p, q);
596
0
        }
597
0
      else
598
0
        {
599
0
          pqswitch = 0;
600
0
          mpi_sub (diff, q, p);
601
0
        }
602
0
      if (mpi_cmp (diff, mindiff) < 0)
603
0
        {
604
0
          if (testparms)
605
0
            goto err;
606
0
          goto qloop;
607
0
        }
608
609
0
      mpi_sub_ui (q1, q, 1);
610
0
      if (mpi_gcd (g, q1, e))
611
0
        {
612
0
          if (_gcry_fips186_4_prime_check (q, pbits) != GPG_ERR_NO_ERROR)
613
0
            {
614
              /* not a prime */
615
0
              if (testparms)
616
0
                goto err;
617
0
            }
618
0
          else
619
0
            break;
620
0
        }
621
0
      else if (testparms)
622
0
        goto err;
623
0
    }
624
0
  if (i >= 20 * pbits)
625
0
    goto err;
626
627
0
  if (testparms)
628
0
    {
629
0
      mpi_clear (p);
630
0
      mpi_clear (q);
631
0
    }
632
0
  else
633
0
    {
634
0
      gcry_mpi_t f;
635
636
0
      if (pqswitch)
637
0
        {
638
0
          gcry_mpi_t tmp;
639
640
0
          tmp = p;
641
0
          p = q;
642
0
          q = tmp;
643
0
        }
644
645
0
      f = mpi_snew (nbits);
646
647
      /* calculate the modulus */
648
0
      mpi_mul (n, p, q);
649
650
      /* calculate the secret key d = e^1 mod phi */
651
0
      mpi_gcd (g, p1, q1);
652
0
      mpi_fdiv_q (f, p1, g);
653
0
      mpi_mul (f, f, q1);
654
655
0
      mpi_invm (d, e, f);
656
657
0
      _gcry_mpi_release (f);
658
659
0
      if (mpi_get_nbits (d) < pbits)
660
0
        goto retry;
661
662
      /* calculate the inverse of p and q (used for chinese remainder theorem)*/
663
0
      mpi_invm (u, p, q );
664
0
    }
665
666
0
  ec = 0; /* Success.  */
667
668
0
  if (DBG_CIPHER)
669
0
    {
670
0
      log_mpidump("  p= ", p );
671
0
      log_mpidump("  q= ", q );
672
0
      log_mpidump("  n= ", n );
673
0
      log_mpidump("  e= ", e );
674
0
      log_mpidump("  d= ", d );
675
0
      log_mpidump("  u= ", u );
676
0
    }
677
678
0
 err:
679
680
0
  _gcry_mpi_release (p1);
681
0
  _gcry_mpi_release (q1);
682
0
  _gcry_mpi_release (g);
683
0
  _gcry_mpi_release (minp);
684
0
  _gcry_mpi_release (mindiff);
685
0
  _gcry_mpi_release (diff);
686
687
0
  sk->n = n;
688
0
  sk->e = e;
689
0
  sk->p = p;
690
0
  sk->q = q;
691
0
  sk->d = d;
692
0
  sk->u = u;
693
694
0
  if (ec)
695
0
    {
696
0
      _gcry_mpi_release (sk->n); sk->n = NULL;
697
0
      _gcry_mpi_release (sk->e); sk->e = NULL;
698
0
      _gcry_mpi_release (sk->p); sk->p = NULL;
699
0
      _gcry_mpi_release (sk->q); sk->q = NULL;
700
0
      _gcry_mpi_release (sk->d); sk->d = NULL;
701
0
      _gcry_mpi_release (sk->u); sk->u = NULL;
702
0
    }
703
704
0
  return ec;
705
0
}
706
707
708
/* Helper for generate_x931.  */
709
static gcry_mpi_t
710
gen_x931_parm_xp (unsigned int nbits)
711
0
{
712
0
  gcry_mpi_t xp;
713
714
0
  xp = mpi_snew (nbits);
715
0
  _gcry_mpi_randomize (xp, nbits, GCRY_VERY_STRONG_RANDOM);
716
717
  /* The requirement for Xp is:
718
719
       sqrt{2}*2^{nbits-1} <= xp <= 2^{nbits} - 1
720
721
     We set the two high order bits to 1 to satisfy the lower bound.
722
     By using mpi_set_highbit we make sure that the upper bound is
723
     satisfied as well.  */
724
0
  mpi_set_highbit (xp, nbits-1);
725
0
  mpi_set_bit (xp, nbits-2);
726
0
  gcry_assert ( mpi_get_nbits (xp) == nbits );
727
728
0
  return xp;
729
0
}
730
731
732
/* Helper for generate_x931.  */
733
static gcry_mpi_t
734
gen_x931_parm_xi (void)
735
0
{
736
0
  gcry_mpi_t xi;
737
738
0
  xi = mpi_snew (101);
739
0
  _gcry_mpi_randomize (xi, 101, GCRY_VERY_STRONG_RANDOM);
740
0
  mpi_set_highbit (xi, 100);
741
0
  gcry_assert ( mpi_get_nbits (xi) == 101 );
742
743
0
  return xi;
744
0
}
745
746
747
748
/* Variant of the standard key generation code using the algorithm
749
   from X9.31.  Using this algorithm has the advantage that the
750
   generation can be made deterministic which is required for CAVS
751
   testing.  */
752
static gpg_err_code_t
753
generate_x931 (RSA_secret_key *sk, unsigned int nbits, unsigned long e_value,
754
               gcry_sexp_t deriveparms, int *swapped)
755
0
{
756
0
  gcry_mpi_t p, q; /* The two primes.  */
757
0
  gcry_mpi_t e;    /* The public exponent.  */
758
0
  gcry_mpi_t n;    /* The public key.  */
759
0
  gcry_mpi_t d;    /* The private key */
760
0
  gcry_mpi_t u;    /* The inverse of p and q.  */
761
0
  gcry_mpi_t pm1;  /* p - 1  */
762
0
  gcry_mpi_t qm1;  /* q - 1  */
763
0
  gcry_mpi_t phi;  /* Euler totient.  */
764
0
  gcry_mpi_t f, g; /* Helper.  */
765
766
0
  *swapped = 0;
767
768
0
  if (e_value == 0)        /* 65537 is the libgcrypt's selection. */
769
0
    e_value = 65537;
770
0
  else if (e_value == 1)   /* Alias for a secure value. */
771
0
    e_value = 65537;
772
773
  /* Point 1 of section 4.1:  k = 1024 + 256s with S >= 0  */
774
0
  if (nbits < 1024 || (nbits % 256))
775
0
    return GPG_ERR_INV_VALUE;
776
777
  /* Point 2:  2 <= bitlength(e) < 2^{k-2}
778
     Note that we do not need to check the upper bound because we use
779
     an unsigned long for E and thus there is no way for E to reach
780
     that limit.  */
781
0
  if (e_value < 3)
782
0
    return GPG_ERR_INV_VALUE;
783
784
  /* Our implementation requires E to be odd.  */
785
0
  if (!(e_value & 1))
786
0
    return GPG_ERR_INV_VALUE;
787
788
  /* Point 3:  e > 0 or e 0 if it is to be randomly generated.
789
     We support only a fixed E and thus there is no need for an extra test.  */
790
791
792
  /* Compute or extract the derive parameters.  */
793
0
  {
794
0
    gcry_mpi_t xp1 = NULL;
795
0
    gcry_mpi_t xp2 = NULL;
796
0
    gcry_mpi_t xp  = NULL;
797
0
    gcry_mpi_t xq1 = NULL;
798
0
    gcry_mpi_t xq2 = NULL;
799
0
    gcry_mpi_t xq  = NULL;
800
0
    gcry_mpi_t tmpval;
801
802
0
    if (!deriveparms)
803
0
      {
804
        /* Not given: Generate them.  */
805
0
        xp = gen_x931_parm_xp (nbits/2);
806
        /* Make sure that |xp - xq| > 2^{nbits - 100} holds.  */
807
0
        tmpval = mpi_snew (nbits/2);
808
0
        do
809
0
          {
810
0
            _gcry_mpi_release (xq);
811
0
            xq = gen_x931_parm_xp (nbits/2);
812
0
            mpi_sub (tmpval, xp, xq);
813
0
          }
814
0
        while (mpi_get_nbits (tmpval) <= (nbits/2 - 100));
815
0
        _gcry_mpi_release (tmpval);
816
817
0
        xp1 = gen_x931_parm_xi ();
818
0
        xp2 = gen_x931_parm_xi ();
819
0
        xq1 = gen_x931_parm_xi ();
820
0
        xq2 = gen_x931_parm_xi ();
821
822
0
      }
823
0
    else
824
0
      {
825
        /* Parameters to derive the key are given.  */
826
        /* Note that we explicitly need to setup the values of tbl
827
           because some compilers (e.g. OpenWatcom, IRIX) don't allow
828
           to initialize a structure with automatic variables.  */
829
0
        struct { const char *name; gcry_mpi_t *value; } tbl[] = {
830
0
          { "Xp1" },
831
0
          { "Xp2" },
832
0
          { "Xp"  },
833
0
          { "Xq1" },
834
0
          { "Xq2" },
835
0
          { "Xq"  },
836
0
          { NULL }
837
0
        };
838
0
        int idx;
839
0
        gcry_sexp_t oneparm;
840
841
0
        tbl[0].value = &xp1;
842
0
        tbl[1].value = &xp2;
843
0
        tbl[2].value = &xp;
844
0
        tbl[3].value = &xq1;
845
0
        tbl[4].value = &xq2;
846
0
        tbl[5].value = &xq;
847
848
0
        for (idx=0; tbl[idx].name; idx++)
849
0
          {
850
0
            oneparm = sexp_find_token (deriveparms, tbl[idx].name, 0);
851
0
            if (oneparm)
852
0
              {
853
0
                *tbl[idx].value = sexp_nth_mpi (oneparm, 1, GCRYMPI_FMT_USG);
854
0
                sexp_release (oneparm);
855
0
              }
856
0
          }
857
0
        for (idx=0; tbl[idx].name; idx++)
858
0
          if (!*tbl[idx].value)
859
0
            break;
860
0
        if (tbl[idx].name)
861
0
          {
862
            /* At least one parameter is missing.  */
863
0
            for (idx=0; tbl[idx].name; idx++)
864
0
              _gcry_mpi_release (*tbl[idx].value);
865
0
            return GPG_ERR_MISSING_VALUE;
866
0
          }
867
0
      }
868
869
0
    e = mpi_alloc_set_ui (e_value);
870
871
    /* Find two prime numbers.  */
872
0
    p = _gcry_derive_x931_prime (xp, xp1, xp2, e, NULL, NULL);
873
0
    q = _gcry_derive_x931_prime (xq, xq1, xq2, e, NULL, NULL);
874
0
    _gcry_mpi_release (xp);  xp  = NULL;
875
0
    _gcry_mpi_release (xp1); xp1 = NULL;
876
0
    _gcry_mpi_release (xp2); xp2 = NULL;
877
0
    _gcry_mpi_release (xq);  xq  = NULL;
878
0
    _gcry_mpi_release (xq1); xq1 = NULL;
879
0
    _gcry_mpi_release (xq2); xq2 = NULL;
880
0
    if (!p || !q)
881
0
      {
882
0
        _gcry_mpi_release (p);
883
0
        _gcry_mpi_release (q);
884
0
        _gcry_mpi_release (e);
885
0
        return GPG_ERR_NO_PRIME;
886
0
      }
887
0
  }
888
889
890
  /* Compute the public modulus.  We make sure that p is smaller than
891
     q to allow the use of the CRT.  */
892
0
  if (mpi_cmp (p, q) > 0 )
893
0
    {
894
0
      mpi_swap (p, q);
895
0
      *swapped = 1;
896
0
    }
897
0
  n = mpi_new (nbits);
898
0
  mpi_mul (n, p, q);
899
900
  /* Compute the Euler totient:  phi = (p-1)(q-1)  */
901
0
  pm1 = mpi_snew (nbits/2);
902
0
  qm1 = mpi_snew (nbits/2);
903
0
  phi = mpi_snew (nbits);
904
0
  mpi_sub_ui (pm1, p, 1);
905
0
  mpi_sub_ui (qm1, q, 1);
906
0
  mpi_mul (phi, pm1, qm1);
907
908
0
  g = mpi_snew (nbits);
909
0
  gcry_assert (mpi_gcd (g, e, phi));
910
911
  /* Compute: f = lcm(p-1,q-1) = phi / gcd(p-1,q-1) */
912
0
  mpi_gcd (g, pm1, qm1);
913
0
  f = pm1; pm1 = NULL;
914
0
  _gcry_mpi_release (qm1); qm1 = NULL;
915
0
  mpi_fdiv_q (f, phi, g);
916
0
  _gcry_mpi_release (phi); phi = NULL;
917
0
  d = g; g = NULL;
918
  /* Compute the secret key:  d = e^{-1} mod lcm(p-1,q-1) */
919
0
  mpi_invm (d, e, f);
920
921
  /* Compute the inverse of p and q.  */
922
0
  u = f; f = NULL;
923
0
  mpi_invm (u, p, q );
924
925
0
  if( DBG_CIPHER )
926
0
    {
927
0
      if (*swapped)
928
0
        log_debug ("p and q are swapped\n");
929
0
      log_mpidump("  p", p );
930
0
      log_mpidump("  q", q );
931
0
      log_mpidump("  n", n );
932
0
      log_mpidump("  e", e );
933
0
      log_mpidump("  d", d );
934
0
      log_mpidump("  u", u );
935
0
    }
936
937
938
0
  sk->n = n;
939
0
  sk->e = e;
940
0
  sk->p = p;
941
0
  sk->q = q;
942
0
  sk->d = d;
943
0
  sk->u = u;
944
945
  /* Now we can test our keys. */
946
0
  if (test_keys (sk, nbits - 64))
947
0
    {
948
0
      _gcry_mpi_release (sk->n); sk->n = NULL;
949
0
      _gcry_mpi_release (sk->e); sk->e = NULL;
950
0
      _gcry_mpi_release (sk->p); sk->p = NULL;
951
0
      _gcry_mpi_release (sk->q); sk->q = NULL;
952
0
      _gcry_mpi_release (sk->d); sk->d = NULL;
953
0
      _gcry_mpi_release (sk->u); sk->u = NULL;
954
0
      fips_signal_error ("self-test after key generation failed");
955
0
      return GPG_ERR_SELFTEST_FAILED;
956
0
    }
957
958
0
  return 0;
959
0
}
960
961
962
/****************
963
 * Test whether the secret key is valid.
964
 * Returns: true if this is a valid key.
965
 */
966
static int
967
check_secret_key( RSA_secret_key *sk )
968
0
{
969
0
  int rc;
970
0
  gcry_mpi_t temp = mpi_alloc( mpi_get_nlimbs(sk->p)*2 );
971
972
0
  mpi_mul(temp, sk->p, sk->q );
973
0
  rc = mpi_cmp( temp, sk->n );
974
0
  mpi_free(temp);
975
0
  return !rc;
976
0
}
977
978
979
980
/****************
981
 * Public key operation. Encrypt INPUT with PKEY and put result into OUTPUT.
982
 *
983
 *  c = m^e mod n
984
 *
985
 * Where c is OUTPUT, m is INPUT and e,n are elements of PKEY.
986
 */
987
static void
988
public(gcry_mpi_t output, gcry_mpi_t input, RSA_public_key *pkey )
989
0
{
990
0
  if( output == input )  /* powm doesn't like output and input the same */
991
0
    {
992
0
      gcry_mpi_t x = mpi_alloc( mpi_get_nlimbs(input)*2 );
993
0
      mpi_powm( x, input, pkey->e, pkey->n );
994
0
      mpi_set(output, x);
995
0
      mpi_free(x);
996
0
    }
997
0
  else
998
0
    mpi_powm( output, input, pkey->e, pkey->n );
999
0
}
1000
1001
#if 0
1002
static void
1003
stronger_key_check ( RSA_secret_key *skey )
1004
{
1005
  gcry_mpi_t t = mpi_alloc_secure ( 0 );
1006
  gcry_mpi_t t1 = mpi_alloc_secure ( 0 );
1007
  gcry_mpi_t t2 = mpi_alloc_secure ( 0 );
1008
  gcry_mpi_t phi = mpi_alloc_secure ( 0 );
1009
1010
  /* check that n == p * q */
1011
  mpi_mul( t, skey->p, skey->q);
1012
  if (mpi_cmp( t, skey->n) )
1013
    log_info ( "RSA Oops: n != p * q\n" );
1014
1015
  /* check that p is less than q */
1016
  if( mpi_cmp( skey->p, skey->q ) > 0 )
1017
    {
1018
      log_info ("RSA Oops: p >= q - fixed\n");
1019
      _gcry_mpi_swap ( skey->p, skey->q);
1020
    }
1021
1022
    /* check that e divides neither p-1 nor q-1 */
1023
    mpi_sub_ui(t, skey->p, 1 );
1024
    mpi_fdiv_r(t, t, skey->e );
1025
    if ( !mpi_cmp_ui( t, 0) )
1026
        log_info ( "RSA Oops: e divides p-1\n" );
1027
    mpi_sub_ui(t, skey->q, 1 );
1028
    mpi_fdiv_r(t, t, skey->e );
1029
    if ( !mpi_cmp_ui( t, 0) )
1030
        log_info ( "RSA Oops: e divides q-1\n" );
1031
1032
    /* check that d is correct */
1033
    mpi_sub_ui( t1, skey->p, 1 );
1034
    mpi_sub_ui( t2, skey->q, 1 );
1035
    mpi_mul( phi, t1, t2 );
1036
    gcry_mpi_gcd(t, t1, t2);
1037
    mpi_fdiv_q(t, phi, t);
1038
    mpi_invm(t, skey->e, t );
1039
    if ( mpi_cmp(t, skey->d ) )
1040
      {
1041
        log_info ( "RSA Oops: d is wrong - fixed\n");
1042
        mpi_set (skey->d, t);
1043
        log_printmpi ("  fixed d", skey->d);
1044
      }
1045
1046
    /* check for correctness of u */
1047
    mpi_invm(t, skey->p, skey->q );
1048
    if ( mpi_cmp(t, skey->u ) )
1049
      {
1050
        log_info ( "RSA Oops: u is wrong - fixed\n");
1051
        mpi_set (skey->u, t);
1052
        log_printmpi ("  fixed u", skey->u);
1053
      }
1054
1055
    log_info ( "RSA secret key check finished\n");
1056
1057
    mpi_free (t);
1058
    mpi_free (t1);
1059
    mpi_free (t2);
1060
    mpi_free (phi);
1061
}
1062
#endif
1063
1064
1065

1066
/* Secret key operation - standard version.
1067
 *
1068
 *  m = c^d mod n
1069
 */
1070
static void
1071
secret_core_std (gcry_mpi_t M, gcry_mpi_t C,
1072
                 gcry_mpi_t D, gcry_mpi_t N)
1073
0
{
1074
0
  mpi_powm (M, C, D, N);
1075
0
}
1076
1077
1078
/* Secret key operation - using the CRT.
1079
 *
1080
 *      m1 = c ^ (d mod (p-1)) mod p
1081
 *      m2 = c ^ (d mod (q-1)) mod q
1082
 *      h = u * (m2 - m1) mod q
1083
 *      m = m1 + h * p
1084
 */
1085
static void
1086
secret_core_crt (gcry_mpi_t M, gcry_mpi_t C,
1087
                 gcry_mpi_t D, unsigned int Nlimbs,
1088
                 gcry_mpi_t P, gcry_mpi_t Q, gcry_mpi_t U)
1089
0
{
1090
0
  gcry_mpi_t m1 = mpi_alloc_secure ( Nlimbs + 1 );
1091
0
  gcry_mpi_t m2 = mpi_alloc_secure ( Nlimbs + 1 );
1092
0
  gcry_mpi_t h  = mpi_alloc_secure ( Nlimbs + 1 );
1093
0
  gcry_mpi_t D_blind = mpi_alloc_secure ( Nlimbs + 1 );
1094
0
  gcry_mpi_t r;
1095
0
  unsigned int r_nbits;
1096
1097
0
  r_nbits = mpi_get_nbits (P) / 4;
1098
0
  if (r_nbits < 96)
1099
0
    r_nbits = 96;
1100
0
  r = mpi_secure_new (r_nbits);
1101
1102
  /* d_blind = (d mod (p-1)) + (p-1) * r            */
1103
  /* m1 = c ^ d_blind mod p */
1104
0
  _gcry_mpi_randomize (r, r_nbits, GCRY_WEAK_RANDOM);
1105
0
  mpi_set_highbit (r, r_nbits - 1);
1106
0
  mpi_sub_ui ( h, P, 1 );
1107
0
  mpi_mul ( D_blind, h, r );
1108
0
  mpi_fdiv_r ( h, D, h );
1109
0
  mpi_add ( D_blind, D_blind, h );
1110
0
  mpi_powm ( m1, C, D_blind, P );
1111
1112
  /* d_blind = (d mod (q-1)) + (q-1) * r            */
1113
  /* m2 = c ^ d_blind mod q */
1114
0
  _gcry_mpi_randomize (r, r_nbits, GCRY_WEAK_RANDOM);
1115
0
  mpi_set_highbit (r, r_nbits - 1);
1116
0
  mpi_sub_ui ( h, Q, 1  );
1117
0
  mpi_mul ( D_blind, h, r );
1118
0
  mpi_fdiv_r ( h, D, h );
1119
0
  mpi_add ( D_blind, D_blind, h );
1120
0
  mpi_powm ( m2, C, D_blind, Q );
1121
1122
0
  mpi_free ( r );
1123
0
  mpi_free ( D_blind );
1124
1125
  /* h = u * ( m2 - m1 ) mod q */
1126
0
  mpi_sub ( h, m2, m1 );
1127
0
  if ( mpi_has_sign ( h ) )
1128
0
    mpi_add ( h, h, Q );
1129
0
  mpi_mulm ( h, U, h, Q );
1130
1131
  /* m = m1 + h * p */
1132
0
  mpi_mul ( h, h, P );
1133
0
  mpi_add ( M, m1, h );
1134
1135
0
  mpi_free ( h );
1136
0
  mpi_free ( m1 );
1137
0
  mpi_free ( m2 );
1138
0
}
1139
1140
1141
/* Secret key operation.
1142
 * Encrypt INPUT with SKEY and put result into
1143
 * OUTPUT.  SKEY has the secret key parameters.
1144
 */
1145
static void
1146
secret (gcry_mpi_t output, gcry_mpi_t input, RSA_secret_key *skey )
1147
0
{
1148
  /* Remove superfluous leading zeroes from INPUT.  */
1149
0
  mpi_normalize (input);
1150
1151
0
  if (!skey->p || !skey->q || !skey->u)
1152
0
    {
1153
0
      secret_core_std (output, input, skey->d, skey->n);
1154
0
    }
1155
0
  else
1156
0
    {
1157
0
      secret_core_crt (output, input, skey->d, mpi_get_nlimbs (skey->n),
1158
0
                       skey->p, skey->q, skey->u);
1159
0
    }
1160
0
}
1161
1162
1163
static void
1164
secret_blinded (gcry_mpi_t output, gcry_mpi_t input,
1165
                RSA_secret_key *sk, unsigned int nbits)
1166
0
{
1167
0
  gcry_mpi_t r;            /* Random number needed for blinding.  */
1168
0
  gcry_mpi_t ri;     /* Modular multiplicative inverse of r.  */
1169
0
  gcry_mpi_t bldata;       /* Blinded data to decrypt.  */
1170
1171
  /* First, we need a random number r between 0 and n - 1, which is
1172
   * relatively prime to n (i.e. it is neither p nor q).  The random
1173
   * number needs to be only unpredictable, thus we employ the
1174
   * gcry_create_nonce function by using GCRY_WEAK_RANDOM with
1175
   * gcry_mpi_randomize.  */
1176
0
  r  = mpi_snew (nbits);
1177
0
  ri = mpi_snew (nbits);
1178
0
  bldata = mpi_snew (nbits);
1179
1180
0
  do
1181
0
    {
1182
0
      _gcry_mpi_randomize (r, nbits, GCRY_WEAK_RANDOM);
1183
0
      mpi_mod (r, r, sk->n);
1184
0
    }
1185
0
  while (!mpi_invm (ri, r, sk->n));
1186
1187
  /* Do blinding.  We calculate: y = (x * r^e) mod n, where r is the
1188
   * random number, e is the public exponent, x is the non-blinded
1189
   * input data and n is the RSA modulus.  */
1190
0
  mpi_powm (bldata, r, sk->e, sk->n);
1191
0
  mpi_mulm (bldata, bldata, input, sk->n);
1192
1193
  /* Perform decryption.  */
1194
0
  secret (output, bldata, sk);
1195
0
  _gcry_mpi_release (bldata);
1196
1197
  /* Undo blinding.  Here we calculate: y = (x * r^-1) mod n, where x
1198
   * is the blinded decrypted data, ri is the modular multiplicative
1199
   * inverse of r and n is the RSA modulus.  */
1200
0
  mpi_mulm (output, output, ri, sk->n);
1201
1202
0
  _gcry_mpi_release (r);
1203
0
  _gcry_mpi_release (ri);
1204
0
}
1205
1206

1207
/*********************************************
1208
 **************  interface  ******************
1209
 *********************************************/
1210
1211
static gcry_err_code_t
1212
rsa_generate (const gcry_sexp_t genparms, gcry_sexp_t *r_skey)
1213
0
{
1214
0
  gpg_err_code_t ec;
1215
0
  unsigned int nbits;
1216
0
  unsigned long evalue;
1217
0
  RSA_secret_key sk;
1218
0
  gcry_sexp_t deriveparms;
1219
0
  int flags = 0;
1220
0
  gcry_sexp_t l1;
1221
0
  gcry_sexp_t swap_info = NULL;
1222
0
  int testparms = 0;
1223
1224
0
  memset (&sk, 0, sizeof sk);
1225
1226
0
  ec = _gcry_pk_util_get_nbits (genparms, &nbits);
1227
0
  if (ec)
1228
0
    return ec;
1229
1230
0
  ec = _gcry_pk_util_get_rsa_use_e (genparms, &evalue);
1231
0
  if (ec)
1232
0
    return ec;
1233
1234
  /* Parse the optional flags list.  */
1235
0
  l1 = sexp_find_token (genparms, "flags", 0);
1236
0
  if (l1)
1237
0
    {
1238
0
      ec = _gcry_pk_util_parse_flaglist (l1, &flags, NULL);
1239
0
      sexp_release (l1);
1240
0
      if (ec)
1241
0
        return ec;
1242
0
    }
1243
1244
0
  deriveparms = (genparms?
1245
0
                 sexp_find_token (genparms, "derive-parms", 0) : NULL);
1246
0
  if (!deriveparms)
1247
0
    {
1248
      /* Parse the optional "use-x931" flag. */
1249
0
      l1 = sexp_find_token (genparms, "use-x931", 0);
1250
0
      if (l1)
1251
0
        {
1252
0
          flags |= PUBKEY_FLAG_USE_X931;
1253
0
          sexp_release (l1);
1254
0
        }
1255
0
    }
1256
1257
0
  if (deriveparms || (flags & PUBKEY_FLAG_USE_X931))
1258
0
    {
1259
0
      int swapped;
1260
0
      if (fips_mode ())
1261
0
        {
1262
0
          sexp_release (deriveparms);
1263
0
          return GPG_ERR_INV_SEXP;
1264
0
        }
1265
0
      ec = generate_x931 (&sk, nbits, evalue, deriveparms, &swapped);
1266
0
      sexp_release (deriveparms);
1267
0
      if (!ec && swapped)
1268
0
        ec = sexp_new (&swap_info, "(misc-key-info(p-q-swapped))", 0, 1);
1269
0
    }
1270
0
  else
1271
0
    {
1272
      /* Parse the optional "transient-key" flag. */
1273
0
      if (!(flags & PUBKEY_FLAG_TRANSIENT_KEY))
1274
0
        {
1275
0
          l1 = sexp_find_token (genparms, "transient-key", 0);
1276
0
          if (l1)
1277
0
            {
1278
0
              flags |= PUBKEY_FLAG_TRANSIENT_KEY;
1279
0
              sexp_release (l1);
1280
0
            }
1281
0
        }
1282
0
      deriveparms = (genparms? sexp_find_token (genparms, "test-parms", 0)
1283
0
                     /**/    : NULL);
1284
0
      if (deriveparms)
1285
0
        testparms = 1;
1286
1287
      /* Generate.  */
1288
0
      if (deriveparms || fips_mode ())
1289
0
        {
1290
0
          ec = generate_fips (&sk, nbits, evalue, deriveparms,
1291
0
                              !!(flags & PUBKEY_FLAG_TRANSIENT_KEY));
1292
0
        }
1293
0
      else
1294
0
        {
1295
0
          ec = generate_std (&sk, nbits, evalue,
1296
0
                             !!(flags & PUBKEY_FLAG_TRANSIENT_KEY));
1297
0
        }
1298
0
      sexp_release (deriveparms);
1299
0
    }
1300
1301
0
  if (!ec)
1302
0
    {
1303
0
      ec = sexp_build (r_skey, NULL,
1304
0
                       "(key-data"
1305
0
                       " (public-key"
1306
0
                       "  (rsa(n%m)(e%m)))"
1307
0
                       " (private-key"
1308
0
                       "  (rsa(n%m)(e%m)(d%m)(p%m)(q%m)(u%m)))"
1309
0
                       " %S)",
1310
0
                       sk.n, sk.e,
1311
0
                       sk.n, sk.e, sk.d, sk.p, sk.q, sk.u,
1312
0
                       swap_info);
1313
0
    }
1314
1315
0
  mpi_free (sk.n);
1316
0
  mpi_free (sk.e);
1317
0
  mpi_free (sk.p);
1318
0
  mpi_free (sk.q);
1319
0
  mpi_free (sk.d);
1320
0
  mpi_free (sk.u);
1321
0
  sexp_release (swap_info);
1322
1323
0
  if (!ec && !testparms && fips_mode () && test_keys_fips (*r_skey))
1324
0
    {
1325
0
      sexp_release (*r_skey); *r_skey = NULL;
1326
0
      fips_signal_error ("self-test after key generation failed");
1327
0
      return GPG_ERR_SELFTEST_FAILED;
1328
0
    }
1329
1330
0
  return ec;
1331
0
}
1332
1333
1334
static gcry_err_code_t
1335
rsa_check_secret_key (gcry_sexp_t keyparms)
1336
0
{
1337
0
  gcry_err_code_t rc;
1338
0
  RSA_secret_key sk = {NULL, NULL, NULL, NULL, NULL, NULL};
1339
1340
  /* To check the key we need the optional parameters. */
1341
0
  rc = sexp_extract_param (keyparms, NULL, "nedpqu",
1342
0
                           &sk.n, &sk.e, &sk.d, &sk.p, &sk.q, &sk.u,
1343
0
                           NULL);
1344
0
  if (rc)
1345
0
    goto leave;
1346
1347
0
  if (!check_secret_key (&sk))
1348
0
    rc = GPG_ERR_BAD_SECKEY;
1349
1350
0
 leave:
1351
0
  _gcry_mpi_release (sk.n);
1352
0
  _gcry_mpi_release (sk.e);
1353
0
  _gcry_mpi_release (sk.d);
1354
0
  _gcry_mpi_release (sk.p);
1355
0
  _gcry_mpi_release (sk.q);
1356
0
  _gcry_mpi_release (sk.u);
1357
0
  if (DBG_CIPHER)
1358
0
    log_debug ("rsa_testkey    => %s\n", gpg_strerror (rc));
1359
0
  return rc;
1360
0
}
1361
1362
1363
static gcry_err_code_t
1364
rsa_encrypt (gcry_sexp_t *r_ciph, gcry_sexp_t s_data, gcry_sexp_t keyparms)
1365
0
{
1366
0
  gcry_err_code_t rc;
1367
0
  struct pk_encoding_ctx ctx;
1368
0
  gcry_mpi_t data = NULL;
1369
0
  RSA_public_key pk = {NULL, NULL};
1370
0
  gcry_mpi_t ciph = NULL;
1371
0
  unsigned int nbits = rsa_get_nbits (keyparms);
1372
1373
0
  rc = rsa_check_keysize (nbits);
1374
0
  if (rc)
1375
0
    return rc;
1376
1377
0
  _gcry_pk_util_init_encoding_ctx (&ctx, PUBKEY_OP_ENCRYPT, nbits);
1378
1379
  /* Extract the data.  */
1380
0
  rc = _gcry_pk_util_data_to_mpi (s_data, &data, &ctx);
1381
0
  if (rc)
1382
0
    goto leave;
1383
0
  if (DBG_CIPHER)
1384
0
    log_mpidump ("rsa_encrypt data", data);
1385
0
  if (!data || mpi_is_opaque (data))
1386
0
    {
1387
0
      rc = GPG_ERR_INV_DATA;
1388
0
      goto leave;
1389
0
    }
1390
1391
  /* Extract the key.  */
1392
0
  rc = sexp_extract_param (keyparms, NULL, "ne", &pk.n, &pk.e, NULL);
1393
0
  if (rc)
1394
0
    goto leave;
1395
0
  if (DBG_CIPHER)
1396
0
    {
1397
0
      log_mpidump ("rsa_encrypt    n", pk.n);
1398
0
      log_mpidump ("rsa_encrypt    e", pk.e);
1399
0
    }
1400
1401
  /* Do RSA computation and build result.  */
1402
0
  ciph = mpi_new (0);
1403
0
  public (ciph, data, &pk);
1404
0
  if (DBG_CIPHER)
1405
0
    log_mpidump ("rsa_encrypt  res", ciph);
1406
0
  if ((ctx.flags & PUBKEY_FLAG_FIXEDLEN))
1407
0
    {
1408
      /* We need to make sure to return the correct length to avoid
1409
         problems with missing leading zeroes.  */
1410
0
      unsigned char *em;
1411
0
      size_t emlen = (mpi_get_nbits (pk.n)+7)/8;
1412
1413
0
      rc = _gcry_mpi_to_octet_string (&em, NULL, ciph, emlen);
1414
0
      if (!rc)
1415
0
        {
1416
0
          rc = sexp_build (r_ciph, NULL, "(enc-val(rsa(a%b)))", (int)emlen, em);
1417
0
          xfree (em);
1418
0
        }
1419
0
    }
1420
0
  else
1421
0
    rc = sexp_build (r_ciph, NULL, "(enc-val(rsa(a%m)))", ciph);
1422
1423
0
 leave:
1424
0
  _gcry_mpi_release (ciph);
1425
0
  _gcry_mpi_release (pk.n);
1426
0
  _gcry_mpi_release (pk.e);
1427
0
  _gcry_mpi_release (data);
1428
0
  _gcry_pk_util_free_encoding_ctx (&ctx);
1429
0
  if (DBG_CIPHER)
1430
0
    log_debug ("rsa_encrypt    => %s\n", gpg_strerror (rc));
1431
0
  return rc;
1432
0
}
1433
1434
1435
static gcry_err_code_t
1436
rsa_decrypt (gcry_sexp_t *r_plain, gcry_sexp_t s_data, gcry_sexp_t keyparms)
1437
1438
0
{
1439
0
  gpg_err_code_t rc, rc_sexp;
1440
0
  struct pk_encoding_ctx ctx;
1441
0
  gcry_sexp_t l1 = NULL;
1442
0
  gcry_mpi_t data = NULL;
1443
0
  RSA_secret_key sk = {NULL, NULL, NULL, NULL, NULL, NULL};
1444
0
  gcry_mpi_t plain = NULL;
1445
0
  unsigned char *unpad = NULL;
1446
0
  size_t unpadlen = 0;
1447
0
  unsigned int nbits = rsa_get_nbits (keyparms);
1448
0
  gcry_sexp_t result = NULL;
1449
0
  gcry_sexp_t dummy = NULL;
1450
1451
0
  rc = rsa_check_keysize (nbits);
1452
0
  if (rc)
1453
0
    return rc;
1454
1455
0
  _gcry_pk_util_init_encoding_ctx (&ctx, PUBKEY_OP_DECRYPT, nbits);
1456
1457
  /* Extract the data.  */
1458
0
  rc = _gcry_pk_util_preparse_encval (s_data, rsa_names, &l1, &ctx);
1459
0
  if (rc)
1460
0
    goto leave;
1461
0
  rc = sexp_extract_param (l1, NULL, "a", &data, NULL);
1462
0
  if (rc)
1463
0
    goto leave;
1464
0
  if (DBG_CIPHER)
1465
0
    log_printmpi ("rsa_decrypt data", data);
1466
0
  if (mpi_is_opaque (data))
1467
0
    {
1468
0
      rc = GPG_ERR_INV_DATA;
1469
0
      goto leave;
1470
0
    }
1471
1472
  /* Extract the key.  */
1473
0
  rc = sexp_extract_param (keyparms, NULL, "nedp?q?u?",
1474
0
                           &sk.n, &sk.e, &sk.d, &sk.p, &sk.q, &sk.u,
1475
0
                           NULL);
1476
0
  if (rc)
1477
0
    goto leave;
1478
0
  if (DBG_CIPHER)
1479
0
    {
1480
0
      log_printmpi ("rsa_decrypt    n", sk.n);
1481
0
      log_printmpi ("rsa_decrypt    e", sk.e);
1482
0
      if (!fips_mode ())
1483
0
        {
1484
0
          log_printmpi ("rsa_decrypt    d", sk.d);
1485
0
          log_printmpi ("rsa_decrypt    p", sk.p);
1486
0
          log_printmpi ("rsa_decrypt    q", sk.q);
1487
0
          log_printmpi ("rsa_decrypt    u", sk.u);
1488
0
        }
1489
0
    }
1490
1491
  /* Better make sure that there are no superfluous leading zeroes in
1492
     the input and it has not been "padded" using multiples of N.
1493
     This mitigates side-channel attacks (CVE-2013-4576).  */
1494
0
  mpi_normalize (data);
1495
0
  mpi_fdiv_r (data, data, sk.n);
1496
1497
  /* Allocate MPI for the plaintext.  */
1498
0
  plain = mpi_snew (nbits);
1499
1500
  /* We use blinding by default to mitigate timing attacks which can
1501
     be practically mounted over the network as shown by Brumley and
1502
     Boney in 2003.  */
1503
0
  if ((ctx.flags & PUBKEY_FLAG_NO_BLINDING))
1504
0
    secret (plain, data, &sk);
1505
0
  else
1506
0
    secret_blinded (plain, data, &sk, nbits);
1507
1508
0
  if (DBG_CIPHER)
1509
0
    log_printmpi ("rsa_decrypt  res", plain);
1510
1511
  /* Reverse the encoding and build the s-expression.  */
1512
0
  switch (ctx.encoding)
1513
0
    {
1514
0
    case PUBKEY_ENC_PKCS1:
1515
0
      rc = _gcry_rsa_pkcs1_decode_for_enc (&unpad, &unpadlen, nbits, plain);
1516
0
      mpi_free (plain);
1517
0
      plain = NULL;
1518
0
      rc_sexp = sexp_build (&result, NULL, "(value %b)", (int)unpadlen, unpad);
1519
0
      *r_plain = sexp_null_cond (result, ct_is_not_zero (rc));
1520
0
      dummy = sexp_null_cond (result, ct_is_zero (rc));
1521
0
      sexp_release (dummy);
1522
0
      rc = ct_ulong_select (rc_sexp, rc,
1523
0
          ct_is_zero (rc) & ct_is_not_zero (rc_sexp));
1524
0
      break;
1525
1526
0
    case PUBKEY_ENC_OAEP:
1527
0
      rc = _gcry_rsa_oaep_decode (&unpad, &unpadlen,
1528
0
                                  nbits, ctx.hash_algo,
1529
0
                                  plain, ctx.label, ctx.labellen);
1530
0
      mpi_free (plain);
1531
0
      plain = NULL;
1532
0
      rc_sexp = sexp_build (&result, NULL, "(value %b)", (int)unpadlen, unpad);
1533
0
      *r_plain = sexp_null_cond (result, ct_is_not_zero (rc));
1534
0
      dummy = sexp_null_cond (result, ct_is_zero (rc));
1535
0
      sexp_release (dummy);
1536
0
      rc = ct_ulong_select (rc_sexp, rc,
1537
0
          ct_is_zero (rc) & ct_is_not_zero (rc_sexp));
1538
0
      break;
1539
1540
0
    default:
1541
      /* Raw format.  For backward compatibility we need to assume a
1542
         signed mpi by using the sexp format string "%m".  */
1543
0
      rc = sexp_build (r_plain, NULL,
1544
0
                       (ctx.flags & PUBKEY_FLAG_LEGACYRESULT)
1545
0
                       ? "%m":"(value %m)", plain);
1546
0
      break;
1547
0
    }
1548
1549
0
 leave:
1550
0
  xfree (unpad);
1551
0
  _gcry_mpi_release (plain);
1552
0
  _gcry_mpi_release (sk.n);
1553
0
  _gcry_mpi_release (sk.e);
1554
0
  _gcry_mpi_release (sk.d);
1555
0
  _gcry_mpi_release (sk.p);
1556
0
  _gcry_mpi_release (sk.q);
1557
0
  _gcry_mpi_release (sk.u);
1558
0
  _gcry_mpi_release (data);
1559
0
  sexp_release (l1);
1560
0
  _gcry_pk_util_free_encoding_ctx (&ctx);
1561
0
  if (DBG_CIPHER)
1562
0
    log_debug ("rsa_decrypt    => %s\n", gpg_strerror (rc));
1563
0
  return rc;
1564
0
}
1565
1566
1567
static gcry_err_code_t
1568
rsa_sign (gcry_sexp_t *r_sig, gcry_sexp_t s_data, gcry_sexp_t keyparms)
1569
0
{
1570
0
  gpg_err_code_t rc;
1571
0
  struct pk_encoding_ctx ctx;
1572
0
  gcry_mpi_t data = NULL;
1573
0
  RSA_secret_key sk = {NULL, NULL, NULL, NULL, NULL, NULL};
1574
0
  RSA_public_key pk;
1575
0
  gcry_mpi_t sig = NULL;
1576
0
  gcry_mpi_t result = NULL;
1577
0
  unsigned int nbits = rsa_get_nbits (keyparms);
1578
1579
0
  rc = rsa_check_keysize (nbits);
1580
0
  if (rc)
1581
0
    return rc;
1582
1583
0
  _gcry_pk_util_init_encoding_ctx (&ctx, PUBKEY_OP_SIGN, nbits);
1584
1585
  /* Extract the data.  */
1586
0
  rc = _gcry_pk_util_data_to_mpi (s_data, &data, &ctx);
1587
0
  if (rc)
1588
0
    goto leave;
1589
0
  if (DBG_CIPHER)
1590
0
    log_printmpi ("rsa_sign   data", data);
1591
0
  if (mpi_is_opaque (data))
1592
0
    {
1593
0
      rc = GPG_ERR_INV_DATA;
1594
0
      goto leave;
1595
0
    }
1596
1597
  /* Extract the key.  */
1598
0
  rc = sexp_extract_param (keyparms, NULL, "nedp?q?u?",
1599
0
                           &sk.n, &sk.e, &sk.d, &sk.p, &sk.q, &sk.u,
1600
0
                           NULL);
1601
0
  if (rc)
1602
0
    goto leave;
1603
0
  if (DBG_CIPHER)
1604
0
    {
1605
0
      log_printmpi ("rsa_sign      n", sk.n);
1606
0
      log_printmpi ("rsa_sign      e", sk.e);
1607
0
      if (!fips_mode ())
1608
0
        {
1609
0
          log_printmpi ("rsa_sign      d", sk.d);
1610
0
          log_printmpi ("rsa_sign      p", sk.p);
1611
0
          log_printmpi ("rsa_sign      q", sk.q);
1612
0
          log_printmpi ("rsa_sign      u", sk.u);
1613
0
        }
1614
0
    }
1615
1616
  /* Do RSA computation.  */
1617
0
  sig = mpi_new (0);
1618
0
  if ((ctx.flags & PUBKEY_FLAG_NO_BLINDING))
1619
0
    secret (sig, data, &sk);
1620
0
  else
1621
0
    secret_blinded (sig, data, &sk, nbits);
1622
0
  if (DBG_CIPHER)
1623
0
    log_printmpi ("rsa_sign    res", sig);
1624
1625
  /* Check that the created signature is good.  This detects a failure
1626
     of the CRT algorithm  (Lenstra's attack on RSA's use of the CRT).  */
1627
0
  result = mpi_new (0);
1628
0
  pk.n = sk.n;
1629
0
  pk.e = sk.e;
1630
0
  public (result, sig, &pk);
1631
0
  if (mpi_cmp (result, data))
1632
0
    {
1633
0
      rc = GPG_ERR_BAD_SIGNATURE;
1634
0
      goto leave;
1635
0
    }
1636
1637
  /* Convert the result.  */
1638
0
  if ((ctx.flags & PUBKEY_FLAG_FIXEDLEN))
1639
0
    {
1640
      /* We need to make sure to return the correct length to avoid
1641
         problems with missing leading zeroes.  */
1642
0
      unsigned char *em;
1643
0
      size_t emlen = (mpi_get_nbits (sk.n)+7)/8;
1644
1645
0
      rc = _gcry_mpi_to_octet_string (&em, NULL, sig, emlen);
1646
0
      if (!rc)
1647
0
        {
1648
0
          rc = sexp_build (r_sig, NULL, "(sig-val(rsa(s%b)))", (int)emlen, em);
1649
0
          xfree (em);
1650
0
        }
1651
0
    }
1652
0
  else
1653
0
    rc = sexp_build (r_sig, NULL, "(sig-val(rsa(s%M)))", sig);
1654
1655
1656
0
 leave:
1657
0
  _gcry_mpi_release (result);
1658
0
  _gcry_mpi_release (sig);
1659
0
  _gcry_mpi_release (sk.n);
1660
0
  _gcry_mpi_release (sk.e);
1661
0
  _gcry_mpi_release (sk.d);
1662
0
  _gcry_mpi_release (sk.p);
1663
0
  _gcry_mpi_release (sk.q);
1664
0
  _gcry_mpi_release (sk.u);
1665
0
  _gcry_mpi_release (data);
1666
0
  _gcry_pk_util_free_encoding_ctx (&ctx);
1667
0
  if (DBG_CIPHER)
1668
0
    log_debug ("rsa_sign      => %s\n", gpg_strerror (rc));
1669
0
  return rc;
1670
0
}
1671
1672
1673
static gcry_err_code_t
1674
rsa_verify (gcry_sexp_t s_sig, gcry_sexp_t s_data, gcry_sexp_t keyparms)
1675
0
{
1676
0
  gcry_err_code_t rc;
1677
0
  struct pk_encoding_ctx ctx;
1678
0
  gcry_sexp_t l1 = NULL;
1679
0
  gcry_mpi_t sig = NULL;
1680
0
  gcry_mpi_t data = NULL;
1681
0
  RSA_public_key pk = { NULL, NULL };
1682
0
  gcry_mpi_t result = NULL;
1683
0
  unsigned int nbits = rsa_get_nbits (keyparms);
1684
1685
0
  rc = rsa_check_verify_keysize (nbits);
1686
0
  if (rc)
1687
0
    return rc;
1688
1689
0
  _gcry_pk_util_init_encoding_ctx (&ctx, PUBKEY_OP_VERIFY, nbits);
1690
1691
  /* Extract the data.  */
1692
0
  rc = _gcry_pk_util_data_to_mpi (s_data, &data, &ctx);
1693
0
  if (rc)
1694
0
    goto leave;
1695
0
  if (DBG_CIPHER)
1696
0
    log_printmpi ("rsa_verify data", data);
1697
0
  if (ctx.encoding != PUBKEY_ENC_PSS && mpi_is_opaque (data))
1698
0
    {
1699
0
      rc = GPG_ERR_INV_DATA;
1700
0
      goto leave;
1701
0
    }
1702
1703
  /* Extract the signature value.  */
1704
0
  rc = _gcry_pk_util_preparse_sigval (s_sig, rsa_names, &l1, NULL);
1705
0
  if (rc)
1706
0
    goto leave;
1707
0
  rc = sexp_extract_param (l1, NULL, "s", &sig, NULL);
1708
0
  if (rc)
1709
0
    goto leave;
1710
0
  if (DBG_CIPHER)
1711
0
    log_printmpi ("rsa_verify  sig", sig);
1712
1713
  /* Extract the key.  */
1714
0
  rc = sexp_extract_param (keyparms, NULL, "ne", &pk.n, &pk.e, NULL);
1715
0
  if (rc)
1716
0
    goto leave;
1717
0
  if (DBG_CIPHER)
1718
0
    {
1719
0
      log_printmpi ("rsa_verify    n", pk.n);
1720
0
      log_printmpi ("rsa_verify    e", pk.e);
1721
0
    }
1722
1723
  /* Do RSA computation and compare.  */
1724
0
  result = mpi_new (0);
1725
0
  public (result, sig, &pk);
1726
0
  if (DBG_CIPHER)
1727
0
    log_printmpi ("rsa_verify  cmp", result);
1728
0
  if (ctx.verify_cmp)
1729
0
    rc = ctx.verify_cmp (&ctx, result);
1730
0
  else
1731
0
    rc = mpi_cmp (result, data) ? GPG_ERR_BAD_SIGNATURE : 0;
1732
1733
0
 leave:
1734
0
  _gcry_mpi_release (result);
1735
0
  _gcry_mpi_release (pk.n);
1736
0
  _gcry_mpi_release (pk.e);
1737
0
  _gcry_mpi_release (data);
1738
0
  _gcry_mpi_release (sig);
1739
0
  sexp_release (l1);
1740
0
  _gcry_pk_util_free_encoding_ctx (&ctx);
1741
0
  if (DBG_CIPHER)
1742
0
    log_debug ("rsa_verify    => %s\n", rc?gpg_strerror (rc):"Good");
1743
0
  return rc;
1744
0
}
1745
1746
1747
1748
/* Return the number of bits for the key described by PARMS.  On error
1749
 * 0 is returned.  The format of PARMS starts with the algorithm name;
1750
 * for example:
1751
 *
1752
 *   (rsa
1753
 *     (n <mpi>)
1754
 *     (e <mpi>))
1755
 *
1756
 * More parameters may be given but we only need N here.
1757
 */
1758
static unsigned int
1759
rsa_get_nbits (gcry_sexp_t parms)
1760
0
{
1761
0
  gcry_sexp_t l1;
1762
0
  gcry_mpi_t n;
1763
0
  unsigned int nbits;
1764
1765
0
  l1 = sexp_find_token (parms, "n", 1);
1766
0
  if (!l1)
1767
0
    return 0; /* Parameter N not found.  */
1768
1769
0
  n = sexp_nth_mpi (l1, 1, GCRYMPI_FMT_USG);
1770
0
  sexp_release (l1);
1771
0
  nbits = n? mpi_get_nbits (n) : 0;
1772
0
  _gcry_mpi_release (n);
1773
0
  return nbits;
1774
0
}
1775
1776
1777
/* Compute a keygrip.  MD is the hash context which we are going to
1778
   update.  KEYPARAM is an S-expression with the key parameters, this
1779
   is usually a public key but may also be a secret key.  An example
1780
   of such an S-expression is:
1781
1782
      (rsa
1783
        (n #00B...#)
1784
        (e #010001#))
1785
1786
   PKCS-15 says that for RSA only the modulus should be hashed -
1787
   however, it is not clear whether this is meant to use the raw bytes
1788
   (assuming this is an unsigned integer) or whether the DER required
1789
   0 should be prefixed.  We hash the raw bytes.  */
1790
static gpg_err_code_t
1791
compute_keygrip (gcry_md_hd_t md, gcry_sexp_t keyparam)
1792
0
{
1793
0
  gcry_sexp_t l1;
1794
0
  const char *data;
1795
0
  size_t datalen;
1796
1797
0
  l1 = sexp_find_token (keyparam, "n", 1);
1798
0
  if (!l1)
1799
0
    return GPG_ERR_NO_OBJ;
1800
1801
0
  data = sexp_nth_data (l1, 1, &datalen);
1802
0
  if (!data)
1803
0
    {
1804
0
      sexp_release (l1);
1805
0
      return GPG_ERR_NO_OBJ;
1806
0
    }
1807
1808
0
  _gcry_md_write (md, data, datalen);
1809
0
  sexp_release (l1);
1810
1811
0
  return 0;
1812
0
}
1813
1814
1815
1816

1817
/*
1818
     Self-test section.
1819
 */
1820
1821
static const char *
1822
selftest_hash_sign_2048 (gcry_sexp_t pkey, gcry_sexp_t skey)
1823
0
{
1824
0
  int md_algo = GCRY_MD_SHA256;
1825
0
  gcry_md_hd_t hd = NULL;
1826
0
  const char *data_tmpl = "(data (flags pkcs1) (hash %s %b))";
1827
0
  static const char sample_data[] =
1828
0
    "11223344556677889900aabbccddeeff"
1829
0
    "102030405060708090a0b0c0d0f01121";
1830
0
  static const char sample_data_bad[] =
1831
0
    "11223344556677889900aabbccddeeff"
1832
0
    "802030405060708090a0b0c0d0f01121";
1833
1834
0
  const char *errtxt = NULL;
1835
0
  gcry_error_t err;
1836
0
  gcry_sexp_t sig = NULL;
1837
  /* raw signature data reference */
1838
0
  const char ref_data[] =
1839
0
    "518f41dea3ad884e93eefff8d7ca68a6f4c30d923632e35673651d675cebd652"
1840
0
    "a44ed66f6879b18f3d48b2d235b1dd78f6189be1440352cc94231a55c1f93109"
1841
0
    "84616b2841c42fe9a6e37be34cd188207209bd028e2fa93e721fbac40c31a068"
1842
0
    "1253b312d4e07addb9c7f3d508fa89f218ea7c7f7b9f6a9b1e522c19fa1cd839"
1843
0
    "93f9d4ca2f16c3d0b9abafe5e63e848152afc72ce7ee19ea45353116f85209ea"
1844
0
    "b9de42129dbccdac8faa461e8e8cc2ae801101cc6add4ba76ccb752030b0e827"
1845
0
    "7352b11cdecebae9cdc9a626c4701cd9c85cd287618888c5fae8b4d0ba48915d"
1846
0
    "e5cc64e3aee2ba2862d04348ea71f65454f74f9fd1e3108005cc367ca41585a4";
1847
0
  gcry_mpi_t ref_mpi = NULL;
1848
0
  gcry_mpi_t sig_mpi = NULL;
1849
1850
0
  err = _gcry_md_open (&hd, md_algo, 0);
1851
0
  if (err)
1852
0
    {
1853
0
      errtxt = "gcry_md_open failed";
1854
0
      goto leave;
1855
0
    }
1856
1857
0
  _gcry_md_write (hd, sample_data, sizeof(sample_data));
1858
1859
0
  err = _gcry_pk_sign_md (&sig, data_tmpl, hd, skey, NULL);
1860
0
  if (err)
1861
0
    {
1862
0
      errtxt = "signing failed";
1863
0
      goto leave;
1864
0
    }
1865
1866
0
  err = _gcry_mpi_scan(&ref_mpi, GCRYMPI_FMT_HEX, ref_data, 0, NULL);
1867
0
  if (err)
1868
0
    {
1869
0
      errtxt = "converting ref_data to mpi failed";
1870
0
      goto leave;
1871
0
    }
1872
1873
0
  err = _gcry_sexp_extract_param(sig, "sig-val!rsa", "s", &sig_mpi, NULL);
1874
0
  if (err)
1875
0
    {
1876
0
      errtxt = "extracting signature data failed";
1877
0
      goto leave;
1878
0
    }
1879
1880
0
  if (mpi_cmp (sig_mpi, ref_mpi))
1881
0
    {
1882
0
      errtxt = "signature does not match reference data";
1883
0
      goto leave;
1884
0
    }
1885
1886
0
  err = _gcry_pk_verify_md (sig, data_tmpl, hd, pkey, NULL);
1887
0
  if (err)
1888
0
    {
1889
0
      errtxt = "verify failed";
1890
0
      goto leave;
1891
0
    }
1892
1893
0
  _gcry_md_reset(hd);
1894
0
  _gcry_md_write (hd, sample_data_bad, sizeof(sample_data_bad));
1895
0
  err = _gcry_pk_verify_md (sig, data_tmpl, hd, pkey, NULL);
1896
0
  if (gcry_err_code (err) != GPG_ERR_BAD_SIGNATURE)
1897
0
    {
1898
0
      errtxt = "bad signature not detected";
1899
0
      goto leave;
1900
0
    }
1901
1902
1903
0
 leave:
1904
0
  sexp_release (sig);
1905
0
  _gcry_md_close (hd);
1906
0
  _gcry_mpi_release (ref_mpi);
1907
0
  _gcry_mpi_release (sig_mpi);
1908
0
  return errtxt;
1909
0
}
1910
1911
static const char *
1912
selftest_sign_2048 (gcry_sexp_t pkey, gcry_sexp_t skey)
1913
0
{
1914
0
  static const char sample_data[] =
1915
0
    "(data (flags pkcs1)"
1916
0
    " (hash sha256 #11223344556677889900aabbccddeeff"
1917
0
    /**/           "102030405060708090a0b0c0d0f01121#))";
1918
0
  static const char sample_data_bad[] =
1919
0
    "(data (flags pkcs1)"
1920
0
    " (hash sha256 #11223344556677889900aabbccddeeff"
1921
0
    /**/           "802030405060708090a0b0c0d0f01121#))";
1922
1923
0
  const char *errtxt = NULL;
1924
0
  gcry_error_t err;
1925
0
  gcry_sexp_t data = NULL;
1926
0
  gcry_sexp_t data_bad = NULL;
1927
0
  gcry_sexp_t sig = NULL;
1928
  /* raw signature data reference */
1929
0
  const char ref_data[] =
1930
0
    "6252a19a11e1d5155ed9376036277193d644fa239397fff03e9b92d6f86415d6"
1931
0
    "d30da9273775f290e580d038295ff8ff89522becccfa6ae870bf76b76df402a8"
1932
0
    "54f69347e3db3de8e1e7d4dada281ec556810c7a8ecd0b5f51f9b1c0e7aa7557"
1933
0
    "61aa2b8ba5f811304acc6af0eca41fe49baf33bf34eddaf44e21e036ac7f0b68"
1934
0
    "03cdef1c60021fb7b5b97ebacdd88ab755ce29af568dbc5728cc6e6eff42618d"
1935
0
    "62a0386ca8beed46402bdeeef29b6a3feded906bace411a06a39192bf516ae10"
1936
0
    "67e4320fa8ea113968525f4574d022a3ceeaafdc41079efe1f22cc94bf59d8d3"
1937
0
    "328085da9674857db56de5978a62394aab48aa3b72e23a1b16260cfd9daafe65";
1938
0
  gcry_mpi_t ref_mpi = NULL;
1939
0
  gcry_mpi_t sig_mpi = NULL;
1940
1941
0
  err = sexp_sscan (&data, NULL, sample_data, strlen (sample_data));
1942
0
  if (!err)
1943
0
    err = sexp_sscan (&data_bad, NULL,
1944
0
                      sample_data_bad, strlen (sample_data_bad));
1945
0
  if (err)
1946
0
    {
1947
0
      errtxt = "converting data failed";
1948
0
      goto leave;
1949
0
    }
1950
1951
0
  err = _gcry_pk_sign (&sig, data, skey);
1952
0
  if (err)
1953
0
    {
1954
0
      errtxt = "signing failed";
1955
0
      goto leave;
1956
0
    }
1957
1958
0
  err = _gcry_mpi_scan(&ref_mpi, GCRYMPI_FMT_HEX, ref_data, 0, NULL);
1959
0
  if (err)
1960
0
    {
1961
0
      errtxt = "converting ref_data to mpi failed";
1962
0
      goto leave;
1963
0
    }
1964
1965
0
  err = _gcry_sexp_extract_param(sig, "sig-val!rsa", "s", &sig_mpi, NULL);
1966
0
  if (err)
1967
0
    {
1968
0
      errtxt = "extracting signature data failed";
1969
0
      goto leave;
1970
0
    }
1971
1972
0
  if (mpi_cmp (sig_mpi, ref_mpi))
1973
0
    {
1974
0
      errtxt = "signature does not match reference data";
1975
0
      goto leave;
1976
0
    }
1977
1978
0
  err = _gcry_pk_verify (sig, data, pkey);
1979
0
  if (err)
1980
0
    {
1981
0
      errtxt = "verify failed";
1982
0
      goto leave;
1983
0
    }
1984
0
  err = _gcry_pk_verify (sig, data_bad, pkey);
1985
0
  if (gcry_err_code (err) != GPG_ERR_BAD_SIGNATURE)
1986
0
    {
1987
0
      errtxt = "bad signature not detected";
1988
0
      goto leave;
1989
0
    }
1990
1991
1992
0
 leave:
1993
0
  sexp_release (sig);
1994
0
  sexp_release (data_bad);
1995
0
  sexp_release (data);
1996
0
  _gcry_mpi_release (ref_mpi);
1997
0
  _gcry_mpi_release (sig_mpi);
1998
0
  return errtxt;
1999
0
}
2000
2001
2002
2003
/* Given an S-expression ENCR_DATA of the form:
2004
2005
   (enc-val
2006
    (rsa
2007
     (a a-value)))
2008
2009
   as returned by gcry_pk_decrypt, return the the A-VALUE.  On error,
2010
   return NULL.  */
2011
static gcry_mpi_t
2012
extract_a_from_sexp (gcry_sexp_t encr_data)
2013
0
{
2014
0
  gcry_sexp_t l1, l2, l3;
2015
0
  gcry_mpi_t a_value;
2016
2017
0
  l1 = sexp_find_token (encr_data, "enc-val", 0);
2018
0
  if (!l1)
2019
0
    return NULL;
2020
0
  l2 = sexp_find_token (l1, "rsa", 0);
2021
0
  sexp_release (l1);
2022
0
  if (!l2)
2023
0
    return NULL;
2024
0
  l3 = sexp_find_token (l2, "a", 0);
2025
0
  sexp_release (l2);
2026
0
  if (!l3)
2027
0
    return NULL;
2028
0
  a_value = sexp_nth_mpi (l3, 1, 0);
2029
0
  sexp_release (l3);
2030
2031
0
  return a_value;
2032
0
}
2033
2034
2035
static const char *
2036
selftest_encr_2048 (gcry_sexp_t pkey, gcry_sexp_t skey)
2037
0
{
2038
0
  const char *errtxt = NULL;
2039
0
  gcry_error_t err;
2040
0
  static const char plaintext[] =
2041
0
    "Jim quickly realized that the beautiful gowns are expensive.";
2042
0
  gcry_sexp_t plain = NULL;
2043
0
  gcry_sexp_t encr  = NULL;
2044
0
  gcry_mpi_t  ciphertext = NULL;
2045
0
  gcry_sexp_t decr  = NULL;
2046
0
  char *decr_plaintext = NULL;
2047
0
  gcry_sexp_t tmplist = NULL;
2048
  /* expected result of encrypting the plaintext with sample_secret_key */
2049
0
  static const char ref_data[] =
2050
0
    "18022e2593a402a737caaa93b4c7e750e20ca265452980e1d6b7710fbd3e"
2051
0
    "7dce72be5c2110fb47691cb38f42170ee3b4a37f2498d4a51567d762585e"
2052
0
    "4cb81d04fbc7df4144f8e5eac2d4b8688521b64011f11d7ad53f4c874004"
2053
0
    "819856f2e2a6f83d1c9c4e73ac26089789c14482b0b8d44139133c88c4a5"
2054
0
    "2dba9dd6d6ffc622666b7d129168333d999706af30a2d7d272db7734e5ed"
2055
0
    "fb8c64ea3018af3ad20f4a013a5060cb0f5e72753967bebe294280a6ed0d"
2056
0
    "dbd3c4f11d0a8696e9d32a0dc03deb0b5e49b2cbd1503392642d4e1211f3"
2057
0
    "e8e2ee38abaa3671ccd57fcde8ca76e85fd2cb77c35706a970a213a27352"
2058
0
    "cec92a9604d543ddb5fc478ff50e0622";
2059
0
  gcry_mpi_t ref_mpi = NULL;
2060
2061
  /* Put the plaintext into an S-expression.  */
2062
0
  err = sexp_build (&plain, NULL, "(data (flags raw) (value %s))", plaintext);
2063
0
  if (err)
2064
0
    {
2065
0
      errtxt = "converting data failed";
2066
0
      goto leave;
2067
0
    }
2068
2069
  /* Encrypt.  */
2070
0
  err = _gcry_pk_encrypt (&encr, plain, pkey);
2071
0
  if (err)
2072
0
    {
2073
0
      errtxt = "encrypt failed";
2074
0
      goto leave;
2075
0
    }
2076
2077
0
  err = _gcry_mpi_scan(&ref_mpi, GCRYMPI_FMT_HEX, ref_data, 0, NULL);
2078
0
  if (err)
2079
0
    {
2080
0
      errtxt = "converting encrydata to mpi failed";
2081
0
      goto leave;
2082
0
    }
2083
2084
  /* Extraxt the ciphertext from the returned S-expression.  */
2085
  /*sexp_dump (encr);*/
2086
0
  ciphertext = extract_a_from_sexp (encr);
2087
0
  if (!ciphertext)
2088
0
    {
2089
0
      errtxt = "gcry_pk_encrypt returned garbage";
2090
0
      goto leave;
2091
0
    }
2092
2093
  /* Check that the ciphertext does no match the plaintext.  */
2094
  /* _gcry_log_printmpi ("plaintext", plaintext); */
2095
  /* _gcry_log_printmpi ("ciphertxt", ciphertext); */
2096
0
  if (mpi_cmp (ref_mpi, ciphertext))
2097
0
    {
2098
0
      errtxt = "ciphertext doesn't match reference data";
2099
0
      goto leave;
2100
0
    }
2101
2102
  /* Decrypt.  */
2103
0
  err = _gcry_pk_decrypt (&decr, encr, skey);
2104
0
  if (err)
2105
0
    {
2106
0
      errtxt = "decrypt failed";
2107
0
      goto leave;
2108
0
    }
2109
2110
  /* Extract the decrypted data from the S-expression.  Note that the
2111
     output of gcry_pk_decrypt depends on whether a flags lists occurs
2112
     in its input data.  Because we passed the output of
2113
     gcry_pk_encrypt directly to gcry_pk_decrypt, such a flag value
2114
     won't be there as of today.  To be prepared for future changes we
2115
     take care of it anyway.  */
2116
0
  tmplist = sexp_find_token (decr, "value", 0);
2117
0
  if (tmplist)
2118
0
    decr_plaintext = sexp_nth_string (tmplist, 1);
2119
0
  else
2120
0
    decr_plaintext = sexp_nth_string (decr, 0);
2121
0
  if (!decr_plaintext)
2122
0
    {
2123
0
      errtxt = "decrypt returned no plaintext";
2124
0
      goto leave;
2125
0
    }
2126
2127
  /* Check that the decrypted plaintext matches the original  plaintext.  */
2128
0
  if (strcmp (plaintext, decr_plaintext))
2129
0
    {
2130
0
      errtxt = "mismatch";
2131
0
      goto leave;
2132
0
    }
2133
2134
0
 leave:
2135
0
  sexp_release (tmplist);
2136
0
  xfree (decr_plaintext);
2137
0
  sexp_release (decr);
2138
0
  _gcry_mpi_release (ciphertext);
2139
0
  _gcry_mpi_release (ref_mpi);
2140
0
  sexp_release (encr);
2141
0
  sexp_release (plain);
2142
0
  return errtxt;
2143
0
}
2144
2145
2146
static gpg_err_code_t
2147
selftests_rsa (selftest_report_func_t report, int extended)
2148
0
{
2149
0
  const char *what;
2150
0
  const char *errtxt;
2151
0
  gcry_error_t err;
2152
0
  gcry_sexp_t skey = NULL;
2153
0
  gcry_sexp_t pkey = NULL;
2154
2155
  /* Convert the S-expressions into the internal representation.  */
2156
0
  what = "convert";
2157
0
  err = sexp_sscan (&skey, NULL, sample_secret_key, strlen (sample_secret_key));
2158
0
  if (!err)
2159
0
    err = sexp_sscan (&pkey, NULL,
2160
0
                      sample_public_key, strlen (sample_public_key));
2161
0
  if (err)
2162
0
    {
2163
0
      errtxt = _gcry_strerror (err);
2164
0
      goto failed;
2165
0
    }
2166
2167
0
  what = "key consistency";
2168
0
  err = _gcry_pk_testkey (skey);
2169
0
  if (err)
2170
0
    {
2171
0
      errtxt = _gcry_strerror (err);
2172
0
      goto failed;
2173
0
    }
2174
2175
0
  if (extended)
2176
0
    {
2177
0
      what = "sign";
2178
0
      errtxt = selftest_sign_2048 (pkey, skey);
2179
0
      if (errtxt)
2180
0
        goto failed;
2181
0
    }
2182
2183
0
  what = "digest sign";
2184
0
  errtxt = selftest_hash_sign_2048 (pkey, skey);
2185
0
  if (errtxt)
2186
0
    goto failed;
2187
2188
0
  if (extended)
2189
0
    {
2190
0
      what = "encrypt";
2191
0
      errtxt = selftest_encr_2048 (pkey, skey);
2192
0
      if (errtxt)
2193
0
        goto failed;
2194
0
    }
2195
2196
0
  sexp_release (pkey);
2197
0
  sexp_release (skey);
2198
0
  return 0; /* Succeeded. */
2199
2200
0
 failed:
2201
0
  sexp_release (pkey);
2202
0
  sexp_release (skey);
2203
0
  if (report)
2204
0
    report ("pubkey", GCRY_PK_RSA, what, errtxt);
2205
0
  return GPG_ERR_SELFTEST_FAILED;
2206
0
}
2207
2208
2209
/* Run a full self-test for ALGO and return 0 on success.  */
2210
static gpg_err_code_t
2211
run_selftests (int algo, int extended, selftest_report_func_t report)
2212
0
{
2213
0
  gpg_err_code_t ec;
2214
2215
0
  switch (algo)
2216
0
    {
2217
0
    case GCRY_PK_RSA:
2218
0
      ec = selftests_rsa (report, extended);
2219
0
      break;
2220
0
    default:
2221
0
      ec = GPG_ERR_PUBKEY_ALGO;
2222
0
      break;
2223
2224
0
    }
2225
0
  return ec;
2226
0
}
2227
2228
2229
2230

2231
gcry_pk_spec_t _gcry_pubkey_spec_rsa =
2232
  {
2233
    GCRY_PK_RSA, { 0, 1 },
2234
    (GCRY_PK_USAGE_SIGN | GCRY_PK_USAGE_ENCR),
2235
    "RSA", rsa_names,
2236
    "ne", "nedpqu", "a", "s", "n",
2237
    rsa_generate,
2238
    rsa_check_secret_key,
2239
    rsa_encrypt,
2240
    rsa_decrypt,
2241
    rsa_sign,
2242
    rsa_verify,
2243
    rsa_get_nbits,
2244
    run_selftests,
2245
    compute_keygrip
2246
  };