1
$\begingroup$

For ElGamal encryption, safe prime $p$ is used such that $p = 2q+1$. However, can someone explain to me, in simple terms, why we would need, in this context, a large order of $G$ and how it will contribute in making $g^{ab}$ more secure such that $a$ and $b$ could be obtained via solving for discrete logarithm problem.

Based on Wikipedia, using $p = 2q+1$ implies $G$ has subgroups either of order $2$ or of order $q$ and that "$g$ is then sometimes chosen to generate the order-$q$ subgroup of $G$, rather than $G$ itself, so that the Legendre symbol of $g^a$ never reveals the low order bit of $a$. A protocol using such a choice is for example IKEv2" Also, wanted some further clarity on what this meant.

$\endgroup$

1 Answer 1

2
$\begingroup$

However, can someone explain to me in simple terms why we would need in this context a large order of G and how it will contribute in making g^ab more secure

Background (which you likely already know), with El Gamal, the ciphertext is the pair $g^r, h^r \cdot m$ (where $h$ is the public key and $r$ is a random value); if we could figure out what the value $r$ is, we could recover $m$ (because we assume we know the value $h$).

So, one of the things that we need to make sure is that, given the value $g^r$, we can't deduce what $r$ is; this is known as the "discrete logarithm problem".

With that in mind, here are some of the math behind the scene:

We define the "order of G" to be the smallest value $k > 0$ for which $G^k = 1$. This is interesting because $G^r$ can take on only $k$ different values, $G^1, G^2, ..., G^{k-1}, G^k = 1$. If we keep on going, we'll end up repeating, starting back at $G^1$, and so that doesn't help us any.

If there are only $k$ different values of $r$ that give us different values of $G^r$, then if $k$ is small, what the attacker could do is just try all $k$ different values of $r$ and see if one works; if he can do that, he can recover the correct value of $r$ [1]. Actually, it turns out that if the attacker uses just a give of cleverness, he can perform this search with about $\sqrt{k}$ multiplications; hence if we want to ensure that the attacker must perform $2^{128}$ operations to attack the system (which is the current standard for "that is beyond anyone's capability"), then we need a $k$ at least $2^{256}$.

And, it turns out that there's another observation to be made: if $k$ is composite and has a prime factor $s$, the attacker can compute $r \bmod s$ with $\sqrt{s}$ operations (by using the same sort of cleverness); this reduces the strength of such a $G$.

using p = 2q+1 denotes that order of G is is 2 and q and that "g is then sometimes chosen to generate the order q subgroup of G, rather than G, so that the Legendre symbol of g^a never reveals the low order bit of a.

This talks about a common method of dealing with the above attacks (not the only method, mind).

It turns out that if $p = 2q+1$ prime, where $q$ is prime as well, and if $p \mod 8 = 7$ (something that Wikipedia forgot to mention), then the value $g=2$ always has order $q$; that is a large prime. What's so special about 2? Well, it makes computing the exponentiation a bit easier (as multiplying by 2 modulo p is quite cheap).

And, when it talks about the Legendre symbol revealing something about $g^a$, well, that is a special purpose method of finding $a \bmod 2$; in essence, it is the same approach as I referenced above to recover $a \bmod s$ for $s=2$; it works only if the order of $g$ has 2 as a factor. Because we picked a $g$ that has an odd order $q$, it doesn't work.


[1]: You might ask: even if $G^r$ is the same, wouldn't it be possible that $H^r$ take on different values? It turns out that no, that can't happen - if we finds any value $r$ that gives him the observed value of $G^r$, he can use that to decrypt.

$\endgroup$
2
  • $\begingroup$ Nit: you define order of an element such as the chosen generator $g$; order of the group $G$ is the number of elements, and for $Z_p^*$ this is $p-1$, so with $p=2q+1$ the order of any element (and equivalently the subgroup it generates) divides $2q$, and as you describe we prefer $q$. Even if $p \bmod 8 \neq 7$ there are order-q elements, just not 2. $\endgroup$ Feb 14, 2022 at 4:19
  • $\begingroup$ @dave_thompson_085: actually, in the notation I used above, $G$ is a group element, not the group taken as a whole. $\endgroup$
    – poncho
    Feb 14, 2022 at 5:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.