80 位安全性和攻擊時間
許多設計師聲稱他們的密碼方案具有 80 位安全性。那麼如何計算攻擊這種 80 位安全密碼方案的時間，例如使用一種 CPU 的 80 位安全 RSA 呢？
這個問題主要歸結為：
做什麼 $ n $ -位安全意味著在實踐中對於給定的值 $ n $ ?
TL;DR：與良好的對稱密碼一樣安全 $ n $ 位密鑰。
沒有一個更精確的定義，即使我們限制使用經典電腦（而不是量子電腦）的攻擊者，就像這個答案一樣。
一種普遍接受的含義是，打破系統的“步驟”數被認為是 $ 2^n $ ; 或者更準確地說，打破系統的機率 $ s $ “步”不知道多於 $ s,2^{-n} $ 通過任何方法對任何 $ s $ . 然而，“steps”和“break”並沒有精確定義。
在對稱加密的理論中，“步驟”通常被視為使用新密鑰執行密碼的一次。這樣一來，理想密碼的密鑰為 $ n $ 位有 $ n $ -位安全，在暴力密鑰搜尋下。當我們開始實踐時，攻擊者不一定會暴力破解密鑰搜尋，並且“步驟”的定義必須成為在數量和計算成本上與執行一次所需的子步驟相當的子步驟。用新密鑰加密密鑰大小的明文。有了這個定義，一個具有密鑰的實用密碼 $ n $ 比特最多 $ n $ 位安全，並以此為目標。
當我們轉向散列時，一個步驟的定義可能會變成許多子步驟，其數量和計算成本與散列新消息所需的子步驟相當，雜湊輸出的大小。
上述問題的其中一個問題是，對於我們是否應該在計算成本中計算記憶體和記憶體訪問的成本並沒有達成一致意見。從使用者的角度來看，安全的事情不是計算它，但這對於攻擊者來說可能是最重要的。
當涉及到像 RSA 這樣的非對稱加密時，“步驟”的定義變得更加模糊。理論上，“步數”可能是用於密碼系統的代數結構中的一種計算；例如，對於 RSA，模乘法的一種評估 $ (a,b)\mapsto a,b\bmod N $ 對於任意整數 $ a $ 和 $ b $ 在 $ [0,N) $ ， 在哪裡 $ N $ 是公共模數。但是將其付諸實踐存在一些問題，特別是對於 RSA：最著名的攻擊是分解公共模數 $ N $ 使用GNFS算法，其計算成本以與模乘幾乎沒有相似性的操作為主，而實際成本以記憶體和對記憶體的訪問為主。這使使用回到 TL;DR 中的模糊定義。
如何計算攻擊這種 80 位安全密碼方案的時間，例如使用一種 CPU 的 80 位安全 RSA？
“80 位安全 RSA”不應理解為具有 80 位公共模數的 RSA $ N $ ，這是最終不安全的。如果我們有大小 $ N $ ，我們可以根據該經驗和以前的經驗來估計難度（請參閱此及其連結）。但我們沒有，而且在規模上也沒有共識 $ N $ 對於具有 80 位安全性的 RSA：經常引用 1024 位，但取決於假設以及您問的人，這太多或太少了。因此，最好的辦法是忽略我們正在談論的 RSA，並回到：用 80 位密鑰破解一個好的對稱密碼所需的時間。
這使我們： $$ \text{Time}=\frac{2^n\times k\times p}{\text{Frequency}\times\text{Number-of-CPUs}} $$ 在哪裡 $ n $ 是以位為單位的安全級別， $ k $ 是對使用超優化算法評估良好密碼的 CPU 週期數的估計，以及 $ p $ 是對手成功的剩餘機率。根據我們可能採取的觀點 $ k=1 $ （省去了檢查細節）， $ k=32 $ （因為這仍然比使用通用電腦對良好密碼的最佳攻擊要少），或者更多。根據不同的觀點，我們可以採取 $ p=1 $ （從合法使用者的角度來看是最謹慎的）， $ p=1/2 $ （在分組密碼的情況下產生預期時間），或更小的 $ p $ 如果我們想要安全邊際¹。
例如，與 $ n=80 $ , $ k=1 $ , $ p=1/1000\approx2^{-10} $ , $ \text{Frequency}=4\text{GHz}\approx2^{32}\text{s}^{-1} $ , $ \text{Number-of-CPUs}=1000\approx2^{10} $ ，我們得到 $ \text{Time}\approx2^{80-10-32-10}\text{s}=2^{28}\text{s} $ ，也就是大約 8 年。換句話說，我們的 1000 個 CPU 對抗 80 位對稱加密的成功機率很小，直到它們在技術上過時。
另一方面，1000 個 CPU 只是全球 CPU 的一小部分，而比特幣探勘最終表明，80 位加密不再足以對抗具有設計 ASIC、大規模建構它們的能力並維持能源成本的對手。他們的操作；看到這個。
¹ 的 $ p $ 從合法使用者的角度來看，公式中的術語是最謹慎的，但它會導致 $ \text{Time} $ 在許多攻擊場景中被低估。例如，在碰撞搜尋中，正確的術語應該更像 $ \sqrt p $ .