蠻力搜尋的複雜性

我目前正在考慮對密碼進行暴力攻擊的複雜性。設密碼的密鑰長度為 64 位。然後有 $ 2^{64} $ 鍵空間中的不同鍵。如果您進行蠻力搜尋，則在中間您將不得不搜尋 $ 2^{63} $ 成功的關鍵。所以我現在的問題是，攻擊的複雜性是什麼？是嗎 $ 2^{64} $ 或者 $ 2^{63} $ ? 我不確定。

正是 $ 2^{64} $ . 您需要尋找所有可能的密鑰以成功進行暴力破解。一個人不能保證鑰匙會在一半， $ 2^{63} $ ，你要搜尋。在 CS 中，有一個對手的論點，即對手總是可以迫使你做出最壞的情況。告訴他你是怎麼搜尋的，他會拿出一個你找不到的案例 $ 2^{63} $ 鍵空間。

實際上， $ 2^{63} $ 是您在暴力破解過程中找到鑰匙的平均情況。

如果您有多個具有加密不同密鑰的已知明文，那麼通過多目標攻擊，您可以更快地找到一些密鑰。從中找到密鑰的預期成本 $ t $ 目標是 $ 2^{64}/t $ .

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