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