3
$\begingroup$

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?

$\endgroup$
6
$\begingroup$
  • 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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – satya Dec 28 '18 at 15:56
  • $\begingroup$ 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? $\endgroup$ – satya Dec 28 '18 at 15:59
  • $\begingroup$ @satya Did you read the linked article? $\endgroup$ – kelalaka Dec 28 '18 at 16:00

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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