伪正键匹配两个明文/密文对的概率

Question

给出了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 )。使用的方程是什么?它是如何推导出来的？

Answer 1

在理想的密码模型下，每个密钥都实现了随机排列。将x_1映射到y_1的随机错误键，从而将x_2\ne x_1映射到y_1以外的随机密文y_2'。对于b-bit分组密码，存在2^b-1这样的密文，因此y_2'=y_2是1/(2^b-1)的概率。

因此，一个不正确的密钥存活两个测试的概率是p=1/(2^b\,(2^b-1))。

随机k-bit密钥的概率q=2^{-k}是正确的。如果正确的话，它通过了两个测试，如果正确的话，则用概率p进行测试。因此，随机密钥具有概率q+(1-q)\,p通过两个测试其中q#qcStackCode#项表示正确的键，(1-q)\,p#qcStackCode#术语是指不正确的密钥，并作为密钥不正确的概率，乘以它通过测试的概率。(x_1,y_1)#qcStackCode#和(x_2,y_2)#qcStackCode#。

因此，已知通过两个测试的随机密钥的概率q/(q+p\,(1-q))是正确的在那里分子q#qcStackCode#是随机密钥正确的概率，分母是一个随机密钥通过两个测试的概率。。这将简化为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，那就是1%以内的2^{k-2b}，这里是2^{-48}，这还不到2.8亿的1/2。

更一般地，可以证明在测试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%以内。

Answer 2

从概率出发:设X是一个可能的不同结果的实验，x_1 ,...,x_n有各自的概率P(x_1)=p_1,...P(x_n)=p_n 。设A是概率为P(A)=p的样本空间{ x_1..,x_n}的子集，设N >0的K <= N整数，以及A发生在N次试验的k上的K>=0，\begin{pmatrix}N \\k \\ \end{pmatrix} p^k (1-p) ^{ (N-k)} \tag{1}。

现在，如果我们使用生日攻击，我们正在寻找的概率是，在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}

与一阶近似下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}}。