0
$\begingroup$

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.

$\endgroup$

1 Answer 1

1
$\begingroup$

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

$\endgroup$
12
  • $\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, 2019 at 14:46
  • $\begingroup$ @Asaf Can you separately find ${x_i}^b \equiv x_i \pmod{p_i}$, and then combine them? $\endgroup$ Jun 12, 2019 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, 2019 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$ Jun 12, 2019 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, 2019 at 17:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.