Cryptography
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$$?

Solution

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) and $$kq+n\mathbb Z$$ (for $$0) 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!

• +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

External links referenced by this document: