Why is a prime number needed for the Diffie-Hellman key exchange? (modular arithmetic)

Question

I'm writing a cryptography essay, and am wondering why you need a prime number for the Diffie-Hellman key exchange? Any help would be appreciated :)

This is a link to a previous post which quickly shows what the Diffie-Hellman key exchange is: Why/How does the Diffie-Hellman Key Exchange work?

I haven't done modular arithmetic for a while, but I'm sure it will be a simple answer if someone is familiar with it/done it recently!

Answer 1

In fact you need two primes p and q

Then you can use arithmetic modulo pq to encrypt messages.

The one that knows the prime numbers can calculate things quickly mod pq

but because it is difficult to factor a number into primes, people who know the product and not the factors will not be able to calculate things so quickly mod pq.

That's how it is used for encryption.

Answer 2

The D-H encryption schema is one of the Discrete Log based systems.

Contrast this with the Integer Factorization Problem (IFP), like Rivest-Shamir-Adelman (RSA) or Elliptic Curve Discrete Log (ECDLP) based problems.

If you don't use primes, the systems relying on them will be severly reduced in bit-strength (makes it easier to break or potentially does not work at all).

Have fun!