Deducerea unei chei secrete din două chei publice diferite

Arată că dacă două chei publice RSA diferite $p_k$sunt cunoscute unui atacator pentru aceeași cheie secretă $s_k$, atunci $s_k$ poate fi spart

Am dedus că, dacă cei 2 exponenți ai cheii publice sunt $e_1,e_2$ atunci au același rest modulo $\phi$, dar asta tot nu mă ajută să determin $d$.

Ar trebui să aruncați o privire la cum $p_{k_1}$ și $p_{k_2}$ sunt derivate din $s_k$ (sau mai concret cum $e_1$, $e_2$ sunt derivate din $d$). Odată ce ați înțeles, vedeți dacă există o modalitate de a deduce modulul acestei operații și din aceasta calculați $s_k$.

Aceasta este o întrebare pentru acasă, așa că vă voi da un indiciu, nu răspunsul.

Abordarea intenționată este să nu se recupereze $d$ direct; în schimb, este factorul de modul $n$ (și odată ce ai asta, recuperându-te $d$ este usor).

Deci, dacă ai valoarea $n$ si valoarea $k \phi(n)$ pentru un număr întreg necunoscut $k$, cum ai putea factor?

O abordare simplă ar funcționa dacă presupuneți $k$ nu este prea mare. Există abordări mai sofisticate în care nu trebuie să faci această presupunere, dar de ce nu începi cu presupunerea simplificatoare...

(BTW: de fapt ai valoarea $k \lambda(n)$ pentru $\lambda(n) = \text{lcm}(p-1, q-1)$, cu toate acestea, asta nu contează cu adevărat pentru această întrebare...)