question on ElGamal implementation

Weikeng Chen w.k at
Thu Sep 21 08:23:53 CEST 2017

Dear All,

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 ElGamal.

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 subgroup.

In the Wikipedia
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 strongly secure.

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
$g=(g_0)^{(p-1)/q_f}$ which 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 file.

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

More information about the Gcrypt-devel mailing list