1
$\begingroup$

it might be a silly question but i need help please

given RSA system , where $n=pq , p\ and \ q \ are \ primes $ , $ v_0,v_1,v_2, v_3 \ are \ known $

$p^p \equiv v_0 \mod q$

$q^q \equiv v_1 \mod p$

$q^p + p^q \equiv v_2 \mod pq$

$(p+q)^{p+q} \equiv v_3 \mod pq$

Mathmatical facts:

$p^{q-1} \equiv 1 \mod q$

is obtained using $\phi(q)=q-1$ , Fermat: $p^{\phi(q)} \equiv 1 \mod q$

$q^{p-1} \equiv 1 \mod p$

$q^p + p^q \equiv p+q \mod pq$

is obtained using $(p^{q} \equiv p \mod pq) + (q^{p} \equiv q \mod pq)$

$(p+q)^{p+q} \equiv p^{p+q}+ q^{p+q} \mod pq$

Edit : The solution from https://ctf-wiki.github.io/ctf-wiki/crypto/asymmetric/rsa/rsa_theory/#2018-national-security-week-pure-math

is $q=\frac{v_3-v_0*v2}{v_1-v_0}$ where you can rewrite as

$q=\frac{p^{p+q}+ q^{p+q} -p^p*(q^p + p^q)}{q^q-p^p}= \frac{p^{p+q}+ q^{p+q} -p^{p+q}-(pq)^p }{q^q-p^p}= \frac{q^{p}*(q^q-p^p) }{q^q-p^p} = q^p = q $

I can prove this backward how is calculated but what is the fundamental idea that used to bring the above equation?

$\endgroup$

closed as off-topic by tylo, kelalaka, AleksanderRas, Maeher, Squeamish Ossifrage Sep 19 at 18:49

This question appears to be off-topic. The users who voted to close gave this specific reason:

If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ I voted to close this, because it is just a copy&paste of the homework question. $\endgroup$ – tylo Sep 19 at 12:20
  • $\begingroup$ It is not homework question, a hint will be helpful $\endgroup$ – hardyrama Sep 19 at 14:01
  • $\begingroup$ The issue is not, if this was an actual homework assignment to you specifically. The issue is, you just copied the question and wrote "help me" - with 0 effort from your side. At the very least, you should state what you tried and where you got stuck. If you did not do that: Try on your own first. $\endgroup$ – tylo Sep 19 at 14:59
  • 1
    $\begingroup$ A hint to get you started: Write $p=q+a$ and replace all $p$ with that. And use the laws you were given below, while respecting the different modulus. It should be obvious, where you can apply which rule. BTW: I don't know if it works, it's just an idea. Without any effort on your side, I don't see a reason to think about this much. $\endgroup$ – tylo Sep 19 at 15:06

Browse other questions tagged or ask your own question.