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?

  • $\begingroup$ I find that Quora answer to be very misleading. When primes are used in hash algorithms, the typical operation is multiplication, not division. $\endgroup$
    – bmm6o
    Dec 5 '18 at 20:03
  • $\begingroup$ One can argue that you selected a special series to result in 2,0's since you show numbers greater than the modulus. It is better to use a circular representation to show full cycle and sub-groups. The closes that I found on Mathematica $\endgroup$
    – kelalaka
    Dec 5 '18 at 20:36

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.

  • $\begingroup$ Do primes come up at all in cryptography because they are better for randomness? Or is that line of thinking a red herring? $\endgroup$ Dec 5 '18 at 21:09
  • 1
    $\begingroup$ @FarleyKnight cryptographers tend rarely to think in terms of "better randomness" outside of PRNG design and analysis. It's usually more about "can we break this and if so how fast" primes usually come up here because of their simple structure and because CRT is a thing. $\endgroup$
    – SEJPM
    Dec 5 '18 at 21:17
  • $\begingroup$ I guess the problem I'm running into is that my audience may not really know or care about "can we break this". If I tell them an algorithm cannot be broken, they will probably believe me. However, if I can show them why it would be difficult to crack because the output "looks random and unpredictable" that would help my presentation. $\endgroup$ Dec 5 '18 at 21:46
  • $\begingroup$ Does it make sense to say that primes are better for the modulus because their outputs are less predictable, thus harder to crack? Is there any 4th grade-level "look at all the numbers" argument that can be made here? Or do we require advanced mathematics to convince someone that one choice for the modulus is better than the other? $\endgroup$ Dec 5 '18 at 21:48
  • $\begingroup$ @FarleyKnight Would "primes are better because there are less shortcuts to predicting / reversing the exponentiation value for them" work better? (This treats the CRT as a "shortcut") $\endgroup$
    – SEJPM
    Dec 5 '18 at 22:15

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.