Line data Source code
1 : /* Elgamal.c - Elgamal Public Key encryption
2 : * Copyright (C) 1998, 2000, 2001, 2002, 2003,
3 : * 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 : * For a description of the algorithm, see:
22 : * Bruce Schneier: Applied Cryptography. John Wiley & Sons, 1996.
23 : * ISBN 0-471-11709-9. Pages 476 ff.
24 : */
25 :
26 : #include <config.h>
27 : #include <stdio.h>
28 : #include <stdlib.h>
29 : #include <string.h>
30 : #include "g10lib.h"
31 : #include "mpi.h"
32 : #include "cipher.h"
33 : #include "pubkey-internal.h"
34 :
35 :
36 : /* Blinding is used to mitigate side-channel attacks. You may undef
37 : this to speed up the operation in case the system is secured
38 : against physical and network mounted side-channel attacks. */
39 : #define USE_BLINDING 1
40 :
41 :
42 : typedef struct
43 : {
44 : gcry_mpi_t p; /* prime */
45 : gcry_mpi_t g; /* group generator */
46 : gcry_mpi_t y; /* g^x mod p */
47 : } ELG_public_key;
48 :
49 :
50 : typedef struct
51 : {
52 : gcry_mpi_t p; /* prime */
53 : gcry_mpi_t g; /* group generator */
54 : gcry_mpi_t y; /* g^x mod p */
55 : gcry_mpi_t x; /* secret exponent */
56 : } ELG_secret_key;
57 :
58 :
59 : static const char *elg_names[] =
60 : {
61 : "elg",
62 : "openpgp-elg",
63 : "openpgp-elg-sig",
64 : NULL,
65 : };
66 :
67 :
68 : static int test_keys (ELG_secret_key *sk, unsigned int nbits, int nodie);
69 : static gcry_mpi_t gen_k (gcry_mpi_t p, int small_k);
70 : static gcry_err_code_t generate (ELG_secret_key *sk, unsigned nbits,
71 : gcry_mpi_t **factors);
72 : static int check_secret_key (ELG_secret_key *sk);
73 : static void do_encrypt (gcry_mpi_t a, gcry_mpi_t b, gcry_mpi_t input,
74 : ELG_public_key *pkey);
75 : static void decrypt (gcry_mpi_t output, gcry_mpi_t a, gcry_mpi_t b,
76 : ELG_secret_key *skey);
77 : static void sign (gcry_mpi_t a, gcry_mpi_t b, gcry_mpi_t input,
78 : ELG_secret_key *skey);
79 : static int verify (gcry_mpi_t a, gcry_mpi_t b, gcry_mpi_t input,
80 : ELG_public_key *pkey);
81 : static unsigned int elg_get_nbits (gcry_sexp_t parms);
82 :
83 :
84 : static void (*progress_cb) (void *, const char *, int, int, int);
85 : static void *progress_cb_data;
86 :
87 : void
88 0 : _gcry_register_pk_elg_progress (void (*cb) (void *, const char *,
89 : int, int, int),
90 : void *cb_data)
91 : {
92 0 : progress_cb = cb;
93 0 : progress_cb_data = cb_data;
94 0 : }
95 :
96 :
97 : static void
98 0 : progress (int c)
99 : {
100 0 : if (progress_cb)
101 0 : progress_cb (progress_cb_data, "pk_elg", c, 0, 0);
102 0 : }
103 :
104 :
105 : /****************
106 : * Michael Wiener's table on subgroup sizes to match field sizes.
107 : * (floating around somewhere, probably based on the paper from
108 : * Eurocrypt 96, page 332)
109 : */
110 : static unsigned int
111 0 : wiener_map( unsigned int n )
112 : {
113 : static struct { unsigned int p_n, q_n; } t[] =
114 : { /* p q attack cost */
115 : { 512, 119 }, /* 9 x 10^17 */
116 : { 768, 145 }, /* 6 x 10^21 */
117 : { 1024, 165 }, /* 7 x 10^24 */
118 : { 1280, 183 }, /* 3 x 10^27 */
119 : { 1536, 198 }, /* 7 x 10^29 */
120 : { 1792, 212 }, /* 9 x 10^31 */
121 : { 2048, 225 }, /* 8 x 10^33 */
122 : { 2304, 237 }, /* 5 x 10^35 */
123 : { 2560, 249 }, /* 3 x 10^37 */
124 : { 2816, 259 }, /* 1 x 10^39 */
125 : { 3072, 269 }, /* 3 x 10^40 */
126 : { 3328, 279 }, /* 8 x 10^41 */
127 : { 3584, 288 }, /* 2 x 10^43 */
128 : { 3840, 296 }, /* 4 x 10^44 */
129 : { 4096, 305 }, /* 7 x 10^45 */
130 : { 4352, 313 }, /* 1 x 10^47 */
131 : { 4608, 320 }, /* 2 x 10^48 */
132 : { 4864, 328 }, /* 2 x 10^49 */
133 : { 5120, 335 }, /* 3 x 10^50 */
134 : { 0, 0 }
135 : };
136 : int i;
137 :
138 0 : for(i=0; t[i].p_n; i++ )
139 : {
140 0 : if( n <= t[i].p_n )
141 0 : return t[i].q_n;
142 : }
143 : /* Not in table - use an arbitrary high number. */
144 0 : return n / 8 + 200;
145 : }
146 :
147 : static int
148 0 : test_keys ( ELG_secret_key *sk, unsigned int nbits, int nodie )
149 : {
150 : ELG_public_key pk;
151 0 : gcry_mpi_t test = mpi_new ( 0 );
152 0 : gcry_mpi_t out1_a = mpi_new ( nbits );
153 0 : gcry_mpi_t out1_b = mpi_new ( nbits );
154 0 : gcry_mpi_t out2 = mpi_new ( nbits );
155 0 : int failed = 0;
156 :
157 0 : pk.p = sk->p;
158 0 : pk.g = sk->g;
159 0 : pk.y = sk->y;
160 :
161 0 : _gcry_mpi_randomize ( test, nbits, GCRY_WEAK_RANDOM );
162 :
163 0 : do_encrypt ( out1_a, out1_b, test, &pk );
164 0 : decrypt ( out2, out1_a, out1_b, sk );
165 0 : if ( mpi_cmp( test, out2 ) )
166 0 : failed |= 1;
167 :
168 0 : sign ( out1_a, out1_b, test, sk );
169 0 : if ( !verify( out1_a, out1_b, test, &pk ) )
170 0 : failed |= 2;
171 :
172 0 : _gcry_mpi_release ( test );
173 0 : _gcry_mpi_release ( out1_a );
174 0 : _gcry_mpi_release ( out1_b );
175 0 : _gcry_mpi_release ( out2 );
176 :
177 0 : if (failed && !nodie)
178 0 : log_fatal ("Elgamal test key for %s %s failed\n",
179 0 : (failed & 1)? "encrypt+decrypt":"",
180 0 : (failed & 2)? "sign+verify":"");
181 0 : if (failed && DBG_CIPHER)
182 0 : log_debug ("Elgamal test key for %s %s failed\n",
183 0 : (failed & 1)? "encrypt+decrypt":"",
184 0 : (failed & 2)? "sign+verify":"");
185 :
186 0 : return failed;
187 : }
188 :
189 :
190 : /****************
191 : * Generate a random secret exponent k from prime p, so that k is
192 : * relatively prime to p-1. With SMALL_K set, k will be selected for
193 : * better encryption performance - this must never be used signing!
194 : */
195 : static gcry_mpi_t
196 0 : gen_k( gcry_mpi_t p, int small_k )
197 : {
198 0 : gcry_mpi_t k = mpi_alloc_secure( 0 );
199 0 : gcry_mpi_t temp = mpi_alloc( mpi_get_nlimbs(p) );
200 0 : gcry_mpi_t p_1 = mpi_copy(p);
201 0 : unsigned int orig_nbits = mpi_get_nbits(p);
202 : unsigned int nbits, nbytes;
203 0 : char *rndbuf = NULL;
204 :
205 0 : if (small_k)
206 : {
207 : /* Using a k much lesser than p is sufficient for encryption and
208 : * it greatly improves the encryption performance. We use
209 : * Wiener's table and add a large safety margin. */
210 0 : nbits = wiener_map( orig_nbits ) * 3 / 2;
211 0 : if( nbits >= orig_nbits )
212 0 : BUG();
213 : }
214 : else
215 0 : nbits = orig_nbits;
216 :
217 :
218 0 : nbytes = (nbits+7)/8;
219 0 : if( DBG_CIPHER )
220 0 : log_debug("choosing a random k\n");
221 0 : mpi_sub_ui( p_1, p, 1);
222 : for(;;)
223 : {
224 0 : if( !rndbuf || nbits < 32 )
225 : {
226 0 : xfree(rndbuf);
227 0 : rndbuf = _gcry_random_bytes_secure( nbytes, GCRY_STRONG_RANDOM );
228 : }
229 : else
230 : {
231 : /* Change only some of the higher bits. We could improve
232 : this by directly requesting more memory at the first call
233 : to get_random_bytes() and use this the here maybe it is
234 : easier to do this directly in random.c Anyway, it is
235 : highly inlikely that we will ever reach this code. */
236 0 : char *pp = _gcry_random_bytes_secure( 4, GCRY_STRONG_RANDOM );
237 0 : memcpy( rndbuf, pp, 4 );
238 0 : xfree(pp);
239 : }
240 0 : _gcry_mpi_set_buffer( k, rndbuf, nbytes, 0 );
241 :
242 : for(;;)
243 : {
244 0 : if( !(mpi_cmp( k, p_1 ) < 0) ) /* check: k < (p-1) */
245 : {
246 0 : if( DBG_CIPHER )
247 0 : progress('+');
248 0 : break; /* no */
249 : }
250 0 : if( !(mpi_cmp_ui( k, 0 ) > 0) ) /* check: k > 0 */
251 : {
252 0 : if( DBG_CIPHER )
253 0 : progress('-');
254 0 : break; /* no */
255 : }
256 0 : if (mpi_gcd( temp, k, p_1 ))
257 0 : goto found; /* okay, k is relative prime to (p-1) */
258 0 : mpi_add_ui( k, k, 1 );
259 0 : if( DBG_CIPHER )
260 0 : progress('.');
261 : }
262 : }
263 : found:
264 0 : xfree (rndbuf);
265 0 : if( DBG_CIPHER )
266 0 : progress('\n');
267 0 : mpi_free(p_1);
268 0 : mpi_free(temp);
269 :
270 0 : return k;
271 : }
272 :
273 : /****************
274 : * Generate a key pair with a key of size NBITS
275 : * Returns: 2 structures filled with all needed values
276 : * and an array with n-1 factors of (p-1)
277 : */
278 : static gcry_err_code_t
279 0 : generate ( ELG_secret_key *sk, unsigned int nbits, gcry_mpi_t **ret_factors )
280 : {
281 : gcry_err_code_t rc;
282 : gcry_mpi_t p; /* the prime */
283 : gcry_mpi_t p_min1;
284 : gcry_mpi_t g;
285 : gcry_mpi_t x; /* the secret exponent */
286 : gcry_mpi_t y;
287 : unsigned int qbits;
288 : unsigned int xbits;
289 : byte *rndbuf;
290 :
291 0 : p_min1 = mpi_new ( nbits );
292 0 : qbits = wiener_map( nbits );
293 0 : if( qbits & 1 ) /* better have a even one */
294 0 : qbits++;
295 0 : g = mpi_alloc(1);
296 0 : rc = _gcry_generate_elg_prime (0, nbits, qbits, g, &p, ret_factors);
297 0 : if (rc)
298 : {
299 0 : mpi_free (p_min1);
300 0 : mpi_free (g);
301 0 : return rc;
302 : }
303 0 : mpi_sub_ui(p_min1, p, 1);
304 :
305 :
306 : /* Select a random number which has these properties:
307 : * 0 < x < p-1
308 : * This must be a very good random number because this is the
309 : * secret part. The prime is public and may be shared anyway,
310 : * so a random generator level of 1 is used for the prime.
311 : *
312 : * I don't see a reason to have a x of about the same size
313 : * as the p. It should be sufficient to have one about the size
314 : * of q or the later used k plus a large safety margin. Decryption
315 : * will be much faster with such an x.
316 : */
317 0 : xbits = qbits * 3 / 2;
318 0 : if( xbits >= nbits )
319 0 : BUG();
320 0 : x = mpi_snew ( xbits );
321 0 : if( DBG_CIPHER )
322 0 : log_debug("choosing a random x of size %u\n", xbits );
323 0 : rndbuf = NULL;
324 : do
325 : {
326 0 : if( DBG_CIPHER )
327 0 : progress('.');
328 0 : if( rndbuf )
329 : { /* Change only some of the higher bits */
330 0 : if( xbits < 16 ) /* should never happen ... */
331 : {
332 0 : xfree(rndbuf);
333 0 : rndbuf = _gcry_random_bytes_secure ((xbits+7)/8,
334 : GCRY_VERY_STRONG_RANDOM);
335 : }
336 : else
337 : {
338 0 : char *r = _gcry_random_bytes_secure (2, GCRY_VERY_STRONG_RANDOM);
339 0 : memcpy(rndbuf, r, 2 );
340 0 : xfree (r);
341 : }
342 : }
343 : else
344 : {
345 0 : rndbuf = _gcry_random_bytes_secure ((xbits+7)/8,
346 : GCRY_VERY_STRONG_RANDOM );
347 : }
348 0 : _gcry_mpi_set_buffer( x, rndbuf, (xbits+7)/8, 0 );
349 0 : mpi_clear_highbit( x, xbits+1 );
350 : }
351 0 : while( !( mpi_cmp_ui( x, 0 )>0 && mpi_cmp( x, p_min1 )<0 ) );
352 0 : xfree(rndbuf);
353 :
354 0 : y = mpi_new (nbits);
355 0 : mpi_powm( y, g, x, p );
356 :
357 0 : if( DBG_CIPHER )
358 : {
359 0 : progress ('\n');
360 0 : log_mpidump ("elg p", p );
361 0 : log_mpidump ("elg g", g );
362 0 : log_mpidump ("elg y", y );
363 0 : log_mpidump ("elg x", x );
364 : }
365 :
366 : /* Copy the stuff to the key structures */
367 0 : sk->p = p;
368 0 : sk->g = g;
369 0 : sk->y = y;
370 0 : sk->x = x;
371 :
372 0 : _gcry_mpi_release ( p_min1 );
373 :
374 : /* Now we can test our keys (this should never fail!) */
375 0 : test_keys ( sk, nbits - 64, 0 );
376 :
377 0 : return 0;
378 : }
379 :
380 :
381 : /* Generate a key pair with a key of size NBITS not using a random
382 : value for the secret key but the one given as X. This is useful to
383 : implement a passphrase based decryption for a public key based
384 : encryption. It has appliactions in backup systems.
385 :
386 : Returns: A structure filled with all needed values and an array
387 : with n-1 factors of (p-1). */
388 : static gcry_err_code_t
389 0 : generate_using_x (ELG_secret_key *sk, unsigned int nbits, gcry_mpi_t x,
390 : gcry_mpi_t **ret_factors )
391 : {
392 : gcry_err_code_t rc;
393 : gcry_mpi_t p; /* The prime. */
394 : gcry_mpi_t p_min1; /* The prime minus 1. */
395 : gcry_mpi_t g; /* The generator. */
396 : gcry_mpi_t y; /* g^x mod p. */
397 : unsigned int qbits;
398 : unsigned int xbits;
399 :
400 0 : sk->p = NULL;
401 0 : sk->g = NULL;
402 0 : sk->y = NULL;
403 0 : sk->x = NULL;
404 :
405 : /* Do a quick check to see whether X is suitable. */
406 0 : xbits = mpi_get_nbits (x);
407 0 : if ( xbits < 64 || xbits >= nbits )
408 0 : return GPG_ERR_INV_VALUE;
409 :
410 0 : p_min1 = mpi_new ( nbits );
411 0 : qbits = wiener_map ( nbits );
412 0 : if ( (qbits & 1) ) /* Better have an even one. */
413 0 : qbits++;
414 0 : g = mpi_alloc (1);
415 0 : rc = _gcry_generate_elg_prime (0, nbits, qbits, g, &p, ret_factors );
416 0 : if (rc)
417 : {
418 0 : mpi_free (p_min1);
419 0 : mpi_free (g);
420 0 : return rc;
421 : }
422 0 : mpi_sub_ui (p_min1, p, 1);
423 :
424 0 : if (DBG_CIPHER)
425 0 : log_debug ("using a supplied x of size %u", xbits );
426 0 : if ( !(mpi_cmp_ui ( x, 0 ) > 0 && mpi_cmp ( x, p_min1 ) <0 ) )
427 : {
428 0 : _gcry_mpi_release ( p_min1 );
429 0 : _gcry_mpi_release ( p );
430 0 : _gcry_mpi_release ( g );
431 0 : return GPG_ERR_INV_VALUE;
432 : }
433 :
434 0 : y = mpi_new (nbits);
435 0 : mpi_powm ( y, g, x, p );
436 :
437 0 : if ( DBG_CIPHER )
438 : {
439 0 : progress ('\n');
440 0 : log_mpidump ("elg p", p );
441 0 : log_mpidump ("elg g", g );
442 0 : log_mpidump ("elg y", y );
443 0 : log_mpidump ("elg x", x );
444 : }
445 :
446 : /* Copy the stuff to the key structures */
447 0 : sk->p = p;
448 0 : sk->g = g;
449 0 : sk->y = y;
450 0 : sk->x = mpi_copy (x);
451 :
452 0 : _gcry_mpi_release ( p_min1 );
453 :
454 : /* Now we can test our keys. */
455 0 : if ( test_keys ( sk, nbits - 64, 1 ) )
456 : {
457 0 : _gcry_mpi_release ( sk->p ); sk->p = NULL;
458 0 : _gcry_mpi_release ( sk->g ); sk->g = NULL;
459 0 : _gcry_mpi_release ( sk->y ); sk->y = NULL;
460 0 : _gcry_mpi_release ( sk->x ); sk->x = NULL;
461 0 : return GPG_ERR_BAD_SECKEY;
462 : }
463 :
464 0 : return 0;
465 : }
466 :
467 :
468 : /****************
469 : * Test whether the secret key is valid.
470 : * Returns: if this is a valid key.
471 : */
472 : static int
473 0 : check_secret_key( ELG_secret_key *sk )
474 : {
475 : int rc;
476 0 : gcry_mpi_t y = mpi_alloc( mpi_get_nlimbs(sk->y) );
477 :
478 0 : mpi_powm (y, sk->g, sk->x, sk->p);
479 0 : rc = !mpi_cmp( y, sk->y );
480 0 : mpi_free( y );
481 0 : return rc;
482 : }
483 :
484 :
485 : static void
486 0 : do_encrypt(gcry_mpi_t a, gcry_mpi_t b, gcry_mpi_t input, ELG_public_key *pkey )
487 : {
488 : gcry_mpi_t k;
489 :
490 : /* Note: maybe we should change the interface, so that it
491 : * is possible to check that input is < p and return an
492 : * error code.
493 : */
494 :
495 0 : k = gen_k( pkey->p, 1 );
496 0 : mpi_powm (a, pkey->g, k, pkey->p);
497 :
498 : /* b = (y^k * input) mod p
499 : * = ((y^k mod p) * (input mod p)) mod p
500 : * and because input is < p
501 : * = ((y^k mod p) * input) mod p
502 : */
503 0 : mpi_powm (b, pkey->y, k, pkey->p);
504 0 : mpi_mulm (b, b, input, pkey->p);
505 : #if 0
506 : if( DBG_CIPHER )
507 : {
508 : log_mpidump("elg encrypted y", pkey->y);
509 : log_mpidump("elg encrypted p", pkey->p);
510 : log_mpidump("elg encrypted k", k);
511 : log_mpidump("elg encrypted M", input);
512 : log_mpidump("elg encrypted a", a);
513 : log_mpidump("elg encrypted b", b);
514 : }
515 : #endif
516 0 : mpi_free(k);
517 0 : }
518 :
519 :
520 :
521 :
522 : static void
523 0 : decrypt (gcry_mpi_t output, gcry_mpi_t a, gcry_mpi_t b, ELG_secret_key *skey )
524 : {
525 : gcry_mpi_t t1, t2, r;
526 0 : unsigned int nbits = mpi_get_nbits (skey->p);
527 :
528 0 : mpi_normalize (a);
529 0 : mpi_normalize (b);
530 :
531 0 : t1 = mpi_snew (nbits);
532 :
533 : #ifdef USE_BLINDING
534 :
535 0 : t2 = mpi_snew (nbits);
536 0 : r = mpi_new (nbits);
537 :
538 : /* We need a random number of about the prime size. The random
539 : number merely needs to be unpredictable; thus we use level 0. */
540 0 : _gcry_mpi_randomize (r, nbits, GCRY_WEAK_RANDOM);
541 :
542 : /* t1 = r^x mod p */
543 0 : mpi_powm (t1, r, skey->x, skey->p);
544 : /* t2 = (a * r)^-x mod p */
545 0 : mpi_mulm (t2, a, r, skey->p);
546 0 : mpi_powm (t2, t2, skey->x, skey->p);
547 0 : mpi_invm (t2, t2, skey->p);
548 : /* t1 = (t1 * t2) mod p*/
549 0 : mpi_mulm (t1, t1, t2, skey->p);
550 :
551 0 : mpi_free (r);
552 0 : mpi_free (t2);
553 :
554 : #else /*!USE_BLINDING*/
555 :
556 : /* output = b/(a^x) mod p */
557 : mpi_powm (t1, a, skey->x, skey->p);
558 : mpi_invm (t1, t1, skey->p);
559 :
560 : #endif /*!USE_BLINDING*/
561 :
562 0 : mpi_mulm (output, b, t1, skey->p);
563 :
564 : #if 0
565 : if( DBG_CIPHER )
566 : {
567 : log_mpidump ("elg decrypted x", skey->x);
568 : log_mpidump ("elg decrypted p", skey->p);
569 : log_mpidump ("elg decrypted a", a);
570 : log_mpidump ("elg decrypted b", b);
571 : log_mpidump ("elg decrypted M", output);
572 : }
573 : #endif
574 0 : mpi_free (t1);
575 0 : }
576 :
577 :
578 : /****************
579 : * Make an Elgamal signature out of INPUT
580 : */
581 :
582 : static void
583 0 : sign(gcry_mpi_t a, gcry_mpi_t b, gcry_mpi_t input, ELG_secret_key *skey )
584 : {
585 : gcry_mpi_t k;
586 0 : gcry_mpi_t t = mpi_alloc( mpi_get_nlimbs(a) );
587 0 : gcry_mpi_t inv = mpi_alloc( mpi_get_nlimbs(a) );
588 0 : gcry_mpi_t p_1 = mpi_copy(skey->p);
589 :
590 : /*
591 : * b = (t * inv) mod (p-1)
592 : * b = (t * inv(k,(p-1),(p-1)) mod (p-1)
593 : * b = (((M-x*a) mod (p-1)) * inv(k,(p-1),(p-1))) mod (p-1)
594 : *
595 : */
596 0 : mpi_sub_ui(p_1, p_1, 1);
597 0 : k = gen_k( skey->p, 0 /* no small K ! */ );
598 0 : mpi_powm( a, skey->g, k, skey->p );
599 0 : mpi_mul(t, skey->x, a );
600 0 : mpi_subm(t, input, t, p_1 );
601 0 : mpi_invm(inv, k, p_1 );
602 0 : mpi_mulm(b, t, inv, p_1 );
603 :
604 : #if 0
605 : if( DBG_CIPHER )
606 : {
607 : log_mpidump ("elg sign p", skey->p);
608 : log_mpidump ("elg sign g", skey->g);
609 : log_mpidump ("elg sign y", skey->y);
610 : log_mpidump ("elg sign x", skey->x);
611 : log_mpidump ("elg sign k", k);
612 : log_mpidump ("elg sign M", input);
613 : log_mpidump ("elg sign a", a);
614 : log_mpidump ("elg sign b", b);
615 : }
616 : #endif
617 0 : mpi_free(k);
618 0 : mpi_free(t);
619 0 : mpi_free(inv);
620 0 : mpi_free(p_1);
621 0 : }
622 :
623 :
624 : /****************
625 : * Returns true if the signature composed of A and B is valid.
626 : */
627 : static int
628 0 : verify(gcry_mpi_t a, gcry_mpi_t b, gcry_mpi_t input, ELG_public_key *pkey )
629 : {
630 : int rc;
631 : gcry_mpi_t t1;
632 : gcry_mpi_t t2;
633 : gcry_mpi_t base[4];
634 : gcry_mpi_t ex[4];
635 :
636 0 : if( !(mpi_cmp_ui( a, 0 ) > 0 && mpi_cmp( a, pkey->p ) < 0) )
637 0 : return 0; /* assertion 0 < a < p failed */
638 :
639 0 : t1 = mpi_alloc( mpi_get_nlimbs(a) );
640 0 : t2 = mpi_alloc( mpi_get_nlimbs(a) );
641 :
642 : #if 0
643 : /* t1 = (y^a mod p) * (a^b mod p) mod p */
644 : gcry_mpi_powm( t1, pkey->y, a, pkey->p );
645 : gcry_mpi_powm( t2, a, b, pkey->p );
646 : mpi_mulm( t1, t1, t2, pkey->p );
647 :
648 : /* t2 = g ^ input mod p */
649 : gcry_mpi_powm( t2, pkey->g, input, pkey->p );
650 :
651 : rc = !mpi_cmp( t1, t2 );
652 : #elif 0
653 : /* t1 = (y^a mod p) * (a^b mod p) mod p */
654 : base[0] = pkey->y; ex[0] = a;
655 : base[1] = a; ex[1] = b;
656 : base[2] = NULL; ex[2] = NULL;
657 : mpi_mulpowm( t1, base, ex, pkey->p );
658 :
659 : /* t2 = g ^ input mod p */
660 : gcry_mpi_powm( t2, pkey->g, input, pkey->p );
661 :
662 : rc = !mpi_cmp( t1, t2 );
663 : #else
664 : /* t1 = g ^ - input * y ^ a * a ^ b mod p */
665 0 : mpi_invm(t2, pkey->g, pkey->p );
666 0 : base[0] = t2 ; ex[0] = input;
667 0 : base[1] = pkey->y; ex[1] = a;
668 0 : base[2] = a; ex[2] = b;
669 0 : base[3] = NULL; ex[3] = NULL;
670 0 : mpi_mulpowm( t1, base, ex, pkey->p );
671 0 : rc = !mpi_cmp_ui( t1, 1 );
672 :
673 : #endif
674 :
675 0 : mpi_free(t1);
676 0 : mpi_free(t2);
677 0 : return rc;
678 : }
679 :
680 : /*********************************************
681 : ************** interface ******************
682 : *********************************************/
683 :
684 : static gpg_err_code_t
685 0 : elg_generate (const gcry_sexp_t genparms, gcry_sexp_t *r_skey)
686 : {
687 : gpg_err_code_t rc;
688 : unsigned int nbits;
689 : ELG_secret_key sk;
690 0 : gcry_mpi_t xvalue = NULL;
691 : gcry_sexp_t l1;
692 0 : gcry_mpi_t *factors = NULL;
693 0 : gcry_sexp_t misc_info = NULL;
694 :
695 0 : memset (&sk, 0, sizeof sk);
696 :
697 0 : rc = _gcry_pk_util_get_nbits (genparms, &nbits);
698 0 : if (rc)
699 0 : return rc;
700 :
701 : /* Parse the optional xvalue element. */
702 0 : l1 = sexp_find_token (genparms, "xvalue", 0);
703 0 : if (l1)
704 : {
705 0 : xvalue = sexp_nth_mpi (l1, 1, 0);
706 0 : sexp_release (l1);
707 0 : if (!xvalue)
708 0 : return GPG_ERR_BAD_MPI;
709 : }
710 :
711 0 : if (xvalue)
712 : {
713 0 : rc = generate_using_x (&sk, nbits, xvalue, &factors);
714 0 : mpi_free (xvalue);
715 : }
716 : else
717 : {
718 0 : rc = generate (&sk, nbits, &factors);
719 : }
720 0 : if (rc)
721 0 : goto leave;
722 :
723 0 : if (factors && factors[0])
724 : {
725 : int nfac;
726 : void **arg_list;
727 : char *buffer, *p;
728 :
729 0 : for (nfac = 0; factors[nfac]; nfac++)
730 : ;
731 0 : arg_list = xtrycalloc (nfac+1, sizeof *arg_list);
732 0 : if (!arg_list)
733 : {
734 0 : rc = gpg_err_code_from_syserror ();
735 0 : goto leave;
736 : }
737 0 : buffer = xtrymalloc (30 + nfac*2 + 2 + 1);
738 0 : if (!buffer)
739 : {
740 0 : rc = gpg_err_code_from_syserror ();
741 0 : xfree (arg_list);
742 0 : goto leave;
743 : }
744 0 : p = stpcpy (buffer, "(misc-key-info(pm1-factors");
745 0 : for(nfac = 0; factors[nfac]; nfac++)
746 : {
747 0 : p = stpcpy (p, "%m");
748 0 : arg_list[nfac] = factors + nfac;
749 : }
750 0 : p = stpcpy (p, "))");
751 0 : rc = sexp_build_array (&misc_info, NULL, buffer, arg_list);
752 0 : xfree (arg_list);
753 0 : xfree (buffer);
754 0 : if (rc)
755 0 : goto leave;
756 : }
757 :
758 0 : rc = sexp_build (r_skey, NULL,
759 : "(key-data"
760 : " (public-key"
761 : " (elg(p%m)(g%m)(y%m)))"
762 : " (private-key"
763 : " (elg(p%m)(g%m)(y%m)(x%m)))"
764 : " %S)",
765 : sk.p, sk.g, sk.y,
766 : sk.p, sk.g, sk.y, sk.x,
767 : misc_info);
768 :
769 : leave:
770 0 : mpi_free (sk.p);
771 0 : mpi_free (sk.g);
772 0 : mpi_free (sk.y);
773 0 : mpi_free (sk.x);
774 0 : sexp_release (misc_info);
775 0 : if (factors)
776 : {
777 : gcry_mpi_t *mp;
778 0 : for (mp = factors; *mp; mp++)
779 0 : mpi_free (*mp);
780 0 : xfree (factors);
781 : }
782 :
783 0 : return rc;
784 : }
785 :
786 :
787 : static gcry_err_code_t
788 0 : elg_check_secret_key (gcry_sexp_t keyparms)
789 : {
790 : gcry_err_code_t rc;
791 0 : ELG_secret_key sk = {NULL, NULL, NULL, NULL};
792 :
793 0 : rc = sexp_extract_param (keyparms, NULL, "pgyx",
794 : &sk.p, &sk.g, &sk.y, &sk.x,
795 : NULL);
796 0 : if (rc)
797 0 : goto leave;
798 :
799 0 : if (!check_secret_key (&sk))
800 0 : rc = GPG_ERR_BAD_SECKEY;
801 :
802 : leave:
803 0 : _gcry_mpi_release (sk.p);
804 0 : _gcry_mpi_release (sk.g);
805 0 : _gcry_mpi_release (sk.y);
806 0 : _gcry_mpi_release (sk.x);
807 0 : if (DBG_CIPHER)
808 0 : log_debug ("elg_testkey => %s\n", gpg_strerror (rc));
809 0 : return rc;
810 : }
811 :
812 :
813 : static gcry_err_code_t
814 0 : elg_encrypt (gcry_sexp_t *r_ciph, gcry_sexp_t s_data, gcry_sexp_t keyparms)
815 : {
816 : gcry_err_code_t rc;
817 : struct pk_encoding_ctx ctx;
818 0 : gcry_mpi_t mpi_a = NULL;
819 0 : gcry_mpi_t mpi_b = NULL;
820 0 : gcry_mpi_t data = NULL;
821 0 : ELG_public_key pk = { NULL, NULL, NULL };
822 :
823 0 : _gcry_pk_util_init_encoding_ctx (&ctx, PUBKEY_OP_ENCRYPT,
824 : elg_get_nbits (keyparms));
825 :
826 : /* Extract the data. */
827 0 : rc = _gcry_pk_util_data_to_mpi (s_data, &data, &ctx);
828 0 : if (rc)
829 0 : goto leave;
830 0 : if (DBG_CIPHER)
831 0 : log_mpidump ("elg_encrypt data", data);
832 0 : if (mpi_is_opaque (data))
833 : {
834 0 : rc = GPG_ERR_INV_DATA;
835 0 : goto leave;
836 : }
837 :
838 : /* Extract the key. */
839 0 : rc = sexp_extract_param (keyparms, NULL, "pgy",
840 : &pk.p, &pk.g, &pk.y, NULL);
841 0 : if (rc)
842 0 : goto leave;
843 0 : if (DBG_CIPHER)
844 : {
845 0 : log_mpidump ("elg_encrypt p", pk.p);
846 0 : log_mpidump ("elg_encrypt g", pk.g);
847 0 : log_mpidump ("elg_encrypt y", pk.y);
848 : }
849 :
850 : /* Do Elgamal computation and build result. */
851 0 : mpi_a = mpi_new (0);
852 0 : mpi_b = mpi_new (0);
853 0 : do_encrypt (mpi_a, mpi_b, data, &pk);
854 0 : rc = sexp_build (r_ciph, NULL, "(enc-val(elg(a%m)(b%m)))", mpi_a, mpi_b);
855 :
856 : leave:
857 0 : _gcry_mpi_release (mpi_a);
858 0 : _gcry_mpi_release (mpi_b);
859 0 : _gcry_mpi_release (pk.p);
860 0 : _gcry_mpi_release (pk.g);
861 0 : _gcry_mpi_release (pk.y);
862 0 : _gcry_mpi_release (data);
863 0 : _gcry_pk_util_free_encoding_ctx (&ctx);
864 0 : if (DBG_CIPHER)
865 0 : log_debug ("elg_encrypt => %s\n", gpg_strerror (rc));
866 0 : return rc;
867 : }
868 :
869 :
870 : static gcry_err_code_t
871 0 : elg_decrypt (gcry_sexp_t *r_plain, gcry_sexp_t s_data, gcry_sexp_t keyparms)
872 : {
873 : gpg_err_code_t rc;
874 : struct pk_encoding_ctx ctx;
875 0 : gcry_sexp_t l1 = NULL;
876 0 : gcry_mpi_t data_a = NULL;
877 0 : gcry_mpi_t data_b = NULL;
878 0 : ELG_secret_key sk = {NULL, NULL, NULL, NULL};
879 0 : gcry_mpi_t plain = NULL;
880 0 : unsigned char *unpad = NULL;
881 0 : size_t unpadlen = 0;
882 :
883 0 : _gcry_pk_util_init_encoding_ctx (&ctx, PUBKEY_OP_DECRYPT,
884 : elg_get_nbits (keyparms));
885 :
886 : /* Extract the data. */
887 0 : rc = _gcry_pk_util_preparse_encval (s_data, elg_names, &l1, &ctx);
888 0 : if (rc)
889 0 : goto leave;
890 0 : rc = sexp_extract_param (l1, NULL, "ab", &data_a, &data_b, NULL);
891 0 : if (rc)
892 0 : goto leave;
893 0 : if (DBG_CIPHER)
894 : {
895 0 : log_printmpi ("elg_decrypt d_a", data_a);
896 0 : log_printmpi ("elg_decrypt d_b", data_b);
897 : }
898 0 : if (mpi_is_opaque (data_a) || mpi_is_opaque (data_b))
899 : {
900 0 : rc = GPG_ERR_INV_DATA;
901 0 : goto leave;
902 : }
903 :
904 : /* Extract the key. */
905 0 : rc = sexp_extract_param (keyparms, NULL, "pgyx",
906 : &sk.p, &sk.g, &sk.y, &sk.x,
907 : NULL);
908 0 : if (rc)
909 0 : goto leave;
910 0 : if (DBG_CIPHER)
911 : {
912 0 : log_printmpi ("elg_decrypt p", sk.p);
913 0 : log_printmpi ("elg_decrypt g", sk.g);
914 0 : log_printmpi ("elg_decrypt y", sk.y);
915 0 : if (!fips_mode ())
916 0 : log_printmpi ("elg_decrypt x", sk.x);
917 : }
918 :
919 0 : plain = mpi_snew (ctx.nbits);
920 0 : decrypt (plain, data_a, data_b, &sk);
921 0 : if (DBG_CIPHER)
922 0 : log_printmpi ("elg_decrypt res", plain);
923 :
924 : /* Reverse the encoding and build the s-expression. */
925 0 : switch (ctx.encoding)
926 : {
927 : case PUBKEY_ENC_PKCS1:
928 0 : rc = _gcry_rsa_pkcs1_decode_for_enc (&unpad, &unpadlen, ctx.nbits, plain);
929 0 : mpi_free (plain); plain = NULL;
930 0 : if (!rc)
931 0 : rc = sexp_build (r_plain, NULL, "(value %b)", (int)unpadlen, unpad);
932 0 : break;
933 :
934 : case PUBKEY_ENC_OAEP:
935 0 : rc = _gcry_rsa_oaep_decode (&unpad, &unpadlen,
936 : ctx.nbits, ctx.hash_algo, plain,
937 0 : ctx.label, ctx.labellen);
938 0 : mpi_free (plain); plain = NULL;
939 0 : if (!rc)
940 0 : rc = sexp_build (r_plain, NULL, "(value %b)", (int)unpadlen, unpad);
941 0 : break;
942 :
943 : default:
944 : /* Raw format. For backward compatibility we need to assume a
945 : signed mpi by using the sexp format string "%m". */
946 0 : rc = sexp_build (r_plain, NULL,
947 0 : (ctx.flags & PUBKEY_FLAG_LEGACYRESULT)
948 : ? "%m" : "(value %m)",
949 : plain);
950 0 : break;
951 : }
952 :
953 :
954 : leave:
955 0 : xfree (unpad);
956 0 : _gcry_mpi_release (plain);
957 0 : _gcry_mpi_release (sk.p);
958 0 : _gcry_mpi_release (sk.g);
959 0 : _gcry_mpi_release (sk.y);
960 0 : _gcry_mpi_release (sk.x);
961 0 : _gcry_mpi_release (data_a);
962 0 : _gcry_mpi_release (data_b);
963 0 : sexp_release (l1);
964 0 : _gcry_pk_util_free_encoding_ctx (&ctx);
965 0 : if (DBG_CIPHER)
966 0 : log_debug ("elg_decrypt => %s\n", gpg_strerror (rc));
967 0 : return rc;
968 : }
969 :
970 :
971 : static gcry_err_code_t
972 0 : elg_sign (gcry_sexp_t *r_sig, gcry_sexp_t s_data, gcry_sexp_t keyparms)
973 : {
974 : gcry_err_code_t rc;
975 : struct pk_encoding_ctx ctx;
976 0 : gcry_mpi_t data = NULL;
977 0 : ELG_secret_key sk = {NULL, NULL, NULL, NULL};
978 0 : gcry_mpi_t sig_r = NULL;
979 0 : gcry_mpi_t sig_s = NULL;
980 :
981 0 : _gcry_pk_util_init_encoding_ctx (&ctx, PUBKEY_OP_SIGN,
982 : elg_get_nbits (keyparms));
983 :
984 : /* Extract the data. */
985 0 : rc = _gcry_pk_util_data_to_mpi (s_data, &data, &ctx);
986 0 : if (rc)
987 0 : goto leave;
988 0 : if (DBG_CIPHER)
989 0 : log_mpidump ("elg_sign data", data);
990 0 : if (mpi_is_opaque (data))
991 : {
992 0 : rc = GPG_ERR_INV_DATA;
993 0 : goto leave;
994 : }
995 :
996 : /* Extract the key. */
997 0 : rc = sexp_extract_param (keyparms, NULL, "pgyx",
998 : &sk.p, &sk.g, &sk.y, &sk.x, NULL);
999 0 : if (rc)
1000 0 : goto leave;
1001 0 : if (DBG_CIPHER)
1002 : {
1003 0 : log_mpidump ("elg_sign p", sk.p);
1004 0 : log_mpidump ("elg_sign g", sk.g);
1005 0 : log_mpidump ("elg_sign y", sk.y);
1006 0 : if (!fips_mode ())
1007 0 : log_mpidump ("elg_sign x", sk.x);
1008 : }
1009 :
1010 0 : sig_r = mpi_new (0);
1011 0 : sig_s = mpi_new (0);
1012 0 : sign (sig_r, sig_s, data, &sk);
1013 0 : if (DBG_CIPHER)
1014 : {
1015 0 : log_mpidump ("elg_sign sig_r", sig_r);
1016 0 : log_mpidump ("elg_sign sig_s", sig_s);
1017 : }
1018 0 : rc = sexp_build (r_sig, NULL, "(sig-val(elg(r%M)(s%M)))", sig_r, sig_s);
1019 :
1020 : leave:
1021 0 : _gcry_mpi_release (sig_r);
1022 0 : _gcry_mpi_release (sig_s);
1023 0 : _gcry_mpi_release (sk.p);
1024 0 : _gcry_mpi_release (sk.g);
1025 0 : _gcry_mpi_release (sk.y);
1026 0 : _gcry_mpi_release (sk.x);
1027 0 : _gcry_mpi_release (data);
1028 0 : _gcry_pk_util_free_encoding_ctx (&ctx);
1029 0 : if (DBG_CIPHER)
1030 0 : log_debug ("elg_sign => %s\n", gpg_strerror (rc));
1031 0 : return rc;
1032 : }
1033 :
1034 :
1035 : static gcry_err_code_t
1036 0 : elg_verify (gcry_sexp_t s_sig, gcry_sexp_t s_data, gcry_sexp_t s_keyparms)
1037 : {
1038 : gcry_err_code_t rc;
1039 : struct pk_encoding_ctx ctx;
1040 0 : gcry_sexp_t l1 = NULL;
1041 0 : gcry_mpi_t sig_r = NULL;
1042 0 : gcry_mpi_t sig_s = NULL;
1043 0 : gcry_mpi_t data = NULL;
1044 0 : ELG_public_key pk = { NULL, NULL, NULL };
1045 :
1046 0 : _gcry_pk_util_init_encoding_ctx (&ctx, PUBKEY_OP_VERIFY,
1047 : elg_get_nbits (s_keyparms));
1048 :
1049 : /* Extract the data. */
1050 0 : rc = _gcry_pk_util_data_to_mpi (s_data, &data, &ctx);
1051 0 : if (rc)
1052 0 : goto leave;
1053 0 : if (DBG_CIPHER)
1054 0 : log_mpidump ("elg_verify data", data);
1055 0 : if (mpi_is_opaque (data))
1056 : {
1057 0 : rc = GPG_ERR_INV_DATA;
1058 0 : goto leave;
1059 : }
1060 :
1061 : /* Extract the signature value. */
1062 0 : rc = _gcry_pk_util_preparse_sigval (s_sig, elg_names, &l1, NULL);
1063 0 : if (rc)
1064 0 : goto leave;
1065 0 : rc = sexp_extract_param (l1, NULL, "rs", &sig_r, &sig_s, NULL);
1066 0 : if (rc)
1067 0 : goto leave;
1068 0 : if (DBG_CIPHER)
1069 : {
1070 0 : log_mpidump ("elg_verify s_r", sig_r);
1071 0 : log_mpidump ("elg_verify s_s", sig_s);
1072 : }
1073 :
1074 : /* Extract the key. */
1075 0 : rc = sexp_extract_param (s_keyparms, NULL, "pgy",
1076 : &pk.p, &pk.g, &pk.y, NULL);
1077 0 : if (rc)
1078 0 : goto leave;
1079 0 : if (DBG_CIPHER)
1080 : {
1081 0 : log_mpidump ("elg_verify p", pk.p);
1082 0 : log_mpidump ("elg_verify g", pk.g);
1083 0 : log_mpidump ("elg_verify y", pk.y);
1084 : }
1085 :
1086 : /* Verify the signature. */
1087 0 : if (!verify (sig_r, sig_s, data, &pk))
1088 0 : rc = GPG_ERR_BAD_SIGNATURE;
1089 :
1090 : leave:
1091 0 : _gcry_mpi_release (pk.p);
1092 0 : _gcry_mpi_release (pk.g);
1093 0 : _gcry_mpi_release (pk.y);
1094 0 : _gcry_mpi_release (data);
1095 0 : _gcry_mpi_release (sig_r);
1096 0 : _gcry_mpi_release (sig_s);
1097 0 : sexp_release (l1);
1098 0 : _gcry_pk_util_free_encoding_ctx (&ctx);
1099 0 : if (DBG_CIPHER)
1100 0 : log_debug ("elg_verify => %s\n", rc?gpg_strerror (rc):"Good");
1101 0 : return rc;
1102 : }
1103 :
1104 :
1105 : /* Return the number of bits for the key described by PARMS. On error
1106 : * 0 is returned. The format of PARMS starts with the algorithm name;
1107 : * for example:
1108 : *
1109 : * (dsa
1110 : * (p <mpi>)
1111 : * (g <mpi>)
1112 : * (y <mpi>))
1113 : *
1114 : * More parameters may be given but we only need P here.
1115 : */
1116 : static unsigned int
1117 0 : elg_get_nbits (gcry_sexp_t parms)
1118 : {
1119 : gcry_sexp_t l1;
1120 : gcry_mpi_t p;
1121 : unsigned int nbits;
1122 :
1123 0 : l1 = sexp_find_token (parms, "p", 1);
1124 0 : if (!l1)
1125 0 : return 0; /* Parameter P not found. */
1126 :
1127 0 : p= sexp_nth_mpi (l1, 1, GCRYMPI_FMT_USG);
1128 0 : sexp_release (l1);
1129 0 : nbits = p? mpi_get_nbits (p) : 0;
1130 0 : _gcry_mpi_release (p);
1131 0 : return nbits;
1132 : }
1133 :
1134 :
1135 :
1136 : gcry_pk_spec_t _gcry_pubkey_spec_elg =
1137 : {
1138 : GCRY_PK_ELG, { 0, 0 },
1139 : (GCRY_PK_USAGE_SIGN | GCRY_PK_USAGE_ENCR),
1140 : "ELG", elg_names,
1141 : "pgy", "pgyx", "ab", "rs", "pgy",
1142 : elg_generate,
1143 : elg_check_secret_key,
1144 : elg_encrypt,
1145 : elg_decrypt,
1146 : elg_sign,
1147 : elg_verify,
1148 : elg_get_nbits,
1149 : };
|
