RSA：如果因子的最低有效位被洩露，那麼分解 N 有什麼好處？

為了 $ N=pq $ , 如果第一個 $ x $ 兩者的最低有效位 $ p $ 和 $ q $ 被洩露。

• 保理有什麼優勢 $ N $ ?
• 除了簡單地降低我們必須猜測的較小因子的位數之外，這是否具有優勢？

這個問題看起來是由於Halderman 等人的冷啟動攻擊。人。通常，研究人員會查看一些由於記憶體衰減而已知的隨機已知位。

• 2009 海寧格等。al從隨機密鑰位重建 RSA 私鑰

如果 $ \delta = .57 $ 位的一部分 $ p $ 和 $ q $ 是隨機給出的，他們可以建構它們。

最接近的文章是 Maira 等人的文章。人。

• 2010 - Maitra Factoring RSA Modulus Using Prime Reconstruction from Random Known Bits，也是其中一位作者的幻燈片。

在第 2 節和第 3 節中，他們著眼於 LSB 案例。與定理1；

定理 1：讓 $ N = pq $ ， 什麼時候 $ p, q $ 是相同位大小的素數。讓 $ S = {0,\ldots, l_{N /4}} $ . 考慮 $ U \subseteq S $ 和 $ V = S \backslash U $ . 假設 p

$$ i $$是為了 $ i \in U $ 和 $ q[j] $ 是為了 $ j \in V $ 是已知的。然後可以考慮 $ N $ 在 $ poly(\log N) $ -時間。

• $ l_N $ 位大小 $ N $ ， IE， $ l_N = \lceil log_2 N\rceil $ .

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