如果 Eve 知道密鑰是共享質數並且知道它們的公鑰，則恢復 3 個私鑰，這將如何完成？
好的，這是原來的問題：
Alice Bob 和 Carl 正在為 RSA 生成公鑰，但他們很懶，決定分享一些生成素數的工作。他們找到 3 個大素數 p、q 和 r，然後 Alice 使用模數 $ n_A = pq $ , Bob 使用模數 $ n_B = pr $ 卡爾使用模數 $ n_C = qr $ . 使用的素數非常大，因為分解是可行的，但是 Eve 知道它們共享素數（並且知道他們的公鑰）她如何獲得 p、q 和 r？
我對這個問題的想法或可能的推理。由於 Eve 知道公鑰並且這些密鑰共享素數，因此她可以計算 n 的 GCD 或分解 n 以計算或找到私鑰。在這種情況下，她將首先使用歐幾里得算法 $ n_A = pq $ & $ n_B= pr $ 我們知道是 p 因為兩個 n 共享一個共同的素數 $ p $ . 她將使用相同的過程進行計算 $ q $ 這是 $ n_A = pq $ & $ n_C = qr $ . 她第三次為 $ r $ 哪個 $ n_B = pr $ & $ n_C = qr $ .
我想知道我是否以正確的方式思考這個問題，或者我是否有正確的想法。如果我在正確的軌道上，我如何在數學上表示這一點？
是的，你的想法是正確的！計算時使用“共享素數” $ n_A $ 和 $ n_B $ 僅僅通過它揭示的事實對安全是災難性的 $ p $ , $ q $ ， 和 $ r $ 打了幾通電話 $ gcd $ 算法。
幸運的是，使用良好的隨機性這極不可能發生。在 512 位 RSA 的情況下，大致有 $ 2^{503} $ 512 位素數，當使用生日界限時，大約等於 $ \sqrt[2][2*2^{503}log(1/(1-0.5)] \approx 6.02520 * 10^{75} $ 生成的素數需要達到 50% 的碰撞機率。