Elgamal encryption

The Elgamal algorithm is an asymmetric key encryption algorithm for public key cryptography which is based on Diffie-Hellman key agreement. It was described by Taher Elgamal in 1984. The Elgamal algorithm is used in the free GNU Privacy Guard software, recent versions of PGP, and other cryptosystems. The Digital Signature Algorithm is a signature scheme is a variant of the ElGamal signature scheme, which should not be confused with the Elgamal algorithm.

Generating the group G

As described above, Elgamal can be defined over any cyclic group G, and is secure if a certain computational assumption (the "DDH Assumption") about that group is true. Unfortunately, the straightforward use of G=Z_p for a prime p is insecure, because the DDH Assumption is false in this group. In contrast, computing discrete logs is believed to be hard in Z_p, but this is not enough for the security of Elgamal.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

The two most popular types of groups used in Elgamal are subgroups of Z_p and groups defined over certain elliptic curves. Here is one popular way of choosing an appropriate subgroup of Z_p which is believed to be secure:

Related Topics:
Subgroup - Elliptic curve

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

• Choose a random large prime $p$ such that $p-1=kq$ for some small integer $k$ and large prime $q$. This can be done, for example with $k=2$, by first choosing a random large prime $q$ and checking if $p=2q+1$ is prime.
• Choose a random element $g\; in\; Z\_p$ such that $g\; eq\; 1$ and , i.e. such that $g$ is of order $q$.
• The group $G$ is the subgroup of $Z\_p$ generated by $g$, i.e. the set of $k$th residues mod $p$.

When encrypting, care must be taken to properly encode the message m as an element of G, and not, say, as just an arbitrary element of Z_p.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~