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$

Question

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.

Answer 1

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$?