I read a lot about Diffie-Hellman, but there is one thing I dont understand: why does the modulus p need to be a prime? What if it would not be a prime?


3 Answers 3


Answer to Martin's and Vadim's comments:

Let $n:=p$ and you want to find $x$ with $g^{x} \equiv y \bmod pq$

Calculate the two easier DL problems:
${x_p}$ with $g^{x_p} \equiv y \bmod p$
${x_q}$ with $g^{x_q} \equiv y \bmod q$

Note that
$x_p \equiv x \bmod p-1$
$x_q \equiv x \bmod q-1$

With the chinese remainder theorem you can calculate $x'$ from $x_p$ and $x_q$ with
$x' \equiv x \bmod lcm(p-1, q-1)$

  • $\begingroup$ Thank you. It is essential that adversary is supposed to be able to solve DL problem for prime-modulus groups from factorization. $\endgroup$ Dec 6, 2015 at 20:39
  • $\begingroup$ once you get $x \pmod{lcm(p-1, q-1)}$ how do you get it mod $(p-1)(q-1)$? $\endgroup$ Mar 5, 2016 at 22:35

It has to do with the Diffie–Hellman assumption. The DH key exchange is secure in groups where the computational DH assumption holds. One of the simplest such groups is the multiplicative group modulo a large prime.

However, that is not necessarily required. At least some composite integers with unknown factors would make a secure Diffie–Hellman modulus, assuming factoring is hard.

  • 4
    $\begingroup$ If the modulus is not prime, someone who knows the factorisation may break the DH. One can easily show that the modulus is prime and that proves that the DH is secure. On the other hand, you cannot prove that you do't know the factorisation of a composite modulus. $\endgroup$
    – user27950
    Nov 5, 2015 at 11:51
  • 1
    $\begingroup$ Ok, the security depends on Eve not to be able to find - if there are - factors of p. But how can Eve break DH if she knows factors of p? $\endgroup$
    – user17971
    Nov 5, 2015 at 12:01
  • 2
    $\begingroup$ you can use the chinese remainder theorem $\endgroup$
    – user27950
    Nov 5, 2015 at 14:56
  • $\begingroup$ Yes, the factors need to be secret. One of the participants in an ephemeral key exchange could safely generate them (if they can be authenticated), but not sure it has any advantages over a prime modulus. $\endgroup$
    – otus
    Nov 5, 2015 at 17:23
  • 1
    $\begingroup$ @Cryptostasis May I second Martin's request please? Exactly how would CRT help breaking CDH? $\endgroup$ Dec 5, 2015 at 17:51

It does not need to be a prime. All that's required for the ciphering scheme to work for a (g, p) pair is that g is a generating element for the cyclic multiplicative group defined by p.

The opposition to using non-prime p usually based on the fact that knowing factorization of p makes the cipher easier to break by solving "easier" problems for each of its factors. However, this is nothing more than a logical fallacy. If the problem is hard to solve for a prime p, it will be as hard (or harder) to solve for any composite number that has p as a factor.

  • 1
    $\begingroup$ Actually, it's the other way around if you consider that it's not $p$ compared to a multiple of $p$. It only makes sense to compare $p$ to some composite of equal length. And that implies the prime factors are at most half the size - which is a lot easier for each factor and combining them back together is comparably irrelevant due to CRT. Even if the full factorization is not known, every known small prime just reduces the size of the given problem. Btw., this question is over 3 years old. $\endgroup$
    – tylo
    Jan 18, 2019 at 19:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.