7
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Thank you. It is essential that adversary is supposed to be able to solve DL problem for prime-modulus groups from factorization. $\endgroup$ – Vadym Fedyukovych Dec 6 '15 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$ – David 天宇 Wong Mar 5 '16 at 22:35
2
$\begingroup$

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.

$\endgroup$
  • 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 '15 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$ – Martin Nov 5 '15 at 12:01
  • 2
    $\begingroup$ you can use the chinese remainder theorem $\endgroup$ – user27950 Nov 5 '15 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 '15 at 17:23
  • 1
    $\begingroup$ @Cryptostasis May I second Martin's request please? Exactly how would CRT help breaking CDH? $\endgroup$ – Vadym Fedyukovych Dec 5 '15 at 17:51
-2
$\begingroup$

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.

$\endgroup$
  • 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 at 19:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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