mac: Fix gcry_mac_close to allow for a NULL handle.
[libgcrypt.git] / cipher / dsa.c
1 /* dsa.c - DSA signature algorithm
2  * Copyright (C) 1998, 2000, 2001, 2002, 2003,
3  *               2006, 2008  Free Software Foundation, Inc.
4  * Copyright (C) 2013 g10 Code GmbH.
5  *
6  * This file is part of Libgcrypt.
7  *
8  * Libgcrypt is free software; you can redistribute it and/or modify
9  * it under the terms of the GNU Lesser General Public License as
10  * published by the Free Software Foundation; either version 2.1 of
11  * the License, or (at your option) any later version.
12  *
13  * Libgcrypt is distributed in the hope that it will be useful,
14  * but WITHOUT ANY WARRANTY; without even the implied warranty of
15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
16  * GNU Lesser General Public License for more details.
17  *
18  * You should have received a copy of the GNU Lesser General Public
19  * License along with this program; if not, see <http://www.gnu.org/licenses/>.
20  */
21
22 #include <config.h>
23 #include <stdio.h>
24 #include <stdlib.h>
25 #include <string.h>
26
27 #include "g10lib.h"
28 #include "mpi.h"
29 #include "cipher.h"
30 #include "pubkey-internal.h"
31
32
33 typedef struct
34 {
35   gcry_mpi_t p;     /* prime */
36   gcry_mpi_t q;     /* group order */
37   gcry_mpi_t g;     /* group generator */
38   gcry_mpi_t y;     /* g^x mod p */
39 } DSA_public_key;
40
41
42 typedef struct
43 {
44   gcry_mpi_t p;     /* prime */
45   gcry_mpi_t q;     /* group order */
46   gcry_mpi_t g;     /* group generator */
47   gcry_mpi_t y;     /* g^x mod p */
48   gcry_mpi_t x;     /* secret exponent */
49 } DSA_secret_key;
50
51
52 /* A structure used to hold domain parameters.  */
53 typedef struct
54 {
55   gcry_mpi_t p;     /* prime */
56   gcry_mpi_t q;     /* group order */
57   gcry_mpi_t g;     /* group generator */
58 } dsa_domain_t;
59
60
61 static const char *dsa_names[] =
62   {
63     "dsa",
64     "openpgp-dsa",
65     NULL,
66   };
67
68
69 /* A sample 1024 bit DSA key used for the selftests.  */
70 static const char sample_secret_key[] =
71 "(private-key"
72 " (dsa"
73 "  (p #00AD7C0025BA1A15F775F3F2D673718391D00456978D347B33D7B49E7F32EDAB"
74 "      96273899DD8B2BB46CD6ECA263FAF04A28903503D59062A8865D2AE8ADFB5191"
75 "      CF36FFB562D0E2F5809801A1F675DAE59698A9E01EFE8D7DCFCA084F4C6F5A44"
76 "      44D499A06FFAEA5E8EF5E01F2FD20A7B7EF3F6968AFBA1FB8D91F1559D52D8777B#)"
77 "  (q #00EB7B5751D25EBBB7BD59D920315FD840E19AEBF9#)"
78 "  (g #1574363387FDFD1DDF38F4FBE135BB20C7EE4772FB94C337AF86EA8E49666503"
79 "      AE04B6BE81A2F8DD095311E0217ACA698A11E6C5D33CCDAE71498ED35D13991E"
80 "      B02F09AB40BD8F4C5ED8C75DA779D0AE104BC34C960B002377068AB4B5A1F984"
81 "      3FBA91F537F1B7CAC4D8DD6D89B0D863AF7025D549F9C765D2FC07EE208F8D15#)"
82 "  (y #64B11EF8871BE4AB572AA810D5D3CA11A6CDBC637A8014602C72960DB135BF46"
83 "      A1816A724C34F87330FC9E187C5D66897A04535CC2AC9164A7150ABFA8179827"
84 "      6E45831AB811EEE848EBB24D9F5F2883B6E5DDC4C659DEF944DCFD80BF4D0A20"
85 "      42CAA7DC289F0C5A9D155F02D3D551DB741A81695B74D4C8F477F9C7838EB0FB#)"
86 "  (x #11D54E4ADBD3034160F2CED4B7CD292A4EBF3EC0#)))";
87 /* A sample 1024 bit DSA key used for the selftests (public only).  */
88 static const char sample_public_key[] =
89 "(public-key"
90 " (dsa"
91 "  (p #00AD7C0025BA1A15F775F3F2D673718391D00456978D347B33D7B49E7F32EDAB"
92 "      96273899DD8B2BB46CD6ECA263FAF04A28903503D59062A8865D2AE8ADFB5191"
93 "      CF36FFB562D0E2F5809801A1F675DAE59698A9E01EFE8D7DCFCA084F4C6F5A44"
94 "      44D499A06FFAEA5E8EF5E01F2FD20A7B7EF3F6968AFBA1FB8D91F1559D52D8777B#)"
95 "  (q #00EB7B5751D25EBBB7BD59D920315FD840E19AEBF9#)"
96 "  (g #1574363387FDFD1DDF38F4FBE135BB20C7EE4772FB94C337AF86EA8E49666503"
97 "      AE04B6BE81A2F8DD095311E0217ACA698A11E6C5D33CCDAE71498ED35D13991E"
98 "      B02F09AB40BD8F4C5ED8C75DA779D0AE104BC34C960B002377068AB4B5A1F984"
99 "      3FBA91F537F1B7CAC4D8DD6D89B0D863AF7025D549F9C765D2FC07EE208F8D15#)"
100 "  (y #64B11EF8871BE4AB572AA810D5D3CA11A6CDBC637A8014602C72960DB135BF46"
101 "      A1816A724C34F87330FC9E187C5D66897A04535CC2AC9164A7150ABFA8179827"
102 "      6E45831AB811EEE848EBB24D9F5F2883B6E5DDC4C659DEF944DCFD80BF4D0A20"
103 "      42CAA7DC289F0C5A9D155F02D3D551DB741A81695B74D4C8F477F9C7838EB0FB#)))";
104
105
106
107 \f
108 static int test_keys (DSA_secret_key *sk, unsigned int qbits);
109 static int check_secret_key (DSA_secret_key *sk);
110 static gpg_err_code_t generate (DSA_secret_key *sk,
111                                 unsigned int nbits,
112                                 unsigned int qbits,
113                                 int transient_key,
114                                 dsa_domain_t *domain,
115                                 gcry_mpi_t **ret_factors);
116 static gpg_err_code_t sign (gcry_mpi_t r, gcry_mpi_t s, gcry_mpi_t input,
117                             DSA_secret_key *skey, int flags, int hashalgo);
118 static gpg_err_code_t verify (gcry_mpi_t r, gcry_mpi_t s, gcry_mpi_t input,
119                    DSA_public_key *pkey);
120 static unsigned int dsa_get_nbits (gcry_sexp_t parms);
121
122
123 static void (*progress_cb) (void *,const char *, int, int, int );
124 static void *progress_cb_data;
125
126
127 void
128 _gcry_register_pk_dsa_progress (void (*cb) (void *, const char *,
129                                             int, int, int),
130                                 void *cb_data)
131 {
132   progress_cb = cb;
133   progress_cb_data = cb_data;
134 }
135
136
137 static void
138 progress (int c)
139 {
140   if (progress_cb)
141     progress_cb (progress_cb_data, "pk_dsa", c, 0, 0);
142 }
143
144
145 /* Check that a freshly generated key actually works.  Returns 0 on success. */
146 static int
147 test_keys (DSA_secret_key *sk, unsigned int qbits)
148 {
149   int result = -1;  /* Default to failure.  */
150   DSA_public_key pk;
151   gcry_mpi_t data  = mpi_new (qbits);
152   gcry_mpi_t sig_a = mpi_new (qbits);
153   gcry_mpi_t sig_b = mpi_new (qbits);
154
155   /* Put the relevant parameters into a public key structure.  */
156   pk.p = sk->p;
157   pk.q = sk->q;
158   pk.g = sk->g;
159   pk.y = sk->y;
160
161   /* Create a random plaintext.  */
162   _gcry_mpi_randomize (data, qbits, GCRY_WEAK_RANDOM);
163
164   /* Sign DATA using the secret key.  */
165   sign (sig_a, sig_b, data, sk, 0, 0);
166
167   /* Verify the signature using the public key.  */
168   if ( verify (sig_a, sig_b, data, &pk) )
169     goto leave; /* Signature does not match.  */
170
171   /* Modify the data and check that the signing fails.  */
172   mpi_add_ui (data, data, 1);
173   if ( !verify (sig_a, sig_b, data, &pk) )
174     goto leave; /* Signature matches but should not.  */
175
176   result = 0; /* The test succeeded.  */
177
178  leave:
179   _gcry_mpi_release (sig_b);
180   _gcry_mpi_release (sig_a);
181   _gcry_mpi_release (data);
182   return result;
183 }
184
185
186
187 /*
188    Generate a DSA key pair with a key of size NBITS.  If transient_key
189    is true the key is generated using the standard RNG and not the
190    very secure one.
191
192    Returns: 2 structures filled with all needed values
193             and an array with the n-1 factors of (p-1)
194  */
195 static gpg_err_code_t
196 generate (DSA_secret_key *sk, unsigned int nbits, unsigned int qbits,
197           int transient_key, dsa_domain_t *domain, gcry_mpi_t **ret_factors )
198 {
199   gpg_err_code_t rc;
200   gcry_mpi_t p;    /* the prime */
201   gcry_mpi_t q;    /* the 160 bit prime factor */
202   gcry_mpi_t g;    /* the generator */
203   gcry_mpi_t y;    /* g^x mod p */
204   gcry_mpi_t x;    /* the secret exponent */
205   gcry_mpi_t h, e;  /* helper */
206   unsigned char *rndbuf;
207   gcry_random_level_t random_level;
208
209   if (qbits)
210     ; /* Caller supplied qbits.  Use this value.  */
211   else if ( nbits >= 512 && nbits <= 1024 )
212     qbits = 160;
213   else if ( nbits == 2048 )
214     qbits = 224;
215   else if ( nbits == 3072 )
216     qbits = 256;
217   else if ( nbits == 7680 )
218     qbits = 384;
219   else if ( nbits == 15360 )
220     qbits = 512;
221   else
222     return GPG_ERR_INV_VALUE;
223
224   if (qbits < 160 || qbits > 512 || (qbits%8) )
225     return GPG_ERR_INV_VALUE;
226   if (nbits < 2*qbits || nbits > 15360)
227     return GPG_ERR_INV_VALUE;
228
229   if (fips_mode ())
230     {
231       if (nbits < 1024)
232         return GPG_ERR_INV_VALUE;
233       if (transient_key)
234         return GPG_ERR_INV_VALUE;
235     }
236
237   if (domain->p && domain->q && domain->g)
238     {
239       /* Domain parameters are given; use them.  */
240       p = mpi_copy (domain->p);
241       q = mpi_copy (domain->q);
242       g = mpi_copy (domain->g);
243       gcry_assert (mpi_get_nbits (p) == nbits);
244       gcry_assert (mpi_get_nbits (q) == qbits);
245       h = mpi_alloc (0);
246       e = NULL;
247     }
248   else
249     {
250       /* Generate new domain parameters.  */
251       rc = _gcry_generate_elg_prime (1, nbits, qbits, NULL, &p, ret_factors);
252       if (rc)
253         return rc;
254
255       /* Get q out of factors.  */
256       q = mpi_copy ((*ret_factors)[0]);
257       gcry_assert (mpi_get_nbits (q) == qbits);
258
259       /* Find a generator g (h and e are helpers).
260          e = (p-1)/q */
261       e = mpi_alloc (mpi_get_nlimbs (p));
262       mpi_sub_ui (e, p, 1);
263       mpi_fdiv_q (e, e, q);
264       g = mpi_alloc (mpi_get_nlimbs (p));
265       h = mpi_alloc_set_ui (1); /* (We start with 2.) */
266       do
267         {
268           mpi_add_ui (h, h, 1);
269           /* g = h^e mod p */
270           mpi_powm (g, h, e, p);
271         }
272       while (!mpi_cmp_ui (g, 1));  /* Continue until g != 1. */
273     }
274
275   /* Select a random number X with the property:
276    *     0 < x < q-1
277    *
278    * FIXME: Why do we use the requirement x < q-1 ? It should be
279    * sufficient to test for x < q.  FIPS-186-3 check x < q-1 but it
280    * does not check for 0 < x because it makes sure that Q is unsigned
281    * and finally adds one to the result so that 0 will never be
282    * returned.  We should replace the code below with _gcry_dsa_gen_k.
283    *
284    * This must be a very good random number because this is the secret
285    * part.  The random quality depends on the transient_key flag.  */
286   random_level = transient_key ? GCRY_STRONG_RANDOM : GCRY_VERY_STRONG_RANDOM;
287   if (DBG_CIPHER)
288     log_debug("choosing a random x%s\n", transient_key? " (transient-key)":"");
289   gcry_assert( qbits >= 160 );
290   x = mpi_alloc_secure( mpi_get_nlimbs(q) );
291   mpi_sub_ui( h, q, 1 );  /* put q-1 into h */
292   rndbuf = NULL;
293   do
294     {
295       if( DBG_CIPHER )
296         progress('.');
297       if( !rndbuf )
298         rndbuf = _gcry_random_bytes_secure ((qbits+7)/8, random_level);
299       else
300         { /* Change only some of the higher bits (= 2 bytes)*/
301           char *r = _gcry_random_bytes_secure (2, random_level);
302           memcpy(rndbuf, r, 2 );
303           xfree(r);
304         }
305
306       _gcry_mpi_set_buffer( x, rndbuf, (qbits+7)/8, 0 );
307       mpi_clear_highbit( x, qbits+1 );
308     }
309   while ( !( mpi_cmp_ui( x, 0 )>0 && mpi_cmp( x, h )<0 ) );
310   xfree(rndbuf);
311   mpi_free( e );
312   mpi_free( h );
313
314   /* y = g^x mod p */
315   y = mpi_alloc( mpi_get_nlimbs(p) );
316   mpi_powm (y, g, x, p);
317
318   if( DBG_CIPHER )
319     {
320       progress('\n');
321       log_mpidump("dsa  p", p );
322       log_mpidump("dsa  q", q );
323       log_mpidump("dsa  g", g );
324       log_mpidump("dsa  y", y );
325       log_mpidump("dsa  x", x );
326     }
327
328   /* Copy the stuff to the key structures. */
329   sk->p = p;
330   sk->q = q;
331   sk->g = g;
332   sk->y = y;
333   sk->x = x;
334
335   /* Now we can test our keys (this should never fail!). */
336   if ( test_keys (sk, qbits) )
337     {
338       _gcry_mpi_release (sk->p); sk->p = NULL;
339       _gcry_mpi_release (sk->q); sk->q = NULL;
340       _gcry_mpi_release (sk->g); sk->g = NULL;
341       _gcry_mpi_release (sk->y); sk->y = NULL;
342       _gcry_mpi_release (sk->x); sk->x = NULL;
343       fips_signal_error ("self-test after key generation failed");
344       return GPG_ERR_SELFTEST_FAILED;
345     }
346   return 0;
347 }
348
349
350 /* Generate a DSA key pair with a key of size NBITS using the
351    algorithm given in FIPS-186-3.  If USE_FIPS186_2 is true,
352    FIPS-186-2 is used and thus the length is restricted to 1024/160.
353    If DERIVEPARMS is not NULL it may contain a seed value.  If domain
354    parameters are specified in DOMAIN, DERIVEPARMS may not be given
355    and NBITS and QBITS must match the specified domain parameters.  */
356 static gpg_err_code_t
357 generate_fips186 (DSA_secret_key *sk, unsigned int nbits, unsigned int qbits,
358                   gcry_sexp_t deriveparms, int use_fips186_2,
359                   dsa_domain_t *domain,
360                   int *r_counter, void **r_seed, size_t *r_seedlen,
361                   gcry_mpi_t *r_h)
362 {
363   gpg_err_code_t ec;
364   struct {
365     gcry_sexp_t sexp;
366     const void *seed;
367     size_t seedlen;
368   } initial_seed = { NULL, NULL, 0 };
369   gcry_mpi_t prime_q = NULL;
370   gcry_mpi_t prime_p = NULL;
371   gcry_mpi_t value_g = NULL; /* The generator. */
372   gcry_mpi_t value_y = NULL; /* g^x mod p */
373   gcry_mpi_t value_x = NULL; /* The secret exponent. */
374   gcry_mpi_t value_h = NULL; /* Helper.  */
375   gcry_mpi_t value_e = NULL; /* Helper.  */
376
377   /* Preset return values.  */
378   *r_counter = 0;
379   *r_seed = NULL;
380   *r_seedlen = 0;
381   *r_h = NULL;
382
383   /* Derive QBITS from NBITS if requested  */
384   if (!qbits)
385     {
386       if (nbits == 1024)
387         qbits = 160;
388       else if (nbits == 2048)
389         qbits = 224;
390       else if (nbits == 3072)
391         qbits = 256;
392     }
393
394   /* Check that QBITS and NBITS match the standard.  Note that FIPS
395      186-3 uses N for QBITS and L for NBITS.  */
396   if (nbits == 1024 && qbits == 160)
397     ;
398   else if (nbits == 2048 && qbits == 224)
399     ;
400   else if (nbits == 2048 && qbits == 256)
401     ;
402   else if (nbits == 3072 && qbits == 256)
403     ;
404   else
405     return GPG_ERR_INV_VALUE;
406
407   if (domain->p && domain->q && domain->g)
408     {
409       /* Domain parameters are given; use them.  */
410       prime_p = mpi_copy (domain->p);
411       prime_q = mpi_copy (domain->q);
412       value_g = mpi_copy (domain->g);
413       gcry_assert (mpi_get_nbits (prime_p) == nbits);
414       gcry_assert (mpi_get_nbits (prime_q) == qbits);
415       gcry_assert (!deriveparms);
416       ec = 0;
417     }
418   else
419     {
420       /* Generate new domain parameters.  */
421
422       /* Get an initial seed value.  */
423       if (deriveparms)
424         {
425           initial_seed.sexp = sexp_find_token (deriveparms, "seed", 0);
426           if (initial_seed.sexp)
427             initial_seed.seed = sexp_nth_data (initial_seed.sexp, 1,
428                                                     &initial_seed.seedlen);
429         }
430
431       /* Fixme: Enable 186-3 after it has been approved and after fixing
432          the generation function.  */
433       /*   if (use_fips186_2) */
434       (void)use_fips186_2;
435       ec = _gcry_generate_fips186_2_prime (nbits, qbits,
436                                            initial_seed.seed,
437                                            initial_seed.seedlen,
438                                            &prime_q, &prime_p,
439                                            r_counter,
440                                            r_seed, r_seedlen);
441       /*   else */
442       /*     ec = _gcry_generate_fips186_3_prime (nbits, qbits, NULL, 0, */
443       /*                                          &prime_q, &prime_p, */
444       /*                                          r_counter, */
445       /*                                          r_seed, r_seedlen, NULL); */
446       sexp_release (initial_seed.sexp);
447       if (ec)
448         goto leave;
449
450       /* Find a generator g (h and e are helpers).
451          e = (p-1)/q */
452       value_e = mpi_alloc_like (prime_p);
453       mpi_sub_ui (value_e, prime_p, 1);
454       mpi_fdiv_q (value_e, value_e, prime_q );
455       value_g = mpi_alloc_like (prime_p);
456       value_h = mpi_alloc_set_ui (1);
457       do
458         {
459           mpi_add_ui (value_h, value_h, 1);
460           /* g = h^e mod p */
461           mpi_powm (value_g, value_h, value_e, prime_p);
462         }
463       while (!mpi_cmp_ui (value_g, 1));  /* Continue until g != 1.  */
464     }
465
466
467   /* Select a random number x with:  0 < x < q  */
468   value_x = mpi_snew (qbits);
469   do
470     {
471       if( DBG_CIPHER )
472         progress('.');
473       _gcry_mpi_randomize (value_x, qbits, GCRY_VERY_STRONG_RANDOM);
474       mpi_clear_highbit (value_x, qbits+1);
475     }
476   while (!(mpi_cmp_ui (value_x, 0) > 0 && mpi_cmp (value_x, prime_q) < 0));
477
478   /* y = g^x mod p */
479   value_y = mpi_alloc_like (prime_p);
480   mpi_powm (value_y, value_g, value_x, prime_p);
481
482   if (DBG_CIPHER)
483     {
484       progress('\n');
485       log_mpidump("dsa  p", prime_p );
486       log_mpidump("dsa  q", prime_q );
487       log_mpidump("dsa  g", value_g );
488       log_mpidump("dsa  y", value_y );
489       log_mpidump("dsa  x", value_x );
490       log_mpidump("dsa  h", value_h );
491     }
492
493   /* Copy the stuff to the key structures. */
494   sk->p = prime_p; prime_p = NULL;
495   sk->q = prime_q; prime_q = NULL;
496   sk->g = value_g; value_g = NULL;
497   sk->y = value_y; value_y = NULL;
498   sk->x = value_x; value_x = NULL;
499   *r_h = value_h; value_h = NULL;
500
501  leave:
502   _gcry_mpi_release (prime_p);
503   _gcry_mpi_release (prime_q);
504   _gcry_mpi_release (value_g);
505   _gcry_mpi_release (value_y);
506   _gcry_mpi_release (value_x);
507   _gcry_mpi_release (value_h);
508   _gcry_mpi_release (value_e);
509
510   /* As a last step test this keys (this should never fail of course). */
511   if (!ec && test_keys (sk, qbits) )
512     {
513       _gcry_mpi_release (sk->p); sk->p = NULL;
514       _gcry_mpi_release (sk->q); sk->q = NULL;
515       _gcry_mpi_release (sk->g); sk->g = NULL;
516       _gcry_mpi_release (sk->y); sk->y = NULL;
517       _gcry_mpi_release (sk->x); sk->x = NULL;
518       fips_signal_error ("self-test after key generation failed");
519       ec = GPG_ERR_SELFTEST_FAILED;
520     }
521
522   if (ec)
523     {
524       *r_counter = 0;
525       xfree (*r_seed); *r_seed = NULL;
526       *r_seedlen = 0;
527       _gcry_mpi_release (*r_h); *r_h = NULL;
528     }
529
530   return ec;
531 }
532
533
534
535 /*
536    Test whether the secret key is valid.
537    Returns: if this is a valid key.
538  */
539 static int
540 check_secret_key( DSA_secret_key *sk )
541 {
542   int rc;
543   gcry_mpi_t y = mpi_alloc( mpi_get_nlimbs(sk->y) );
544
545   mpi_powm( y, sk->g, sk->x, sk->p );
546   rc = !mpi_cmp( y, sk->y );
547   mpi_free( y );
548   return rc;
549 }
550
551
552
553 /*
554    Make a DSA signature from INPUT and put it into r and s.
555
556    INPUT may either be a plain MPI or an opaque MPI which is then
557    internally converted to a plain MPI.  FLAGS and HASHALGO may both
558    be 0 for standard operation mode.
559
560    The return value is 0 on success or an error code.  Note that for
561    backward compatibility the function will not return any error if
562    FLAGS and HASHALGO are both 0 and INPUT is a plain MPI.
563  */
564 static gpg_err_code_t
565 sign (gcry_mpi_t r, gcry_mpi_t s, gcry_mpi_t input, DSA_secret_key *skey,
566       int flags, int hashalgo)
567 {
568   gpg_err_code_t rc;
569   gcry_mpi_t hash;
570   gcry_mpi_t k;
571   gcry_mpi_t kinv;
572   gcry_mpi_t tmp;
573   const void *abuf;
574   unsigned int abits, qbits;
575   int extraloops = 0;
576
577   qbits = mpi_get_nbits (skey->q);
578
579   /* Convert the INPUT into an MPI.  */
580   rc = _gcry_dsa_normalize_hash (input, &hash, qbits);
581   if (rc)
582     return rc;
583
584  again:
585   /* Create the K value.  */
586   if ((flags & PUBKEY_FLAG_RFC6979) && hashalgo)
587     {
588       /* Use Pornin's method for deterministic DSA.  If this flag is
589          set, it is expected that HASH is an opaque MPI with the to be
590          signed hash.  That hash is also used as h1 from 3.2.a.  */
591       if (!mpi_is_opaque (input))
592         {
593           rc = GPG_ERR_CONFLICT;
594           goto leave;
595         }
596
597       abuf = mpi_get_opaque (input, &abits);
598       rc = _gcry_dsa_gen_rfc6979_k (&k, skey->q, skey->x,
599                                     abuf, (abits+7)/8, hashalgo, extraloops);
600       if (rc)
601         goto leave;
602     }
603   else
604     {
605       /* Select a random k with 0 < k < q */
606       k = _gcry_dsa_gen_k (skey->q, GCRY_STRONG_RANDOM);
607     }
608
609   /* r = (a^k mod p) mod q */
610   mpi_powm( r, skey->g, k, skey->p );
611   mpi_fdiv_r( r, r, skey->q );
612
613   /* kinv = k^(-1) mod q */
614   kinv = mpi_alloc( mpi_get_nlimbs(k) );
615   mpi_invm(kinv, k, skey->q );
616
617   /* s = (kinv * ( hash + x * r)) mod q */
618   tmp = mpi_alloc( mpi_get_nlimbs(skey->p) );
619   mpi_mul( tmp, skey->x, r );
620   mpi_add( tmp, tmp, hash );
621   mpi_mulm( s , kinv, tmp, skey->q );
622
623   mpi_free(k);
624   mpi_free(kinv);
625   mpi_free(tmp);
626
627   if (!mpi_cmp_ui (r, 0))
628     {
629       /* This is a highly unlikely code path.  */
630       extraloops++;
631       goto again;
632     }
633
634   rc = 0;
635
636  leave:
637   if (hash != input)
638     mpi_free (hash);
639
640   return rc;
641 }
642
643
644 /*
645    Returns true if the signature composed from R and S is valid.
646  */
647 static gpg_err_code_t
648 verify (gcry_mpi_t r, gcry_mpi_t s, gcry_mpi_t input, DSA_public_key *pkey )
649 {
650   gpg_err_code_t rc = 0;
651   gcry_mpi_t w, u1, u2, v;
652   gcry_mpi_t base[3];
653   gcry_mpi_t ex[3];
654   gcry_mpi_t hash;
655   unsigned int nbits;
656
657   if( !(mpi_cmp_ui( r, 0 ) > 0 && mpi_cmp( r, pkey->q ) < 0) )
658     return GPG_ERR_BAD_SIGNATURE; /* Assertion  0 < r < n  failed.  */
659   if( !(mpi_cmp_ui( s, 0 ) > 0 && mpi_cmp( s, pkey->q ) < 0) )
660     return GPG_ERR_BAD_SIGNATURE; /* Assertion  0 < s < n  failed.  */
661
662   nbits = mpi_get_nbits (pkey->q);
663   rc = _gcry_dsa_normalize_hash (input, &hash, nbits);
664   if (rc)
665     return rc;
666
667   w  = mpi_alloc( mpi_get_nlimbs(pkey->q) );
668   u1 = mpi_alloc( mpi_get_nlimbs(pkey->q) );
669   u2 = mpi_alloc( mpi_get_nlimbs(pkey->q) );
670   v  = mpi_alloc( mpi_get_nlimbs(pkey->p) );
671
672   /* w = s^(-1) mod q */
673   mpi_invm( w, s, pkey->q );
674
675   /* u1 = (hash * w) mod q */
676   mpi_mulm( u1, hash, w, pkey->q );
677
678   /* u2 = r * w mod q  */
679   mpi_mulm( u2, r, w, pkey->q );
680
681   /* v =  g^u1 * y^u2 mod p mod q */
682   base[0] = pkey->g; ex[0] = u1;
683   base[1] = pkey->y; ex[1] = u2;
684   base[2] = NULL;    ex[2] = NULL;
685   mpi_mulpowm( v, base, ex, pkey->p );
686   mpi_fdiv_r( v, v, pkey->q );
687
688   if (mpi_cmp( v, r ))
689     {
690       if (DBG_CIPHER)
691         {
692           log_mpidump ("     i", input);
693           log_mpidump ("     h", hash);
694           log_mpidump ("     v", v);
695           log_mpidump ("     r", r);
696           log_mpidump ("     s", s);
697         }
698       rc = GPG_ERR_BAD_SIGNATURE;
699     }
700
701   mpi_free(w);
702   mpi_free(u1);
703   mpi_free(u2);
704   mpi_free(v);
705   if (hash != input)
706     mpi_free (hash);
707
708   return rc;
709 }
710
711
712 /*********************************************
713  **************  interface  ******************
714  *********************************************/
715
716 static gcry_err_code_t
717 dsa_generate (const gcry_sexp_t genparms, gcry_sexp_t *r_skey)
718 {
719   gpg_err_code_t rc;
720   unsigned int nbits;
721   gcry_sexp_t domainsexp;
722   DSA_secret_key sk;
723   gcry_sexp_t l1;
724   unsigned int qbits = 0;
725   gcry_sexp_t deriveparms = NULL;
726   gcry_sexp_t seedinfo = NULL;
727   gcry_sexp_t misc_info = NULL;
728   int flags = 0;
729   dsa_domain_t domain;
730   gcry_mpi_t *factors = NULL;
731
732   memset (&sk, 0, sizeof sk);
733   memset (&domain, 0, sizeof domain);
734
735   rc = _gcry_pk_util_get_nbits (genparms, &nbits);
736   if (rc)
737     return rc;
738
739   /* Parse the optional flags list.  */
740   l1 = sexp_find_token (genparms, "flags", 0);
741   if (l1)
742     {
743       rc = _gcry_pk_util_parse_flaglist (l1, &flags, NULL);
744       sexp_release (l1);
745       if (rc)
746         return rc;\
747     }
748
749   /* Parse the optional qbits element.  */
750   l1 = sexp_find_token (genparms, "qbits", 0);
751   if (l1)
752     {
753       char buf[50];
754       const char *s;
755       size_t n;
756
757       s = sexp_nth_data (l1, 1, &n);
758       if (!s || n >= DIM (buf) - 1 )
759         {
760           sexp_release (l1);
761           return GPG_ERR_INV_OBJ; /* No value or value too large.  */
762         }
763       memcpy (buf, s, n);
764       buf[n] = 0;
765       qbits = (unsigned int)strtoul (buf, NULL, 0);
766       sexp_release (l1);
767     }
768
769   /* Parse the optional transient-key flag.  */
770   if (!(flags & PUBKEY_FLAG_TRANSIENT_KEY))
771     {
772       l1 = sexp_find_token (genparms, "transient-key", 0);
773       if (l1)
774         {
775           flags |= PUBKEY_FLAG_TRANSIENT_KEY;
776           sexp_release (l1);
777         }
778     }
779
780   /* Get the optional derive parameters.  */
781   deriveparms = sexp_find_token (genparms, "derive-parms", 0);
782
783   /* Parse the optional "use-fips186" flags.  */
784   if (!(flags & PUBKEY_FLAG_USE_FIPS186))
785     {
786       l1 = sexp_find_token (genparms, "use-fips186", 0);
787       if (l1)
788         {
789           flags |= PUBKEY_FLAG_USE_FIPS186;
790           sexp_release (l1);
791         }
792     }
793   if (!(flags & PUBKEY_FLAG_USE_FIPS186_2))
794     {
795       l1 = sexp_find_token (genparms, "use-fips186-2", 0);
796       if (l1)
797         {
798           flags |= PUBKEY_FLAG_USE_FIPS186_2;
799           sexp_release (l1);
800         }
801     }
802
803   /* Check whether domain parameters are given.  */
804   domainsexp = sexp_find_token (genparms, "domain", 0);
805   if (domainsexp)
806     {
807       /* DERIVEPARMS can't be used together with domain parameters.
808          NBITS abnd QBITS may not be specified because there values
809          are derived from the domain parameters.  */
810       if (deriveparms || qbits || nbits)
811         {
812           sexp_release (domainsexp);
813           sexp_release (deriveparms);
814           return GPG_ERR_INV_VALUE;
815         }
816
817       /* Put all domain parameters into the domain object.  */
818       l1 = sexp_find_token (domainsexp, "p", 0);
819       domain.p = sexp_nth_mpi (l1, 1, GCRYMPI_FMT_USG);
820       sexp_release (l1);
821       l1 = sexp_find_token (domainsexp, "q", 0);
822       domain.q = sexp_nth_mpi (l1, 1, GCRYMPI_FMT_USG);
823       sexp_release (l1);
824       l1 = sexp_find_token (domainsexp, "g", 0);
825       domain.g = sexp_nth_mpi (l1, 1, GCRYMPI_FMT_USG);
826       sexp_release (l1);
827       sexp_release (domainsexp);
828
829       /* Check that all domain parameters are available.  */
830       if (!domain.p || !domain.q || !domain.g)
831         {
832           _gcry_mpi_release (domain.p);
833           _gcry_mpi_release (domain.q);
834           _gcry_mpi_release (domain.g);
835           sexp_release (deriveparms);
836           return GPG_ERR_MISSING_VALUE;
837         }
838
839       /* Get NBITS and QBITS from the domain parameters.  */
840       nbits = mpi_get_nbits (domain.p);
841       qbits = mpi_get_nbits (domain.q);
842     }
843
844   if (deriveparms
845       || (flags & PUBKEY_FLAG_USE_FIPS186)
846       || (flags & PUBKEY_FLAG_USE_FIPS186_2)
847       || fips_mode ())
848     {
849       int counter;
850       void *seed;
851       size_t seedlen;
852       gcry_mpi_t h_value;
853
854       rc = generate_fips186 (&sk, nbits, qbits, deriveparms,
855                              !!(flags & PUBKEY_FLAG_USE_FIPS186_2),
856                              &domain,
857                              &counter, &seed, &seedlen, &h_value);
858       if (!rc && h_value)
859         {
860           /* Format the seed-values unless domain parameters are used
861              for which a H_VALUE of NULL is an indication.  */
862           rc = sexp_build (&seedinfo, NULL,
863                            "(seed-values(counter %d)(seed %b)(h %m))",
864                            counter, (int)seedlen, seed, h_value);
865           xfree (seed);
866           _gcry_mpi_release (h_value);
867         }
868     }
869   else
870     {
871       rc = generate (&sk, nbits, qbits,
872                      !!(flags & PUBKEY_FLAG_TRANSIENT_KEY),
873                      &domain, &factors);
874     }
875
876   if (!rc)
877     {
878       /* Put the factors into MISC_INFO.  Note that the factors are
879          not confidential thus we can store them in standard memory.  */
880       int nfactors, i, j;
881       char *p;
882       char *format = NULL;
883       void **arg_list = NULL;
884
885       for (nfactors=0; factors && factors[nfactors]; nfactors++)
886         ;
887       /* Allocate space for the format string:
888          "(misc-key-info%S(pm1-factors%m))"
889          with one "%m" for each factor and construct it.  */
890       format = xtrymalloc (50 + 2*nfactors);
891       if (!format)
892         rc = gpg_err_code_from_syserror ();
893       else
894         {
895           p = stpcpy (format, "(misc-key-info");
896           if (seedinfo)
897             p = stpcpy (p, "%S");
898           if (nfactors)
899             {
900               p = stpcpy (p, "(pm1-factors");
901               for (i=0; i < nfactors; i++)
902                 p = stpcpy (p, "%m");
903               p = stpcpy (p, ")");
904             }
905           p = stpcpy (p, ")");
906
907           /* Allocate space for the list of factors plus one for the
908              seedinfo s-exp plus an extra NULL entry for safety and
909              fill it with the factors.  */
910           arg_list = xtrycalloc (nfactors+1+1, sizeof *arg_list);
911           if (!arg_list)
912             rc = gpg_err_code_from_syserror ();
913           else
914             {
915               i = 0;
916               if (seedinfo)
917                 arg_list[i++] = &seedinfo;
918               for (j=0; j < nfactors; j++)
919                 arg_list[i++] = factors + j;
920               arg_list[i] = NULL;
921
922               rc = sexp_build_array (&misc_info, NULL, format, arg_list);
923             }
924         }
925
926       xfree (arg_list);
927       xfree (format);
928     }
929
930   if (!rc)
931     rc = sexp_build (r_skey, NULL,
932                      "(key-data"
933                      " (public-key"
934                      "  (dsa(p%m)(q%m)(g%m)(y%m)))"
935                      " (private-key"
936                      "  (dsa(p%m)(q%m)(g%m)(y%m)(x%m)))"
937                      " %S)",
938                      sk.p, sk.q, sk.g, sk.y,
939                      sk.p, sk.q, sk.g, sk.y, sk.x,
940                      misc_info);
941
942
943   _gcry_mpi_release (sk.p);
944   _gcry_mpi_release (sk.q);
945   _gcry_mpi_release (sk.g);
946   _gcry_mpi_release (sk.y);
947   _gcry_mpi_release (sk.x);
948
949   _gcry_mpi_release (domain.p);
950   _gcry_mpi_release (domain.q);
951   _gcry_mpi_release (domain.g);
952
953   sexp_release (seedinfo);
954   sexp_release (misc_info);
955   sexp_release (deriveparms);
956   if (factors)
957     {
958       gcry_mpi_t *mp;
959       for (mp = factors; *mp; mp++)
960         mpi_free (*mp);
961       xfree (factors);
962     }
963   return rc;
964 }
965
966
967
968 static gcry_err_code_t
969 dsa_check_secret_key (gcry_sexp_t keyparms)
970 {
971   gcry_err_code_t rc;
972   DSA_secret_key sk = {NULL, NULL, NULL, NULL, NULL};
973
974   rc = _gcry_sexp_extract_param (keyparms, NULL, "pqgyx",
975                                  &sk.p, &sk.q, &sk.g, &sk.y, &sk.x,
976                                  NULL);
977   if (rc)
978     goto leave;
979
980   if (!check_secret_key (&sk))
981     rc = GPG_ERR_BAD_SECKEY;
982
983  leave:
984   _gcry_mpi_release (sk.p);
985   _gcry_mpi_release (sk.q);
986   _gcry_mpi_release (sk.g);
987   _gcry_mpi_release (sk.y);
988   _gcry_mpi_release (sk.x);
989   if (DBG_CIPHER)
990     log_debug ("dsa_testkey    => %s\n", gpg_strerror (rc));
991   return rc;
992 }
993
994
995 static gcry_err_code_t
996 dsa_sign (gcry_sexp_t *r_sig, gcry_sexp_t s_data, gcry_sexp_t keyparms)
997 {
998   gcry_err_code_t rc;
999   struct pk_encoding_ctx ctx;
1000   gcry_mpi_t data = NULL;
1001   DSA_secret_key sk = {NULL, NULL, NULL, NULL, NULL};
1002   gcry_mpi_t sig_r = NULL;
1003   gcry_mpi_t sig_s = NULL;
1004
1005   _gcry_pk_util_init_encoding_ctx (&ctx, PUBKEY_OP_SIGN,
1006                                    dsa_get_nbits (keyparms));
1007
1008   /* Extract the data.  */
1009   rc = _gcry_pk_util_data_to_mpi (s_data, &data, &ctx);
1010   if (rc)
1011     goto leave;
1012   if (DBG_CIPHER)
1013     log_mpidump ("dsa_sign   data", data);
1014
1015   /* Extract the key.  */
1016   rc = _gcry_sexp_extract_param (keyparms, NULL, "pqgyx",
1017                                  &sk.p, &sk.q, &sk.g, &sk.y, &sk.x, NULL);
1018   if (rc)
1019     goto leave;
1020   if (DBG_CIPHER)
1021     {
1022       log_mpidump ("dsa_sign      p", sk.p);
1023       log_mpidump ("dsa_sign      q", sk.q);
1024       log_mpidump ("dsa_sign      g", sk.g);
1025       log_mpidump ("dsa_sign      y", sk.y);
1026       if (!fips_mode ())
1027         log_mpidump ("dsa_sign      x", sk.x);
1028     }
1029
1030   sig_r = mpi_new (0);
1031   sig_s = mpi_new (0);
1032   rc = sign (sig_r, sig_s, data, &sk, ctx.flags, ctx.hash_algo);
1033   if (rc)
1034     goto leave;
1035   if (DBG_CIPHER)
1036     {
1037       log_mpidump ("dsa_sign  sig_r", sig_r);
1038       log_mpidump ("dsa_sign  sig_s", sig_s);
1039     }
1040   rc = sexp_build (r_sig, NULL, "(sig-val(dsa(r%M)(s%M)))", sig_r, sig_s);
1041
1042  leave:
1043   _gcry_mpi_release (sig_r);
1044   _gcry_mpi_release (sig_s);
1045   _gcry_mpi_release (sk.p);
1046   _gcry_mpi_release (sk.q);
1047   _gcry_mpi_release (sk.g);
1048   _gcry_mpi_release (sk.y);
1049   _gcry_mpi_release (sk.x);
1050   _gcry_mpi_release (data);
1051   _gcry_pk_util_free_encoding_ctx (&ctx);
1052   if (DBG_CIPHER)
1053     log_debug ("dsa_sign      => %s\n", gpg_strerror (rc));
1054   return rc;
1055 }
1056
1057
1058 static gcry_err_code_t
1059 dsa_verify (gcry_sexp_t s_sig, gcry_sexp_t s_data, gcry_sexp_t s_keyparms)
1060 {
1061   gcry_err_code_t rc;
1062   struct pk_encoding_ctx ctx;
1063   gcry_sexp_t l1 = NULL;
1064   gcry_mpi_t sig_r = NULL;
1065   gcry_mpi_t sig_s = NULL;
1066   gcry_mpi_t data = NULL;
1067   DSA_public_key pk = { NULL, NULL, NULL, NULL };
1068
1069   _gcry_pk_util_init_encoding_ctx (&ctx, PUBKEY_OP_VERIFY,
1070                                    dsa_get_nbits (s_keyparms));
1071
1072   /* Extract the data.  */
1073   rc = _gcry_pk_util_data_to_mpi (s_data, &data, &ctx);
1074   if (rc)
1075     goto leave;
1076   if (DBG_CIPHER)
1077     log_mpidump ("dsa_verify data", data);
1078
1079   /* Extract the signature value.  */
1080   rc = _gcry_pk_util_preparse_sigval (s_sig, dsa_names, &l1, NULL);
1081   if (rc)
1082     goto leave;
1083   rc = _gcry_sexp_extract_param (l1, NULL, "rs", &sig_r, &sig_s, NULL);
1084   if (rc)
1085     goto leave;
1086   if (DBG_CIPHER)
1087     {
1088       log_mpidump ("dsa_verify  s_r", sig_r);
1089       log_mpidump ("dsa_verify  s_s", sig_s);
1090     }
1091
1092   /* Extract the key.  */
1093   rc = _gcry_sexp_extract_param (s_keyparms, NULL, "pqgy",
1094                                  &pk.p, &pk.q, &pk.g, &pk.y, NULL);
1095   if (rc)
1096     goto leave;
1097   if (DBG_CIPHER)
1098     {
1099       log_mpidump ("dsa_verify    p", pk.p);
1100       log_mpidump ("dsa_verify    q", pk.q);
1101       log_mpidump ("dsa_verify    g", pk.g);
1102       log_mpidump ("dsa_verify    y", pk.y);
1103     }
1104
1105   /* Verify the signature.  */
1106   rc = verify (sig_r, sig_s, data, &pk);
1107
1108  leave:
1109   _gcry_mpi_release (pk.p);
1110   _gcry_mpi_release (pk.q);
1111   _gcry_mpi_release (pk.g);
1112   _gcry_mpi_release (pk.y);
1113   _gcry_mpi_release (data);
1114   _gcry_mpi_release (sig_r);
1115   _gcry_mpi_release (sig_s);
1116   sexp_release (l1);
1117   _gcry_pk_util_free_encoding_ctx (&ctx);
1118   if (DBG_CIPHER)
1119     log_debug ("dsa_verify    => %s\n", rc?gpg_strerror (rc):"Good");
1120   return rc;
1121 }
1122
1123
1124 /* Return the number of bits for the key described by PARMS.  On error
1125  * 0 is returned.  The format of PARMS starts with the algorithm name;
1126  * for example:
1127  *
1128  *   (dsa
1129  *     (p <mpi>)
1130  *     (q <mpi>)
1131  *     (g <mpi>)
1132  *     (y <mpi>))
1133  *
1134  * More parameters may be given but we only need P here.
1135  */
1136 static unsigned int
1137 dsa_get_nbits (gcry_sexp_t parms)
1138 {
1139   gcry_sexp_t l1;
1140   gcry_mpi_t p;
1141   unsigned int nbits;
1142
1143   l1 = sexp_find_token (parms, "p", 1);
1144   if (!l1)
1145     return 0; /* Parameter P not found.  */
1146
1147   p = sexp_nth_mpi (l1, 1, GCRYMPI_FMT_USG);
1148   sexp_release (l1);
1149   nbits = p? mpi_get_nbits (p) : 0;
1150   _gcry_mpi_release (p);
1151   return nbits;
1152 }
1153
1154
1155 \f
1156 /*
1157      Self-test section.
1158  */
1159
1160 static const char *
1161 selftest_sign_1024 (gcry_sexp_t pkey, gcry_sexp_t skey)
1162 {
1163   static const char sample_data[] =
1164     "(data (flags raw)"
1165     " (value #a0b1c2d3e4f500102030405060708090a1b2c3d4#))";
1166   static const char sample_data_bad[] =
1167     "(data (flags raw)"
1168     " (value #a0b1c2d3e4f510102030405060708090a1b2c3d4#))";
1169
1170   const char *errtxt = NULL;
1171   gcry_error_t err;
1172   gcry_sexp_t data = NULL;
1173   gcry_sexp_t data_bad = NULL;
1174   gcry_sexp_t sig = NULL;
1175
1176   err = sexp_sscan (&data, NULL, sample_data, strlen (sample_data));
1177   if (!err)
1178     err = sexp_sscan (&data_bad, NULL,
1179                       sample_data_bad, strlen (sample_data_bad));
1180   if (err)
1181     {
1182       errtxt = "converting data failed";
1183       goto leave;
1184     }
1185
1186   err = _gcry_pk_sign (&sig, data, skey);
1187   if (err)
1188     {
1189       errtxt = "signing failed";
1190       goto leave;
1191     }
1192   err = _gcry_pk_verify (sig, data, pkey);
1193   if (err)
1194     {
1195       errtxt = "verify failed";
1196       goto leave;
1197     }
1198   err = _gcry_pk_verify (sig, data_bad, pkey);
1199   if (gcry_err_code (err) != GPG_ERR_BAD_SIGNATURE)
1200     {
1201       errtxt = "bad signature not detected";
1202       goto leave;
1203     }
1204
1205
1206  leave:
1207   sexp_release (sig);
1208   sexp_release (data_bad);
1209   sexp_release (data);
1210   return errtxt;
1211 }
1212
1213
1214 static gpg_err_code_t
1215 selftests_dsa (selftest_report_func_t report)
1216 {
1217   const char *what;
1218   const char *errtxt;
1219   gcry_error_t err;
1220   gcry_sexp_t skey = NULL;
1221   gcry_sexp_t pkey = NULL;
1222
1223   /* Convert the S-expressions into the internal representation.  */
1224   what = "convert";
1225   err = sexp_sscan (&skey, NULL, sample_secret_key, strlen (sample_secret_key));
1226   if (!err)
1227     err = sexp_sscan (&pkey, NULL,
1228                       sample_public_key, strlen (sample_public_key));
1229   if (err)
1230     {
1231       errtxt = _gcry_strerror (err);
1232       goto failed;
1233     }
1234
1235   what = "key consistency";
1236   err = _gcry_pk_testkey (skey);
1237   if (err)
1238     {
1239       errtxt = _gcry_strerror (err);
1240       goto failed;
1241     }
1242
1243   what = "sign";
1244   errtxt = selftest_sign_1024 (pkey, skey);
1245   if (errtxt)
1246     goto failed;
1247
1248   sexp_release (pkey);
1249   sexp_release (skey);
1250   return 0; /* Succeeded. */
1251
1252  failed:
1253   sexp_release (pkey);
1254   sexp_release (skey);
1255   if (report)
1256     report ("pubkey", GCRY_PK_DSA, what, errtxt);
1257   return GPG_ERR_SELFTEST_FAILED;
1258 }
1259
1260
1261 /* Run a full self-test for ALGO and return 0 on success.  */
1262 static gpg_err_code_t
1263 run_selftests (int algo, int extended, selftest_report_func_t report)
1264 {
1265   gpg_err_code_t ec;
1266
1267   (void)extended;
1268
1269   switch (algo)
1270     {
1271     case GCRY_PK_DSA:
1272       ec = selftests_dsa (report);
1273       break;
1274     default:
1275       ec = GPG_ERR_PUBKEY_ALGO;
1276       break;
1277
1278     }
1279   return ec;
1280 }
1281
1282
1283
1284 \f
1285 gcry_pk_spec_t _gcry_pubkey_spec_dsa =
1286   {
1287     GCRY_PK_DSA, { 0, 1 },
1288     GCRY_PK_USAGE_SIGN,
1289     "DSA", dsa_names,
1290     "pqgy", "pqgyx", "", "rs", "pqgy",
1291     dsa_generate,
1292     dsa_check_secret_key,
1293     NULL,
1294     NULL,
1295     dsa_sign,
1296     dsa_verify,
1297     dsa_get_nbits,
1298     run_selftests
1299   };