# Big prime factor of the prime number you feed to Diffie Hellman

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?

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$$.

• 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? Jul 5, 2023 at 21:35
• @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). Jul 5, 2023 at 21:41
• @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 Jul 5, 2023 at 21:44
• 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? Jul 5, 2023 at 21:44
• @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) Jul 5, 2023 at 21:46