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?

  • $\begingroup$ Note that, while use of Miller-Rabin is certainly common, it is not universal; there are other ways of generating primes that are used in practice... $\endgroup$ – poncho Nov 1 '17 at 12:48

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.

| improve this answer | |
  • $\begingroup$ 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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.