1 /* dsa.c - DSA signature algorithm
2 * Copyright (C) 1998, 2000, 2001, 2002, 2003,
3 * 2006, 2008 Free Software Foundation, Inc.
4 * Copyright (C) 2013 g10 Code GmbH.
5 *
6 * This file is part of Libgcrypt.
7 *
8 * Libgcrypt is free software; you can redistribute it and/or modify
9 * it under the terms of the GNU Lesser General Public License as
10 * published by the Free Software Foundation; either version 2.1 of
11 * the License, or (at your option) any later version.
12 *
13 * Libgcrypt is distributed in the hope that it will be useful,
14 * but WITHOUT ANY WARRANTY; without even the implied warranty of
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 * GNU Lesser General Public License for more details.
17 *
18 * You should have received a copy of the GNU Lesser General Public
19 * License along with this program; if not, see <http://www.gnu.org/licenses/>.
20 */
21
22 #include <config.h>
23 #include <stdio.h>
24 #include <stdlib.h>
25 #include <string.h>
26
27 #include "g10lib.h"
28 #include "mpi.h"
29 #include "cipher.h"
30 #include "pubkey-internal.h"
31
32
33 typedef struct
34 {
35 gcry_mpi_t p; /* prime */
36 gcry_mpi_t q; /* group order */
37 gcry_mpi_t g; /* group generator */
38 gcry_mpi_t y; /* g^x mod p */
39 } DSA_public_key;
40
41
42 typedef struct
43 {
44 gcry_mpi_t p; /* prime */
45 gcry_mpi_t q; /* group order */
46 gcry_mpi_t g; /* group generator */
47 gcry_mpi_t y; /* g^x mod p */
48 gcry_mpi_t x; /* secret exponent */
49 } DSA_secret_key;
50
51
52 /* A structure used to hold domain parameters. */
53 typedef struct
54 {
55 gcry_mpi_t p; /* prime */
56 gcry_mpi_t q; /* group order */
57 gcry_mpi_t g; /* group generator */
58 } dsa_domain_t;
59
60
61 static const char *dsa_names[] =
62 {
63 "dsa",
64 "openpgp-dsa",
65 NULL,
66 };
67
68
69 /* A sample 1024 bit DSA key used for the selftests. Not anymore
70 * used, kept only for reference. */
71 #if 0
72 static const char sample_secret_key_1024[] =
73 "(private-key"
74 " (dsa"
75 " (p #00AD7C0025BA1A15F775F3F2D673718391D00456978D347B33D7B49E7F32EDAB"
76 " 96273899DD8B2BB46CD6ECA263FAF04A28903503D59062A8865D2AE8ADFB5191"
77 " CF36FFB562D0E2F5809801A1F675DAE59698A9E01EFE8D7DCFCA084F4C6F5A44"
78 " 44D499A06FFAEA5E8EF5E01F2FD20A7B7EF3F6968AFBA1FB8D91F1559D52D8777B#)"
79 " (q #00EB7B5751D25EBBB7BD59D920315FD840E19AEBF9#)"
80 " (g #1574363387FDFD1DDF38F4FBE135BB20C7EE4772FB94C337AF86EA8E49666503"
81 " AE04B6BE81A2F8DD095311E0217ACA698A11E6C5D33CCDAE71498ED35D13991E"
82 " B02F09AB40BD8F4C5ED8C75DA779D0AE104BC34C960B002377068AB4B5A1F984"
83 " 3FBA91F537F1B7CAC4D8DD6D89B0D863AF7025D549F9C765D2FC07EE208F8D15#)"
84 " (y #64B11EF8871BE4AB572AA810D5D3CA11A6CDBC637A8014602C72960DB135BF46"
85 " A1816A724C34F87330FC9E187C5D66897A04535CC2AC9164A7150ABFA8179827"
86 " 6E45831AB811EEE848EBB24D9F5F2883B6E5DDC4C659DEF944DCFD80BF4D0A20"
87 " 42CAA7DC289F0C5A9D155F02D3D551DB741A81695B74D4C8F477F9C7838EB0FB#)"
88 " (x #11D54E4ADBD3034160F2CED4B7CD292A4EBF3EC0#)))";
89 /* A sample 1024 bit DSA key used for the selftests (public only). */
90 static const char sample_public_key_1024[] =
91 "(public-key"
92 " (dsa"
93 " (p #00AD7C0025BA1A15F775F3F2D673718391D00456978D347B33D7B49E7F32EDAB"
94 " 96273899DD8B2BB46CD6ECA263FAF04A28903503D59062A8865D2AE8ADFB5191"
95 " CF36FFB562D0E2F5809801A1F675DAE59698A9E01EFE8D7DCFCA084F4C6F5A44"
96 " 44D499A06FFAEA5E8EF5E01F2FD20A7B7EF3F6968AFBA1FB8D91F1559D52D8777B#)"
97 " (q #00EB7B5751D25EBBB7BD59D920315FD840E19AEBF9#)"
98 " (g #1574363387FDFD1DDF38F4FBE135BB20C7EE4772FB94C337AF86EA8E49666503"
99 " AE04B6BE81A2F8DD095311E0217ACA698A11E6C5D33CCDAE71498ED35D13991E"
100 " B02F09AB40BD8F4C5ED8C75DA779D0AE104BC34C960B002377068AB4B5A1F984"
101 " 3FBA91F537F1B7CAC4D8DD6D89B0D863AF7025D549F9C765D2FC07EE208F8D15#)"
102 " (y #64B11EF8871BE4AB572AA810D5D3CA11A6CDBC637A8014602C72960DB135BF46"
103 " A1816A724C34F87330FC9E187C5D66897A04535CC2AC9164A7150ABFA8179827"
104 " 6E45831AB811EEE848EBB24D9F5F2883B6E5DDC4C659DEF944DCFD80BF4D0A20"
105 " 42CAA7DC289F0C5A9D155F02D3D551DB741A81695B74D4C8F477F9C7838EB0FB#)))";
106 #endif /*0*/
107
108 /* 2048 DSA key from RFC 6979 A.2.2 */
109 static const char sample_public_key_2048[] =
110 "(public-key"
111 " (dsa"
112 " (p #9DB6FB5951B66BB6FE1E140F1D2CE5502374161FD6538DF1648218642F0B5C48C8F7A41AADFA187324B87674FA1822B00F1ECF8136943D7C55757264E5A1A44FFE012E9936E00C1D3E9310B01C7D179805D3058B2A9F4BB6F9716BFE6117C6B5B3CC4D9BE341104AD4A80AD6C94E005F4B993E14F091EB51743BF33050C38DE235567E1B34C3D6A5C0CEAA1A0F368213C3D19843D0B4B09DCB9FC72D39C8DE41F1BF14D4BB4563CA28371621CAD3324B6A2D392145BEBFAC748805236F5CA2FE92B871CD8F9C36D3292B5509CA8CAA77A2ADFC7BFD77DDA6F71125A7456FEA153E433256A2261C6A06ED3693797E7995FAD5AABBCFBE3EDA2741E375404AE25B#)"
113 " (q #F2C3119374CE76C9356990B465374A17F23F9ED35089BD969F61C6DDE9998C1F#)"
114 " (g #5C7FF6B06F8F143FE8288433493E4769C4D988ACE5BE25A0E24809670716C613D7B0CEE6932F8FAA7C44D2CB24523DA53FBE4F6EC3595892D1AA58C4328A06C46A15662E7EAA703A1DECF8BBB2D05DBE2EB956C142A338661D10461C0D135472085057F3494309FFA73C611F78B32ADBB5740C361C9F35BE90997DB2014E2EF5AA61782F52ABEB8BD6432C4DD097BC5423B285DAFB60DC364E8161F4A2A35ACA3A10B1C4D203CC76A470A33AFDCBDD92959859ABD8B56E1725252D78EAC66E71BA9AE3F1DD2487199874393CD4D832186800654760E1E34C09E4D155179F9EC0DC4473F996BDCE6EED1CABED8B6F116F7AD9CF505DF0F998E34AB27514B0FFE7#)"
115 " (y #667098C654426C78D7F8201EAC6C203EF030D43605032C2F1FA937E5237DBD949F34A0A2564FE126DC8B715C5141802CE0979C8246463C40E6B6BDAA2513FA611728716C2E4FD53BC95B89E69949D96512E873B9C8F8DFD499CC312882561ADECB31F658E934C0C197F2C4D96B05CBAD67381E7B768891E4DA3843D24D94CDFB5126E9B8BF21E8358EE0E0A30EF13FD6A664C0DCE3731F7FB49A4845A4FD8254687972A2D382599C9BAC4E0ED7998193078913032558134976410B89D2C171D123AC35FD977219597AA7D15C1A9A428E59194F75C721EBCBCFAE44696A499AFA74E04299F132026601638CB87AB79190D4A0986315DA8EEC6561C938996BEADF#)))";
116
117 static const char sample_secret_key_2048[] =
118 "(private-key"
119 " (dsa"
120 " (p #9DB6FB5951B66BB6FE1E140F1D2CE5502374161FD6538DF1648218642F0B5C48C8F7A41AADFA187324B87674FA1822B00F1ECF8136943D7C55757264E5A1A44FFE012E9936E00C1D3E9310B01C7D179805D3058B2A9F4BB6F9716BFE6117C6B5B3CC4D9BE341104AD4A80AD6C94E005F4B993E14F091EB51743BF33050C38DE235567E1B34C3D6A5C0CEAA1A0F368213C3D19843D0B4B09DCB9FC72D39C8DE41F1BF14D4BB4563CA28371621CAD3324B6A2D392145BEBFAC748805236F5CA2FE92B871CD8F9C36D3292B5509CA8CAA77A2ADFC7BFD77DDA6F71125A7456FEA153E433256A2261C6A06ED3693797E7995FAD5AABBCFBE3EDA2741E375404AE25B#)"
121 " (q #F2C3119374CE76C9356990B465374A17F23F9ED35089BD969F61C6DDE9998C1F#)"
122 " (g #5C7FF6B06F8F143FE8288433493E4769C4D988ACE5BE25A0E24809670716C613D7B0CEE6932F8FAA7C44D2CB24523DA53FBE4F6EC3595892D1AA58C4328A06C46A15662E7EAA703A1DECF8BBB2D05DBE2EB956C142A338661D10461C0D135472085057F3494309FFA73C611F78B32ADBB5740C361C9F35BE90997DB2014E2EF5AA61782F52ABEB8BD6432C4DD097BC5423B285DAFB60DC364E8161F4A2A35ACA3A10B1C4D203CC76A470A33AFDCBDD92959859ABD8B56E1725252D78EAC66E71BA9AE3F1DD2487199874393CD4D832186800654760E1E34C09E4D155179F9EC0DC4473F996BDCE6EED1CABED8B6F116F7AD9CF505DF0F998E34AB27514B0FFE7#)"
123 " (y #667098C654426C78D7F8201EAC6C203EF030D43605032C2F1FA937E5237DBD949F34A0A2564FE126DC8B715C5141802CE0979C8246463C40E6B6BDAA2513FA611728716C2E4FD53BC95B89E69949D96512E873B9C8F8DFD499CC312882561ADECB31F658E934C0C197F2C4D96B05CBAD67381E7B768891E4DA3843D24D94CDFB5126E9B8BF21E8358EE0E0A30EF13FD6A664C0DCE3731F7FB49A4845A4FD8254687972A2D382599C9BAC4E0ED7998193078913032558134976410B89D2C171D123AC35FD977219597AA7D15C1A9A428E59194F75C721EBCBCFAE44696A499AFA74E04299F132026601638CB87AB79190D4A0986315DA8EEC6561C938996BEADF#)"
124 " (x #69C7548C21D0DFEA6B9A51C9EAD4E27C33D3B3F180316E5BCAB92C933F0E4DBC#)))";
125
126
127
128 static int test_keys (DSA_secret_key *sk, unsigned int qbits);
129 static int check_secret_key (DSA_secret_key *sk);
130 static gpg_err_code_t generate (DSA_secret_key *sk,
131 unsigned int nbits,
132 unsigned int qbits,
133 int transient_key,
134 dsa_domain_t *domain,
135 gcry_mpi_t **ret_factors);
136 static gpg_err_code_t sign (gcry_mpi_t r, gcry_mpi_t s, gcry_mpi_t input,
137 DSA_secret_key *skey, int flags, int hashalgo);
138 static gpg_err_code_t verify (gcry_mpi_t r, gcry_mpi_t s, gcry_mpi_t input,
139 DSA_public_key *pkey);
140 static unsigned int dsa_get_nbits (gcry_sexp_t parms);
141
142
143 static void (*progress_cb) (void *,const char *, int, int, int );
144 static void *progress_cb_data;
145
146
147 void
_gcry_register_pk_dsa_progress(void (* cb)(void *,const char *,int,int,int),void * cb_data)148 _gcry_register_pk_dsa_progress (void (*cb) (void *, const char *,
149 int, int, int),
150 void *cb_data)
151 {
152 progress_cb = cb;
153 progress_cb_data = cb_data;
154 }
155
156
157 static void
progress(int c)158 progress (int c)
159 {
160 if (progress_cb)
161 progress_cb (progress_cb_data, "pk_dsa", c, 0, 0);
162 }
163
164
165 /* Check that a freshly generated key actually works. Returns 0 on success. */
166 static int
test_keys(DSA_secret_key * sk,unsigned int qbits)167 test_keys (DSA_secret_key *sk, unsigned int qbits)
168 {
169 int result = -1; /* Default to failure. */
170 DSA_public_key pk;
171 gcry_mpi_t data = mpi_new (qbits);
172 gcry_mpi_t sig_a = mpi_new (qbits);
173 gcry_mpi_t sig_b = mpi_new (qbits);
174
175 /* Put the relevant parameters into a public key structure. */
176 pk.p = sk->p;
177 pk.q = sk->q;
178 pk.g = sk->g;
179 pk.y = sk->y;
180
181 /* Create a random plaintext. */
182 _gcry_mpi_randomize (data, qbits, GCRY_WEAK_RANDOM);
183
184 /* Sign DATA using the secret key. */
185 sign (sig_a, sig_b, data, sk, 0, 0);
186
187 /* Verify the signature using the public key. */
188 if ( verify (sig_a, sig_b, data, &pk) )
189 goto leave; /* Signature does not match. */
190
191 /* Modify the data and check that the signing fails. */
192 mpi_add_ui (data, data, 1);
193 if ( !verify (sig_a, sig_b, data, &pk) )
194 goto leave; /* Signature matches but should not. */
195
196 result = 0; /* The test succeeded. */
197
198 leave:
199 _gcry_mpi_release (sig_b);
200 _gcry_mpi_release (sig_a);
201 _gcry_mpi_release (data);
202 return result;
203 }
204
205
206
207 /*
208 Generate a DSA key pair with a key of size NBITS. If transient_key
209 is true the key is generated using the standard RNG and not the
210 very secure one.
211
212 Returns: 2 structures filled with all needed values
213 and an array with the n-1 factors of (p-1)
214 */
215 static gpg_err_code_t
generate(DSA_secret_key * sk,unsigned int nbits,unsigned int qbits,int transient_key,dsa_domain_t * domain,gcry_mpi_t ** ret_factors)216 generate (DSA_secret_key *sk, unsigned int nbits, unsigned int qbits,
217 int transient_key, dsa_domain_t *domain, gcry_mpi_t **ret_factors )
218 {
219 gpg_err_code_t rc;
220 gcry_mpi_t p; /* the prime */
221 gcry_mpi_t q; /* the 160 bit prime factor */
222 gcry_mpi_t g; /* the generator */
223 gcry_mpi_t y; /* g^x mod p */
224 gcry_mpi_t x; /* the secret exponent */
225 gcry_mpi_t h, e; /* helper */
226 unsigned char *rndbuf;
227 gcry_random_level_t random_level;
228
229 if (qbits)
230 ; /* Caller supplied qbits. Use this value. */
231 else if ( nbits >= 512 && nbits <= 1024 )
232 qbits = 160;
233 else if ( nbits == 2048 )
234 qbits = 224;
235 else if ( nbits == 3072 )
236 qbits = 256;
237 else if ( nbits == 7680 )
238 qbits = 384;
239 else if ( nbits == 15360 )
240 qbits = 512;
241 else
242 return GPG_ERR_INV_VALUE;
243
244 if (qbits < 160 || qbits > 512 || (qbits%8) )
245 return GPG_ERR_INV_VALUE;
246 if (nbits < 2*qbits || nbits > 15360)
247 return GPG_ERR_INV_VALUE;
248
249 if (fips_mode ())
250 {
251 if (nbits < 1024)
252 return GPG_ERR_INV_VALUE;
253 if (transient_key)
254 return GPG_ERR_INV_VALUE;
255 }
256
257 if (domain->p && domain->q && domain->g)
258 {
259 /* Domain parameters are given; use them. */
260 p = mpi_copy (domain->p);
261 q = mpi_copy (domain->q);
262 g = mpi_copy (domain->g);
263 gcry_assert (mpi_get_nbits (p) == nbits);
264 gcry_assert (mpi_get_nbits (q) == qbits);
265 h = mpi_alloc (0);
266 e = NULL;
267 }
268 else
269 {
270 /* Generate new domain parameters. */
271 rc = _gcry_generate_elg_prime (1, nbits, qbits, NULL, &p, ret_factors);
272 if (rc)
273 return rc;
274
275 /* Get q out of factors. */
276 q = mpi_copy ((*ret_factors)[0]);
277 gcry_assert (mpi_get_nbits (q) == qbits);
278
279 /* Find a generator g (h and e are helpers).
280 e = (p-1)/q */
281 e = mpi_alloc (mpi_get_nlimbs (p));
282 mpi_sub_ui (e, p, 1);
283 mpi_fdiv_q (e, e, q);
284 g = mpi_alloc (mpi_get_nlimbs (p));
285 h = mpi_alloc_set_ui (1); /* (We start with 2.) */
286 do
287 {
288 mpi_add_ui (h, h, 1);
289 /* g = h^e mod p */
290 mpi_powm (g, h, e, p);
291 }
292 while (!mpi_cmp_ui (g, 1)); /* Continue until g != 1. */
293 }
294
295 /* Select a random number X with the property:
296 * 0 < x < q-1
297 *
298 * FIXME: Why do we use the requirement x < q-1 ? It should be
299 * sufficient to test for x < q. FIPS-186-3 check x < q-1 but it
300 * does not check for 0 < x because it makes sure that Q is unsigned
301 * and finally adds one to the result so that 0 will never be
302 * returned. We should replace the code below with _gcry_dsa_gen_k.
303 *
304 * This must be a very good random number because this is the secret
305 * part. The random quality depends on the transient_key flag. */
306 random_level = transient_key ? GCRY_STRONG_RANDOM : GCRY_VERY_STRONG_RANDOM;
307 if (DBG_CIPHER)
308 log_debug("choosing a random x%s\n", transient_key? " (transient-key)":"");
309 gcry_assert( qbits >= 160 );
310 x = mpi_alloc_secure( mpi_get_nlimbs(q) );
311 mpi_sub_ui( h, q, 1 ); /* put q-1 into h */
312 rndbuf = NULL;
313 do
314 {
315 if( DBG_CIPHER )
316 progress('.');
317 if( !rndbuf )
318 rndbuf = _gcry_random_bytes_secure ((qbits+7)/8, random_level);
319 else
320 { /* Change only some of the higher bits (= 2 bytes)*/
321 char *r = _gcry_random_bytes_secure (2, random_level);
322 memcpy(rndbuf, r, 2 );
323 xfree(r);
324 }
325
326 _gcry_mpi_set_buffer( x, rndbuf, (qbits+7)/8, 0 );
327 mpi_clear_highbit( x, qbits+1 );
328 }
329 while ( !( mpi_cmp_ui( x, 0 )>0 && mpi_cmp( x, h )<0 ) );
330 xfree(rndbuf);
331 mpi_free( e );
332 mpi_free( h );
333
334 /* y = g^x mod p */
335 y = mpi_alloc( mpi_get_nlimbs(p) );
336 mpi_powm (y, g, x, p);
337
338 if( DBG_CIPHER )
339 {
340 progress('\n');
341 log_mpidump("dsa p", p );
342 log_mpidump("dsa q", q );
343 log_mpidump("dsa g", g );
344 log_mpidump("dsa y", y );
345 log_mpidump("dsa x", x );
346 }
347
348 /* Copy the stuff to the key structures. */
349 sk->p = p;
350 sk->q = q;
351 sk->g = g;
352 sk->y = y;
353 sk->x = x;
354
355 /* Now we can test our keys (this should never fail!). */
356 if ( test_keys (sk, qbits) )
357 {
358 _gcry_mpi_release (sk->p); sk->p = NULL;
359 _gcry_mpi_release (sk->q); sk->q = NULL;
360 _gcry_mpi_release (sk->g); sk->g = NULL;
361 _gcry_mpi_release (sk->y); sk->y = NULL;
362 _gcry_mpi_release (sk->x); sk->x = NULL;
363 fips_signal_error ("self-test after key generation failed");
364 return GPG_ERR_SELFTEST_FAILED;
365 }
366 return 0;
367 }
368
369
370 /* Generate a DSA key pair with a key of size NBITS using the
371 algorithm given in FIPS-186-3. If USE_FIPS186_2 is true,
372 FIPS-186-2 is used and thus the length is restricted to 1024/160.
373 If DERIVEPARMS is not NULL it may contain a seed value. If domain
374 parameters are specified in DOMAIN, DERIVEPARMS may not be given
375 and NBITS and QBITS must match the specified domain parameters. */
376 static gpg_err_code_t
generate_fips186(DSA_secret_key * sk,unsigned int nbits,unsigned int qbits,gcry_sexp_t deriveparms,int use_fips186_2,dsa_domain_t * domain,int * r_counter,void ** r_seed,size_t * r_seedlen,gcry_mpi_t * r_h)377 generate_fips186 (DSA_secret_key *sk, unsigned int nbits, unsigned int qbits,
378 gcry_sexp_t deriveparms, int use_fips186_2,
379 dsa_domain_t *domain,
380 int *r_counter, void **r_seed, size_t *r_seedlen,
381 gcry_mpi_t *r_h)
382 {
383 gpg_err_code_t ec;
384 struct {
385 gcry_sexp_t sexp;
386 const void *seed;
387 size_t seedlen;
388 } initial_seed = { NULL, NULL, 0 };
389 gcry_mpi_t prime_q = NULL;
390 gcry_mpi_t prime_p = NULL;
391 gcry_mpi_t value_g = NULL; /* The generator. */
392 gcry_mpi_t value_y = NULL; /* g^x mod p */
393 gcry_mpi_t value_x = NULL; /* The secret exponent. */
394 gcry_mpi_t value_h = NULL; /* Helper. */
395 gcry_mpi_t value_e = NULL; /* Helper. */
396 gcry_mpi_t value_c = NULL; /* helper for x */
397 gcry_mpi_t value_qm2 = NULL; /* q - 2 */
398
399 /* Preset return values. */
400 *r_counter = 0;
401 *r_seed = NULL;
402 *r_seedlen = 0;
403 *r_h = NULL;
404
405 /* Derive QBITS from NBITS if requested */
406 if (!qbits)
407 {
408 if (nbits == 1024)
409 qbits = 160;
410 else if (nbits == 2048)
411 qbits = 224;
412 else if (nbits == 3072)
413 qbits = 256;
414 }
415
416 /* Check that QBITS and NBITS match the standard. Note that FIPS
417 186-3 uses N for QBITS and L for NBITS. */
418 if (nbits == 1024 && qbits == 160 && use_fips186_2)
419 ; /* Allowed in FIPS 186-2 mode. */
420 else if (nbits == 2048 && qbits == 224)
421 ;
422 else if (nbits == 2048 && qbits == 256)
423 ;
424 else if (nbits == 3072 && qbits == 256)
425 ;
426 else
427 return GPG_ERR_INV_VALUE;
428
429 if (domain->p && domain->q && domain->g)
430 {
431 /* Domain parameters are given; use them. */
432 prime_p = mpi_copy (domain->p);
433 prime_q = mpi_copy (domain->q);
434 value_g = mpi_copy (domain->g);
435 gcry_assert (mpi_get_nbits (prime_p) == nbits);
436 gcry_assert (mpi_get_nbits (prime_q) == qbits);
437 gcry_assert (!deriveparms);
438 ec = 0;
439 }
440 else
441 {
442 /* Generate new domain parameters. */
443
444 /* Get an initial seed value. */
445 if (deriveparms)
446 {
447 initial_seed.sexp = sexp_find_token (deriveparms, "seed", 0);
448 if (initial_seed.sexp)
449 initial_seed.seed = sexp_nth_data (initial_seed.sexp, 1,
450 &initial_seed.seedlen);
451 }
452
453 if (use_fips186_2)
454 ec = _gcry_generate_fips186_2_prime (nbits, qbits,
455 initial_seed.seed,
456 initial_seed.seedlen,
457 &prime_q, &prime_p,
458 r_counter,
459 r_seed, r_seedlen);
460 else
461 ec = _gcry_generate_fips186_3_prime (nbits, qbits,
462 initial_seed.seed,
463 initial_seed.seedlen,
464 &prime_q, &prime_p,
465 r_counter,
466 r_seed, r_seedlen, NULL);
467 sexp_release (initial_seed.sexp);
468 if (ec)
469 goto leave;
470
471 /* Find a generator g (h and e are helpers).
472 * e = (p-1)/q
473 */
474 value_e = mpi_alloc_like (prime_p);
475 mpi_sub_ui (value_e, prime_p, 1);
476 mpi_fdiv_q (value_e, value_e, prime_q );
477 value_g = mpi_alloc_like (prime_p);
478 value_h = mpi_alloc_set_ui (1);
479 do
480 {
481 mpi_add_ui (value_h, value_h, 1);
482 /* g = h^e mod p */
483 mpi_powm (value_g, value_h, value_e, prime_p);
484 }
485 while (!mpi_cmp_ui (value_g, 1)); /* Continue until g != 1. */
486 }
487
488 value_c = mpi_snew (qbits);
489 value_x = mpi_snew (qbits);
490 value_qm2 = mpi_snew (qbits);
491 mpi_sub_ui (value_qm2, prime_q, 2);
492
493 /* FIPS 186-4 B.1.2 steps 4-6 */
494 do
495 {
496 if( DBG_CIPHER )
497 progress('.');
498 _gcry_mpi_randomize (value_c, qbits, GCRY_VERY_STRONG_RANDOM);
499 mpi_clear_highbit (value_c, qbits+1);
500 }
501 while (!(mpi_cmp_ui (value_c, 0) > 0 && mpi_cmp (value_c, value_qm2) < 0));
502 /* while (mpi_cmp (value_c, value_qm2) > 0); */
503
504 /* x = c + 1 */
505 mpi_add_ui(value_x, value_c, 1);
506
507 /* y = g^x mod p */
508 value_y = mpi_alloc_like (prime_p);
509 mpi_powm (value_y, value_g, value_x, prime_p);
510
511 if (DBG_CIPHER)
512 {
513 progress('\n');
514 log_mpidump("dsa p", prime_p );
515 log_mpidump("dsa q", prime_q );
516 log_mpidump("dsa g", value_g );
517 log_mpidump("dsa y", value_y );
518 log_mpidump("dsa x", value_x );
519 log_mpidump("dsa h", value_h );
520 }
521
522 /* Copy the stuff to the key structures. */
523 sk->p = prime_p; prime_p = NULL;
524 sk->q = prime_q; prime_q = NULL;
525 sk->g = value_g; value_g = NULL;
526 sk->y = value_y; value_y = NULL;
527 sk->x = value_x; value_x = NULL;
528 *r_h = value_h; value_h = NULL;
529
530 leave:
531 _gcry_mpi_release (prime_p);
532 _gcry_mpi_release (prime_q);
533 _gcry_mpi_release (value_g);
534 _gcry_mpi_release (value_y);
535 _gcry_mpi_release (value_x);
536 _gcry_mpi_release (value_h);
537 _gcry_mpi_release (value_e);
538 _gcry_mpi_release (value_c);
539 _gcry_mpi_release (value_qm2);
540
541 /* As a last step test this keys (this should never fail of course). */
542 if (!ec && test_keys (sk, qbits) )
543 {
544 _gcry_mpi_release (sk->p); sk->p = NULL;
545 _gcry_mpi_release (sk->q); sk->q = NULL;
546 _gcry_mpi_release (sk->g); sk->g = NULL;
547 _gcry_mpi_release (sk->y); sk->y = NULL;
548 _gcry_mpi_release (sk->x); sk->x = NULL;
549 fips_signal_error ("self-test after key generation failed");
550 ec = GPG_ERR_SELFTEST_FAILED;
551 }
552
553 if (ec)
554 {
555 *r_counter = 0;
556 xfree (*r_seed); *r_seed = NULL;
557 *r_seedlen = 0;
558 _gcry_mpi_release (*r_h); *r_h = NULL;
559 }
560
561 return ec;
562 }
563
564
565
566 /*
567 Test whether the secret key is valid.
568 Returns: if this is a valid key.
569 */
570 static int
check_secret_key(DSA_secret_key * sk)571 check_secret_key( DSA_secret_key *sk )
572 {
573 int rc;
574 gcry_mpi_t y = mpi_alloc( mpi_get_nlimbs(sk->y) );
575
576 mpi_powm( y, sk->g, sk->x, sk->p );
577 rc = !mpi_cmp( y, sk->y );
578 mpi_free( y );
579 return rc;
580 }
581
582
583
584 /*
585 Make a DSA signature from INPUT and put it into r and s.
586
587 INPUT may either be a plain MPI or an opaque MPI which is then
588 internally converted to a plain MPI. FLAGS and HASHALGO may both
589 be 0 for standard operation mode.
590
591 The return value is 0 on success or an error code. Note that for
592 backward compatibility the function will not return any error if
593 FLAGS and HASHALGO are both 0 and INPUT is a plain MPI.
594 */
595 static gpg_err_code_t
sign(gcry_mpi_t r,gcry_mpi_t s,gcry_mpi_t input,DSA_secret_key * skey,int flags,int hashalgo)596 sign (gcry_mpi_t r, gcry_mpi_t s, gcry_mpi_t input, DSA_secret_key *skey,
597 int flags, int hashalgo)
598 {
599 gpg_err_code_t rc;
600 gcry_mpi_t hash;
601 gcry_mpi_t k;
602 gcry_mpi_t kinv;
603 gcry_mpi_t tmp;
604 const void *abuf;
605 unsigned int abits, qbits;
606 int extraloops = 0;
607
608 qbits = mpi_get_nbits (skey->q);
609
610 /* Convert the INPUT into an MPI. */
611 rc = _gcry_dsa_normalize_hash (input, &hash, qbits);
612 if (rc)
613 return rc;
614
615 again:
616 /* Create the K value. */
617 if ((flags & PUBKEY_FLAG_RFC6979) && hashalgo)
618 {
619 /* Use Pornin's method for deterministic DSA. If this flag is
620 set, it is expected that HASH is an opaque MPI with the to be
621 signed hash. That hash is also used as h1 from 3.2.a. */
622 if (!mpi_is_opaque (input))
623 {
624 rc = GPG_ERR_CONFLICT;
625 goto leave;
626 }
627
628 abuf = mpi_get_opaque (input, &abits);
629 rc = _gcry_dsa_gen_rfc6979_k (&k, skey->q, skey->x,
630 abuf, (abits+7)/8, hashalgo, extraloops);
631 if (rc)
632 goto leave;
633 }
634 else
635 {
636 /* Select a random k with 0 < k < q */
637 k = _gcry_dsa_gen_k (skey->q, GCRY_STRONG_RANDOM);
638 }
639
640 /* kinv = k^(-1) mod q */
641 kinv = mpi_alloc( mpi_get_nlimbs(k) );
642 mpi_invm(kinv, k, skey->q );
643
644 _gcry_dsa_modify_k (k, skey->q, qbits);
645
646 /* r = (a^k mod p) mod q */
647 mpi_powm( r, skey->g, k, skey->p );
648 mpi_fdiv_r( r, r, skey->q );
649
650 /* s = (kinv * ( hash + x * r)) mod q */
651 tmp = mpi_alloc( mpi_get_nlimbs(skey->p) );
652 mpi_mul( tmp, skey->x, r );
653 mpi_add( tmp, tmp, hash );
654 mpi_mulm( s , kinv, tmp, skey->q );
655
656 mpi_free(k);
657 mpi_free(kinv);
658 mpi_free(tmp);
659
660 if (!mpi_cmp_ui (r, 0))
661 {
662 /* This is a highly unlikely code path. */
663 extraloops++;
664 goto again;
665 }
666
667 rc = 0;
668
669 leave:
670 if (hash != input)
671 mpi_free (hash);
672
673 return rc;
674 }
675
676
677 /*
678 Returns true if the signature composed from R and S is valid.
679 */
680 static gpg_err_code_t
verify(gcry_mpi_t r,gcry_mpi_t s,gcry_mpi_t input,DSA_public_key * pkey)681 verify (gcry_mpi_t r, gcry_mpi_t s, gcry_mpi_t input, DSA_public_key *pkey )
682 {
683 gpg_err_code_t rc = 0;
684 gcry_mpi_t w, u1, u2, v;
685 gcry_mpi_t base[3];
686 gcry_mpi_t ex[3];
687 gcry_mpi_t hash;
688 unsigned int nbits;
689
690 if( !(mpi_cmp_ui( r, 0 ) > 0 && mpi_cmp( r, pkey->q ) < 0) )
691 return GPG_ERR_BAD_SIGNATURE; /* Assertion 0 < r < n failed. */
692 if( !(mpi_cmp_ui( s, 0 ) > 0 && mpi_cmp( s, pkey->q ) < 0) )
693 return GPG_ERR_BAD_SIGNATURE; /* Assertion 0 < s < n failed. */
694
695 nbits = mpi_get_nbits (pkey->q);
696 rc = _gcry_dsa_normalize_hash (input, &hash, nbits);
697 if (rc)
698 return rc;
699
700 w = mpi_alloc( mpi_get_nlimbs(pkey->q) );
701 u1 = mpi_alloc( mpi_get_nlimbs(pkey->q) );
702 u2 = mpi_alloc( mpi_get_nlimbs(pkey->q) );
703 v = mpi_alloc( mpi_get_nlimbs(pkey->p) );
704
705 /* w = s^(-1) mod q */
706 mpi_invm( w, s, pkey->q );
707
708 /* u1 = (hash * w) mod q */
709 mpi_mulm( u1, hash, w, pkey->q );
710
711 /* u2 = r * w mod q */
712 mpi_mulm( u2, r, w, pkey->q );
713
714 /* v = g^u1 * y^u2 mod p mod q */
715 base[0] = pkey->g; ex[0] = u1;
716 base[1] = pkey->y; ex[1] = u2;
717 base[2] = NULL; ex[2] = NULL;
718 mpi_mulpowm( v, base, ex, pkey->p );
719 mpi_fdiv_r( v, v, pkey->q );
720
721 if (mpi_cmp( v, r ))
722 {
723 if (DBG_CIPHER)
724 {
725 log_mpidump (" i", input);
726 log_mpidump (" h", hash);
727 log_mpidump (" v", v);
728 log_mpidump (" r", r);
729 log_mpidump (" s", s);
730 }
731 rc = GPG_ERR_BAD_SIGNATURE;
732 }
733
734 mpi_free(w);
735 mpi_free(u1);
736 mpi_free(u2);
737 mpi_free(v);
738 if (hash != input)
739 mpi_free (hash);
740
741 return rc;
742 }
743
744
745 /*********************************************
746 ************** interface ******************
747 *********************************************/
748
749 static gcry_err_code_t
dsa_generate(const gcry_sexp_t genparms,gcry_sexp_t * r_skey)750 dsa_generate (const gcry_sexp_t genparms, gcry_sexp_t *r_skey)
751 {
752 gpg_err_code_t rc;
753 unsigned int nbits;
754 gcry_sexp_t domainsexp;
755 DSA_secret_key sk;
756 gcry_sexp_t l1;
757 unsigned int qbits = 0;
758 gcry_sexp_t deriveparms = NULL;
759 gcry_sexp_t seedinfo = NULL;
760 gcry_sexp_t misc_info = NULL;
761 int flags = 0;
762 dsa_domain_t domain;
763 gcry_mpi_t *factors = NULL;
764
765 memset (&sk, 0, sizeof sk);
766 memset (&domain, 0, sizeof domain);
767
768 rc = _gcry_pk_util_get_nbits (genparms, &nbits);
769 if (rc)
770 return rc;
771
772 /* Parse the optional flags list. */
773 l1 = sexp_find_token (genparms, "flags", 0);
774 if (l1)
775 {
776 rc = _gcry_pk_util_parse_flaglist (l1, &flags, NULL);
777 sexp_release (l1);
778 if (rc)
779 return rc;\
780 }
781
782 /* Parse the optional qbits element. */
783 l1 = sexp_find_token (genparms, "qbits", 0);
784 if (l1)
785 {
786 char buf[50];
787 const char *s;
788 size_t n;
789
790 s = sexp_nth_data (l1, 1, &n);
791 if (!s || n >= DIM (buf) - 1 )
792 {
793 sexp_release (l1);
794 return GPG_ERR_INV_OBJ; /* No value or value too large. */
795 }
796 memcpy (buf, s, n);
797 buf[n] = 0;
798 qbits = (unsigned int)strtoul (buf, NULL, 0);
799 sexp_release (l1);
800 }
801
802 /* Parse the optional transient-key flag. */
803 if (!(flags & PUBKEY_FLAG_TRANSIENT_KEY))
804 {
805 l1 = sexp_find_token (genparms, "transient-key", 0);
806 if (l1)
807 {
808 flags |= PUBKEY_FLAG_TRANSIENT_KEY;
809 sexp_release (l1);
810 }
811 }
812
813 /* Get the optional derive parameters. */
814 deriveparms = sexp_find_token (genparms, "derive-parms", 0);
815
816 /* Parse the optional "use-fips186" flags. */
817 if (!(flags & PUBKEY_FLAG_USE_FIPS186))
818 {
819 l1 = sexp_find_token (genparms, "use-fips186", 0);
820 if (l1)
821 {
822 flags |= PUBKEY_FLAG_USE_FIPS186;
823 sexp_release (l1);
824 }
825 }
826 if (!(flags & PUBKEY_FLAG_USE_FIPS186_2))
827 {
828 l1 = sexp_find_token (genparms, "use-fips186-2", 0);
829 if (l1)
830 {
831 flags |= PUBKEY_FLAG_USE_FIPS186_2;
832 sexp_release (l1);
833 }
834 }
835
836 /* Check whether domain parameters are given. */
837 domainsexp = sexp_find_token (genparms, "domain", 0);
838 if (domainsexp)
839 {
840 /* DERIVEPARMS can't be used together with domain parameters.
841 NBITS abnd QBITS may not be specified because there values
842 are derived from the domain parameters. */
843 if (deriveparms || qbits || nbits)
844 {
845 sexp_release (domainsexp);
846 sexp_release (deriveparms);
847 return GPG_ERR_INV_VALUE;
848 }
849
850 /* Put all domain parameters into the domain object. */
851 l1 = sexp_find_token (domainsexp, "p", 0);
852 domain.p = sexp_nth_mpi (l1, 1, GCRYMPI_FMT_USG);
853 sexp_release (l1);
854 l1 = sexp_find_token (domainsexp, "q", 0);
855 domain.q = sexp_nth_mpi (l1, 1, GCRYMPI_FMT_USG);
856 sexp_release (l1);
857 l1 = sexp_find_token (domainsexp, "g", 0);
858 domain.g = sexp_nth_mpi (l1, 1, GCRYMPI_FMT_USG);
859 sexp_release (l1);
860 sexp_release (domainsexp);
861
862 /* Check that all domain parameters are available. */
863 if (!domain.p || !domain.q || !domain.g)
864 {
865 _gcry_mpi_release (domain.p);
866 _gcry_mpi_release (domain.q);
867 _gcry_mpi_release (domain.g);
868 sexp_release (deriveparms);
869 return GPG_ERR_MISSING_VALUE;
870 }
871
872 /* Get NBITS and QBITS from the domain parameters. */
873 nbits = mpi_get_nbits (domain.p);
874 qbits = mpi_get_nbits (domain.q);
875 }
876
877 if (deriveparms
878 || (flags & PUBKEY_FLAG_USE_FIPS186)
879 || (flags & PUBKEY_FLAG_USE_FIPS186_2)
880 || fips_mode ())
881 {
882 int counter;
883 void *seed;
884 size_t seedlen;
885 gcry_mpi_t h_value;
886
887 rc = generate_fips186 (&sk, nbits, qbits, deriveparms,
888 !!(flags & PUBKEY_FLAG_USE_FIPS186_2),
889 &domain,
890 &counter, &seed, &seedlen, &h_value);
891 if (!rc && h_value)
892 {
893 /* Format the seed-values unless domain parameters are used
894 for which a H_VALUE of NULL is an indication. */
895 rc = sexp_build (&seedinfo, NULL,
896 "(seed-values(counter %d)(seed %b)(h %m))",
897 counter, (int)seedlen, seed, h_value);
898 xfree (seed);
899 _gcry_mpi_release (h_value);
900 }
901 }
902 else
903 {
904 rc = generate (&sk, nbits, qbits,
905 !!(flags & PUBKEY_FLAG_TRANSIENT_KEY),
906 &domain, &factors);
907 }
908
909 if (!rc)
910 {
911 /* Put the factors into MISC_INFO. Note that the factors are
912 not confidential thus we can store them in standard memory. */
913 int nfactors, i, j;
914 char *p;
915 char *format = NULL;
916 void **arg_list = NULL;
917
918 for (nfactors=0; factors && factors[nfactors]; nfactors++)
919 ;
920 /* Allocate space for the format string:
921 "(misc-key-info%S(pm1-factors%m))"
922 with one "%m" for each factor and construct it. */
923 format = xtrymalloc (50 + 2*nfactors);
924 if (!format)
925 rc = gpg_err_code_from_syserror ();
926 else
927 {
928 p = stpcpy (format, "(misc-key-info");
929 if (seedinfo)
930 p = stpcpy (p, "%S");
931 if (nfactors)
932 {
933 p = stpcpy (p, "(pm1-factors");
934 for (i=0; i < nfactors; i++)
935 p = stpcpy (p, "%m");
936 p = stpcpy (p, ")");
937 }
938 p = stpcpy (p, ")");
939
940 /* Allocate space for the list of factors plus one for the
941 seedinfo s-exp plus an extra NULL entry for safety and
942 fill it with the factors. */
943 arg_list = xtrycalloc (nfactors+1+1, sizeof *arg_list);
944 if (!arg_list)
945 rc = gpg_err_code_from_syserror ();
946 else
947 {
948 i = 0;
949 if (seedinfo)
950 arg_list[i++] = &seedinfo;
951 for (j=0; j < nfactors; j++)
952 arg_list[i++] = factors + j;
953 arg_list[i] = NULL;
954
955 rc = sexp_build_array (&misc_info, NULL, format, arg_list);
956 }
957 }
958
959 xfree (arg_list);
960 xfree (format);
961 }
962
963 if (!rc)
964 rc = sexp_build (r_skey, NULL,
965 "(key-data"
966 " (public-key"
967 " (dsa(p%m)(q%m)(g%m)(y%m)))"
968 " (private-key"
969 " (dsa(p%m)(q%m)(g%m)(y%m)(x%m)))"
970 " %S)",
971 sk.p, sk.q, sk.g, sk.y,
972 sk.p, sk.q, sk.g, sk.y, sk.x,
973 misc_info);
974
975
976 _gcry_mpi_release (sk.p);
977 _gcry_mpi_release (sk.q);
978 _gcry_mpi_release (sk.g);
979 _gcry_mpi_release (sk.y);
980 _gcry_mpi_release (sk.x);
981
982 _gcry_mpi_release (domain.p);
983 _gcry_mpi_release (domain.q);
984 _gcry_mpi_release (domain.g);
985
986 sexp_release (seedinfo);
987 sexp_release (misc_info);
988 sexp_release (deriveparms);
989 if (factors)
990 {
991 gcry_mpi_t *mp;
992 for (mp = factors; *mp; mp++)
993 mpi_free (*mp);
994 xfree (factors);
995 }
996 return rc;
997 }
998
999
1000
1001 static gcry_err_code_t
dsa_check_secret_key(gcry_sexp_t keyparms)1002 dsa_check_secret_key (gcry_sexp_t keyparms)
1003 {
1004 gcry_err_code_t rc;
1005 DSA_secret_key sk = {NULL, NULL, NULL, NULL, NULL};
1006
1007 rc = _gcry_sexp_extract_param (keyparms, NULL, "pqgyx",
1008 &sk.p, &sk.q, &sk.g, &sk.y, &sk.x,
1009 NULL);
1010 if (rc)
1011 goto leave;
1012
1013 if (!check_secret_key (&sk))
1014 rc = GPG_ERR_BAD_SECKEY;
1015
1016 leave:
1017 _gcry_mpi_release (sk.p);
1018 _gcry_mpi_release (sk.q);
1019 _gcry_mpi_release (sk.g);
1020 _gcry_mpi_release (sk.y);
1021 _gcry_mpi_release (sk.x);
1022 if (DBG_CIPHER)
1023 log_debug ("dsa_testkey => %s\n", gpg_strerror (rc));
1024 return rc;
1025 }
1026
1027
1028 static gcry_err_code_t
dsa_sign(gcry_sexp_t * r_sig,gcry_sexp_t s_data,gcry_sexp_t keyparms)1029 dsa_sign (gcry_sexp_t *r_sig, gcry_sexp_t s_data, gcry_sexp_t keyparms)
1030 {
1031 gcry_err_code_t rc;
1032 struct pk_encoding_ctx ctx;
1033 gcry_mpi_t data = NULL;
1034 DSA_secret_key sk = {NULL, NULL, NULL, NULL, NULL};
1035 gcry_mpi_t sig_r = NULL;
1036 gcry_mpi_t sig_s = NULL;
1037
1038 _gcry_pk_util_init_encoding_ctx (&ctx, PUBKEY_OP_SIGN,
1039 dsa_get_nbits (keyparms));
1040
1041 /* Extract the data. */
1042 rc = _gcry_pk_util_data_to_mpi (s_data, &data, &ctx);
1043 if (rc)
1044 goto leave;
1045 if (DBG_CIPHER)
1046 log_mpidump ("dsa_sign data", data);
1047
1048 /* Extract the key. */
1049 rc = _gcry_sexp_extract_param (keyparms, NULL, "pqgyx",
1050 &sk.p, &sk.q, &sk.g, &sk.y, &sk.x, NULL);
1051 if (rc)
1052 goto leave;
1053 if (DBG_CIPHER)
1054 {
1055 log_mpidump ("dsa_sign p", sk.p);
1056 log_mpidump ("dsa_sign q", sk.q);
1057 log_mpidump ("dsa_sign g", sk.g);
1058 log_mpidump ("dsa_sign y", sk.y);
1059 if (!fips_mode ())
1060 log_mpidump ("dsa_sign x", sk.x);
1061 }
1062
1063 sig_r = mpi_new (0);
1064 sig_s = mpi_new (0);
1065 rc = sign (sig_r, sig_s, data, &sk, ctx.flags, ctx.hash_algo);
1066 if (rc)
1067 goto leave;
1068 if (DBG_CIPHER)
1069 {
1070 log_mpidump ("dsa_sign sig_r", sig_r);
1071 log_mpidump ("dsa_sign sig_s", sig_s);
1072 }
1073 rc = sexp_build (r_sig, NULL, "(sig-val(dsa(r%M)(s%M)))", sig_r, sig_s);
1074
1075 leave:
1076 _gcry_mpi_release (sig_r);
1077 _gcry_mpi_release (sig_s);
1078 _gcry_mpi_release (sk.p);
1079 _gcry_mpi_release (sk.q);
1080 _gcry_mpi_release (sk.g);
1081 _gcry_mpi_release (sk.y);
1082 _gcry_mpi_release (sk.x);
1083 _gcry_mpi_release (data);
1084 _gcry_pk_util_free_encoding_ctx (&ctx);
1085 if (DBG_CIPHER)
1086 log_debug ("dsa_sign => %s\n", gpg_strerror (rc));
1087 return rc;
1088 }
1089
1090
1091 static gcry_err_code_t
dsa_verify(gcry_sexp_t s_sig,gcry_sexp_t s_data,gcry_sexp_t s_keyparms)1092 dsa_verify (gcry_sexp_t s_sig, gcry_sexp_t s_data, gcry_sexp_t s_keyparms)
1093 {
1094 gcry_err_code_t rc;
1095 struct pk_encoding_ctx ctx;
1096 gcry_sexp_t l1 = NULL;
1097 gcry_mpi_t sig_r = NULL;
1098 gcry_mpi_t sig_s = NULL;
1099 gcry_mpi_t data = NULL;
1100 DSA_public_key pk = { NULL, NULL, NULL, NULL };
1101
1102 _gcry_pk_util_init_encoding_ctx (&ctx, PUBKEY_OP_VERIFY,
1103 dsa_get_nbits (s_keyparms));
1104
1105 /* Extract the data. */
1106 rc = _gcry_pk_util_data_to_mpi (s_data, &data, &ctx);
1107 if (rc)
1108 goto leave;
1109 if (DBG_CIPHER)
1110 log_mpidump ("dsa_verify data", data);
1111
1112 /* Extract the signature value. */
1113 rc = _gcry_pk_util_preparse_sigval (s_sig, dsa_names, &l1, NULL);
1114 if (rc)
1115 goto leave;
1116 rc = _gcry_sexp_extract_param (l1, NULL, "rs", &sig_r, &sig_s, NULL);
1117 if (rc)
1118 goto leave;
1119 if (DBG_CIPHER)
1120 {
1121 log_mpidump ("dsa_verify s_r", sig_r);
1122 log_mpidump ("dsa_verify s_s", sig_s);
1123 }
1124
1125 /* Extract the key. */
1126 rc = _gcry_sexp_extract_param (s_keyparms, NULL, "pqgy",
1127 &pk.p, &pk.q, &pk.g, &pk.y, NULL);
1128 if (rc)
1129 goto leave;
1130 if (DBG_CIPHER)
1131 {
1132 log_mpidump ("dsa_verify p", pk.p);
1133 log_mpidump ("dsa_verify q", pk.q);
1134 log_mpidump ("dsa_verify g", pk.g);
1135 log_mpidump ("dsa_verify y", pk.y);
1136 }
1137
1138 /* Verify the signature. */
1139 rc = verify (sig_r, sig_s, data, &pk);
1140
1141 leave:
1142 _gcry_mpi_release (pk.p);
1143 _gcry_mpi_release (pk.q);
1144 _gcry_mpi_release (pk.g);
1145 _gcry_mpi_release (pk.y);
1146 _gcry_mpi_release (data);
1147 _gcry_mpi_release (sig_r);
1148 _gcry_mpi_release (sig_s);
1149 sexp_release (l1);
1150 _gcry_pk_util_free_encoding_ctx (&ctx);
1151 if (DBG_CIPHER)
1152 log_debug ("dsa_verify => %s\n", rc?gpg_strerror (rc):"Good");
1153 return rc;
1154 }
1155
1156
1157 /* Return the number of bits for the key described by PARMS. On error
1158 * 0 is returned. The format of PARMS starts with the algorithm name;
1159 * for example:
1160 *
1161 * (dsa
1162 * (p <mpi>)
1163 * (q <mpi>)
1164 * (g <mpi>)
1165 * (y <mpi>))
1166 *
1167 * More parameters may be given but we only need P here.
1168 */
1169 static unsigned int
dsa_get_nbits(gcry_sexp_t parms)1170 dsa_get_nbits (gcry_sexp_t parms)
1171 {
1172 gcry_sexp_t l1;
1173 gcry_mpi_t p;
1174 unsigned int nbits;
1175
1176 l1 = sexp_find_token (parms, "p", 1);
1177 if (!l1)
1178 return 0; /* Parameter P not found. */
1179
1180 p = sexp_nth_mpi (l1, 1, GCRYMPI_FMT_USG);
1181 sexp_release (l1);
1182 nbits = p? mpi_get_nbits (p) : 0;
1183 _gcry_mpi_release (p);
1184 return nbits;
1185 }
1186
1187
1188
1189 /*
1190 Self-test section.
1191 */
1192
1193 static const char *
selftest_sign(gcry_sexp_t pkey,gcry_sexp_t skey)1194 selftest_sign (gcry_sexp_t pkey, gcry_sexp_t skey)
1195 {
1196 /* Sample data from RFC 6979 section A.2.2, hash is of message "sample" */
1197 static const char sample_data[] =
1198 "(data (flags rfc6979)"
1199 " (hash sha256 #af2bdbe1aa9b6ec1e2ade1d694f41fc71a831d0268e9891562113d8a62add1bf#))";
1200 static const char sample_data_bad[] =
1201 "(data (flags rfc6979)"
1202 " (hash sha256 #bf2bdbe1aa9b6ec1e2ade1d694f41fc71a831d0268e9891562113d8a62add1bf#))";
1203 static const char signature_r[] =
1204 "eace8bdbbe353c432a795d9ec556c6d021f7a03f42c36e9bc87e4ac7932cc809";
1205 static const char signature_s[] =
1206 "7081e175455f9247b812b74583e9e94f9ea79bd640dc962533b0680793a38d53";
1207
1208 const char *errtxt = NULL;
1209 gcry_error_t err;
1210 gcry_sexp_t data = NULL;
1211 gcry_sexp_t data_bad = NULL;
1212 gcry_sexp_t sig = NULL;
1213 gcry_sexp_t l1 = NULL;
1214 gcry_sexp_t l2 = NULL;
1215 gcry_mpi_t r = NULL;
1216 gcry_mpi_t s = NULL;
1217 gcry_mpi_t calculated_r = NULL;
1218 gcry_mpi_t calculated_s = NULL;
1219 int cmp;
1220
1221 err = sexp_sscan (&data, NULL, sample_data, strlen (sample_data));
1222 if (!err)
1223 err = sexp_sscan (&data_bad, NULL,
1224 sample_data_bad, strlen (sample_data_bad));
1225 if (!err)
1226 err = _gcry_mpi_scan (&r, GCRYMPI_FMT_HEX, signature_r, 0, NULL);
1227 if (!err)
1228 err = _gcry_mpi_scan (&s, GCRYMPI_FMT_HEX, signature_s, 0, NULL);
1229
1230 if (err)
1231 {
1232 errtxt = "converting data failed";
1233 goto leave;
1234 }
1235
1236 err = _gcry_pk_sign (&sig, data, skey);
1237 if (err)
1238 {
1239 errtxt = "signing failed";
1240 goto leave;
1241 }
1242
1243 /* check against known signature */
1244 errtxt = "signature validity failed";
1245 l1 = _gcry_sexp_find_token (sig, "sig-val", 0);
1246 if (!l1)
1247 goto leave;
1248 l2 = _gcry_sexp_find_token (l1, "dsa", 0);
1249 if (!l2)
1250 goto leave;
1251
1252 sexp_release (l1);
1253 l1 = l2;
1254
1255 l2 = _gcry_sexp_find_token (l1, "r", 0);
1256 if (!l2)
1257 goto leave;
1258 calculated_r = _gcry_sexp_nth_mpi (l2, 1, GCRYMPI_FMT_USG);
1259 if (!calculated_r)
1260 goto leave;
1261
1262 sexp_release (l2);
1263 l2 = _gcry_sexp_find_token (l1, "s", 0);
1264 if (!l2)
1265 goto leave;
1266 calculated_s = _gcry_sexp_nth_mpi (l2, 1, GCRYMPI_FMT_USG);
1267 if (!calculated_s)
1268 goto leave;
1269
1270 errtxt = "known sig check failed";
1271
1272 cmp = _gcry_mpi_cmp (r, calculated_r);
1273 if (cmp)
1274 goto leave;
1275 cmp = _gcry_mpi_cmp (s, calculated_s);
1276 if (cmp)
1277 goto leave;
1278
1279 errtxt = NULL;
1280
1281
1282 err = _gcry_pk_verify (sig, data, pkey);
1283 if (err)
1284 {
1285 errtxt = "verify failed";
1286 goto leave;
1287 }
1288 err = _gcry_pk_verify (sig, data_bad, pkey);
1289 if (gcry_err_code (err) != GPG_ERR_BAD_SIGNATURE)
1290 {
1291 errtxt = "bad signature not detected";
1292 goto leave;
1293 }
1294
1295
1296 leave:
1297 _gcry_mpi_release (calculated_s);
1298 _gcry_mpi_release (calculated_r);
1299 _gcry_mpi_release (s);
1300 _gcry_mpi_release (r);
1301 sexp_release (l2);
1302 sexp_release (l1);
1303 sexp_release (sig);
1304 sexp_release (data_bad);
1305 sexp_release (data);
1306 return errtxt;
1307 }
1308
1309
1310 static gpg_err_code_t
selftests_dsa_2048(selftest_report_func_t report)1311 selftests_dsa_2048 (selftest_report_func_t report)
1312 {
1313 const char *what;
1314 const char *errtxt;
1315 gcry_error_t err;
1316 gcry_sexp_t skey = NULL;
1317 gcry_sexp_t pkey = NULL;
1318
1319 /* Convert the S-expressions into the internal representation. */
1320 what = "convert";
1321 err = sexp_sscan (&skey, NULL, sample_secret_key_2048, strlen (sample_secret_key_2048));
1322 if (!err)
1323 err = sexp_sscan (&pkey, NULL,
1324 sample_public_key_2048, strlen (sample_public_key_2048));
1325 if (err)
1326 {
1327 errtxt = _gcry_strerror (err);
1328 goto failed;
1329 }
1330
1331 what = "key consistency";
1332 err = _gcry_pk_testkey (skey);
1333 if (err)
1334 {
1335 errtxt = _gcry_strerror (err);
1336 goto failed;
1337 }
1338
1339 what = "sign";
1340 errtxt = selftest_sign (pkey, skey);
1341 if (errtxt)
1342 goto failed;
1343
1344 sexp_release (pkey);
1345 sexp_release (skey);
1346 return 0; /* Succeeded. */
1347
1348 failed:
1349 sexp_release (pkey);
1350 sexp_release (skey);
1351 if (report)
1352 report ("pubkey", GCRY_PK_DSA, what, errtxt);
1353 return GPG_ERR_SELFTEST_FAILED;
1354 }
1355
1356
1357 /* Run a full self-test for ALGO and return 0 on success. */
1358 static gpg_err_code_t
run_selftests(int algo,int extended,selftest_report_func_t report)1359 run_selftests (int algo, int extended, selftest_report_func_t report)
1360 {
1361 gpg_err_code_t ec;
1362
1363 (void)extended;
1364
1365 switch (algo)
1366 {
1367 case GCRY_PK_DSA:
1368 ec = selftests_dsa_2048 (report);
1369 break;
1370 default:
1371 ec = GPG_ERR_PUBKEY_ALGO;
1372 break;
1373
1374 }
1375 return ec;
1376 }
1377
1378
1379
1380 gcry_pk_spec_t _gcry_pubkey_spec_dsa =
1381 {
1382 GCRY_PK_DSA, { 0, 1 },
1383 GCRY_PK_USAGE_SIGN,
1384 "DSA", dsa_names,
1385 "pqgy", "pqgyx", "", "rs", "pqgy",
1386 dsa_generate,
1387 dsa_check_secret_key,
1388 NULL,
1389 NULL,
1390 dsa_sign,
1391 dsa_verify,
1392 dsa_get_nbits,
1393 run_selftests
1394 };
1395