# Cracking RSA with small plaintext

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, 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?

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.
• Put $t = m+ u\cdot k$ and see. – kelalaka Aug 16 '20 at 15:17
• 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$? – kelalaka Aug 16 '20 at 18:57