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