State of the art RSA key generation

Question

I would like to know if there is an algorithm to generate a RSA key at the state of the art of the present cryptanalysis.

Beside the key lenght I know there are some weakness in the choice of prime numbers that could help an attacker to factor the modulus $N$.

The standard key generation, as far as I know, generate a random number of the right lenght, tries to factorise it dividing it by small factors (say $\leq 10000$) and then one or more primality test (as Fermat and Miller-Rabin) until the confidence level is high enough.

But what about risks that $p-1, q-1$ are with small factors?

Answer 1

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 186-4, appendix B.3; specifically, wording in B.3.1 item A:

Using methods 1 and 2 [yielding provable (1) and probable (2) random primes], $p$ and $q$ with lengths of 1024 or 1536 bits may be generated; $p$ and $q$ with lengths of 512 bits shall not be generated using these methods. Instead, $p$ and $q$ with lengths of 512 bits shall be generated using the conditions based on auxiliary primes.

Even though FIPS 186-4 requires (in the second part of this quote) that $p-1$, $q-1$, $p+1$, $q+1$ have at least one known large prime factor when generating a 1024-bit key which two prime factors $p$ and $q$ are 512-bit, many regard this as an unnecessary complication.

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 factoring. The standard rationale that such precautions become pointless past a certain size is that we have factoring algorithms (including GNFS and ECM) 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 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}$ for low computing effort when factoring random integers (for this reason, in GMP-ECM, a significant time is spent in Pollard's p-1, with great success); 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 become the 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), and unbalanced RSA as in RSAP and SPAKE/ALIKE, 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].

Answer 2

Generation of prime numbers is just madness by crypto gurus. My guess is that no prime will be strong enough, or safe enough if you follow all the recommendations.

not be close to a power p = k^j + r   with |r| small
p-1/2  must have a large factor
((p-1/2)-1)/2  must have a large factor
(p+1)/2  must have a large factor

avoid p = k*q + r   with |r| small

not be at the end or the start of a large prime gap, 
i.e.  p - r and p + s with |r| and |s| small are also acceptable primes

and of course, p - q > |r|  with r at least a certain amount of bits
(this implies the trap p != q for which RSA does not work)

make sure p is not a pseudoprime.
do not forget that miller-rabin tests work only if gcd(base, p) == 1 and base != p
when running multiple miller-rabin tests, make sure the different basis
are co-prime, else a pseudoprime could escape with an unacceptable 
high probability.

ensure log2(p*q) == log2(n) by ensuring log2(p*p) == log2(q*q) == log2(n) 

and so on, and so on. All the recommendations do have some ground. They might not be all necessary. Some famous recommendations apply to unpractical attacks.

All known practical failures are related to weak randomness, or protocol failures, or implementation bugs exposing the computer memory and possibly key material.

Simple advice : Just follow the standard blindly. Document that you follow the standard strictly. If there is a weakness, it will be published, you will know it, corrections will be published and you know how to detect and fix the problem.

If the standard suggest that it is secure to use primes made from randomness from an approved generator, as suggested in the other answer, then this is the state of the art.