# Why is Diffie-Hellman Insecure If Order of the Generator Has Only Small Prime Factors?

In this post from security SE, Tom Leek mentioned that, for Diffie-Hellman to be secure order of the group $$g$$ should have a prime factor at least $$2k$$ bits long, where $$k$$ is the security parameter.

Why is it so? Order of $$g$$ has to be large, otherwise, the discrete log would be easy. But I couldn't see any other reason why the order of $$g$$ should have a large prime factor. And why should it be at least $$2k$$ bits long (instead of $$k$$ bits long)?

It also says the private keys $$a$$ and $$b$$ should also be $$2\text{k}$$ bits long. They should be large, otherwise, the discrete log would be easy. But why should they be $$2\text{k}$$ bits long, instead of $$\text{k}$$ bits long?

• But I couldn't see any other reason why the order of g should have a large prime factor.

Let $$p$$ be the Diffie-Hellman modulus. The order $$q$$ of the subgroup generated by $$g$$ must have at least one large prime factor to prevent the use of Pohlig–Hellman algorithm. The complexity of this algorithm $$\mathcal O\left(\sum_i {e_i(\log n+\sqrt p_i)}\right)$$ where $$e_i$$ is the power of the prime factor $$p_i$$. In short, the larger one of the $$p_i$$s the higher complexity.

• Why should it be at least 2k bits long (instead of k bits long)?

The $$\text{k}$$-bit is the required for the target security. The generic attacks on Discrete logarithm problem have $$\mathcal{O}(2^\text{k/2})$$ complexity thus you need to start at least from $$2\text{k}$$.

Note: The safe primes $$p = 2q+1$$ guarantees that the order of $$g$$ is $$q$$ or $$2q$$.

• It also says the private keys a and b should also be 2k bits long.

No, the $$2\text{k}$$-bit for the choice of $$a$$ and $$b$$ is not necessary. As you can see from this answer;

The standard Decisional Diffie-Hellman assumption holds for the case that $$g^{x_a}$$ and $$g^{x_b}$$ are uniformly distributed in the group (which should be a prime-order subgroup).

There is also a linked article (Short Exponent Diffie-Hellman Problems) for this issue in the comments of this the answer.

• Why should $g^{x_a}$ and $g^{x_b}$ be uniformly distributed in a "prime-order" subgroup? What happens if the order of the subgroup is composite? – satya Dec 28 '18 at 15:56
• Since order of $g$ is at least 2k bits long, it means we need to chose $x_a$ and $x_b$ to be at least 2k bits long right? – satya Dec 28 '18 at 15:59
• @satya Did you read the linked article? – kelalaka Dec 28 '18 at 16:00