2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Imagine that the secret message you wanted to encrypt happened to be equal to $X$, what would it get encrypted to? $\endgroup$ – Matthew Towers May 6 at 9:26
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ You might just find factors of $k$ instead... $\endgroup$ – Henno Brandsma May 9 at 21:51
  • $\begingroup$ @HennoBrandsma thanks, I think, in the worst case $X$ is equal to a divisor $t$ of $k$ and $X^{E-1}-1,n$ is equal to $tn$. $\endgroup$ – kelalaka May 10 at 13:13

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.