8
$\begingroup$

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?
$\endgroup$
15
$\begingroup$
  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.

| improve this answer | |
$\endgroup$
4
$\begingroup$

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.

| improve this answer | |
$\endgroup$

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.