6
$\begingroup$

For RSA, we need two primes p and q to define N = pq. We will only look how long it takes to generate a prime for p because the process is similar for q.

From my lecture slides, my professor states that the Rabin-Miller prime testing "algorithm can be made deterministic assuming the GRH (!), by running it for all a between 1 and 2(log p)2." Here, a is the arbitrary base. I couldn't find any other course material mentioning GRH, but I assume he's referring to the Generalized Riemann Hypothesis. So, assuming GRH (!) (still not quite sure what that means), we can find a prime p in O(2(log p)2). Obviously, there are enough primes where we can simply guess and check, but I wanted to mention the running time of the Rabin-Miller algorithm mentioned in my course slides.

For DH, we need a prime p and a generator g ∈ (Z/pZ)* (i.e., all of the powers gx mod p give every element in (Z/pZ)*). Finding a discrete logarithm using the Pohlig–Hellman algorithm has a worst-case runtime of O($\sqrt{p}$). Does this imply that generating a p and g will take this long in the worst case as well?

The question specifically states that generating arbitrarily large primes for DH typically takes much longer than for RSA, and I am to verify this claim. Using the worst-case scenarios above, yes, DH takes longer, but the runtimes seem similar when graphing them.

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ cs.cmu.edu/~glmiller/Publications/Papers/Mi76.pdf $\endgroup$ Commented May 1, 2024 at 15:31
  • $\begingroup$ ams.org/journals/mcom/1990-55-191/S0025-5718-1990-1023756-8 $\endgroup$ Commented May 1, 2024 at 15:31
  • $\begingroup$ en.wikipedia.org/wiki/… $\endgroup$ Commented May 1, 2024 at 15:31
  • $\begingroup$ As a quick comment, the "GRH (!)" is probably partially because the Riemann Hypothesis is not proven, so any algorithm relying on it is taking a risk, and partially because it's highlighting one of the (many!) practical consequences of a famous but rather abstract unproved theorem. $\endgroup$ Commented May 2, 2024 at 10:25

3 Answers 3

Reset to default
10
$\begingroup$

The question specifically states that generating arbitrarily large primes for DH typically takes much longer than for RSA, and I am to verify this claim.

Well, yes. In the simplest terms, to generate primes for a 3k RSA key, we need to find two 1.5k primes, but to generate the modulus for a 3k DH, we need to find a single 3k prime, and finding a 3k prime is more than twice as expensive as finding a 1.5k prime.

Of course, it is more complex than that:

  • With RSA, there are no specific requirements we place on the primes; we can pick them at random, and they'll be fine.
  • With DH, we have an additional requirement; we need to insist that the multiplicative group has a large prime subgroup (and we know the size of that subgroup).

There are a couple of different ways to handle to this subgroup requirement. One is to just pick the subgroup size first (a prime $q$ of perhaps 256 bits), and then search for a large prime $p = kq +1$ for appropriate $k$; this can be done with about the same efficiency as searching for a random prime of the same size, and so it doesn't cost us much. We can then pick an arbitrary value $h$, compute $g = h^k \bmod p$, and if $g \ne 1$, then $g$ is our generator (no solving of discrete logs needed).

Another popular method is searching for a "safe prime" of the appropriate size, that is, a prime $p$ where $q = (p-1)/2$ is also prime. This takes much longer (because for a random odd $p$, the probability that both $p$ and $(p-1)/2$ just happen to be prime is obviously considerably less than just $p$ being prime). On the other hand, the subgroup structure has nice properties (for example, any $g \ne 1, p-1$ is safe), and so that's what we do when we generate a DH group for general use.

You also make a statement:

For DH, we need a prime $p$ and a generator $g \in (\mathbb{Z}/p\mathbb{Z})^*$ (i.e., all of the powers $g^x \bmod p$ give every element in $(\mathbb{Z}/p\mathbb{Z})^*$)

Actually, we generally don't want a full generator. In fact, in the first method I mentioned (which has a moderate sized subgroup), this can actually lead to a weakness (because, given the value $g^x \bmod p$, the attacker can find the value $x \bmod q$ for all small factors $q$ of $p-1$).

Instead, we generally want $g$ to live in a decent sized prime subgroup of $\mathbb{Z}_p^*$; that avoids such weakness.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ There are in fact some requirements on the primes for RSA (they can't be too close together), but it adds essentially no cost to achieve them (and less and less likely to occur by chance as key size increases), so your general statement that DH prime generation is more expensive still holds. $\endgroup$ Commented May 1, 2024 at 22:39
3
$\begingroup$

generating arbitrarily large primes for DH typically takes much longer than for RSA

Yes. That's for several reasons

  • For comparable security, the prime $p$ in DH needs to have about as many bits as the product $p\,q$ in RSA. Thus the prime to search has twice more bits in DH; on the other hand we need two primes in RSA.

    • Twice more bits in primes makes then scarcer by a factor two, thus for the same amount of screening by sieving with small primes we need to test for primality about twice as many candidates for each prime found. This about compensates needing to search two primes in RSA.
    • Testing a candidate prime $p$ for primality by one round of the strong pseudoprime test takes effort that grows about as $\mathcal O((\ln p)^3)$ with textbook algorithms, at best like $\mathcal O((\ln p)^{2.58})$ with Karatsuba multiplication for sizes of cryptographic interest, asymptotically at least $\mathcal O((\ln p)^2(\ln \ln p))$ per Harvey&Hoeven. While in RSA we may want one more round of Rabin-Miller (thus one more strong pseudoprime test) for each prime (since they are smaller, Rabin-Miller is more likely to fail to detect a composite), the increased cost of a test (by a factor like 7) is overwhelming. Deterministic generation of primes by e.g. this method have cost that also grows fast with the prime size.

  • In RSA, it's customary to use essentially random primes (or primes with characteristics that do not make them much harder to find). In DH it's customary to use a safe prime, that is a prime $p$ such that further $q=(p-1)/2$ is a prime. That's because for $1<g<p-1$ it insures that the order of $g$ has the large prime factor $q$, thus resistance to Pohlig-Hellman. Safe primes are much rarer than primes: their density around $p$ is about $1/\ln(p)^2$ rather than $1/\ln(p)$, making them much harder to find. If we just generated prime $p$ at random then checked if $(p-1)/2$ is prime, the probability of that would be only about $2/\ln(p)$, making it necessary to generate hundreds $p$ for primes of cryptographic interest.

    Therefore, when searching safe primes, it is essential to screen the candidates $p$ by sieving with small primes $r$ so that they verify $p\bmod r\ne0$ and $(p-1)/2\bmod r\ne 0$. And that must be done for a much larger interval to compensate for the scarcity. Then for each candidate $p=2q+1$ we might want to first check if $2^q\bmod p\in\{1,p-1\}$, then check if $q$ is prime by a standard primality check such as Miller-Rabin, which is enough to insure that $p$ is a safe prime (Daniel Fischer's proof, mine with credit to Fedor Petrov's).

    Note: Safe primes are not absolutely necessary. We can also do DH with a Schnorr prime, that is $p=q\,r+1$ where $q$ is a largish prime (e.g. $q$ 384-bits, $p$ 4096-bit) which is marginally harder to find than a 4096-bit prime, and resistant enough to Pohlig-Hellman and more DLP algorithms thanks to $q$, and yet other DLP algorithms thanks to $p$. We need to choose $g$ approriately, e.g. as $g=h^r\bmod p$ for random $h$ and $g\ne1$.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ Miller-Rabin is on average much faster if you apply it to composite numbers. So if you need two related numbers to be both primes, you don't check that the first is prime (doing (ln p)^2 tests) and then the second. Instead you do one round of Miller-Rabin for each which is quite likely to find that one is composite, then a second round for each, and so on. So you take time for the two successful tests, but those where one number is composite can be done fast. $\endgroup$ Commented May 2, 2024 at 17:24
  • $\begingroup$ @gnasher729. Right, but here a Fermat or Euler test to base 2 on $p$ (as proposed in the answer) followed by Miller-Rabin test on $q=(p-1)/2$ is enough: if $q$ is prime (as the MR test suggests), then $p$ demonstrably is, without need to perform more MR on $p$. Also, AFAIK, it's not known $p$ and $q=(p-1)/2$ that both pass a strong pseudoprime test to base 2, with either $p$ or $q$ composite. $\endgroup$ Commented May 2, 2024 at 17:53
1
$\begingroup$

The complexity of generating a prime depends only on the size (bitlength) of the prime. So whether for DH or not this won't change and will be polynomial complexity (polynomial in $\log p$ see details below) not exponential complexity like breaking discrete log.

It is always the case that random generation with primality testing (whether by Miller-Rabin or similar algorithms) is the way to go for realistic sizes used in practice.

The point you make about assuming GRH, Miller-Rabin enter link description here can be made deterministic is actually moot in practice. There is a deterministic primality test (AKS test) which is somewhat less efficient than Miller-Rabin.

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ "It is always the case that random generation with primality testing (whether by Miller-Rabin or similar algorithms) is the way to go for realistic sizes used in practice"; actually, in my experience, the provably prime finding method of Shawe-Taylor is a bit faster (and, again, is provable). The downside is that not all primes can be generated by this (however it doesn't appear to be a practical problem) $\endgroup$ Commented May 1, 2024 at 13:41

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.