두 개의 일반 텍스트 / 암호문 쌍과 일치하는 오 탐지 키의 확률
주어진 키 스페이스 $ 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$-비트 키에는 확률이 있습니다. $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 천만 분의 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. N> 0 및 K> = 0 인 K <= N 정수,$$ \begin{pmatrix}N \\k \\ \end{pmatrix} p^k (1-p) ^{ (N-k)} \tag{1}$$ A는 N 번의 시행 중 정확히 k 번 발생합니다.
이제 생일 공격을 사용하는 경우 n 번의 시도 후에 최소 2 개의 결과가 동일 할 확률이 최소 $$ 1- e^ {-1/2(n-1)n/N} \tag{2}$$. 따라서$$ n >{\sqrt {2 ln 2}}{\sqrt N} \tag{3}$$. 두 결과가 동일 할 확률은 최소 1/2입니다.
증명을 위해 두 결과가 같지 않을 확률을 계산하고 원하는 결과를 얻기 위해이 결과를 1에서 빼는 것이 좋습니다. n 번의 시행을 순서대로 고려하고 n 번의 시행에 대한 결과의 관점에서 n 번의 시행에 대해 두 개의 동일한 결과가 없을 확률을 계산할 수 있습니다.
예를 들어. 결과가 하나뿐이므로 한 번의 시행 후 확률은 1입니다. 두 번의 시도 후 두 번째 시도의 결과가 첫 번째 시도의 결과와 같을 확률은 1 / N입니다. 즉, 우리의 경우 암호 함수 F가 동일한 키 K를 사용 했으므로 두 시도의 결과가 다를 확률은 1- (1 / N)입니다. 따라서 P (n 시행은 모두 다름) =$${(1-1/N)(1-2/N)... (1-((n-1)/N)) }\tag{4}$$
Taylor의 확장과 비교하여 $$ e^x, where,{e^x = 1 + x} \tag{5}$$1 차 근사치를 위해. 취득$$ {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 (Same) = 1-P (different) 즉 $${1- e^\frac{-n^2}{2N}\tag{10}}$$