| Can you expand on the applicability of Prime and Prejudice [1] to RSA key generation? As far as I can tell, the two have nothing to do with one another. The point of the Prime and Prejudice paper is, in effect, that the Miller-Rabin primality test should only be applied to random prime candidates, not adversarially chosen ones. The reason is: for a random composite, each M-R iteration has probability roughly 1/4 of revealing that the number is indeed composite. But it is possible to find composites that fool M-R with high probability. The upshot is: if an adversary is proposing primes to you, be very careful about using M-R! For RSA key generation, unless you're worried about your RNG (in which case you're sunk anyway, to a first approximation), candidate primes are not adversarially chosen. So, as this article says, it does not appear that Prime and Prejudice is an issue for RSA key generation. As further evidence for this, the Prime and Prejudice paper does not talk about vulnerabilities in RSA key generation. The issues that it describes have to do with validating prime-field DH parameters provided to a client by a potentially adversarial TLS server. As far as I can tell, the P&P paper only mentions RSA three times: twice as name-checks and once in the name of a library. This isn't a defense of any other claim in the article. But as far as I can tell, P&P is not an issue in the context of RSA key generation. [1] https://eprint.iacr.org/2018/749 |