5
$\begingroup$

It seems that this is pretty difficult to find large (above 1024 bits) strong primes, or at least such primes $p$ where $(p-1)$ has a very large prime factor. Is there any information regarding the distribution of strong primes vs. other primes? The GNU library generates strong primes for RSA?

$\endgroup$
  • 1
    $\begingroup$ This does not answer your questions but you might find it quite interesting. crypto.stackexchange.com/questions/15744/… I had the same question some time ago and find out, thanks to the answer, that is not necessary to use strong primes for large RSA keys. $\endgroup$ – ddddavidee Nov 30 '14 at 11:58
  • 3
    $\begingroup$ FIPS 186-4, appendix B.3 contains one of several possible definitions of strong prime, and methods to generate these. $\endgroup$ – fgrieu Nov 30 '14 at 21:02
  • $\begingroup$ You may look at "Fast generation of prime numbers on portable devices: An update" (CHES 2006), doi.org/10.1007/11894063_13, for efficient algorithms. $\endgroup$ – user94293 Mar 6 '18 at 4:16
5
+50
$\begingroup$

Quoth Messrs. Rivest, Shamir, and Adleman in 1978:

To find a prime number $p$ such that $(p - 1)$ has a large prime factor, generate a large random prime number $u$, then let $p$ be the first prime in the sequence $i \cdot u + 1$, for $i = 2, 4, 6, \dots$. (This shouldn't take too long). Additional security is provided by ensuring that $(u - 1)$ also has a large prime factor.

A high-speed computer can determine in several seconds whether a 100-digit number is prime, and can find the first prime after a given point in a minute or two.

Quoth Messrs. Rivest and Silverman two decades later in 1999:

We argue that, contrary to common belief, it is unnecessary to use strong primes in the RSA cryptosystem. That is, by using strong primes one gains a negligible increase in security over what is obtained merely by using ‘random’ primes of the same size.

The latter reference also contains a handful of citations on methods for generating strong primes and their expected performance—admittedly, for numbers of somewhat smaller magnitudes, but the paper should explain why everyone may have been sapped of the motivation for more recent studies on the subject. Specifically, citing John Gordon in 1984 (whose primitive typography renders the original paper nigh illegible), they summarize:

The naive algorithm for finding a $k$-bit prime by testing random $k$-bit numbers for primality thus requires time $\Theta(k\,T(k))$. Gordon's algorithm requires finding one $k$-bit prime after finding three $k/2$-bit primes, taking a total time of $$k\,T(k) + 3(k/2)\,T(k/2) = 1.1875 (k\,T(k)).$$ This justifies Gordon's claim that finding strong primes requires only 19% more work than the naive algorithm for finding strong primes.

Gordon's analysis assumes there is nothing remarkable about the distribution of strong primes among all primes. While that's not a priori clear, any interesting properties of that distribution would likely be a remarkable result worthy of publication in a mathematics journal, at least, even if cryptographers don't care any more.

How to weigh the lack of interest of practical cryptographers against the excitement of pure mathematicians about completely useless but difficult trivia in number theory in the fine tradition of G.H. Hardy is a question I leave to the sociologists.

$\endgroup$
  • $\begingroup$ I guess that the expected performance could contain the answer to the question. I agree that strong primes are not considered all that important anymore, but I'm still missing a direct answer. $\endgroup$ – Maarten Bodewes Mar 4 '18 at 23:27
  • 1
    $\begingroup$ Without "completely useless but difficult trivia" that number theorists discovered and proved cryptography would still be in the dark ages. $\endgroup$ – kodlu Mar 5 '18 at 0:21
  • $\begingroup$ @kodlu Quite so! Hence I cannot help anyone to predict which of those forces would be more likely to win between ignoring and pursuing answers to such questions as this. $\endgroup$ – Squeamish Ossifrage Mar 5 '18 at 0:50
  • 2
    $\begingroup$ @MaartenBodewes Not a fan of Poe's literary styling, I see! (‘Quoth the Maarten, nope.’) $\endgroup$ – Squeamish Ossifrage Mar 5 '18 at 1:51
  • $\begingroup$ @SqueamishOssifrage I'm not a huge fan of classic US literature and it's not something I grew up with. I'm fan of little quips though, as long as they don't confuse matters. I'll re-edit. $\endgroup$ – Maarten Bodewes Mar 5 '18 at 9:27
5
$\begingroup$

It is not very difficult to find large strong primes.


The original RSA article recommended, for some vague definition of large, that

  • $p$ is a large prime,
  • $p-1$ has a large prime factor $p^-$ (as a protection against Pollard's p-1 factoring),
  • and $p^--1$ has a large prime factor $p^{--}$ (as a protection against the cycling attack).

Later it was added that $p+1$ has a large prime factor $p^+$ (as a protection against Williams's p+1 factoring), and a few other obscure criteria (see Ronald L. Rivest and Robert D. Silverman's Are Strong Primes Needed for RSA?).

Modern practice (in particular, FIPS 186-4) has only kept the requirements of large $p^-$ and $p^+$, or dropped them altogether because they do not guard against the generally faster algorithms that later emerged (ECM, GNFS..). It seems these large $p^-$ and $p^+$ requirements remain sensible for primes less than some bound like 512-bit, or/and multiprime RSA, but only when an adversary would be content with factoring one of extremely many public moduli (the requirements do not sizably protect one particular RSA key, only a large set of keys).

Finding such strong RSA primes requires marginally more computational effort than finding "normal" random primes, but the code is more complex. A basic method is to first choose $p^-$ and $p^+$ randomly, of the desired order of magnitude; then search odd $p$ with $p\equiv1\pmod{p^-}$ and $p\equiv-1\pmod{p^+}$. A first candidate is found using the Chinese Remainder Theorem, and others are spaced by $2\,p^-\,p^+$. A sieve can efficiently eliminate those divisible by small primes.

$\endgroup$
  • 1
    $\begingroup$ I think this is the first time I have seen the term ‘strong prime’ to mean prime of the form $p = 2q + 1$ where $q$ is prime. I'm pretty sure the original questioner was asking about notion of strong primes introduced in the seminal RSA paper. $\endgroup$ – Squeamish Ossifrage Mar 6 '18 at 3:15
  • 1
    $\begingroup$ @Squeamish Ossifrage: You are right and I was totally confused. Now I wonder what my answer brings. $\endgroup$ – fgrieu Mar 6 '18 at 20:26

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.