How to formally say that the integers modulo $p$ for a prime $p$ gives results that are "more random" than for a composite $n$? I'm doing a presentation on cryptography for non-experts. My main algorithm of the presentation is the Diffie Hellman key exchange. It uses modulo arithmetic for a prime $p$. During my presentation, I'd like to be able to explain why the modulo operation uses a prime instead of a composite number. I've seen documents that kind of 'hand wave' the explanation. The best explanation I've seen, albeit hand-wavey is from Quora:

But when data is not random then strange things happen. For example
consider numeric data that is always a multiple of 10.
If we use mod 4 we find:
$10 \bmod 4 = 2$
$20 \bmod 4 = 0$
$30 \bmod 4 = 2$
$40 \bmod 4 = 0$
$50 \bmod 4 = 2$
So from the $3$ possible values of the modulus $(0,1,2,3)$ only $0$ and $2$
will have collisions, that is bad.
If we use a prime number like $7$:
$10 \bmod 7 = 3$
$20 \bmod 7 = 6$
$30 \bmod 7 = 2$
$40 \bmod 7 = 4$
$50 \bmod 7 = 1$

My question is: Can we get more precise than this? Are there any mathematical theorems that can show why this pattern would emerge?
Can we get more precise than this?


Actually the "randomness" of the resulting values is not the blocking issue with composite moduli for DH.

What is much more severe is the fact that if you know the factorization of the modulus $n=pq$, then solving $g^x\bmod n$ is essentially the same as solving $g^x\bmod p$ and $g^x\bmod q$ both of which are substantially easier than solving the problem for $n$ itself (using eg GNFS). Afterwards you can cheaply recombine the solutions with CRT.

In particular note that using a 2048-bit safe prime for DH yields a secure (unauthenticated) key exchange (with effort needed of about $2^{112}$ to break it) whereas if you were to use eg balanced factors that would drop to solving two 1024-bit discrete log instances, both of which need about $2^{80}$ work (so $2^{81}$ in total). This is considered feasible if you have the right amount of funding (eg nation-state level). Obviously if you use unbalanced factors the run-time of attacks is dominated by the larger factor and at that point you may just do away with the smaller one and save yourself the computation time (for your normal exchanges).

If you don't know the factorization, things become harder, but so does uncertainity. You have to trust that whoever generated the composite modulus actually doesn't know the factors (and thus is able to much more easily break the security). Also it allows for parameter replacement attacks which in turn do allow such attacks. This is not a theoretical attack. And in fact with such a parameter replacement attack you could just sneak in a value that is a composite of 4x 512-bit primes, nobody could factor that (easily) but with about a week of pre-computation every discrete log instance with that modulus could be solved in a matter of seconds.

So TL;DR: By using composite moduli you only gain a lot of headaches and neither speed nor security.



If the above is too complex try the following:

We use primes for the modulus in Diffie-Hellman because it gives us no speed nor a security advantage not to use them. In fact quite the opposite, if we used composites, we could split the relevant hard problem of discrete logarithm along the factorization and solve both sub-problems in parallel. Even worse each of these instances is significantly easier to solve due to the large reduction due to the solving algorithm's complexity growing really fast with the problem size. If we don't know the factorization we'd have to trust the generator of the modulus not to exploit the above weakness against us and attackers may replace our parameters with theirs, giving them backdoor access to the data.