ElGamal: Multiplicative cyclic group and key generation

Question

Here on the ElGamal wikipedia page http://en.wikipedia.org/wiki/ElGamal_encryption

Alice generates an efficient description of a multiplicative cyclic group G, of order q, with generator g.

How is this done? What are some of the properties here?

Answer 1

I'm not sure what level of explanation you are looking for, but from the very basics, subgroups work like this.

Consider concretely the example of working $\mod{p}$ where $p=11$. Next we have to find a generator $g$. Initially, any number $\{0,\ldots,n-1\}$ (or $\mathbb{Z}_p$ for short) is a candidate.

Below is a chart showing each $g$ value as a row, each $a$ value as a column, and the expression $g^a \mod{11}$ evaluated for each $g$ and $a$.

$ \begin{array}{c|ccccccccccc} g \backslash a & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ \hline 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 2 & 1 & 2 & 4 & 8 & 5 & 10 & 9 & 7 & 3 & 6 & 1 \\ 3 & 1 & 3 & 9 & 5 & 4 & 1 & 3 & 9 & 5 & 4 & 1 \\ 4 & 1 & 4 & 5 & 9 & 3 & 1 & 4 & 5 & 9 & 3 & 1 \\ 5 & 1 & 5 & 3 & 4 & 9 & 1 & 5 & 3 & 4 & 9 & 1 \\ 6 & 1 & 6 & 3 & 7 & 9 & 10 & 5 & 8 & 4 & 2 & 1 \\ 7 & 1 & 7 & 5 & 2 & 3 & 10 & 4 & 6 & 9 & 8 & 1 \\ 8 & 1 & 8 & 9 & 6 & 4 & 10 & 3 & 2 & 5 & 7 & 1 \\ 9 & 1 & 9 & 4 & 3 & 5 & 1 & 9 & 4 & 3 & 5 & 1 \\ 10 & 1 & 10 & 1 & 10 & 1 & 10 & 1 & 10 & 1 & 10 & 1 \end{array} $

Property 1: for each row (except the first), the numbers eventually reach $1$ and then repeat.

The first generator, $0$, is degenerate. We usually exclude it from consideration. $\mathbb{Z}_p$ without $0$ is denoted $\mathbb{Z}^*_p$.

The next generator, $1$, only generates the number $1$.

The next generator, $2$, generates $\{1,2,4,8,5,10,9,7,3,6\}$, which if you sort turns out to be each 10 elements of $\mathbb Z_p^*$.

The next generator, $3$, generates $\{1,3,9,5,4\}$.

Generators $6,7,8$ generate the same group as $2$ (just in a different order). Generators $4,5,9$ generate the same group as $3$. Generator $10$ generates $\{1,10\}$.

There are a lot of properties contained in this chart but the relevant one is to consider the order (number of elements) in each possible group. We saw generators with $1$, $2$, $5$ and $10$ elements. These numbers are not coincidental. Property 2: they are the factors of $p-1$ which is $10$ when $p=11$. This holds true for any $p$ that is prime.

Each of these smaller groups are called "subgroups" of $\mathbb{Z}^*_p$. Take the group generated by $3$: $\{1,3,9,5,4\}$. If you take any element of this group and multiply it by any other element $\bmod 11$, the result will always be one of the elements of this group. This means it is closed under multiplication or a "multiplicative subgroup." Property 3: If $p$ is prime, each subgroup will be multiplicative.

For the security of Elgamal, we essentially want both $p$ and the order of the subgroup $q$ to be large primes. This means $q$ should divide $p-1$. In the example $p=11$ and $q=5$. It is typical to set $p=2q+1$ (that is $(p-1)=2q$). For things other than Elgamal (like DSA), we might use $p=\alpha q+1$ for some $\alpha$ larger than 2 (e.g., so that $p$ will be 1024 bits and $q$ will be 160 bits). For $p=2q+1$, there will be subgroups of order $p-1$, $q$, $2$ and $1$ (the factors of $p-1$). Most generators will either have order $p-1$ (generating $\mathbb{Z}^*_p$) or $q$ (generating a group we call $\mathbb{G}_q$).

How do we find $\mathbb{G}_q$?

1. Find a $p$ that will have $\mathbb{G}_q$: we choose a random prime $q$, compute $p=2q+1$, repeat until $p$ is prime.
2. Find a $g$ that will generate $\mathbb{G}_q$ and not $\mathbb{Z}^*_p$ (or any other subgroup). Since groups end with $1$ and then repeat, we test if $g^q \mod{p}$ is equal to $1$. If it is, we have very likely found a generator of $\mathbb{G}_q$ (and very unlikely found something of order $1$ or $2$; we can check that $g^2$ is not equal to $1$).
3. The description of the group is $\langle g,q,p \rangle$ (you could compute $q$ from $p$ to save space in the description).

One final thing: look at the column with $a=2$. These are the quadratic residues of $\mathbb{Z}_p^*$. Property 4: When $p=2q+1$, they are the exact same group as $\mathbb{G}_q$. This means, by using $\mathbb{G}_q$, you don't have to worry about an adversary testing if certain numbers are quadratic residues or not (see @Jalaj's answer).

Answer 2

Well to give a "description" of a multiplicative cyclic group, one need only send the modulus. Since everyone knows how the group is used, that's all you really need. How this is done in practice is described on page 164 of the Handbook of Applied Cryptography. Algorithm 4.84 specifically.

Answer 3

One of the property that you need from the group is that it should be of order $q$, where $q$ is a safe prime (of form $2p+1$ where $p$ is also a prime). The reason behind this is because one can possibly break the discrete log assumption if the $q$ is improperly chosen by using Legendre symbol. More details are below.

For the semantic security of an ElGamal encryption scheme, we need DDH assumption to be true.

If $q$ is improperly chosen, we can have the following attack:$\newcommand\lsb{\operatorname{lsb}}\newcommand\Dlog{\operatorname{Dlog}}$
Given $(\alpha, \beta, \gamma)$, the attacker needs to know whether these are of the form $(g^x, g^y, g^{x·y})$.

If $$\lsb(\Dlog(\alpha)) × \lsb(\Dlog(\beta)) = \lsb(\Dlog(\gamma))\mod 2,$$ then return $1$, else return $0$.

Now finding $\lsb$ is a simple arithmetic by the use of Legendre symbol, if $q$ is not a safe prime.