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.



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

| improve this answer | |
  • $\begingroup$ 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. $\endgroup$ – Asaf Jun 12 '19 at 14:46
  • $\begingroup$ @Asaf Can you separately find ${x_i}^b \equiv x_i \pmod{p_i}$, and then combine them? $\endgroup$ – Squeamish Ossifrage Jun 12 '19 at 14:59
  • $\begingroup$ 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. $\endgroup$ – Asaf Jun 12 '19 at 16:46
  • $\begingroup$ @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$? $\endgroup$ – Squeamish Ossifrage Jun 12 '19 at 16:52
  • $\begingroup$ that $0 \le x_i \lt p_i$, because $p_3 = 3$ so I have to check only $x=2$? $\endgroup$ – Asaf Jun 12 '19 at 17:01

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.