Assorted changeds
[libgcrypt.git] / cipher / dsa.c
1 /* dsa.c  -  DSA signature scheme
2  * Copyright (C) 1998, 2000, 2001, 2002, 2003 Free Software Foundation, Inc.
3  *
4  * This file is part of Libgcrypt.
5  *
6  * Libgcrypt is free software; you can redistribute it and/or modify
7  * it under the terms of the GNU Lesser general Public License as
8  * published by the Free Software Foundation; either version 2.1 of
9  * the License, or (at your option) any later version.
10  *
11  * Libgcrypt is distributed in the hope that it will be useful,
12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14  * GNU Lesser General Public License for more details.
15  *
16  * You should have received a copy of the GNU Lesser General Public
17  * License along with this program; if not, write to the Free Software
18  * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA
19  */
20
21 #include <config.h>
22 #include <stdio.h>
23 #include <stdlib.h>
24 #include <string.h>
25 #include <assert.h>
26
27 #include "g10lib.h"
28 #include "mpi.h"
29 #include "cipher.h"
30
31 typedef struct
32 {
33   gcry_mpi_t p;     /* prime */
34   gcry_mpi_t q;     /* group order */
35   gcry_mpi_t g;     /* group generator */
36   gcry_mpi_t y;     /* g^x mod p */
37 } DSA_public_key;
38
39
40 typedef struct
41 {
42   gcry_mpi_t p;     /* prime */
43   gcry_mpi_t q;     /* group order */
44   gcry_mpi_t g;     /* group generator */
45   gcry_mpi_t y;     /* g^x mod p */
46   gcry_mpi_t x;     /* secret exponent */
47 } DSA_secret_key;
48
49
50 static gcry_mpi_t gen_k (gcry_mpi_t q);
51 static void test_keys (DSA_secret_key *sk, unsigned qbits);
52 static int check_secret_key (DSA_secret_key *sk);
53 static gpg_err_code_t generate (DSA_secret_key *sk, unsigned nbits,
54                                 gcry_mpi_t **ret_factors);
55 static void sign (gcry_mpi_t r, gcry_mpi_t s, gcry_mpi_t input,
56                   DSA_secret_key *skey);
57 static int verify (gcry_mpi_t r, gcry_mpi_t s, gcry_mpi_t input,
58                    DSA_public_key *pkey);
59
60 static void (*progress_cb) (void *,const char *, int, int, int );
61 static void *progress_cb_data;
62
63
64 void
65 _gcry_register_pk_dsa_progress (void (*cb) (void *, const char *,
66                                             int, int, int),
67                                 void *cb_data)
68 {
69   progress_cb = cb;
70   progress_cb_data = cb_data;
71 }
72
73
74 static void
75 progress (int c)
76 {
77   if (progress_cb)
78     progress_cb (progress_cb_data, "pk_dsa", c, 0, 0);
79 }
80
81
82 /*
83  * Generate a random secret exponent k less than q.
84  */
85 static gcry_mpi_t
86 gen_k( gcry_mpi_t q )
87 {
88   gcry_mpi_t k = mpi_alloc_secure( mpi_get_nlimbs(q) );
89   unsigned int nbits = mpi_get_nbits(q);
90   unsigned int nbytes = (nbits+7)/8;
91   char *rndbuf = NULL;
92
93   if ( DBG_CIPHER )
94     log_debug("choosing a random k ");
95   for (;;) 
96     {
97       if( DBG_CIPHER )
98         progress('.');
99
100       if ( !rndbuf || nbits < 32 ) 
101         {
102           gcry_free(rndbuf);
103           rndbuf = gcry_random_bytes_secure( (nbits+7)/8, GCRY_STRONG_RANDOM );
104         }
105       else
106         { /* Change only some of the higher bits.  We could improve
107              this by directly requesting more memory at the first call
108              to get_random_bytes() and use this the here maybe it is
109              easier to do this directly in random.c. */
110           char *pp = gcry_random_bytes_secure( 4, GCRY_STRONG_RANDOM );
111           memcpy( rndbuf,pp, 4 );
112           gcry_free(pp);
113         }
114       _gcry_mpi_set_buffer( k, rndbuf, nbytes, 0 );
115       if ( mpi_test_bit( k, nbits-1 ) )
116         mpi_set_highbit( k, nbits-1 );
117       else
118         {
119           mpi_set_highbit( k, nbits-1 );
120           mpi_clear_bit( k, nbits-1 );
121         }
122
123       if( !(mpi_cmp( k, q ) < 0) ) /* check: k < q */
124         {       
125           if( DBG_CIPHER )
126             progress('+');
127           continue; /* no  */
128         }
129       if( !(mpi_cmp_ui( k, 0 ) > 0) )  /* check: k > 0 */
130         {
131           if( DBG_CIPHER )
132             progress('-');
133           continue; /* no */
134         }
135       break;    /* okay */
136     }
137   gcry_free(rndbuf);
138   if( DBG_CIPHER )
139     progress('\n');
140   
141   return k;
142 }
143
144
145 static void
146 test_keys( DSA_secret_key *sk, unsigned qbits )
147 {
148   DSA_public_key pk;
149   gcry_mpi_t test = gcry_mpi_new ( qbits  );
150   gcry_mpi_t out1_a = gcry_mpi_new ( qbits );
151   gcry_mpi_t out1_b = gcry_mpi_new ( qbits );
152
153   pk.p = sk->p;
154   pk.q = sk->q;
155   pk.g = sk->g;
156   pk.y = sk->y;
157   gcry_mpi_randomize( test, qbits, GCRY_WEAK_RANDOM );
158
159   sign( out1_a, out1_b, test, sk );
160   if( !verify( out1_a, out1_b, test, &pk ) )
161     log_fatal("DSA:: sign, verify failed\n");
162
163   gcry_mpi_release ( test );
164   gcry_mpi_release ( out1_a );
165   gcry_mpi_release ( out1_b );
166 }
167
168
169
170 /*
171    Generate a DSA key pair with a key of size NBITS.
172    Returns: 2 structures filled with all needed values
173             and an array with the n-1 factors of (p-1)
174  */
175 static gpg_err_code_t
176 generate( DSA_secret_key *sk, unsigned nbits, gcry_mpi_t **ret_factors )
177 {
178   gcry_mpi_t p;    /* the prime */
179   gcry_mpi_t q;    /* the 160 bit prime factor */
180   gcry_mpi_t g;    /* the generator */
181   gcry_mpi_t y;    /* g^x mod p */
182   gcry_mpi_t x;    /* the secret exponent */
183   gcry_mpi_t h, e;  /* helper */
184   unsigned qbits;
185   unsigned char *rndbuf;
186
187   if ( nbits >= 512 && nbits <= 1024 )
188     qbits = 160;
189   else if ( nbits == 2048 )
190     qbits = 224;
191   else if ( nbits == 3072 )
192     qbits = 256;
193 /*   else if ( nbits == 7680 ) */
194 /*     qbits = 384; */
195 /*   else if ( nbits == 15360 ) */
196 /*     qbits = 512; */
197   else
198     return GPG_ERR_INV_VALUE;
199
200   p = _gcry_generate_elg_prime( 1, nbits, qbits, NULL, ret_factors );
201   /* get q out of factors */
202   q = mpi_copy((*ret_factors)[0]);
203   if( mpi_get_nbits(q) != qbits )
204     BUG();
205
206   /* Find a generator g (h and e are helpers).
207      e = (p-1)/q */
208   e = mpi_alloc( mpi_get_nlimbs(p) );
209   mpi_sub_ui( e, p, 1 );
210   mpi_fdiv_q( e, e, q );
211   g = mpi_alloc( mpi_get_nlimbs(p) );
212   h = mpi_alloc_set_ui( 1 ); /* we start with 2 */
213   do
214     {
215       mpi_add_ui( h, h, 1 );
216       /* g = h^e mod p */
217       gcry_mpi_powm( g, h, e, p );
218     } 
219   while( !mpi_cmp_ui( g, 1 ) );  /* continue until g != 1 */
220
221   /* Select a random number which has these properties:
222    *     0 < x < q-1
223    * This must be a very good random number because this
224    * is the secret part. */
225   if( DBG_CIPHER )
226     log_debug("choosing a random x ");
227   assert( qbits >= 160 );
228   x = mpi_alloc_secure( mpi_get_nlimbs(q) );
229   mpi_sub_ui( h, q, 1 );  /* put q-1 into h */
230   rndbuf = NULL;
231   do 
232     {
233       if( DBG_CIPHER )
234         progress('.');
235       if( !rndbuf )
236         rndbuf = gcry_random_bytes_secure( (qbits+7)/8,
237                                            GCRY_VERY_STRONG_RANDOM );
238       else 
239         { /* Change only some of the higher bits (= 2 bytes)*/
240           char *r = gcry_random_bytes_secure (2, GCRY_VERY_STRONG_RANDOM);
241           memcpy(rndbuf, r, 2 );
242           gcry_free(r);
243         }
244
245       _gcry_mpi_set_buffer( x, rndbuf, (qbits+7)/8, 0 );
246       mpi_clear_highbit( x, qbits+1 );
247     } 
248   while ( !( mpi_cmp_ui( x, 0 )>0 && mpi_cmp( x, h )<0 ) );
249   gcry_free(rndbuf);
250   mpi_free( e );
251   mpi_free( h );
252
253   /* y = g^x mod p */
254   y = mpi_alloc( mpi_get_nlimbs(p) );
255   gcry_mpi_powm( y, g, x, p );
256
257   if( DBG_CIPHER ) 
258     {
259       progress('\n');
260       log_mpidump("dsa  p= ", p );
261       log_mpidump("dsa  q= ", q );
262       log_mpidump("dsa  g= ", g );
263       log_mpidump("dsa  y= ", y );
264       log_mpidump("dsa  x= ", x );
265     }
266
267   /* Copy the stuff to the key structures. */
268   sk->p = p;
269   sk->q = q;
270   sk->g = g;
271   sk->y = y;
272   sk->x = x;
273
274   /* Now we can test our keys (this should never fail!). */
275   test_keys( sk, qbits );
276   return 0;
277 }
278
279
280
281 /*
282    Test whether the secret key is valid.
283    Returns: if this is a valid key.
284  */
285 static int
286 check_secret_key( DSA_secret_key *sk )
287 {
288   int rc;
289   gcry_mpi_t y = mpi_alloc( mpi_get_nlimbs(sk->y) );
290
291   gcry_mpi_powm( y, sk->g, sk->x, sk->p );
292   rc = !mpi_cmp( y, sk->y );
293   mpi_free( y );
294   return rc;
295 }
296
297
298
299 /*
300    Make a DSA signature from HASH and put it into r and s.
301  */
302 static void
303 sign(gcry_mpi_t r, gcry_mpi_t s, gcry_mpi_t hash, DSA_secret_key *skey )
304 {
305   gcry_mpi_t k;
306   gcry_mpi_t kinv;
307   gcry_mpi_t tmp;
308
309   /* Select a random k with 0 < k < q */
310   k = gen_k( skey->q );
311
312   /* r = (a^k mod p) mod q */
313   gcry_mpi_powm( r, skey->g, k, skey->p );
314   mpi_fdiv_r( r, r, skey->q );
315
316   /* kinv = k^(-1) mod q */
317   kinv = mpi_alloc( mpi_get_nlimbs(k) );
318   mpi_invm(kinv, k, skey->q );
319
320   /* s = (kinv * ( hash + x * r)) mod q */
321   tmp = mpi_alloc( mpi_get_nlimbs(skey->p) );
322   mpi_mul( tmp, skey->x, r );
323   mpi_add( tmp, tmp, hash );
324   mpi_mulm( s , kinv, tmp, skey->q );
325
326   mpi_free(k);
327   mpi_free(kinv);
328   mpi_free(tmp);
329 }
330
331
332 /*
333    Returns true if the signature composed from R and S is valid.
334  */
335 static int
336 verify (gcry_mpi_t r, gcry_mpi_t s, gcry_mpi_t hash, DSA_public_key *pkey )
337 {
338   int rc;
339   gcry_mpi_t w, u1, u2, v;
340   gcry_mpi_t base[3];
341   gcry_mpi_t ex[3];
342
343   if( !(mpi_cmp_ui( r, 0 ) > 0 && mpi_cmp( r, pkey->q ) < 0) )
344     return 0; /* assertion      0 < r < q  failed */
345   if( !(mpi_cmp_ui( s, 0 ) > 0 && mpi_cmp( s, pkey->q ) < 0) )
346     return 0; /* assertion      0 < s < q  failed */
347
348   w  = mpi_alloc( mpi_get_nlimbs(pkey->q) );
349   u1 = mpi_alloc( mpi_get_nlimbs(pkey->q) );
350   u2 = mpi_alloc( mpi_get_nlimbs(pkey->q) );
351   v  = mpi_alloc( mpi_get_nlimbs(pkey->p) );
352
353   /* w = s^(-1) mod q */
354   mpi_invm( w, s, pkey->q );
355
356   /* u1 = (hash * w) mod q */
357   mpi_mulm( u1, hash, w, pkey->q );
358
359   /* u2 = r * w mod q  */
360   mpi_mulm( u2, r, w, pkey->q );
361
362   /* v =  g^u1 * y^u2 mod p mod q */
363   base[0] = pkey->g; ex[0] = u1;
364   base[1] = pkey->y; ex[1] = u2;
365   base[2] = NULL;    ex[2] = NULL;
366   mpi_mulpowm( v, base, ex, pkey->p );
367   mpi_fdiv_r( v, v, pkey->q );
368
369   rc = !mpi_cmp( v, r );
370
371   mpi_free(w);
372   mpi_free(u1);
373   mpi_free(u2);
374   mpi_free(v);
375
376   return rc;
377 }
378
379
380 /*********************************************
381  **************  interface  ******************
382  *********************************************/
383
384 gcry_err_code_t
385 _gcry_dsa_generate (int algo, unsigned nbits, unsigned long dummy,
386                     gcry_mpi_t *skey, gcry_mpi_t **retfactors)
387 {
388   gpg_err_code_t err;
389   DSA_secret_key sk;
390
391   err = generate (&sk, nbits, retfactors);
392   if (!err)
393     {
394       skey[0] = sk.p;
395       skey[1] = sk.q;
396       skey[2] = sk.g;
397       skey[3] = sk.y;
398       skey[4] = sk.x;
399     }
400
401   return err;
402 }
403
404
405 gcry_err_code_t
406 _gcry_dsa_check_secret_key (int algo, gcry_mpi_t *skey)
407 {
408   gcry_err_code_t err = GPG_ERR_NO_ERROR;
409   DSA_secret_key sk;
410
411   if ((! skey[0]) || (! skey[1]) || (! skey[2]) || (! skey[3]) || (! skey[4]))
412     err = GPG_ERR_BAD_MPI;
413   else
414     {
415       sk.p = skey[0];
416       sk.q = skey[1];
417       sk.g = skey[2];
418       sk.y = skey[3];
419       sk.x = skey[4];
420       if (! check_secret_key (&sk))
421         err = GPG_ERR_BAD_SECKEY;
422     }
423
424   return err;
425 }
426
427
428 gcry_err_code_t
429 _gcry_dsa_sign (int algo, gcry_mpi_t *resarr, gcry_mpi_t data, gcry_mpi_t *skey)
430 {
431   gcry_err_code_t err = GPG_ERR_NO_ERROR;
432   DSA_secret_key sk;
433
434   if ((! data)
435       || (! skey[0]) || (! skey[1]) || (! skey[2])
436       || (! skey[3]) || (! skey[4]))
437     err = GPG_ERR_BAD_MPI;
438   else
439     {
440       sk.p = skey[0];
441       sk.q = skey[1];
442       sk.g = skey[2];
443       sk.y = skey[3];
444       sk.x = skey[4];
445       resarr[0] = mpi_alloc (mpi_get_nlimbs (sk.p));
446       resarr[1] = mpi_alloc (mpi_get_nlimbs (sk.p));
447       sign (resarr[0], resarr[1], data, &sk);
448     }
449   return err;
450 }
451
452 gcry_err_code_t
453 _gcry_dsa_verify (int algo, gcry_mpi_t hash, gcry_mpi_t *data, gcry_mpi_t *pkey,
454                   int (*cmp) (void *, gcry_mpi_t), void *opaquev)
455 {
456   gcry_err_code_t err = GPG_ERR_NO_ERROR;
457   DSA_public_key pk;
458
459   if ((! data[0]) || (! data[1]) || (! hash)
460       || (! pkey[0]) || (! pkey[1]) || (! pkey[2]) || (! pkey[3]))
461     err = GPG_ERR_BAD_MPI;
462   else
463     {
464       pk.p = pkey[0];
465       pk.q = pkey[1];
466       pk.g = pkey[2];
467       pk.y = pkey[3];
468       if (! verify (data[0], data[1], hash, &pk))
469         err = GPG_ERR_BAD_SIGNATURE;
470     }
471   return err;
472 }
473
474
475 unsigned int
476 _gcry_dsa_get_nbits (int algo, gcry_mpi_t *pkey)
477 {
478   return mpi_get_nbits (pkey[0]);
479 }
480
481 static char *dsa_names[] =
482   {
483     "dsa",
484     "openpgp-dsa",
485     NULL,
486   };
487
488 gcry_pk_spec_t _gcry_pubkey_spec_dsa =
489   {
490     "DSA", dsa_names, 
491     "pqgy", "pqgyx", "", "rs", "pqgy",
492     GCRY_PK_USAGE_SIGN,
493     _gcry_dsa_generate,
494     _gcry_dsa_check_secret_key,
495     NULL,
496     NULL,
497     _gcry_dsa_sign,
498     _gcry_dsa_verify,
499     _gcry_dsa_get_nbits,
500   };
501