Rsa
如何計算破解 RSA 或 DH 所需的時間？
有時，描述一種密碼學的安全性的最簡單方法是說“解決 x 位密鑰所需的時間將是 y 年”。如何對 RSA、DH 和 ElGamal 進行這樣的計算。換句話說，給定 x，如何求解 y？
General Number Field Sieve有一個用於分解大整數的漸近公式。這是破解長度超過 400 位左右的 RSA 密鑰的最有效的已知算法（由於目前的世界紀錄是 768 位，因此 400 位 RSA 密鑰非常弱）。對於離散對數（打破 DH），最著名的算法也稱為“數域篩”，它與分解的算法非常相似。特別是，它具有相同的漸近複雜度。
但是，漸近公式不能擷取您想要的所有資訊：
- 漸近公式描述了函式的行為，它根據輸入的大小給出計算時間，對於足夠大的輸入。它說“當輸入大小向無窮大增長時，複雜性會以類似於這個公式的方式增長”。但這仍然是一個近似值，並不能保證您嘗試破解的實際 RSA 密鑰足夠大，以使漸近公式相當準確。例如，Multi-Polynomial Quadratic Sieve漸近地比 GNFS 慢；但對於 300 位整數，它實際上比 GNFS 快。這意味著 300 位整數不足以讓漸近公式準確地對因式分解算法進行評分。
- 即使公式準確，它前面也有一個隱含的乘法常數（如果您願意，可以將其命名為“每秒操作數”）。所以公式必須用實際實驗來校準。說到這一點，儘管用於分解的 GNFS 和用於離散對數的 NFS 具有相同的漸近行為，但它們沒有相同的“常數”，因此在實踐中，600 位 DH 密鑰似乎比 600 位更難破解-bit RSA 密鑰（事實上，離散對數的目前世界紀錄是“僅”530 位）。
- 時間複雜度公式只討論操作，而不描述空間要求。在 GNFS 中處理大數時，儲存空間會變得非常巨大，尤其是算法的最後一部分（“線性代數”），它是對巨大矩陣的概念上簡單的操作（高斯歸約）；實際上，該步驟受 RAM 大小和速度的限制，以及在集群中移動數據的速度。CPU 不是瓶頸，時間複雜度公式只講 CPU。
- 整個過程沒有精簡。算法有幾個步驟（多項式選擇、篩選、線性代數），雖然有很好的開原始碼，但在某些關鍵時刻仍然需要聰明人思考。要打破因式分解的世界紀錄，你需要強大的能力，還需要了解 GNFS 來龍去脈的電腦科學家，全世界可能有一百個這樣的人。
因此，估算 RSA 或 DH 密鑰的破解時間的實用方法是從已發布的整數分解記錄和離散對數記錄中推斷。
在這種“外推”方面已經做了大量工作，特別是在尋找對稱和非對稱密鑰長度之間的“等價性”（如：“1024 位 RSA 密鑰大致與 160 位散列一樣健壯）功能”）。請參閱此站點以獲取各種組織提出的最終建議的綜合摘要（帶有線上計算器和許多指針）。鑑於我上面提到的觀點，發布的建議並不真正相互匹配也就不足為奇了……
2011 年經常給出的綜合建議是：“使用 2048 位 RSA/DH/DSA 密鑰，你會在很長一段時間內沒問題。”