1 /* This file was automatically imported with
2 import_gcry.py. Please don't modify it */
3 /* Elgamal.c - Elgamal Public Key encryption
4 * Copyright (C) 1998, 2000, 2001, 2002, 2003,
5 * 2008 Free Software Foundation, Inc.
7 * This file is part of Libgcrypt.
9 * Libgcrypt is free software; you can redistribute it and/or modify
10 * it under the terms of the GNU Lesser General Public License as
11 * published by the Free Software Foundation; either version 2.1 of
12 * the License, or (at your option) any later version.
14 * Libgcrypt is distributed in the hope that it will be useful,
15 * but WITHOUT ANY WARRANTY; without even the implied warranty of
16 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17 * GNU Lesser General Public License for more details.
19 * You should have received a copy of the GNU Lesser General Public
20 * License along with this program; if not, see <http://www.gnu.org/licenses/>.
22 * For a description of the algorithm, see:
23 * Bruce Schneier: Applied Cryptography. John Wiley & Sons, 1996.
24 * ISBN 0-471-11709-9. Pages 476 ff.
33 gcry_mpi_t p
; /* prime */
34 gcry_mpi_t g
; /* group generator */
35 gcry_mpi_t y
; /* g^x mod p */
41 gcry_mpi_t p
; /* prime */
42 gcry_mpi_t g
; /* group generator */
43 gcry_mpi_t y
; /* g^x mod p */
44 gcry_mpi_t x
; /* secret exponent */
48 static int test_keys (ELG_secret_key
*sk
, unsigned int nbits
, int nodie
);
49 static gcry_mpi_t
gen_k (gcry_mpi_t p
, int small_k
);
50 static void generate (ELG_secret_key
*sk
, unsigned nbits
, gcry_mpi_t
**factors
);
51 static int check_secret_key (ELG_secret_key
*sk
);
52 static void do_encrypt (gcry_mpi_t a
, gcry_mpi_t b
, gcry_mpi_t input
,
53 ELG_public_key
*pkey
);
54 static void decrypt (gcry_mpi_t output
, gcry_mpi_t a
, gcry_mpi_t b
,
55 ELG_secret_key
*skey
);
56 static void sign (gcry_mpi_t a
, gcry_mpi_t b
, gcry_mpi_t input
,
57 ELG_secret_key
*skey
);
58 static int verify (gcry_mpi_t a
, gcry_mpi_t b
, gcry_mpi_t input
,
59 ELG_public_key
*pkey
);
62 static void (*progress_cb
) (void *, const char *, int, int, int);
63 static void *progress_cb_data
;
66 _gcry_register_pk_elg_progress (void (*cb
) (void *, const char *,
71 progress_cb_data
= cb_data
;
79 progress_cb (progress_cb_data
, "pk_elg", c
, 0, 0);
84 * Michael Wiener's table on subgroup sizes to match field sizes.
85 * (floating around somewhere, probably based on the paper from
86 * Eurocrypt 96, page 332)
89 wiener_map( unsigned int n
)
91 static struct { unsigned int p_n
, q_n
; } t
[] =
92 { /* p q attack cost */
93 { 512, 119 }, /* 9 x 10^17 */
94 { 768, 145 }, /* 6 x 10^21 */
95 { 1024, 165 }, /* 7 x 10^24 */
96 { 1280, 183 }, /* 3 x 10^27 */
97 { 1536, 198 }, /* 7 x 10^29 */
98 { 1792, 212 }, /* 9 x 10^31 */
99 { 2048, 225 }, /* 8 x 10^33 */
100 { 2304, 237 }, /* 5 x 10^35 */
101 { 2560, 249 }, /* 3 x 10^37 */
102 { 2816, 259 }, /* 1 x 10^39 */
103 { 3072, 269 }, /* 3 x 10^40 */
104 { 3328, 279 }, /* 8 x 10^41 */
105 { 3584, 288 }, /* 2 x 10^43 */
106 { 3840, 296 }, /* 4 x 10^44 */
107 { 4096, 305 }, /* 7 x 10^45 */
108 { 4352, 313 }, /* 1 x 10^47 */
109 { 4608, 320 }, /* 2 x 10^48 */
110 { 4864, 328 }, /* 2 x 10^49 */
111 { 5120, 335 }, /* 3 x 10^50 */
116 for(i
=0; t
[i
].p_n
; i
++ )
121 /* Not in table - use an arbitrary high number. */
126 test_keys ( ELG_secret_key
*sk
, unsigned int nbits
, int nodie
)
129 gcry_mpi_t test
= gcry_mpi_new ( 0 );
130 gcry_mpi_t out1_a
= gcry_mpi_new ( nbits
);
131 gcry_mpi_t out1_b
= gcry_mpi_new ( nbits
);
132 gcry_mpi_t out2
= gcry_mpi_new ( nbits
);
139 gcry_mpi_randomize ( test
, nbits
, GCRY_WEAK_RANDOM
);
141 do_encrypt ( out1_a
, out1_b
, test
, &pk
);
142 decrypt ( out2
, out1_a
, out1_b
, sk
);
143 if ( mpi_cmp( test
, out2
) )
146 sign ( out1_a
, out1_b
, test
, sk
);
147 if ( !verify( out1_a
, out1_b
, test
, &pk
) )
150 gcry_mpi_release ( test
);
151 gcry_mpi_release ( out1_a
);
152 gcry_mpi_release ( out1_b
);
153 gcry_mpi_release ( out2
);
155 if (failed
&& !nodie
)
156 log_fatal ("Elgamal test key for %s %s failed\n",
157 (failed
& 1)? "encrypt+decrypt":"",
158 (failed
& 2)? "sign+verify":"");
159 if (failed
&& DBG_CIPHER
)
160 log_debug ("Elgamal test key for %s %s failed\n",
161 (failed
& 1)? "encrypt+decrypt":"",
162 (failed
& 2)? "sign+verify":"");
169 * Generate a random secret exponent k from prime p, so that k is
170 * relatively prime to p-1. With SMALL_K set, k will be selected for
171 * better encryption performance - this must never be used signing!
174 gen_k( gcry_mpi_t p
, int small_k
)
176 gcry_mpi_t k
= mpi_alloc_secure( 0 );
177 gcry_mpi_t temp
= mpi_alloc( mpi_get_nlimbs(p
) );
178 gcry_mpi_t p_1
= mpi_copy(p
);
179 unsigned int orig_nbits
= mpi_get_nbits(p
);
180 unsigned int nbits
, nbytes
;
185 /* Using a k much lesser than p is sufficient for encryption and
186 * it greatly improves the encryption performance. We use
187 * Wiener's table and add a large safety margin. */
188 nbits
= wiener_map( orig_nbits
) * 3 / 2;
189 if( nbits
>= orig_nbits
)
196 nbytes
= (nbits
+7)/8;
198 log_debug("choosing a random k ");
199 mpi_sub_ui( p_1
, p
, 1);
202 if( !rndbuf
|| nbits
< 32 )
205 rndbuf
= gcry_random_bytes_secure( nbytes
, GCRY_STRONG_RANDOM
);
209 /* Change only some of the higher bits. We could improve
210 this by directly requesting more memory at the first call
211 to get_random_bytes() and use this the here maybe it is
212 easier to do this directly in random.c Anyway, it is
213 highly inlikely that we will ever reach this code. */
214 char *pp
= gcry_random_bytes_secure( 4, GCRY_STRONG_RANDOM
);
215 memcpy( rndbuf
, pp
, 4 );
218 _gcry_mpi_set_buffer( k
, rndbuf
, nbytes
, 0 );
222 if( !(mpi_cmp( k
, p_1
) < 0) ) /* check: k < (p-1) */
228 if( !(mpi_cmp_ui( k
, 0 ) > 0) ) /* check: k > 0 */
234 if (gcry_mpi_gcd( temp
, k
, p_1
))
235 goto found
; /* okay, k is relative prime to (p-1) */
236 mpi_add_ui( k
, k
, 1 );
252 * Generate a key pair with a key of size NBITS
253 * Returns: 2 structures filled with all needed values
254 * and an array with n-1 factors of (p-1)
257 generate ( ELG_secret_key
*sk
, unsigned int nbits
, gcry_mpi_t
**ret_factors
)
259 gcry_mpi_t p
; /* the prime */
262 gcry_mpi_t x
; /* the secret exponent */
268 p_min1
= gcry_mpi_new ( nbits
);
269 qbits
= wiener_map( nbits
);
270 if( qbits
& 1 ) /* better have a even one */
273 p
= _gcry_generate_elg_prime( 0, nbits
, qbits
, g
, ret_factors
);
274 mpi_sub_ui(p_min1
, p
, 1);
277 /* Select a random number which has these properties:
279 * This must be a very good random number because this is the
280 * secret part. The prime is public and may be shared anyway,
281 * so a random generator level of 1 is used for the prime.
283 * I don't see a reason to have a x of about the same size
284 * as the p. It should be sufficient to have one about the size
285 * of q or the later used k plus a large safety margin. Decryption
286 * will be much faster with such an x.
288 xbits
= qbits
* 3 / 2;
291 x
= gcry_mpi_snew ( xbits
);
293 log_debug("choosing a random x of size %u", xbits
);
300 { /* Change only some of the higher bits */
301 if( xbits
< 16 ) /* should never happen ... */
304 rndbuf
= gcry_random_bytes_secure( (xbits
+7)/8,
305 GCRY_VERY_STRONG_RANDOM
);
309 char *r
= gcry_random_bytes_secure( 2,
310 GCRY_VERY_STRONG_RANDOM
);
311 memcpy(rndbuf
, r
, 2 );
317 rndbuf
= gcry_random_bytes_secure( (xbits
+7)/8,
318 GCRY_VERY_STRONG_RANDOM
);
320 _gcry_mpi_set_buffer( x
, rndbuf
, (xbits
+7)/8, 0 );
321 mpi_clear_highbit( x
, xbits
+1 );
323 while( !( mpi_cmp_ui( x
, 0 )>0 && mpi_cmp( x
, p_min1
)<0 ) );
326 y
= gcry_mpi_new (nbits
);
327 gcry_mpi_powm( y
, g
, x
, p
);
332 log_mpidump("elg p= ", p
);
333 log_mpidump("elg g= ", g
);
334 log_mpidump("elg y= ", y
);
335 log_mpidump("elg x= ", x
);
338 /* Copy the stuff to the key structures */
344 gcry_mpi_release ( p_min1
);
346 /* Now we can test our keys (this should never fail!) */
347 test_keys ( sk
, nbits
- 64, 0 );
351 /* Generate a key pair with a key of size NBITS not using a random
352 value for the secret key but the one given as X. This is useful to
353 implement a passphrase based decryption for a public key based
354 encryption. It has appliactions in backup systems.
356 Returns: A structure filled with all needed values and an array
357 with n-1 factors of (p-1). */
358 static gcry_err_code_t
359 generate_using_x (ELG_secret_key
*sk
, unsigned int nbits
, gcry_mpi_t x
,
360 gcry_mpi_t
**ret_factors
)
362 gcry_mpi_t p
; /* The prime. */
363 gcry_mpi_t p_min1
; /* The prime minus 1. */
364 gcry_mpi_t g
; /* The generator. */
365 gcry_mpi_t y
; /* g^x mod p. */
374 /* Do a quick check to see whether X is suitable. */
375 xbits
= mpi_get_nbits (x
);
376 if ( xbits
< 64 || xbits
>= nbits
)
377 return GPG_ERR_INV_VALUE
;
379 p_min1
= gcry_mpi_new ( nbits
);
380 qbits
= wiener_map ( nbits
);
381 if ( (qbits
& 1) ) /* Better have an even one. */
384 p
= _gcry_generate_elg_prime ( 0, nbits
, qbits
, g
, ret_factors
);
385 mpi_sub_ui (p_min1
, p
, 1);
388 log_debug ("using a supplied x of size %u", xbits
);
389 if ( !(mpi_cmp_ui ( x
, 0 ) > 0 && mpi_cmp ( x
, p_min1
) <0 ) )
391 gcry_mpi_release ( p_min1
);
392 gcry_mpi_release ( p
);
393 gcry_mpi_release ( g
);
394 return GPG_ERR_INV_VALUE
;
397 y
= gcry_mpi_new (nbits
);
398 gcry_mpi_powm ( y
, g
, x
, p
);
403 log_mpidump ("elg p= ", p
);
404 log_mpidump ("elg g= ", g
);
405 log_mpidump ("elg y= ", y
);
406 log_mpidump ("elg x= ", x
);
409 /* Copy the stuff to the key structures */
413 sk
->x
= gcry_mpi_copy (x
);
415 gcry_mpi_release ( p_min1
);
417 /* Now we can test our keys. */
418 if ( test_keys ( sk
, nbits
- 64, 1 ) )
420 gcry_mpi_release ( sk
->p
); sk
->p
= NULL
;
421 gcry_mpi_release ( sk
->g
); sk
->g
= NULL
;
422 gcry_mpi_release ( sk
->y
); sk
->y
= NULL
;
423 gcry_mpi_release ( sk
->x
); sk
->x
= NULL
;
424 return GPG_ERR_BAD_SECKEY
;
432 * Test whether the secret key is valid.
433 * Returns: if this is a valid key.
436 check_secret_key( ELG_secret_key
*sk
)
439 gcry_mpi_t y
= mpi_alloc( mpi_get_nlimbs(sk
->y
) );
441 gcry_mpi_powm( y
, sk
->g
, sk
->x
, sk
->p
);
442 rc
= !mpi_cmp( y
, sk
->y
);
449 do_encrypt(gcry_mpi_t a
, gcry_mpi_t b
, gcry_mpi_t input
, ELG_public_key
*pkey
)
453 /* Note: maybe we should change the interface, so that it
454 * is possible to check that input is < p and return an
458 k
= gen_k( pkey
->p
, 1 );
459 gcry_mpi_powm( a
, pkey
->g
, k
, pkey
->p
);
460 /* b = (y^k * input) mod p
461 * = ((y^k mod p) * (input mod p)) mod p
462 * and because input is < p
463 * = ((y^k mod p) * input) mod p
465 gcry_mpi_powm( b
, pkey
->y
, k
, pkey
->p
);
466 gcry_mpi_mulm( b
, b
, input
, pkey
->p
);
470 log_mpidump("elg encrypted y= ", pkey
->y
);
471 log_mpidump("elg encrypted p= ", pkey
->p
);
472 log_mpidump("elg encrypted k= ", k
);
473 log_mpidump("elg encrypted M= ", input
);
474 log_mpidump("elg encrypted a= ", a
);
475 log_mpidump("elg encrypted b= ", b
);
485 decrypt(gcry_mpi_t output
, gcry_mpi_t a
, gcry_mpi_t b
, ELG_secret_key
*skey
)
487 gcry_mpi_t t1
= mpi_alloc_secure( mpi_get_nlimbs( skey
->p
) );
489 /* output = b/(a^x) mod p */
490 gcry_mpi_powm( t1
, a
, skey
->x
, skey
->p
);
491 mpi_invm( t1
, t1
, skey
->p
);
492 mpi_mulm( output
, b
, t1
, skey
->p
);
496 log_mpidump("elg decrypted x= ", skey
->x
);
497 log_mpidump("elg decrypted p= ", skey
->p
);
498 log_mpidump("elg decrypted a= ", a
);
499 log_mpidump("elg decrypted b= ", b
);
500 log_mpidump("elg decrypted M= ", output
);
508 * Make an Elgamal signature out of INPUT
512 sign(gcry_mpi_t a
, gcry_mpi_t b
, gcry_mpi_t input
, ELG_secret_key
*skey
)
515 gcry_mpi_t t
= mpi_alloc( mpi_get_nlimbs(a
) );
516 gcry_mpi_t inv
= mpi_alloc( mpi_get_nlimbs(a
) );
517 gcry_mpi_t p_1
= mpi_copy(skey
->p
);
520 * b = (t * inv) mod (p-1)
521 * b = (t * inv(k,(p-1),(p-1)) mod (p-1)
522 * b = (((M-x*a) mod (p-1)) * inv(k,(p-1),(p-1))) mod (p-1)
525 mpi_sub_ui(p_1
, p_1
, 1);
526 k
= gen_k( skey
->p
, 0 /* no small K ! */ );
527 gcry_mpi_powm( a
, skey
->g
, k
, skey
->p
);
528 mpi_mul(t
, skey
->x
, a
);
529 mpi_subm(t
, input
, t
, p_1
);
530 mpi_invm(inv
, k
, p_1
);
531 mpi_mulm(b
, t
, inv
, p_1
);
536 log_mpidump("elg sign p= ", skey
->p
);
537 log_mpidump("elg sign g= ", skey
->g
);
538 log_mpidump("elg sign y= ", skey
->y
);
539 log_mpidump("elg sign x= ", skey
->x
);
540 log_mpidump("elg sign k= ", k
);
541 log_mpidump("elg sign M= ", input
);
542 log_mpidump("elg sign a= ", a
);
543 log_mpidump("elg sign b= ", b
);
554 * Returns true if the signature composed of A and B is valid.
557 verify(gcry_mpi_t a
, gcry_mpi_t b
, gcry_mpi_t input
, ELG_public_key
*pkey
)
565 if( !(mpi_cmp_ui( a
, 0 ) > 0 && mpi_cmp( a
, pkey
->p
) < 0) )
566 return 0; /* assertion 0 < a < p failed */
568 t1
= mpi_alloc( mpi_get_nlimbs(a
) );
569 t2
= mpi_alloc( mpi_get_nlimbs(a
) );
572 /* t1 = (y^a mod p) * (a^b mod p) mod p */
573 gcry_mpi_powm( t1
, pkey
->y
, a
, pkey
->p
);
574 gcry_mpi_powm( t2
, a
, b
, pkey
->p
);
575 mpi_mulm( t1
, t1
, t2
, pkey
->p
);
577 /* t2 = g ^ input mod p */
578 gcry_mpi_powm( t2
, pkey
->g
, input
, pkey
->p
);
580 rc
= !mpi_cmp( t1
, t2
);
582 /* t1 = (y^a mod p) * (a^b mod p) mod p */
583 base
[0] = pkey
->y
; ex
[0] = a
;
584 base
[1] = a
; ex
[1] = b
;
585 base
[2] = NULL
; ex
[2] = NULL
;
586 mpi_mulpowm( t1
, base
, ex
, pkey
->p
);
588 /* t2 = g ^ input mod p */
589 gcry_mpi_powm( t2
, pkey
->g
, input
, pkey
->p
);
591 rc
= !mpi_cmp( t1
, t2
);
593 /* t1 = g ^ - input * y ^ a * a ^ b mod p */
594 mpi_invm(t2
, pkey
->g
, pkey
->p
);
595 base
[0] = t2
; ex
[0] = input
;
596 base
[1] = pkey
->y
; ex
[1] = a
;
597 base
[2] = a
; ex
[2] = b
;
598 base
[3] = NULL
; ex
[3] = NULL
;
599 mpi_mulpowm( t1
, base
, ex
, pkey
->p
);
600 rc
= !mpi_cmp_ui( t1
, 1 );
609 /*********************************************
610 ************** interface ******************
611 *********************************************/
613 static gpg_err_code_t
614 elg_generate_ext (int algo
, unsigned int nbits
, unsigned long evalue
,
615 const gcry_sexp_t genparms
,
616 gcry_mpi_t
*skey
, gcry_mpi_t
**retfactors
,
617 gcry_sexp_t
*r_extrainfo
)
621 gcry_mpi_t xvalue
= NULL
;
630 /* Parse the optional xvalue element. */
631 l1
= gcry_sexp_find_token (genparms
, "xvalue", 0);
634 xvalue
= gcry_sexp_nth_mpi (l1
, 1, 0);
635 gcry_sexp_release (l1
);
637 return GPG_ERR_BAD_MPI
;
642 ec
= generate_using_x (&sk
, nbits
, xvalue
, retfactors
);
645 generate (&sk
, nbits
, retfactors
);
658 static gcry_err_code_t
659 elg_generate (int algo
, unsigned int nbits
, unsigned long evalue
,
660 gcry_mpi_t
*skey
, gcry_mpi_t
**retfactors
)
667 generate (&sk
, nbits
, retfactors
);
673 return GPG_ERR_NO_ERROR
;
677 static gcry_err_code_t
678 elg_check_secret_key (int algo
, gcry_mpi_t
*skey
)
680 gcry_err_code_t err
= GPG_ERR_NO_ERROR
;
685 if ((! skey
[0]) || (! skey
[1]) || (! skey
[2]) || (! skey
[3]))
686 err
= GPG_ERR_BAD_MPI
;
694 if (! check_secret_key (&sk
))
695 err
= GPG_ERR_BAD_SECKEY
;
702 static gcry_err_code_t
703 elg_encrypt (int algo
, gcry_mpi_t
*resarr
,
704 gcry_mpi_t data
, gcry_mpi_t
*pkey
, int flags
)
706 gcry_err_code_t err
= GPG_ERR_NO_ERROR
;
712 if ((! data
) || (! pkey
[0]) || (! pkey
[1]) || (! pkey
[2]))
713 err
= GPG_ERR_BAD_MPI
;
719 resarr
[0] = mpi_alloc (mpi_get_nlimbs (pk
.p
));
720 resarr
[1] = mpi_alloc (mpi_get_nlimbs (pk
.p
));
721 do_encrypt (resarr
[0], resarr
[1], data
, &pk
);
727 static gcry_err_code_t
728 elg_decrypt (int algo
, gcry_mpi_t
*result
,
729 gcry_mpi_t
*data
, gcry_mpi_t
*skey
, int flags
)
731 gcry_err_code_t err
= GPG_ERR_NO_ERROR
;
737 if ((! data
[0]) || (! data
[1])
738 || (! skey
[0]) || (! skey
[1]) || (! skey
[2]) || (! skey
[3]))
739 err
= GPG_ERR_BAD_MPI
;
746 *result
= mpi_alloc_secure (mpi_get_nlimbs (sk
.p
));
747 decrypt (*result
, data
[0], data
[1], &sk
);
753 static gcry_err_code_t
754 elg_sign (int algo
, gcry_mpi_t
*resarr
, gcry_mpi_t data
, gcry_mpi_t
*skey
)
756 gcry_err_code_t err
= GPG_ERR_NO_ERROR
;
762 || (! skey
[0]) || (! skey
[1]) || (! skey
[2]) || (! skey
[3]))
763 err
= GPG_ERR_BAD_MPI
;
770 resarr
[0] = mpi_alloc (mpi_get_nlimbs (sk
.p
));
771 resarr
[1] = mpi_alloc (mpi_get_nlimbs (sk
.p
));
772 sign (resarr
[0], resarr
[1], data
, &sk
);
779 static gcry_err_code_t
780 elg_verify (int algo
, gcry_mpi_t hash
, gcry_mpi_t
*data
, gcry_mpi_t
*pkey
,
781 int (*cmp
) (void *, gcry_mpi_t
), void *opaquev
)
783 gcry_err_code_t err
= GPG_ERR_NO_ERROR
;
790 if ((! data
[0]) || (! data
[1]) || (! hash
)
791 || (! pkey
[0]) || (! pkey
[1]) || (! pkey
[2]))
792 err
= GPG_ERR_BAD_MPI
;
798 if (! verify (data
[0], data
[1], hash
, &pk
))
799 err
= GPG_ERR_BAD_SIGNATURE
;
807 elg_get_nbits (int algo
, gcry_mpi_t
*pkey
)
811 return mpi_get_nbits (pkey
[0]);
815 static const char *elg_names
[] =
824 gcry_pk_spec_t _gcry_pubkey_spec_elg
=
827 "pgy", "pgyx", "ab", "rs", "pgy",
828 GCRY_PK_USAGE_SIGN
| GCRY_PK_USAGE_ENCR
,
830 elg_check_secret_key
,
838 pk_extra_spec_t _gcry_pubkey_extraspec_elg
=