pubkey: Move sexp parsing of remaining fucntions to the modules.
[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 int 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  = gcry_mpi_new (qbits);
152   gcry_mpi_t sig_a = gcry_mpi_new (qbits);
153   gcry_mpi_t sig_b = gcry_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   gcry_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           gcry_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           gcry_free(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   gcry_free(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   gcry_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 = gcry_sexp_find_token (deriveparms, "seed", 0);
422           if (initial_seed.sexp)
423             initial_seed.seed = gcry_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       gcry_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 = gcry_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   gcry_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       gcry_free (*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   gcry_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   if (mpi_is_opaque (input))
577     {
578       abuf = gcry_mpi_get_opaque (input, &abits);
579       rc = gpg_err_code (gcry_mpi_scan (&hash, GCRYMPI_FMT_USG,
580                                         abuf, (abits+7)/8, NULL));
581       if (rc)
582         return rc;
583       if (abits > qbits)
584         gcry_mpi_rshift (hash, hash, abits - qbits);
585     }
586   else
587     hash = input;
588
589  again:
590   /* Create the K value.  */
591   if ((flags & PUBKEY_FLAG_RFC6979) && hashalgo)
592     {
593       /* Use Pornin's method for deterministic DSA.  If this flag is
594          set, it is expected that HASH is an opaque MPI with the to be
595          signed hash.  That hash is also used as h1 from 3.2.a.  */
596       if (!mpi_is_opaque (input))
597         {
598           rc = GPG_ERR_CONFLICT;
599           goto leave;
600         }
601
602       abuf = gcry_mpi_get_opaque (input, &abits);
603       rc = _gcry_dsa_gen_rfc6979_k (&k, skey->q, skey->x,
604                                     abuf, (abits+7)/8, hashalgo, extraloops);
605       if (rc)
606         goto leave;
607     }
608   else
609     {
610       /* Select a random k with 0 < k < q */
611       k = _gcry_dsa_gen_k (skey->q, GCRY_STRONG_RANDOM);
612     }
613
614   /* r = (a^k mod p) mod q */
615   gcry_mpi_powm( r, skey->g, k, skey->p );
616   mpi_fdiv_r( r, r, skey->q );
617
618   /* kinv = k^(-1) mod q */
619   kinv = mpi_alloc( mpi_get_nlimbs(k) );
620   mpi_invm(kinv, k, skey->q );
621
622   /* s = (kinv * ( hash + x * r)) mod q */
623   tmp = mpi_alloc( mpi_get_nlimbs(skey->p) );
624   mpi_mul( tmp, skey->x, r );
625   mpi_add( tmp, tmp, hash );
626   mpi_mulm( s , kinv, tmp, skey->q );
627
628   mpi_free(k);
629   mpi_free(kinv);
630   mpi_free(tmp);
631
632   if (!mpi_cmp_ui (r, 0))
633     {
634       /* This is a highly unlikely code path.  */
635       extraloops++;
636       goto again;
637     }
638
639   rc = 0;
640
641  leave:
642   if (hash != input)
643     mpi_free (hash);
644
645   return rc;
646 }
647
648
649 /*
650    Returns true if the signature composed from R and S is valid.
651  */
652 static int
653 verify (gcry_mpi_t r, gcry_mpi_t s, gcry_mpi_t hash, DSA_public_key *pkey )
654 {
655   int rc;
656   gcry_mpi_t w, u1, u2, v;
657   gcry_mpi_t base[3];
658   gcry_mpi_t ex[3];
659
660   if( !(mpi_cmp_ui( r, 0 ) > 0 && mpi_cmp( r, pkey->q ) < 0) )
661     return 0; /* assertion      0 < r < q  failed */
662   if( !(mpi_cmp_ui( s, 0 ) > 0 && mpi_cmp( s, pkey->q ) < 0) )
663     return 0; /* assertion      0 < s < q  failed */
664
665   w  = mpi_alloc( mpi_get_nlimbs(pkey->q) );
666   u1 = mpi_alloc( mpi_get_nlimbs(pkey->q) );
667   u2 = mpi_alloc( mpi_get_nlimbs(pkey->q) );
668   v  = mpi_alloc( mpi_get_nlimbs(pkey->p) );
669
670   /* w = s^(-1) mod q */
671   mpi_invm( w, s, pkey->q );
672
673   /* u1 = (hash * w) mod q */
674   mpi_mulm( u1, hash, w, pkey->q );
675
676   /* u2 = r * w mod q  */
677   mpi_mulm( u2, r, w, pkey->q );
678
679   /* v =  g^u1 * y^u2 mod p mod q */
680   base[0] = pkey->g; ex[0] = u1;
681   base[1] = pkey->y; ex[1] = u2;
682   base[2] = NULL;    ex[2] = NULL;
683   mpi_mulpowm( v, base, ex, pkey->p );
684   mpi_fdiv_r( v, v, pkey->q );
685
686   rc = !mpi_cmp( v, r );
687
688   mpi_free(w);
689   mpi_free(u1);
690   mpi_free(u2);
691   mpi_free(v);
692
693   return rc;
694 }
695
696
697 /*********************************************
698  **************  interface  ******************
699  *********************************************/
700
701 static gcry_err_code_t
702 dsa_generate (const gcry_sexp_t genparms, gcry_sexp_t *r_skey)
703 {
704   gpg_err_code_t rc;
705   unsigned int nbits;
706   gcry_sexp_t domainsexp;
707   DSA_secret_key sk;
708   gcry_sexp_t l1;
709   unsigned int qbits = 0;
710   gcry_sexp_t deriveparms = NULL;
711   gcry_sexp_t seedinfo = NULL;
712   gcry_sexp_t misc_info = NULL;
713   int transient_key = 0;
714   int use_fips186_2 = 0;
715   int use_fips186 = 0;
716   dsa_domain_t domain;
717   gcry_mpi_t *factors = NULL;
718
719   memset (&sk, 0, sizeof sk);
720   memset (&domain, 0, sizeof domain);
721
722   rc = _gcry_pk_util_get_nbits (genparms, &nbits);
723   if (rc)
724     return rc;
725
726   /* Parse the optional qbits element.  */
727   l1 = gcry_sexp_find_token (genparms, "qbits", 0);
728   if (l1)
729     {
730       char buf[50];
731       const char *s;
732       size_t n;
733
734       s = gcry_sexp_nth_data (l1, 1, &n);
735       if (!s || n >= DIM (buf) - 1 )
736         {
737           gcry_sexp_release (l1);
738           return GPG_ERR_INV_OBJ; /* No value or value too large.  */
739         }
740       memcpy (buf, s, n);
741       buf[n] = 0;
742       qbits = (unsigned int)strtoul (buf, NULL, 0);
743       gcry_sexp_release (l1);
744     }
745
746   /* Parse the optional transient-key flag.  */
747   l1 = gcry_sexp_find_token (genparms, "transient-key", 0);
748   if (l1)
749     {
750       transient_key = 1;
751       gcry_sexp_release (l1);
752     }
753
754   /* Get the optional derive parameters.  */
755   deriveparms = gcry_sexp_find_token (genparms, "derive-parms", 0);
756
757   /* Parse the optional "use-fips186" flags.  */
758   l1 = gcry_sexp_find_token (genparms, "use-fips186", 0);
759   if (l1)
760     {
761       use_fips186 = 1;
762       gcry_sexp_release (l1);
763     }
764   l1 = gcry_sexp_find_token (genparms, "use-fips186-2", 0);
765   if (l1)
766     {
767       use_fips186_2 = 1;
768       gcry_sexp_release (l1);
769     }
770
771   /* Check whether domain parameters are given.  */
772   domainsexp = gcry_sexp_find_token (genparms, "domain", 0);
773   if (domainsexp)
774     {
775       /* DERIVEPARMS can't be used together with domain parameters.
776          NBITS abnd QBITS may not be specified because there values
777          are derived from the domain parameters.  */
778       if (deriveparms || qbits || nbits)
779         {
780           gcry_sexp_release (domainsexp);
781           gcry_sexp_release (deriveparms);
782           return GPG_ERR_INV_VALUE;
783         }
784
785       /* Put all domain parameters into the domain object.  */
786       l1 = gcry_sexp_find_token (domainsexp, "p", 0);
787       domain.p = gcry_sexp_nth_mpi (l1, 1, GCRYMPI_FMT_USG);
788       gcry_sexp_release (l1);
789       l1 = gcry_sexp_find_token (domainsexp, "q", 0);
790       domain.q = gcry_sexp_nth_mpi (l1, 1, GCRYMPI_FMT_USG);
791       gcry_sexp_release (l1);
792       l1 = gcry_sexp_find_token (domainsexp, "g", 0);
793       domain.g = gcry_sexp_nth_mpi (l1, 1, GCRYMPI_FMT_USG);
794       gcry_sexp_release (l1);
795       gcry_sexp_release (domainsexp);
796
797       /* Check that all domain parameters are available.  */
798       if (!domain.p || !domain.q || !domain.g)
799         {
800           gcry_mpi_release (domain.p);
801           gcry_mpi_release (domain.q);
802           gcry_mpi_release (domain.g);
803           gcry_sexp_release (deriveparms);
804           return GPG_ERR_MISSING_VALUE;
805         }
806
807       /* Get NBITS and QBITS from the domain parameters.  */
808       nbits = mpi_get_nbits (domain.p);
809       qbits = mpi_get_nbits (domain.q);
810     }
811
812   if (deriveparms || use_fips186 || use_fips186_2 || fips_mode ())
813     {
814       int counter;
815       void *seed;
816       size_t seedlen;
817       gcry_mpi_t h_value;
818
819       rc = generate_fips186 (&sk, nbits, qbits, deriveparms, use_fips186_2,
820                              &domain,
821                              &counter, &seed, &seedlen, &h_value);
822       if (!rc && h_value)
823         {
824           /* Format the seed-values unless domain parameters are used
825              for which a H_VALUE of NULL is an indication.  */
826           rc = gcry_sexp_build (&seedinfo, NULL,
827                                 "(seed-values(counter %d)(seed %b)(h %m))",
828                                 counter, (int)seedlen, seed, h_value);
829           gcry_free (seed);
830           gcry_mpi_release (h_value);
831         }
832     }
833   else
834     {
835       rc = generate (&sk, nbits, qbits, transient_key, &domain, &factors);
836     }
837
838   if (!rc)
839     {
840       /* Put the factors into MISC_INFO.  Note that the factors are
841          not confidential thus we can store them in standard memory.  */
842       int nfactors, i, j;
843       char *p;
844       char *format = NULL;
845       void **arg_list = NULL;
846
847       for (nfactors=0; factors && factors[nfactors]; nfactors++)
848         ;
849       /* Allocate space for the format string:
850          "(misc-key-info%S(pm1-factors%m))"
851          with one "%m" for each factor and construct it.  */
852       format = gcry_malloc (50 + 2*nfactors);
853       if (!format)
854         rc = gpg_err_code_from_syserror ();
855       else
856         {
857           p = stpcpy (format, "(misc-key-info");
858           if (seedinfo)
859             p = stpcpy (p, "%S");
860           if (nfactors)
861             {
862               p = stpcpy (p, "(pm1-factors");
863               for (i=0; i < nfactors; i++)
864                 p = stpcpy (p, "%m");
865               p = stpcpy (p, ")");
866             }
867           p = stpcpy (p, ")");
868
869           /* Allocate space for the list of factors plus one for the
870              seedinfo s-exp plus an extra NULL entry for safety and
871              fill it with the factors.  */
872           arg_list = gcry_calloc (nfactors+1+1, sizeof *arg_list);
873           if (!arg_list)
874             rc = gpg_err_code_from_syserror ();
875           else
876             {
877               i = 0;
878               if (seedinfo)
879                 arg_list[i++] = &seedinfo;
880               for (j=0; j < nfactors; j++)
881                 arg_list[i++] = factors + j;
882               arg_list[i] = NULL;
883
884               rc = gcry_sexp_build_array (&misc_info, NULL, format, arg_list);
885             }
886         }
887
888       gcry_free (arg_list);
889       gcry_free (format);
890     }
891
892   if (!rc)
893     rc = gcry_sexp_build (r_skey, NULL,
894                           "(key-data"
895                           " (public-key"
896                           "  (dsa(p%m)(q%m)(g%m)(y%m)))"
897                           " (private-key"
898                           "  (dsa(p%m)(q%m)(g%m)(y%m)(x%m)))"
899                           " %S)",
900                           sk.p, sk.q, sk.g, sk.y,
901                           sk.p, sk.q, sk.g, sk.y, sk.x,
902                           misc_info);
903
904
905   gcry_mpi_release (sk.p);
906   gcry_mpi_release (sk.q);
907   gcry_mpi_release (sk.g);
908   gcry_mpi_release (sk.y);
909   gcry_mpi_release (sk.x);
910
911   gcry_mpi_release (domain.p);
912   gcry_mpi_release (domain.q);
913   gcry_mpi_release (domain.g);
914
915   gcry_sexp_release (seedinfo);
916   gcry_sexp_release (misc_info);
917   gcry_sexp_release (deriveparms);
918   if (factors)
919     {
920       gcry_mpi_t *mp;
921       for (mp = factors; *mp; mp++)
922         mpi_free (*mp);
923       gcry_free (factors);
924     }
925   return rc;
926 }
927
928
929
930 static gcry_err_code_t
931 dsa_check_secret_key (gcry_sexp_t keyparms)
932 {
933   gcry_err_code_t rc;
934   DSA_secret_key sk = {NULL, NULL, NULL, NULL, NULL};
935
936   rc = _gcry_pk_util_extract_mpis (keyparms, "pqgyx",
937                                    &sk.p, &sk.q, &sk.g, &sk.y, &sk.x,
938                                    NULL);
939   if (rc)
940     goto leave;
941
942   if (!check_secret_key (&sk))
943     rc = GPG_ERR_BAD_SECKEY;
944
945  leave:
946   gcry_mpi_release (sk.p);
947   gcry_mpi_release (sk.q);
948   gcry_mpi_release (sk.g);
949   gcry_mpi_release (sk.y);
950   gcry_mpi_release (sk.x);
951   if (DBG_CIPHER)
952     log_debug ("dsa_testkey    => %s\n", gpg_strerror (rc));
953   return rc;
954 }
955
956
957 static gcry_err_code_t
958 dsa_sign (gcry_sexp_t *r_sig, gcry_sexp_t s_data, gcry_sexp_t keyparms)
959 {
960   gcry_err_code_t rc;
961   struct pk_encoding_ctx ctx;
962   gcry_mpi_t data = NULL;
963   DSA_secret_key sk = {NULL, NULL, NULL, NULL, NULL};
964   gcry_mpi_t sig_r = NULL;
965   gcry_mpi_t sig_s = NULL;
966
967   _gcry_pk_util_init_encoding_ctx (&ctx, PUBKEY_OP_SIGN,
968                                    dsa_get_nbits (keyparms));
969
970   /* Extract the data.  */
971   rc = _gcry_pk_util_data_to_mpi (s_data, &data, &ctx);
972   if (rc)
973     goto leave;
974   if (DBG_CIPHER)
975     log_mpidump ("dsa_sign   data", data);
976
977   /* Extract the key.  */
978   rc = _gcry_pk_util_extract_mpis (keyparms, "pqgyx",
979                                    &sk.p, &sk.q, &sk.g, &sk.y, &sk.x, NULL);
980   if (rc)
981     goto leave;
982   if (DBG_CIPHER)
983     {
984       log_mpidump ("dsa_sign      p", sk.p);
985       log_mpidump ("dsa_sign      q", sk.q);
986       log_mpidump ("dsa_sign      g", sk.g);
987       log_mpidump ("dsa_sign      y", sk.y);
988       if (!fips_mode ())
989         log_mpidump ("dsa_sign      x", sk.x);
990     }
991
992   sig_r = gcry_mpi_new (0);
993   sig_s = gcry_mpi_new (0);
994   rc = sign (sig_r, sig_s, data, &sk, ctx.flags, ctx.hash_algo);
995   if (rc)
996     goto leave;
997   if (DBG_CIPHER)
998     {
999       log_mpidump ("dsa_sign  sig_r", sig_r);
1000       log_mpidump ("dsa_sign  sig_s", sig_s);
1001     }
1002   rc = gcry_sexp_build (r_sig, NULL, "(sig-val(dsa(r%M)(s%M)))", sig_r, sig_s);
1003
1004  leave:
1005   gcry_mpi_release (sig_r);
1006   gcry_mpi_release (sig_s);
1007   gcry_mpi_release (sk.p);
1008   gcry_mpi_release (sk.q);
1009   gcry_mpi_release (sk.g);
1010   gcry_mpi_release (sk.y);
1011   gcry_mpi_release (sk.x);
1012   gcry_mpi_release (data);
1013   _gcry_pk_util_free_encoding_ctx (&ctx);
1014   if (DBG_CIPHER)
1015     log_debug ("dsa_sign      => %s\n", gpg_strerror (rc));
1016   return rc;
1017 }
1018
1019
1020 static gcry_err_code_t
1021 dsa_verify (gcry_sexp_t s_sig, gcry_sexp_t s_data, gcry_sexp_t s_keyparms)
1022 {
1023   gcry_err_code_t rc;
1024   struct pk_encoding_ctx ctx;
1025   gcry_sexp_t l1 = NULL;
1026   gcry_mpi_t sig_r = NULL;
1027   gcry_mpi_t sig_s = NULL;
1028   gcry_mpi_t data = NULL;
1029   DSA_public_key pk = { NULL, NULL, NULL, NULL };
1030
1031   _gcry_pk_util_init_encoding_ctx (&ctx, PUBKEY_OP_VERIFY,
1032                                    dsa_get_nbits (s_keyparms));
1033
1034   /* Extract the data.  */
1035   rc = _gcry_pk_util_data_to_mpi (s_data, &data, &ctx);
1036   if (rc)
1037     goto leave;
1038   if (DBG_CIPHER)
1039     log_mpidump ("dsa_verify data", data);
1040
1041   /* Extract the signature value.  */
1042   rc = _gcry_pk_util_preparse_sigval (s_sig, dsa_names, &l1, NULL);
1043   if (rc)
1044     goto leave;
1045   rc = _gcry_pk_util_extract_mpis (l1, "rs", &sig_r, &sig_s, NULL);
1046   if (rc)
1047     goto leave;
1048   if (DBG_CIPHER)
1049     {
1050       log_mpidump ("dsa_verify  s_r", sig_r);
1051       log_mpidump ("dsa_verify  s_s", sig_s);
1052     }
1053
1054   /* Extract the key.  */
1055   rc = _gcry_pk_util_extract_mpis (s_keyparms, "pqgy",
1056                                    &pk.p, &pk.q, &pk.g, &pk.y, NULL);
1057   if (rc)
1058     goto leave;
1059   if (DBG_CIPHER)
1060     {
1061       log_mpidump ("dsa_verify    p", pk.p);
1062       log_mpidump ("dsa_verify    q", pk.q);
1063       log_mpidump ("dsa_verify    g", pk.g);
1064       log_mpidump ("dsa_verify    y", pk.y);
1065     }
1066
1067   /* Verify the signature.  */
1068   if (mpi_is_opaque (data))
1069     {
1070       const void *abuf;
1071       unsigned int abits, qbits;
1072       gcry_mpi_t a;
1073
1074       qbits = mpi_get_nbits (pk.q);
1075
1076       abuf = gcry_mpi_get_opaque (data, &abits);
1077       rc = gpg_err_code (gcry_mpi_scan (&a, GCRYMPI_FMT_USG,
1078                                         abuf, (abits+7)/8, NULL));
1079       if (!rc)
1080         {
1081           if (abits > qbits)
1082             gcry_mpi_rshift (a, a, abits - qbits);
1083
1084           if (!verify (sig_r, sig_s, a, &pk))
1085             rc = GPG_ERR_BAD_SIGNATURE;
1086           gcry_mpi_release (a);
1087         }
1088     }
1089   else
1090     {
1091       if (!verify (sig_r, sig_s, data, &pk))
1092         rc = GPG_ERR_BAD_SIGNATURE;
1093     }
1094
1095  leave:
1096   gcry_mpi_release (pk.p);
1097   gcry_mpi_release (pk.q);
1098   gcry_mpi_release (pk.g);
1099   gcry_mpi_release (pk.y);
1100   gcry_mpi_release (data);
1101   gcry_mpi_release (sig_r);
1102   gcry_mpi_release (sig_s);
1103   gcry_sexp_release (l1);
1104   _gcry_pk_util_free_encoding_ctx (&ctx);
1105   if (DBG_CIPHER)
1106     log_debug ("dsa_verify    => %s\n", rc?gpg_strerror (rc):"Good");
1107   return rc;
1108 }
1109
1110
1111 /* Return the number of bits for the key described by PARMS.  On error
1112  * 0 is returned.  The format of PARMS starts with the algorithm name;
1113  * for example:
1114  *
1115  *   (dsa
1116  *     (p <mpi>)
1117  *     (q <mpi>)
1118  *     (g <mpi>)
1119  *     (y <mpi>))
1120  *
1121  * More parameters may be given but we only need P here.
1122  */
1123 static unsigned int
1124 dsa_get_nbits (gcry_sexp_t parms)
1125 {
1126   gcry_sexp_t l1;
1127   gcry_mpi_t p;
1128   unsigned int nbits;
1129
1130   l1 = gcry_sexp_find_token (parms, "p", 1);
1131   if (!l1)
1132     return 0; /* Parameter P not found.  */
1133
1134   p = gcry_sexp_nth_mpi (l1, 1, GCRYMPI_FMT_USG);
1135   gcry_sexp_release (l1);
1136   nbits = p? mpi_get_nbits (p) : 0;
1137   gcry_mpi_release (p);
1138   return nbits;
1139 }
1140
1141
1142 \f
1143 /*
1144      Self-test section.
1145  */
1146
1147 static const char *
1148 selftest_sign_1024 (gcry_sexp_t pkey, gcry_sexp_t skey)
1149 {
1150   static const char sample_data[] =
1151     "(data (flags raw)"
1152     " (value #a0b1c2d3e4f500102030405060708090a1b2c3d4#))";
1153   static const char sample_data_bad[] =
1154     "(data (flags raw)"
1155     " (value #a0b1c2d3e4f510102030405060708090a1b2c3d4#))";
1156
1157   const char *errtxt = NULL;
1158   gcry_error_t err;
1159   gcry_sexp_t data = NULL;
1160   gcry_sexp_t data_bad = NULL;
1161   gcry_sexp_t sig = NULL;
1162
1163   err = gcry_sexp_sscan (&data, NULL,
1164                          sample_data, strlen (sample_data));
1165   if (!err)
1166     err = gcry_sexp_sscan (&data_bad, NULL,
1167                            sample_data_bad, strlen (sample_data_bad));
1168   if (err)
1169     {
1170       errtxt = "converting data failed";
1171       goto leave;
1172     }
1173
1174   err = gcry_pk_sign (&sig, data, skey);
1175   if (err)
1176     {
1177       errtxt = "signing failed";
1178       goto leave;
1179     }
1180   err = gcry_pk_verify (sig, data, pkey);
1181   if (err)
1182     {
1183       errtxt = "verify failed";
1184       goto leave;
1185     }
1186   err = gcry_pk_verify (sig, data_bad, pkey);
1187   if (gcry_err_code (err) != GPG_ERR_BAD_SIGNATURE)
1188     {
1189       errtxt = "bad signature not detected";
1190       goto leave;
1191     }
1192
1193
1194  leave:
1195   gcry_sexp_release (sig);
1196   gcry_sexp_release (data_bad);
1197   gcry_sexp_release (data);
1198   return errtxt;
1199 }
1200
1201
1202 static gpg_err_code_t
1203 selftests_dsa (selftest_report_func_t report)
1204 {
1205   const char *what;
1206   const char *errtxt;
1207   gcry_error_t err;
1208   gcry_sexp_t skey = NULL;
1209   gcry_sexp_t pkey = NULL;
1210
1211   /* Convert the S-expressions into the internal representation.  */
1212   what = "convert";
1213   err = gcry_sexp_sscan (&skey, NULL,
1214                          sample_secret_key, strlen (sample_secret_key));
1215   if (!err)
1216     err = gcry_sexp_sscan (&pkey, NULL,
1217                            sample_public_key, strlen (sample_public_key));
1218   if (err)
1219     {
1220       errtxt = gcry_strerror (err);
1221       goto failed;
1222     }
1223
1224   what = "key consistency";
1225   err = gcry_pk_testkey (skey);
1226   if (err)
1227     {
1228       errtxt = gcry_strerror (err);
1229       goto failed;
1230     }
1231
1232   what = "sign";
1233   errtxt = selftest_sign_1024 (pkey, skey);
1234   if (errtxt)
1235     goto failed;
1236
1237   gcry_sexp_release (pkey);
1238   gcry_sexp_release (skey);
1239   return 0; /* Succeeded. */
1240
1241  failed:
1242   gcry_sexp_release (pkey);
1243   gcry_sexp_release (skey);
1244   if (report)
1245     report ("pubkey", GCRY_PK_DSA, what, errtxt);
1246   return GPG_ERR_SELFTEST_FAILED;
1247 }
1248
1249
1250 /* Run a full self-test for ALGO and return 0 on success.  */
1251 static gpg_err_code_t
1252 run_selftests (int algo, int extended, selftest_report_func_t report)
1253 {
1254   gpg_err_code_t ec;
1255
1256   (void)extended;
1257
1258   switch (algo)
1259     {
1260     case GCRY_PK_DSA:
1261       ec = selftests_dsa (report);
1262       break;
1263     default:
1264       ec = GPG_ERR_PUBKEY_ALGO;
1265       break;
1266
1267     }
1268   return ec;
1269 }
1270
1271
1272
1273 \f
1274 gcry_pk_spec_t _gcry_pubkey_spec_dsa =
1275   {
1276     GCRY_PK_DSA, { 0, 1 },
1277     GCRY_PK_USAGE_SIGN,
1278     "DSA", dsa_names,
1279     "pqgy", "pqgyx", "", "rs", "pqgy",
1280     dsa_generate,
1281     dsa_check_secret_key,
1282     NULL,
1283     NULL,
1284     dsa_sign,
1285     dsa_verify,
1286     dsa_get_nbits,
1287     run_selftests
1288   };