0

我们知道在流密码中 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 呢？

4

2 回答 2

1

我将举一个非常简化的例子。假设消息只有 1 位，并且从以下分布中独立选择：

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

然后，我们可以计算两个消息的联合分布m1和m2：

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

因此，我们可以使用贝叶斯定理计算m1给定的后验分布：x

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可能需要其中一个0大约160% 的时间，另一个大约 40% 的时间。如果x赞成0，那么可能m1=1，反之亦然。

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

于 2017-09-20T00:54:33.877 回答
1

正如您所说： c1 xor c2 = m1 xor m2如果 k 相同。

在这个等式中，您必须知道 m1 或 m2 才能恢复另一个。

在现实生活中，请注意 m1 或 m2 不是像G(k). 它们可能是可预测的或易于猜测的内容。例如，m1 和 m2 都是英文句子，或者 m1 和 m2 都是某些协议的 header。

于 2017-09-18T06:37:32.710 回答