Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
Factoring a 2048 bit number is a difficult topic with a well known complexity.
But it seems that p, q, the prime numbers used in RSA (order of magnitude: 10^308) are generated thanks to the probabilistic primality Miller Rabin test. Indeed even a table of primes between 10^307 and 10^308 would be out of reach.
Is RSA vulnerable to the potential specific arithmetic properties (if any) of the primes generated during the pseudo random number generator + Miller Rabin process?
RSA is vulnerable to poor choice of the primes of the modulus, and there are quite a few examples of that: RNG that generates the same output on different calls (see CVE-2008-0166, smartfacts and an example in usenix 2016's best paper); or dubious mathematical shortcut to make the generation faster (see the Roca attack).
It is much less common that a bad implementation of the primality test cause disaster, because a single iteration of a correct implementation of the Miller-Rabin test is actually quite solid when the number generated is random (see FIPS 186-4 appendix F); and accidentally choosing a non-prime would most often be caught on the first use of the RSA key: an RSA encryption/decryption is a Fermat primality test for its factors, and this has excellent chances of catching a composite.
choosing a non-prime would most often be caught on the first use of the RSA key: I'm not sure to understand: if RSA can catch a composite, then in a way, it's a primality test (you also mentioned this), then why don't we use it instead of Miller Rabin?
$\endgroup$
– Basj
Nov 11 '17 at 21:57
