Mostly indendation changes. Completed the Manifest.
[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 void 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 void
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   byte *rndbuf;
186
187   assert( nbits >= 512 && nbits <= 1024 );
188
189   qbits = 160;
190   p = _gcry_generate_elg_prime( 1, nbits, qbits, NULL, ret_factors );
191   /* get q out of factors */
192   q = mpi_copy((*ret_factors)[0]);
193   if( mpi_get_nbits(q) != qbits )
194     BUG();
195
196   /* Find a generator g (h and e are helpers).
197      e = (p-1)/q */
198   e = mpi_alloc( mpi_get_nlimbs(p) );
199   mpi_sub_ui( e, p, 1 );
200   mpi_fdiv_q( e, e, q );
201   g = mpi_alloc( mpi_get_nlimbs(p) );
202   h = mpi_alloc_set_ui( 1 ); /* we start with 2 */
203   do
204     {
205       mpi_add_ui( h, h, 1 );
206       /* g = h^e mod p */
207       gcry_mpi_powm( g, h, e, p );
208     } 
209   while( !mpi_cmp_ui( g, 1 ) );  /* continue until g != 1 */
210
211   /* Select a random number which has these properties:
212    *     0 < x < q-1
213    * This must be a very good random number because this
214    * is the secret part. */
215   if( DBG_CIPHER )
216     log_debug("choosing a random x ");
217   assert( qbits >= 160 );
218   x = mpi_alloc_secure( mpi_get_nlimbs(q) );
219   mpi_sub_ui( h, q, 1 );  /* put q-1 into h */
220   rndbuf = NULL;
221   do 
222     {
223       if( DBG_CIPHER )
224         progress('.');
225       if( !rndbuf )
226         rndbuf = gcry_random_bytes_secure( (qbits+7)/8,
227                                            GCRY_VERY_STRONG_RANDOM );
228       else 
229         { /* Change only some of the higher bits (= 2 bytes)*/
230           char *r = gcry_random_bytes_secure (2, GCRY_VERY_STRONG_RANDOM);
231           memcpy(rndbuf, r, 2 );
232           gcry_free(r);
233         }
234
235       _gcry_mpi_set_buffer( x, rndbuf, (qbits+7)/8, 0 );
236       mpi_clear_highbit( x, qbits+1 );
237     } 
238   while ( !( mpi_cmp_ui( x, 0 )>0 && mpi_cmp( x, h )<0 ) );
239   gcry_free(rndbuf);
240   mpi_free( e );
241   mpi_free( h );
242
243   /* y = g^x mod p */
244   y = mpi_alloc( mpi_get_nlimbs(p) );
245   gcry_mpi_powm( y, g, x, p );
246
247   if( DBG_CIPHER ) 
248     {
249       progress('\n');
250       log_mpidump("dsa  p= ", p );
251       log_mpidump("dsa  q= ", q );
252       log_mpidump("dsa  g= ", g );
253       log_mpidump("dsa  y= ", y );
254       log_mpidump("dsa  x= ", x );
255     }
256
257   /* Copy the stuff to the key structures. */
258   sk->p = p;
259   sk->q = q;
260   sk->g = g;
261   sk->y = y;
262   sk->x = x;
263
264   /* Now we can test our keys (this should never fail!). */
265   test_keys( sk, qbits );
266 }
267
268
269
270 /*
271    Test whether the secret key is valid.
272    Returns: if this is a valid key.
273  */
274 static int
275 check_secret_key( DSA_secret_key *sk )
276 {
277   int rc;
278   gcry_mpi_t y = mpi_alloc( mpi_get_nlimbs(sk->y) );
279
280   gcry_mpi_powm( y, sk->g, sk->x, sk->p );
281   rc = !mpi_cmp( y, sk->y );
282   mpi_free( y );
283   return rc;
284 }
285
286
287
288 /*
289    Make a DSA signature from HASH and put it into r and s.
290  */
291 static void
292 sign(gcry_mpi_t r, gcry_mpi_t s, gcry_mpi_t hash, DSA_secret_key *skey )
293 {
294   gcry_mpi_t k;
295   gcry_mpi_t kinv;
296   gcry_mpi_t tmp;
297
298   /* Select a random k with 0 < k < q */
299   k = gen_k( skey->q );
300
301   /* r = (a^k mod p) mod q */
302   gcry_mpi_powm( r, skey->g, k, skey->p );
303   mpi_fdiv_r( r, r, skey->q );
304
305   /* kinv = k^(-1) mod q */
306   kinv = mpi_alloc( mpi_get_nlimbs(k) );
307   mpi_invm(kinv, k, skey->q );
308
309   /* s = (kinv * ( hash + x * r)) mod q */
310   tmp = mpi_alloc( mpi_get_nlimbs(skey->p) );
311   mpi_mul( tmp, skey->x, r );
312   mpi_add( tmp, tmp, hash );
313   mpi_mulm( s , kinv, tmp, skey->q );
314
315   mpi_free(k);
316   mpi_free(kinv);
317   mpi_free(tmp);
318 }
319
320
321 /*
322    Returns true if the signature composed from R and S is valid.
323  */
324 static int
325 verify (gcry_mpi_t r, gcry_mpi_t s, gcry_mpi_t hash, DSA_public_key *pkey )
326 {
327   int rc;
328   gcry_mpi_t w, u1, u2, v;
329   gcry_mpi_t base[3];
330   gcry_mpi_t ex[3];
331
332   if( !(mpi_cmp_ui( r, 0 ) > 0 && mpi_cmp( r, pkey->q ) < 0) )
333     return 0; /* assertion      0 < r < q  failed */
334   if( !(mpi_cmp_ui( s, 0 ) > 0 && mpi_cmp( s, pkey->q ) < 0) )
335     return 0; /* assertion      0 < s < q  failed */
336
337   w  = mpi_alloc( mpi_get_nlimbs(pkey->q) );
338   u1 = mpi_alloc( mpi_get_nlimbs(pkey->q) );
339   u2 = mpi_alloc( mpi_get_nlimbs(pkey->q) );
340   v  = mpi_alloc( mpi_get_nlimbs(pkey->p) );
341
342   /* w = s^(-1) mod q */
343   mpi_invm( w, s, pkey->q );
344
345   /* u1 = (hash * w) mod q */
346   mpi_mulm( u1, hash, w, pkey->q );
347
348   /* u2 = r * w mod q  */
349   mpi_mulm( u2, r, w, pkey->q );
350
351   /* v =  g^u1 * y^u2 mod p mod q */
352   base[0] = pkey->g; ex[0] = u1;
353   base[1] = pkey->y; ex[1] = u2;
354   base[2] = NULL;    ex[2] = NULL;
355   mpi_mulpowm( v, base, ex, pkey->p );
356   mpi_fdiv_r( v, v, pkey->q );
357
358   rc = !mpi_cmp( v, r );
359
360   mpi_free(w);
361   mpi_free(u1);
362   mpi_free(u2);
363   mpi_free(v);
364
365   return rc;
366 }
367
368
369 /*********************************************
370  **************  interface  ******************
371  *********************************************/
372
373 gcry_err_code_t
374 _gcry_dsa_generate (int algo, unsigned nbits, unsigned long dummy,
375                     gcry_mpi_t *skey, gcry_mpi_t **retfactors)
376 {
377   DSA_secret_key sk;
378
379   generate (&sk, nbits, retfactors);
380   skey[0] = sk.p;
381   skey[1] = sk.q;
382   skey[2] = sk.g;
383   skey[3] = sk.y;
384   skey[4] = sk.x;
385
386   return GPG_ERR_NO_ERROR;
387 }
388
389
390 gcry_err_code_t
391 _gcry_dsa_check_secret_key (int algo, gcry_mpi_t *skey)
392 {
393   gcry_err_code_t err = GPG_ERR_NO_ERROR;
394   DSA_secret_key sk;
395
396   if ((! skey[0]) || (! skey[1]) || (! skey[2]) || (! skey[3]) || (! skey[4]))
397     err = GPG_ERR_BAD_MPI;
398   else
399     {
400       sk.p = skey[0];
401       sk.q = skey[1];
402       sk.g = skey[2];
403       sk.y = skey[3];
404       sk.x = skey[4];
405       if (! check_secret_key (&sk))
406         err = GPG_ERR_BAD_SECKEY;
407     }
408
409   return err;
410 }
411
412
413 gcry_err_code_t
414 _gcry_dsa_sign (int algo, gcry_mpi_t *resarr, gcry_mpi_t data, gcry_mpi_t *skey)
415 {
416   gcry_err_code_t err = GPG_ERR_NO_ERROR;
417   DSA_secret_key sk;
418
419   if ((! data)
420       || (! skey[0]) || (! skey[1]) || (! skey[2])
421       || (! skey[3]) || (! skey[4]))
422     err = GPG_ERR_BAD_MPI;
423   else
424     {
425       sk.p = skey[0];
426       sk.q = skey[1];
427       sk.g = skey[2];
428       sk.y = skey[3];
429       sk.x = skey[4];
430       resarr[0] = mpi_alloc (mpi_get_nlimbs (sk.p));
431       resarr[1] = mpi_alloc (mpi_get_nlimbs (sk.p));
432       sign (resarr[0], resarr[1], data, &sk);
433     }
434   return err;
435 }
436
437 gcry_err_code_t
438 _gcry_dsa_verify (int algo, gcry_mpi_t hash, gcry_mpi_t *data, gcry_mpi_t *pkey,
439                   int (*cmp) (void *, gcry_mpi_t), void *opaquev)
440 {
441   gcry_err_code_t err = GPG_ERR_NO_ERROR;
442   DSA_public_key pk;
443
444   if ((! data[0]) || (! data[1]) || (! hash)
445       || (! pkey[0]) || (! pkey[1]) || (! pkey[2]) || (! pkey[3]))
446     err = GPG_ERR_BAD_MPI;
447   else
448     {
449       pk.p = pkey[0];
450       pk.q = pkey[1];
451       pk.g = pkey[2];
452       pk.y = pkey[3];
453       if (! verify (data[0], data[1], hash, &pk))
454         err = GPG_ERR_BAD_SIGNATURE;
455     }
456   return err;
457 }
458
459
460 unsigned int
461 _gcry_dsa_get_nbits (int algo, gcry_mpi_t *pkey)
462 {
463   return mpi_get_nbits (pkey[0]);
464 }
465
466 static char *dsa_names[] =
467   {
468     "dsa",
469     "openpgp-dsa",
470     NULL,
471   };
472
473 gcry_pk_spec_t _gcry_pubkey_spec_dsa =
474   {
475     "DSA", dsa_names, 
476     "pqgy", "pqgyx", "", "rs", "pqgy",
477     GCRY_PK_USAGE_SIGN,
478     _gcry_dsa_generate,
479     _gcry_dsa_check_secret_key,
480     NULL,
481     NULL,
482     _gcry_dsa_sign,
483     _gcry_dsa_verify,
484     _gcry_dsa_get_nbits,
485   };
486