单字节异或密码(Python)

6

我正在上一门现代密码学课程,挑战是Cryptopals的第三个挑战:单字节XOR密码。我正在尝试使用Python 3来完成此任务。

我知道我应该对字符串进行XOR并转换为英文。十六进制字符串是"1b37373331363f78151b7f2b783431333d78397828372d363c78373e783a393b3736",它转换为十进制形式为"806748453371902409051174291875458592743800337585421566549206796642836053682239286"。

我已经对这个字符串进行了多次XOR运算,但不知道如何将其转换为英文。现在只能靠暴力猜测吗?

我知道关于ETAOIN SHRDLU,但这并没有真正帮助到我。

谢谢您的时间和帮助。


补充: 此外,我尝试了第4个挑战,但这段代码似乎不起作用。但它确实可以用于第3个挑战,所以我很困惑。

挑战 #3 挑战 #4


你有解密密码吗? - bzimor
有256个可能的密钥。它是两个十六进制字符的任意组合。我尝试了很多,但我不知道该选择哪个密钥。 - Phillip Sloan
3个回答

6

您可以使用 binascii.hexlifybinascii.unhexlify 将字节串转换为十六进制或将十六进制转换为字节串:

>>> import binascii
>>> binascii.hexlify(b'HELLO')  # to Hex
b'48454c4c4f'
>>> binascii.unhexlify('48454c4c4f')  # from Hex
b'HELLO'

使用 str.isprintable,可以过滤掉非可打印字符:
>>> 'abcd'.isprintable()
True
>>> '\x00'.isprintable()
False
>>> '\x7f'.isprintable()
False

import binascii

encoded = binascii.unhexlify('1b37373331363f78151b7f2b783431333d78397828372d363c78373e783a393b3736')
for xor_key in range(256):
    decoded = ''.join(chr(b ^ xor_key) for b in encoded)
    if decoded.isprintable():
        print(xor_key, decoded)

1
这是使用上述代码得到的可能答案:像一磅培根一样烹饪MC。 - bzimor
1
@falsetru 我尝试了两种不同的方式将其用作权重,都得到了正确的结果。 - Stefan Pochmann
88行得通了!谢谢!至少现在我知道答案了。 - Phillip Sloan
我知道 ETAOIN SHRDLU 不是一条消息,而是英语中最常见的字母。 - Phillip Sloan
2
@PhillipSloan,请阅读以下内容:列表推导式生成器表达式str.joinchr - falsetru
显示剩余7条评论

5

在 @falsetru 的回答基础上,但只显示带有最多空格字符的解码字符串:

>>> encoded = '1b37373331363f78151b7f2b783431333d78397828372d363c78373e783a393b3736'
>>> import binascii
>>> nums = binascii.unhexlify(encoded)
>>> strings = (''.join(chr(num ^ key) for num in nums) for key in range(256))
>>> max(strings, key=lambda s: s.count(' '))
"Cooking MC's like a pound of bacon"

不必计算空格,你可以使用ETAOIN SHRDLU(“英语中12个最常用字母的近似频率顺序”)作为权重,但在这里并非必要。

顺便说一下,如果你链接到挑战会更好。


编辑: 或者,您可以尝试找到密钥(或几个最有前途的密钥),然后仅使用该密钥(或这些少数密钥)进行解码。例如,假设通过计算空格来确定获胜者:

>>> encoded = '1b37373331363f78151b7f2b783431333d78397828372d363c78373e783a393b3736'
>>> import binascii
>>> nums = binascii.unhexlify(encoded)
>>> key = max(nums, key=nums.count) ^ ord(' ')
>>> ''.join(chr(num ^ key) for num in nums)
"Cooking MC's like a pound of bacon"

这甚至可以手动完成(尽管挑战告诉你不要这样做)。

1
@PhillipSloan 谁说你必须手动完成?挑战并不是这样要求的。挑战恰恰相反,要求你不要手动完成。对于权重,我刚刚注意到,如果我只使用12个字母,不包括昨天我在中间使用的空格,我实际上很难使正确结果成为最高价值的字符串... - Stefan Pochmann
@PhillipSloan 这是一种可行的方法,虽然不完全干净:max(strings, key=lambda s: sum((26-i) * s.count(c) for i, c in enumerate('etaoinshrdlu')))。请注意,我在我的答案中添加了另一种可能会让你感兴趣的替代方案。 - Stefan Pochmann
@PhillipSloan 这样做会产生完全不同的结果,并且让你离目标更远(它将所有内容放入单个非数组值中)。我不明白为什么你要这样做。 - Stefan Pochmann
1
@PhillipSloan 我已经用第一种方法解决了第四个挑战,只是使用每个可能的密钥对每个字符串进行解码,并打印具有最多空格字符的结果。如果这种方法对你不起作用,请尝试打印更多的最佳候选项而不是仅一个。总体来说,只有两个候选项具有最高数量的空格字符,正确答案是其中之一。 - Stefan Pochmann
1
@PhillipSloan 另外,我在上面的评论中建议的加权方法效果非常好。正确答案得分为353分,而第二高的得分仅为318分。 - Stefan Pochmann
显示剩余8条评论

0
通过观察编码字符串,可以发现其中存在 "3737",因此可能表示一个英文单词中的 "e"、"E"、"o"、"O"、"r" 或 "R"。 通过逆向工程,异或结果显示 "R"、"r"、"X"、"x"、"E" 和 "e" 都有可能是密钥。 尝试这些潜在密钥后,你会发现 "X" 是正确的密钥。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接