在沒有密鑰派生函式的情況下使用 Diffie-Hellman
在對另一個問題的回答中，有人建議從 Diffie-Hellman 密鑰交換中派生的共享密鑰可以直接用作一次性密碼來加密消息（通過在將所有內容寫入二進製文件後將消息與共享密鑰進行異或運算） ）。這形成了一個簡單的混合密碼系統。
使用者 fgrieu 在評論中寫道，這有一個缺陷，他說：
“您可以將其生成的共享密鑰用作一次性密碼”：但這還不夠安全！如果一個人只是簡單地用共享密鑰對消息進行異或併發送整個結果，那麼就有可能辨識出兩條消息中的哪一條被發送的機率比隨機消息要好得多。ElGamal 加密也有類似的問題。問題是：在 $ \mathbb Z ^*_p $ , Diffie-Hellman 洩露了共享密鑰的勒讓德符號。這就是我們在 DH 之上添加密鑰派生函式的原因之一。
回想一下勒讓德符號確定群的元素是否是二次餘數。
我們可以通過選擇一個元素來解決這個問題嗎 $ g $ 生成一個大子群，其所有元素都是二次殘差？具體來說，我們可以採取 $ p= 2q + 1 $ 對於一個大素數 $ p $ 然後找到一個生成訂單的元素 $ q $ 子群。
現在，如果 Diffie-Hellman 完成了這個組元素，任何竊聽者都知道共享秘密的最低位。所以我可以刪除這個位並使用所有高階位作為一次性填充，並且沒有關於共享秘密洩漏的資訊。
假設竊聽者無法破解 Diffie-Hellman，這個方案是否安全？即使 fgrieu 指出的特定缺陷已被該方案修復，還有其他令人信服的理由將 Diffie-Hellman 與密鑰推導函式結合起來嗎？
Diffie–Hellman的Wikipedia 頁面指出 IKEv2 以這種方式選擇公共組元素。但是，他們沒有說明是否應用了進一步的密鑰派生函式。
我們可以通過選擇一個元素來解決這個問題嗎 $ g $ 生成一個大子組（的 $ \Bbb Z_p^*\ $ )，其所有元素都是二次餘數？具體來說，我們可以採取 $ p=2q+1 $ 對於一個大素數 $ p $ 然後找到一個生成訂單的元素 $ q $ 子群。
現在，如果 Diffie-Hellman 完成了這個組元素，任何竊聽者都知道共享秘密的最低位。所以我可以刪除這個位並使用所有高階位作為一次性填充，並且沒有關於共享秘密洩漏的資訊。
那不安全。問題：
- 對手學到的不是 Diffie-Hellman 共享密鑰的低位 $ a $ 就像聲明的那樣。相反，洩漏的是勒讓德符號 $ \bigl(\frac ap\bigr)=a^q\bmod p $ ，這總是 $ +1 $ . 因此，即使我們移除了低位位，對手仍然會了解一些關於共享秘密的資訊，這是一個優勢。
例如與 $ p=23 $ , $ q=11 $ , $ g=3=7^2\bmod p $ , 對手知道 $ a $ 是其中的權力 $ g $ 模組 $ p $ ， 那是 $ a\in{3,9,4,12,13,16,2,6,18,8,1} $ （其中低位相當隨意）。因此，例如，如果密文是 $ 101_2 $ , 對手可以判斷明文不能 $ 000_2 $ ，因為這意味著 $ \lfloor a/2\rfloor=000_2\oplus101_2=101_2=5 $ 因此 $ a\in{10,11} $ ，這不可能是因為 $ \bigl(\frac{10}p\bigr)=10^q\bmod p\ne+1 $ 和 $ \bigl(\frac{11}p\bigr)=11^q\bmod p\ne+1 $ .
這種攻擊也適用於大型 $ p $ 並且在實際場景中。例如，如果班級卷上的名字被加密，那麼以班級卷上的每個名字計算兩次勒讓德符號為代價（兩個可能的 DH 共享秘密中的每一個），對手可能可以確定地排除大約四分之一的名字（有兩個負面結果的那些），並找到另一個四分之一（有兩個正面結果的那些），其中實際名字比剩下的班級卷的可能性更大。
- 的高位 $ a $ 表示為固定長度的位串 $ \lceil\log_2(p)\rceil $ 位分佈不均。
- 如果 $ q $ 有中等的質因數，那麼我不能排除由於Pohlig-Hellman算法而洩露的關於共享秘密的資訊不止一點。
我猜想這個變體是安全的（ind-CPA）：
- 挑選 $ p $ 一個安全的素數（即 $ p=2q+1 $ 和 $ q $ 主要）， $ p $ 大（例如 $ 4096 $ -bit)，而不是特殊形式 $ r^e\pm s $ 對於小 $ r $ 和 $ s $ .
- 選擇 $ g\in[2,p-2] $ 這樣 $ g^q\bmod p=1 $ , 意味著 $ g $ 是二次殘差的子群的生成器 $ \Bbb Z_p^* $ , 有素數 $ q $ .
- 像往常一樣執行 DH，產生共享密鑰 $ a $ .
- 截短 $ a $ 例如 $ \lceil\log_2(p)\rceil-k $ 低位產生 $ a’ $ ， 在哪裡 $ k $ 是一個安全參數（例如 $ k=128 $ ，給出一個 $ 496 $ -字節 $ a’ $ ).
- 利用 $ a’ $ 對於明文的 XOR 加密，最多為 $ a’ $ （或者最好，投入一些 $ a’ $ 使用通用散列à la Carter-Wegman 提供消息的完整性）。
論證：DH 的安全假設表明 $ a $ 在計算上與均勻隨機二次殘差在計算上無法區分 $ \Bbb Z_p^* $ ，因為它具有素數順序。我猜想這些二次殘差足夠好地分佈在 $ \Bbb Z_p^* $ 那 $ a’ $ 在計算上與均勻隨機無法區分，優勢消失為 $ \mathcal O(2^{-k}) $ .
這可能是在由被動對手監視的連結上執行 ind-CPA 公鑰加密的最簡單的學術正確方法。但要注意：這並不常用。公認的做法是提供 DH 共享密鑰 $ a $ 通過密鑰派生函式或偽隨機函式/雜湊（例如 SHA-256），並將結果用作經過身份驗證的對稱密碼（例如RFC 8452
AEAD_AES_256_GCM_SIV）的密鑰。