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

Question

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?

Answer 1

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.

Answer 2

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<n$ 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<n$ 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.