# question on ElGamal implementation

Weikeng Chen w.k at berkeley.edu
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
generator.

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
(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 strongly secure.

Professor Dan Boneh from Stanford University said this in his paper
"The decision Diffie-Hellman problem" in Section 4.1
(http://crypto.stanford.edu/~dabo/abstracts/DDH.html):

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?