Hash
如何證明兩個人都知道同一個字典單詞？
有什麼方法可以證明你和我都知道同一個字典單詞？如果我們都對單詞進行散列，那麼我們可以比較散列，但是任何看到散列的人都可以通過散列字典中的所有單詞來找到原始單詞。有什麼更好的方法？
檢驗兩個低熵字元串是否相等的問題稱為私人相等檢驗或社會主義百萬富翁問題。這也是**密碼認證密鑰交換（PAKE）**的主要挑戰。您已經正確地觀察到，當字元串具有低熵時，簡單地發送雜湊不是一個好方法——它暴露了離線字典攻擊。
社會主義百萬富翁問題的維基百科頁面提供了一個範例協議，但我認為這不是一個很好的例子（通過避免隨機預言使它變得更加複雜，我認為這不是維基百科最重要的標準例子）。有一種更簡單的方法——實際上是有史以來第一個提出的 PAKE 協議：來自 Bellovin & Merrit的 EKE 。這個想法很簡單：只需將 Diffie-Hellman 密鑰協議包裝在一層理想密碼中，輸入字元串作為密鑰：
- 愛麗絲持有 $ x $ 鮑勃認為 $ y $ . 他們同意一個帶有發電機的公共 Diffie-Hellman 組 $ g $ .
- Alice 選擇一個隨機指數 $ a $ 並發送 $ A = E(x, g^a) $ 在哪裡 $ E $ 是理想密碼。
- Bob 選擇一個隨機指數 $ b $ 並發送 $ B = E(y, g^b) $ .
- 愛麗絲可以計算 $ K = (E^{-1}(x, B))^a $
- Bob 可以計算 $ K’ = (E^{-1}(y, A))^b $
- 什麼時候 $ x=y $ ， 然後 $ K=K’ $ 太（你可以檢查一下 $ K=K’=g^{ab} $ ）。但當 $ x \ne y $ , $ K $ Bob 和 $ K’ $ 在 Alice 看來是隨機的（具有高熵！）。所以他們可以簡單地比較 $ K $ 和 $ K’ $ 在明確。
如果您想在實踐中實現 EKE，那麼您將不得不處理密鑰協議（發生在循環組中，可能是橢圓曲線組）和分組密碼（需要一串位作為輸入）之間的輕微不匹配. 這確實可以處理，但它使事情變得更加混亂。
如果我們可以通過某種方法共享一個密鑰（例如預共享帶外，或使用某種加密密鑰建立），那麼我們都可以計算一個密鑰 HMAC。我們將能夠檢查雜湊值，但沒有密鑰的任何人都無法耗盡可能的輸入。