Add ARMv8/CE acceleration for AES-XTS
[libgcrypt.git] / cipher / dsa.c
1 /* dsa.c - DSA signature algorithm
2  * Copyright (C) 1998, 2000, 2001, 2002, 2003,
3  *               2006, 2008  Free Software Foundation, Inc.
4  * Copyright (C) 2013 g10 Code GmbH.
5  *
6  * This file is part of Libgcrypt.
7  *
8  * Libgcrypt is free software; you can redistribute it and/or modify
9  * it under the terms of the GNU Lesser General Public License as
10  * published by the Free Software Foundation; either version 2.1 of
11  * the License, or (at your option) any later version.
12  *
13  * Libgcrypt is distributed in the hope that it will be useful,
14  * but WITHOUT ANY WARRANTY; without even the implied warranty of
15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
16  * GNU Lesser General Public License for more details.
17  *
18  * You should have received a copy of the GNU Lesser General Public
19  * License along with this program; if not, see <http://www.gnu.org/licenses/>.
20  */
21
22 #include <config.h>
23 #include <stdio.h>
24 #include <stdlib.h>
25 #include <string.h>
26
27 #include "g10lib.h"
28 #include "mpi.h"
29 #include "cipher.h"
30 #include "pubkey-internal.h"
31
32
33 typedef struct
34 {
35   gcry_mpi_t p;     /* prime */
36   gcry_mpi_t q;     /* group order */
37   gcry_mpi_t g;     /* group generator */
38   gcry_mpi_t y;     /* g^x mod p */
39 } DSA_public_key;
40
41
42 typedef struct
43 {
44   gcry_mpi_t p;     /* prime */
45   gcry_mpi_t q;     /* group order */
46   gcry_mpi_t g;     /* group generator */
47   gcry_mpi_t y;     /* g^x mod p */
48   gcry_mpi_t x;     /* secret exponent */
49 } DSA_secret_key;
50
51
52 /* A structure used to hold domain parameters.  */
53 typedef struct
54 {
55   gcry_mpi_t p;     /* prime */
56   gcry_mpi_t q;     /* group order */
57   gcry_mpi_t g;     /* group generator */
58 } dsa_domain_t;
59
60
61 static const char *dsa_names[] =
62   {
63     "dsa",
64     "openpgp-dsa",
65     NULL,
66   };
67
68
69 /* A sample 1024 bit DSA key used for the selftests.  Not anymore
70  * used, kept only for reference.  */
71 #if 0
72 static const char sample_secret_key_1024[] =
73 "(private-key"
74 " (dsa"
75 "  (p #00AD7C0025BA1A15F775F3F2D673718391D00456978D347B33D7B49E7F32EDAB"
76 "      96273899DD8B2BB46CD6ECA263FAF04A28903503D59062A8865D2AE8ADFB5191"
77 "      CF36FFB562D0E2F5809801A1F675DAE59698A9E01EFE8D7DCFCA084F4C6F5A44"
78 "      44D499A06FFAEA5E8EF5E01F2FD20A7B7EF3F6968AFBA1FB8D91F1559D52D8777B#)"
79 "  (q #00EB7B5751D25EBBB7BD59D920315FD840E19AEBF9#)"
80 "  (g #1574363387FDFD1DDF38F4FBE135BB20C7EE4772FB94C337AF86EA8E49666503"
81 "      AE04B6BE81A2F8DD095311E0217ACA698A11E6C5D33CCDAE71498ED35D13991E"
82 "      B02F09AB40BD8F4C5ED8C75DA779D0AE104BC34C960B002377068AB4B5A1F984"
83 "      3FBA91F537F1B7CAC4D8DD6D89B0D863AF7025D549F9C765D2FC07EE208F8D15#)"
84 "  (y #64B11EF8871BE4AB572AA810D5D3CA11A6CDBC637A8014602C72960DB135BF46"
85 "      A1816A724C34F87330FC9E187C5D66897A04535CC2AC9164A7150ABFA8179827"
86 "      6E45831AB811EEE848EBB24D9F5F2883B6E5DDC4C659DEF944DCFD80BF4D0A20"
87 "      42CAA7DC289F0C5A9D155F02D3D551DB741A81695B74D4C8F477F9C7838EB0FB#)"
88 "  (x #11D54E4ADBD3034160F2CED4B7CD292A4EBF3EC0#)))";
89 /* A sample 1024 bit DSA key used for the selftests (public only).  */
90 static const char sample_public_key_1024[] =
91 "(public-key"
92 " (dsa"
93 "  (p #00AD7C0025BA1A15F775F3F2D673718391D00456978D347B33D7B49E7F32EDAB"
94 "      96273899DD8B2BB46CD6ECA263FAF04A28903503D59062A8865D2AE8ADFB5191"
95 "      CF36FFB562D0E2F5809801A1F675DAE59698A9E01EFE8D7DCFCA084F4C6F5A44"
96 "      44D499A06FFAEA5E8EF5E01F2FD20A7B7EF3F6968AFBA1FB8D91F1559D52D8777B#)"
97 "  (q #00EB7B5751D25EBBB7BD59D920315FD840E19AEBF9#)"
98 "  (g #1574363387FDFD1DDF38F4FBE135BB20C7EE4772FB94C337AF86EA8E49666503"
99 "      AE04B6BE81A2F8DD095311E0217ACA698A11E6C5D33CCDAE71498ED35D13991E"
100 "      B02F09AB40BD8F4C5ED8C75DA779D0AE104BC34C960B002377068AB4B5A1F984"
101 "      3FBA91F537F1B7CAC4D8DD6D89B0D863AF7025D549F9C765D2FC07EE208F8D15#)"
102 "  (y #64B11EF8871BE4AB572AA810D5D3CA11A6CDBC637A8014602C72960DB135BF46"
103 "      A1816A724C34F87330FC9E187C5D66897A04535CC2AC9164A7150ABFA8179827"
104 "      6E45831AB811EEE848EBB24D9F5F2883B6E5DDC4C659DEF944DCFD80BF4D0A20"
105 "      42CAA7DC289F0C5A9D155F02D3D551DB741A81695B74D4C8F477F9C7838EB0FB#)))";
106 #endif /*0*/
107
108 /* 2048 DSA key from RFC 6979 A.2.2 */
109 static const char sample_public_key_2048[] =
110 "(public-key"
111 " (dsa"
112 "  (p #9DB6FB5951B66BB6FE1E140F1D2CE5502374161FD6538DF1648218642F0B5C48C8F7A41AADFA187324B87674FA1822B00F1ECF8136943D7C55757264E5A1A44FFE012E9936E00C1D3E9310B01C7D179805D3058B2A9F4BB6F9716BFE6117C6B5B3CC4D9BE341104AD4A80AD6C94E005F4B993E14F091EB51743BF33050C38DE235567E1B34C3D6A5C0CEAA1A0F368213C3D19843D0B4B09DCB9FC72D39C8DE41F1BF14D4BB4563CA28371621CAD3324B6A2D392145BEBFAC748805236F5CA2FE92B871CD8F9C36D3292B5509CA8CAA77A2ADFC7BFD77DDA6F71125A7456FEA153E433256A2261C6A06ED3693797E7995FAD5AABBCFBE3EDA2741E375404AE25B#)"
113 "  (q #F2C3119374CE76C9356990B465374A17F23F9ED35089BD969F61C6DDE9998C1F#)"
114 "  (g #5C7FF6B06F8F143FE8288433493E4769C4D988ACE5BE25A0E24809670716C613D7B0CEE6932F8FAA7C44D2CB24523DA53FBE4F6EC3595892D1AA58C4328A06C46A15662E7EAA703A1DECF8BBB2D05DBE2EB956C142A338661D10461C0D135472085057F3494309FFA73C611F78B32ADBB5740C361C9F35BE90997DB2014E2EF5AA61782F52ABEB8BD6432C4DD097BC5423B285DAFB60DC364E8161F4A2A35ACA3A10B1C4D203CC76A470A33AFDCBDD92959859ABD8B56E1725252D78EAC66E71BA9AE3F1DD2487199874393CD4D832186800654760E1E34C09E4D155179F9EC0DC4473F996BDCE6EED1CABED8B6F116F7AD9CF505DF0F998E34AB27514B0FFE7#)"
115 "  (y #667098C654426C78D7F8201EAC6C203EF030D43605032C2F1FA937E5237DBD949F34A0A2564FE126DC8B715C5141802CE0979C8246463C40E6B6BDAA2513FA611728716C2E4FD53BC95B89E69949D96512E873B9C8F8DFD499CC312882561ADECB31F658E934C0C197F2C4D96B05CBAD67381E7B768891E4DA3843D24D94CDFB5126E9B8BF21E8358EE0E0A30EF13FD6A664C0DCE3731F7FB49A4845A4FD8254687972A2D382599C9BAC4E0ED7998193078913032558134976410B89D2C171D123AC35FD977219597AA7D15C1A9A428E59194F75C721EBCBCFAE44696A499AFA74E04299F132026601638CB87AB79190D4A0986315DA8EEC6561C938996BEADF#)))";
116
117 static const char sample_secret_key_2048[] =
118 "(private-key"
119 " (dsa"
120 "  (p #9DB6FB5951B66BB6FE1E140F1D2CE5502374161FD6538DF1648218642F0B5C48C8F7A41AADFA187324B87674FA1822B00F1ECF8136943D7C55757264E5A1A44FFE012E9936E00C1D3E9310B01C7D179805D3058B2A9F4BB6F9716BFE6117C6B5B3CC4D9BE341104AD4A80AD6C94E005F4B993E14F091EB51743BF33050C38DE235567E1B34C3D6A5C0CEAA1A0F368213C3D19843D0B4B09DCB9FC72D39C8DE41F1BF14D4BB4563CA28371621CAD3324B6A2D392145BEBFAC748805236F5CA2FE92B871CD8F9C36D3292B5509CA8CAA77A2ADFC7BFD77DDA6F71125A7456FEA153E433256A2261C6A06ED3693797E7995FAD5AABBCFBE3EDA2741E375404AE25B#)"
121 "  (q #F2C3119374CE76C9356990B465374A17F23F9ED35089BD969F61C6DDE9998C1F#)"
122 "  (g #5C7FF6B06F8F143FE8288433493E4769C4D988ACE5BE25A0E24809670716C613D7B0CEE6932F8FAA7C44D2CB24523DA53FBE4F6EC3595892D1AA58C4328A06C46A15662E7EAA703A1DECF8BBB2D05DBE2EB956C142A338661D10461C0D135472085057F3494309FFA73C611F78B32ADBB5740C361C9F35BE90997DB2014E2EF5AA61782F52ABEB8BD6432C4DD097BC5423B285DAFB60DC364E8161F4A2A35ACA3A10B1C4D203CC76A470A33AFDCBDD92959859ABD8B56E1725252D78EAC66E71BA9AE3F1DD2487199874393CD4D832186800654760E1E34C09E4D155179F9EC0DC4473F996BDCE6EED1CABED8B6F116F7AD9CF505DF0F998E34AB27514B0FFE7#)"
123 "  (y #667098C654426C78D7F8201EAC6C203EF030D43605032C2F1FA937E5237DBD949F34A0A2564FE126DC8B715C5141802CE0979C8246463C40E6B6BDAA2513FA611728716C2E4FD53BC95B89E69949D96512E873B9C8F8DFD499CC312882561ADECB31F658E934C0C197F2C4D96B05CBAD67381E7B768891E4DA3843D24D94CDFB5126E9B8BF21E8358EE0E0A30EF13FD6A664C0DCE3731F7FB49A4845A4FD8254687972A2D382599C9BAC4E0ED7998193078913032558134976410B89D2C171D123AC35FD977219597AA7D15C1A9A428E59194F75C721EBCBCFAE44696A499AFA74E04299F132026601638CB87AB79190D4A0986315DA8EEC6561C938996BEADF#)"
124 "  (x #69C7548C21D0DFEA6B9A51C9EAD4E27C33D3B3F180316E5BCAB92C933F0E4DBC#)))";
125
126
127 \f
128 static int test_keys (DSA_secret_key *sk, unsigned int qbits);
129 static int check_secret_key (DSA_secret_key *sk);
130 static gpg_err_code_t generate (DSA_secret_key *sk,
131                                 unsigned int nbits,
132                                 unsigned int qbits,
133                                 int transient_key,
134                                 dsa_domain_t *domain,
135                                 gcry_mpi_t **ret_factors);
136 static gpg_err_code_t sign (gcry_mpi_t r, gcry_mpi_t s, gcry_mpi_t input,
137                             DSA_secret_key *skey, int flags, int hashalgo);
138 static gpg_err_code_t verify (gcry_mpi_t r, gcry_mpi_t s, gcry_mpi_t input,
139                    DSA_public_key *pkey);
140 static unsigned int dsa_get_nbits (gcry_sexp_t parms);
141
142
143 static void (*progress_cb) (void *,const char *, int, int, int );
144 static void *progress_cb_data;
145
146
147 void
148 _gcry_register_pk_dsa_progress (void (*cb) (void *, const char *,
149                                             int, int, int),
150                                 void *cb_data)
151 {
152   progress_cb = cb;
153   progress_cb_data = cb_data;
154 }
155
156
157 static void
158 progress (int c)
159 {
160   if (progress_cb)
161     progress_cb (progress_cb_data, "pk_dsa", c, 0, 0);
162 }
163
164
165 /* Check that a freshly generated key actually works.  Returns 0 on success. */
166 static int
167 test_keys (DSA_secret_key *sk, unsigned int qbits)
168 {
169   int result = -1;  /* Default to failure.  */
170   DSA_public_key pk;
171   gcry_mpi_t data  = mpi_new (qbits);
172   gcry_mpi_t sig_a = mpi_new (qbits);
173   gcry_mpi_t sig_b = mpi_new (qbits);
174
175   /* Put the relevant parameters into a public key structure.  */
176   pk.p = sk->p;
177   pk.q = sk->q;
178   pk.g = sk->g;
179   pk.y = sk->y;
180
181   /* Create a random plaintext.  */
182   _gcry_mpi_randomize (data, qbits, GCRY_WEAK_RANDOM);
183
184   /* Sign DATA using the secret key.  */
185   sign (sig_a, sig_b, data, sk, 0, 0);
186
187   /* Verify the signature using the public key.  */
188   if ( verify (sig_a, sig_b, data, &pk) )
189     goto leave; /* Signature does not match.  */
190
191   /* Modify the data and check that the signing fails.  */
192   mpi_add_ui (data, data, 1);
193   if ( !verify (sig_a, sig_b, data, &pk) )
194     goto leave; /* Signature matches but should not.  */
195
196   result = 0; /* The test succeeded.  */
197
198  leave:
199   _gcry_mpi_release (sig_b);
200   _gcry_mpi_release (sig_a);
201   _gcry_mpi_release (data);
202   return result;
203 }
204
205
206
207 /*
208    Generate a DSA key pair with a key of size NBITS.  If transient_key
209    is true the key is generated using the standard RNG and not the
210    very secure one.
211
212    Returns: 2 structures filled with all needed values
213             and an array with the n-1 factors of (p-1)
214  */
215 static gpg_err_code_t
216 generate (DSA_secret_key *sk, unsigned int nbits, unsigned int qbits,
217           int transient_key, dsa_domain_t *domain, gcry_mpi_t **ret_factors )
218 {
219   gpg_err_code_t rc;
220   gcry_mpi_t p;    /* the prime */
221   gcry_mpi_t q;    /* the 160 bit prime factor */
222   gcry_mpi_t g;    /* the generator */
223   gcry_mpi_t y;    /* g^x mod p */
224   gcry_mpi_t x;    /* the secret exponent */
225   gcry_mpi_t h, e;  /* helper */
226   unsigned char *rndbuf;
227   gcry_random_level_t random_level;
228
229   if (qbits)
230     ; /* Caller supplied qbits.  Use this value.  */
231   else if ( nbits >= 512 && nbits <= 1024 )
232     qbits = 160;
233   else if ( nbits == 2048 )
234     qbits = 224;
235   else if ( nbits == 3072 )
236     qbits = 256;
237   else if ( nbits == 7680 )
238     qbits = 384;
239   else if ( nbits == 15360 )
240     qbits = 512;
241   else
242     return GPG_ERR_INV_VALUE;
243
244   if (qbits < 160 || qbits > 512 || (qbits%8) )
245     return GPG_ERR_INV_VALUE;
246   if (nbits < 2*qbits || nbits > 15360)
247     return GPG_ERR_INV_VALUE;
248
249   if (fips_mode ())
250     {
251       if (nbits < 1024)
252         return GPG_ERR_INV_VALUE;
253       if (transient_key)
254         return GPG_ERR_INV_VALUE;
255     }
256
257   if (domain->p && domain->q && domain->g)
258     {
259       /* Domain parameters are given; use them.  */
260       p = mpi_copy (domain->p);
261       q = mpi_copy (domain->q);
262       g = mpi_copy (domain->g);
263       gcry_assert (mpi_get_nbits (p) == nbits);
264       gcry_assert (mpi_get_nbits (q) == qbits);
265       h = mpi_alloc (0);
266       e = NULL;
267     }
268   else
269     {
270       /* Generate new domain parameters.  */
271       rc = _gcry_generate_elg_prime (1, nbits, qbits, NULL, &p, ret_factors);
272       if (rc)
273         return rc;
274
275       /* Get q out of factors.  */
276       q = mpi_copy ((*ret_factors)[0]);
277       gcry_assert (mpi_get_nbits (q) == qbits);
278
279       /* Find a generator g (h and e are helpers).
280          e = (p-1)/q */
281       e = mpi_alloc (mpi_get_nlimbs (p));
282       mpi_sub_ui (e, p, 1);
283       mpi_fdiv_q (e, e, q);
284       g = mpi_alloc (mpi_get_nlimbs (p));
285       h = mpi_alloc_set_ui (1); /* (We start with 2.) */
286       do
287         {
288           mpi_add_ui (h, h, 1);
289           /* g = h^e mod p */
290           mpi_powm (g, h, e, p);
291         }
292       while (!mpi_cmp_ui (g, 1));  /* Continue until g != 1. */
293     }
294
295   /* Select a random number X with the property:
296    *     0 < x < q-1
297    *
298    * FIXME: Why do we use the requirement x < q-1 ? It should be
299    * sufficient to test for x < q.  FIPS-186-3 check x < q-1 but it
300    * does not check for 0 < x because it makes sure that Q is unsigned
301    * and finally adds one to the result so that 0 will never be
302    * returned.  We should replace the code below with _gcry_dsa_gen_k.
303    *
304    * This must be a very good random number because this is the secret
305    * part.  The random quality depends on the transient_key flag.  */
306   random_level = transient_key ? GCRY_STRONG_RANDOM : GCRY_VERY_STRONG_RANDOM;
307   if (DBG_CIPHER)
308     log_debug("choosing a random x%s\n", transient_key? " (transient-key)":"");
309   gcry_assert( qbits >= 160 );
310   x = mpi_alloc_secure( mpi_get_nlimbs(q) );
311   mpi_sub_ui( h, q, 1 );  /* put q-1 into h */
312   rndbuf = NULL;
313   do
314     {
315       if( DBG_CIPHER )
316         progress('.');
317       if( !rndbuf )
318         rndbuf = _gcry_random_bytes_secure ((qbits+7)/8, random_level);
319       else
320         { /* Change only some of the higher bits (= 2 bytes)*/
321           char *r = _gcry_random_bytes_secure (2, random_level);
322           memcpy(rndbuf, r, 2 );
323           xfree(r);
324         }
325
326       _gcry_mpi_set_buffer( x, rndbuf, (qbits+7)/8, 0 );
327       mpi_clear_highbit( x, qbits+1 );
328     }
329   while ( !( mpi_cmp_ui( x, 0 )>0 && mpi_cmp( x, h )<0 ) );
330   xfree(rndbuf);
331   mpi_free( e );
332   mpi_free( h );
333
334   /* y = g^x mod p */
335   y = mpi_alloc( mpi_get_nlimbs(p) );
336   mpi_powm (y, g, x, p);
337
338   if( DBG_CIPHER )
339     {
340       progress('\n');
341       log_mpidump("dsa  p", p );
342       log_mpidump("dsa  q", q );
343       log_mpidump("dsa  g", g );
344       log_mpidump("dsa  y", y );
345       log_mpidump("dsa  x", x );
346     }
347
348   /* Copy the stuff to the key structures. */
349   sk->p = p;
350   sk->q = q;
351   sk->g = g;
352   sk->y = y;
353   sk->x = x;
354
355   /* Now we can test our keys (this should never fail!). */
356   if ( test_keys (sk, qbits) )
357     {
358       _gcry_mpi_release (sk->p); sk->p = NULL;
359       _gcry_mpi_release (sk->q); sk->q = NULL;
360       _gcry_mpi_release (sk->g); sk->g = NULL;
361       _gcry_mpi_release (sk->y); sk->y = NULL;
362       _gcry_mpi_release (sk->x); sk->x = NULL;
363       fips_signal_error ("self-test after key generation failed");
364       return GPG_ERR_SELFTEST_FAILED;
365     }
366   return 0;
367 }
368
369
370 /* Generate a DSA key pair with a key of size NBITS using the
371    algorithm given in FIPS-186-3.  If USE_FIPS186_2 is true,
372    FIPS-186-2 is used and thus the length is restricted to 1024/160.
373    If DERIVEPARMS is not NULL it may contain a seed value.  If domain
374    parameters are specified in DOMAIN, DERIVEPARMS may not be given
375    and NBITS and QBITS must match the specified domain parameters.  */
376 static gpg_err_code_t
377 generate_fips186 (DSA_secret_key *sk, unsigned int nbits, unsigned int qbits,
378                   gcry_sexp_t deriveparms, int use_fips186_2,
379                   dsa_domain_t *domain,
380                   int *r_counter, void **r_seed, size_t *r_seedlen,
381                   gcry_mpi_t *r_h)
382 {
383   gpg_err_code_t ec;
384   struct {
385     gcry_sexp_t sexp;
386     const void *seed;
387     size_t seedlen;
388   } initial_seed = { NULL, NULL, 0 };
389   gcry_mpi_t prime_q = NULL;
390   gcry_mpi_t prime_p = NULL;
391   gcry_mpi_t value_g = NULL; /* The generator. */
392   gcry_mpi_t value_y = NULL; /* g^x mod p */
393   gcry_mpi_t value_x = NULL; /* The secret exponent. */
394   gcry_mpi_t value_h = NULL; /* Helper.  */
395   gcry_mpi_t value_e = NULL; /* Helper.  */
396   gcry_mpi_t value_c = NULL; /* helper for x */
397   gcry_mpi_t value_qm2 = NULL; /* q - 2 */
398
399   /* Preset return values.  */
400   *r_counter = 0;
401   *r_seed = NULL;
402   *r_seedlen = 0;
403   *r_h = NULL;
404
405   /* Derive QBITS from NBITS if requested  */
406   if (!qbits)
407     {
408       if (nbits == 1024)
409         qbits = 160;
410       else if (nbits == 2048)
411         qbits = 224;
412       else if (nbits == 3072)
413         qbits = 256;
414     }
415
416   /* Check that QBITS and NBITS match the standard.  Note that FIPS
417      186-3 uses N for QBITS and L for NBITS.  */
418   if (nbits == 1024 && qbits == 160 && use_fips186_2)
419     ; /* Allowed in FIPS 186-2 mode.  */
420   else if (nbits == 2048 && qbits == 224)
421     ;
422   else if (nbits == 2048 && qbits == 256)
423     ;
424   else if (nbits == 3072 && qbits == 256)
425     ;
426   else
427     return GPG_ERR_INV_VALUE;
428
429   if (domain->p && domain->q && domain->g)
430     {
431       /* Domain parameters are given; use them.  */
432       prime_p = mpi_copy (domain->p);
433       prime_q = mpi_copy (domain->q);
434       value_g = mpi_copy (domain->g);
435       gcry_assert (mpi_get_nbits (prime_p) == nbits);
436       gcry_assert (mpi_get_nbits (prime_q) == qbits);
437       gcry_assert (!deriveparms);
438       ec = 0;
439     }
440   else
441     {
442       /* Generate new domain parameters.  */
443
444       /* Get an initial seed value.  */
445       if (deriveparms)
446         {
447           initial_seed.sexp = sexp_find_token (deriveparms, "seed", 0);
448           if (initial_seed.sexp)
449             initial_seed.seed = sexp_nth_data (initial_seed.sexp, 1,
450                                                &initial_seed.seedlen);
451         }
452
453       if (use_fips186_2)
454         ec = _gcry_generate_fips186_2_prime (nbits, qbits,
455                                              initial_seed.seed,
456                                              initial_seed.seedlen,
457                                              &prime_q, &prime_p,
458                                              r_counter,
459                                              r_seed, r_seedlen);
460       else
461         ec = _gcry_generate_fips186_3_prime (nbits, qbits, NULL, 0,
462                                              &prime_q, &prime_p,
463                                              r_counter,
464                                              r_seed, r_seedlen, NULL);
465       sexp_release (initial_seed.sexp);
466       if (ec)
467         goto leave;
468
469       /* Find a generator g (h and e are helpers).
470        *    e = (p-1)/q
471        */
472       value_e = mpi_alloc_like (prime_p);
473       mpi_sub_ui (value_e, prime_p, 1);
474       mpi_fdiv_q (value_e, value_e, prime_q );
475       value_g = mpi_alloc_like (prime_p);
476       value_h = mpi_alloc_set_ui (1);
477       do
478         {
479           mpi_add_ui (value_h, value_h, 1);
480           /* g = h^e mod p */
481           mpi_powm (value_g, value_h, value_e, prime_p);
482         }
483       while (!mpi_cmp_ui (value_g, 1));  /* Continue until g != 1.  */
484     }
485
486   value_c = mpi_snew (qbits);
487   value_x = mpi_snew (qbits);
488   value_qm2 = mpi_snew (qbits);
489   mpi_sub_ui (value_qm2, prime_q, 2);
490
491   /* FIPS 186-4 B.1.2 steps 4-6 */
492   do
493     {
494       if( DBG_CIPHER )
495         progress('.');
496       _gcry_mpi_randomize (value_c, qbits, GCRY_VERY_STRONG_RANDOM);
497       mpi_clear_highbit (value_c, qbits+1);
498     }
499   while (!(mpi_cmp_ui (value_c, 0) > 0 && mpi_cmp (value_c, value_qm2) < 0));
500   /* while (mpi_cmp (value_c, value_qm2) > 0); */
501
502   /* x = c + 1 */
503   mpi_add_ui(value_x, value_c, 1);
504
505   /* y = g^x mod p */
506   value_y = mpi_alloc_like (prime_p);
507   mpi_powm (value_y, value_g, value_x, prime_p);
508
509   if (DBG_CIPHER)
510     {
511       progress('\n');
512       log_mpidump("dsa  p", prime_p );
513       log_mpidump("dsa  q", prime_q );
514       log_mpidump("dsa  g", value_g );
515       log_mpidump("dsa  y", value_y );
516       log_mpidump("dsa  x", value_x );
517       log_mpidump("dsa  h", value_h );
518     }
519
520   /* Copy the stuff to the key structures. */
521   sk->p = prime_p; prime_p = NULL;
522   sk->q = prime_q; prime_q = NULL;
523   sk->g = value_g; value_g = NULL;
524   sk->y = value_y; value_y = NULL;
525   sk->x = value_x; value_x = NULL;
526   *r_h = value_h; value_h = NULL;
527
528  leave:
529   _gcry_mpi_release (prime_p);
530   _gcry_mpi_release (prime_q);
531   _gcry_mpi_release (value_g);
532   _gcry_mpi_release (value_y);
533   _gcry_mpi_release (value_x);
534   _gcry_mpi_release (value_h);
535   _gcry_mpi_release (value_e);
536   _gcry_mpi_release (value_c);
537   _gcry_mpi_release (value_qm2);
538
539   /* As a last step test this keys (this should never fail of course). */
540   if (!ec && test_keys (sk, qbits) )
541     {
542       _gcry_mpi_release (sk->p); sk->p = NULL;
543       _gcry_mpi_release (sk->q); sk->q = NULL;
544       _gcry_mpi_release (sk->g); sk->g = NULL;
545       _gcry_mpi_release (sk->y); sk->y = NULL;
546       _gcry_mpi_release (sk->x); sk->x = NULL;
547       fips_signal_error ("self-test after key generation failed");
548       ec = GPG_ERR_SELFTEST_FAILED;
549     }
550
551   if (ec)
552     {
553       *r_counter = 0;
554       xfree (*r_seed); *r_seed = NULL;
555       *r_seedlen = 0;
556       _gcry_mpi_release (*r_h); *r_h = NULL;
557     }
558
559   return ec;
560 }
561
562
563
564 /*
565    Test whether the secret key is valid.
566    Returns: if this is a valid key.
567  */
568 static int
569 check_secret_key( DSA_secret_key *sk )
570 {
571   int rc;
572   gcry_mpi_t y = mpi_alloc( mpi_get_nlimbs(sk->y) );
573
574   mpi_powm( y, sk->g, sk->x, sk->p );
575   rc = !mpi_cmp( y, sk->y );
576   mpi_free( y );
577   return rc;
578 }
579
580
581
582 /*
583    Make a DSA signature from INPUT and put it into r and s.
584
585    INPUT may either be a plain MPI or an opaque MPI which is then
586    internally converted to a plain MPI.  FLAGS and HASHALGO may both
587    be 0 for standard operation mode.
588
589    The return value is 0 on success or an error code.  Note that for
590    backward compatibility the function will not return any error if
591    FLAGS and HASHALGO are both 0 and INPUT is a plain MPI.
592  */
593 static gpg_err_code_t
594 sign (gcry_mpi_t r, gcry_mpi_t s, gcry_mpi_t input, DSA_secret_key *skey,
595       int flags, int hashalgo)
596 {
597   gpg_err_code_t rc;
598   gcry_mpi_t hash;
599   gcry_mpi_t k;
600   gcry_mpi_t kinv;
601   gcry_mpi_t tmp;
602   const void *abuf;
603   unsigned int abits, qbits;
604   int extraloops = 0;
605
606   qbits = mpi_get_nbits (skey->q);
607
608   /* Convert the INPUT into an MPI.  */
609   rc = _gcry_dsa_normalize_hash (input, &hash, qbits);
610   if (rc)
611     return rc;
612
613  again:
614   /* Create the K value.  */
615   if ((flags & PUBKEY_FLAG_RFC6979) && hashalgo)
616     {
617       /* Use Pornin's method for deterministic DSA.  If this flag is
618          set, it is expected that HASH is an opaque MPI with the to be
619          signed hash.  That hash is also used as h1 from 3.2.a.  */
620       if (!mpi_is_opaque (input))
621         {
622           rc = GPG_ERR_CONFLICT;
623           goto leave;
624         }
625
626       abuf = mpi_get_opaque (input, &abits);
627       rc = _gcry_dsa_gen_rfc6979_k (&k, skey->q, skey->x,
628                                     abuf, (abits+7)/8, hashalgo, extraloops);
629       if (rc)
630         goto leave;
631     }
632   else
633     {
634       /* Select a random k with 0 < k < q */
635       k = _gcry_dsa_gen_k (skey->q, GCRY_STRONG_RANDOM);
636     }
637
638   /* r = (a^k mod p) mod q */
639   mpi_powm( r, skey->g, k, skey->p );
640   mpi_fdiv_r( r, r, skey->q );
641
642   /* kinv = k^(-1) mod q */
643   kinv = mpi_alloc( mpi_get_nlimbs(k) );
644   mpi_invm(kinv, k, skey->q );
645
646   /* s = (kinv * ( hash + x * r)) mod q */
647   tmp = mpi_alloc( mpi_get_nlimbs(skey->p) );
648   mpi_mul( tmp, skey->x, r );
649   mpi_add( tmp, tmp, hash );
650   mpi_mulm( s , kinv, tmp, skey->q );
651
652   mpi_free(k);
653   mpi_free(kinv);
654   mpi_free(tmp);
655
656   if (!mpi_cmp_ui (r, 0))
657     {
658       /* This is a highly unlikely code path.  */
659       extraloops++;
660       goto again;
661     }
662
663   rc = 0;
664
665  leave:
666   if (hash != input)
667     mpi_free (hash);
668
669   return rc;
670 }
671
672
673 /*
674    Returns true if the signature composed from R and S is valid.
675  */
676 static gpg_err_code_t
677 verify (gcry_mpi_t r, gcry_mpi_t s, gcry_mpi_t input, DSA_public_key *pkey )
678 {
679   gpg_err_code_t rc = 0;
680   gcry_mpi_t w, u1, u2, v;
681   gcry_mpi_t base[3];
682   gcry_mpi_t ex[3];
683   gcry_mpi_t hash;
684   unsigned int nbits;
685
686   if( !(mpi_cmp_ui( r, 0 ) > 0 && mpi_cmp( r, pkey->q ) < 0) )
687     return GPG_ERR_BAD_SIGNATURE; /* Assertion  0 < r < n  failed.  */
688   if( !(mpi_cmp_ui( s, 0 ) > 0 && mpi_cmp( s, pkey->q ) < 0) )
689     return GPG_ERR_BAD_SIGNATURE; /* Assertion  0 < s < n  failed.  */
690
691   nbits = mpi_get_nbits (pkey->q);
692   rc = _gcry_dsa_normalize_hash (input, &hash, nbits);
693   if (rc)
694     return rc;
695
696   w  = mpi_alloc( mpi_get_nlimbs(pkey->q) );
697   u1 = mpi_alloc( mpi_get_nlimbs(pkey->q) );
698   u2 = mpi_alloc( mpi_get_nlimbs(pkey->q) );
699   v  = mpi_alloc( mpi_get_nlimbs(pkey->p) );
700
701   /* w = s^(-1) mod q */
702   mpi_invm( w, s, pkey->q );
703
704   /* u1 = (hash * w) mod q */
705   mpi_mulm( u1, hash, w, pkey->q );
706
707   /* u2 = r * w mod q  */
708   mpi_mulm( u2, r, w, pkey->q );
709
710   /* v =  g^u1 * y^u2 mod p mod q */
711   base[0] = pkey->g; ex[0] = u1;
712   base[1] = pkey->y; ex[1] = u2;
713   base[2] = NULL;    ex[2] = NULL;
714   mpi_mulpowm( v, base, ex, pkey->p );
715   mpi_fdiv_r( v, v, pkey->q );
716
717   if (mpi_cmp( v, r ))
718     {
719       if (DBG_CIPHER)
720         {
721           log_mpidump ("     i", input);
722           log_mpidump ("     h", hash);
723           log_mpidump ("     v", v);
724           log_mpidump ("     r", r);
725           log_mpidump ("     s", s);
726         }
727       rc = GPG_ERR_BAD_SIGNATURE;
728     }
729
730   mpi_free(w);
731   mpi_free(u1);
732   mpi_free(u2);
733   mpi_free(v);
734   if (hash != input)
735     mpi_free (hash);
736
737   return rc;
738 }
739
740
741 /*********************************************
742  **************  interface  ******************
743  *********************************************/
744
745 static gcry_err_code_t
746 dsa_generate (const gcry_sexp_t genparms, gcry_sexp_t *r_skey)
747 {
748   gpg_err_code_t rc;
749   unsigned int nbits;
750   gcry_sexp_t domainsexp;
751   DSA_secret_key sk;
752   gcry_sexp_t l1;
753   unsigned int qbits = 0;
754   gcry_sexp_t deriveparms = NULL;
755   gcry_sexp_t seedinfo = NULL;
756   gcry_sexp_t misc_info = NULL;
757   int flags = 0;
758   dsa_domain_t domain;
759   gcry_mpi_t *factors = NULL;
760
761   memset (&sk, 0, sizeof sk);
762   memset (&domain, 0, sizeof domain);
763
764   rc = _gcry_pk_util_get_nbits (genparms, &nbits);
765   if (rc)
766     return rc;
767
768   /* Parse the optional flags list.  */
769   l1 = sexp_find_token (genparms, "flags", 0);
770   if (l1)
771     {
772       rc = _gcry_pk_util_parse_flaglist (l1, &flags, NULL);
773       sexp_release (l1);
774       if (rc)
775         return rc;\
776     }
777
778   /* Parse the optional qbits element.  */
779   l1 = sexp_find_token (genparms, "qbits", 0);
780   if (l1)
781     {
782       char buf[50];
783       const char *s;
784       size_t n;
785
786       s = sexp_nth_data (l1, 1, &n);
787       if (!s || n >= DIM (buf) - 1 )
788         {
789           sexp_release (l1);
790           return GPG_ERR_INV_OBJ; /* No value or value too large.  */
791         }
792       memcpy (buf, s, n);
793       buf[n] = 0;
794       qbits = (unsigned int)strtoul (buf, NULL, 0);
795       sexp_release (l1);
796     }
797
798   /* Parse the optional transient-key flag.  */
799   if (!(flags & PUBKEY_FLAG_TRANSIENT_KEY))
800     {
801       l1 = sexp_find_token (genparms, "transient-key", 0);
802       if (l1)
803         {
804           flags |= PUBKEY_FLAG_TRANSIENT_KEY;
805           sexp_release (l1);
806         }
807     }
808
809   /* Get the optional derive parameters.  */
810   deriveparms = sexp_find_token (genparms, "derive-parms", 0);
811
812   /* Parse the optional "use-fips186" flags.  */
813   if (!(flags & PUBKEY_FLAG_USE_FIPS186))
814     {
815       l1 = sexp_find_token (genparms, "use-fips186", 0);
816       if (l1)
817         {
818           flags |= PUBKEY_FLAG_USE_FIPS186;
819           sexp_release (l1);
820         }
821     }
822   if (!(flags & PUBKEY_FLAG_USE_FIPS186_2))
823     {
824       l1 = sexp_find_token (genparms, "use-fips186-2", 0);
825       if (l1)
826         {
827           flags |= PUBKEY_FLAG_USE_FIPS186_2;
828           sexp_release (l1);
829         }
830     }
831
832   /* Check whether domain parameters are given.  */
833   domainsexp = sexp_find_token (genparms, "domain", 0);
834   if (domainsexp)
835     {
836       /* DERIVEPARMS can't be used together with domain parameters.
837          NBITS abnd QBITS may not be specified because there values
838          are derived from the domain parameters.  */
839       if (deriveparms || qbits || nbits)
840         {
841           sexp_release (domainsexp);
842           sexp_release (deriveparms);
843           return GPG_ERR_INV_VALUE;
844         }
845
846       /* Put all domain parameters into the domain object.  */
847       l1 = sexp_find_token (domainsexp, "p", 0);
848       domain.p = sexp_nth_mpi (l1, 1, GCRYMPI_FMT_USG);
849       sexp_release (l1);
850       l1 = sexp_find_token (domainsexp, "q", 0);
851       domain.q = sexp_nth_mpi (l1, 1, GCRYMPI_FMT_USG);
852       sexp_release (l1);
853       l1 = sexp_find_token (domainsexp, "g", 0);
854       domain.g = sexp_nth_mpi (l1, 1, GCRYMPI_FMT_USG);
855       sexp_release (l1);
856       sexp_release (domainsexp);
857
858       /* Check that all domain parameters are available.  */
859       if (!domain.p || !domain.q || !domain.g)
860         {
861           _gcry_mpi_release (domain.p);
862           _gcry_mpi_release (domain.q);
863           _gcry_mpi_release (domain.g);
864           sexp_release (deriveparms);
865           return GPG_ERR_MISSING_VALUE;
866         }
867
868       /* Get NBITS and QBITS from the domain parameters.  */
869       nbits = mpi_get_nbits (domain.p);
870       qbits = mpi_get_nbits (domain.q);
871     }
872
873   if (deriveparms
874       || (flags & PUBKEY_FLAG_USE_FIPS186)
875       || (flags & PUBKEY_FLAG_USE_FIPS186_2)
876       || fips_mode ())
877     {
878       int counter;
879       void *seed;
880       size_t seedlen;
881       gcry_mpi_t h_value;
882
883       rc = generate_fips186 (&sk, nbits, qbits, deriveparms,
884                              !!(flags & PUBKEY_FLAG_USE_FIPS186_2),
885                              &domain,
886                              &counter, &seed, &seedlen, &h_value);
887       if (!rc && h_value)
888         {
889           /* Format the seed-values unless domain parameters are used
890              for which a H_VALUE of NULL is an indication.  */
891           rc = sexp_build (&seedinfo, NULL,
892                            "(seed-values(counter %d)(seed %b)(h %m))",
893                            counter, (int)seedlen, seed, h_value);
894           xfree (seed);
895           _gcry_mpi_release (h_value);
896         }
897     }
898   else
899     {
900       rc = generate (&sk, nbits, qbits,
901                      !!(flags & PUBKEY_FLAG_TRANSIENT_KEY),
902                      &domain, &factors);
903     }
904
905   if (!rc)
906     {
907       /* Put the factors into MISC_INFO.  Note that the factors are
908          not confidential thus we can store them in standard memory.  */
909       int nfactors, i, j;
910       char *p;
911       char *format = NULL;
912       void **arg_list = NULL;
913
914       for (nfactors=0; factors && factors[nfactors]; nfactors++)
915         ;
916       /* Allocate space for the format string:
917          "(misc-key-info%S(pm1-factors%m))"
918          with one "%m" for each factor and construct it.  */
919       format = xtrymalloc (50 + 2*nfactors);
920       if (!format)
921         rc = gpg_err_code_from_syserror ();
922       else
923         {
924           p = stpcpy (format, "(misc-key-info");
925           if (seedinfo)
926             p = stpcpy (p, "%S");
927           if (nfactors)
928             {
929               p = stpcpy (p, "(pm1-factors");
930               for (i=0; i < nfactors; i++)
931                 p = stpcpy (p, "%m");
932               p = stpcpy (p, ")");
933             }
934           p = stpcpy (p, ")");
935
936           /* Allocate space for the list of factors plus one for the
937              seedinfo s-exp plus an extra NULL entry for safety and
938              fill it with the factors.  */
939           arg_list = xtrycalloc (nfactors+1+1, sizeof *arg_list);
940           if (!arg_list)
941             rc = gpg_err_code_from_syserror ();
942           else
943             {
944               i = 0;
945               if (seedinfo)
946                 arg_list[i++] = &seedinfo;
947               for (j=0; j < nfactors; j++)
948                 arg_list[i++] = factors + j;
949               arg_list[i] = NULL;
950
951               rc = sexp_build_array (&misc_info, NULL, format, arg_list);
952             }
953         }
954
955       xfree (arg_list);
956       xfree (format);
957     }
958
959   if (!rc)
960     rc = sexp_build (r_skey, NULL,
961                      "(key-data"
962                      " (public-key"
963                      "  (dsa(p%m)(q%m)(g%m)(y%m)))"
964                      " (private-key"
965                      "  (dsa(p%m)(q%m)(g%m)(y%m)(x%m)))"
966                      " %S)",
967                      sk.p, sk.q, sk.g, sk.y,
968                      sk.p, sk.q, sk.g, sk.y, sk.x,
969                      misc_info);
970
971
972   _gcry_mpi_release (sk.p);
973   _gcry_mpi_release (sk.q);
974   _gcry_mpi_release (sk.g);
975   _gcry_mpi_release (sk.y);
976   _gcry_mpi_release (sk.x);
977
978   _gcry_mpi_release (domain.p);
979   _gcry_mpi_release (domain.q);
980   _gcry_mpi_release (domain.g);
981
982   sexp_release (seedinfo);
983   sexp_release (misc_info);
984   sexp_release (deriveparms);
985   if (factors)
986     {
987       gcry_mpi_t *mp;
988       for (mp = factors; *mp; mp++)
989         mpi_free (*mp);
990       xfree (factors);
991     }
992   return rc;
993 }
994
995
996
997 static gcry_err_code_t
998 dsa_check_secret_key (gcry_sexp_t keyparms)
999 {
1000   gcry_err_code_t rc;
1001   DSA_secret_key sk = {NULL, NULL, NULL, NULL, NULL};
1002
1003   rc = _gcry_sexp_extract_param (keyparms, NULL, "pqgyx",
1004                                   &sk.p, &sk.q, &sk.g, &sk.y, &sk.x,
1005                                   NULL);
1006   if (rc)
1007     goto leave;
1008
1009   if (!check_secret_key (&sk))
1010     rc = GPG_ERR_BAD_SECKEY;
1011
1012  leave:
1013   _gcry_mpi_release (sk.p);
1014   _gcry_mpi_release (sk.q);
1015   _gcry_mpi_release (sk.g);
1016   _gcry_mpi_release (sk.y);
1017   _gcry_mpi_release (sk.x);
1018   if (DBG_CIPHER)
1019     log_debug ("dsa_testkey    => %s\n", gpg_strerror (rc));
1020   return rc;
1021 }
1022
1023
1024 static gcry_err_code_t
1025 dsa_sign (gcry_sexp_t *r_sig, gcry_sexp_t s_data, gcry_sexp_t keyparms)
1026 {
1027   gcry_err_code_t rc;
1028   struct pk_encoding_ctx ctx;
1029   gcry_mpi_t data = NULL;
1030   DSA_secret_key sk = {NULL, NULL, NULL, NULL, NULL};
1031   gcry_mpi_t sig_r = NULL;
1032   gcry_mpi_t sig_s = NULL;
1033
1034   _gcry_pk_util_init_encoding_ctx (&ctx, PUBKEY_OP_SIGN,
1035                                    dsa_get_nbits (keyparms));
1036
1037   /* Extract the data.  */
1038   rc = _gcry_pk_util_data_to_mpi (s_data, &data, &ctx);
1039   if (rc)
1040     goto leave;
1041   if (DBG_CIPHER)
1042     log_mpidump ("dsa_sign   data", data);
1043
1044   /* Extract the key.  */
1045   rc = _gcry_sexp_extract_param (keyparms, NULL, "pqgyx",
1046                                  &sk.p, &sk.q, &sk.g, &sk.y, &sk.x, NULL);
1047   if (rc)
1048     goto leave;
1049   if (DBG_CIPHER)
1050     {
1051       log_mpidump ("dsa_sign      p", sk.p);
1052       log_mpidump ("dsa_sign      q", sk.q);
1053       log_mpidump ("dsa_sign      g", sk.g);
1054       log_mpidump ("dsa_sign      y", sk.y);
1055       if (!fips_mode ())
1056         log_mpidump ("dsa_sign      x", sk.x);
1057     }
1058
1059   sig_r = mpi_new (0);
1060   sig_s = mpi_new (0);
1061   rc = sign (sig_r, sig_s, data, &sk, ctx.flags, ctx.hash_algo);
1062   if (rc)
1063     goto leave;
1064   if (DBG_CIPHER)
1065     {
1066       log_mpidump ("dsa_sign  sig_r", sig_r);
1067       log_mpidump ("dsa_sign  sig_s", sig_s);
1068     }
1069   rc = sexp_build (r_sig, NULL, "(sig-val(dsa(r%M)(s%M)))", sig_r, sig_s);
1070
1071  leave:
1072   _gcry_mpi_release (sig_r);
1073   _gcry_mpi_release (sig_s);
1074   _gcry_mpi_release (sk.p);
1075   _gcry_mpi_release (sk.q);
1076   _gcry_mpi_release (sk.g);
1077   _gcry_mpi_release (sk.y);
1078   _gcry_mpi_release (sk.x);
1079   _gcry_mpi_release (data);
1080   _gcry_pk_util_free_encoding_ctx (&ctx);
1081   if (DBG_CIPHER)
1082     log_debug ("dsa_sign      => %s\n", gpg_strerror (rc));
1083   return rc;
1084 }
1085
1086
1087 static gcry_err_code_t
1088 dsa_verify (gcry_sexp_t s_sig, gcry_sexp_t s_data, gcry_sexp_t s_keyparms)
1089 {
1090   gcry_err_code_t rc;
1091   struct pk_encoding_ctx ctx;
1092   gcry_sexp_t l1 = NULL;
1093   gcry_mpi_t sig_r = NULL;
1094   gcry_mpi_t sig_s = NULL;
1095   gcry_mpi_t data = NULL;
1096   DSA_public_key pk = { NULL, NULL, NULL, NULL };
1097
1098   _gcry_pk_util_init_encoding_ctx (&ctx, PUBKEY_OP_VERIFY,
1099                                    dsa_get_nbits (s_keyparms));
1100
1101   /* Extract the data.  */
1102   rc = _gcry_pk_util_data_to_mpi (s_data, &data, &ctx);
1103   if (rc)
1104     goto leave;
1105   if (DBG_CIPHER)
1106     log_mpidump ("dsa_verify data", data);
1107
1108   /* Extract the signature value.  */
1109   rc = _gcry_pk_util_preparse_sigval (s_sig, dsa_names, &l1, NULL);
1110   if (rc)
1111     goto leave;
1112   rc = _gcry_sexp_extract_param (l1, NULL, "rs", &sig_r, &sig_s, NULL);
1113   if (rc)
1114     goto leave;
1115   if (DBG_CIPHER)
1116     {
1117       log_mpidump ("dsa_verify  s_r", sig_r);
1118       log_mpidump ("dsa_verify  s_s", sig_s);
1119     }
1120
1121   /* Extract the key.  */
1122   rc = _gcry_sexp_extract_param (s_keyparms, NULL, "pqgy",
1123                                  &pk.p, &pk.q, &pk.g, &pk.y, NULL);
1124   if (rc)
1125     goto leave;
1126   if (DBG_CIPHER)
1127     {
1128       log_mpidump ("dsa_verify    p", pk.p);
1129       log_mpidump ("dsa_verify    q", pk.q);
1130       log_mpidump ("dsa_verify    g", pk.g);
1131       log_mpidump ("dsa_verify    y", pk.y);
1132     }
1133
1134   /* Verify the signature.  */
1135   rc = verify (sig_r, sig_s, data, &pk);
1136
1137  leave:
1138   _gcry_mpi_release (pk.p);
1139   _gcry_mpi_release (pk.q);
1140   _gcry_mpi_release (pk.g);
1141   _gcry_mpi_release (pk.y);
1142   _gcry_mpi_release (data);
1143   _gcry_mpi_release (sig_r);
1144   _gcry_mpi_release (sig_s);
1145   sexp_release (l1);
1146   _gcry_pk_util_free_encoding_ctx (&ctx);
1147   if (DBG_CIPHER)
1148     log_debug ("dsa_verify    => %s\n", rc?gpg_strerror (rc):"Good");
1149   return rc;
1150 }
1151
1152
1153 /* Return the number of bits for the key described by PARMS.  On error
1154  * 0 is returned.  The format of PARMS starts with the algorithm name;
1155  * for example:
1156  *
1157  *   (dsa
1158  *     (p <mpi>)
1159  *     (q <mpi>)
1160  *     (g <mpi>)
1161  *     (y <mpi>))
1162  *
1163  * More parameters may be given but we only need P here.
1164  */
1165 static unsigned int
1166 dsa_get_nbits (gcry_sexp_t parms)
1167 {
1168   gcry_sexp_t l1;
1169   gcry_mpi_t p;
1170   unsigned int nbits;
1171
1172   l1 = sexp_find_token (parms, "p", 1);
1173   if (!l1)
1174     return 0; /* Parameter P not found.  */
1175
1176   p = sexp_nth_mpi (l1, 1, GCRYMPI_FMT_USG);
1177   sexp_release (l1);
1178   nbits = p? mpi_get_nbits (p) : 0;
1179   _gcry_mpi_release (p);
1180   return nbits;
1181 }
1182
1183
1184 \f
1185 /*
1186      Self-test section.
1187  */
1188
1189 static const char *
1190 selftest_sign (gcry_sexp_t pkey, gcry_sexp_t skey)
1191 {
1192   /* Sample data from RFC 6979 section A.2.2, hash is of message "sample" */
1193   static const char sample_data[] =
1194     "(data (flags rfc6979)"
1195     " (hash sha256 #af2bdbe1aa9b6ec1e2ade1d694f41fc71a831d0268e9891562113d8a62add1bf#))";
1196   static const char sample_data_bad[] =
1197     "(data (flags rfc6979)"
1198     " (hash sha256 #bf2bdbe1aa9b6ec1e2ade1d694f41fc71a831d0268e9891562113d8a62add1bf#))";
1199   static const char signature_r[] =
1200     "eace8bdbbe353c432a795d9ec556c6d021f7a03f42c36e9bc87e4ac7932cc809";
1201   static const char signature_s[] =
1202     "7081e175455f9247b812b74583e9e94f9ea79bd640dc962533b0680793a38d53";
1203
1204   const char *errtxt = NULL;
1205   gcry_error_t err;
1206   gcry_sexp_t data = NULL;
1207   gcry_sexp_t data_bad = NULL;
1208   gcry_sexp_t sig = NULL;
1209   gcry_sexp_t l1 = NULL;
1210   gcry_sexp_t l2 = NULL;
1211   gcry_mpi_t r = NULL;
1212   gcry_mpi_t s = NULL;
1213   gcry_mpi_t calculated_r = NULL;
1214   gcry_mpi_t calculated_s = NULL;
1215   int cmp;
1216
1217   err = sexp_sscan (&data, NULL, sample_data, strlen (sample_data));
1218   if (!err)
1219     err = sexp_sscan (&data_bad, NULL,
1220                       sample_data_bad, strlen (sample_data_bad));
1221   if (!err)
1222     err = _gcry_mpi_scan (&r, GCRYMPI_FMT_HEX, signature_r, 0, NULL);
1223   if (!err)
1224     err = _gcry_mpi_scan (&s, GCRYMPI_FMT_HEX, signature_s, 0, NULL);
1225
1226   if (err)
1227     {
1228       errtxt = "converting data failed";
1229       goto leave;
1230     }
1231
1232   err = _gcry_pk_sign (&sig, data, skey);
1233   if (err)
1234     {
1235       errtxt = "signing failed";
1236       goto leave;
1237     }
1238
1239   /* check against known signature */
1240   errtxt = "signature validity failed";
1241   l1 = _gcry_sexp_find_token (sig, "sig-val", 0);
1242   if (!l1)
1243     goto leave;
1244   l2 = _gcry_sexp_find_token (l1, "dsa", 0);
1245   if (!l2)
1246     goto leave;
1247
1248   sexp_release (l1);
1249   l1 = l2;
1250
1251   l2 = _gcry_sexp_find_token (l1, "r", 0);
1252   if (!l2)
1253     goto leave;
1254   calculated_r = _gcry_sexp_nth_mpi (l2, 1, GCRYMPI_FMT_USG);
1255   if (!calculated_r)
1256     goto leave;
1257
1258   sexp_release (l2);
1259   l2 = _gcry_sexp_find_token (l1, "s", 0);
1260   if (!l2)
1261     goto leave;
1262   calculated_s = _gcry_sexp_nth_mpi (l2, 1, GCRYMPI_FMT_USG);
1263   if (!calculated_s)
1264     goto leave;
1265
1266   errtxt = "known sig check failed";
1267
1268   cmp = _gcry_mpi_cmp (r, calculated_r);
1269   if (cmp)
1270     goto leave;
1271   cmp = _gcry_mpi_cmp (s, calculated_s);
1272   if (cmp)
1273     goto leave;
1274
1275   errtxt = NULL;
1276
1277
1278   err = _gcry_pk_verify (sig, data, pkey);
1279   if (err)
1280     {
1281       errtxt = "verify failed";
1282       goto leave;
1283     }
1284   err = _gcry_pk_verify (sig, data_bad, pkey);
1285   if (gcry_err_code (err) != GPG_ERR_BAD_SIGNATURE)
1286     {
1287       errtxt = "bad signature not detected";
1288       goto leave;
1289     }
1290
1291
1292  leave:
1293   _gcry_mpi_release (calculated_s);
1294   _gcry_mpi_release (calculated_r);
1295   _gcry_mpi_release (s);
1296   _gcry_mpi_release (r);
1297   sexp_release (l2);
1298   sexp_release (l1);
1299   sexp_release (sig);
1300   sexp_release (data_bad);
1301   sexp_release (data);
1302   return errtxt;
1303 }
1304
1305
1306 static gpg_err_code_t
1307 selftests_dsa_2048 (selftest_report_func_t report)
1308 {
1309   const char *what;
1310   const char *errtxt;
1311   gcry_error_t err;
1312   gcry_sexp_t skey = NULL;
1313   gcry_sexp_t pkey = NULL;
1314
1315   /* Convert the S-expressions into the internal representation.  */
1316   what = "convert";
1317   err = sexp_sscan (&skey, NULL, sample_secret_key_2048, strlen (sample_secret_key_2048));
1318   if (!err)
1319     err = sexp_sscan (&pkey, NULL,
1320                       sample_public_key_2048, strlen (sample_public_key_2048));
1321   if (err)
1322     {
1323       errtxt = _gcry_strerror (err);
1324       goto failed;
1325     }
1326
1327   what = "key consistency";
1328   err = _gcry_pk_testkey (skey);
1329   if (err)
1330     {
1331       errtxt = _gcry_strerror (err);
1332       goto failed;
1333     }
1334
1335   what = "sign";
1336   errtxt = selftest_sign (pkey, skey);
1337   if (errtxt)
1338     goto failed;
1339
1340   sexp_release (pkey);
1341   sexp_release (skey);
1342   return 0; /* Succeeded. */
1343
1344  failed:
1345   sexp_release (pkey);
1346   sexp_release (skey);
1347   if (report)
1348     report ("pubkey", GCRY_PK_DSA, what, errtxt);
1349   return GPG_ERR_SELFTEST_FAILED;
1350 }
1351
1352
1353 /* Run a full self-test for ALGO and return 0 on success.  */
1354 static gpg_err_code_t
1355 run_selftests (int algo, int extended, selftest_report_func_t report)
1356 {
1357   gpg_err_code_t ec;
1358
1359   (void)extended;
1360
1361   switch (algo)
1362     {
1363     case GCRY_PK_DSA:
1364       ec = selftests_dsa_2048 (report);
1365       break;
1366     default:
1367       ec = GPG_ERR_PUBKEY_ALGO;
1368       break;
1369
1370     }
1371   return ec;
1372 }
1373
1374
1375 \f
1376 gcry_pk_spec_t _gcry_pubkey_spec_dsa =
1377   {
1378     GCRY_PK_DSA, { 0, 1 },
1379     GCRY_PK_USAGE_SIGN,
1380     "DSA", dsa_names,
1381     "pqgy", "pqgyx", "", "rs", "pqgy",
1382     dsa_generate,
1383     dsa_check_secret_key,
1384     NULL,
1385     NULL,
1386     dsa_sign,
1387     dsa_verify,
1388     dsa_get_nbits,
1389     run_selftests
1390   };