[kwantam]

The general message here is true, but I suspect that your specific example is not. Do you have a citation for the claim that PRIMEINC (generate random odd value, increment by 2 until you find a prime) caused overlapping prime factors?

The work I'm guessing you refer to on colliding prime factors is by Heninger et al., "Mining Your Ps and Qs", USENIX Security 2012 [1]. That paper does not mention anything about PRIMEINC causing this problem. The cases they found all related to bad entropy or extremely bad ways of generating moduli (like, pick two random values from a short list of known primes and use that as the modulus---an IBM product actually did this).

In fact, PRIMEINC is provably secure for generating RSA keys (though this was only shown somewhat recently): Abboud and Prest [2] analyze the distribution of outputs from PRIMEINC and show (see Section 4.1) that the security loss is negligible under quite mild conditions. Concretely, generating a reasonably sized RSA key using PRIMEINC rather than uniformly random primes reduces the security of RSA by a few bits at most.

But in some sense this reinforces your point---it was definitely not trivial to show that a tweak as seemingly simple as PRIMEINC is actually safe!

[1] https://factorable.net/weakkeys12.extended.pdf

[2] https://eprint.iacr.org/2020/815.pdf

[thomasahle]

Thank you for clearing this up! I knew I should have found my source before posting.

I remembered reading https://rjlipton.wpcomstaging.com/2012/03/01/do-gaps-between... which I suppose only says this _could_ be very bad.

Very interesting and great that it was resolved in the negative!