当暴力破解 DES 时,了解明文有帮助吗?

信息安全 密码学 加密 密码分析
2021-08-15 04:47:36

数据加密标准(维基百科)

我知道通过蛮力可以检查 2^56 个可能的密钥(56 位,每个为 1 或 0)。但假设我知道消息本身仅由字母 (az, AZ) 组成。

知道关于明文的事情(比如仅限于字母)会使破解加密更容易吗?

4个回答

在标准的蛮力搜索中,假设您已经知道至少一个明文及其与给定密钥相关的加密。因此,除非您正在利用其他一些弱点,否则让明文来自受限制的集合并没有帮助。

为了使蛮力攻击真正成功(即使在理论上),攻击者必须知道关于明文的“一些东西”,以知道他是否找到了正确的密钥。换句话说:如果攻击者只知道明文是一堆随机字节,那么对于每个尝试过的密钥,这正是他将得到的:一堆看起来随机的字节。

另一方面,如果攻击者发现攻击系统是值得的(因为 2 56穷举搜索虽然可行,但相当昂贵),那么他必须先验地知道他会找到什么。这可以是任何标准格式(例如,数据是 XML,以 XML 标头开头;或者数据被压缩gzip并因此以gzip标头开头),甚至可以是一些基本信息,例如“明文是一些'有意义'的文本” .

带有 ASCII 编码的英文文本将仅使用一些字节值,即从 32 到 126(含)的字节值,可能还有 9(水平制表)、10 和 13(分别用于行尾的 LF 和 CR), 12(垂直列表),可能还有 26(DOS/Windows 系统上的文件结尾)。所以这是 255 个可能的字节值中的 100 个。使用错误密钥对单个 DES 块(8 个字节)进行解密的概率约为 (100/255) 8,仅包含在这组“似是而非的字符”中。由于攻击者有 2 56个密钥要尝试,他必须解密n个块,以便接受错误密钥的概率不超过 2 -56只要n = 6(因为 (100/255) 8*6 ≤ 2-56 )。这导致了穷举搜索攻击,攻击者对每个潜在密钥解密6个块,通过查看获得的字符过滤掉错误的密钥。

现在,让我们面对现实吧,“8g.;=7Zf”并不完全是“有意义的文本”。因此,攻击者实际上知道的不仅仅是“明文仅包含可打印的 ASCII 字符”。他可以过滤掉错误的解密,这些解密只产生可打印的字符,而不是合理的文本摘录。比如说,他还可以得到一千个“可能的密钥”(每一个都产生一些东西,从计算机的角度来看,这些都是有感觉的文本)并用手完成工作(人脑非常好)在看起来乱七八糟的字符列表中发现真实文本)。所以攻击者可以使用,比如说,两三个块,仍然可以完成任务。

很难量化攻击者在过滤错误解密方面的效率,因为这取决于攻击者“猜测”什么,这属于心理学领域,而不是计算机科学。因此,学者们使用“安全惯例”来考虑攻击者有一个已知的明文块:他 100% 确定地知道一个 8 字节的明文,他也有相应的密文。在实际的攻击情况下这可能不是真的,但你无法真正预见到它。

这取决于您如何检查每个键。如果从 0 开始并不断递增,则必须转换为字符集并验证该字符是否有效。或者你应该以另一种方式工作,从一个字符开始,只增加集合中的一个字符。

我认为如果你按字符而不是按位递增,你的工作集会小得多,因此运行所有组合所需的时间会更少。

知道可能的解决方案属于受限集合将对您有所帮助,因为您可以提前终止解密过程。
在您的情况下,您可以仅解密有限数量的加密/密文(例如前 8/16/... 字节),并仅保存仅由字母组成的解密/纯文本以供以后使用(阿兹,阿兹)。接下来,如果保存的解决方案空间太大,您可以增加解密数量,或者简单地检查所有解决方案并确定哪个是正确的。