Prawdopodobieństwo fałszywie dodatniego klucza pasującego do dwóch par tekst jawny / szyfrogram
Biorąc pod uwagę przestrzeń kluczy $ 2^{80} $ i przestrzeń tekstu jawnego $2^{64}$. I dwie pary tekstu jawnego i szyfrogramu$(x_1, y_1)$ , $(x_2, y_2)$. Teraz mamy$2^{80}/2^{64} = 2^{16}$ klucze, które szyfrują $x_1$ do $y_1$ i kolejny $2^{16}$ klucze, które szyfrują $x_2$ do $y_2$, z tylko jednym kluczem, który powinien być kluczem docelowym (prawidłowym kluczem).
Jakie jest prawdopodobieństwo, że raz brutalna siła zidentyfikuje pierwszy klucz ($k_1$) ten sam klucz jest przez pomyłkę szyfrowany $x_2$ do $y_2$, to znaczy ten klucz jest fałszywie dodatni (to znaczy, że ten klucz prawdopodobnie nie będzie szyfrowany$x_3$prawidłowo). Jakie równanie jest używane i jak się je wyprowadza?
Odpowiedzi
Zgodnie z modelem idealnego szyfru, każdy klucz implementuje losową permutację. Losowy zły klucz, który mapuje$x_1$ do $y_1$ w ten sposób mapy $x_2\ne x_1$ do losowego zaszyfrowanego tekstu $y_2'$ inny niż $y_1$. Dla$b$-bitowy szyfr blokowy, są $2^b-1$ takie zaszyfrowane teksty, stąd prawdopodobieństwo, że $y_2'=y_2$ jest $1/(2^b-1)$.
Prawdopodobieństwo, że niepoprawny klucz przetrwa dwa testy, wynosi zatem $p=1/(2^b\,(2^b-1))$.
Losowy $k$-bitowy klucz ma prawdopodobieństwo $q=2^{-k}$aby być poprawnym. Przechodzi dwa testy z pewnością, jeśli jest poprawny, z prawdopodobieństwem$p$Inaczej. Zatem losowy klucz ma prawdopodobieństwo$q+(1-q)\,p$ zdać dwa testy [gdzie $q$ Termin dotyczy prawidłowego klucza, rozszerzenie $(1-q)\,p$ termin dotyczy niepoprawnych kluczy i otrzymywany jako prawdopodobieństwo, że klucz jest nieprawidłowy, razy prawdopodobieństwo, że mimo to przejdzie test z $(x_1,y_1)$ i $(x_2,y_2)$ ].
Zatem losowy klucz, o którym wiadomo, że przeszedł dwa testy, ma prawdopodobieństwo $q/(q+p\,(1-q))$ być poprawnym [gdzie licznik $q$jest prawdopodobieństwem poprawności klucza losowego, a mianownikiem jest prawdopodobieństwo, że klucz losowy przejdzie dwa testy]. To upraszcza$1/(1+p\,(1/q-1))$.
To znaczy, że pożądane prawdopodobieństwo fałszywie pozytywnego wyniku jest uzupełnieniem $$\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}$$
Dla $b$ i $k$ co najmniej 7, to jest $1/(1+2^{2b-k})$w granicach 1%. Kiedy dalej$2b-k$ to co najmniej 7, to jest $2^{k-2b}$ w granicach 1% $2^{-48}$, czyli mniej niż jeden na 280 milionów milionów.
Mówiąc bardziej ogólnie, można wykazać, że prawdopodobieństwo wyniku fałszywie dodatniego po przeprowadzeniu testu $n$ różne pary tekst jawny / szyfrogram to $1/(1+(2^b)!/((2^b-n+1)!(2^k-1)))$. W przypadku popularnych szyfrów blokowych, takich jak DES i szersze, jest to bardzo blisko$1/(1+2^{n\,b-k})$, i kiedy $n\,b-k$ to co najmniej 7, to jest $2^{k-n\,b}$ w granicach 1%.
Z prawdopodobieństwa: Niech X będzie eksperymentem z możliwymi różnymi wynikami $x_1 ,...,x_n$ z odpowiednimi prawdopodobieństwami $P(x_1)=p_1,...P(x_n)=p_n $. Niech A będzie podzbiorem przestrzeni próbkowania${ x_1..,x_n}$z prawdopodobieństwem P (A) = p. Niech K <= N liczb całkowitych z N> 0 i K> = 0,$$ \begin{pmatrix}N \\k \\ \end{pmatrix} p^k (1-p) ^{ (N-k)} \tag{1}$$ że A występuje w dokładnie k z N prób.
teraz, jeśli użyjemy ataku urodzinowego, szukamy prawdopodobieństwa, że po n próbach co najmniej 2 wyniki będą takie same wynosi co najmniej $$ 1- e^ {-1/2(n-1)n/N} \tag{2}$$. stąd dla$$ n >{\sqrt {2 ln 2}}{\sqrt N} \tag{3}$$. Prawdopodobieństwo co najmniej 1/2, że dwa wyniki będą takie same.
Jako dowód lepiej obliczyć prawdopodobieństwo, że żadne dwa wyniki nie są takie same i odjąć ten wynik od 1, aby uzyskać pożądany wynik. możemy rozważyć n prób w kolejności i obliczyć prawdopodobieństwo braku dwóch identycznych wyników dla n prób w kategoriach wyniku dla n-1 prób.
Na przykład. po jednej próbie prawdopodobieństwo wynosi 1, ponieważ jest tylko jeden wynik. Po dwóch próbach jest tylko 1 / N szansa, że druga próba miała wynik równy wynikowi pierwszej. co oznacza, że w naszym przypadku funkcja szyfrująca F użyła tego samego klucza K, więc prawdopodobieństwo wynosi 1- (1 / N), że wyniki dwóch prób będą różne. więc P (n prób różne) =$${(1-1/N)(1-2/N)... (1-((n-1)/N)) }\tag{4}$$
W porównaniu z rozszerzeniem Taylora dla $$ e^x, where,{e^x = 1 + x} \tag{5}$$dla przybliżenia pierwszego rzędu. Nabierający$$ {x \approx -a/N} \tag{6} $$ równanie (5) staje się $${e^ \frac{-a}{N}}\approx 1-\frac{a}{N} \tag{7}$$ , teraz równanie (4) to ... $${e^ \frac{-1}{N} \cdot e^\frac{-2}{N} }\cdots{e^\frac{-(n-1)} {N}\tag{8}}$$ , Bierzemy sumę n liczb naturalnych $${e^ \frac{-(n(n-1))/2}{N}}$$ Dla większego n możemy wziąć $$n(n-1)\approx n^2 \tag{9}$$, teraz P (to samo) = 1 - P (różne), które jest $${1- e^\frac{-n^2}{2N}\tag{10}}$$