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