question on ElGamal implementation
w.k at berkeley.edu
Thu Sep 21 08:04:01 CEST 2017
I am not sure about whether libGCrypt uses the correct multiplicative group
for ElGamal to ensure the underlying cryptographic guarantee -- DDH
assumption -- holds.
I cannot find details in the source code that libGCrypt uses such a
subgroup -- this seems not the best practice. I would like to raise this as
an issue to discuss -- whether it is really using a secure subgroup for
*The group for ElGamal. *In non-curve case, we use a multiplicative group
with modulus $p$, where $p$ is a safe prime.
In cipher/primegen.c, the function _gcry_generate_elg_prime calls
prime_generate_internal to generate a safe prime group, and also the
It seems to return the generator for the multiplicative group with modulus
$p$, not a special subgroup -- while the DDH assumption only holds in this
In the Wikipedia (https://en.wikipedia.org/wiki
/Decisional_Diffie%E2%80%93Hellman_assumption), it said that DDH assumption
does not hold for this group.
But DDH assumption is crucial for the semantic security of the ElGamal
algorithm. If we are using a generator for group modulus $p$, it is not
Professor Dan Boneh from Stanford University said this in his paper "The
decision Diffie-Hellman problem" in Section 4.1 (
*When $g$ is a generator of $Z_p^*$ the system is not semantically secure. *
while semantical security is the foundation of security encryption schemes.
*The general treatment. *Instead of letting $g$ be the generator of $Z_p^*$,
we let $g$ becomes the generator of a subgroup of $Z_p^*$. This subgroup
has the prime order.
In prime_generate_internal, the prime $p$ is given as $p=2(q f_1 f_2 ...
f_n) + 1$, where $q$ as the prime with a sufficient size.
If we have a generator $g_0$ in $Z_p^*$, we can have
is the generator of a prime group. In this group, DDH assumption is
believed to hold.
*Cannot find relevant code in libGCrypt.* In cipher/elgamal.c, we have the
key generation function generate, which uses the generator $g$ directly
from _gcry_generate_elg_prime. This function is defined in cipher/primegen.c.
This function directly calls prime_generate_internal, which is in the same
Before Ln 624, the code of prime_generate_internal, it is about finding a
safe prime and returns its factors (this is helpful because finding the
generator/primitive root becomes probabilistic polynomial-time). Starting
Ln 629, we start to test the candidate generator. It seems that we are
finding the primitive root of the group modulus $p$, not the subgroup.
*My question. *Many open-source implementations of ElGamal do not jump to
this subgroup. But DDH assumption holds only in these subgroups.
*1. [Correctness of my code reading]* Is it due to my misunderstanding of
the code and I made it wrong -- that libGCrypt is surely finding the good
generator for that subgroup?
*2. [Should we improve?]* Why not prefer a better generator?
Thanks a lot for reading!
Weikeng Chen @ 795 Soda Hall
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the Gcrypt-devel