Msieve & Yafu - RSA 指數和暴力破解

對於 RSA 背後的數學（一般來說，相對而言），我是一個外行，我的目標是暴力破解大量 512 位 RSA 密鑰。經過四處搜尋，我發現 msieve、yafu 和 Amazon FaaS（因子即服務）程序是主要候選者，但是，使用 Amazon 破解密鑰在成本方面是不切實際的，而我想破解的密鑰（對於長時間關閉的影片遊戲，我會指定，沒有惡意），指數為 17。

簡而言之，我想知道…

1. 如果需要在模數旁邊指定指數，如果是這樣，如何實際指定指數（最好使用 msieve，因為據此它是唯一被證明可以破解這種大小的密鑰的算法），因為似乎沒有選項那個（msieve 1.53 版）。
2. 擁有多台電腦/CPU 核心是否會加快這個過程，以及如果可能的話如何使用它們（這和 msieve 自述文件似乎暗示了這種情況）。儘管上述程序是單執行緒的，但我也有點好奇它是如何通過亞馬遜在短短幾個小時內完成的。

公共指數的事實 $ e $ 是 $ 17 $ 沒有幫助。針對正確生成的 RSA 密鑰的標準攻擊（除了它們的公共模數小 $ N $ ) 是因子 $ N $ . 這是保理任務的唯一輸入，這是絕大多數工作的重點。

$ e $ 只涉及準備私鑰的最終形式，這很容易：準備私鑰的程式碼 $ e $ 和主要因素 $ p $ , $ q $ 的 $ N $ 可以生成所需格式的 RSA 密鑰的任何內容。為了 $ N(n,d) $ 格式，一個工作 $ d $ 是 $ e^{-1}\bmod((p-1)(q-1)) $ 這是 Python 中的單行程式碼：d=pow(17,-1,(p-1)*(q-1)).

在 512 位，GNFS 是首選算法，兩個常見的瓶頸是篩分和矩陣步驟。多個 CPU 絕對有助於篩分。矩陣步驟比較複雜，但是需要大記憶體的機器。

查看CADO-NFS的實現。

GPU 是否有助於分解是有爭議的，我還沒有找到任何關於 512 位實際使用的說明。

如果您有多個 $ N $ 有些是由有缺陷的程序產生的，可能會有特殊的攻擊計算GCD對 $ (N_i,N_j) $ , $ i<j $ . 當發現一個不是 $ 1 $ , 那微不足道的因素 $ N_i $ 和 $ N_j $ . 如果“長時間關閉的影片遊戲”使用了較差的密鑰生成器，那麼值得一試，在 CTF 上下文中更是如此。對此有改進，包括計算和擴展可利用的弱生成器類別；看到這個。

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