匹配兩個明文/密文對的誤報密鑰的機率
給定一個鍵空間 $ 2^{80} $ 和明文空間 $ 2^{64} $ . 以及兩個明文和密文對 $ (x_1, y_1) $ , $ (x_2, y_2) $ . 現在我們有 $ 2^{80}/2^{64} = 2^{16} $ 加密的密鑰 $ x_1 $ 至 $ y_1 $ 和另一個 $ 2^{16} $ 加密的密鑰 $ x_2 $ 至 $ y_2 $ ，只有一個鍵應該是目標鍵（正確的鍵）。
一旦暴力辨識第一個密鑰的機率是多少（ $ k_1 $ ）這個相同的密鑰發生錯誤也加密 $ x_2 $ 至 $ y_2 $ ，也就是說這個密鑰恰好是假陽性（也就是說，這個密鑰可能不會加密 $ x_3 $ 正確）。使用的方程是什麼，它是如何推導出來的？
在理想的密碼模型下，每個密鑰都實現了一個隨機排列。映射的隨機錯誤鍵 $ x_1 $ 至 $ y_1 $ 因此映射 $ x_2\ne x_1 $ 隨機密文 $ y_2’ $ 以外 $ y_1 $ . 為一個 $ b $ -位塊密碼，有 $ 2^b-1 $ 這樣的密文，因此機率 $ y_2’=y_2 $ 是 $ 1/(2^b-1) $ .
因此，不正確的密鑰在兩次測試中倖存下來的機率是 $ p=1/(2^b,(2^b-1)) $ .
一個隨機的 $ k $ -bit key 有機率 $ q=2^{-k} $ 是正確的。如果正確，它肯定會通過兩次測試，並且有機率 $ p $ 否則。因此隨機密鑰具有機率 $ q+(1-q),p $ 通過兩項測試 [其中 $ q $ 術語是正確的鍵， $ (1-q),p $ 術語用於不正確的密鑰，並獲得為密鑰不正確的機率乘以它仍然通過測試的機率 $ (x_1,y_1) $ 和 $ (x_2,y_2) $ ].
因此，已知通過兩個測試的隨機密鑰具有機率 $ q/(q+p,(1-q)) $ 是正確的[分子在哪裡 $ q $ 是隨機密鑰正確的機率，分母是隨機密鑰通過兩次測試的機率]。這簡化為 $ 1/(1+p,(1/q-1)) $ .
所需的誤報機率是補碼，即 $$ \begin{align}1-1/(1+p,(1/q-1)),&=,1/(1+1/(p,(1/q-1)))\&=,1/(1+2^b,(2^b-1)/(2^k-1))\end{align} $$
為了 $ b $ 和 $ k $ 至少7個，那是 $ 1/(1+2^{2b-k}) $ 1%以內。當進一步 $ 2b-k $ 至少是 7，那是 $ 2^{k-2b} $ 1%以內，這裡 $ 2^{-48} $ ，也就是不到 2.8 億分之一。
更一般地，可以證明測試後假陽性的機率 $ n $ 不同的明文/密文對是 $ 1/(1+(2^b)!/((2^b-n+1)!(2^k-1))) $ . 對於像 DES 和更廣泛的常見分組密碼，這非常接近 $ 1/(1+2^{n,b-k}) $ ， 什麼時候 $ n,b-k $ 至少是 7，那是 $ 2^{k-n,b} $ 1%以內。