Skip to main content
3 of 3
typos
kelalaka
  • 49.5k
  • 12
  • 119
  • 205

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?

satya
  • 1.5k
  • 10
  • 32