~ilya-yanok/ubuntu/precise/grub2/fix-for-948716
» Revision
1.17.14
: grub-core/lib/libgcrypt-grub/cipher/dsa.c
« back to all changes in this revision
Viewing changes to grub-core/lib/libgcrypt-grub/cipher/dsa.c
- browse files at revision 1.17.14
- compare with another revision
- download diff
- download tarball
- view history from revision 1.17.14
- Committer: Bazaar Package Importer
- Author(s): Colin Watson
- Date: 2011-01-17 13:43:06 UTC
- mto: (17.6.26 experimental)
- mto: This revision was merged to the branch mainline in revision 102.
- Revision ID: james.westby@ubuntu.com-20110117134306-fy7qewn4s3qdx2pl
Tags: upstream-1.99~rc1
Import upstream version 1.99~rc1
- files added:
- Makefile.in
- autom4te.cache
- grub-core/lib/libgcrypt-grub
- grub-core/lib/libgcrypt-grub/cipher
- files removed:
- po/LINGUAS
- files modified:
- .bzrignore
added
removed
grub-core/lib/libgcrypt-grub/cipher/dsa.c
1
/* This file was automatically imported with
2
import_gcry.py. Please don't modify it */
3
/* dsa.c - DSA signature algorithm
4
* Copyright (C) 1998, 2000, 2001, 2002, 2003,
5
* 2006, 2008 Free Software Foundation, Inc.
6
*
7
* This file is part of Libgcrypt.
8
*
9
* Libgcrypt is free software; you can redistribute it and/or modify
10
* it under the terms of the GNU Lesser General Public License as
11
* published by the Free Software Foundation; either version 2.1 of
12
* the License, or (at your option) any later version.
13
*
14
* Libgcrypt is distributed in the hope that it will be useful,
15
* but WITHOUT ANY WARRANTY; without even the implied warranty of
16
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17
* GNU Lesser General Public License for more details.
18
*
19
* You should have received a copy of the GNU Lesser General Public
20
* License along with this program; if not, see <http://www.gnu.org/licenses/>.
21
*/
22
23
24
#include "g10lib.h"
25
#include "mpi.h"
26
#include "cipher.h"
27
28
typedef struct
29
{
30
gcry_mpi_t p; /* prime */
31
gcry_mpi_t q; /* group order */
32
gcry_mpi_t g; /* group generator */
33
gcry_mpi_t y; /* g^x mod p */
34
} DSA_public_key;
35
36
37
typedef struct
38
{
39
gcry_mpi_t p; /* prime */
40
gcry_mpi_t q; /* group order */
41
gcry_mpi_t g; /* group generator */
42
gcry_mpi_t y; /* g^x mod p */
43
gcry_mpi_t x; /* secret exponent */
44
} DSA_secret_key;
45
46
47
/* A structure used to hold domain parameters. */
48
typedef struct
49
{
50
gcry_mpi_t p; /* prime */
51
gcry_mpi_t q; /* group order */
52
gcry_mpi_t g; /* group generator */
53
} dsa_domain_t;
54
55
56
/* A sample 1024 bit DSA key used for the selftests. */
57
static const char sample_secret_key[] =
58
"(private-key"
59
" (dsa"
60
" (p #00AD7C0025BA1A15F775F3F2D673718391D00456978D347B33D7B49E7F32EDAB"
61
" 96273899DD8B2BB46CD6ECA263FAF04A28903503D59062A8865D2AE8ADFB5191"
62
" CF36FFB562D0E2F5809801A1F675DAE59698A9E01EFE8D7DCFCA084F4C6F5A44"
63
" 44D499A06FFAEA5E8EF5E01F2FD20A7B7EF3F6968AFBA1FB8D91F1559D52D8777B#)"
64
" (q #00EB7B5751D25EBBB7BD59D920315FD840E19AEBF9#)"
65
" (g #1574363387FDFD1DDF38F4FBE135BB20C7EE4772FB94C337AF86EA8E49666503"
66
" AE04B6BE81A2F8DD095311E0217ACA698A11E6C5D33CCDAE71498ED35D13991E"
67
" B02F09AB40BD8F4C5ED8C75DA779D0AE104BC34C960B002377068AB4B5A1F984"
68
" 3FBA91F537F1B7CAC4D8DD6D89B0D863AF7025D549F9C765D2FC07EE208F8D15#)"
69
" (y #64B11EF8871BE4AB572AA810D5D3CA11A6CDBC637A8014602C72960DB135BF46"
70
" A1816A724C34F87330FC9E187C5D66897A04535CC2AC9164A7150ABFA8179827"
71
" 6E45831AB811EEE848EBB24D9F5F2883B6E5DDC4C659DEF944DCFD80BF4D0A20"
72
" 42CAA7DC289F0C5A9D155F02D3D551DB741A81695B74D4C8F477F9C7838EB0FB#)"
73
" (x #11D54E4ADBD3034160F2CED4B7CD292A4EBF3EC0#)))";
74
/* A sample 1024 bit DSA key used for the selftests (public only). */
75
static const char sample_public_key[] =
76
"(public-key"
77
" (dsa"
78
" (p #00AD7C0025BA1A15F775F3F2D673718391D00456978D347B33D7B49E7F32EDAB"
79
" 96273899DD8B2BB46CD6ECA263FAF04A28903503D59062A8865D2AE8ADFB5191"
80
" CF36FFB562D0E2F5809801A1F675DAE59698A9E01EFE8D7DCFCA084F4C6F5A44"
81
" 44D499A06FFAEA5E8EF5E01F2FD20A7B7EF3F6968AFBA1FB8D91F1559D52D8777B#)"
82
" (q #00EB7B5751D25EBBB7BD59D920315FD840E19AEBF9#)"
83
" (g #1574363387FDFD1DDF38F4FBE135BB20C7EE4772FB94C337AF86EA8E49666503"
84
" AE04B6BE81A2F8DD095311E0217ACA698A11E6C5D33CCDAE71498ED35D13991E"
85
" B02F09AB40BD8F4C5ED8C75DA779D0AE104BC34C960B002377068AB4B5A1F984"
86
" 3FBA91F537F1B7CAC4D8DD6D89B0D863AF7025D549F9C765D2FC07EE208F8D15#)"
87
" (y #64B11EF8871BE4AB572AA810D5D3CA11A6CDBC637A8014602C72960DB135BF46"
88
" A1816A724C34F87330FC9E187C5D66897A04535CC2AC9164A7150ABFA8179827"
89
" 6E45831AB811EEE848EBB24D9F5F2883B6E5DDC4C659DEF944DCFD80BF4D0A20"
90
" 42CAA7DC289F0C5A9D155F02D3D551DB741A81695B74D4C8F477F9C7838EB0FB#)))";
91
92
93
94
95
static gcry_mpi_t gen_k (gcry_mpi_t q);
96
static int test_keys (DSA_secret_key *sk, unsigned int qbits);
97
static int check_secret_key (DSA_secret_key *sk);
98
static gpg_err_code_t generate (DSA_secret_key *sk,
99
unsigned int nbits,
100
unsigned int qbits,
101
int transient_key,
102
dsa_domain_t *domain,
103
gcry_mpi_t **ret_factors);
104
static void sign (gcry_mpi_t r, gcry_mpi_t s, gcry_mpi_t input,
105
DSA_secret_key *skey);
106
static int verify (gcry_mpi_t r, gcry_mpi_t s, gcry_mpi_t input,
107
DSA_public_key *pkey);
108
109
static void (*progress_cb) (void *,const char *, int, int, int );
110
static void *progress_cb_data;
111
112
113
void
114
_gcry_register_pk_dsa_progress (void (*cb) (void *, const char *,
115
int, int, int),
116
void *cb_data)
117
{
118
progress_cb = cb;
119
progress_cb_data = cb_data;
120
}
121
122
123
static void
124
progress (int c)
125
{
126
if (progress_cb)
127
progress_cb (progress_cb_data, "pk_dsa", c, 0, 0);
128
}
129
130
131
/*
132
* Generate a random secret exponent k less than q.
133
*/
134
static gcry_mpi_t
135
gen_k( gcry_mpi_t q )
136
{
137
gcry_mpi_t k = mpi_alloc_secure( mpi_get_nlimbs(q) );
138
unsigned int nbits = mpi_get_nbits(q);
139
unsigned int nbytes = (nbits+7)/8;
140
char *rndbuf = NULL;
141
142
if ( DBG_CIPHER )
143
log_debug("choosing a random k ");
144
for (;;)
145
{
146
if( DBG_CIPHER )
147
progress('.');
148
149
if ( !rndbuf || nbits < 32 )
150
{
151
gcry_free(rndbuf);
152
rndbuf = gcry_random_bytes_secure( (nbits+7)/8, GCRY_STRONG_RANDOM );
153
}
154
else
155
{ /* Change only some of the higher bits. We could improve
156
this by directly requesting more memory at the first call
157
to get_random_bytes() and use this the here maybe it is
158
easier to do this directly in random.c. */
159
char *pp = gcry_random_bytes_secure( 4, GCRY_STRONG_RANDOM );
160
memcpy( rndbuf,pp, 4 );
161
gcry_free(pp);
162
}
163
_gcry_mpi_set_buffer( k, rndbuf, nbytes, 0 );
164
if ( mpi_test_bit( k, nbits-1 ) )
165
mpi_set_highbit( k, nbits-1 );
166
else
167
{
168
mpi_set_highbit( k, nbits-1 );
169
mpi_clear_bit( k, nbits-1 );
170
}
171
172
if( !(mpi_cmp( k, q ) < 0) ) /* check: k < q */
173
{
174
if( DBG_CIPHER )
175
progress('+');
176
continue; /* no */
177
}
178
if( !(mpi_cmp_ui( k, 0 ) > 0) ) /* check: k > 0 */
179
{
180
if( DBG_CIPHER )
181
progress('-');
182
continue; /* no */
183
}
184
break; /* okay */
185
}
186
gcry_free(rndbuf);
187
if( DBG_CIPHER )
188
progress('\n');
189
190
return k;
191
}
192
193
194
/* Check that a freshly generated key actually works. Returns 0 on success. */
195
static int
196
test_keys (DSA_secret_key *sk, unsigned int qbits)
197
{
198
int result = -1; /* Default to failure. */
199
DSA_public_key pk;
200
gcry_mpi_t data = gcry_mpi_new (qbits);
201
gcry_mpi_t sig_a = gcry_mpi_new (qbits);
202
gcry_mpi_t sig_b = gcry_mpi_new (qbits);
203
204
/* Put the relevant parameters into a public key structure. */
205
pk.p = sk->p;
206
pk.q = sk->q;
207
pk.g = sk->g;
208
pk.y = sk->y;
209
210
/* Create a random plaintext. */
211
gcry_mpi_randomize (data, qbits, GCRY_WEAK_RANDOM);
212
213
/* Sign DATA using the secret key. */
214
sign (sig_a, sig_b, data, sk);
215
216
/* Verify the signature using the public key. */
217
if ( !verify (sig_a, sig_b, data, &pk) )
218
goto leave; /* Signature does not match. */
219
220
/* Modify the data and check that the signing fails. */
221
gcry_mpi_add_ui (data, data, 1);
222
if ( verify (sig_a, sig_b, data, &pk) )
223
goto leave; /* Signature matches but should not. */
224
225
result = 0; /* The test succeeded. */
226
227
leave:
228
gcry_mpi_release (sig_b);
229
gcry_mpi_release (sig_a);
230
gcry_mpi_release (data);
231
return result;
232
}
233
234
235
236
/*
237
Generate a DSA key pair with a key of size NBITS. If transient_key
238
is true the key is generated using the standard RNG and not the
239
very secure one.
240
241
Returns: 2 structures filled with all needed values
242
and an array with the n-1 factors of (p-1)
243
*/
244
static gpg_err_code_t
245
generate (DSA_secret_key *sk, unsigned int nbits, unsigned int qbits,
246
int transient_key, dsa_domain_t *domain, gcry_mpi_t **ret_factors )
247
{
248
gcry_mpi_t p; /* the prime */
249
gcry_mpi_t q; /* the 160 bit prime factor */
250
gcry_mpi_t g; /* the generator */
251
gcry_mpi_t y; /* g^x mod p */
252
gcry_mpi_t x; /* the secret exponent */
253
gcry_mpi_t h, e; /* helper */
254
unsigned char *rndbuf;
255
gcry_random_level_t random_level;
256
257
if (qbits)
258
; /* Caller supplied qbits. Use this value. */
259
else if ( nbits >= 512 && nbits <= 1024 )
260
qbits = 160;
261
else if ( nbits == 2048 )
262
qbits = 224;
263
else if ( nbits == 3072 )
264
qbits = 256;
265
else if ( nbits == 7680 )
266
qbits = 384;
267
else if ( nbits == 15360 )
268
qbits = 512;
269
else
270
return GPG_ERR_INV_VALUE;
271
272
if (qbits < 160 || qbits > 512 || (qbits%8) )
273
return GPG_ERR_INV_VALUE;
274
if (nbits < 2*qbits || nbits > 15360)
275
return GPG_ERR_INV_VALUE;
276
277
if (fips_mode ())
278
{
279
if (nbits < 1024)
280
return GPG_ERR_INV_VALUE;
281
if (transient_key)
282
return GPG_ERR_INV_VALUE;
283
}
284
285
if (domain->p && domain->q && domain->g)
286
{
287
/* Domain parameters are given; use them. */
288
p = mpi_copy (domain->p);
289
q = mpi_copy (domain->q);
290
g = mpi_copy (domain->g);
291
gcry_assert (mpi_get_nbits (p) == nbits);
292
gcry_assert (mpi_get_nbits (q) == qbits);
293
h = mpi_alloc (0);
294
e = NULL;
295
}
296
else
297
{
298
/* Generate new domain parameters. */
299
p = _gcry_generate_elg_prime (1, nbits, qbits, NULL, ret_factors);
300
/* Get q out of factors. */
301
q = mpi_copy ((*ret_factors)[0]);
302
gcry_assert (mpi_get_nbits (q) == qbits);
303
304
/* Find a generator g (h and e are helpers).
305
e = (p-1)/q */
306
e = mpi_alloc (mpi_get_nlimbs (p));
307
mpi_sub_ui (e, p, 1);
308
mpi_fdiv_q (e, e, q);
309
g = mpi_alloc (mpi_get_nlimbs (p));
310
h = mpi_alloc_set_ui (1); /* (We start with 2.) */
311
do
312
{
313
mpi_add_ui (h, h, 1);
314
/* g = h^e mod p */
315
gcry_mpi_powm (g, h, e, p);
316
}
317
while (!mpi_cmp_ui (g, 1)); /* Continue until g != 1. */
318
}
319
320
/* Select a random number X with the property:
321
* 0 < x < q-1
322
* This must be a very good random number because this is the secret
323
* part. The random quality depends on the transient_key flag. */
324
random_level = transient_key ? GCRY_STRONG_RANDOM : GCRY_VERY_STRONG_RANDOM;
325
if (DBG_CIPHER)
326
log_debug("choosing a random x%s", transient_key? " (transient-key)":"");
327
gcry_assert( qbits >= 160 );
328
x = mpi_alloc_secure( mpi_get_nlimbs(q) );
329
mpi_sub_ui( h, q, 1 ); /* put q-1 into h */
330
rndbuf = NULL;
331
do
332
{
333
if( DBG_CIPHER )
334
progress('.');
335
if( !rndbuf )
336
rndbuf = gcry_random_bytes_secure ((qbits+7)/8, random_level);
337
else
338
{ /* Change only some of the higher bits (= 2 bytes)*/
339
char *r = gcry_random_bytes_secure (2, random_level);
340
memcpy(rndbuf, r, 2 );
341
gcry_free(r);
342
}
343
344
_gcry_mpi_set_buffer( x, rndbuf, (qbits+7)/8, 0 );
345
mpi_clear_highbit( x, qbits+1 );
346
}
347
while ( !( mpi_cmp_ui( x, 0 )>0 && mpi_cmp( x, h )<0 ) );
348
gcry_free(rndbuf);
349
mpi_free( e );
350
mpi_free( h );
351
352
/* y = g^x mod p */
353
y = mpi_alloc( mpi_get_nlimbs(p) );
354
gcry_mpi_powm( y, g, x, p );
355
356
if( DBG_CIPHER )
357
{
358
progress('\n');
359
log_mpidump("dsa p", p );
360
log_mpidump("dsa q", q );
361
log_mpidump("dsa g", g );
362
log_mpidump("dsa y", y );
363
log_mpidump("dsa x", x );
364
}
365
366
/* Copy the stuff to the key structures. */
367
sk->p = p;
368
sk->q = q;
369
sk->g = g;
370
sk->y = y;
371
sk->x = x;
372
373
/* Now we can test our keys (this should never fail!). */
374
if ( test_keys (sk, qbits) )
375
{
376
gcry_mpi_release (sk->p); sk->p = NULL;
377
gcry_mpi_release (sk->q); sk->q = NULL;
378
gcry_mpi_release (sk->g); sk->g = NULL;
379
gcry_mpi_release (sk->y); sk->y = NULL;
380
gcry_mpi_release (sk->x); sk->x = NULL;
381
fips_signal_error ("self-test after key generation failed");
382
return GPG_ERR_SELFTEST_FAILED;
383
}
384
return 0;
385
}
386
387
388
/* Generate a DSA key pair with a key of size NBITS using the
389
algorithm given in FIPS-186-3. If USE_FIPS186_2 is true,
390
FIPS-186-2 is used and thus the length is restricted to 1024/160.
391
If DERIVEPARMS is not NULL it may contain a seed value. If domain
392
parameters are specified in DOMAIN, DERIVEPARMS may not be given
393
and NBITS and QBITS must match the specified domain parameters. */
394
static gpg_err_code_t
395
generate_fips186 (DSA_secret_key *sk, unsigned int nbits, unsigned int qbits,
396
gcry_sexp_t deriveparms, int use_fips186_2,
397
dsa_domain_t *domain,
398
int *r_counter, void **r_seed, size_t *r_seedlen,
399
gcry_mpi_t *r_h)
400
{
401
gpg_err_code_t ec;
402
struct {
403
gcry_sexp_t sexp;
404
const void *seed;
405
size_t seedlen;
406
} initial_seed = { NULL, NULL, 0 };
407
gcry_mpi_t prime_q = NULL;
408
gcry_mpi_t prime_p = NULL;
409
gcry_mpi_t value_g = NULL; /* The generator. */
410
gcry_mpi_t value_y = NULL; /* g^x mod p */
411
gcry_mpi_t value_x = NULL; /* The secret exponent. */
412
gcry_mpi_t value_h = NULL; /* Helper. */
413
gcry_mpi_t value_e = NULL; /* Helper. */
414
415
/* Preset return values. */
416
*r_counter = 0;
417
*r_seed = NULL;
418
*r_seedlen = 0;
419
*r_h = NULL;
420
421
/* Derive QBITS from NBITS if requested */
422
if (!qbits)
423
{
424
if (nbits == 1024)
425
qbits = 160;
426
else if (nbits == 2048)
427
qbits = 224;
428
else if (nbits == 3072)
429
qbits = 256;
430
}
431
432
/* Check that QBITS and NBITS match the standard. Note that FIPS
433
186-3 uses N for QBITS and L for NBITS. */
434
if (nbits == 1024 && qbits == 160)
435
;
436
else if (nbits == 2048 && qbits == 224)
437
;
438
else if (nbits == 2048 && qbits == 256)
439
;
440
else if (nbits == 3072 && qbits == 256)
441
;
442
else
443
return GPG_ERR_INV_VALUE;
444
445
if (domain->p && domain->q && domain->g)
446
{
447
/* Domain parameters are given; use them. */
448
prime_p = mpi_copy (domain->p);
449
prime_q = mpi_copy (domain->q);
450
value_g = mpi_copy (domain->g);
451
gcry_assert (mpi_get_nbits (prime_p) == nbits);
452
gcry_assert (mpi_get_nbits (prime_q) == qbits);
453
gcry_assert (!deriveparms);
454
ec = 0;
455
}
456
else
457
{
458
/* Generate new domain parameters. */
459
460
/* Get an initial seed value. */
461
if (deriveparms)
462
{
463
initial_seed.sexp = gcry_sexp_find_token (deriveparms, "seed", 0);
464
if (initial_seed.sexp)
465
initial_seed.seed = gcry_sexp_nth_data (initial_seed.sexp, 1,
466
&initial_seed.seedlen);
467
}
468
469
/* Fixme: Enable 186-3 after it has been approved and after fixing
470
the generation function. */
471
/* if (use_fips186_2) */
472
(void)use_fips186_2;
473
ec = _gcry_generate_fips186_2_prime (nbits, qbits,
474
initial_seed.seed,
475
initial_seed.seedlen,
476
&prime_q, &prime_p,
477
r_counter,
478
r_seed, r_seedlen);
479
/* else */
480
/* ec = _gcry_generate_fips186_3_prime (nbits, qbits, NULL, 0, */
481
/* &prime_q, &prime_p, */
482
/* r_counter, */
483
/* r_seed, r_seedlen, NULL); */
484
gcry_sexp_release (initial_seed.sexp);
485
if (ec)
486
goto leave;
487
488
/* Find a generator g (h and e are helpers).
489
e = (p-1)/q */
490
value_e = mpi_alloc_like (prime_p);
491
mpi_sub_ui (value_e, prime_p, 1);
492
mpi_fdiv_q (value_e, value_e, prime_q );
493
value_g = mpi_alloc_like (prime_p);
494
value_h = mpi_alloc_set_ui (1);
495
do
496
{
497
mpi_add_ui (value_h, value_h, 1);
498
/* g = h^e mod p */
499
mpi_powm (value_g, value_h, value_e, prime_p);
500
}
501
while (!mpi_cmp_ui (value_g, 1)); /* Continue until g != 1. */
502
}
503
504
505
/* Select a random number x with: 0 < x < q */
506
value_x = gcry_mpi_snew (qbits);
507
do
508
{
509
if( DBG_CIPHER )
510
progress('.');
511
gcry_mpi_randomize (value_x, qbits, GCRY_VERY_STRONG_RANDOM);
512
mpi_clear_highbit (value_x, qbits+1);
513
}
514
while (!(mpi_cmp_ui (value_x, 0) > 0 && mpi_cmp (value_x, prime_q) < 0));
515
516
/* y = g^x mod p */
517
value_y = mpi_alloc_like (prime_p);
518
gcry_mpi_powm (value_y, value_g, value_x, prime_p);
519
520
if (DBG_CIPHER)
521
{
522
progress('\n');
523
log_mpidump("dsa p", prime_p );
524
log_mpidump("dsa q", prime_q );
525
log_mpidump("dsa g", value_g );
526
log_mpidump("dsa y", value_y );
527
log_mpidump("dsa x", value_x );
528
log_mpidump("dsa h", value_h );
529
}
530
531
/* Copy the stuff to the key structures. */
532
sk->p = prime_p; prime_p = NULL;
533
sk->q = prime_q; prime_q = NULL;
534
sk->g = value_g; value_g = NULL;
535
sk->y = value_y; value_y = NULL;
536
sk->x = value_x; value_x = NULL;
537
*r_h = value_h; value_h = NULL;
538
539
leave:
540
gcry_mpi_release (prime_p);
541
gcry_mpi_release (prime_q);
542
gcry_mpi_release (value_g);
543
gcry_mpi_release (value_y);
544
gcry_mpi_release (value_x);
545
gcry_mpi_release (value_h);
546
gcry_mpi_release (value_e);
547
548
/* As a last step test this keys (this should never fail of course). */
549
if (!ec && test_keys (sk, qbits) )
550
{
551
gcry_mpi_release (sk->p); sk->p = NULL;
552
gcry_mpi_release (sk->q); sk->q = NULL;
553
gcry_mpi_release (sk->g); sk->g = NULL;
554
gcry_mpi_release (sk->y); sk->y = NULL;
555
gcry_mpi_release (sk->x); sk->x = NULL;
556
fips_signal_error ("self-test after key generation failed");
557
ec = GPG_ERR_SELFTEST_FAILED;
558
}
559
560
if (ec)
561
{
562
*r_counter = 0;
563
gcry_free (*r_seed); *r_seed = NULL;
564
*r_seedlen = 0;
565
gcry_mpi_release (*r_h); *r_h = NULL;
566
}
567
568
return ec;
569
}
570
571
572
573
/*
574
Test whether the secret key is valid.
575
Returns: if this is a valid key.
576
*/
577
static int
578
check_secret_key( DSA_secret_key *sk )
579
{
580
int rc;
581
gcry_mpi_t y = mpi_alloc( mpi_get_nlimbs(sk->y) );
582
583
gcry_mpi_powm( y, sk->g, sk->x, sk->p );
584
rc = !mpi_cmp( y, sk->y );
585
mpi_free( y );
586
return rc;
587
}
588
589
590
591
/*
592
Make a DSA signature from HASH and put it into r and s.
593
*/
594
static void
595
sign(gcry_mpi_t r, gcry_mpi_t s, gcry_mpi_t hash, DSA_secret_key *skey )
596
{
597
gcry_mpi_t k;
598
gcry_mpi_t kinv;
599
gcry_mpi_t tmp;
600
601
/* Select a random k with 0 < k < q */
602
k = gen_k( skey->q );
603
604
/* r = (a^k mod p) mod q */
605
gcry_mpi_powm( r, skey->g, k, skey->p );
606
mpi_fdiv_r( r, r, skey->q );
607
608
/* kinv = k^(-1) mod q */
609
kinv = mpi_alloc( mpi_get_nlimbs(k) );
610
mpi_invm(kinv, k, skey->q );
611
612
/* s = (kinv * ( hash + x * r)) mod q */
613
tmp = mpi_alloc( mpi_get_nlimbs(skey->p) );
614
mpi_mul( tmp, skey->x, r );
615
mpi_add( tmp, tmp, hash );
616
mpi_mulm( s , kinv, tmp, skey->q );
617
618
mpi_free(k);
619
mpi_free(kinv);
620
mpi_free(tmp);
621
}
622
623
624
/*
625
Returns true if the signature composed from R and S is valid.
626
*/
627
static int
628
verify (gcry_mpi_t r, gcry_mpi_t s, gcry_mpi_t hash, DSA_public_key *pkey )
629
{
630
int rc;
631
gcry_mpi_t w, u1, u2, v;
632
gcry_mpi_t base[3];
633
gcry_mpi_t ex[3];
634
635
if( !(mpi_cmp_ui( r, 0 ) > 0 && mpi_cmp( r, pkey->q ) < 0) )
636
return 0; /* assertion 0 < r < q failed */
637
if( !(mpi_cmp_ui( s, 0 ) > 0 && mpi_cmp( s, pkey->q ) < 0) )
638
return 0; /* assertion 0 < s < q failed */
639
640
w = mpi_alloc( mpi_get_nlimbs(pkey->q) );
641
u1 = mpi_alloc( mpi_get_nlimbs(pkey->q) );
642
u2 = mpi_alloc( mpi_get_nlimbs(pkey->q) );
643
v = mpi_alloc( mpi_get_nlimbs(pkey->p) );
644
645
/* w = s^(-1) mod q */
646
mpi_invm( w, s, pkey->q );
647
648
/* u1 = (hash * w) mod q */
649
mpi_mulm( u1, hash, w, pkey->q );
650
651
/* u2 = r * w mod q */
652
mpi_mulm( u2, r, w, pkey->q );
653
654
/* v = g^u1 * y^u2 mod p mod q */
655
base[0] = pkey->g; ex[0] = u1;
656
base[1] = pkey->y; ex[1] = u2;
657
base[2] = NULL; ex[2] = NULL;
658
mpi_mulpowm( v, base, ex, pkey->p );
659
mpi_fdiv_r( v, v, pkey->q );
660
661
rc = !mpi_cmp( v, r );
662
663
mpi_free(w);
664
mpi_free(u1);
665
mpi_free(u2);
666
mpi_free(v);
667
668
return rc;
669
}
670
671
672
/*********************************************
673
************** interface ******************
674
*********************************************/
675
676
static gcry_err_code_t
677
dsa_generate_ext (int algo, unsigned int nbits, unsigned long evalue,
678
const gcry_sexp_t genparms,
679
gcry_mpi_t *skey, gcry_mpi_t **retfactors,
680
gcry_sexp_t *r_extrainfo)
681
{
682
gpg_err_code_t ec;
683
DSA_secret_key sk;
684
gcry_sexp_t l1;
685
unsigned int qbits = 0;
686
gcry_sexp_t deriveparms = NULL;
687
gcry_sexp_t seedinfo = NULL;
688
int transient_key = 0;
689
int use_fips186_2 = 0;
690
int use_fips186 = 0;
691
dsa_domain_t domain;
692
693
(void)algo; /* No need to check it. */
694
(void)evalue; /* Not required for DSA. */
695
696
memset (&domain, 0, sizeof domain);
697
698
if (genparms)
699
{
700
gcry_sexp_t domainsexp;
701
702
/* Parse the optional qbits element. */
703
l1 = gcry_sexp_find_token (genparms, "qbits", 0);
704
if (l1)
705
{
706
char buf[50];
707
const char *s;
708
size_t n;
709
710
s = gcry_sexp_nth_data (l1, 1, &n);
711
if (!s || n >= DIM (buf) - 1 )
712
{
713
gcry_sexp_release (l1);
714
return GPG_ERR_INV_OBJ; /* No value or value too large. */
715
}
716
memcpy (buf, s, n);
717
buf[n] = 0;
718
qbits = (unsigned int)strtoul (buf, NULL, 0);
719
gcry_sexp_release (l1);
720
}
721
722
/* Parse the optional transient-key flag. */
723
l1 = gcry_sexp_find_token (genparms, "transient-key", 0);
724
if (l1)
725
{
726
transient_key = 1;
727
gcry_sexp_release (l1);
728
}
729
730
/* Get the optional derive parameters. */
731
deriveparms = gcry_sexp_find_token (genparms, "derive-parms", 0);
732
733
/* Parse the optional "use-fips186" flags. */
734
l1 = gcry_sexp_find_token (genparms, "use-fips186", 0);
735
if (l1)
736
{
737
use_fips186 = 1;
738
gcry_sexp_release (l1);
739
}
740
l1 = gcry_sexp_find_token (genparms, "use-fips186-2", 0);
741
if (l1)
742
{
743
use_fips186_2 = 1;
744
gcry_sexp_release (l1);
745
}
746
747
/* Check whether domain parameters are given. */
748
domainsexp = gcry_sexp_find_token (genparms, "domain", 0);
749
if (domainsexp)
750
{
751
/* DERIVEPARMS can't be used together with domain
752
parameters. NBITS abnd QBITS may not be specified
753
because there values are derived from the domain
754
parameters. */
755
if (deriveparms || qbits || nbits)
756
{
757
gcry_sexp_release (domainsexp);
758
gcry_sexp_release (deriveparms);
759
return GPG_ERR_INV_VALUE;
760
}
761
762
/* Put all domain parameters into the domain object. */
763
l1 = gcry_sexp_find_token (domainsexp, "p", 0);
764
domain.p = gcry_sexp_nth_mpi (l1, 1, GCRYMPI_FMT_USG);
765
gcry_sexp_release (l1);
766
l1 = gcry_sexp_find_token (domainsexp, "q", 0);
767
domain.q = gcry_sexp_nth_mpi (l1, 1, GCRYMPI_FMT_USG);
768
gcry_sexp_release (l1);
769
l1 = gcry_sexp_find_token (domainsexp, "g", 0);
770
domain.g = gcry_sexp_nth_mpi (l1, 1, GCRYMPI_FMT_USG);
771
gcry_sexp_release (l1);
772
gcry_sexp_release (domainsexp);
773
774
/* Check that all domain parameters are available. */
775
if (!domain.p || !domain.q || !domain.g)
776
{
777
gcry_mpi_release (domain.p);
778
gcry_mpi_release (domain.q);
779
gcry_mpi_release (domain.g);
780
gcry_sexp_release (deriveparms);
781
return GPG_ERR_MISSING_VALUE;
782
}
783
784
/* Get NBITS and QBITS from the domain parameters. */
785
nbits = mpi_get_nbits (domain.p);
786
qbits = mpi_get_nbits (domain.q);
787
}
788
}
789
790
if (deriveparms || use_fips186 || use_fips186_2 || fips_mode ())
791
{
792
int counter;
793
void *seed;
794
size_t seedlen;
795
gcry_mpi_t h_value;
796
797
ec = generate_fips186 (&sk, nbits, qbits, deriveparms, use_fips186_2,
798
&domain,
799
&counter, &seed, &seedlen, &h_value);
800
gcry_sexp_release (deriveparms);
801
if (!ec && h_value)
802
{
803
/* Format the seed-values unless domain parameters are used
804
for which a H_VALUE of NULL is an indication. */
805
ec = gpg_err_code (gcry_sexp_build
806
(&seedinfo, NULL,
807
"(seed-values(counter %d)(seed %b)(h %m))",
808
counter, (int)seedlen, seed, h_value));
809
if (ec)
810
{
811
gcry_mpi_release (sk.p); sk.p = NULL;
812
gcry_mpi_release (sk.q); sk.q = NULL;
813
gcry_mpi_release (sk.g); sk.g = NULL;
814
gcry_mpi_release (sk.y); sk.y = NULL;
815
gcry_mpi_release (sk.x); sk.x = NULL;
816
}
817
gcry_free (seed);
818
gcry_mpi_release (h_value);
819
}
820
}
821
else
822
{
823
ec = generate (&sk, nbits, qbits, transient_key, &domain, retfactors);
824
}
825
826
gcry_mpi_release (domain.p);
827
gcry_mpi_release (domain.q);
828
gcry_mpi_release (domain.g);
829
830
if (!ec)
831
{
832
skey[0] = sk.p;
833
skey[1] = sk.q;
834
skey[2] = sk.g;
835
skey[3] = sk.y;
836
skey[4] = sk.x;
837
838
if (!r_extrainfo)
839
{
840
/* Old style interface - return the factors - if any - at
841
retfactors. */
842
}
843
else if (!*retfactors && !seedinfo)
844
{
845
/* No factors and no seedinfo, thus there is nothing to return. */
846
*r_extrainfo = NULL;
847
}
848
else
849
{
850
/* Put the factors into extrainfo and set retfactors to NULL
851
to make use of the new interface. Note that the factors
852
are not confidential thus we can store them in standard
853
memory. */
854
int nfactors, i, j;
855
char *p;
856
char *format = NULL;
857
void **arg_list = NULL;
858
859
for (nfactors=0; *retfactors && (*retfactors)[nfactors]; nfactors++)
860
;
861
/* Allocate space for the format string:
862
"(misc-key-info%S(pm1-factors%m))"
863
with one "%m" for each factor and construct it. */
864
format = gcry_malloc (50 + 2*nfactors);
865
if (!format)
866
ec = gpg_err_code_from_syserror ();
867
else
868
{
869
p = stpcpy (format, "(misc-key-info");
870
if (seedinfo)
871
p = stpcpy (p, "%S");
872
if (nfactors)
873
{
874
p = stpcpy (p, "(pm1-factors");
875
for (i=0; i < nfactors; i++)
876
p = stpcpy (p, "%m");
877
p = stpcpy (p, ")");
878
}
879
p = stpcpy (p, ")");
880
881
/* Allocate space for the list of factors plus one for
882
an S-expression plus an extra NULL entry for safety
883
and fill it with the factors. */
884
arg_list = gcry_calloc (nfactors+1+1, sizeof *arg_list);
885
if (!arg_list)
886
ec = gpg_err_code_from_syserror ();
887
else
888
{
889
i = 0;
890
if (seedinfo)
891
arg_list[i++] = &seedinfo;
892
for (j=0; j < nfactors; j++)
893
arg_list[i++] = (*retfactors) + j;
894
arg_list[i] = NULL;
895
896
ec = gpg_err_code (gcry_sexp_build_array
897
(r_extrainfo, NULL, format, arg_list));
898
}
899
}
900
901
gcry_free (arg_list);
902
gcry_free (format);
903
for (i=0; i < nfactors; i++)
904
{
905
gcry_mpi_release ((*retfactors)[i]);
906
(*retfactors)[i] = NULL;
907
}
908
*retfactors = NULL;
909
if (ec)
910
{
911
for (i=0; i < 5; i++)
912
{
913
gcry_mpi_release (skey[i]);
914
skey[i] = NULL;
915
}
916
}
917
}
918
}
919
920
gcry_sexp_release (seedinfo);
921
return ec;
922
}
923
924
925
static gcry_err_code_t
926
dsa_generate (int algo, unsigned int nbits, unsigned long evalue,
927
gcry_mpi_t *skey, gcry_mpi_t **retfactors)
928
{
929
(void)evalue;
930
return dsa_generate_ext (algo, nbits, 0, NULL, skey, retfactors, NULL);
931
}
932
933
934
935
static gcry_err_code_t
936
dsa_check_secret_key (int algo, gcry_mpi_t *skey)
937
{
938
gcry_err_code_t err = GPG_ERR_NO_ERROR;
939
DSA_secret_key sk;
940
941
(void)algo;
942
943
if ((! skey[0]) || (! skey[1]) || (! skey[2]) || (! skey[3]) || (! skey[4]))
944
err = GPG_ERR_BAD_MPI;
945
else
946
{
947
sk.p = skey[0];
948
sk.q = skey[1];
949
sk.g = skey[2];
950
sk.y = skey[3];
951
sk.x = skey[4];
952
if (! check_secret_key (&sk))
953
err = GPG_ERR_BAD_SECKEY;
954
}
955
956
return err;
957
}
958
959
960
static gcry_err_code_t
961
dsa_sign (int algo, gcry_mpi_t *resarr, gcry_mpi_t data, gcry_mpi_t *skey)
962
{
963
gcry_err_code_t err = GPG_ERR_NO_ERROR;
964
DSA_secret_key sk;
965
966
(void)algo;
967
968
if ((! data)
969
|| (! skey[0]) || (! skey[1]) || (! skey[2])
970
|| (! skey[3]) || (! skey[4]))
971
err = GPG_ERR_BAD_MPI;
972
else
973
{
974
sk.p = skey[0];
975
sk.q = skey[1];
976
sk.g = skey[2];
977
sk.y = skey[3];
978
sk.x = skey[4];
979
resarr[0] = mpi_alloc (mpi_get_nlimbs (sk.p));
980
resarr[1] = mpi_alloc (mpi_get_nlimbs (sk.p));
981
sign (resarr[0], resarr[1], data, &sk);
982
}
983
return err;
984
}
985
986
static gcry_err_code_t
987
dsa_verify (int algo, gcry_mpi_t hash, gcry_mpi_t *data, gcry_mpi_t *pkey,
988
int (*cmp) (void *, gcry_mpi_t), void *opaquev)
989
{
990
gcry_err_code_t err = GPG_ERR_NO_ERROR;
991
DSA_public_key pk;
992
993
(void)algo;
994
(void)cmp;
995
(void)opaquev;
996
997
if ((! data[0]) || (! data[1]) || (! hash)
998
|| (! pkey[0]) || (! pkey[1]) || (! pkey[2]) || (! pkey[3]))
999
err = GPG_ERR_BAD_MPI;
1000
else
1001
{
1002
pk.p = pkey[0];
1003
pk.q = pkey[1];
1004
pk.g = pkey[2];
1005
pk.y = pkey[3];
1006
if (! verify (data[0], data[1], hash, &pk))
1007
err = GPG_ERR_BAD_SIGNATURE;
1008
}
1009
return err;
1010
}
1011
1012
1013
static unsigned int
1014
dsa_get_nbits (int algo, gcry_mpi_t *pkey)
1015
{
1016
(void)algo;
1017
1018
return mpi_get_nbits (pkey[0]);
1019
}
1020
1021
1022
1023
/*
1024
Self-test section.
1025
*/
1026
1027
1028
1029
1030
1031
/* Run a full self-test for ALGO and return 0 on success. */
1032
1033
1034
1035
1036
static const char *dsa_names[] =
1037
{
1038
"dsa",
1039
"openpgp-dsa",
1040
NULL,
1041
};
1042
1043
gcry_pk_spec_t _gcry_pubkey_spec_dsa =
1044
{
1045
"DSA", dsa_names,
1046
"pqgy", "pqgyx", "", "rs", "pqgy",
1047
GCRY_PK_USAGE_SIGN,
1048
dsa_generate,
1049
dsa_check_secret_key,
1050
NULL,
1051
NULL,
1052
dsa_sign,
1053
dsa_verify,
1054
dsa_get_nbits
1055
};
1056
pk_extra_spec_t _gcry_pubkey_extraspec_dsa =
1057
{
1058
run_selftests,
1059
dsa_generate_ext
1060
};
1061
Loggerhead is a web-based interface for Breezy
Version: 2.0.1