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