Fixed the fips 186 dsa 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-3.  If USE_FIPS186_2 is true,
359    FIPS-186-2 is used and thus the length is restricted to 1024/160.
360    If DERIVEPARMS are not NULL the may contain a seed value. */
361 static gpg_err_code_t
362 generate_fips186 (DSA_secret_key *sk, unsigned int nbits, unsigned int qbits,
363                   gcry_sexp_t deriveparms, int use_fips186_2,
364                   int *r_counter, void **r_seed, size_t *r_seedlen,
365                   gcry_mpi_t *r_h)
366 {
367   gpg_err_code_t ec;
368   struct {
369     gcry_sexp_t sexp;
370     const void *seed;
371     size_t seedlen;
372   } initial_seed = { NULL, NULL, 0 };
373   gcry_mpi_t prime_q = NULL; 
374   gcry_mpi_t prime_p = NULL; 
375   gcry_mpi_t value_g = NULL; /* The generator. */
376   gcry_mpi_t value_y = NULL; /* g^x mod p */
377   gcry_mpi_t value_x = NULL; /* The secret exponent. */
378   gcry_mpi_t value_h = NULL; /* Helper.  */
379   gcry_mpi_t value_e = NULL; /* Helper.  */
380
381   /* Preset return values.  */
382   *r_counter = 0;
383   *r_seed = NULL;
384   *r_seedlen = 0;
385   *r_h = NULL;
386
387   /* Derive QBITS from NBITS if requested  */
388   if (!qbits)
389     {
390       if (nbits == 1024)
391         qbits = 160;
392       else if (nbits == 2048)
393         qbits = 224;
394       else if (nbits == 3072)
395         qbits = 256;
396     }
397
398   /* Check that QBITS and NBITS match the standard.  Note that FIPS
399      186-3 uses N for QBITS and L for NBITS.  */
400   if (nbits == 1024 && qbits == 160)
401     ;
402   else if (nbits == 2048 && qbits == 224)
403     ;
404   else if (nbits == 2048 && qbits == 256)
405     ;
406   else if (nbits == 3072 && qbits == 256)
407     ;
408   else
409     return GPG_ERR_INV_VALUE;
410
411   /* Get an initial seed value.  */
412   if (deriveparms)
413     {
414       initial_seed.sexp = gcry_sexp_find_token (deriveparms, "seed", 0);
415       if (initial_seed.sexp)
416         initial_seed.seed = gcry_sexp_nth_data (initial_seed.sexp, 1,
417                                                 &initial_seed.seedlen);
418     }
419
420   /* Fixme: Enable 186-3 after it has been approved and after fixing
421      the generation function.  */
422 /*   if (use_fips186_2) */
423   (void)use_fips186_2;
424     ec = _gcry_generate_fips186_2_prime (nbits, qbits, 
425                                          initial_seed.seed, 
426                                          initial_seed.seedlen,
427                                          &prime_q, &prime_p, 
428                                          r_counter,
429                                          r_seed, r_seedlen);
430 /*   else */
431 /*     ec = _gcry_generate_fips186_3_prime (nbits, qbits, NULL, 0, */
432 /*                                          &prime_q, &prime_p, */
433 /*                                          r_counter, */
434 /*                                          r_seed, r_seedlen, NULL); */
435   gcry_sexp_release (initial_seed.sexp);
436   if (ec)
437     goto leave;
438
439   /* Find a generator g (h and e are helpers).
440      e = (p-1)/q */
441   value_e = mpi_alloc_like (prime_p);
442   mpi_sub_ui (value_e, prime_p, 1);
443   mpi_fdiv_q (value_e, value_e, prime_q );
444   value_g = mpi_alloc_like (prime_p);
445   value_h = mpi_alloc_set_ui (1); 
446   do
447     {
448       mpi_add_ui (value_h, value_h, 1);
449       /* g = h^e mod p */
450       mpi_powm (value_g, value_h, value_e, prime_p);
451     } 
452   while (!mpi_cmp_ui (value_g, 1));  /* Continue until g != 1.  */
453
454   /* Select a random number x with:  0 < x < q  */
455   value_x = gcry_mpi_snew (qbits);
456   do 
457     {
458       if( DBG_CIPHER )
459         progress('.');
460       gcry_mpi_randomize (value_x, qbits, GCRY_VERY_STRONG_RANDOM);
461       mpi_clear_highbit (value_x, qbits+1);
462     } 
463   while (!(mpi_cmp_ui (value_x, 0) > 0 && mpi_cmp (value_x, prime_q) < 0));
464
465   /* y = g^x mod p */
466   value_y = mpi_alloc_like (prime_p);
467   gcry_mpi_powm (value_y, value_g, value_x, prime_p);
468
469   if (DBG_CIPHER) 
470     {
471       progress('\n');
472       log_mpidump("dsa  p", prime_p );
473       log_mpidump("dsa  q", prime_q );
474       log_mpidump("dsa  g", value_g );
475       log_mpidump("dsa  y", value_y );
476       log_mpidump("dsa  x", value_x );
477       log_mpidump("dsa  h", value_h );
478     }
479
480   /* Copy the stuff to the key structures. */
481   sk->p = prime_p; prime_p = NULL;
482   sk->q = prime_q; prime_q = NULL;
483   sk->g = value_g; value_g = NULL;
484   sk->y = value_y; value_y = NULL;
485   sk->x = value_x; value_x = NULL;
486   *r_h = value_h; value_h = NULL;
487
488  leave:
489   gcry_mpi_release (prime_p);
490   gcry_mpi_release (prime_q);
491   gcry_mpi_release (value_g);
492   gcry_mpi_release (value_y);
493   gcry_mpi_release (value_x);
494   gcry_mpi_release (value_h);
495   gcry_mpi_release (value_e);
496
497   /* As a last step test this keys (this should never fail of course). */
498   if (!ec && test_keys (sk, qbits) )
499     {
500       gcry_mpi_release (sk->p); sk->p = NULL;
501       gcry_mpi_release (sk->q); sk->q = NULL;
502       gcry_mpi_release (sk->g); sk->g = NULL;
503       gcry_mpi_release (sk->y); sk->y = NULL;
504       gcry_mpi_release (sk->x); sk->x = NULL;
505       fips_signal_error ("self-test after key generation failed");
506       ec = GPG_ERR_SELFTEST_FAILED;
507     }
508
509   if (ec)
510     {
511       *r_counter = 0;
512       gcry_free (*r_seed); *r_seed = NULL;
513       *r_seedlen = 0;
514       gcry_mpi_release (*r_h); *r_h = NULL;
515     }
516
517   return ec;
518 }
519
520
521
522 /*
523    Test whether the secret key is valid.
524    Returns: if this is a valid key.
525  */
526 static int
527 check_secret_key( DSA_secret_key *sk )
528 {
529   int rc;
530   gcry_mpi_t y = mpi_alloc( mpi_get_nlimbs(sk->y) );
531
532   gcry_mpi_powm( y, sk->g, sk->x, sk->p );
533   rc = !mpi_cmp( y, sk->y );
534   mpi_free( y );
535   return rc;
536 }
537
538
539
540 /*
541    Make a DSA signature from HASH and put it into r and s.
542  */
543 static void
544 sign(gcry_mpi_t r, gcry_mpi_t s, gcry_mpi_t hash, DSA_secret_key *skey )
545 {
546   gcry_mpi_t k;
547   gcry_mpi_t kinv;
548   gcry_mpi_t tmp;
549
550   /* Select a random k with 0 < k < q */
551   k = gen_k( skey->q );
552
553   /* r = (a^k mod p) mod q */
554   gcry_mpi_powm( r, skey->g, k, skey->p );
555   mpi_fdiv_r( r, r, skey->q );
556
557   /* kinv = k^(-1) mod q */
558   kinv = mpi_alloc( mpi_get_nlimbs(k) );
559   mpi_invm(kinv, k, skey->q );
560
561   /* s = (kinv * ( hash + x * r)) mod q */
562   tmp = mpi_alloc( mpi_get_nlimbs(skey->p) );
563   mpi_mul( tmp, skey->x, r );
564   mpi_add( tmp, tmp, hash );
565   mpi_mulm( s , kinv, tmp, skey->q );
566
567   mpi_free(k);
568   mpi_free(kinv);
569   mpi_free(tmp);
570 }
571
572
573 /*
574    Returns true if the signature composed from R and S is valid.
575  */
576 static int
577 verify (gcry_mpi_t r, gcry_mpi_t s, gcry_mpi_t hash, DSA_public_key *pkey )
578 {
579   int rc;
580   gcry_mpi_t w, u1, u2, v;
581   gcry_mpi_t base[3];
582   gcry_mpi_t ex[3];
583
584   if( !(mpi_cmp_ui( r, 0 ) > 0 && mpi_cmp( r, pkey->q ) < 0) )
585     return 0; /* assertion      0 < r < q  failed */
586   if( !(mpi_cmp_ui( s, 0 ) > 0 && mpi_cmp( s, pkey->q ) < 0) )
587     return 0; /* assertion      0 < s < q  failed */
588
589   w  = mpi_alloc( mpi_get_nlimbs(pkey->q) );
590   u1 = mpi_alloc( mpi_get_nlimbs(pkey->q) );
591   u2 = mpi_alloc( mpi_get_nlimbs(pkey->q) );
592   v  = mpi_alloc( mpi_get_nlimbs(pkey->p) );
593
594   /* w = s^(-1) mod q */
595   mpi_invm( w, s, pkey->q );
596
597   /* u1 = (hash * w) mod q */
598   mpi_mulm( u1, hash, w, pkey->q );
599
600   /* u2 = r * w mod q  */
601   mpi_mulm( u2, r, w, pkey->q );
602
603   /* v =  g^u1 * y^u2 mod p mod q */
604   base[0] = pkey->g; ex[0] = u1;
605   base[1] = pkey->y; ex[1] = u2;
606   base[2] = NULL;    ex[2] = NULL;
607   mpi_mulpowm( v, base, ex, pkey->p );
608   mpi_fdiv_r( v, v, pkey->q );
609
610   rc = !mpi_cmp( v, r );
611
612   mpi_free(w);
613   mpi_free(u1);
614   mpi_free(u2);
615   mpi_free(v);
616
617   return rc;
618 }
619
620
621 /*********************************************
622  **************  interface  ******************
623  *********************************************/
624
625 static gcry_err_code_t
626 dsa_generate_ext (int algo, unsigned int nbits, unsigned long evalue,
627                   const gcry_sexp_t genparms,
628                   gcry_mpi_t *skey, gcry_mpi_t **retfactors,
629                   gcry_sexp_t *r_extrainfo)
630 {
631   gpg_err_code_t ec;
632   DSA_secret_key sk;
633   gcry_sexp_t l1;
634   unsigned int qbits = 0;
635   gcry_sexp_t deriveparms = NULL;
636   gcry_sexp_t seedinfo = NULL;
637   int use_fips186_2 = 0;
638   int use_fips186 = 0;
639   
640
641   (void)algo;    /* No need to check it.  */
642   (void)evalue;  /* Not required for DSA. */
643
644   if (genparms)
645     {
646       /* Parse the optional qbits element.  */
647       l1 = gcry_sexp_find_token (genparms, "qbits", 0);
648       if (l1)
649         {
650           char buf[50];
651           const char *s;
652           size_t n;
653           
654           s = gcry_sexp_nth_data (l1, 1, &n);
655           if (!s || n >= DIM (buf) - 1 )
656             {
657               gcry_sexp_release (l1);
658               return GPG_ERR_INV_OBJ; /* No value or value too large.  */
659             }
660           memcpy (buf, s, n);
661           buf[n] = 0;
662           qbits = (unsigned int)strtoul (buf, NULL, 0);
663           gcry_sexp_release (l1);
664         }
665
666       deriveparms = gcry_sexp_find_token (genparms, "derive-parms", 0);
667
668       /* Parse the optional "use-fips186" flags.  */
669       l1 = gcry_sexp_find_token (genparms, "use-fips186", 0);
670       if (l1)
671         {
672           use_fips186 = 1;
673           gcry_sexp_release (l1);
674         }
675       l1 = gcry_sexp_find_token (genparms, "use-fips186-2", 0);
676       if (l1)
677         {
678           use_fips186_2 = 1;
679           gcry_sexp_release (l1);
680         }
681     }
682
683   if (deriveparms || use_fips186 || use_fips186_2 || fips_mode ())
684     {
685       int counter;
686       void *seed;
687       size_t seedlen;
688       gcry_mpi_t h_value;
689
690       ec = generate_fips186 (&sk, nbits, qbits, deriveparms, use_fips186_2,
691                              &counter, &seed, &seedlen, &h_value);
692       gcry_sexp_release (deriveparms);
693       if (!ec)
694         {
695           ec = gpg_err_code (gcry_sexp_build 
696                              (&seedinfo, NULL,
697                               "(seed-values(counter %d)(seed %b)(h %m))",
698                               counter, (int)seedlen, seed, h_value));
699           if (ec)
700             {
701               gcry_mpi_release (sk.p); sk.p = NULL;
702               gcry_mpi_release (sk.q); sk.q = NULL;
703               gcry_mpi_release (sk.g); sk.g = NULL;
704               gcry_mpi_release (sk.y); sk.y = NULL;
705               gcry_mpi_release (sk.x); sk.x = NULL;
706             }
707           gcry_free (seed);
708           gcry_mpi_release (h_value);
709         }
710     }
711   else
712     {
713       ec = generate (&sk, nbits, qbits, retfactors);
714     }
715   if (!ec)
716     {
717       skey[0] = sk.p;
718       skey[1] = sk.q;
719       skey[2] = sk.g;
720       skey[3] = sk.y;
721       skey[4] = sk.x;
722
723       if (!r_extrainfo)
724         {
725           /* Old style interface - return the factors - if any - at
726              retfactors.  */
727         }
728       else if (!*retfactors && !seedinfo)
729         {
730           /* No factors and no seedinfo, thus there is nothing to return.  */
731           *r_extrainfo = NULL;
732         }
733       else
734         {
735           /* Put the factors into extrainfo and set retfactors to NULL
736              to make use of the new interface.  Note that the factors
737              are not confidential thus we can store them in standard
738              memory.  */
739           int nfactors, i, j;
740           char *p;
741           char *format = NULL;
742           void **arg_list = NULL;
743
744           for (nfactors=0; *retfactors && (*retfactors)[nfactors]; nfactors++)
745             ;
746           /* Allocate space for the format string:
747                "(misc-key-info%S(pm1-factors%m))"
748              with one "%m" for each factor and construct it.  */
749           format = gcry_malloc (50 + 2*nfactors);
750           if (!format)
751             ec = gpg_err_code_from_syserror ();
752           else
753             {
754               p = stpcpy (format, "(misc-key-info");
755               if (seedinfo)
756                 p = stpcpy (p, "%S");
757               if (nfactors)
758                 {
759                   p = stpcpy (p, "(pm1-factors");
760                   for (i=0; i < nfactors; i++)
761                     p = stpcpy (p, "%m");
762                   p = stpcpy (p, ")");
763                 }
764               p = stpcpy (p, ")");
765               
766               /* Allocate space for the list of factors plus one for
767                  an S-expression plus an extra NULL entry for safety
768                  and fill it with the factors.  */
769               arg_list = gcry_calloc (nfactors+1+1, sizeof *arg_list);
770               if (!arg_list)
771                 ec = gpg_err_code_from_syserror ();
772               else
773                 {
774                   i = 0;
775                   if (seedinfo)
776                     arg_list[i++] = &seedinfo;
777                   for (j=0; j < nfactors; j++)
778                     arg_list[i++] = (*retfactors) + j;
779                   arg_list[i] = NULL;
780                   
781                   ec = gpg_err_code (gcry_sexp_build_array 
782                                      (r_extrainfo, NULL, format, arg_list));
783                 }
784             }
785
786           gcry_free (arg_list);
787           gcry_free (format);
788           for (i=0; i < nfactors; i++)
789             {
790               gcry_mpi_release ((*retfactors)[i]);
791               (*retfactors)[i] = NULL;
792             }
793           *retfactors = NULL;
794           if (ec)
795             {
796               for (i=0; i < 5; i++)
797                 {
798                   gcry_mpi_release (skey[i]);
799                   skey[i] = NULL;
800                 }
801             }
802         }
803     }
804
805   gcry_sexp_release (seedinfo);
806   return ec;
807 }
808
809
810 static gcry_err_code_t
811 dsa_generate (int algo, unsigned int nbits, unsigned long evalue,
812               gcry_mpi_t *skey, gcry_mpi_t **retfactors)
813 {
814   (void)evalue;
815   return dsa_generate_ext (algo, nbits, 0, NULL, skey, retfactors, NULL);
816 }
817
818
819
820 static gcry_err_code_t
821 dsa_check_secret_key (int algo, gcry_mpi_t *skey)
822 {
823   gcry_err_code_t err = GPG_ERR_NO_ERROR;
824   DSA_secret_key sk;
825
826   (void)algo;
827
828   if ((! skey[0]) || (! skey[1]) || (! skey[2]) || (! skey[3]) || (! skey[4]))
829     err = GPG_ERR_BAD_MPI;
830   else
831     {
832       sk.p = skey[0];
833       sk.q = skey[1];
834       sk.g = skey[2];
835       sk.y = skey[3];
836       sk.x = skey[4];
837       if (! check_secret_key (&sk))
838         err = GPG_ERR_BAD_SECKEY;
839     }
840
841   return err;
842 }
843
844
845 static gcry_err_code_t
846 dsa_sign (int algo, gcry_mpi_t *resarr, gcry_mpi_t data, gcry_mpi_t *skey)
847 {
848   gcry_err_code_t err = GPG_ERR_NO_ERROR;
849   DSA_secret_key sk;
850
851   (void)algo;
852
853   if ((! data)
854       || (! skey[0]) || (! skey[1]) || (! skey[2])
855       || (! skey[3]) || (! skey[4]))
856     err = GPG_ERR_BAD_MPI;
857   else
858     {
859       sk.p = skey[0];
860       sk.q = skey[1];
861       sk.g = skey[2];
862       sk.y = skey[3];
863       sk.x = skey[4];
864       resarr[0] = mpi_alloc (mpi_get_nlimbs (sk.p));
865       resarr[1] = mpi_alloc (mpi_get_nlimbs (sk.p));
866       sign (resarr[0], resarr[1], data, &sk);
867     }
868   return err;
869 }
870
871 static gcry_err_code_t
872 dsa_verify (int algo, gcry_mpi_t hash, gcry_mpi_t *data, gcry_mpi_t *pkey,
873             int (*cmp) (void *, gcry_mpi_t), void *opaquev)
874 {
875   gcry_err_code_t err = GPG_ERR_NO_ERROR;
876   DSA_public_key pk;
877
878   (void)algo;
879   (void)cmp;
880   (void)opaquev;
881
882   if ((! data[0]) || (! data[1]) || (! hash)
883       || (! pkey[0]) || (! pkey[1]) || (! pkey[2]) || (! pkey[3]))
884     err = GPG_ERR_BAD_MPI;
885   else
886     {
887       pk.p = pkey[0];
888       pk.q = pkey[1];
889       pk.g = pkey[2];
890       pk.y = pkey[3];
891       if (! verify (data[0], data[1], hash, &pk))
892         err = GPG_ERR_BAD_SIGNATURE;
893     }
894   return err;
895 }
896
897
898 static unsigned int
899 dsa_get_nbits (int algo, gcry_mpi_t *pkey)
900 {
901   (void)algo;
902
903   return mpi_get_nbits (pkey[0]);
904 }
905
906
907 \f
908 /* 
909      Self-test section.
910  */
911
912 static const char *
913 selftest_sign_1024 (gcry_sexp_t pkey, gcry_sexp_t skey)
914 {
915   static const char sample_data[] = 
916     "(data (flags pkcs1)"
917     " (hash sha1 #a0b1c2d3e4f500102030405060708090a1b2c3d4#))";
918   static const char sample_data_bad[] = 
919     "(data (flags pkcs1)"
920     " (hash sha1 #a0b1c2d3e4f510102030405060708090a1b2c3d4#))";
921
922   const char *errtxt = NULL;
923   gcry_error_t err;
924   gcry_sexp_t data = NULL;
925   gcry_sexp_t data_bad = NULL;
926   gcry_sexp_t sig = NULL;
927
928   err = gcry_sexp_sscan (&data, NULL,
929                          sample_data, strlen (sample_data));
930   if (!err)
931     err = gcry_sexp_sscan (&data_bad, NULL, 
932                            sample_data_bad, strlen (sample_data_bad));
933   if (err)
934     {
935       errtxt = "converting data failed";
936       goto leave;
937     }
938
939   err = gcry_pk_sign (&sig, data, skey);
940   if (err)
941     {
942       errtxt = "signing failed";
943       goto leave;
944     }
945   err = gcry_pk_verify (sig, data, pkey);
946   if (err)
947     {
948       errtxt = "verify failed";
949       goto leave;
950     }
951   err = gcry_pk_verify (sig, data_bad, pkey);
952   if (gcry_err_code (err) != GPG_ERR_BAD_SIGNATURE)
953     {
954       errtxt = "bad signature not detected";
955       goto leave;
956     }
957
958
959  leave:
960   gcry_sexp_release (sig);
961   gcry_sexp_release (data_bad);
962   gcry_sexp_release (data);
963   return errtxt;
964 }
965
966
967 static gpg_err_code_t
968 selftests_dsa (selftest_report_func_t report)
969 {
970   const char *what;
971   const char *errtxt;
972   gcry_error_t err;
973   gcry_sexp_t skey = NULL;
974   gcry_sexp_t pkey = NULL;
975
976   /* Convert the S-expressions into the internal representation.  */
977   what = "convert";
978   err = gcry_sexp_sscan (&skey, NULL, 
979                          sample_secret_key, strlen (sample_secret_key));
980   if (!err)
981     err = gcry_sexp_sscan (&pkey, NULL, 
982                            sample_public_key, strlen (sample_public_key));
983   if (err)
984     {
985       errtxt = gcry_strerror (err);
986       goto failed;
987     }
988
989   what = "key consistency";
990   err = gcry_pk_testkey (skey);
991   if (err)
992     {
993       errtxt = gcry_strerror (err);
994       goto failed;
995     }
996
997   what = "sign";
998   errtxt = selftest_sign_1024 (pkey, skey);
999   if (errtxt)
1000     goto failed;
1001
1002   gcry_sexp_release (pkey);
1003   gcry_sexp_release (skey);
1004   return 0; /* Succeeded. */
1005
1006  failed:
1007   gcry_sexp_release (pkey);
1008   gcry_sexp_release (skey);
1009   if (report)
1010     report ("pubkey", GCRY_PK_DSA, what, errtxt);
1011   return GPG_ERR_SELFTEST_FAILED;
1012 }
1013
1014
1015 /* Run a full self-test for ALGO and return 0 on success.  */
1016 static gpg_err_code_t
1017 run_selftests (int algo, int extended, selftest_report_func_t report)
1018 {
1019   gpg_err_code_t ec;
1020
1021   (void)extended;
1022
1023   switch (algo)
1024     {
1025     case GCRY_PK_DSA:
1026       ec = selftests_dsa (report);
1027       break;
1028     default:
1029       ec = GPG_ERR_PUBKEY_ALGO;
1030       break;
1031         
1032     }
1033   return ec;
1034 }
1035
1036
1037
1038 \f
1039 static const char *dsa_names[] =
1040   {
1041     "dsa",
1042     "openpgp-dsa",
1043     NULL,
1044   };
1045
1046 gcry_pk_spec_t _gcry_pubkey_spec_dsa =
1047   {
1048     "DSA", dsa_names, 
1049     "pqgy", "pqgyx", "", "rs", "pqgy",
1050     GCRY_PK_USAGE_SIGN,
1051     dsa_generate,
1052     dsa_check_secret_key,
1053     NULL,
1054     NULL,
1055     dsa_sign,
1056     dsa_verify,
1057     dsa_get_nbits
1058   };
1059 pk_extra_spec_t _gcry_pubkey_extraspec_dsa = 
1060   {
1061     run_selftests,
1062     dsa_generate_ext
1063   };
1064