Revision ac484081-4ae2-4555-9bdf-0e57ea312145

**There is consensus that it is safe to use random primes $p$ and $q$ when generating 2048-bit (or wider) RSA public moduli which two prime factors $p$ and $q$ are about half the key size**. That is sanctioned by [FIPS&nbsp;186-4][1], appendix B.3. Even though that reference requires $p-1$, $q-1$, $p+1$, $q+1$ having at least one known large prime factor when generating a 1024-bit key which two prime factors $p$ and $q$ are 512-bit, some regard this as an unnecessary complication (and I second that at least when few keys are generated).

The rationale about requiring that $p-1$ (and $q-1$) has at least one large factor is to insure resistance against [Pollard's p-1][2] factoring. The standard rationale that such precautions become pointless past a certain size is that we have factoring algorithms (including [GNFS][3] and [ECM][4]) with a much better asymptotic run time; that becomes rigorous (thus true) if we add: for any fixed odds of success [Pretty much the same applies to requiring that $p+1$ (and $q+1$) has at least one large factor, which would be in order to guard against [Williams' p+1][5] factoring; and when we do not need to guard against Pollard's p-1, we do not need to guard against Williams' p+1, thus I disregard the later].

Determining _quantitatively_ when we can dispense of precautions against Pollard's p-1 is not trivial!

- There's a line of thought that if parameters make us safe enough from ECM, we are also safe from Pollard's p-1. This _argument_ is wrong (which does not preclude that it leads to correct conclusions), at least when we consider generation of many keys in a context where an adversary would be content with factoring _any_ of $k$ keys, rather than _a_ certain key (e.g. the adversary's objective is to pass some signature check, and she knows many public key certificates of entities that can emit valid signatures, which is common in machine-to-machine applications). Counter-argument: Pollard's p-1 is _better_ than ECM from the standpoint of the ratio $\text{odds to factor}\over\text{computing effort}$ when factoring random integers (for this reason, in [GMP-ECM][6], a significant time is spent in Pollard's p-1, with [great success][7]); that extends (with comparable advantage) to factoring integers that are product of random primes of specified size; and that ratio is what matters as long a the number $k$ of keys does not becomes a limiting factor.
- There's a line of thought that GNFS is so much better than ECM that it transcends any advantage Pollard's p-1 may have over ECM for parameters of cryptographic interest. That argument works (past some point depending on the previous consideration) for RSA modulus $N$ with two prime factors of about equal size. But it does not apply when $N$ has one factor $p$ much smaller than half of $N$, which is the case in multi-prime RSA (see [PKCS#1][8]), and unbalanced RSA as in [RSAP and SPAKE/ALIKE][9], which e.g. consider a 1248-bit $N$ with a 352-bit $p$, expected to provide 80-bit security [for some definition of that; these parameters are supposed to balance GNFS and ECM]. In the following I consider these parameters.

---

As a first-order approximation, the asymptotic run time of the simplest form of Pollard's p-1 attempting to factor one $N$ (product of at least two random primes of large specified sizes), assuming standard multiplication algorithms, is $\mathcal O(B\cdot\log B\cdot \log^2(N))$ where $B$ is a parameter.

With goods odds, the algorithm succeeds or fails depending on if a prime factor $p$ of $N$ is such that $p-1$ has all its prime factors less than $B$, or not.

Odds that a large random prime $p$ has all its prime factors less than $B$ can be approximated using the [Dickman–de Bruijn function][10] as $\rho(\log(p)/\log(B))$. We could approximate that as $\rho(u)\approx u^{-u}$ [that's valid within a factor of $3$ for $u\le9$].

According to [a reputable source][11], a form of Pollard's p-1 was used to find a 189-bit factor $p$ of an at-least 595-bit number [the product of non-trivial factors of the 750-bit $5^{323}+2^{323}$], with the highest prime factor of $p-1$ a 48-bit value. I do not know the exact effort involved, but the context makes it probable that it was done with a single CPU of 2012 running for a moderate amount of time.

Thus it is not unreasonable to target $B=2^{48}$ for our 1248-bit $N$ [the $\log^2(N)$ term in the asymptotic difficulty increases it by a factor of only about $4$]. Odds that it is enough to find a random 352-bit prime $p$ are about $\rho(352/48)\approx2^{-21.7}$. With $k=2^{20}$ (about a million) target keys (thus correspondingly more work compared to our reference), odds of success becomes sizable. We have not even tried to optimize $B$; and as the saying goes: attacks only get better, they never get worse.

I conclude that for the parameters considered [moduli of 1248-bit with a 352-bit factor that has been chosen at random], it is quite reasonable to fear that trying Pollard's p-1 on all available moduli (for plausibly many of these) is a better strategy than using GNFS on a single modulus. Also, there is a formidable advantage to Pollard's p-1: the great ease of distributing the attack on independent commodity machines, when GNFS requires a heavily-connected supercomputer in the final step. Thus it is reasonable to implement measures to guard against Pollard's p-1 (and while we are at it Williams's $p+1$) with such parameters. This complicates the generation method proposed in [_SPAKE: A Single-Party Public-Key Authenticated Key Exchange Protocol for Contact-Less Applications_][12] (Financial Cryptography 2010 Workshops, pay-walled with free extract), which wants to encode identity informations in some bits of the modulus.


  [1]: http://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-4.pdf
  [2]: http://en.wikipedia.org/wiki/Pollard%27s_p_%E2%88%92_1_algorithm#Algorithm_and_running_time
  [3]: http://en.wikipedia.org/wiki/General_number_field_sieve
  [4]: http://en.wikipedia.org/wiki/Lenstra_elliptic_curve_factorization
  [5]: http://en.wikipedia.org/wiki/Williams%27_p_+_1_algorithm
  [6]: https://gforge.inria.fr/projects/ecm/
  [7]: http://www.loria.fr/~zimmerma/records/Pminus1.html
  [8]: http://www.emc.com/domains/rsa/index.htm?id=2125
  [9]: http://crypto.stackexchange.com/q/15553/555
  [10]: http://en.wikipedia.org/wiki/Dickman_function
  [11]: http://www.loria.fr/~zimmerma/records/Pminus1.html
  [12]: http://rd.springer.com/chapter/10.1007/978-3-642-14992-4_11