If $x^e \equiv y^e \pmod N $, is $x \equiv y \pmod N$ where $\gcd(e,\phi(N))=1$?

Question

Let $x,y,e,$ $p$, and $q$ be any integers where $N= pq$ and $e$ is coprime to $(p-1)(q-1)$ . I am wondering whether $x^e \equiv y^e \pmod N $ implies $x \equiv y \pmod N$, and if so how to show this. My first thoughts were to use Fermat's little thrm, but $N$ is not necessarily prime here.

The reason why I am asking is because in RSA cryptosystem, I have learned that a potential strategy for an eavesdropper to figure out the message $x$ given the quantities $N$,$x^e$, and $e$, is to try all possible values $y$, and if $y^e \equiv x^e \pmod N$, then the eavesdropper as found $x$ in the form of $y$. I am trying to justify why the eavesdropper has actually found $x$ here, which depends on the claim I have asked about.

Answer 1

I notice that you are confused with the case where $x$ and/or $y$ may be not coprime to $N$.

---

The Euler’s theorem states that:

• For integer $m \ge 1$ and integer $a$ coprime to $m$, the following holds: $$ a^{\varphi(m)} \equiv 1 \pmod{m}. $$

For the case when $m = N = p q$ where $p, q$ are different primes, a generalization holds: For arbitrary $a$ (not necessarily coprime to $N$), $$ a^{\varphi(N) + 1} \equiv a \pmod{N}. $$

For example, when $N = 3 \cdot 5 = 15$, we have the powers of $3$ are $[1, 3, 9, 12, 6, 3, 9, 12, 6, 3, \ldots]$. We find that the $9$-th power is equal to $3$, where $9 = \varphi(15) + 1 = 8 + 1$.

---

This generalization actually tells us that we can reduce $a^k$ to $a^{k - \varphi(N)}$ as long as $k > \varphi(N)$.

Now consider when $x^e \equiv y^e \pmod{N}$.

We have such $d$ exists as the multiplicative inverse of $e$ modulo $\varphi(N)$, that is, $d e \equiv 1 \pmod{\varphi(N)}$, or equivalently, $d e = k \cdot \varphi(N) + 1$ for some non-negative integer $k$.

Raise the equality to $d$-th power:

$$ \begin{aligned} x^{d e} &\equiv y^{d e} \\ x^{k \varphi(N) + 1} &\equiv y^{k \varphi(N) + 1} \\ x^{(k - 1) \varphi(N) + 1} &\equiv y^{(k - 1) \varphi(N) + 1} \\ \vdots \\ x^{1} &\equiv y^{1} \pmod{N} \end{aligned} $$

And that’s it.

---

This generalization generalize further to:

Assume $m = \prod_{i = 1}^{\ell} p_i^{\alpha_i}$. Here all $\alpha_i \ge 1$ are required.

Then we can tell about the sequence of the powers of $a$, for arbitrary integer $a$, is:

Assume $\gcd(a, m) = \prod_{i = 1}^{\ell} p_i^{\beta_i}$. Here all $p_i$ are the same as those $p_i$’s in the factorization of $m$, and $\beta_i \ge 0$, thus $\beta_i = 0$ for some $i$ is allowed.

Then the sequence of the powers of $a$, that is, $\{ (a^j \bmod m) \}_{j = 0}^{\infty}$, goes into a period after $j_0 = \max_{i = 1}^{\ell} \Bigl\{ [\beta_i \ne 0] \Bigl\lceil \frac{\alpha_i}{\beta_i} \Bigr\rceil \Bigr\}$, and the length of the period is a divisor of $\lambda(m')$, where $m' = \prod_{i = 1}^{\ell} p_i^{[\beta_i = 0] \alpha_i}$ and $\lambda({\cdot})$ is the Carmichael function.

This criterion is quite precise. For loosening, you may note that $j_0 = 0$ when $a$ coprime to $m$, and $j_0 \le \max_{i = 1}^{\ell} \alpha_i \le \log_2 m$ when $a$ not coprime to $m$, also $\lambda(m')$ is a divisor of $\varphi(m')$ and also $\lambda(m)$, which are divisors of $\varphi(m)$.

Answer 2

I mildly disagree with what's said in the comment that it must be the other way around: That this statement holds so RSA works. The statement itself is the same as to say $x\mapsto x^e$ is injective, while RSA gives a specific (left) inverse (hence stronger).

Abstractly speaking, for any encryption and description pair $D$ and $E$, we shall have $$D\circ E = \operatorname{Id}$$

From basic set theory, we know that $D$ is surjective and $E$ is injective. In the specific case, $x\mapsto x^e$ is the encryption funciton which must be injective, hence if $x^e\equiv y^e$, then $x\equiv y$. Or just to give a direct proof: If $E(x)=E(y)$, then $$D(E(x))=D(E(y))\Rightarrow(D\circ E)(x)=(D\circ E)(y)\Rightarrow x=y$$

Therefore if we assume RSA (decryption) works, then the statement must be true.

To show RSA works, by $\gcd(e, \phi(N))=1$, we can pick $d$ such that $de\equiv 1\operatorname{ mod }\phi(N)$, hence $(x^e)^d\equiv(x^{\phi(n)})^\alpha x\operatorname{ mod } N$ for some $\alpha\in\mathbb N$. Now it suffices to show for any $x$, $$(x^{\phi(n)})^\alpha x\equiv x\operatorname{ mod } N$$ When $\gcd(x, N)=1$, we can show $x^{\phi(N)}\equiv 1\operatorname{ mod } N$ by applying Lagrange to the group $(\mathbb Z/N\mathbb Z)^{\times}$, hence the equality holds.

In general by Chinese remainder theorem, this is equivalent to $$\begin{cases} (x^{\phi(n)})^\alpha x\equiv x\operatorname{ mod } p \\ (x^{\phi(n)})^\alpha x\equiv x\operatorname{ mod } q \end{cases}$$

If $x\equiv 0\operatorname{ mod } p$ (resp. $\operatorname { mod } q$), then clearly the first (resp. second) equation holds. Otherwise, the equality can be established by $x^{p-1}\equiv 1\operatorname{ mod } p$ (resp. $x^{q-1}\equiv 1\operatorname{ mod } q$).

So you don't need to make the assumption of $\gcd(x, N)=1$. However, this assumption really doesn't hurt: The probability of $\gcd(x, N)\not=1$ is extremely small $$1-\frac{\phi(N)}{N}=1-(1-\frac{1}{p})(1-\frac{1}{q})=\frac{1}{p}+\frac{1}{q}-\frac{1}{pq}\le \frac{1}{p}+\frac{1}{q}$$

In practice, $p, q$ are usually primes of more than $1024$ bits, hence the probability is less than $\frac{2}{2^{1024}}$. Also if one happens to find a $x$ (that is not $0\operatorname{ mod } N$) such that $\gcd(x, N)\not=1$, then use Euclid algorithm to find $\gcd(x, N)$, we can find a factor of $N$, hence break RSA.