0
$\begingroup$

It is mentioned here that the public value $N=p*q$ of the RSA cryptosystem can be factorized if one of the factors is reused. Thus, if $N_1=p*q_1$ and $N_2=p*q_2$ and only $N_1$ and $N_2$ are known, then one can factor $N_1$ and $N_2$.

I wasn't able to come up how this can be achieved. Is that statement really true?

$\endgroup$

1 Answer 1

2
$\begingroup$

Since $p$ is a factor in both $N_1$ and $N_2$ you can simply calculate $p$ by using Euclid's algorithm.

Once you have $p$ you can then calculate $q_1$ and $q_2$ (simply divide $N_1$ by $p$ to get $q_1$ and divide $N_2$ by $p$ to get $q_2$).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.