Why are prime numbers used in Diffie-Hellman key exchange?

Question

Diffie-Hellman key exchange algorithm uses operations like 2^8 mod n where n is a prime number.

What is the reason for using prime numbers instead of other numbers?

Answer 1

Prime numbers don't break down into smaller factors, making cracking the code or hash much harder than using, say 12, which breaks down with /2 or /3 or /4 or /6. The prime number 7, is less than 12, but only has the factor of 7, so there are less attack vectors. This is a drastic oversimplification, but hopefully helps a little.

Here's a specific example:

2^x mod 12

This only has 2 possible values, for any x above 1: 4 or 8. Since this is used to generate the shared key in a similar way, you end up with the same two possibilities. In other words, once you know that the base and mod are 2 and 12 (which any computer listening in on the conversation would be able to pick up), you automatically know that the shared secret encryption key can be only one of two possibilities. It only takes two simple operations to determine which decrypts the message. Now let's look at a prime mod:

2^x mod 13

This has 12 different possibilities, for x>1. It also has 12 different possible shared keys that can be generated. Thus it requires 6x more computing power to decrypt a message based on this prime modulus, than it would on the mod 12 example.

2^x mod 14 has 4 possibilities.

2^x mod 15 has 4

2^x mod 16 collapses completely into 1 possibility after x=3 (which is why choosing a base that fits the DH requirements is important)

2^x mod 17 has... you guessed it, 16 possibilities! Aren't primes cool? :)

Thus, yes the factorability of the modulus number has everything to do with crackability of the encrypted message.