在溪流密码中,攻击者知道如果知道的话,如何获得M1 M2(M1 XOR M2)



我们知道,在流中心C = m xor g(k)中。而且,如果密钥不止一次使用,攻击者可以得到

  • c1 = m1 xor g(k)
  • c2 = m2 xor g(k)

然后他知道c1 xor c2 = m1 xor g(k)xor m2 xor g(k)= m1 xor m2。

因此,借助(M1 XOR M2),攻击者如何了解M1 M2?

如您所说: c1 xor c2 = m1 xor m2如果K相同。

在此等式中,您必须知道M1或M2才能恢复另一个。

在现实生活中,请注意,M1或M2不是G(k)的伪随机字符串。它们可能是可以预测的或易于猜测的内容。例如,M1和M2既是英语句子,也是M1和M2都是某些协议的标题。

我将举一个非常简单的示例。假设消息只有1位,并且从以下分布中独立选择:

P(m=0) = .4
P(m=1) = .6

然后,我们可以计算两条消息m1m2的联合分布:

P(m1=1, m2=1) = .36
P(m1=1, m2=0) = P(m1=0, m2=1) = .24
P(m1=0, m2=0) = .16

然后,考虑x = m1 xor m2。我们有:

P(x=0) = P(m1=1, m2=1) + P(m1=0, m2=0) = .52
P(x=1) = .48
P(x=0|m1=1) = P(m2=1) = 0.6
P(x=0|m1=0) = P(m2=0) = 0.4
P(x=1|m1=1) = P(m2=0) = 0.4
P(x=1|m1=0) = P(m2=1) = 0.6

因此,我们可以使用贝叶斯定理计算给定xm1的后验分布:

P(m1=1|x=0) = P(x=0|m1=1) * P(m1=1) / P(x=0) = .6 * .6 / .52 = 9/13 (.692)
P(m1=0|x=0) = P(x=0|m1=0) * P(m1=0) / P(x=0) = .4 * .4 / .52 = 4/13 (.308)
P(m1=1|x=1) = P(x=1|m1=1) * P(m1=1) / P(x=1) = .4 * .6 / .48 = .5
P(m1=0|x=1) = P(x=1|m1=0) * P(m1=0) / P(x=1) = .6 * .4 / .48 = .5

换句话说,如果x=0,我们调整了最初的60%/40%估计,以说该消息更有可能是1。如果x=1,我们会调整我们的初始估计值,以说两条消息同样可能。在这两种情况下,新的估计值均优于最初的60%/40%的估计值。

我们没有足够的信息来确定明文是什么,但是已经获得了一些信息(如果仅使用一次键,这不会发生)。

如果初始分布为50%/50%,则条件概率仍然以50%/50%的速度出现,因此偏斜的事实很重要。

如果知道更多消息,也可以使用相同的技术:

x1 = m1 xor m2
x2 = m1 xor m3
P(m1=1|x1=0, x2=0) = P(x1=0, x2=0|m1=1) * P(m1=1) / P(x1=0, x2=0) = (.6 * .6) * .6 / .28 = 27/35 (.771)

如果我们有大量独立消息,因此大量x变量,我们可以说x可能会在01中占用一个时间,大约60%的时间,而另一个时间约为40%。。如果x有利于0,则可能是m1=1,反之亦然。

对于英语文本,一种简单的估计方法是简单地将英文字母频率表作为初始分布,然后将此方法应用于每个字母。但是,有更好的英语模型将更加复杂。例如,一个人可以采用英语模型,其中每个字母具有不同的频率分布,具体取决于前面的字母(即马尔可夫链)。通过使用这些条件概率迭代单字母方法,可以从马尔可夫链中取样,以发现可能的明文。或者,有了更多的努力,可以计算此模型下最可能的消息的列表(但请注意,在每个阶段中最有可能的字母"贪婪"不一定会给总体上提供最可能的消息)。

最新更新