RSA with probable primes

I am a bit of a newbie to RSA encryption, so please be patient.

I understand that for a 4096 bit RSA, the numbers p and q should be prime. And to have the best security, the p and q should both be about 2048 bits long.

However, we don't have a way of generating and verifying a 2048 bit prime number with 100% accuracy. The implementation for prime generation that gpg uses goes through 64 rounds of miller-rabin which is enough to give a prime probability of $1 - 2^{-128}$.

Given that these primes are only probabalistically prime, what happens if we selected composite values for p or q?

Does the RSA algo run into any sort of problem?

My guess is that there will be no problem and RSA continues to function normally (encryption and decryption both) because, if there was a problem, we could use that problem as a way to detect that the numbers are not prime. This would give us a really fast way to verify extremely large prime numbers. I am guessing this is not the case.

So, my conclusion is that RSA works with prime or composite p, q... but using composite p, q makes it easy to break the encryption (because its easier to derive p, q from n).

Is this conclusion correct?

• – user991
May 24 '15 at 6:34
• Bernstein's AKS isn't actually implemented, but for real algorithms: 2048 bits is a bit over 600 digits, so about 15-30 seconds with one core for an APR-CL or ECPP proof. BPSW probable prime testing is about 7 milliseconds.. probableprime.org/images/primality-times.png. As others have pointed out, we certainly do have constructive random proven prime methods: Maurer and Shawe-Taylor to name two. May 25 '15 at 6:26
• I have a code to generate provable primes with Maurer's algorithm, see s13.zetaboards.com/Crypto/topic/7234475/1 Dec 22 '16 at 11:12

The premise "we don't have a way of generating and verifying a 2048-bit prime number with 100% accuracy" is wrong (if we trust the computers performing the operations): it has long been known practicable ways to generate randomly-seeded provable primes, and it is a (somewhat marginal) practice in RSA key generation (see FIPS 186-4 appendix B.3.2). We can even practically prove (or disprove) the primality of an arbitrary 2048-bit integer, using a number of methods, including (as pointed in comment): Daniel J. Bernstein, Proving primality in essentially quartic random time, in Mathematics of Computation 76 (2007), 389–403 (which is a randomized test giving a certainty; only the time it takes to reach certainty depends on the particular randomness used). Or better (as pointed in another comment) APR-CL or ECPP.

However this is complex, and practical cryptography is happy with a simpler probabilistic primality test. Notice that 64 rounds of Miller-Rabin test against a 2048-bit integer one have randomly drawn (which is the case in RSA key generation), rather than received from a potentially hostile party, are way overkill to rule out compositeness with residual odds less than $$2^{-128}$$; 4 rounds are more than enough, see FIPS 186-4 table C-2, with justification in appendix F and its reference: Ivan Damgard, Peter Landrock, and Carl Pomerance, Average case error estimates for the strong probable prime test, in Mathematics of Computation 61 (1993), 177–194.

If we accidentally try to perform RSA with one of $$p$$ or $$q$$ composite (because an error crept in the implementation of the primality test), the usual formulas $$\varphi(p\cdot q)=(p-1)\cdot(q-1)$$ or $$\lambda(p\cdot q)=\operatorname{lcm}(p-1,q-1)$$ will lead to an incorrect value, and with overwhelming odds, decryption or signature verification will fail on the first real use (assuming non-malicious choice of $$p$$ and $$q$$, and a random message or proper padding is used). In a PKI context, the verification by the certification authority of the public-key certification request (which is customarily self-signed) will almost certainly fail.

That's because successful use of RSA with a random message constitutes a powerful primality test of $$p$$ and $$q$$, essentially performing a Fermat test for $$p$$ and $$q$$; that is less powerful than a Miller-Rabin test, but still very effective for random $$p$$ and $$q$$. However (just as all practical primality tests for large integers), it gives an indication of compositeness, but does not reveal a previously unknown factor; that's where the reasoning/intuition in the question breaks.

More precisely, assume $$e$$ and $$d$$ follow the necessary and sufficient condition to be matching public and private exponents in two-primes RSA, that is $$e\cdot d\equiv1\pmod{\operatorname{lcm}(p-1,q-1)}$$. Equivalently $$\exists u\in\mathbb N, e\cdot d=1+u\cdot\operatorname{lcm}(p-1,q-1)$$. By setting $$v=\gcd(p-1,q-1)\cdot(q-1)$$, we get $$e\cdot d=1+u\cdot v\cdot(p-1)$$. Now if for some random $$x, we verify that $${(x^e\bmod N)}^d\bmod N=x$$ (that is, textbook RSA encryption then decryption for $$x$$ yields back $$x$$), by reducing modulo $$p$$ we see this implies $$x^{e\cdot d}\equiv x\pmod p$$, thus $$x^{1+u\cdot v\cdot(p-1)}\equiv x\pmod p$$, thus (except if $$\gcd(x,p)\ne1$$, which is improbable) $${(x^{u\cdot v})}^{p-1}\equiv 1\pmod p$$. Our RSA encryption/decryption test has performed a Fermat test for $$p$$ with witness $$x^{u\cdot v}\bmod p$$, and this witness is quite random if things are non-maliciously crafted (e.g. $$q$$ is chosen independently of $$p$$, and $$d).

An exception pointed in comment is when the composite $$p$$ that crept-in happens to be a Carmichael number. These are (rare) composites such that $$x\not\equiv0\pmod p\implies x^{p-1}\equiv 1\pmod p$$; that is, no Fermat test can detect that a Carmichael number is composite! Correspondingly, RSA will "work" with Carmichael numbers instead of primes, but will be arguably less safe than if $$p$$ was prime because $$p\cdot q$$ will be relatively easy to factor: if $$p$$ is 2048-bit, it will have at least one factor of less than 682-bit (or less if $$p$$ has more than three factors). However this won't happen by chance, because Carmichael numbers are very rare: by far the most abundant kind has three factors, and there are no more than $$x^{5/14+\mathcal o(1)}$$ of these below $$x$$ (see R. Balasubramanian and S. V. Nagaraj, Density of Carmichael numbers with three prime factors, in Mathematics of Computation 66 (1997), 1705-1708). A random 2048-bit integer has odds less than $$2^{-1300}$$ to be a Carmichael number. Hence if $$p$$ is a Carmichael number, this could only have happened by malicious intend: in addition to the primality test, the random selection of $$p$$ is intentionally flawed, and the possibility of factorization of $$p\cdot q$$ using that it has a small prime factor is a comparatively moot issue.

• Two comments: 1) in my experience, the deterministic prime generation method in FIPS 140 (based on Shawe-Taylor) is about as fast as verifying primality using a number of Miller-Rabin iterations, and 2) if you use a composite p (or q) which happens to be a Carmichael numer, RSA actually works (!). That's because the correctness of RSA depends on $x^p \equiv x \pmod{p}$, and that's true for Carmichael numbers. May 24 '15 at 16:57
• We would do practical proofs of general numbers this size with APR-CL or ECPP, not AKS or Bernstein's AKS variant. To my knowledge there is no implementation of the latter, and he points out it is slower than ECPP anyway. May 25 '15 at 6:29