1
/* dsa.c - DSA signature algorithm
2
* Copyright (C) 1998, 1999, 2000 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
33
MPI q; /* group order */
34
MPI g; /* group generator */
35
MPI y; /* g^x mod p */
41
MPI q; /* group order */
42
MPI g; /* group generator */
43
MPI y; /* g^x mod p */
44
MPI x; /* secret exponent */
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);
56
static void (*progress_cb) ( void *, int );
57
static void *progress_cb_data;
60
register_pk_dsa_progress ( void (*cb)( void *, int), void *cb_data )
63
progress_cb_data = cb_data;
71
progress_cb ( progress_cb_data, c );
79
* Generate a random secret exponent k less than q
84
MPI k = mpi_alloc_secure( mpi_get_nlimbs(q) );
85
unsigned int nbits = mpi_get_nbits(q);
86
unsigned int nbytes = (nbits+7)/8;
90
log_debug("choosing a random k ");
95
if( !rndbuf || nbits < 32 ) {
97
rndbuf = get_random_bits( nbits, 1, 1 );
99
else { /* change only some of the higher bits */
100
/* we could imporove this by directly requesting more memory
101
* at the first call to get_random_bits() and use this the here
102
* maybe it is easier to do this directly in random.c */
103
char *pp = get_random_bits( 32, 1, 1 );
104
memcpy( rndbuf,pp, 4 );
107
mpi_set_buffer( k, rndbuf, nbytes, 0 );
108
if( mpi_test_bit( k, nbits-1 ) )
109
mpi_set_highbit( k, nbits-1 );
111
mpi_set_highbit( k, nbits-1 );
112
mpi_clear_bit( k, nbits-1 );
115
if( !(mpi_cmp( k, q ) < 0) ) { /* check: k < q */
120
if( !(mpi_cmp_ui( k, 0 ) > 0) ) { /* check: k > 0 */
136
test_keys( DSA_secret_key *sk, unsigned qbits )
139
MPI test = mpi_alloc( qbits / BITS_PER_MPI_LIMB );
140
MPI out1_a = mpi_alloc( qbits / BITS_PER_MPI_LIMB );
141
MPI out1_b = mpi_alloc( qbits / BITS_PER_MPI_LIMB );
147
/*mpi_set_bytes( test, qbits, get_random_byte, 0 );*/
148
{ char *p = get_random_bits( qbits, 0, 0 );
149
mpi_set_buffer( test, p, (qbits+7)/8, 0 );
153
sign( out1_a, out1_b, test, sk );
154
if( !verify( out1_a, out1_b, test, &pk ) )
155
log_fatal("DSA:: sign, verify failed\n");
165
* Generate a DSA key pair with a key of size NBITS
166
* Returns: 2 structures filled with all needed values
167
* and an array with the n-1 factors of (p-1)
170
generate( DSA_secret_key *sk, unsigned nbits, MPI **ret_factors )
172
MPI p; /* the prime */
173
MPI q; /* the 160 bit prime factor */
174
MPI g; /* the generator */
175
MPI y; /* g^x mod p */
176
MPI x; /* the secret exponent */
177
MPI h, e; /* helper */
181
assert( nbits >= 512 && nbits <= 1024 );
184
p = generate_elg_prime( 1, nbits, qbits, NULL, ret_factors );
185
/* get q out of factors */
186
q = mpi_copy((*ret_factors)[0]);
187
if( mpi_get_nbits(q) != qbits )
190
/* find a generator g (h and e are helpers)*/
192
e = mpi_alloc( mpi_get_nlimbs(p) );
193
mpi_sub_ui( e, p, 1 );
194
mpi_fdiv_q( e, e, q );
195
g = mpi_alloc( mpi_get_nlimbs(p) );
196
h = mpi_alloc_set_ui( 1 ); /* we start with 2 */
198
mpi_add_ui( h, h, 1 );
200
mpi_powm( g, h, e, p );
201
} while( !mpi_cmp_ui( g, 1 ) ); /* continue until g != 1 */
203
/* select a random number which has these properties:
205
* This must be a very good random number because this
206
* is the secret part. */
208
log_debug("choosing a random x ");
209
assert( qbits >= 160 );
210
x = mpi_alloc_secure( mpi_get_nlimbs(q) );
211
mpi_sub_ui( h, q, 1 ); /* put q-1 into h */
217
rndbuf = get_random_bits( qbits, 2, 1 );
218
else { /* change only some of the higher bits (= 2 bytes)*/
219
char *r = get_random_bits( 16, 2, 1 );
220
memcpy(rndbuf, r, 16/8 );
223
mpi_set_buffer( x, rndbuf, (qbits+7)/8, 0 );
224
mpi_clear_highbit( x, qbits+1 );
225
} while( !( mpi_cmp_ui( x, 0 )>0 && mpi_cmp( x, h )<0 ) );
231
y = mpi_alloc( mpi_get_nlimbs(p) );
232
mpi_powm( y, g, x, p );
236
log_mpidump("dsa p= ", p );
237
log_mpidump("dsa q= ", q );
238
log_mpidump("dsa g= ", g );
239
log_mpidump("dsa y= ", y );
240
log_mpidump("dsa x= ", x );
243
/* copy the stuff to the key structures */
250
/* now we can test our keys (this should never fail!) */
251
test_keys( sk, qbits );
257
* Test whether the secret key is valid.
258
* Returns: if this is a valid key.
261
check_secret_key( DSA_secret_key *sk )
264
MPI y = mpi_alloc( mpi_get_nlimbs(sk->y) );
266
mpi_powm( y, sk->g, sk->x, sk->p );
267
rc = !mpi_cmp( y, sk->y );
275
* Make a DSA signature from HASH and put it into r and s.
277
* Without generating the k this function runs in
278
* about 26ms on a 300 Mhz Mobile Pentium
282
sign(MPI r, MPI s, MPI hash, DSA_secret_key *skey )
288
/* select a random k with 0 < k < q */
289
k = gen_k( skey->q );
291
/* r = (a^k mod p) mod q */
292
mpi_powm( r, skey->g, k, skey->p );
293
mpi_fdiv_r( r, r, skey->q );
295
/* kinv = k^(-1) mod q */
296
kinv = mpi_alloc( mpi_get_nlimbs(k) );
297
mpi_invm(kinv, k, skey->q );
299
/* s = (kinv * ( hash + x * r)) mod q */
300
tmp = mpi_alloc( mpi_get_nlimbs(skey->p) );
301
mpi_mul( tmp, skey->x, r );
302
mpi_add( tmp, tmp, hash );
303
mpi_mulm( s , kinv, tmp, skey->q );
312
* Returns true if the signature composed from R and S is valid.
314
* Without the checks this function runs in
315
* about 31ms on a 300 Mhz Mobile Pentium
318
verify(MPI r, MPI s, MPI hash, DSA_public_key *pkey )
326
if( !(mpi_cmp_ui( r, 0 ) > 0 && mpi_cmp( r, pkey->q ) < 0) )
327
return 0; /* assertion 0 < r < q failed */
328
if( !(mpi_cmp_ui( s, 0 ) > 0 && mpi_cmp( s, pkey->q ) < 0) )
329
return 0; /* assertion 0 < s < q failed */
331
w = mpi_alloc( mpi_get_nlimbs(pkey->q) );
332
u1 = mpi_alloc( mpi_get_nlimbs(pkey->q) );
333
u2 = mpi_alloc( mpi_get_nlimbs(pkey->q) );
334
v = mpi_alloc( mpi_get_nlimbs(pkey->p) );
336
/* w = s^(-1) mod q */
337
mpi_invm( w, s, pkey->q );
339
/* u1 = (hash * w) mod q */
340
mpi_mulm( u1, hash, w, pkey->q );
342
/* u2 = r * w mod q */
343
mpi_mulm( u2, r, w, pkey->q );
345
/* v = g^u1 * y^u2 mod p mod q */
346
base[0] = pkey->g; exp[0] = u1;
347
base[1] = pkey->y; exp[1] = u2;
348
base[2] = NULL; exp[2] = NULL;
349
mpi_mulpowm( v, base, exp, pkey->p );
350
mpi_fdiv_r( v, v, pkey->q );
352
rc = !mpi_cmp( v, r );
362
/*********************************************
363
************** interface ******************
364
*********************************************/
367
dsa_generate( int algo, unsigned nbits, MPI *skey, MPI **retfactors )
371
if( algo != PUBKEY_ALGO_DSA )
372
return G10ERR_PUBKEY_ALGO;
374
generate( &sk, nbits, retfactors );
385
dsa_check_secret_key( int algo, MPI *skey )
389
if( algo != PUBKEY_ALGO_DSA )
390
return G10ERR_PUBKEY_ALGO;
391
if( !skey[0] || !skey[1] || !skey[2] || !skey[3] || !skey[4] )
392
return G10ERR_BAD_MPI;
399
if( !check_secret_key( &sk ) )
400
return G10ERR_BAD_SECKEY;
408
dsa_sign( int algo, MPI *resarr, MPI data, MPI *skey )
412
if( algo != PUBKEY_ALGO_DSA )
413
return G10ERR_PUBKEY_ALGO;
414
if( !data || !skey[0] || !skey[1] || !skey[2] || !skey[3] || !skey[4] )
415
return G10ERR_BAD_MPI;
422
resarr[0] = mpi_alloc( mpi_get_nlimbs( sk.p ) );
423
resarr[1] = mpi_alloc( mpi_get_nlimbs( sk.p ) );
424
sign( resarr[0], resarr[1], data, &sk );
429
dsa_verify( int algo, MPI hash, MPI *data, MPI *pkey,
430
int (*cmp)(void *, MPI), void *opaquev )
434
if( algo != PUBKEY_ALGO_DSA )
435
return G10ERR_PUBKEY_ALGO;
436
if( !data[0] || !data[1] || !hash
437
|| !pkey[0] || !pkey[1] || !pkey[2] || !pkey[3] )
438
return G10ERR_BAD_MPI;
444
if( !verify( data[0], data[1], hash, &pk ) )
445
return G10ERR_BAD_SIGN;
452
dsa_get_nbits( int algo, MPI *pkey )
454
if( algo != PUBKEY_ALGO_DSA )
456
return mpi_get_nbits( pkey[0] );
461
* Return some information about the algorithm. We need algo here to
462
* distinguish different flavors of the algorithm.
463
* Returns: A pointer to string describing the algorithm or NULL if
464
* the ALGO is invalid.
465
* Usage: Bit 0 set : allows signing
466
* 1 set : allows encryption
469
dsa_get_info( int algo, int *npkey, int *nskey, int *nenc, int *nsig,
478
case PUBKEY_ALGO_DSA: *use = PUBKEY_USAGE_SIG; return "DSA";
479
default: *use = 0; return NULL;
added
removed
cipher/dsa.c
