3

When using the Diffie-Hellman key-exchange, it is said to be important to use a safe prime. However, if a non-prime modulus with sufficient bit-length is generated, is there an attack that can be used to recover the shared secret from the public communication (g, g^a, g^b, modulus) or to decrypt an encrypted message?

5

TL;DR: Yes, it possibly could be decrypted.

NOTE: I originally did not realize your question has a subtle nuance to it. You mention safe primes and then non-primes. But safe primes is a mathematical term. Not every prime is a safe prime! Safe prime is a prime 2p + 1 such that p is also prime. It is not only important that modulus in DH is prime but it should be a safe prime for best security.

Why you should not use non-primes

Whether non-primes can be safe depends on what you mean by sufficient length. It may not be possible to reasonably break them, if the numbers are much bigger then usual, but it would very much depend on the exact numbers.

One of the reasons we use safe primes as modulus (p) is to make sure we generate many possible secrets from the range <0, p). When p is not prime, this may not be the case. The fewer secrets we generate, the easier to brute-force them.

For example lets say we use g=5, p=25. Then the generated secret s will always be either 0 or 5. Obviously this is much easier to brute-force than all the numbers from 0 to 24. Safe primes (not normal primes) generate large prime subgroups, meaning the secret can have many values, even if not all the possible ones.

Another even bigger problem is that, if you use a non-prime you would only have to solve the discrete logarithm problem for the factors of p, which is much easier. You can read more on CryptoSE.

Now as you can see, it is still possible to think of numbers large enough that it would be secure enough. For example if we choose two different primes both large enough to be secure on their own and then multiply them and use the result as p, then this should be secure. But you can't really be sure for arbitrary values as there may be many small factors or the same factors and using unnecessarily large numbers would cost you in performance.

There also may be other problems I am unaware of.

Thanks to AleksanderRas for the link to CryptoSE.

Why you should use safe primes

The reason to use safe primes is related to the first reason to use primes. Even a prime number may have a small prime group. This means it does not generate many secrets from the range <0,p). Safe primes are better at having large prime groups and therefore generating more secrets making brute-forcing harder. You can read a bit more at CryptoSE.

5

Yes, it would be quite feasible to recover the shared secret, because you would now "only" have the discrete log problem modulo all the primes that make up the composite numbers. This could still take some time but would be possible to do in a reasonable time.

Also see this question on CryptoSE for more information.

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.