當複雜性形式為212821282^{128}
在我閱讀的許多密碼分析論文中，攻擊複雜性以常數的形式表示。例如，對 AES狀態的相關密鑰攻擊：
$$ … $$對於 AES-256，我們展示了第一個適用於所有密鑰的密鑰恢復攻擊，並且具有 $ 2^{99.5} $ 時間和數據複雜度
我見過這個符號 $ 2^{n} $ 其他論文的時間也是如此。但是，我不清楚將哪個基本操作作為“時間”測量的基線？底層模型當然不是圖靈機，那是什麼？對於其他算法，大 O 表示法通常隱藏常數因子，使得精確的基本操作成為不重要的細節。但是密碼學論文準確地說明了複雜性，這讓我感到驚訝。
對於其他算法，大 O 表示法通常隱藏常數因子，使得精確的基本操作成為不重要的細節。但是密碼學論文準確地說明了複雜性，這讓我感到驚訝。
您感到驚訝是對的——通常，由於所謂的線性加速定理，寫“精確複雜性”是沒有希望的——我們只能將計算複雜性限制為任意乘法因子。這是因為我們總是可以將底層字母表的大小增加一些常數因子，以允許我們在單位時間步長上計算更多的操作。這（有點）有一個實用的組件——您可以增加指令集架構的大小以在每個時鐘週期進行更多計算（以使用更多矽片的晶片為代價）。
那麼人們使用什麼成本指標呢？這真的取決於應用程序。例如，一個著名的 AES 攻擊是Biclique Attack，它恢復了複雜的 AES 密鑰 $ 2^{126.1} $ . 當然，作者並不傾向於將任意數字作為他們的結果——他們如何計算這個？
獨立 biclique 方法的完整復雜性評估如下： $$ C_{full} = 2^{n−2d}[C_{biclique} + C_{precomp} + C_{recomp} + C_{falsepos}], $$ 在哪裡
- $ C_{precomp} $ 是步驟 3 中預計算的複雜度。它相當於小於 $ 2^d $ 子密碼的執行 $ g $ .
- $ C_{recomp} $ 是內部變數重新計算的複雜度 $ v $ $ 2^{2d} $ 次。它在很大程度上取決於密碼的擴散特性。對於 AES，此值從 $ 2^{2d−1.5} $ 至 $ 2^{2d−4} $ . 在這個範例中，biclique 結構相當便宜。3.1 節中的方法只能在 $ 2^{d+1} $ 子密碼呼叫 $ f $ . 因此，通常完整的密鑰恢復複雜度將由 $ 2^{n−2d}C_{recomp} $ . 但是，它取決於匹配變數的寬度和 biclique 維度 $ d $ 也。我們將在後續部分中提供有關 AES 案例的更多詳細資訊。密鑰恢復的記憶體複雜度上限為儲存 $ 2^d $ 密碼的完整計算。
特別是對於 AES，他們然後說
總之，我們需要一個等價的 $ 3.4375 $ SubBytes 操作（即 55 個 S-box）、2.3125 個 MixColumns 操作以及密鑰調度中的可忽略的 XOR 數量。SubBytes 計算的數量顯然是一個更大的總和。S-box 也是 AES 在硬體和軟體方面的實際複雜性的主要貢獻者。**因此，如果我們的目標是一個單一的數字來表示複雜性，那麼計算我們需要的 SubBytes 操作的數量並將其與完整密碼中的數量進行比較是有意義的。**後面的數字是 $ 10 + 2.5 = 12.5 $ 因為我們必須考慮到關鍵調度非線性。因此， $ C_{recomp} $ 相當於 $ 2^{16}\times 3.4375/12.5 = 2^{14.14} $ 執行完整的 AES-128。價值 $ C_{biclique} $ 和 $ C_{precomp} $ 一起不超過 $ 2^8 $ 完整的 AES-128 呼叫。完整的計算複雜度約為 $ 2^{112} (2^7 + 2^7 + 2^{14.14} + 2^8) = 2^{126.18} $ .
這就是說 biclique 攻擊的“原始操作”是 SubBytes 呼叫的數量，其中一個規範化的東西使得蠻力攻擊將採取 $ 2^{128} $ 複雜性。
當然還有其他復雜性的概念。例如
- 我聽說過“面積 x 時間”度量標準，它根據一定大小的電路完成攻擊所需的時間來衡量攻擊的複雜性（但現在找不到參考資料），
- 同樣，攻擊通常會同時測量一些計算複雜度的概念以及一些記憶體/樣本複雜度的概念，
- 在基於格的密碼學中，稱為“核心 SVP 計數”的某個度量在分析中相當流行。
但總的來說，因為根本不明顯 $ 2^{128} $ 原始操作意味著（例如），由作者來定義這些術語，所以他們通常會這樣做。