2つの平文/暗号文のペアに一致する誤検知キーの確率
与えられたキースペース $ 2^{80} $ との平文スペース $2^{64}$。そして2つの平文と暗号文のペア$(x_1, y_1)$ 、 $(x_2, y_2)$。今、私たちは持っています$2^{80}/2^{64} = 2^{16}$ 暗号化するキー $x_1$ に $y_1$ と別の $2^{16}$ 暗号化するキー $x_2$ に $y_2$、ターゲットキー（正しいキー）となるはずのキーが1つだけあります。
一度ブルートフォースが最初のキーを識別する確率はどれくらいですか（$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)$。
したがって、誤ったキーが2つのテストに耐える確率は、 $p=1/(2^b\,(2^b-1))$。
ランダム $k$-ビットキーには確率があります $q=2^{-k}$正しいこと。正しければ確実に2つのテストに合格し、確率で合格します$p$さもないと。したがって、ランダムキーには確率があります$q+(1-q)\,p$ 2つのテストに合格する[ここで $q$ 用語は正しいキー、 $(1-q)\,p$ 用語は不正なキーを表し、キーが不正である確率に、それでもテストに合格する確率を掛けたものとして取得されます。 $(x_1,y_1)$ そして $(x_2,y_2)$ ]。
したがって、2つのテストに合格することがわかっているランダムキーには確率があります $q/(q+p\,(1-q))$ 正しくなるために[分子が $q$はランダムキーが正しい確率であり、分母はランダムキーが2つのテストに合格する確率です]。それは単純化して$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億8000万人に1人未満です。
より一般的には、テスト後の誤検知の確率を示すことができます $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％以内。
確率から：Xを可能な異なる結果の実験とします $x_1 ,...,x_n$ それぞれの確率で $P(x_1)=p_1,...P(x_n)=p_n $。Aをサンプル空間のサブセットとします${ x_1..,x_n}$確率P（A）= pで。K <= N> 0およびK> = 0のN個の整数とします。$$ \begin{pmatrix}N \\k \\ \end{pmatrix} p^k (1-p) ^{ (N-k)} \tag{1}$$ そのAは正確にk回のN回の試行で発生します。
現在、誕生日攻撃を使用する場合、n回の試行後に少なくとも2つの結果が同じになる確率を探しています。 $$ 1- e^ {-1/2(n-1)n/N} \tag{2}$$。したがって、$$ n >{\sqrt {2 ln 2}}{\sqrt N} \tag{3}$$。2つの結果が同じになる確率は少なくとも1/2です。
証明のために、2つの結果が同じではない確率を計算し、この結果を1から減算して、目的の結果を取得することをお勧めします。n回の試行を順番に検討し、n-1回の試行の結果に関して、n回の試行で2つの同一の結果がない確率を計算できます。
例：結果が1つしかないため、1回の試行後の確率は1です。2回の試行の後、2回目の試行で最初の試行と同じ結果が得られた可能性は1 / Nのみです。つまり、この場合、暗号関数Fは同じキーKを使用しているため、2つの試行の結果が異なる確率は1-（1 / N）です。したがって、P（n回の試行はすべて異なる）=$${(1-1/N)(1-2/N)... (1-((n-1)/N)) }\tag{4}$$
テイラー展開との比較 $$ e^x, where,{e^x = 1 + x} \tag{5}$$一次近似用。取る$$ {x \approx -a/N} \tag{6} $$ 式（5）は次のようになります $${e^ \frac{-a}{N}}\approx 1-\frac{a}{N} \tag{7}$$ 、今式（4）は.. $${e^ \frac{-1}{N} \cdot e^\frac{-2}{N} }\cdots{e^\frac{-(n-1)} {N}\tag{8}}$$ 、n個の自然数の合計を取ります $${e^ \frac{-(n(n-1))/2}{N}}$$ より大きなnの場合、 $$n(n-1)\approx n^2 \tag{9}$$、今P（同じ）= 1-P（異なる）これは $${1- e^\frac{-n^2}{2N}\tag{10}}$$