1
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • $\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 at 15:15
  • 1
    $\begingroup$ Put $t = m+ u\cdot k$ and see. $\endgroup$ – kelalaka Aug 16 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 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 at 18:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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