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

I'm writing a cryptography essay, and am wondering why you need a prime number for the deffie-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!

• Gosh, have you even tried an example where the modulus is not prime? Let the modulus be 45, 64, or 300. If you are uncomfortable with modular arithmetic then you need to buckle down and relearn it, because that is essential to making any sense of Diffie-Hellman. – KCd Apr 20 '13 at 12:20

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!

• Another great answer, and link for exploration! – Namaste Apr 21 '13 at 0:10
• @amWhy: I am a big fan of crypto because of the number theory and computational complexity! Thanks – Amzoti Apr 21 '13 at 0:12
• And there's connections to algebra, which appeals to me – Namaste Apr 21 '13 at 0:14
• Amazing how number theory finds application in protecting data.(+1) – Inceptio Apr 21 '13 at 11:57

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.