1 /* dsa.c - DSA signature scheme
2 * Copyright (C) 1998 Free Software Foundation, Inc.
4 * This file is part of GnuPG.
6 * GnuPG is free software; you can redistribute it and/or modify
7 * it under the terms of the GNU General Public License as published by
8 * the Free Software Foundation; either version 2 of the License, or
9 * (at your option) any later version.
11 * GnuPG 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 General Public License for more details.
16 * You should have received a copy of the GNU General Public License
17 * along with this program; if not, write to the Free Software
18 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA
24 #include "constants.h"
28 #include "gcryptfix.h"
30 /* #include <config.h> */
38 /* #include <assert.h> */
39 /* #include "util.h" */
40 /* #include "mpi.h" */
41 /* #include "cipher.h" */
48 MPI q; /* group order */
49 MPI g; /* group generator */
50 MPI y; /* g^x mod p */
56 MPI q; /* group order */
57 MPI g; /* group generator */
58 MPI y; /* g^x mod p */
59 MPI x; /* secret exponent */
63 static MPI gen_k( MPI q );
64 static void test_keys( DSA_secret_key *sk, unsigned qbits );
65 static int check_secret_key( DSA_secret_key *sk );
66 static void generate( DSA_secret_key *sk, unsigned nbits, MPI **ret_factors );
67 static void sign(MPI r, MPI s, MPI input, DSA_secret_key *skey);
68 static int verify(MPI r, MPI s, MPI input, DSA_public_key *pkey);
78 * Generate a random secret exponent k less than q
83 MPI k = mpi_alloc_secure( mpi_get_nlimbs(q) );
84 unsigned int nbits = mpi_get_nbits(q);
85 unsigned int nbytes = (nbits+7)/8;
89 log_debug("choosing a random k ");
94 if( !rndbuf || nbits < 32 ) {
96 rndbuf = get_random_bits( nbits, 1, 1 );
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_bits() and use this the here
101 * maybe it is easier to do this directly in random.c */
102 char *pp = get_random_bits( 32, 1, 1 );
103 memcpy( rndbuf,pp, 4 );
106 mpi_set_buffer( k, rndbuf, nbytes, 0 );
107 if( mpi_test_bit( k, nbits-1 ) )
108 mpi_set_highbit( k, nbits-1 );
110 mpi_set_highbit( k, nbits-1 );
111 mpi_clear_bit( k, nbits-1 );
114 if( !(mpi_cmp( k, q ) < 0) ) { /* check: k < q */
119 if( !(mpi_cmp_ui( k, 0 ) > 0) ) { /* check: k > 0 */
135 test_keys( DSA_secret_key *sk, unsigned qbits )
138 MPI test = mpi_alloc( qbits / BITS_PER_MPI_LIMB );
139 MPI out1_a = mpi_alloc( qbits / BITS_PER_MPI_LIMB );
140 MPI out1_b = mpi_alloc( qbits / BITS_PER_MPI_LIMB );
146 /*mpi_set_bytes( test, qbits, get_random_byte, 0 );*/
147 { char *p = get_random_bits( qbits, 0, 0 );
148 mpi_set_buffer( test, p, (qbits+7)/8, 0 );
152 sign( out1_a, out1_b, test, sk );
153 if( !verify( out1_a, out1_b, test, &pk ) )
154 log_fatal("DSA:: sign, verify failed\n");
164 * Generate a DSA key pair with a key of size NBITS
165 * Returns: 2 structures filled with all needed values
166 * and an array with the n-1 factors of (p-1)
169 generate( DSA_secret_key *sk, unsigned nbits, MPI **ret_factors )
171 MPI p; /* the prime */
172 MPI q; /* the 160 bit prime factor */
173 MPI g; /* the generator */
174 MPI y; /* g^x mod p */
175 MPI x; /* the secret exponent */
176 MPI h, e; /* helper */
180 assert( nbits >= 512 && nbits <= 1024 );
183 p = generate_elg_prime( 1, nbits, qbits, NULL, ret_factors );
184 /* get q out of factors */
185 q = mpi_copy((*ret_factors)[0]);
186 if( mpi_get_nbits(q) != qbits )
189 /* find a generator g (h and e are helpers)*/
191 e = mpi_alloc( mpi_get_nlimbs(p) );
192 mpi_sub_ui( e, p, 1 );
193 mpi_fdiv_q( e, e, q );
194 g = mpi_alloc( mpi_get_nlimbs(p) );
195 h = mpi_alloc_set_ui( 1 ); /* we start with 2 */
197 mpi_add_ui( h, h, 1 );
199 mpi_powm( g, h, e, p );
200 } while( !mpi_cmp_ui( g, 1 ) ); /* continue until g != 1 */
202 /* select a random number which has these properties:
204 * This must be a very good random number because this
205 * is the secret part. */
207 log_debug("choosing a random x ");
208 assert( qbits >= 160 );
209 x = mpi_alloc_secure( mpi_get_nlimbs(q) );
210 mpi_sub_ui( h, q, 1 ); /* put q-1 into h */
216 rndbuf = get_random_bits( qbits, 2, 1 );
217 else { /* change only some of the higher bits (= 2 bytes)*/
218 char *r = get_random_bits( 16, 2, 1 );
219 memcpy(rndbuf, r, 16/8 );
222 mpi_set_buffer( x, rndbuf, (qbits+7)/8, 0 );
223 mpi_clear_highbit( x, qbits+1 );
224 } while( !( mpi_cmp_ui( x, 0 )>0 && mpi_cmp( x, h )<0 ) );
230 y = mpi_alloc( mpi_get_nlimbs(p) );
231 mpi_powm( y, g, x, p );
235 log_mpidump("dsa p= ", p );
236 log_mpidump("dsa q= ", q );
237 log_mpidump("dsa g= ", g );
238 log_mpidump("dsa y= ", y );
239 log_mpidump("dsa x= ", x );
242 /* copy the stuff to the key structures */
249 /* now we can test our keys (this should never fail!) */
250 test_keys( sk, qbits );
256 * Test whether the secret key is valid.
257 * Returns: if this is a valid key.
260 check_secret_key( DSA_secret_key *sk )
263 MPI y = mpi_alloc( mpi_get_nlimbs(sk->y) );
265 mpi_powm( y, sk->g, sk->x, sk->p );
266 rc = !mpi_cmp( y, sk->y );
274 * Make a DSA signature from HASH and put it into r and s.
278 sign(MPI r, MPI s, MPI hash, DSA_secret_key *skey )
284 /* select a random k with 0 < k < q */
285 k = gen_k( skey->q );
287 /* r = (a^k mod p) mod q */
288 mpi_powm( r, skey->g, k, skey->p );
289 mpi_fdiv_r( r, r, skey->q );
291 /* kinv = k^(-1) mod q */
292 kinv = mpi_alloc( mpi_get_nlimbs(k) );
293 mpi_invm(kinv, k, skey->q );
295 /* s = (kinv * ( hash + x * r)) mod q */
296 tmp = mpi_alloc( mpi_get_nlimbs(skey->p) );
297 mpi_mul( tmp, skey->x, r );
298 mpi_add( tmp, tmp, hash );
299 mpi_mulm( s , kinv, tmp, skey->q );
308 * Returns true if the signature composed from R and S is valid.
311 verify(MPI r, MPI s, MPI hash, DSA_public_key *pkey )
319 if( !(mpi_cmp_ui( r, 0 ) > 0 && mpi_cmp( r, pkey->q ) < 0) )
320 return 0; /* assertion 0 < r < q failed */
321 if( !(mpi_cmp_ui( s, 0 ) > 0 && mpi_cmp( s, pkey->q ) < 0) )
322 return 0; /* assertion 0 < s < q failed */
324 w = mpi_alloc( mpi_get_nlimbs(pkey->q) );
325 u1 = mpi_alloc( mpi_get_nlimbs(pkey->q) );
326 u2 = mpi_alloc( mpi_get_nlimbs(pkey->q) );
327 v = mpi_alloc( mpi_get_nlimbs(pkey->p) );
329 /* w = s^(-1) mod q */
330 mpi_invm( w, s, pkey->q );
332 /* u1 = (hash * w) mod q */
333 mpi_mulm( u1, hash, w, pkey->q );
335 /* u2 = r * w mod q */
336 mpi_mulm( u2, r, w, pkey->q );
338 /* v = g^u1 * y^u2 mod p mod q */
339 base[0] = pkey->g; exp[0] = u1;
340 base[1] = pkey->y; exp[1] = u2;
341 base[2] = NULL; exp[2] = NULL;
342 mpi_mulpowm( v, base, exp, pkey->p );
343 mpi_fdiv_r( v, v, pkey->q );
345 rc = !mpi_cmp( v, r );
355 /*********************************************
356 ************** interface ******************
357 *********************************************/
360 dsa_generate( int algo, unsigned nbits, MPI *skey, MPI **retfactors )
364 if( algo != PUBKEY_ALGO_DSA )
365 return G10ERR_PUBKEY_ALGO;
367 generate( &sk, nbits, retfactors );
378 dsa_check_secret_key( int algo, MPI *skey )
382 if( algo != PUBKEY_ALGO_DSA )
383 return G10ERR_PUBKEY_ALGO;
384 if( !skey[0] || !skey[1] || !skey[2] || !skey[3] || !skey[4] )
385 return G10ERR_BAD_MPI;
392 if( !check_secret_key( &sk ) )
393 return G10ERR_BAD_SECKEY;
401 dsa_sign( int algo, MPI *resarr, MPI data, MPI *skey )
405 if( algo != PUBKEY_ALGO_DSA )
406 return G10ERR_PUBKEY_ALGO;
407 if( !data || !skey[0] || !skey[1] || !skey[2] || !skey[3] || !skey[4] )
408 return G10ERR_BAD_MPI;
415 resarr[0] = mpi_alloc( mpi_get_nlimbs( sk.p ) );
416 resarr[1] = mpi_alloc( mpi_get_nlimbs( sk.p ) );
417 sign( resarr[0], resarr[1], data, &sk );
422 dsa_verify( int algo, MPI hash, MPI *data, MPI *pkey,
423 int (*cmp)(void *, MPI) UNUSED, void *opaquev UNUSED)
427 if( algo != PUBKEY_ALGO_DSA )
428 return G10ERR_PUBKEY_ALGO;
429 if( !data[0] || !data[1] || !hash
430 || !pkey[0] || !pkey[1] || !pkey[2] || !pkey[3] )
431 return G10ERR_BAD_MPI;
437 if( !verify( data[0], data[1], hash, &pk ) )
438 return G10ERR_BAD_SIGN;
445 dsa_get_nbits( int algo, MPI *pkey )
447 if( algo != PUBKEY_ALGO_DSA )
449 return mpi_get_nbits( pkey[0] );
454 * Return some information about the algorithm. We need algo here to
455 * distinguish different flavors of the algorithm.
456 * Returns: A pointer to string describing the algorithm or NULL if
457 * the ALGO is invalid.
458 * Usage: Bit 0 set : allows signing
459 * 1 set : allows encryption
462 dsa_get_info( int algo, int *npkey, int *nskey, int *nenc, int *nsig,
471 case PUBKEY_ALGO_DSA: *use = PUBKEY_USAGE_SIG; return "DSA";
472 default: *use = 0; return NULL;