Score:0

Could someone explain to me in simple terms why we need a large order of group G for Diffie-Hellman and what does that mean?

vn flag
Zod

For El-gamal 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 & b could be 0btained via solving for discrete logarithm problem.

Based on Wikipedia, 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 ga never reveals the low order bit of a. A protocol using such a choice is for example IKEv2.[15]" Also wanted some further clarity on what this meant.

Score:2
my flag

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.

dave_thompson_085 avatar
cn flag
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.
poncho avatar
my flag
@dave_thompson_085: actually, in the notation I used above, $G$ is a group element, not the group taken as a whole.
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.