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