Encryption
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 $ 值作為區分…