# 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 $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 mod 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).

-

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. – Paŭlo Ebermann Dec 13 '11 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). – Paŭlo Ebermann Dec 13 '11 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 :) – Jalaj Dec 13 '11 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'. – curious Nov 23 '13 at 13:22