I am trying to work out an RSA challenge where I am given n, e, c and the result of

n mod (q-1)

However, I can't wrap my head around the maths. Could anyone help?

  • $\begingroup$ Thanks for cheating in rarctf. :) $\endgroup$
    – rak1507
    Aug 9 at 20:05

We can use the same trick as in this previous answer: since we have the value $n \bmod (p-1)$, $n - n \bmod (p-1)$ is going to be $0$ modulo $p-1$, that is, a multiple of $p-1$, and having a multiple of $p-1$ leads to a factorization of $n$ by computing $$ p = \gcd\left(n, \left(2^{n - n \bmod (p-1)} \bmod n\right) - 1\right)\,. $$

  • $\begingroup$ Thank you! This is very helpful. I was wondering if you could explain the maths in the second bracket - why it is 2 to the power of n-n mod (p-1), mod n? $\endgroup$
    – user94159
    Aug 8 at 16:22
  • 4
    $\begingroup$ It's a consequence of Fermat's little theorem: $a^{p-1} \equiv 1 \bmod p$. So $a^{p-1} \bmod p - 1$ is going to be $0$ modulo $p$, so it will have $p$ in common with $n$ as a divisor. I picked $a = 2$ as the base arbitrarily, it could be anything. I should also note that when you do arithmetic modulo $n$, you're doing it "in parallel" modulo $p$ and $q$ at the same time. So all of the properties of the integers modulo $p$ are preserved, including Fermat's little theorem. $\endgroup$ Aug 8 at 16:40

n mod (q-1) is equivalent to p*q mod (q-1) = p * (q-1 +1) mod (q-1) = p * (q-1) + p mod (q-1) = p mod (q-1)

  • 1
    $\begingroup$ Right, knowing $n\bmod(q-1)$ is the same as knowing $p\bmod(q-1)$. And if $p<q$, that's $p$, making factrization of $n$ trivial. However, if $p>q$, we need something more. $\endgroup$
    – fgrieu
    Aug 9 at 17:07

${n (mod (q-1)) \equiv p \cdot q (mod(q-1)) \equiv p (mod(q-1)) \cdot q (mod(q-1)) \equiv p (mod(q-1))}$

  • now if p>q then it will be in the coset generated by p mod(q-1)
  • for ex. p=23 and q=13 , p x q=299, 299 %12= 11 , hence coset generated by p mod (q-1) is {11,23,35,..}

  • however we can use ${ n- \phi(n)+1 = p\cdot q -(p-1)(q-1)+1=p+q}$, and taking modulo (q-1) can land us to same result.

Though there are a few good answers already I think something longer is in order.

From Fermat's little theorem we know $a^{p-1} mod p = 1$ and due to exponentiation rules $a^{(p-1)*k} mod p = (a^{(p-1)})^k mod p = 1^k mod p = 1 mod p$

If we have $n$ and $n\space mod (q-1)$ we can calculate n - n mod (q-1) which will obviously be congruent to 0 mod q-1. So we know n - n mod (q-1) = k * (q-1)

Hence $2^{n-n \space mod(q-1)} \equiv 1 \space mod \space q $

We can actually calculate this only mod n, but that is Ok, because n=pq anything we do mod n will preserve result mod q.

So we calculate $2^{n-n \space mod(q-1)} \space mod \space n \equiv 1 (mod \space q)$

subtract 1 to get 0 mod q which means. $2^{n-n \space mod(q-1)} \space -1 mod \space n = c*q$

And we have n=pq, so we can calculate $gcd(pq,cq)=q$

And together: $gcd(n,(2^{n-n \space mod(q-1)}\space mod \space n) -1) = q$

Thus factorizing n, and then we can find the secret key $d=e^{-1}\space mod (p-1)(q-1)$


Your Answer

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