從私有指數和公共指數計算 RSA 公共模數
如果我知道私人和公共指數（ $ d $ 和 $ e $ ) 的 RSA 密鑰對，是否可以（有效地）計算公共模數 $ n $ ?
總結：發現 $ n $ 從 $ (e,d) $ 對於一小部分實際感興趣的 RSA 密鑰（包括模數太大而無法分解），在計算上是可行的，具有公平的機率，甚至是確定的。
我會假設
- 未知 $ n=p,q $ 和 $ p $ 和 $ q $ 類似數量級的未知不同大素數，比如說 $ \max(p,q)<2\min(p,q) $ .
- 給定 $ (e,d) $ 與小 $ e $ （例如 5 個費馬素數之一）。
- 一個已知的 $ d=e^{-1}\bmod\varphi(n) $ （通常在教科書 RSA 中）或 $ d=e^{-1}\bmod\lambda(n) $ （如FIPS 186-4中）成立。
從它們各自的定義可以看出 $ \varphi(n)=(p-1)(q-1) $ 和 $ \lambda(n)=\varphi(n)/g $ ， 和 $ g=\gcd(p-1,q-1) $ .
它擁有 $ h,(p-1)(q-1)=(e,d-1) $ 或者 $ h,(p-1)(q-1)=g,(e,d-1) $ 對於一些未知的 $ h<e $ , 和一個 $ g $ 可以通過列舉找到，因為它是一個小的偶整數，通常 $ 2 $ （總是在一些密鑰生成策略中），很少高於 $ 10 $ .
在我們可以充分考慮的情況下 $ e,d-1 $ ，這將留下無數的選擇來重新安排其因素到 $ p-1 $ , $ q-1 $ 和 $ h $ . 給定大小和素數限制 $ p $ 和 $ q $ ，剩下的可能性很少，通常只有一個。 $ n $ 跟隨。
這有時可以在獲得最佳分解的情況下起作用 $ e,d-1 $ 是部分的，但我們很幸運，剩下的大型複合材料的所有因素都在一個單一的 $ p-1 $ 或者 $ q-1 $ . 只有當剩餘的複合小於 $ \max(p,q) $ ，然後只有低機率。
方法起作用的鍵的比例取決於模數大小，取決於我們願意嘗試考慮的程度 $ e,d-1 $ ，以及關於素數如何 $ p $ 和 $ q $ 已經生成（特別是：隨機生成的，或具有較大的已知素數） $ p-1 $ 和 $ q-1 $ 考慮到Pollard 的 p-1分解。在後一種情況下，該因素的大小將很重要。如果高（例如素數位大小的 60%），則任務會很困難；但典型的參數化較低）。
分解策略可能類似於任意整數的分解策略：
- 拉小因素 $ e,d-1 $ 由審判部門。
- 通過Pollard 的 rho拉出更多的小因素
- 可選但有些有利的是，一些Pollard 的 p-1。
- 可選但仍然有些有利的是，一些威廉的 p+1。
- 很多ECM，當我們勉強夠用的時候，大部分的努力應該是 $ (e,d) $ 對希望找到一個允許成功的人。
- 也許，如果需要考慮的大型複合材料仍然存在，MPQS或GNFS。
插圖，基於最近分解的 829 位 RSA-250 。
我們得到 $ e=65537 $ 以及以下 828 位 $ d $ 已知是 $ d=e^{-1}\bmod\varphi(n) $ .
1219002363472329316632678572665837077877528004905520939230037996503041169769564562618818603930146413036298872224725717654149810234132887053185714832075764978825457518728410705223332728199047961645304133836997233492855592278022423674340390891560261753我們計算 844 位 $ m=e,d-1 $ , 並取出它的小因素 $ 2^3\times3\times5\times13\times6221\times6213239\times440117350342384303 $ （那是幾秒鐘），留下一個 740 位 $ m_1 $ 因素。
該命令¹
ecm -pm1 1e7 <m1找到了一個 73 位因子 $ 8015381692860102796237 $ 在 <3 秒內，留下 667 位 $ m_2 $ 因素。該命令
ecm -pp1 1e7 <m2找到了一個 67 位因子 $ 101910617047160921359 $ 在 <7 秒內，留下 600 位 $ m_3 $ 因素。該命令
ecm -pp1 1e8 <m3找到了一個 72 位因子 $ 4597395223158209096147 $ 在 <77 秒內，留下 528 位 $ m_4 $ 因素。我們需要考慮到這一點 $ m_4 $ , 因為它仍然太大而不能成為的除數 $ p-1 $ 或者 $ q-1 $ . 該命令
ecm -pm1 3e8 <m4在 ≈85 秒後失敗。該命令ecm -pp1 1e8 <m4在 ≈69 秒後失敗。在 ≈272 秒後，在多個核心上重複啟動的命令ecm 1e8 <m4反复失敗。如果這行得通，我們會非常幸運。我並沒有真正考慮到 $ m_4 $ 使用 GNFS²，但這是觸手可及的。的因素 $ m_4 $ 是 276 位和 253 位（下面列表中的前兩個）
$ p-1 $ 和 $ q-1 $ 是偶數，因此我們有這 12 個因素可以分開 $ (p-1)/2 $ , $ (q-1)/2 $ 和 $ h $ :
72769022935390028131583224155323574786067394416649454368282707661426220155269516297 11015842872223957032465527015746975907581857223611379316467045416408679146689 8015381692860102796237 4597395223158209096147 101910617047160921359 440117350342384303 6213239 6221 13 5 3 2有一個單純的 $ 3^{10}<2^{16} $ 在我們將前兩個條目分配給之後探索的可能性 $ (p-1)/2 $ 和 $ (q-1)/2 $ . 我們想探索那些 $ \max(p,q)<2\min(p,q) $ 和 $ h<e $ . 修剪這棵樹只需要添加近似對數。這是一個近乎微不足道的背包問題。我沒有編碼，但如果有解決方案產生，我會感到驚訝 $ p $ 和 $ q $ 素數以外的 $ h=2\times3\times6221 $ ， 還有這些 $ p $ 和 $ q $ 立即產生 $ n=p,q $ ，這裡是 RSA-250。
33372027594978156556226010605355114227940760344767554666784520987023841729210037080257448673296881877565718986258036932062711 64135289477071580278790190170577389084825014742943447208116859632024532344630238623598752668347708737661925585694639798853367¹ GMP-ECM實現了精心優化的 Pollard 的 p-1、William 的 p+1和ECM。我讓它使用隨機種子，因此某些結果可能需要執行幾次才能重現。
² 我聽到了很多關於CADO-NFS實施的好消息。