分組密碼中弱密鑰機率的證明
我的教科書有以下定理：
給定一個密鑰長度為K位、塊大小為n位的分組密碼以及t個明文-密文對，將所有明文加密為相應密文的假密鑰的預期數量為$$ 2^{k - tn} $$
如果您認為 DES 給我們提供了大致 $ 2^{-8} $ 對於單個明文-密文對，如此處所述。但是作者沒有證明這個定理，我想知道是否可以證明它，我該如何證明它？我考慮過使用歸納法，但我對可以做出哪些假設有一些問題
但是作者沒有證明這個定理，我想知道是否可以證明它，我該如何證明它？
作者可能不會理會證明，因為它非常簡單；我們還需要注意的是，該圖 $ 2^{k-tn} $ 不是精確的，而只是一個近似值（儘管對於現實的密鑰和塊大小來說非常接近）；一旦我們跳過近似，證明就變得不那麼簡單了。
首先，我們做出的假設：密碼就像一個理想密碼，特別是，如果我們給密碼一個不正確的密鑰，它會生成隨機密文塊（以及獨立於使用正確密鑰生成的密文塊） .
那麼，如果我們考慮給出已知的 $ t $ 使用不正確的密鑰向密碼發送明文，它將生成 $ t $ 隨機密文，每一個都是 $ n $ 位。鑑於這些是隨機的，所有的機率 $ n $ 其中的位與預期的密文位完全相同 $ 2^{-nt} $ （因為總共有 $ nt $ 位，所有這些都必須是正確的值。
現在，這不太準確。分組密碼，即使給定一個不正確的密鑰，仍然是一個排列，並且假設所有的明文塊都是不同的，那麼所有生成的密文塊都是不同的。這意味著，如果 $ t>1 $ ，某些輸出（例如全0輸出）將是不可能的（因為密碼永遠不會將兩個不同的明文加密到同一個全0密文塊中）；錯誤密鑰的精確機率是 $ (2^n-t)! / 2^n! = \frac{1}{2^n \cdot (2^n-1) \cdot (2^n-2) \cdot … \cdot (2^n-t+1)} $ . 如果 $ 2^{n/2} \ggg t $ ，也就是說，我們大大低於“生日界限”，這非常接近 $ 2^{-nt} $
現在，這是一個不正確鍵的期望值，總期望值是所有各種不相交可能性的期望值的總和。共有 $ 2^k $ 不正確的鍵，因此總期望值為 $ 2^k \cdot 2^{-nt} = 2^{k - nt} $
現在，這也不太準確，有 $ 2^k-1 $ 不正確的鍵（因為我們假設有一個正確的鍵）；顯然，對於我們使用的密鑰大小， $ 2^k $ 是一個很好的近似值；我們也看到了 $ (2^k-1)(2^n-t)! / 2^n! $ 是精確的（如果通常不太有用）的期望。