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