偽隨機排列/偽隨機函式/分組密碼有什麼區別？
有什麼區別;
- 偽隨機排列
- 偽隨機函式
- 分組密碼？
對這三個術語非常困惑，我不擅長高等數學。有人可以用簡單的語言解釋嗎？
這三個都是函式族。例如， $ f_k(x) = k \oplus x $ ， 在哪裡 $ \oplus $ 是異或 $ k $ 和 $ x $ 是 256 位字元串，是一個函式族；對於任何 256 位字元串 $ k $ , 有一個函式 $ f_k $ 給出另一個 256 位字元串 $ x $ 返回的異或 $ k $ 和 $ x $ . 輸入和輸出空間不必相同；我們可以想像一個函式族 $ f_k $ 從 512 位輸入 $ x $ 到 128 位輸出 $ f_k(x) $ , 以 256 位字元串為鍵 $ k $ . 這是一個小型函式族 $ g_k $ 具有 1 位密鑰、2 位輸入和 3 位輸出：
$$ \begin{equation*} \begin{array}{c|c} x & g_0(x) \ \hline 00 & 111 \ 01 & 000 \ 10 & 100 \ 11 & 110 \end{array} \qquad\qquad \begin{array}{c|c} x & g_1(x) \ \hline 00 & 011 \ 01 & 110 \ 10 & 100 \ 11 & 100 \end{array} \end{equation*} $$
偽隨機函式族是一個函式族——比如從 512 位字元串到 128 位字元串的函式，由 256 位密鑰索引——它具有以下屬性。
- 假設我擲硬幣 256 次來挑選 $ k $ ——也就是說，我選擇 $ k $ 均勻隨機。
- 假設我還選擇了一個功能 $ F $ 從 512 位字元串到 128 位字元串均勻隨機從所有 $ (2^{128})^{2^{512}} $ 這樣的功能，通過擲大量硬幣——足以裝滿一本書 $ 2^{512} $ 頁面，以便每個頁面上都有一個 128 位的答案。
（上面的每張表都有 $ 4 = 2^2 $ 行，因為輸入是 2 位長，總共有 $ 3 \cdot 2^2 = 12 $ 寫下輸出位，因為每個不同的輸入都有三位輸出，並且 $ 2^2 $ 不同的輸入。對於統一的隨機 512 位到 128 位函式，您需要 $ 2^{512} $ 行，並且每一行都有 $ 128 $ 位輸出，總共 $ 128 \cdot 2^{512} $ 位只是為了寫下其中之一 $ (2^{128})^{2^{512}} = 2^{128 \cdot 2^{512}} $ 該形狀的不同功能！）
我將選擇其中一項功能—— $ f_k $ 或者 $ F $ ，但你不知道是哪個——並且在你詢問的任何時候告訴你函式的值是什麼。
- （其實我不需要提前填書；如果我選擇 $ F $ ，我可以在收到您的詢問時懶洋洋地填寫書頁。）
你不知道我是否給了你一個函式家族的成員， $ f_k $ ，或均勻隨機函式， $ F $ .
換句話說，函式的機率分佈 $ f_k $ , 當鍵 $ k $ 是隨機均勻選擇的，非常接近（就計算有界決策算法可以辨別的而言）函式上的機率分佈 $ F $ 從所有函式中均勻隨機選擇。
偽隨機排列族是類似的，除了 $ f_k $ 和 $ F $ 被限制為排列，即它們的輸入和輸出空間是相同的，比如所有 256 位字元串的集合，並且它們將每個輸入映射到一個唯一的輸出，因此還有一個反函式。所以沒有那麼多可能性 $ F $ ——雖然有 $ (2^{256})^{2^{256}} $ 256位字元串的函式，只有 $ 2^{256}! \approx (2^{256}/e)^{2^{256}} $ 256 位字元串的排列。在大多數情況下，分組密碼只是偽隨機排列族的另一個術語。 *
這是一個小排列族的例子 $ \pi_k $ 進行比較——同樣，鍵是 1 位，輸入和輸出是 2 位字元串：
$$ \begin{equation*} \begin{array}{c|c} x & \pi_0(x) \ \hline 00 & 00 \ 01 & 11 \ 10 & 10 \ 11 & 01 \end{array} \qquad\qquad \begin{array}{c|c} x & \pi_1(x) \ \hline 00 & 01 \ 01 & 00 \ 10 & 10 \ 11 & 11 \end{array} \end{equation*} $$
請注意，與表格不同的是 $ g_k $ ，每個輸出在此處的每個表中只出現一次，因此我們可以翻轉每個表以獲得逆排列。
我們可以將位字元串解釋為（比如）大端二進制中的整數，並使用替代符號來編寫 $ \pi_k = (\pi_k(0) ; \pi_k(1) ; \pi_k(2) ; \pi_k(3)) $ 對於排列，通過說 $ \pi_0 = (0 ; 3 ; 2 ; 1) $ 和 $ \pi_1 = (1 ; 0 ; 2 ; 3) $ . 當然，對於像 AES 這樣的偽隨機排列族，被排列的元素數量不是 $ 2^2 = 4 $ 但 $ 2^{128} = 340282366920938463463374607431768211456 $ ，所以我們這裡沒有足夠的空間來用任何一種表示法詳盡地寫下 AES，即使是單個密鑰也是如此。
實際上，與其說函式族是否是偽隨機函式族，不如說我們量化了您作為對手在玩該遊戲時的優勢。具體來說，我們考慮一個決策算法 $ A(\mathcal O) $ 這需要一個神諭 $ \mathcal O $ ——這可能是 $ f_k $ 對於均勻隨機 $ k $ ，或者可能是均勻隨機 $ F $ ——並返回一個決定 $ {0,1} $ ，我們考慮機率之間的距離 $ A(\mathcal O) $ 返回 $ 1 $ 給定 $ f_k $ 對於均勻隨機 $ k $ 以及它返回的機率 $ 1 $ 給定均勻隨機 $ F $ ，稱為優勢 $ A $ 作為 PRF 區分器**：
$$ \begin{equation*} \operatorname{Adv}^{\operatorname{PRF}}_f(A) := \lvert\Pr[A(f_k)] - \Pr[A(F)]\rvert. \end{equation*} $$
PRP 的優勢是相似的，但同樣 $ f_k $ 和 $ F $ 被限制為排列。如果很難判斷預言機是否正在回答 $ f_k $ 或者 $ F $ ，那麼這個距離幾乎為零。顯然，總有一個非零優勢的區分器：猜一個鍵 $ \hat k $ 隨機並檢查是否 $ \mathcal O(x) = f_{\hat k}(x) $ ，但優勢很小，與密鑰空間的大小成反比。更有趣的是具有更高優勢的區分器。
我們推測某些功能，如 HMAC-SHA256 或 KMAC128——基於密碼分析者未能找到好的區分器的長期記錄——無論對手是什麼，這個距離都很小 $ A $ 是，只要 $ A $ 進行可想像數量的查詢。（例如，我們對一個對手不感興趣 $ 2^{256} $ 向 oracle 查詢，因為沒有人可以這樣做。）
然後，在研究像 CBC-MAC 這樣的高級結構時，我們根據與底層 PRF的區別優勢的界限來設置高級協議的*偽造機率的界限。*這樣，我們可以研究像 CBC-MAC 這樣的東西是否是一種從 PRF 建構 MAC 的好方法，而不是 AES 是否是一個好的 PRF。
“等等，AES 是一個很好的 PRF？”，你說，“我認為 AES 應該是一個排列！” 好吧，任何PRP 都可以在生日之前製作一個很好的 PRF。具體來說，有一個定理，有時稱為 PRF/PRP 切換引理，如果 $ f_k $ 是一個 $ b $ -位排列，然後對於任何對手 $ A $ 最多做 $ q $ 對預言機的查詢，$$ \operatorname{Adv}^{\operatorname{PRF}}_f(A) \leq \operatorname{Adv}^{\operatorname{PRP}}_f(A) + \binom{q}{2} 2^{-b}. $$ 只要 $ q \lll \sqrt{2^b} = 2^{b/2} $ 以便 $ \binom{q}{2} = q(q - 1)/2 \lll 2^b $ ， 期限 $ \binom{q}{2} 2^{-b} $ 非常小。換句話說，只要我們的應用程序將其數據量保持在遠低於 $ 2^{b/2} $ 塊，像 AES 這樣的良好偽隨機排列族幾乎與偽隨機函式族一樣好。順便說一句，這就是為什麼涉及 AES的密碼系統對於單個密鑰下超過幾 PB 的數據不安全的一般原因- 對於其中一些數據量限制來說，安全數據量限制要低得多。
- 在某些安全分析中，用比偽隨機性稍強的理想化對分組密碼進行建模可能更方便：理想密碼模型。偽隨機性是一種邏輯量詞：對於均勻隨機 $ k $ , $ f_k $ 很難與統一的隨機排列區分開來，它適用於特定的函式族，如 HMAC-SHA256。在理想的密碼模型中，我們研究隨機選擇函式族本身的協議：對於**所有不同的 $ k $ , $ f_k $ 是一個獨立的均勻隨機排列。與隨機預言機模型一樣，它是攻擊者結構的模型，而不是 SHA-256 或 HMAC-SHA256 等特定可計算事物可以展示的“屬性”。
偽隨機排列
令人困惑的是，在置換的經典定義中，這裡並沒有真正得到置換。它更像是對排列的常見概念的加密扭曲。實際的輸入/輸出行為如下：-
每個輸入都映射到一個輸出值。上圖很簡單，因為輸入和輸出的大小可以是 128 位或 $ 0 \to (2^{128} -1) $ . 這稱為雙射或單射滿射函式，AES就是一個例子。
偽隨機函式
這裡的想法是輸出是隨機的。因此，它們的行為如下：-
注意與 3、4 和 C 的碰撞。這是因為看起來隨機的輸出隨機碰撞，類似於骰子中的滾動對。由於相同的衝突，無法獲得輸出 A。但也要注意，由於輸入/輸出域的大小，這些衝突很少見（但並非不可能，具體取決於它們的實際大小）。這稱為非內射非滿射函式。SHA-1就是一個例子。
分組密碼
這只是一個密碼函式，一次作用於多個字節，而不是一個。像這樣，每個小方塊代表一個字節：-
它必須是偽隨機排列，否則會發生衝突（根據上述定義）。這意味著會有多個密文與單個純文字匹配。這很令人困惑。上面的範例可能是DES，一次作用於 8 個字節。AES 也是一種，但一次執行 16 個字節。
相反的是一個稱為“流密碼”的函式，一次按一個字節順序操作，如RC4。
已經進行了一些小的簡化，並採取了一些瑣碎的自由。這是為了對該主題進行更具戰略性的概述，並提供一個不那麼“數學”的答案。
