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$
$\endgroup$
1
-
$\begingroup$ Thanks for cheating in rarctf. :) $\endgroup$– rak1507Commented Aug 9, 2021 at 20:05
Add a comment
|
4 Answers
$\begingroup$
$\endgroup$
2
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$– user94159Commented Aug 8, 2021 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$ Commented Aug 8, 2021 at 16:40
$\begingroup$
$\endgroup$
1
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 ♦Commented Aug 9, 2021 at 17:07
$\begingroup$
$\endgroup$
${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.
$\begingroup$
$\endgroup$
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)$
