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