是否每一輪中 50% 的位改變最終總是給出 50% 的改變位?
假設我們有一個具有這種屬性的密碼,每輪平均改變每個塊中 50% 的位。這很明顯還是意味著在幾輪之後我們將獲得 50% 的更改位?
如果我仔細想想,它似乎不必那樣。下一輪可以刪除上一輪的一些更改,依此類推。最後,我們可以得到不同數量的比特改變,即使每一輪恰好改變了 50% 的比特。
我對嗎?如果我們有這樣的性質,即每輪改變 50% 的比特,那麼如何確定在最後的許多輪中,我們最終也會改變 50% 的比特呢?能否以某種方式證明或通常我們必須依靠統計測試?
如果我們有這樣的性質,即每輪改變 50% 的比特,那麼如何確定在最後的許多輪中,我們最終也會改變 50% 的比特呢?
好吧,顯然可以建構不會發生這種情況的人工範例;最明顯(也是微不足道的)是,如果第 1 輪和第 2 輪彼此相反(即,第 1 輪和第 2 輪為您提供原始明文);即使兩輪單獨理想,兩輪後我們仍然沒有得到雪崩效應(即使我們在一輪後得到了它)。
對稱密碼通常沒有足夠的結構來讓我們建構不會發生這種情況的證據(添加結構通常會使密碼更弱,而不是更強;對手也可以利用結構);我們通常不得不依靠似是而非的論據。
這是一個不同的觀點。正如評論中所指出的,您可以做出結構化的選擇,這意味著所有或一半的位都被翻轉。相反,讓我們考慮一個使用隨機性的模型。
讓 $ b $ 是塊長度,它總是偶數,實際上通常是 2 的冪。為了對過程進行建模,假設我們隨機翻轉一半位(一個整數,因為 $ b $ 是偶數)在第一輪;然後隨機且獨立於第一輪發生的事情,選擇一個子集 $ b/2 $ 位並在第二輪翻轉它們,依此類推。
由於該過程是獨立的,因此與輸入向量相比,翻轉的最終位數將按二項式分佈 $ \mathrm{Bin}(b,1/2). $
恰好一半位被翻轉的機率是 $$ 2^{-b} \binom{b}{b/2}\approx \frac1{\sqrt{\pi b}}. $$ 現在這可能看起來很矛盾,恰好一半位被翻轉的機率正在緩慢下降 $ b $ . 如果 $ b=32, $ 這個準確計算的機率是 $ 0.134 $ 而對於 $ b=128, $ 它減半 $ 0.070 $ 正如近似值所預期的那樣。
然而,沒有悖論。如果我們問我們正好在被翻轉的一半位的 5% 以內的機率是多少,我們將中間係數周圍的一些二項式係數相加,如 $$ 2^{-b} \sum_{\lceil (1-\epsilon)b/2\rceil}^{\lfloor(1+\epsilon)b/2\rfloor} \binom{b}{k}. $$ 如果 $ b=32, $ 和 $ \epsilon=0.05 $ ,這個準確計算的機率是 $ 0.134 $ 而對於 $ b=128, $ 它已增加到 $ 0.464 $ 正如近似值所預期的那樣。