（非）Vernam Cipher 的完全保密使用和(m)=m⊕k⊕rev(k)和(米)=米⊕ķ⊕轉(ķ)E(m) = m oplus k oplus operatorname{rev}(k)
給定密碼
$$ E(k, m) = m \oplus k \oplus \operatorname{rev}(k) $$ 在哪裡 $ \operatorname{rev}(k) $ 是逆二進制 $ k $ ，如何證明密碼不是完全秘密的。 我知道完美保密的定義是 $ P(M = m \mid C = c) = P(M = m) $ 對所有人 $ m $ 和 $ c $ 並且每個密鑰只使用一次。
顯然，當密鑰對稱時，直覺就會出現 $ k \oplus \operatorname{rev}(k) = 0 $ ，但是鑑於上面的定義，我如何才能使用上面的定義正式顯示這一點？
謝謝！這是一個家庭作業問題。
到目前為止，我的工作是 $ P(M = m) = 1/2^n $ 在哪裡 $ n $ 是位數和
$$ P(M = m \mid C = c) \= P(M = m \text{ and } C = c) / P(C = c) \= 2^n \cdot P(M = m \text{ and } C = c) \= 2^n \cdot (1/2^n \cdot 1/2^{n/2}) \text, $$ 但是，這似乎不是很正式。
雖然另一個答案是正確的，但有多種方法可以反駁一個定理。
在你的情況下，你想反駁
$$ \Pr[\mathcal M=m|\mathcal C=c]=\Pr[\mathcal M=m] $$為$$ c=m\oplus k \oplus \operatorname{rev}(k) $$. 第一個是使用機率進行論證，並表明上述等式不適用於該方案。
第二種（形式上正確的）方法是找到一個反例。請注意，反例總是反駁定理，而它們永遠不能用來證明它們（這就是物理學等科學的工作方式）。
現在考慮以下消息空間 $ \mathcal M={(0,1),(1,1)} $ 和 $ \Pr[\mathcal M=m]=\frac{1}{2} $ （即兩個消息同樣可能）。對於下一步，請注意
$$ c_0\oplus c_1 = m_0\oplus k_0 \oplus \operatorname{rev}(k)\oplus m_1\oplus k_1 \oplus \operatorname{rev}(k)= m_0\oplus k_0 \oplus k_1 \oplus m_1\oplus k_1 \oplus k_0=m_0\oplus m_1 $$ 正如 Maarten 在評論中指出的那樣。 $ m_0,m_1 $ 這裡表示消息空間的第一位和第二位，並且 $ c_0,c_1,k_0,k_1 $ 相應的密文和密鑰位。 現在觀察第一條消息總是產生一個 $ 1 $ 應用上述內容時 $ \oplus $ 並且第二個總是產生 $ 0 $ 應用時。所以你知道
$$ \Pr[\mathcal M=m|\mathcal C=c]\neq \frac{1}{2}=\Pr[\mathcal M=m] $$因此該方案並不完全安全。第一個機率是從以下事實可以得出的：在給定特定密文的情況下，您可以準確地知道哪條消息是加密的。