3
$\begingroup$

They say the security of Diffie-Hellman depends on the factorization of (N-1), where N is the big prime number you feed it.

More specifically, (N-1) itself has to have a big prime factor, such as (N-1)/2 also being prime.

My question isn't about why that's the case or how to tell if it has a big prime factor or not, I've seen those on here already.

My question is: HOW BIG of a prime factor does (N-1) need to have, in order for Diffie-Hellman to be considered secure, if N is let's say a 3000-bit prime? (N-1)/2 ? Divided by 4? Or a prime factor that has twice as few bits as N would suffice? For example, if N is 3000-bit, then (N-1) having a 1500-bit prime factor is enough?

How big does the prime factor need to be for Diffie-Hellman to be considered secure enough?

$\endgroup$

1 Answer 1

5
$\begingroup$

My question is: HOW BIG of a prime factor does (N-1) need to have, in order for Diffie-Hellman to be considered secure,

Background: if Diffie-Hellman, we have a generator $g$; the size of the subgroup generated by $g$ (that is, the number of values $g^x \bmod N$ can take on for various values of $x$) can be designated by $q$. That is the "large prime factor of $N-1$" (and we usually select $g$ such that $q$ is prime; if you select a subgroup that isn't of prime size, then we can assume $q$ is the largest prime factor).

With that background in place, one way to attack Diffie-Hellman is to take one of the keyshares $g^x \bmod N$ and try to recover $x$ using a generic group attack (such as Baby-Step-Giant-Step); if we recover $x$, it becomes simple to recover the shared secret. Now, it can be shown that such a generic group attack (and there are several known) always takes $\Omega( \sqrt{q} )$ steps [1]. In addition, we know algorithms for which the implied constant in $\Omega( \sqrt{q} )$ isn't that far from 1.

Because of this, if we have a security level $\lambda$, that is, we want to ensure that it takes at least $2^\lambda$ operations to break it, we need to ensure that $\sqrt{q} \ge 2^\lambda$, that is, $q \ge 2^{2 \lambda}$. Or, in other words, the prime factor needs to have a bit length (at least) twice as long as the security level we hope to achieve. For example, if we are aiming at a 128 bit security level, this means that the prime factor needs to be at least 256 bits long.

Of course, there are other attacks which depend on the size of $N$; those attacks give other constraints on the size of $N$.

[1]: This $\Omega$ notation is just like the more common $O$ notation, except that it gives a lower bound, not an upper one; that is, for the attack to succeed with a given probability (given a random instance) always takes at least $M \sqrt{q}$ operations, for some constant $M$.

$\endgroup$
9
  • $\begingroup$ So G is the generator (which is usually a very small prime, right?) and M is the modulus, which is a very big prime, these are both public. Alice and Bob pick A and B, both randomly chosen between 1 and M and then send to each other (G^A) mod M and (G^B) mod M, respectively. M is the big prime that needs to have a big prime factor for the security of DH to work, right? if M is a 3000-bit prime, how big of a prime factor would it need to have? $\endgroup$ Commented Jul 5, 2023 at 21:35
  • $\begingroup$ @KevinStefanov: Actually, $G$ needs not be either small or prime; what is crucial is that it generates your large prime subgroup (and if you pick a $q \lll N-1$, then $g$ will almost never be small). If $M$ is a 3000-bit prime, which would take circa $2^{128}$ operations to break using NFS, then the prime group should be at least 256 bits (any smaller would actively reduce the security; larger wouldn't directly help security, but may be useful for other reasons). $\endgroup$
    – poncho
    Commented Jul 5, 2023 at 21:41
  • $\begingroup$ @KevinStefanov: and, if you are looking at using a well-vetted DH group, you could do worse than using one of the groups found in datatracker.ietf.org/doc/rfc3526 $\endgroup$
    – poncho
    Commented Jul 5, 2023 at 21:44
  • $\begingroup$ So what you're saying is that if M is a 3000-bit prime, then it needs to have a 256-bit prime factor for DH to be considered secure? $\endgroup$ Commented Jul 5, 2023 at 21:44
  • $\begingroup$ @KevinStefanov: at least 256 bits to have circa 128 bits of security. Again, nothing wrong with going larger (there's a lot to be said for picking $N$ such that $(N-1)/2$ is prime) $\endgroup$
    – poncho
    Commented Jul 5, 2023 at 21:46

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.