Solving system of equation based on RSA

Since this is a past CTF we can provide a guide to solve it.

Euler's theorem states that if $\gcd(m,n) =1$ with $m,n \in \mathbb{Z}^+$ then

$$m^{\varphi (n)} \equiv 1 \pmod{n} \label{5}\tag{1}$$

and $\varphi$ is Euler's totient function. In the case of $n= pq$ where $p$ and $q$ are distinct primes $$\varphi (n) = (p-1)(q-1)$$

Now, a little arithmetic;

\begin{align} \varphi (n) &= (p-1)(q-1)\\ \varphi (n) &= pq-p- q +1\\ \varphi (n) &= n - p - q +1\\ \end{align}

Now use this on equation $\ref{5}$

$$m^{n - p - q +1} \equiv 1 \pmod{n}$$

The rest should be obvious.

$$\frac{m^{n}\cdot m}{m^p\cdot m^q} \equiv 1 \pmod{n}$$

The rest should be more obvious.

$$m \equiv \frac{m^p\cdot m^q}{m^{n}} \pmod{n} \label{lab1}\tag{2}$$ People working on CTF can directly use equation $\ref{lab1}$.

To reach this, however, we need to make sure that $m^n$ has an inverse to modulo $n$.

The only elements that are non-invertible are $kp+n\mathbb Z$ (for $0<k<q$) and $kq+n\mathbb Z$ (for $0<k<p$) since to have inverse one must have $\gcd(a,n) =1$ and this is not the case for the multiples of $p$ and $q$ ( actually, there are exactly $\varphi(n)$ invertible elements in $\mathbb Z$.
Therefore $m^n$ is invertible iff $ p \nmid m$ or $q \nmid m$. For this, the blow SageMath code is verification that for some $m$, there is no inverse of $m^n$.

The rest is a big spoiler since it includes SageMath code!! To see it, you need to edit this answer.

Since this is a CTF, one can make sure that the CTF organizers selected the $m$ invertible so that CTF players can have solutions!

Solved by user18298 (44,255 )
Sep 03, 2022 at 16:16