Hash

可以通過一些技巧重複使用相同的一次性便箋簿嗎

  • September 11, 2018

假設我有一條消息 $ m $ 的 $ n $ 位。和一個預定的墊 $ k*n $ 位。每一點 $ b $ 這條消息的 $ m $ ,我正在創建隨機序列 $ s $ 的 $ k $ 位。

我還有一個預定的布爾隨機函式 $ f $ (想像這樣的事情: $ f(s) = hash(s)\ mod\ 2 $ ).

對於每一位 $ b_i $ ,我選擇一個隨機值 $ s_i $ , 以便 $ f(s_i)=b_i $ .

所以,我可以建構一個填充版本 $ m $ 像這樣: $ m_p= s_0 || s_1 || … || s_n $ ,刪除填充是微不足道的。

加密也是直接的 XOR $ m_p $ 具有相同長度的預定焊盤的值( $ k * n $ )

該協議是否可以證明/允許反複使用同一個墊子來提供類似 OTP 的安全性?


等效的基於文本的方案公式:

為每個消息位提供一個新鮮的、隨機的散列原像,當散列時產生作為 LSB 的消息位。然後,您傳輸前映像並使用重複使用​​的 OTP 對其進行加密。

根據評論,問題似乎是問這是否與 OTP 一樣安全,而不是尋找實際攻擊。

它顯然不如 OTP 安全。它不是資訊論安全的。如果消息總數超過密鑰大小,我們可以暴力破解密鑰,只需迭代可能的密鑰,直到找到一個適用於所有消息的密鑰。

使用 OTP,當總消息大小永遠不會超過密鑰大小時,沒有計算能力可以讓您暴力破解密鑰,所有消息都有同樣的可能性,並且知道消息的一部分並沒有幫助,因為密鑰永遠不會被重用。

編輯:即使是攻擊 $ O(2^{kn}) $ 足以使它不是理論上的資訊安全。但我們至少可以做得更好一些。

和 $ O(k) $ 消息對我們可以用 O(n*2^k) 破解密鑰。一次工作一個片段。遍歷所有 $ 2^k $ 可能的密鑰段,並檢查消息,每條消息都會以 0.5 的機率排除一個壞密鑰,因此我們只需要幾個消息對即可排除所有錯誤密鑰。

我保留對大 k 和安全散列的安全性的判斷。

引用自:https://crypto.stackexchange.com/questions/62231