Assuming that you are given the public modulus $N$, the public exponent $e$, and the private number $d_P = d\mod (p-1)$, is it possible to recover $d$?
If not, is it possible to recover $m$, also given a $c$?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
is it possible to recover $d$?
Yes, with $N, e, d_P$, you can factor $N$ (and from there, recover $d$)
If we select an arbitrary $r$, $r^{e \cdot d_P} - r \bmod n$ will have $p$ as a factor. This is because $r^{e \cdot d_P} = r \bmod p$ (as $e$ and $d_P = d \bmod (p-1)$ are inverses of each other modulo $p-1$).
In contrast, $r^{e \cdot d_P} - r$ is unlikely to have $q$ as a factor.
So, if we select a random $r$, and compute $\gcd( n, r^{e \cdot d_P} - r\bmod n )$, we will (with high probability) recover $p$, and from there, factoring $n$ and reconstructing $d$ is straight-forward.
