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