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