A whole bunch of changes to eventually support
[libgcrypt.git] / cipher / dsa.c
1 /* dsa.c  -  DSA signature scheme
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 #include <assert.h>
27
28 #include "g10lib.h"
29 #include "mpi.h"
30 #include "cipher.h"
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 static gcry_mpi_t gen_k (gcry_mpi_t q);
52 static void test_keys (DSA_secret_key *sk, unsigned qbits);
53 static int check_secret_key (DSA_secret_key *sk);
54 static gpg_err_code_t generate (DSA_secret_key *sk,
55                                 unsigned int nbits,
56                                 unsigned int qbits,
57                                 gcry_mpi_t **ret_factors);
58 static void sign (gcry_mpi_t r, gcry_mpi_t s, gcry_mpi_t input,
59                   DSA_secret_key *skey);
60 static int verify (gcry_mpi_t r, gcry_mpi_t s, gcry_mpi_t input,
61                    DSA_public_key *pkey);
62
63 static void (*progress_cb) (void *,const char *, int, int, int );
64 static void *progress_cb_data;
65
66
67 void
68 _gcry_register_pk_dsa_progress (void (*cb) (void *, const char *,
69                                             int, int, int),
70                                 void *cb_data)
71 {
72   progress_cb = cb;
73   progress_cb_data = cb_data;
74 }
75
76
77 static void
78 progress (int c)
79 {
80   if (progress_cb)
81     progress_cb (progress_cb_data, "pk_dsa", c, 0, 0);
82 }
83
84
85 /*
86  * Generate a random secret exponent k less than q.
87  */
88 static gcry_mpi_t
89 gen_k( gcry_mpi_t q )
90 {
91   gcry_mpi_t k = mpi_alloc_secure( mpi_get_nlimbs(q) );
92   unsigned int nbits = mpi_get_nbits(q);
93   unsigned int nbytes = (nbits+7)/8;
94   char *rndbuf = NULL;
95
96   if ( DBG_CIPHER )
97     log_debug("choosing a random k ");
98   for (;;) 
99     {
100       if( DBG_CIPHER )
101         progress('.');
102
103       if ( !rndbuf || nbits < 32 ) 
104         {
105           gcry_free(rndbuf);
106           rndbuf = gcry_random_bytes_secure( (nbits+7)/8, GCRY_STRONG_RANDOM );
107         }
108       else
109         { /* Change only some of the higher bits.  We could improve
110              this by directly requesting more memory at the first call
111              to get_random_bytes() and use this the here maybe it is
112              easier to do this directly in random.c. */
113           char *pp = gcry_random_bytes_secure( 4, GCRY_STRONG_RANDOM );
114           memcpy( rndbuf,pp, 4 );
115           gcry_free(pp);
116         }
117       _gcry_mpi_set_buffer( k, rndbuf, nbytes, 0 );
118       if ( mpi_test_bit( k, nbits-1 ) )
119         mpi_set_highbit( k, nbits-1 );
120       else
121         {
122           mpi_set_highbit( k, nbits-1 );
123           mpi_clear_bit( k, nbits-1 );
124         }
125
126       if( !(mpi_cmp( k, q ) < 0) ) /* check: k < q */
127         {       
128           if( DBG_CIPHER )
129             progress('+');
130           continue; /* no  */
131         }
132       if( !(mpi_cmp_ui( k, 0 ) > 0) )  /* check: k > 0 */
133         {
134           if( DBG_CIPHER )
135             progress('-');
136           continue; /* no */
137         }
138       break;    /* okay */
139     }
140   gcry_free(rndbuf);
141   if( DBG_CIPHER )
142     progress('\n');
143   
144   return k;
145 }
146
147
148 static void
149 test_keys( DSA_secret_key *sk, unsigned qbits )
150 {
151   DSA_public_key pk;
152   gcry_mpi_t test = gcry_mpi_new ( qbits  );
153   gcry_mpi_t out1_a = gcry_mpi_new ( qbits );
154   gcry_mpi_t out1_b = gcry_mpi_new ( qbits );
155
156   pk.p = sk->p;
157   pk.q = sk->q;
158   pk.g = sk->g;
159   pk.y = sk->y;
160   gcry_mpi_randomize( test, qbits, GCRY_WEAK_RANDOM );
161
162   sign( out1_a, out1_b, test, sk );
163   if( !verify( out1_a, out1_b, test, &pk ) )
164     log_fatal("DSA:: sign, verify failed\n");
165
166   gcry_mpi_release ( test );
167   gcry_mpi_release ( out1_a );
168   gcry_mpi_release ( out1_b );
169 }
170
171
172
173 /*
174    Generate a DSA key pair with a key of size NBITS.
175    Returns: 2 structures filled with all needed values
176             and an array with the n-1 factors of (p-1)
177  */
178 static gpg_err_code_t
179 generate (DSA_secret_key *sk, unsigned int nbits, unsigned int qbits,
180           gcry_mpi_t **ret_factors )
181 {
182   gcry_mpi_t p;    /* the prime */
183   gcry_mpi_t q;    /* the 160 bit prime factor */
184   gcry_mpi_t g;    /* the generator */
185   gcry_mpi_t y;    /* g^x mod p */
186   gcry_mpi_t x;    /* the secret exponent */
187   gcry_mpi_t h, e;  /* helper */
188   unsigned char *rndbuf;
189
190   if (qbits)
191     ; /* Caller supplied qbits.  Use this value.  */
192   else if ( nbits >= 512 && nbits <= 1024 )
193     qbits = 160;
194   else if ( nbits == 2048 )
195     qbits = 224;
196   else if ( nbits == 3072 )
197     qbits = 256;
198   else if ( nbits == 7680 )
199     qbits = 384;
200   else if ( nbits == 15360 )
201     qbits = 512;
202   else
203     return GPG_ERR_INV_VALUE;
204
205   if (qbits < 160 || qbits > 512 || (qbits%8) )
206     return GPG_ERR_INV_VALUE;
207   if (nbits < 2*qbits || nbits > 15360)
208     return GPG_ERR_INV_VALUE;
209
210   if (nbits < 1024 && fips_mode ())
211     return GPG_ERR_INV_VALUE;
212
213   p = _gcry_generate_elg_prime( 1, nbits, qbits, NULL, ret_factors );
214   /* get q out of factors */
215   q = mpi_copy((*ret_factors)[0]);
216   if( mpi_get_nbits(q) != qbits )
217     BUG();
218
219   /* Find a generator g (h and e are helpers).
220      e = (p-1)/q */
221   e = mpi_alloc( mpi_get_nlimbs(p) );
222   mpi_sub_ui( e, p, 1 );
223   mpi_fdiv_q( e, e, q );
224   g = mpi_alloc( mpi_get_nlimbs(p) );
225   h = mpi_alloc_set_ui( 1 ); /* we start with 2 */
226   do
227     {
228       mpi_add_ui( h, h, 1 );
229       /* g = h^e mod p */
230       gcry_mpi_powm( g, h, e, p );
231     } 
232   while( !mpi_cmp_ui( g, 1 ) );  /* continue until g != 1 */
233
234   /* Select a random number which has these properties:
235    *     0 < x < q-1
236    * This must be a very good random number because this
237    * is the secret part. */
238   if( DBG_CIPHER )
239     log_debug("choosing a random x ");
240   assert( qbits >= 160 );
241   x = mpi_alloc_secure( mpi_get_nlimbs(q) );
242   mpi_sub_ui( h, q, 1 );  /* put q-1 into h */
243   rndbuf = NULL;
244   do 
245     {
246       if( DBG_CIPHER )
247         progress('.');
248       if( !rndbuf )
249         rndbuf = gcry_random_bytes_secure( (qbits+7)/8,
250                                            GCRY_VERY_STRONG_RANDOM );
251       else 
252         { /* Change only some of the higher bits (= 2 bytes)*/
253           char *r = gcry_random_bytes_secure (2, GCRY_VERY_STRONG_RANDOM);
254           memcpy(rndbuf, r, 2 );
255           gcry_free(r);
256         }
257
258       _gcry_mpi_set_buffer( x, rndbuf, (qbits+7)/8, 0 );
259       mpi_clear_highbit( x, qbits+1 );
260     } 
261   while ( !( mpi_cmp_ui( x, 0 )>0 && mpi_cmp( x, h )<0 ) );
262   gcry_free(rndbuf);
263   mpi_free( e );
264   mpi_free( h );
265
266   /* y = g^x mod p */
267   y = mpi_alloc( mpi_get_nlimbs(p) );
268   gcry_mpi_powm( y, g, x, p );
269
270   if( DBG_CIPHER ) 
271     {
272       progress('\n');
273       log_mpidump("dsa  p= ", p );
274       log_mpidump("dsa  q= ", q );
275       log_mpidump("dsa  g= ", g );
276       log_mpidump("dsa  y= ", y );
277       log_mpidump("dsa  x= ", x );
278     }
279
280   /* Copy the stuff to the key structures. */
281   sk->p = p;
282   sk->q = q;
283   sk->g = g;
284   sk->y = y;
285   sk->x = x;
286
287   /* Now we can test our keys (this should never fail!). */
288   test_keys( sk, qbits );
289   return 0;
290 }
291
292
293
294 /*
295    Test whether the secret key is valid.
296    Returns: if this is a valid key.
297  */
298 static int
299 check_secret_key( DSA_secret_key *sk )
300 {
301   int rc;
302   gcry_mpi_t y = mpi_alloc( mpi_get_nlimbs(sk->y) );
303
304   gcry_mpi_powm( y, sk->g, sk->x, sk->p );
305   rc = !mpi_cmp( y, sk->y );
306   mpi_free( y );
307   return rc;
308 }
309
310
311
312 /*
313    Make a DSA signature from HASH and put it into r and s.
314  */
315 static void
316 sign(gcry_mpi_t r, gcry_mpi_t s, gcry_mpi_t hash, DSA_secret_key *skey )
317 {
318   gcry_mpi_t k;
319   gcry_mpi_t kinv;
320   gcry_mpi_t tmp;
321
322   /* Select a random k with 0 < k < q */
323   k = gen_k( skey->q );
324
325   /* r = (a^k mod p) mod q */
326   gcry_mpi_powm( r, skey->g, k, skey->p );
327   mpi_fdiv_r( r, r, skey->q );
328
329   /* kinv = k^(-1) mod q */
330   kinv = mpi_alloc( mpi_get_nlimbs(k) );
331   mpi_invm(kinv, k, skey->q );
332
333   /* s = (kinv * ( hash + x * r)) mod q */
334   tmp = mpi_alloc( mpi_get_nlimbs(skey->p) );
335   mpi_mul( tmp, skey->x, r );
336   mpi_add( tmp, tmp, hash );
337   mpi_mulm( s , kinv, tmp, skey->q );
338
339   mpi_free(k);
340   mpi_free(kinv);
341   mpi_free(tmp);
342 }
343
344
345 /*
346    Returns true if the signature composed from R and S is valid.
347  */
348 static int
349 verify (gcry_mpi_t r, gcry_mpi_t s, gcry_mpi_t hash, DSA_public_key *pkey )
350 {
351   int rc;
352   gcry_mpi_t w, u1, u2, v;
353   gcry_mpi_t base[3];
354   gcry_mpi_t ex[3];
355
356   if( !(mpi_cmp_ui( r, 0 ) > 0 && mpi_cmp( r, pkey->q ) < 0) )
357     return 0; /* assertion      0 < r < q  failed */
358   if( !(mpi_cmp_ui( s, 0 ) > 0 && mpi_cmp( s, pkey->q ) < 0) )
359     return 0; /* assertion      0 < s < q  failed */
360
361   w  = mpi_alloc( mpi_get_nlimbs(pkey->q) );
362   u1 = mpi_alloc( mpi_get_nlimbs(pkey->q) );
363   u2 = mpi_alloc( mpi_get_nlimbs(pkey->q) );
364   v  = mpi_alloc( mpi_get_nlimbs(pkey->p) );
365
366   /* w = s^(-1) mod q */
367   mpi_invm( w, s, pkey->q );
368
369   /* u1 = (hash * w) mod q */
370   mpi_mulm( u1, hash, w, pkey->q );
371
372   /* u2 = r * w mod q  */
373   mpi_mulm( u2, r, w, pkey->q );
374
375   /* v =  g^u1 * y^u2 mod p mod q */
376   base[0] = pkey->g; ex[0] = u1;
377   base[1] = pkey->y; ex[1] = u2;
378   base[2] = NULL;    ex[2] = NULL;
379   mpi_mulpowm( v, base, ex, pkey->p );
380   mpi_fdiv_r( v, v, pkey->q );
381
382   rc = !mpi_cmp( v, r );
383
384   mpi_free(w);
385   mpi_free(u1);
386   mpi_free(u2);
387   mpi_free(v);
388
389   return rc;
390 }
391
392
393 /*********************************************
394  **************  interface  ******************
395  *********************************************/
396
397 gcry_err_code_t
398 _gcry_dsa_generate (int algo, unsigned int nbits, unsigned long dummy,
399                     gcry_mpi_t *skey, gcry_mpi_t **retfactors)
400 {
401   gpg_err_code_t err;
402   DSA_secret_key sk;
403
404   (void)algo;
405   (void)dummy;
406
407   err = generate (&sk, nbits, 0, retfactors);
408   if (!err)
409     {
410       skey[0] = sk.p;
411       skey[1] = sk.q;
412       skey[2] = sk.g;
413       skey[3] = sk.y;
414       skey[4] = sk.x;
415     }
416
417   return err;
418 }
419
420
421 /* We don't want to break our API.  Thus we use a hack in pubkey.c to
422    link directly to this function.  Note that we can't reuse the dummy
423    parameter because we can't be sure that applicaions accidently pass
424    a USE_E (that is for what dummy is used with RSA) to a DSA
425    generation. */
426 gcry_err_code_t
427 _gcry_dsa_generate2 (int algo, unsigned int nbits, unsigned int qbits,
428                      unsigned long dummy,
429                      gcry_mpi_t *skey, gcry_mpi_t **retfactors)
430 {
431   gpg_err_code_t err;
432   DSA_secret_key sk;
433
434   (void)algo;
435   (void)dummy;
436
437   err = generate (&sk, nbits, qbits, retfactors);
438   if (!err)
439     {
440       skey[0] = sk.p;
441       skey[1] = sk.q;
442       skey[2] = sk.g;
443       skey[3] = sk.y;
444       skey[4] = sk.x;
445     }
446
447   return err;
448 }
449
450
451 gcry_err_code_t
452 _gcry_dsa_check_secret_key (int algo, gcry_mpi_t *skey)
453 {
454   gcry_err_code_t err = GPG_ERR_NO_ERROR;
455   DSA_secret_key sk;
456
457   (void)algo;
458
459   if ((! skey[0]) || (! skey[1]) || (! skey[2]) || (! skey[3]) || (! skey[4]))
460     err = GPG_ERR_BAD_MPI;
461   else
462     {
463       sk.p = skey[0];
464       sk.q = skey[1];
465       sk.g = skey[2];
466       sk.y = skey[3];
467       sk.x = skey[4];
468       if (! check_secret_key (&sk))
469         err = GPG_ERR_BAD_SECKEY;
470     }
471
472   return err;
473 }
474
475
476 gcry_err_code_t
477 _gcry_dsa_sign (int algo, gcry_mpi_t *resarr, gcry_mpi_t data, gcry_mpi_t *skey)
478 {
479   gcry_err_code_t err = GPG_ERR_NO_ERROR;
480   DSA_secret_key sk;
481
482   (void)algo;
483
484   if ((! data)
485       || (! skey[0]) || (! skey[1]) || (! skey[2])
486       || (! skey[3]) || (! skey[4]))
487     err = GPG_ERR_BAD_MPI;
488   else
489     {
490       sk.p = skey[0];
491       sk.q = skey[1];
492       sk.g = skey[2];
493       sk.y = skey[3];
494       sk.x = skey[4];
495       resarr[0] = mpi_alloc (mpi_get_nlimbs (sk.p));
496       resarr[1] = mpi_alloc (mpi_get_nlimbs (sk.p));
497       sign (resarr[0], resarr[1], data, &sk);
498     }
499   return err;
500 }
501
502 gcry_err_code_t
503 _gcry_dsa_verify (int algo, gcry_mpi_t hash, gcry_mpi_t *data, gcry_mpi_t *pkey,
504                   int (*cmp) (void *, gcry_mpi_t), void *opaquev)
505 {
506   gcry_err_code_t err = GPG_ERR_NO_ERROR;
507   DSA_public_key pk;
508
509   (void)algo;
510   (void)cmp;
511   (void)opaquev;
512
513   if ((! data[0]) || (! data[1]) || (! hash)
514       || (! pkey[0]) || (! pkey[1]) || (! pkey[2]) || (! pkey[3]))
515     err = GPG_ERR_BAD_MPI;
516   else
517     {
518       pk.p = pkey[0];
519       pk.q = pkey[1];
520       pk.g = pkey[2];
521       pk.y = pkey[3];
522       if (! verify (data[0], data[1], hash, &pk))
523         err = GPG_ERR_BAD_SIGNATURE;
524     }
525   return err;
526 }
527
528
529 unsigned int
530 _gcry_dsa_get_nbits (int algo, gcry_mpi_t *pkey)
531 {
532   (void)algo;
533
534   return mpi_get_nbits (pkey[0]);
535 }
536
537
538 \f
539 /* 
540      Self-test section.
541  */
542
543
544 static gpg_err_code_t
545 selftests_dsa (selftest_report_func_t report)
546 {
547   const char *what;
548   const char *errtxt;
549   
550   what = "low-level";
551   errtxt = NULL; /*selftest ();*/
552   if (errtxt)
553     goto failed;
554
555   /* FIXME:  need more tests.  */
556
557   return 0; /* Succeeded. */
558
559  failed:
560   if (report)
561     report ("pubkey", GCRY_PK_DSA, what, errtxt);
562   return GPG_ERR_SELFTEST_FAILED;
563 }
564
565
566 /* Run a full self-test for ALGO and return 0 on success.  */
567 static gpg_err_code_t
568 run_selftests (int algo, selftest_report_func_t report)
569 {
570   gpg_err_code_t ec;
571
572   switch (algo)
573     {
574     case GCRY_PK_DSA:
575       ec = selftests_dsa (report);
576       break;
577     default:
578       ec = GPG_ERR_PUBKEY_ALGO;
579       break;
580         
581     }
582   return ec;
583 }
584
585
586
587 \f
588 static const char *dsa_names[] =
589   {
590     "dsa",
591     "openpgp-dsa",
592     NULL,
593   };
594
595 gcry_pk_spec_t _gcry_pubkey_spec_dsa =
596   {
597     "DSA", dsa_names, 
598     "pqgy", "pqgyx", "", "rs", "pqgy",
599     GCRY_PK_USAGE_SIGN,
600     _gcry_dsa_generate,
601     _gcry_dsa_check_secret_key,
602     NULL,
603     NULL,
604     _gcry_dsa_sign,
605     _gcry_dsa_verify,
606     _gcry_dsa_get_nbits,
607   };
608 pk_extra_spec_t _gcry_pubkey_extraspec_dsa = 
609   {
610     run_selftests
611   };
612