1
$\begingroup$

I am currently writing a thesis about different cryptographic protocols like DH-Key exchange, TLS or IKE. Most of them rely on a prime number earlier or later, so for security reasons I wondered if this prime number is supplied by the user and if yes that leads to the question if I can manually provide it (for example to use a pseudoprime to break the underlying primitive more easily).

I really tried to search online, but there are very little information about this part of protocols. I hope you can help me with that.

Thank you for your time and answers :)

$\endgroup$
3
  • $\begingroup$ Recent related question: How is a generator found for a group, both in case of DH & ECDH?. $\endgroup$
    – fgrieu
    Feb 11 at 14:47
  • $\begingroup$ Have a look at crypto.stackexchange.com/questions/45151/…. In this example, the two large primes are generated by openssl. But, if you wanted to provide your own large primes, you could do so, and write them to the private.key file the same way that openssl does, and the rest of the process would be the same. $\endgroup$
    – mti2935
    Feb 11 at 15:13
  • 1
    $\begingroup$ Actually, if you are trying to specify DH parameters in such a way to make it attackable, the most promising way would not to be to specify $p$ composite (fairly easy to detect if someone checks); instead, it would be to specify $p$ prime, and $g$ with a smooth (or, at least, not too rough) order. Now, it wouldn't be true NOBUS (ECM is just too good at finding moderate factors of $p-1$), however it would not be easy to detect automatically $\endgroup$
    – poncho
    Feb 11 at 18:46
2
$\begingroup$

Let's have a look at how these are implemented:

RSA

RSA is probably the example, showing how prime numbers are used in cryptography. In order to calculate a private key, two prime numbers, $p$ and $q$ are "chosen". What that means in practice is that your computer will generate a random number (and set a few bits) and then check whether or not the generated random number is a prime.

Well...not exactly. Actually, the generated number is a "pseudo prime number", which is a number that is probably a prime number, but we can't know for sure. In order to be certain, we would have to divide the number by every prime number up to the square root of the prime candidate.

Why isn't this check done? As you can imagine, checking whether or not 13377216267221394781281321803240685565647633863945354245591337480581850892718220086347852930388186839929611014777408043323753186115505611255512212061593047 is a prime factor of 168581487233807662095985877892466382655984504887588184273878566402288131033127314863556248166230176818735604347430473403376658381900826700241919315590165489510028586594896744589808921429729412701596114362546978418049726172509111051384159129475101054095614648000575426731420406552789078218487162756487172295557 is a computationally expensive task. Especially if our current tests run magnitudes faster and can give us a $4^{-k}$ chance of a non-prime passing the test, with $k$ being the number of runs of the Miller-Rabin test.

You can even try this yourself by running openssl genrsa. You will see output like this:

Generating RSA private key, 2048 bit long modulus (2 primes)
................+++++
...............+++++
e is 65537 (0x010001)

Each . means a potential prime candidate was generated, and each + means a round of Miller-Rabin was passed. According to this answer, even three rounds of Miller-Rabin will be enough to make it very unlikely that a randomly generated non-prime passes the Miller-Rabin test. So as you can see, OpenSSL stops after five passed rounds and moves on to generating a new number.

Diffie-Hellman Key Exchange

In order for DH to work, there needs to be a public prime $p$, which can be a known default value. These can be generated on-the-spot by either the client or the server, but publicly known default values can be used. Since these are just transmitted over plain text, an attacker can intercept them.

It should be noted that you want to pick a $p$ for which $p-1$ has a large prime factor $q$.

The secret keys $a$ and $b$ generated in DH don't need to be primes, so any random number will suffice.

Are they supplied by the user?

Yes and no. Many protocols require a user's private key, which they supply in form of a key file. Nothing stops a user from generating their own key file with any prime number of their choosing.

However, most users won't do that, as there is really no benefit to that. Even an attacker has no benefit of supplying something like a semi-prime (a number that is the result of two prime numbers, e.g. 15), since that would not give them any advantage.

Definitely, no serious program will ever ask the user to enter a prime number, which is then used for cryptographic purposes, aside from demonstration tools.

$\endgroup$
5
  • $\begingroup$ Thanks for this answer, especially the part with DH helps me a lot. I have to correct you in one point tho: Using a composite number for DH helps the attacker very much, as the cyclic group gets significantly smaller and thus the discrete logarithm is easier to calculate. This is the main topic of my thesis and that's why this question came up. $\endgroup$
    – Greybound
    Feb 11 at 14:06
  • 2
    $\begingroup$ @Greybound: I trust you are aware that using a random prime in DH is generally not a good idea; you want to generate a prime $p$ where $p-1$ has a known large prime factor $q$. $\endgroup$
    – poncho
    Feb 11 at 14:50
  • $\begingroup$ @poncho That is true. Which is why the overwhelming majority of implementations us known values for $p$. $\endgroup$
    – MechMK1
    Feb 11 at 15:14
  • $\begingroup$ @poncho I am aware of that. But that's exactly my point, I want to attack DH by providing a weak value for p (i.e. a composite that passes primality tests with maximum likelihood) $\endgroup$
    – Greybound
    Feb 11 at 15:31
  • 2
    $\begingroup$ @Greybound: you are thinking of "a composite that passes primality tests with maximum likelihood" when poncho suggested a prime $p$ with $p-1$ having no large prime factor. So "that's exactly my point" needs reconsideration. $\endgroup$
    – fgrieu
    Feb 11 at 17:39
0
$\begingroup$

For most purposes, your computer generates a random prime. It does this by taking a random odd number and checking whether that's prime. Repeat until such a number has been found.

In some cases, it is possible to create cryptographic material with your own, chosen, prime numbers. For example, RSA keys consist of two prime numbers multiplied together. If you choose one or both of these prime numbers in a particular way, you may create a deliberately insecure RSA key pair.

$\endgroup$
1
  • $\begingroup$ What about Diffie-Hellman? $\endgroup$
    – DannyNiu
    Feb 11 at 19:35

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.