Is $X^{E} \equiv X \;(\text{mod}\; n)$ a potential problem in the RSA cryptosystem?

186 Views Asked by At

This is Exercises 11 from Section 7.3 of the book "Abstract Algebra: Theory and Applications" (aata-20180801) by Thomas W. Judson.

Find integers $n$, $E$, $X$ such that $$ X^{E} \equiv X \;(\text{mod}\; n). $$ Is this a potential problem in the RSA cryptosystem?

What does the "potential problem" mean in this problem? Is it related to the Iterated Encryption Attack described in this article?

1

There are 1 best solutions below

2
On

Assume that you find integers $n$, $E$, $X$ such that $$ X^{E} \equiv X \;(\text{mod}\; n). $$ Then;

$$ X^{E} -X = k \cdot n \quad\text{ for some } k\in \mathbb{Z}.$$

Take out $X$

$$ X ( X^{E-1} -1) = k \cdot n \quad (= k \cdot p \cdot q)$$

Now, calculate $\gcd(X,n)$ and $\gcd(X^{E-1} -1,n)$.

If you are lucky, you might find $p$ and $q$.