Use extra counter to check random pool filling.
[libgcrypt.git] / cipher / dsa.c
1 /* dsa.c  -  DSA signature scheme
2  * Copyright (C) 1998, 2000, 2001, 2002, 2003,
3  *               2006  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   p = _gcry_generate_elg_prime( 1, nbits, qbits, NULL, ret_factors );
211   /* get q out of factors */
212   q = mpi_copy((*ret_factors)[0]);
213   if( mpi_get_nbits(q) != qbits )
214     BUG();
215
216   /* Find a generator g (h and e are helpers).
217      e = (p-1)/q */
218   e = mpi_alloc( mpi_get_nlimbs(p) );
219   mpi_sub_ui( e, p, 1 );
220   mpi_fdiv_q( e, e, q );
221   g = mpi_alloc( mpi_get_nlimbs(p) );
222   h = mpi_alloc_set_ui( 1 ); /* we start with 2 */
223   do
224     {
225       mpi_add_ui( h, h, 1 );
226       /* g = h^e mod p */
227       gcry_mpi_powm( g, h, e, p );
228     } 
229   while( !mpi_cmp_ui( g, 1 ) );  /* continue until g != 1 */
230
231   /* Select a random number which has these properties:
232    *     0 < x < q-1
233    * This must be a very good random number because this
234    * is the secret part. */
235   if( DBG_CIPHER )
236     log_debug("choosing a random x ");
237   assert( qbits >= 160 );
238   x = mpi_alloc_secure( mpi_get_nlimbs(q) );
239   mpi_sub_ui( h, q, 1 );  /* put q-1 into h */
240   rndbuf = NULL;
241   do 
242     {
243       if( DBG_CIPHER )
244         progress('.');
245       if( !rndbuf )
246         rndbuf = gcry_random_bytes_secure( (qbits+7)/8,
247                                            GCRY_VERY_STRONG_RANDOM );
248       else 
249         { /* Change only some of the higher bits (= 2 bytes)*/
250           char *r = gcry_random_bytes_secure (2, GCRY_VERY_STRONG_RANDOM);
251           memcpy(rndbuf, r, 2 );
252           gcry_free(r);
253         }
254
255       _gcry_mpi_set_buffer( x, rndbuf, (qbits+7)/8, 0 );
256       mpi_clear_highbit( x, qbits+1 );
257     } 
258   while ( !( mpi_cmp_ui( x, 0 )>0 && mpi_cmp( x, h )<0 ) );
259   gcry_free(rndbuf);
260   mpi_free( e );
261   mpi_free( h );
262
263   /* y = g^x mod p */
264   y = mpi_alloc( mpi_get_nlimbs(p) );
265   gcry_mpi_powm( y, g, x, p );
266
267   if( DBG_CIPHER ) 
268     {
269       progress('\n');
270       log_mpidump("dsa  p= ", p );
271       log_mpidump("dsa  q= ", q );
272       log_mpidump("dsa  g= ", g );
273       log_mpidump("dsa  y= ", y );
274       log_mpidump("dsa  x= ", x );
275     }
276
277   /* Copy the stuff to the key structures. */
278   sk->p = p;
279   sk->q = q;
280   sk->g = g;
281   sk->y = y;
282   sk->x = x;
283
284   /* Now we can test our keys (this should never fail!). */
285   test_keys( sk, qbits );
286   return 0;
287 }
288
289
290
291 /*
292    Test whether the secret key is valid.
293    Returns: if this is a valid key.
294  */
295 static int
296 check_secret_key( DSA_secret_key *sk )
297 {
298   int rc;
299   gcry_mpi_t y = mpi_alloc( mpi_get_nlimbs(sk->y) );
300
301   gcry_mpi_powm( y, sk->g, sk->x, sk->p );
302   rc = !mpi_cmp( y, sk->y );
303   mpi_free( y );
304   return rc;
305 }
306
307
308
309 /*
310    Make a DSA signature from HASH and put it into r and s.
311  */
312 static void
313 sign(gcry_mpi_t r, gcry_mpi_t s, gcry_mpi_t hash, DSA_secret_key *skey )
314 {
315   gcry_mpi_t k;
316   gcry_mpi_t kinv;
317   gcry_mpi_t tmp;
318
319   /* Select a random k with 0 < k < q */
320   k = gen_k( skey->q );
321
322   /* r = (a^k mod p) mod q */
323   gcry_mpi_powm( r, skey->g, k, skey->p );
324   mpi_fdiv_r( r, r, skey->q );
325
326   /* kinv = k^(-1) mod q */
327   kinv = mpi_alloc( mpi_get_nlimbs(k) );
328   mpi_invm(kinv, k, skey->q );
329
330   /* s = (kinv * ( hash + x * r)) mod q */
331   tmp = mpi_alloc( mpi_get_nlimbs(skey->p) );
332   mpi_mul( tmp, skey->x, r );
333   mpi_add( tmp, tmp, hash );
334   mpi_mulm( s , kinv, tmp, skey->q );
335
336   mpi_free(k);
337   mpi_free(kinv);
338   mpi_free(tmp);
339 }
340
341
342 /*
343    Returns true if the signature composed from R and S is valid.
344  */
345 static int
346 verify (gcry_mpi_t r, gcry_mpi_t s, gcry_mpi_t hash, DSA_public_key *pkey )
347 {
348   int rc;
349   gcry_mpi_t w, u1, u2, v;
350   gcry_mpi_t base[3];
351   gcry_mpi_t ex[3];
352
353   if( !(mpi_cmp_ui( r, 0 ) > 0 && mpi_cmp( r, pkey->q ) < 0) )
354     return 0; /* assertion      0 < r < q  failed */
355   if( !(mpi_cmp_ui( s, 0 ) > 0 && mpi_cmp( s, pkey->q ) < 0) )
356     return 0; /* assertion      0 < s < q  failed */
357
358   w  = mpi_alloc( mpi_get_nlimbs(pkey->q) );
359   u1 = mpi_alloc( mpi_get_nlimbs(pkey->q) );
360   u2 = mpi_alloc( mpi_get_nlimbs(pkey->q) );
361   v  = mpi_alloc( mpi_get_nlimbs(pkey->p) );
362
363   /* w = s^(-1) mod q */
364   mpi_invm( w, s, pkey->q );
365
366   /* u1 = (hash * w) mod q */
367   mpi_mulm( u1, hash, w, pkey->q );
368
369   /* u2 = r * w mod q  */
370   mpi_mulm( u2, r, w, pkey->q );
371
372   /* v =  g^u1 * y^u2 mod p mod q */
373   base[0] = pkey->g; ex[0] = u1;
374   base[1] = pkey->y; ex[1] = u2;
375   base[2] = NULL;    ex[2] = NULL;
376   mpi_mulpowm( v, base, ex, pkey->p );
377   mpi_fdiv_r( v, v, pkey->q );
378
379   rc = !mpi_cmp( v, r );
380
381   mpi_free(w);
382   mpi_free(u1);
383   mpi_free(u2);
384   mpi_free(v);
385
386   return rc;
387 }
388
389
390 /*********************************************
391  **************  interface  ******************
392  *********************************************/
393
394 gcry_err_code_t
395 _gcry_dsa_generate (int algo, unsigned int nbits, unsigned long dummy,
396                     gcry_mpi_t *skey, gcry_mpi_t **retfactors)
397 {
398   gpg_err_code_t err;
399   DSA_secret_key sk;
400
401   (void)algo;
402   (void)dummy;
403
404   err = generate (&sk, nbits, 0, retfactors);
405   if (!err)
406     {
407       skey[0] = sk.p;
408       skey[1] = sk.q;
409       skey[2] = sk.g;
410       skey[3] = sk.y;
411       skey[4] = sk.x;
412     }
413
414   return err;
415 }
416
417
418 /* We don't want to break our API.  Thus we use a hack in pubkey.c to
419    link directly to this function.  Note that we can't reuse the dummy
420    parameter because we can't be sure that applicaions accidently pass
421    a USE_E (that is for what dummy is used with RSA) to a DSA
422    generation. */
423 gcry_err_code_t
424 _gcry_dsa_generate2 (int algo, unsigned int nbits, unsigned int qbits,
425                      unsigned long dummy,
426                      gcry_mpi_t *skey, gcry_mpi_t **retfactors)
427 {
428   gpg_err_code_t err;
429   DSA_secret_key sk;
430
431   (void)algo;
432   (void)dummy;
433
434   err = generate (&sk, nbits, qbits, retfactors);
435   if (!err)
436     {
437       skey[0] = sk.p;
438       skey[1] = sk.q;
439       skey[2] = sk.g;
440       skey[3] = sk.y;
441       skey[4] = sk.x;
442     }
443
444   return err;
445 }
446
447
448 gcry_err_code_t
449 _gcry_dsa_check_secret_key (int algo, gcry_mpi_t *skey)
450 {
451   gcry_err_code_t err = GPG_ERR_NO_ERROR;
452   DSA_secret_key sk;
453
454   (void)algo;
455
456   if ((! skey[0]) || (! skey[1]) || (! skey[2]) || (! skey[3]) || (! skey[4]))
457     err = GPG_ERR_BAD_MPI;
458   else
459     {
460       sk.p = skey[0];
461       sk.q = skey[1];
462       sk.g = skey[2];
463       sk.y = skey[3];
464       sk.x = skey[4];
465       if (! check_secret_key (&sk))
466         err = GPG_ERR_BAD_SECKEY;
467     }
468
469   return err;
470 }
471
472
473 gcry_err_code_t
474 _gcry_dsa_sign (int algo, gcry_mpi_t *resarr, gcry_mpi_t data, gcry_mpi_t *skey)
475 {
476   gcry_err_code_t err = GPG_ERR_NO_ERROR;
477   DSA_secret_key sk;
478
479   (void)algo;
480
481   if ((! data)
482       || (! skey[0]) || (! skey[1]) || (! skey[2])
483       || (! skey[3]) || (! skey[4]))
484     err = GPG_ERR_BAD_MPI;
485   else
486     {
487       sk.p = skey[0];
488       sk.q = skey[1];
489       sk.g = skey[2];
490       sk.y = skey[3];
491       sk.x = skey[4];
492       resarr[0] = mpi_alloc (mpi_get_nlimbs (sk.p));
493       resarr[1] = mpi_alloc (mpi_get_nlimbs (sk.p));
494       sign (resarr[0], resarr[1], data, &sk);
495     }
496   return err;
497 }
498
499 gcry_err_code_t
500 _gcry_dsa_verify (int algo, gcry_mpi_t hash, gcry_mpi_t *data, gcry_mpi_t *pkey,
501                   int (*cmp) (void *, gcry_mpi_t), void *opaquev)
502 {
503   gcry_err_code_t err = GPG_ERR_NO_ERROR;
504   DSA_public_key pk;
505
506   (void)algo;
507   (void)cmp;
508   (void)opaquev;
509
510   if ((! data[0]) || (! data[1]) || (! hash)
511       || (! pkey[0]) || (! pkey[1]) || (! pkey[2]) || (! pkey[3]))
512     err = GPG_ERR_BAD_MPI;
513   else
514     {
515       pk.p = pkey[0];
516       pk.q = pkey[1];
517       pk.g = pkey[2];
518       pk.y = pkey[3];
519       if (! verify (data[0], data[1], hash, &pk))
520         err = GPG_ERR_BAD_SIGNATURE;
521     }
522   return err;
523 }
524
525
526 unsigned int
527 _gcry_dsa_get_nbits (int algo, gcry_mpi_t *pkey)
528 {
529   (void)algo;
530
531   return mpi_get_nbits (pkey[0]);
532 }
533
534 static const char *dsa_names[] =
535   {
536     "dsa",
537     "openpgp-dsa",
538     NULL,
539   };
540
541 gcry_pk_spec_t _gcry_pubkey_spec_dsa =
542   {
543     "DSA", dsa_names, 
544     "pqgy", "pqgyx", "", "rs", "pqgy",
545     GCRY_PK_USAGE_SIGN,
546     _gcry_dsa_generate,
547     _gcry_dsa_check_secret_key,
548     NULL,
549     NULL,
550     _gcry_dsa_sign,
551     _gcry_dsa_verify,
552     _gcry_dsa_get_nbits,
553   };
554