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