RSA中的因子計算

給你 $ d\bmod(p-1) $ , $ d\bmod(q-1) $ , $ \operatorname{invert}(p,q) $ 和 $ p\bmod2^{200} $ ，公共指數是 $ e=65537 $ .

$ \operatorname{invert}(p,q) $ 是的答案 $ p*x \equiv 1 (mod\quad q) $

$ d $ 是私有指數，模數未知。

有什麼方法可以計算 $ p $ , $ q $ ?

給你 $ d \bmod(p−1) $ ..，公共指數是 $ e=65537 $ . 有什麼方法可以計算 $ p $ ?

好吧，我們知道 $ d_p = d \bmod p-1 $ 和 $ e $ 與 $ d_p \cdot e = 1 + kp $ , 對於某個整數 $ k $ ， 然後 $ k < 65537 $

所以，做一個部分因式分解 $ d_p \cdot e - 1 $ 進入 $ a \cdot b $ ， 在哪裡 $ a $ 由低於 65537 的因子和 $ b $ 沒有這樣的因素（這很容易）。我們知道 $ p = (a/c) b $ ， 在哪裡 $ c $ 是一個因素 $ a $ ; $ a $ 相對較小，因此只需要考慮幾個這樣的因素。因為我們知道

$ p \bmod 2^{200} $

很容易區分它是哪一種。

而且，對於問題的另一半：

有什麼要計算的嗎 $ q $

我們可以使用相同的技巧，除了使用已知的 $ p^{-1} \bmod q $ 值作為區分…

引用自：https://crypto.stackexchange.com/questions/92005