GCD 在 2019 年反擊 RSA - 好的隨機性是唯一的解決方案？
當有人收集大量 RSA 公共模數時，首先想到的是；
$$ \text{GCD them all} $$
如果您計算兩個不同 RSA 模數的 GCD，如果結果不是 1，那麼您會找到其中一個因素。這已經在積極研究
- 2012 - 海寧格等。al探勘你的 Ps 和 Qs：檢測網路設備中普遍存在的弱鍵
這些研究人員收集了 580 萬個唯一的 TLS 證書和 620 萬個唯一的 SSH 主機密鑰。在合併的集合中，有 1100 萬個不同的 RSA 模數，它們能夠分解 16,717 個不同的公鑰。即破壞 23,576 (.4%) 的 TLS 證書和 1,013 (.02%) 的 RSA SSH 主機密鑰。
- 2012 - 倫斯特拉等。al Ron 錯了，Whit 是對的
他們在 Internet 上收集了 620 萬個數字證書，發現其中大約 4.3% 的證書與另一個證書完全共享其 RSA 模數。
- 2013伯恩斯坦等。al，從經過認證的智能卡中提取 RSA 密鑰：Coppersmith in the wild
研究人員調查了包含超過 200 萬個 RSA 模數的台灣國家“公民數字證書”數據庫。他們有效地分解了 184 個不同的 RSA 密鑰。他們注意到一些素數出現的次數比 p110 出現的次數多 46 次。原因是某些智能卡中的隨機數生成器存在缺陷。
- 2016 - Hasting 等人，弱密鑰在網路設備中仍然普遍存在
為了查看供應商和最終使用者的反應，作者檢查了 8100 萬個不同的 RSA 密鑰，並能夠分解出 313,000 個密鑰 (0.37%)。他們發現來自華為、D-Link 和 ADTRAN 的大量新設備很容易受到攻擊。
- 2016 年巴布列斯庫在。網際網路上提供的RSA弱公鑰
他們在 2015 年 12 月 22 日至 2016 年 1 月 7 日期間爬取了 GitHub SSH-RSA 密鑰。它們只是 512 位的因子 1。他們還分析了一個包含 2048 位 RSA 的勒索軟體數據庫，該數據庫沒有任何弱點。
從 2012 年收集的原始 X.509 證書中，他們測試了 26177420 個 1024 位 RSA 密鑰，發現有 63502 個（0.25%）密鑰被分解。
- 2018 - N. Amiet 和 Y. Romailler，來自 Kudelski 的研究人員，大規模獲取和破解密鑰：當加密遇到大數據時。
他們收集了 3.4 億個 RSA 密鑰，其中 21 萬個被破解。1600 個密鑰中的 1 個密鑰容易受到Chapel編寫的 batch-gcd 的攻擊。
最近；
- 2019 - KeyFactor Factoring RSA Keys in the IoT Era 的研究人員
他們在 2015 年至 2017 年期間從網際網路上抓取了 7500 萬個 RSA 證書，總共有 25 萬個可能被完全破解。也就是說，172 個股票中有 1 個股票是一個因子。
防止共同因素的一種解決方案是公共數據庫。這是可下載的，以便人們可以使用 GCD 測試他們的新模數。當然，這樣的數據庫還有另一個問題。一些攻擊者可以利用導致相同素數生成的原因，即隨機過程。在任何情況下，攻擊者都可以作為研究人員抓取他們的數據庫。
問題：
- 如果我們考慮使用 RSA-2048 並假設我們需要 10 億個 RSA 模數，一個好的隨機數生成器可以解決這個問題嗎？
- 如果我們只考慮 1024 位數字，我們至少可以選擇兩次素數的機率是多少？
- 為什麼我們不在不同的位域中生成素數，例如 1024,1025,1026,1027 位，…
解決方案只是確保您具有良好的隨機性。在我們正在考慮的數字大小下，使用良好隨機性時重複的機率非常小。為了說明這一點，有很多 $ 2^{1000} $ 長度為 1024 的素數。當使用真正的隨機性時，在選擇的任何合理數量的素數處重複的機率是如此之小，以至於不值得考慮。更準確地說，如果我們生成 $ t = 2^{50} $ 長度為 1024 的隨機素數（即 1,000 萬億），則重複的機率小於 $ \frac{t^2}{2^{1000}} = 2^{-900} $ .
真正的隨機性並沒有那麼有用，因此 NIST 的建議是為您的 PRG採用您正在尋找的位安全*長度的兩倍的隨機種子。*因此，假設 RSA-2048 是 128 位安全性的（據估計它實際上有點低，但我們在這裡忽略該細節）。然後，您應該使用 256 位真正的隨機種子，並在基於 AES-256 之類的 PRG 中使用它。在這種情況下，即使生成了數千萬億個密鑰，獲得重複的機會仍然基本上為 0。同樣，更準確地說，機率的上限為 $ \frac{t^2}{2^{256}} = \frac{2^{100}}{2^{256}} = 2^{-156} $ .
主要挑戰是如何確保使用良好的隨機性。在沒有任何獨特之處的工廠線上生產相同的設備要便宜得多，也更容易。在這種情況下，每個設備稍後都需要自己生成其密鑰，而最簡單的事情還是讓它使用自己的內部狀態。這行不通。最好的選擇是在生產過程中在每個設備中寫入一個新的隨機 256 位種子（在工廠中，擁有一台具有真正隨機生成器的機器可以生成寫入設備的種子，這根本不是問題） . 如果不這樣做，則需要某種方式將好的種子安全地傳送到設備。也可以“添加”任何可以在本地生成的熵，但這不能是主要來源。