2003-04-27 Moritz Schulte <moritz@g10code.com>
[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     MPI p;          /* prime */
33     MPI q;          /* group order */
34     MPI g;          /* group generator */
35     MPI y;          /* g^x mod p */
36 } DSA_public_key;
37
38
39 typedef struct {
40     MPI p;          /* prime */
41     MPI q;          /* group order */
42     MPI g;          /* group generator */
43     MPI y;          /* g^x mod p */
44     MPI x;          /* secret exponent */
45 } DSA_secret_key;
46
47
48 static MPI gen_k( MPI q );
49 static void test_keys( DSA_secret_key *sk, unsigned qbits );
50 static int  check_secret_key( DSA_secret_key *sk );
51 static void generate( DSA_secret_key *sk, unsigned nbits, MPI **ret_factors );
52 static void sign(MPI r, MPI s, MPI input, DSA_secret_key *skey);
53 static int  verify(MPI r, MPI s, MPI input, DSA_public_key *pkey);
54
55 static void (*progress_cb) (void *,const char *, int, int, int );
56 static void *progress_cb_data;
57
58 void
59 _gcry_register_pk_dsa_progress ( void (*cb)( void *,const char *, int,int,int),
60                                  void *cb_data )
61 {
62     progress_cb = cb;
63     progress_cb_data = cb_data;
64 }
65
66
67 static void
68 progress( int c )
69 {
70   if (progress_cb)
71     progress_cb ( progress_cb_data, "pk_dsa", c, 0, 0);
72 }
73
74
75
76 /****************
77  * Generate a random secret exponent k less than q
78  */
79 static MPI
80 gen_k( MPI q )
81 {
82     MPI k = mpi_alloc_secure( mpi_get_nlimbs(q) );
83     unsigned int nbits = mpi_get_nbits(q);
84     unsigned int nbytes = (nbits+7)/8;
85     char *rndbuf = NULL;
86
87     if( DBG_CIPHER )
88         log_debug("choosing a random k ");
89     for(;;) {
90         if( DBG_CIPHER )
91             progress('.');
92
93         if( !rndbuf || nbits < 32 ) {
94             gcry_free(rndbuf);
95             rndbuf = gcry_random_bytes_secure( (nbits+7)/8,
96                                                GCRY_STRONG_RANDOM );
97         }
98         else { /* change only some of the higher bits */
99             /* we could imporove this by directly requesting more memory
100              * at the first call to get_random_bytes() and use this the here
101              * maybe it is easier to do this directly in random.c */
102             char *pp = gcry_random_bytes_secure( 4, GCRY_STRONG_RANDOM );
103             memcpy( rndbuf,pp, 4 );
104             gcry_free(pp);
105         }
106         _gcry_mpi_set_buffer( k, rndbuf, nbytes, 0 );
107         if( mpi_test_bit( k, nbits-1 ) )
108             mpi_set_highbit( k, nbits-1 );
109         else {
110             mpi_set_highbit( k, nbits-1 );
111             mpi_clear_bit( k, nbits-1 );
112         }
113
114         if( !(mpi_cmp( k, q ) < 0) ) {  /* check: k < q */
115             if( DBG_CIPHER )
116                 progress('+');
117             continue; /* no  */
118         }
119         if( !(mpi_cmp_ui( k, 0 ) > 0) ) { /* check: k > 0 */
120             if( DBG_CIPHER )
121                 progress('-');
122             continue; /* no */
123         }
124         break;  /* okay */
125     }
126     gcry_free(rndbuf);
127     if( DBG_CIPHER )
128         progress('\n');
129
130     return k;
131 }
132
133
134 static void
135 test_keys( DSA_secret_key *sk, unsigned qbits )
136 {
137     DSA_public_key pk;
138     MPI test = gcry_mpi_new ( qbits  );
139     MPI out1_a = gcry_mpi_new ( qbits );
140     MPI out1_b = gcry_mpi_new ( qbits );
141
142     pk.p = sk->p;
143     pk.q = sk->q;
144     pk.g = sk->g;
145     pk.y = sk->y;
146     gcry_mpi_randomize( test, qbits, GCRY_WEAK_RANDOM );
147
148     sign( out1_a, out1_b, test, sk );
149     if( !verify( out1_a, out1_b, test, &pk ) )
150         log_fatal("DSA:: sign, verify failed\n");
151
152     gcry_mpi_release ( test );
153     gcry_mpi_release ( out1_a );
154     gcry_mpi_release ( out1_b );
155 }
156
157
158
159 /****************
160  * Generate a DSA key pair with a key of size NBITS
161  * Returns: 2 structures filled with all needed values
162  *          and an array with the n-1 factors of (p-1)
163  */
164 static void
165 generate( DSA_secret_key *sk, unsigned nbits, MPI **ret_factors )
166 {
167     MPI p;    /* the prime */
168     MPI q;    /* the 160 bit prime factor */
169     MPI g;    /* the generator */
170     MPI y;    /* g^x mod p */
171     MPI x;    /* the secret exponent */
172     MPI h, e;  /* helper */
173     unsigned qbits;
174     byte *rndbuf;
175
176     assert( nbits >= 512 && nbits <= 1024 );
177
178     qbits = 160;
179     p = _gcry_generate_elg_prime( 1, nbits, qbits, NULL, ret_factors );
180     /* get q out of factors */
181     q = mpi_copy((*ret_factors)[0]);
182     if( mpi_get_nbits(q) != qbits )
183         BUG();
184
185     /* find a generator g (h and e are helpers)*/
186     /* e = (p-1)/q */
187     e = mpi_alloc( mpi_get_nlimbs(p) );
188     mpi_sub_ui( e, p, 1 );
189     mpi_fdiv_q( e, e, q );
190     g = mpi_alloc( mpi_get_nlimbs(p) );
191     h = mpi_alloc_set_ui( 1 ); /* we start with 2 */
192     do {
193         mpi_add_ui( h, h, 1 );
194         /* g = h^e mod p */
195         gcry_mpi_powm( g, h, e, p );
196     } while( !mpi_cmp_ui( g, 1 ) );  /* continue until g != 1 */
197
198     /* select a random number which has these properties:
199      *   0 < x < q-1
200      * This must be a very good random number because this
201      * is the secret part. */
202     if( DBG_CIPHER )
203         log_debug("choosing a random x ");
204     assert( qbits >= 160 );
205     x = mpi_alloc_secure( mpi_get_nlimbs(q) );
206     mpi_sub_ui( h, q, 1 );  /* put q-1 into h */
207     rndbuf = NULL;
208     do {
209         if( DBG_CIPHER )
210             progress('.');
211         if( !rndbuf )
212             rndbuf = gcry_random_bytes_secure( (qbits+7)/8,
213                                                GCRY_VERY_STRONG_RANDOM );
214         else { /* change only some of the higher bits (= 2 bytes)*/
215             char *r = gcry_random_bytes_secure( 2,
216                                                 GCRY_VERY_STRONG_RANDOM );
217             memcpy(rndbuf, r, 2 );
218             gcry_free(r);
219         }
220         _gcry_mpi_set_buffer( x, rndbuf, (qbits+7)/8, 0 );
221         mpi_clear_highbit( x, qbits+1 );
222     } while( !( mpi_cmp_ui( x, 0 )>0 && mpi_cmp( x, h )<0 ) );
223     gcry_free(rndbuf);
224     mpi_free( e );
225     mpi_free( h );
226
227     /* y = g^x mod p */
228     y = mpi_alloc( mpi_get_nlimbs(p) );
229     gcry_mpi_powm( y, g, x, p );
230
231     if( DBG_CIPHER ) {
232         progress('\n');
233         log_mpidump("dsa  p= ", p );
234         log_mpidump("dsa  q= ", q );
235         log_mpidump("dsa  g= ", g );
236         log_mpidump("dsa  y= ", y );
237         log_mpidump("dsa  x= ", x );
238     }
239
240     /* copy the stuff to the key structures */
241     sk->p = p;
242     sk->q = q;
243     sk->g = g;
244     sk->y = y;
245     sk->x = x;
246
247     /* now we can test our keys (this should never fail!) */
248     test_keys( sk, qbits );
249 }
250
251
252
253 /****************
254  * Test whether the secret key is valid.
255  * Returns: if this is a valid key.
256  */
257 static int
258 check_secret_key( DSA_secret_key *sk )
259 {
260     int rc;
261     MPI y = mpi_alloc( mpi_get_nlimbs(sk->y) );
262
263     gcry_mpi_powm( y, sk->g, sk->x, sk->p );
264     rc = !mpi_cmp( y, sk->y );
265     mpi_free( y );
266     return rc;
267 }
268
269
270
271 /****************
272  * Make a DSA signature from HASH and put it into r and s.
273  */
274
275 static void
276 sign(MPI r, MPI s, MPI hash, DSA_secret_key *skey )
277 {
278     MPI k;
279     MPI kinv;
280     MPI tmp;
281
282     /* select a random k with 0 < k < q */
283     k = gen_k( skey->q );
284
285     /* r = (a^k mod p) mod q */
286     gcry_mpi_powm( r, skey->g, k, skey->p );
287     mpi_fdiv_r( r, r, skey->q );
288
289     /* kinv = k^(-1) mod q */
290     kinv = mpi_alloc( mpi_get_nlimbs(k) );
291     mpi_invm(kinv, k, skey->q );
292
293     /* s = (kinv * ( hash + x * r)) mod q */
294     tmp = mpi_alloc( mpi_get_nlimbs(skey->p) );
295     mpi_mul( tmp, skey->x, r );
296     mpi_add( tmp, tmp, hash );
297     mpi_mulm( s , kinv, tmp, skey->q );
298
299     mpi_free(k);
300     mpi_free(kinv);
301     mpi_free(tmp);
302 }
303
304
305 /****************
306  * Returns true if the signature composed from R and S is valid.
307  */
308 static int
309 verify(MPI r, MPI s, MPI hash, DSA_public_key *pkey )
310 {
311     int rc;
312     MPI w, u1, u2, v;
313     MPI base[3];
314     MPI exp[3];
315
316
317     if( !(mpi_cmp_ui( r, 0 ) > 0 && mpi_cmp( r, pkey->q ) < 0) )
318         return 0; /* assertion  0 < r < q  failed */
319     if( !(mpi_cmp_ui( s, 0 ) > 0 && mpi_cmp( s, pkey->q ) < 0) )
320         return 0; /* assertion  0 < s < q  failed */
321
322     w  = mpi_alloc( mpi_get_nlimbs(pkey->q) );
323     u1 = mpi_alloc( mpi_get_nlimbs(pkey->q) );
324     u2 = mpi_alloc( mpi_get_nlimbs(pkey->q) );
325     v  = mpi_alloc( mpi_get_nlimbs(pkey->p) );
326
327     /* w = s^(-1) mod q */
328     mpi_invm( w, s, pkey->q );
329
330     /* u1 = (hash * w) mod q */
331     mpi_mulm( u1, hash, w, pkey->q );
332
333     /* u2 = r * w mod q  */
334     mpi_mulm( u2, r, w, pkey->q );
335
336     /* v =  g^u1 * y^u2 mod p mod q */
337     base[0] = pkey->g; exp[0] = u1;
338     base[1] = pkey->y; exp[1] = u2;
339     base[2] = NULL;    exp[2] = NULL;
340     mpi_mulpowm( v, base, exp, pkey->p );
341     mpi_fdiv_r( v, v, pkey->q );
342
343     rc = !mpi_cmp( v, r );
344
345     mpi_free(w);
346     mpi_free(u1);
347     mpi_free(u2);
348     mpi_free(v);
349     return rc;
350 }
351
352
353 /*********************************************
354  **************  interface  ******************
355  *********************************************/
356
357 int
358 _gcry_dsa_generate( int algo, unsigned nbits, unsigned long dummy,
359                     MPI *skey, MPI **retfactors )
360 {
361     DSA_secret_key sk;
362
363     if( algo != GCRY_PK_DSA )
364         return GCRYERR_INV_PK_ALGO;
365
366     generate( &sk, nbits, retfactors );
367     skey[0] = sk.p;
368     skey[1] = sk.q;
369     skey[2] = sk.g;
370     skey[3] = sk.y;
371     skey[4] = sk.x;
372     return 0;
373 }
374
375
376 int
377 _gcry_dsa_check_secret_key( int algo, MPI *skey )
378 {
379     DSA_secret_key sk;
380
381     if( algo != GCRY_PK_DSA )
382         return GCRYERR_INV_PK_ALGO;
383     if( !skey[0] || !skey[1] || !skey[2] || !skey[3] || !skey[4] )
384         return GCRYERR_BAD_MPI;
385
386     sk.p = skey[0];
387     sk.q = skey[1];
388     sk.g = skey[2];
389     sk.y = skey[3];
390     sk.x = skey[4];
391     if( !check_secret_key( &sk ) )
392         return GCRYERR_BAD_SECRET_KEY;
393
394     return 0;
395 }
396
397
398
399 int
400 _gcry_dsa_sign( int algo, MPI *resarr, MPI data, MPI *skey )
401 {
402     DSA_secret_key sk;
403
404     if( algo != GCRY_PK_DSA )
405         return GCRYERR_INV_PK_ALGO;
406     if( !data || !skey[0] || !skey[1] || !skey[2] || !skey[3] || !skey[4] )
407         return GCRYERR_BAD_MPI;
408
409     sk.p = skey[0];
410     sk.q = skey[1];
411     sk.g = skey[2];
412     sk.y = skey[3];
413     sk.x = skey[4];
414     resarr[0] = mpi_alloc( mpi_get_nlimbs( sk.p ) );
415     resarr[1] = mpi_alloc( mpi_get_nlimbs( sk.p ) );
416     sign( resarr[0], resarr[1], data, &sk );
417     return 0;
418 }
419
420 int
421 _gcry_dsa_verify( int algo, MPI hash, MPI *data, MPI *pkey,
422                     int (*cmp)(void *, MPI), void *opaquev )
423 {
424     DSA_public_key pk;
425
426     if( algo != GCRY_PK_DSA )
427         return GCRYERR_INV_PK_ALGO;
428     if( !data[0] || !data[1] || !hash
429         || !pkey[0] || !pkey[1] || !pkey[2] || !pkey[3] )
430         return GCRYERR_BAD_MPI;
431
432     pk.p = pkey[0];
433     pk.q = pkey[1];
434     pk.g = pkey[2];
435     pk.y = pkey[3];
436     if( !verify( data[0], data[1], hash, &pk ) )
437         return GCRYERR_BAD_SIGNATURE;
438     return 0;
439 }
440
441
442
443 unsigned int
444 _gcry_dsa_get_nbits( int algo, MPI *pkey )
445 {
446     if( algo != GCRY_PK_DSA )
447         return 0;
448     return mpi_get_nbits( pkey[0] );
449 }
450
451 static char *dsa_names[] =
452   {
453     "dsa",
454     "openpgp-dsa",
455     NULL,
456   };
457
458 GcryPubkeySpec pubkey_spec_dsa =
459   {
460     "DSA", dsa_names, GCRY_PK_DSA,
461     "pqgy", "pqgyx", "", "rs", "pqgy",
462     GCRY_PK_USAGE_SIGN,
463     _gcry_dsa_generate,
464     _gcry_dsa_check_secret_key,
465     NULL,
466     NULL,
467     _gcry_dsa_sign,
468     _gcry_dsa_verify,
469     _gcry_dsa_get_nbits,
470   };