# Is there a pseudo message that will encrypt and decrypt correctly if one of the primes is a pseudo prime in RSA

For prime number generation, one can use a probabilistic prime number generation algorithm like the Miller–Rabin primality test that will yield a composite as a probable prime with probability $$\frac{1}{4^r}$$ for $$r$$ rounds. If we use $$r=50$$, this has probablity $$2^{-100}$$. This is enough to believe that it is prime due to the high probability, if the collective power of Bitcoin miners is not searching a candidate, we will not see one around.

What if we want to make sure that it is 100%? We can use the deterministic AKS primality test and its faster variants to see that it is prime or it was a pseudoprime for the Miller-Rabin. AKS primality test, however, is very slow, and that is why we use probabilistic methods.

Now, instead of AKS, we want a faster approach and use it in the RSA cryptosystem to encrypt and decrypt a message. If everything works we will assume it is prime (should we?)!

Take a well-known prime like Fermat or Mersenne primes call it $$p$$ and the pseudo-prime (a real one can be found if we use fewer rounds but assume that we found one with 50 rounds) and call it $$\bar{p}$$. Construct the RSA as usual with the exception that instead of choosing firstly $$e$$ then finding primes, choose a suitable $$e$$.

1. $$n = p \cdot\bar{p}$$
2. $$\varphi{(n)} = (p-1)(\bar{p}-1)$$, (actually we can use $$\lambda{(n)}$$)
3. find $$e$$ such that $$\gcd(e, \varphi(n)) = 1$$
4. find $$d \equiv e^{-1} \pmod{\varphi(n)}$$

and the rest is textbook RSA encryption and decryption.

Question(s):

1. We expect that the encryption will fail since the incorrect $$\varphi(n)$$. Is there a pseudo message that correctly encrypts and decrypts under this pseudoprime $$\bar{p}$$?
1. If, so, how we can find one?
2. If, so, what is the probability of the pseudo messages?

1. We expect that the encryption will fail since the incorrect $$\varphi(n)$$.

Not always; for example, consider the case $$p=31$$ (a Mersenne prime) and $$\bar{p} = 561 = 3 \times 11 \times 17$$. We'll set $$e = 13$$ and $$d = e^{-1} \bmod 30 \times 560 = 3877$$.

Then, if we pick a random message $$m=2$$, then $$2^e \bmod n = 8192$$, and $$8192^{3877} \bmod n = 2$$; encryption and decryption works just fine. Actually, it turns out that any value $$m$$ will encrypt and decrypt properly with this particular $$n, e, d$$ set.

Lets try it again with another random example; this time we'll pick a Fermat prime $$p=17$$ and an arbitrary $$\bar{p} = 91 = 7 \times 13$$, and so $$n= 1547$$. This time, we'll use $$\lambda(n) = (p-1)(\bar{p}-1) / \gcd( p-1, \bar{p}-1 )= 720$$; we'll pick $$e=7$$ and so $$d=e^{-1} \bmod \lambda(n) = 103$$. Again, if we pick a random message (we'll try $$m=3$$ this time, we have $$3^e \bmod n = 640$$ and $$640^d \bmod n = 3$$. And, again, any $$m$$ will encrypt and decrypt properly with this particular $$n, e, d$$ set.

So, how did this work? Did I just pick these examples at random? Is this always true of Fermat and Mersenne primes? Well, no, for this trick, I selected my $$\hat{p}$$ values carefully, and most everything else was arbitrary.

In the first case, I selected $$\hat{p}$$ to be a Carmichael number, that is, a composite number such that $$\lambda(\hat{p})$$ is a factor of $$\hat{p}-1$$. It turns out that a Carmichael number acts just like a prime as far as RSA is concerned; any $$p$$ (relatively prime to $$\hat{p}$$ would make it work).

In the second case, I selected a $$\hat{p}$$ that wasn't a Carmichael number (561 happens to be the smallest), but instead it is something we may call a "semicarmichael number" (terminology I just made up, so don't bother googling it); it has the property that $$\lambda(\hat{p})$$ is a factor of $$2(\hat{p}-1)$$. Now, these numbers won't always work within RSA, however it does work if either $$p \equiv 1 \bmod 2^{k+1}$$ (where $$2^k$$ is the largest power of 2 which is a divisor of $$\hat{p}-1$$), or alternatively you use the $$\phi(n)$$ relation of $$e, d$$ (rather than the $$\lambda(n)$$ relation - for primes and Carmichael numbers, it doesn't matter - for semicarmichael numbers, it does).

So, what does this stage magic trick relate to your question:

If, so, what is the probability of the pseudo messages?

Higher than you'd expect, if you did a number of rounds of Fermat or Miller-Rabin beforehand. It turns out that Carmichael numbers will always fool Fermat (unless you happen to pick a generator that's not relatively prime to the Carmichael number), and semicarmichael numbers will fool Fermat half the time. And, both these numbers have good probability of fooling Miller-Rabin (obviously $$< 1/4$$, however sometimes not much less). Hence, while Carmichael and semicarmichael numbers are rare, if you have a composite number that fools several rounds of Fermat or MR, the probability you started with such a number is pretty good.

I'll assume $$\gcd(p,\bar p)=1$$ (which is likely for random $$p$$, and easily verifiable). Therefore, per the CRT, a message $$m$$ with $$0\le m encrypts/decrypts correctly if and only if $$m^{e\,d}\equiv m\pmod p\tag{1}\label{fgr1}$$ and $$m^{e\,d}\equiv m \pmod{\bar p}\tag{2}\label{fgr2}$$.

From the construction of $$e$$ and $$d$$, it holds $$e\,d=i\,(p-1)+1$$ and $$e\,d=j\,(\bar p-1)+1$$ for some integer $$i$$ and $$j$$. Per the FLT, just as in RSA, the former implies that $$\eqref{fgr1}$$ holds for all integers $$m$$.

Define the set $$\mathcal V$$ to be the subset of $$[0,\bar p)$$ which elements $$m$$ satisfy $$\eqref{fgr2}$$. This set $$\mathcal V$$ depends on $$\bar p$$, and to a degree may depend on $$e\,d$$, thus on $$e$$ and on how $$d$$ is selected.

Per the usual CRT formula in RSA, the set $$\mathcal M$$ of message $$m$$ with $$0\le m that encrypt/decrypt correctly is precisely the set of $$m=((\bar p^{-1}\bmod p)(u-v)\bmod p)\,\bar p+v\tag{3}\label{fgr3}$$ for all $$(u,v)\in[0,p)\times\mathcal V$$. Instead of $$\eqref{fgr3}$$ we could also use $$m=((p^{-1}\bmod \bar p)(v-u)\bmod\bar p)\,p+u\tag{4}\label{fgr4}$$.

This tells $$|\mathcal M|$$ is a multiple of $$p$$. And the probability of hitting one for a random $$m$$ is precisely $$\mu=|\mathcal V|/\bar p\tag{5}\label{fgr5}$$.

Since $$\{0,1,\bar p-1\}\subset\mathcal V$$, it holds $$|\mathcal M|\ge3\,p$$, and $$\mu\ge2/\bar p$$.

Thus we can answer the question's 1 and 1.1: yes there are messages that correctly encrypt and decrypt, and we exhibited some. So far, vanishingly few. But that's before we invoked that $$\bar p$$ is a pseudoprime!

Define the set $$\mathcal W$$ to be the subset of $$[0,\bar p)$$ which elements $$w$$ satisfy $$w^{p-1}\equiv1\pmod n$$; that is, bases $$w$$ making $$\bar p$$ a Fermat pseudoprime. It holds $$(\mathcal W\cup\{0\})\subset\mathcal V$$, and $$\{1,\bar p-1\}\subset\mathcal W$$.

The stronger pseudoprimes are Carmichael numbers A002997. When $$\bar p$$ is one of these, $$\mathcal W=\mathbb Z_\bar p^*$$, and therefore is most of $$[1,\bar p)$$, thus $$\mu$$ is close to $$1$$.

Without proof, I observe $$\mu=1$$ when $$\bar p$$ is a Carmichael number (which are vanishingly rare, including among pseudoprimes), and then some other pseudoprimes, including some Fermat pseudoprimes to base 2 A001567 (e.g. $$\bar p=997633$$); and that $$\mu$$ is sizable for more classes of pseudoprimes.

Thus we can answer the question's 1.2 by: there exists pseudoprimes $$\bar p$$ making $$\mu=1$$, and more making it a non-vanishing value.