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