# RSA - plaintext equal ciphertext

Just started learning about RSA cryptography so forgive me if I made any mistakes or misunderstandings.

n = 1024-bit integer (product of two large primes p*q)
e = 65537 (standard exponent)


However I also have some ciphertext all encrypted with the same keys.

c1 = m1e MOD n
c2 = m2e MOD n
...
ck = mke MOD n

Among these there is a particular ciphertext.

c = me MOD n
m == c
m == mek MOD n
So ek - 1 is a multiple of ϕ(n)?

If not mistaken, therefore, it is possible to derive the following equations.

me ≡ m MOD n
me - m ≡ 0 MOD n
me - 1 ≡ 0 MOD n
me - 1 ≡ 0 MOD (p*q)

me - 1 ≡ 0 MOD p AND me - 1 ≡ 0 MOD q

Knowing all these strange characteristics, is there any way to obtain the private key and consequently be able to decrypt the other ciphertexts?

• Critic 1: From $m≡m^{(e^k)}\pmod n$ it can't be concluded that $e^k-1$ is a multiple of $ϕ(n)$; the implication is in the other direction. Critic 2: You can go from $m^e-m\equiv0\pmod n$ to $m(m^{e-1}-1)≡0\pmod n$, but from there you can't quite conclude that $m^{e-1}≡1\pmod n$, much less that $m^{e-1}≡0\pmod n$ as in the question. Hint: but from $m(m^{e-1}-1)≡0\pmod n$ you can go to $m(m^{e-1}-1)≡0\pmod p$ and $m(m^{e-1}-1)≡0\pmod q$, and then it's at least possible that one the two equations holds because $m≡0\pmod p$ or $m≡0\pmod q$. Assuming that, it's easy to factor $n$. Else, well…
– fgrieu
Commented Apr 2, 2023 at 15:40

is there any way to obtain the private key and consequently be able to decrypt the other ciphertexts?

Sometimes. A fuller answer involves number theory (but to understand why RSA works, you really need to know the basics anyways).

First off, a definition: the order of a value $$a$$ (modulo $$p$$) is the smallest positive integer $$x$$ such that $$a^x \equiv 1 \pmod p$$. The value $$a \equiv 0 \pmod p$$ doesn't have an order (it's not considered an element in the multiplicative group $$\mathbb{Z}_p^*$$); all other values have an order (assuming $$p$$ is prime).

Now, if we have $$m^e = m \pmod {pq}$$ (where $$pq=n$$, expressed as its prime factors), then we know that:

• Either $$m = 0 \pmod p$$, or the order of $$m$$ modulo $$p$$ is a divisor of $$e-1$$

• Either $$m = 0 \pmod q$$, or the order of $$m$$ modulo $$q$$ is a divisor of $$e-1$$

Now, if either $$m = 0 \pmod p$$ or $$m = 0 \pmod q$$, then a simple computation $$\gcd(m, n)$$ reveals the factorization (unless both are true, in which case we have $$m = 0$$; we can't deduce anything from that).

The other case is if both have orders; if the two orders are different, say, $$x$$ and $$y$$ (with $$x < y$$), then a simple computation of $$\gcd( m^x - 1, n )$$ reveals the factorization.

On the other, if the two orders are the same, well, the knowledge of $$m$$ doesn't reveal a factorization.

And, because $$e$$ is typically small, $$e-1$$ is easy to factor, hence it is practical to test $$\gcd( m^x - 1, n )$$ for all divisors $$x$$ of $$e-1$$

Now, there are some simplifications: to test if $$m$$ is order 1 (either modulo $$p$$ or $$q$$), we can just compute $$\gcd( m - 1, n )$$ (and if both sides have that order, that corresponds to $$m = 1$$)

And, for the order $$2$$, it turns out we can compute $$\gcd( m + 1, n )$$ (and if both sides have that order, that corresponds to $$m = n-1$$)

In most cases, computing $$\gcd(m, n), \gcd(m-1, n), \gcd(m+1, n)$$ is sufficient to recover the factorization; however the fuller test will catch some more cases.