为什么OTP不容易受到暴力攻击？

#1 楼

OTP上的蛮力攻击会给您各种有意义的消息，而不是有意义的消息。

例如，您有4个字符的加密文本：weaw。现在，暴力破解将为您提供各种有意义和不有意义的消息，例如：


erwe
hell
road
.....

现在，真正的信息是哪一个？那将是困难的，甚至是不可能的。

#2 楼

您所缺少的是，每个结果消息都是同等可能的事实。无法验证结果消息是否确实是发送的消息。


如果您有$ P_1P_2P_3P_4 \ oplus K_1K_2K_3K_4 = C_1C_2C_3C_4 $，其中每个$ P $，$ K $和$ C $是一位，那么$ C_1C_2C_3C_4 $可以有任何值。

现在假设您的蛮力将$ A_1A_2A_3A_4 $作为键，然后$ C_1C_2C_3C_4 \ oplus A_1A_2A_3A_4 = Z_1Z_2Z_3Z_4也会有任何价值。但是，无法测试$ Z_1Z_2Z_3Z_4 = P_1P_2P_3P_4 $。由于不同的位之间根本没有任何关系，因此每个$ Z $值都将具有同等的可能性。这就是为什么OTP对于特定大小的消息完全安全的原因。诸如AES之类的现代密码确实在位之间具有（非常复杂的）关系，因此可以确定地确定给定密钥的正确明文是否存在。使用OTP时，获得纯文本位的机会恰好是每位$ 0.5 $-也就是说，您不知道猜对与否。

#3 楼

首先，您必须了解为什么可以在其他系统上进行详尽的密钥搜索。

假设您有一个长度为n的明文，长度为n的密文，以及一个长度为k的密钥（全部以位为单位）。然后，通过尝试所有可能的键，我们最多获得2k个候选纯文本。如果系统内置某种验证或消息完整性，那么它可能会小于2k。它必须至少为1，也可能仅为1，在这种情况下，穷举搜索始终会在该系统上运行（当然，如果k足够大，我们不在乎穷举搜索是否起作用，但这超出了问题的范围）。

但是假设系统本身并没有告诉我们哪个密钥是正确的（当然哪个OTP不正确）：如果k比n小得多，则只有很小的一个所有可能的长度为n的消息的比例将在我们的详尽搜索中表示。其中之一是正确的明文，其余的则不是。我们通常如何知道哪个是对的？答案是，通常其他的将是垃圾[*]，因为如果您伪随机地选择长度为n的2k个字符串，则对于k显着小于n的k，则它们很有可能都是垃圾。仅仅是因为我们从头开始就是已知的加密消息，所以我们才有权期望任何输出都是有意义的。

因此，通常来说，如果我们找到能产生意义的候选键，我们就很有信心打破信息。我们仍然可能不确定。例如，也许偶然地系统具有两个不同的密钥，其中一个将给定的密文解密为“黎明时攻击”，而另一个将其解密为“黄昏时攻击”。但是对于要进行详尽搜索的密码系统来说，这是非常不可能的，因此，一旦我们找到一条有意义的消息，我们就比消息发件人对我们拥有的信心更加自信，这确实是消息他们发送了。如果只有这两个有意义的候选纯文本，那么我们已经比发送者想要的更多地了解了消息。此外，假设（通常是OTP以外的其他密码）发件人多次使用同一密钥，并且同一密钥对多个不同的密文产生意义。这几乎不可能是偶然发生的，因此我们现在非常有信心将密钥强行使用。

现在，OTP呢？然后k = n，所以即使输出是伪随机的，我们也希望有很多有意义的候选。更糟糕的是，穷举地尝试每个键会生成长度为n的每个文本作为候选纯文本。具体来说，消息M是由密钥M XOR C生成的，其中C是密文。可以肯定的是，我们将找到一个解密该消息为“黎明时攻击”的密钥，另一个解密为“黄昏时攻击”的密钥，另一个解密为“我的品脱！”的密钥，依此类推。这样的长度。

因此，如果我们进行详尽的搜索，它只会告诉我们“明文可以是任何长度为n的消息”。我们已经知道了。我们仍然可以排除垃圾，但是这样做会给我们留下正确长度的每条非垃圾邮件。

详尽的搜索没有告诉我们。



[*]“垃圾”在这里不是一个专业术语，但我的意思是，如果认为纯文本消息是英语，则生成的大多数输出​​将不是英语。如果认为它是.png文件，则生成的大多数输出​​将没有正确的.png文件头。等等。许多密码系统在进行详尽的密钥搜索时让攻击者拥有“婴儿床”是一个优势：并非如此。

#4 楼

最重要的答案是：每个可能的5个字符的ASCII字符串都是等效的。因此，如果您尝试所有可能的键（如您所注意到的，这是实用的），那么您肯定会在某个时候看到正确的纯文本字符串。但是您将无法知道正确的字符串就是正确的字符串。

为了使这一点更加清晰，请考虑仅包含1位消息的OTP。换句话说，明文为0或1。现在有一个秘密密钥位0或1与明文异或。

因此密文等效为0或1。您可以轻松地蛮力地使用1位密钥。但是，这为您提供了零的明文值信息。

#5 楼

尽管先前的答案/评论解释了基本思想，但可以帮助将OTP与伪OTP进行对比。在伪OTP中：$ Enc_s（m）：= G（s）\ oplus m $，$ Dec_s（c）：= G（s）\ oplus c $，其中$ G $是伪随机数生成器。 （这是OTP，只是密钥由$ G $的输出代替，并由较短的密钥$ s $作为种子。）

基本思想：强行使用OTP不会给攻击者她不知道的有关纯文本的任何其他信息。正式地，将明文空间设为集合$ P $。给定在OTP下加密的密文$ c = k \ oplus m $，使用所有可能的密钥$ k $解密$ c $，并将生成的明文值的集合设为$ Q $。那么$ Q = P $。您没有学到任何新知识。

伪OTP有何不同？用所有可能的密钥$ s $解密$ c = G（s）\ oplus m $。现在，$ Q \ subset P $。为什么？因为$ | s | <| G（s）| = | P | $。因此，您学到了一些新东西：加密的消息不在$ P-Q $中。

#6 楼

可以这样想：假设您截取了长度为$ N $位的密文$ C $的传输，并且您偶然知道它是使用带有$ N $位密钥的OTP加密的。

对于每个明文$ Y $（长度为$ N $位），都有一个$ N $位密钥，这样$ Y_x = C \ oplus K_x $。

例如，使用8位ASCII字符，如果接收到8 * 40 = 320位密文$ C $，则可以从密文中导出任何40个字符的短语。实际上，找到生成明文$ Y_x $
$ C_oplus K_x = Y_x \ rightarrow K_x = C \ oplus Y_x $

的密钥$ K_x $很简单。 />
现在考虑概率论。在收到密文$ C $之前，您可能会拦截的所有可能的明文消息$ P（Y）$都有一定的概率分布。这是您先前的概率分布。

问题是，接收密文$ C_0 $对这种分布有何影响？

贝叶斯定理说

> $
P（Y_x | C_0）= \ frac {P（C_0 | Y_x）\ times P（Y_x）} {P（C_0）}
$

您对找到每个$ Y_x $的概率感兴趣。请注意，底部的$ P（C_0）$没关系，因为它不依赖于$ Y_x $。

$ P（C_0 | Y_x）= 0 $对于所有$ Y_k长度不是$ N $位的$。如果我们假设所有键$ K_x $的可能性均等，则对于$ N $位的所有$ Y_x $，$ P（C_0 | Y_x）= \ frac {1} {2 ^ N} $。重新归一化概率分布后，发现给定消息为$ N $位，您发现$ P（Y_x | C_0）$只是$ P（Y_x）$的边际概率。基本上，在消除位数错误的明文之后，您的概率分布基本上只是先前分布的缩放版本！

#7 楼

我最初以这种想法写这是一个答案，但是后来我意识到，它本身并不严格与OTP相关，而是与计算机安全中通常使用OTP的方式有关（我在计算机安全中的经验比在纯密码技术方面的经验还多） 。无论如何我都会发布它，因为在分析日常OTP系统时，这是一个有趣的考虑因素，例如用于用户身份验证（2FA等）。

OTP密钥通常仅在有限的时间段或尝试次数内有效。之后，系统会重新生成OTP或移至预共享密钥列表中的下一个密钥，从而使攻击者有一定的时间长度或尝试完成攻击的次数，因此密钥在更改之前几乎总是会更改

尽管如此，对于被OTP加密的消息（例如，两个间谍之间的协同工作）已被拦截的情况，攻击者的时间和尝试次数是无限的解密；在这种情况下，OTP的好处是恢复一个密钥不会损害所有先前或后续的消息。