# Plain RSA with $3$ primes, find all integers $x$ so that $x$ is equal to $y$ when $y= e_K(x) = x^{b} \bmod n$

I'm using the notation from the book: Cryptography: Theory and Practice, Third Edition.

I have a cryptosystem with the following information:

$$n = p_1 p_2 p_3$$ and integer $$x$$ is encrypted using $$y = e_K(x) = x^b$$ $$mod$$ $$n$$ and the decryption is $$x = d_K(y) = y^a \bmod n$$ when $$ab\equiv 1 \pmod{\varphi(n)}$$

$$n=231$$, so: $$p_1 = 11$$, $$p_2 = 7$$, $$p_3 = 3$$

I want to find all $$x$$ so $$x= e_K(x) = x^b \bmod{231}$$

I tried this:

$$x^b-x \equiv 0 \pmod{231}$$

$$x(x^{b-1}-1) \equiv 0 \pmod{231}$$

$$x = 0$$, $$x = 1$$ are solutions, to find the rest:

$$\varphi(231)=120$$ so $$ab\equiv 1\pmod{120}$$ but I don't know how to continue.

Since $$120=2^{3}\cdot3\cdot5$$ so $$2\nmid{b}$$ and $$3\nmid{b}$$ and $$5\nmid{b}$$

by following the RSA page from wikipedia: key generation:

$$\lambda (231)=30$$, so $$1 \lt b \lt 30$$, the only integers that left from $$1, 2, \ldots, 30$$ are primes. then using Fermat's little theorem implies that for any integer $$a$$: $$a^{p} \equiv a\pmod p$$ so,

I tried to check CRT, CRT implies that $$e_K(x) = x$$ iff $$x^b \equiv x \pmod{p_i}$$ for $$i=1,2,3$$.

But I still don't know how to continue.

Thanks.

If I understand correctly, you are looking for the integers $$x$$ such that, for all $$b$$, $$x^b \equiv x \pmod n$$.
You almost have it! You've correctly identified $$x = 0$$ and $$x = 1$$ as solutions. If you had a solution $$x$$, what can you say about $$x_i := x \bmod p_i$$ for each $$p_i$$—how are $$x_i$$ and $${x_i}^b$$ related modulo $$p_i$$? Can you use the solutions $$x = 0$$ or $$x = 1$$ modulo $$n$$ as inspirations to find solutions modulo $$p_i$$ and recombine them into solutions modulo $$n$$?
• How do I use solutions $x=0$ or $x=1$ for that? Using CRT, $x^b\ \equiv x \pmod{11}$ and $x^b\ \equiv x \pmod{7}$ and $x^b\ \equiv x \pmod{3}$, treating it like system of congruences and $N_1 = 231/3 = 77$, $N_2 = 231/7 = 33$, $N_3 = 231/11 = 21$ so a solution of the system of congruences is $$x^b = \sum_{i=1}^3 x\cdot M_i \cdot N_i$$ and $M_1 = 2$, $M_2 = 3$, $M_3 = 10$ so, $x^b = (x \cdot 2\cdot 77 + x \cdot 3\cdot 33 + x \cdot 10\cdot 21) = 463 \cdot x$. I don't understand how to continue. – Asaf Jun 12 '19 at 14:46
• @Asaf Can you separately find ${x_i}^b \equiv x_i \pmod{p_i}$, and then combine them? – Squeamish Ossifrage Jun 12 '19 at 14:59
• By using the fact that $0 \le x \lt 231$ and $1 \lt b \lt 30$ to check all the possible $x$ that ${x_i}^b \equiv x_i \pmod{p_i}$? I don't understand. – Asaf Jun 12 '19 at 16:46
• @Asaf If ${x_i}^b \equiv x_i \pmod{p_i}$ for prime $p_i$, what can you say about $x_i \bmod p_i$? – Squeamish Ossifrage Jun 12 '19 at 16:52
• that $0 \le x_i \lt p_i$, because $p_3 = 3$ so I have to check only $x=2$? – Asaf Jun 12 '19 at 17:01