# ElGamal: Multiplicative cyclic group and key generation

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?

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

• Where does q come in though? It doesn't appear in any of the equations used by ElGamal that you give. Feb 29, 2016 at 23:07
• This is the best explanation I've found on the internet after a long time of searching. Most of the content - Wikipedia, for example - I find is too abstract and doesn't really help me visualizing the construction. Do you have a literature/resource suggestion on where I can learn those topics in a friendly format like yours? Sep 14, 2016 at 17:20

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.

• ElGamal-like schemes can be used also with other groups than the standard "Integers modulo prime" group, where some more information might be necessary. Dec 13, 2011 at 17:44

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.

• I edited your answer to format it a bit more nicely, and add some additional information. Please read again to make sure that I didn't add things you would not have written (and feel free to revert or edit again). Dec 13, 2011 at 17:55
• Thanks! I tried using the basic latex method to write in the math mode, but it didn't work. Now I know :) Dec 13, 2011 at 18:10
• You mean that $q$ should be a safe prime of the form $q=2k+1$ where $k$ is also a prime? Because in your writing you substitute $k$ with $p$ where $p$ is the prime of the initial group.Which is like a 'loop'. Nov 23, 2013 at 13:22