Suy ra một khóa bí mật từ hai khóa công khai khác nhau

Chứng minh rằng nếu hai khóa công khai RSA khác nhau $p_k$s được kẻ tấn công biết đến với cùng một khóa bí mật $s_k$, sau đó $s_k$ có thể bị phá vỡ

Tôi đã suy luận rằng nếu 2 số mũ khóa công khai là $e_1,e_2$ thì chúng có cùng số dư modulo $\phi$, nhưng điều đó vẫn không giúp tôi xác định $d$.

Đây là một câu hỏi bài tập về nhà, vì vậy tôi sẽ cho bạn một gợi ý chứ không phải câu trả lời.

Cách tiếp cận dự định thực hiện là không phục hồi $d$ trực tiếp; thay vào đó, nó là yếu tố mô đun $n$ (và một khi bạn có điều đó, phục hồi $d$ dễ).

Vì vậy, nếu bạn có giá trị $n$ và giá trị $k \phi(n)$ cho một số nguyên chưa biết $k$, làm thế nào bạn có thể yếu tố?

Một cách tiếp cận đơn giản sẽ hiệu quả nếu bạn cho rằng $k$ không phải là quá lớn. Có những cách tiếp cận thú vị hơn mà bạn không cần phải đưa ra giả định đó, nhưng tại sao bạn không bắt đầu với giả định đơn giản hóa...

(BTW: bạn thực sự có giá trị $k \lambda(n)$ vì $\lambda(n) = \text{lcm}(p-1, q-1)$, tuy nhiên điều đó không thực sự quan trọng đối với câu hỏi này ...)

Bạn nên xem cách $p_{k_1}$ và $p_{k_2}$ có nguồn gốc từ $s_k$ (hoặc cụ thể hơn là làm thế nào $e_1$, $e_2$ có nguồn gốc từ $d$). Khi bạn hiểu nó, hãy xem liệu có cách nào để suy ra mô đun của phép toán này và từ đó tính toán $s_k$.