# RSA given n % (q-1)

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?

• Thanks for cheating in rarctf. :) 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)\,.$$

• 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?
– user94159
Aug 8 at 16:22
• 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. 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)

• 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.
– 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)$$