ceff947cfeedd1efcd95206d007145b693224d66
[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 (int algo, unsigned int nbits, unsigned long evalue,
693               const gcry_sexp_t genparms, gcry_sexp_t *r_skey)
694 {
695   gpg_err_code_t rc;
696   DSA_secret_key sk;
697   gcry_sexp_t l1;
698   unsigned int qbits = 0;
699   gcry_sexp_t deriveparms = NULL;
700   gcry_sexp_t seedinfo = NULL;
701   gcry_sexp_t misc_info = NULL;
702   int transient_key = 0;
703   int use_fips186_2 = 0;
704   int use_fips186 = 0;
705   dsa_domain_t domain;
706   gcry_mpi_t *factors = NULL;
707
708   (void)algo;    /* No need to check it.  */
709   (void)evalue;  /* Not required for DSA. */
710
711   memset (&sk, 0, sizeof sk);
712   memset (&domain, 0, sizeof domain);
713
714   if (genparms)
715     {
716       gcry_sexp_t domainsexp;
717
718       /* Parse the optional qbits element.  */
719       l1 = gcry_sexp_find_token (genparms, "qbits", 0);
720       if (l1)
721         {
722           char buf[50];
723           const char *s;
724           size_t n;
725
726           s = gcry_sexp_nth_data (l1, 1, &n);
727           if (!s || n >= DIM (buf) - 1 )
728             {
729               gcry_sexp_release (l1);
730               return GPG_ERR_INV_OBJ; /* No value or value too large.  */
731             }
732           memcpy (buf, s, n);
733           buf[n] = 0;
734           qbits = (unsigned int)strtoul (buf, NULL, 0);
735           gcry_sexp_release (l1);
736         }
737
738       /* Parse the optional transient-key flag.  */
739       l1 = gcry_sexp_find_token (genparms, "transient-key", 0);
740       if (l1)
741         {
742           transient_key = 1;
743           gcry_sexp_release (l1);
744         }
745
746       /* Get the optional derive parameters.  */
747       deriveparms = gcry_sexp_find_token (genparms, "derive-parms", 0);
748
749       /* Parse the optional "use-fips186" flags.  */
750       l1 = gcry_sexp_find_token (genparms, "use-fips186", 0);
751       if (l1)
752         {
753           use_fips186 = 1;
754           gcry_sexp_release (l1);
755         }
756       l1 = gcry_sexp_find_token (genparms, "use-fips186-2", 0);
757       if (l1)
758         {
759           use_fips186_2 = 1;
760           gcry_sexp_release (l1);
761         }
762
763       /* Check whether domain parameters are given.  */
764       domainsexp = gcry_sexp_find_token (genparms, "domain", 0);
765       if (domainsexp)
766         {
767           /* DERIVEPARMS can't be used together with domain
768              parameters.  NBITS abnd QBITS may not be specified
769              because there values are derived from the domain
770              parameters.  */
771           if (deriveparms || qbits || nbits)
772             {
773               gcry_sexp_release (domainsexp);
774               gcry_sexp_release (deriveparms);
775               return GPG_ERR_INV_VALUE;
776             }
777
778           /* Put all domain parameters into the domain object.  */
779           l1 = gcry_sexp_find_token (domainsexp, "p", 0);
780           domain.p = gcry_sexp_nth_mpi (l1, 1, GCRYMPI_FMT_USG);
781           gcry_sexp_release (l1);
782           l1 = gcry_sexp_find_token (domainsexp, "q", 0);
783           domain.q = gcry_sexp_nth_mpi (l1, 1, GCRYMPI_FMT_USG);
784           gcry_sexp_release (l1);
785           l1 = gcry_sexp_find_token (domainsexp, "g", 0);
786           domain.g = gcry_sexp_nth_mpi (l1, 1, GCRYMPI_FMT_USG);
787           gcry_sexp_release (l1);
788           gcry_sexp_release (domainsexp);
789
790           /* Check that all domain parameters are available.  */
791           if (!domain.p || !domain.q || !domain.g)
792             {
793               gcry_mpi_release (domain.p);
794               gcry_mpi_release (domain.q);
795               gcry_mpi_release (domain.g);
796               gcry_sexp_release (deriveparms);
797               return GPG_ERR_MISSING_VALUE;
798             }
799
800           /* Get NBITS and QBITS from the domain parameters.  */
801           nbits = mpi_get_nbits (domain.p);
802           qbits = mpi_get_nbits (domain.q);
803         }
804     }
805
806   if (deriveparms || use_fips186 || use_fips186_2 || fips_mode ())
807     {
808       int counter;
809       void *seed;
810       size_t seedlen;
811       gcry_mpi_t h_value;
812
813       rc = generate_fips186 (&sk, nbits, qbits, deriveparms, use_fips186_2,
814                              &domain,
815                              &counter, &seed, &seedlen, &h_value);
816       if (!rc && h_value)
817         {
818           /* Format the seed-values unless domain parameters are used
819              for which a H_VALUE of NULL is an indication.  */
820           rc = gpg_err_code (gcry_sexp_build
821                              (&seedinfo, NULL,
822                               "(seed-values(counter %d)(seed %b)(h %m))",
823                               counter, (int)seedlen, seed, h_value));
824           gcry_free (seed);
825           gcry_mpi_release (h_value);
826         }
827     }
828   else
829     {
830       rc = generate (&sk, nbits, qbits, transient_key, &domain, &factors);
831     }
832
833   if (!rc)
834     {
835       /* Put the factors into MISC_INFO.  Note that the factors are
836          not confidential thus we can store them in standard memory.  */
837       int nfactors, i, j;
838       char *p;
839       char *format = NULL;
840       void **arg_list = NULL;
841
842       for (nfactors=0; factors && factors[nfactors]; nfactors++)
843         ;
844       /* Allocate space for the format string:
845          "(misc-key-info%S(pm1-factors%m))"
846          with one "%m" for each factor and construct it.  */
847       format = gcry_malloc (50 + 2*nfactors);
848       if (!format)
849         rc = gpg_err_code_from_syserror ();
850       else
851         {
852           p = stpcpy (format, "(misc-key-info");
853           if (seedinfo)
854             p = stpcpy (p, "%S");
855           if (nfactors)
856             {
857               p = stpcpy (p, "(pm1-factors");
858               for (i=0; i < nfactors; i++)
859                 p = stpcpy (p, "%m");
860               p = stpcpy (p, ")");
861             }
862           p = stpcpy (p, ")");
863
864           /* Allocate space for the list of factors plus one for the
865              seedinfo s-exp plus an extra NULL entry for safety and
866              fill it with the factors.  */
867           arg_list = gcry_calloc (nfactors+1+1, sizeof *arg_list);
868           if (!arg_list)
869             rc = gpg_err_code_from_syserror ();
870           else
871             {
872               i = 0;
873               if (seedinfo)
874                 arg_list[i++] = &seedinfo;
875               for (j=0; j < nfactors; j++)
876                 arg_list[i++] = factors + j;
877               arg_list[i] = NULL;
878
879               rc = gpg_err_code (gcry_sexp_build_array
880                                  (&misc_info, NULL, format, arg_list));
881             }
882         }
883
884       gcry_free (arg_list);
885       gcry_free (format);
886     }
887
888   if (!rc)
889     rc = gcry_err_code (gcry_sexp_build
890                         (r_skey, NULL,
891                          "(key-data"
892                          " (public-key"
893                          "  (dsa(p%m)(q%m)(g%m)(y%m)))"
894                          " (private-key"
895                          "  (dsa(p%m)(q%m)(g%m)(y%m)(x%m)))"
896                          " %S)",
897                          sk.p, sk.q, sk.g, sk.y,
898                          sk.p, sk.q, sk.g, sk.y, sk.x,
899                          misc_info));
900
901
902   gcry_mpi_release (sk.p);
903   gcry_mpi_release (sk.q);
904   gcry_mpi_release (sk.g);
905   gcry_mpi_release (sk.y);
906   gcry_mpi_release (sk.x);
907
908   gcry_mpi_release (domain.p);
909   gcry_mpi_release (domain.q);
910   gcry_mpi_release (domain.g);
911
912   gcry_sexp_release (seedinfo);
913   gcry_sexp_release (misc_info);
914   gcry_sexp_release (deriveparms);
915   if (factors)
916     {
917       gcry_mpi_t *mp;
918       for (mp = factors; *mp; mp++)
919         mpi_free (*mp);
920       gcry_free (factors);
921     }
922   return rc;
923 }
924
925
926
927 static gcry_err_code_t
928 dsa_check_secret_key (int algo, gcry_mpi_t *skey)
929 {
930   gcry_err_code_t err = GPG_ERR_NO_ERROR;
931   DSA_secret_key sk;
932
933   (void)algo;
934
935   if ((! skey[0]) || (! skey[1]) || (! skey[2]) || (! skey[3]) || (! skey[4]))
936     err = GPG_ERR_BAD_MPI;
937   else
938     {
939       sk.p = skey[0];
940       sk.q = skey[1];
941       sk.g = skey[2];
942       sk.y = skey[3];
943       sk.x = skey[4];
944       if (! check_secret_key (&sk))
945         err = GPG_ERR_BAD_SECKEY;
946     }
947
948   return err;
949 }
950
951
952 static gcry_err_code_t
953 dsa_sign (int algo, gcry_sexp_t *r_result, gcry_mpi_t data, gcry_mpi_t *skey,
954           int flags, int hashalgo)
955 {
956   gcry_err_code_t rc;
957   DSA_secret_key sk;
958   gcry_mpi_t r, s;
959
960   (void)algo;
961   (void)flags;
962   (void)hashalgo;
963
964   if ((! data)
965       || (! skey[0]) || (! skey[1]) || (! skey[2])
966       || (! skey[3]) || (! skey[4]))
967     rc = GPG_ERR_BAD_MPI;
968   else
969     {
970       sk.p = skey[0];
971       sk.q = skey[1];
972       sk.g = skey[2];
973       sk.y = skey[3];
974       sk.x = skey[4];
975       r = mpi_alloc (mpi_get_nlimbs (sk.p));
976       s = mpi_alloc (mpi_get_nlimbs (sk.p));
977       rc = sign (r, s, data, &sk, flags, hashalgo);
978       if (!rc)
979         rc = gcry_err_code (gcry_sexp_build (r_result, NULL,
980                                              "(sig-val(dsa(r%M)(s%M)))",
981                                              r, s));
982       mpi_free (r);
983       mpi_free (s);
984     }
985   return rc;
986 }
987
988 static gcry_err_code_t
989 dsa_verify (int algo, gcry_mpi_t hash, gcry_mpi_t *data, gcry_mpi_t *pkey,
990             int (*cmp) (void *, gcry_mpi_t), void *opaquev,
991             int flags, int hashalgo)
992 {
993   gcry_err_code_t err = GPG_ERR_NO_ERROR;
994   DSA_public_key pk;
995
996   (void)algo;
997   (void)cmp;
998   (void)opaquev;
999   (void)flags;
1000   (void)hashalgo;
1001
1002   if ((! data[0]) || (! data[1]) || (! hash)
1003       || (! pkey[0]) || (! pkey[1]) || (! pkey[2]) || (! pkey[3]))
1004     err = GPG_ERR_BAD_MPI;
1005   else
1006     {
1007       pk.p = pkey[0];
1008       pk.q = pkey[1];
1009       pk.g = pkey[2];
1010       pk.y = pkey[3];
1011       if (mpi_is_opaque (hash))
1012         {
1013           const void *abuf;
1014           unsigned int abits, qbits;
1015           gcry_mpi_t a;
1016
1017           qbits = mpi_get_nbits (pk.q);
1018
1019           abuf = gcry_mpi_get_opaque (hash, &abits);
1020           err = gcry_mpi_scan (&a, GCRYMPI_FMT_USG, abuf, (abits+7)/8, NULL);
1021           if (!err)
1022             {
1023               if (abits > qbits)
1024                 gcry_mpi_rshift (a, a, abits - qbits);
1025
1026               if (!verify (data[0], data[1], a, &pk))
1027                 err = GPG_ERR_BAD_SIGNATURE;
1028               gcry_mpi_release (a);
1029             }
1030         }
1031       else
1032         {
1033           if (!verify (data[0], data[1], hash, &pk))
1034             err = GPG_ERR_BAD_SIGNATURE;
1035         }
1036     }
1037   return err;
1038 }
1039
1040
1041 static unsigned int
1042 dsa_get_nbits (int algo, gcry_mpi_t *pkey)
1043 {
1044   (void)algo;
1045
1046   return mpi_get_nbits (pkey[0]);
1047 }
1048
1049
1050 \f
1051 /*
1052      Self-test section.
1053  */
1054
1055 static const char *
1056 selftest_sign_1024 (gcry_sexp_t pkey, gcry_sexp_t skey)
1057 {
1058   static const char sample_data[] =
1059     "(data (flags raw)"
1060     " (value #a0b1c2d3e4f500102030405060708090a1b2c3d4#))";
1061   static const char sample_data_bad[] =
1062     "(data (flags raw)"
1063     " (value #a0b1c2d3e4f510102030405060708090a1b2c3d4#))";
1064
1065   const char *errtxt = NULL;
1066   gcry_error_t err;
1067   gcry_sexp_t data = NULL;
1068   gcry_sexp_t data_bad = NULL;
1069   gcry_sexp_t sig = NULL;
1070
1071   err = gcry_sexp_sscan (&data, NULL,
1072                          sample_data, strlen (sample_data));
1073   if (!err)
1074     err = gcry_sexp_sscan (&data_bad, NULL,
1075                            sample_data_bad, strlen (sample_data_bad));
1076   if (err)
1077     {
1078       errtxt = "converting data failed";
1079       goto leave;
1080     }
1081
1082   err = gcry_pk_sign (&sig, data, skey);
1083   if (err)
1084     {
1085       errtxt = "signing failed";
1086       goto leave;
1087     }
1088   err = gcry_pk_verify (sig, data, pkey);
1089   if (err)
1090     {
1091       errtxt = "verify failed";
1092       goto leave;
1093     }
1094   err = gcry_pk_verify (sig, data_bad, pkey);
1095   if (gcry_err_code (err) != GPG_ERR_BAD_SIGNATURE)
1096     {
1097       errtxt = "bad signature not detected";
1098       goto leave;
1099     }
1100
1101
1102  leave:
1103   gcry_sexp_release (sig);
1104   gcry_sexp_release (data_bad);
1105   gcry_sexp_release (data);
1106   return errtxt;
1107 }
1108
1109
1110 static gpg_err_code_t
1111 selftests_dsa (selftest_report_func_t report)
1112 {
1113   const char *what;
1114   const char *errtxt;
1115   gcry_error_t err;
1116   gcry_sexp_t skey = NULL;
1117   gcry_sexp_t pkey = NULL;
1118
1119   /* Convert the S-expressions into the internal representation.  */
1120   what = "convert";
1121   err = gcry_sexp_sscan (&skey, NULL,
1122                          sample_secret_key, strlen (sample_secret_key));
1123   if (!err)
1124     err = gcry_sexp_sscan (&pkey, NULL,
1125                            sample_public_key, strlen (sample_public_key));
1126   if (err)
1127     {
1128       errtxt = gcry_strerror (err);
1129       goto failed;
1130     }
1131
1132   what = "key consistency";
1133   err = gcry_pk_testkey (skey);
1134   if (err)
1135     {
1136       errtxt = gcry_strerror (err);
1137       goto failed;
1138     }
1139
1140   what = "sign";
1141   errtxt = selftest_sign_1024 (pkey, skey);
1142   if (errtxt)
1143     goto failed;
1144
1145   gcry_sexp_release (pkey);
1146   gcry_sexp_release (skey);
1147   return 0; /* Succeeded. */
1148
1149  failed:
1150   gcry_sexp_release (pkey);
1151   gcry_sexp_release (skey);
1152   if (report)
1153     report ("pubkey", GCRY_PK_DSA, what, errtxt);
1154   return GPG_ERR_SELFTEST_FAILED;
1155 }
1156
1157
1158 /* Run a full self-test for ALGO and return 0 on success.  */
1159 static gpg_err_code_t
1160 run_selftests (int algo, int extended, selftest_report_func_t report)
1161 {
1162   gpg_err_code_t ec;
1163
1164   (void)extended;
1165
1166   switch (algo)
1167     {
1168     case GCRY_PK_DSA:
1169       ec = selftests_dsa (report);
1170       break;
1171     default:
1172       ec = GPG_ERR_PUBKEY_ALGO;
1173       break;
1174
1175     }
1176   return ec;
1177 }
1178
1179
1180
1181 \f
1182 static const char *dsa_names[] =
1183   {
1184     "dsa",
1185     "openpgp-dsa",
1186     NULL,
1187   };
1188
1189 gcry_pk_spec_t _gcry_pubkey_spec_dsa =
1190   {
1191     GCRY_PK_DSA, { 0, 1 },
1192     GCRY_PK_USAGE_SIGN,
1193     "DSA", dsa_names,
1194     "pqgy", "pqgyx", "", "rs", "pqgy",
1195     dsa_generate,
1196     dsa_check_secret_key,
1197     NULL,
1198     NULL,
1199     dsa_sign,
1200     dsa_verify,
1201     dsa_get_nbits,
1202     run_selftests
1203   };