暴力破解 RSA 需要多少計算資源？
自 Rivest、Shamir 和 Adleman 首次公開描述他們的公鑰密碼算法以來，已經過去了 30 多年。情報界被認為已經知道它大約 40 年——可能更久。
可以公平地假設，在這 40 年中，某些三字母組織已經利用其大量資源來“破解”RSA。一種蠻力方法可能是列舉每個可能的密鑰對，這樣，在遇到已知使用特定公鑰加密的消息時，他們只需要查找關聯的私鑰即可解密該消息。簽名可以類似地偽造。
這個假設有多合理？在這 40 年中，列舉每個可能的 {1024,2048,4096} 位密鑰對需要多少計算資源？我認為最好避免討論，而將幽靈是否可以利用這種資源作為練習的問題留給讀者。
這是不可能的。
小於的素數個數 $ x $ 大約是 $ \frac{x}{\ln x} $ . 因此數 $ 512 $ 位素數（大約是您需要的長度 $ 1024 $ 位模數）大約為：
$$ \frac{2^{513}}{\ln 2^{513}}-\frac{2^{512}}{\ln 2^{512}} \approx 2.76×10^{151} $$ 因此，RSA 模數（即兩個不同的素數對）為：
$$ \frac{(2.76×10^{151})^2}{2}-2.76×10^{151}=1.88×10^{302} $$ 現在考慮可觀測宇宙包含大約 $ 10^{80} $ 原子。假設您可以將這些原子中的每一個用作 CPU，並且這些 CPU 中的每一個都可以每毫秒列舉一個模數。列舉所有 $ 1024 $ 您需要的位 RSA 模數：
$$ \begin{eqnarray*} 1.88×10^{302}ms / 10^{80}&=&1.88×10^{222}ms\ &=&1.88×10^{219}s\ &=&5.22×10^{215}h\ &=&5.95×10^{211} \text{years} \end{eqnarray*} $$ 只是作為一個比較：宇宙大約是 $ 13.75×10^9 $ 歲。
這不是資源問題，根本不可能。
此外，這樣做沒有任何意義。有很多更快的方法可以找到密鑰。事實上，有一些算法具有亞指數執行時間來分解整數。