rsa modular-arithmetic
Updated Tue, 04 Oct 2022 09:48:19 GMT

Solving system of equation based on RSA

I have got 4 variables $n$, $x$, $y$, and $z$:

Here, $n = p\cdot q$ with $p$ and $q$ are distinct primes

\begin{align} x &= m^p \bmod n\\ y &= m^q \bmod n\\ z &= m^n \bmod n\\ \end{align} How can I find $m$?


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!

Comments (2)

  • +1 – Our community Guide on Capture the flag questions. Why the downvote? Could downvoter explain the reason for this? — Sep 04, 2022 at 08:28  
  • +0 – Moderator note: an appropriate place to make that explanation seems to be a new answer to the meta-question linked. [update] There is such new answer. — Sep 04, 2022 at 08:39