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