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

| improve this answer | |
$\endgroup$

Your Answer

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