I read a CTF writeup about cracking 4 primes RSA numbers from here: Given $p, q, r,$ and $p+q+r$ are prime numbers.

The challenge encrypts the flag with a modulus $N=(p∗q∗r)∗(p+q+r)$

and gives the output $n=pqr, k=p+q+r$. To totally break the cryptosystem, we would want to find the totient of the modulus $\varphi(N)=(p−1)(q−1)(r−1)(p+q+r−1)$

but we can simplify this when the encrypted message $m$ is small enough. If we have $m<k$, we can instead find $\varphi(k)=k−1$, and find $e^{-1}\bmod{\varphi(k)}$, and solve!

But how can they replace $p*q*r*(p+q+r)$ with only $(p+q+r)$ and somebody explains that part?


1 Answer 1


We have given $c = m^{17} \bmod (N=pqrk)$ with $k = p+q+r$

We can write this as $$m^{17} = c + \ell (pqr)k$$ for some integer $\ell$.

Now consider this as $$m^{17} = c + (\ell pqr)k$$

if $m < k$ you can find the $m$ if not information is lost and the answer is not unique.

  • $\begingroup$ can you give an example or explain more the part where you say: if not information is lost and the answer is not unique $\endgroup$
    – haxerl
    Aug 16, 2020 at 15:15
  • 1
    $\begingroup$ Put $t = m+ u\cdot k$ and see. $\endgroup$
    – kelalaka
    Aug 16, 2020 at 15:17
  • $\begingroup$ i still don't understand why do we need the constraint m < k for this to work $\endgroup$
    – haxerl
    Aug 16, 2020 at 18:01
  • 1
    $\begingroup$ It will not give the correct answer. you will get it's residue mod $k$ and which one will be the answer. $m+u\cdot k$? $\endgroup$
    – kelalaka
    Aug 16, 2020 at 18:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.