OAEP 中種子長度的安全效應
在用於非對稱加密填充的OAEP方案中，使用了隨機種子，其長度可以選擇。1994 年介紹 OAEP的論文只是指出，種子的長度 $ k_0 $ 應該選擇使得對手的執行時間明顯小於 $ 2^{k_0} $ 步驟。
我想知道，選擇非常小或非常大的安全效果會是什麼 $ k_0 $ .
**注意：**我問的是通用 OAEP，而不是 RSA-OAEP，它修復了 $ k_0 $ 到所使用的散列函式的長度。
讓我們從預賽開始。基本方案的加密定義如下：
$$ \mathcal{E}^{G, H}(x) = f(x \oplus G(r) || r \oplus H(x \oplus G(r))) $$ 一些定義：
- $ f: {0,1}^k \rightarrow{0, 1}^k $ 是一個陷門置換，其中 $ k $ 是安全參數
- $ x $ 是要加密的消息
- $ n = |x| $ 是消息的位長
- $ k_0 = k - n $ （出局的利息價值）
- $ G: {0,1}^{k_0} \rightarrow{0, 1}^n $ 是來自的“生成器” $ k_0 $ 位到 $ n $ 位
- $ H: {0,1}^n \rightarrow{0, 1}^{k_0} $ 是一個“雜湊函式” $ n $ 位到 $ k_0 $ 位
- $ r \gets {0, 1}^{k_0} $ 是隨機選擇的 $ k_0 $ 位串
設置背後的總體構想 $ 2^{k_0} $ 遠大於對手的執行時間是為了防止對手有不可忽略的機會暴力破解 $ r $ . 回顧 $ r $ 是隨機的 $ k_0 $ 位串所以有 $ 2^{k_0} $ 的可能值 $ r $ .
假設 $ k_0 $ 被選擇為只有幾個位，在這種情況下 $ \mathcal{E}^{G, H} $ 在選擇的明文攻擊 (IND-CPA) 下不安全。有關如何證明 IND-CPA 的直覺，請參見此圖。簡而言之，如果對手送出消息 $ m_0, m_1 $ 被加密 $ \mathcal{E}^{G,H} $ 然後回來 $ c $ 它需要確定是否 $ c $ 是加密的 $ m_0 $ 或者 $ m_1 $ . 下面是它是如何做到的：
$ G $ , $ H $ ， 和 $ f $ 都是公開的，所以方程中唯一的未知數是 $ r $ , 是隨機抽樣的。如果 $ r $ 足夠小（即如果 $ k_0 $ 很小）那麼對手可以計算 $ \mathcal{E}^{G, H}(m_0) $ 和 $ \mathcal{E}^{G, H}(m_1) $ 對於所有可能的值 $ r $ . 一旦它計算出一個匹配的值 $ c $ 對手知道 $ c $ 是輸入的任何消息的加密 $ \mathcal{E}^{G, H} $ ，這意味著它在 IND-CPA 博弈中具有不可忽略的優勢（即該方案不是 IND-CPA）。
所以很自然地我們要選擇一個 $ k_0 $ 足夠大，以至於對手無法暴力破解 $ r $ . 這意味著定義 $ k_0 $ 選擇使得對手的執行時間明顯小於 $ 2^{k_0} $ 腳步。
總而言之，對於價值觀 $ k_0 $ 這是非常小的結果是災難性的，因為你失去了語義安全。對於值 $ k_0 $ 非常大沒有安全缺陷，但是你的排列 $ f $ 需要更大，這通常會轉化為更慢的方案（例如考慮 RSA2048 與 RSA4096）。