字符频率记分操作

Question

如https://cryptopals.com/sets/1/challenges/3所述的加密挑战是:

Single-byte XOR cipher
The hex encoded string:
1b37373331363f78151b7f2b783431333d78397828372d363c78373e783a393b3736
... has been XOR'd against a single character. Find the key, decrypt the message.
You can do this by hand. But don't: write code to do it for you.
How? Devise some method for "scoring" a piece of English plaintext. Character frequency is a good metric. Evaluate each output and choose the one with the best score.

这个问题的解决方案是什么?:

作为异或的倒数是异或，我应该将字符串1b37373331363f78151b7f2b783431333d78397828372d363c78373e783a393b3736与a-z范围内的每个字符进行异或，但我应该如何评分这个字符串?字符频率与分数的关系如何?

Answer 1

注意该字符串是十六进制的，因此必须将其解释为一系列十六进制字符(大概是ascii编码)。

编码前

1b37373331363f78151b7f2b783431333d78397828372d363c78373e783a393b3736
1b 37 37 33 31 36 3f 78 
15 1b 7f 2b 78 34 31 33
3d 78 39 78 28 37 2d 36
3c 78 37 3e 78 3a 39 3b
37 36

编码后

77316?x+x413=x9x(7-6<x7>x:9;76
   7  7  3  1  6  ?  x
   +     x     4  1  3
=  x  9  x  (  7  -  6
<  x  7  >  x  :  9  ;
7  6

评分怎么样?

评分基本上是将输出与我们期望的输出进行比较，在开发正式称为启发式的过程中是一个非常重要的概念;有根据的猜测/问题的解决方案。

在英语中，某些字母明显比其他字母更常见。"e"是英语文本中出现频率最高的字母。字母的频率表允许您检查字符串是否可能是英语。换句话说，当您解密字符串时，对进行任何猜测。

为了好玩，你可以写一个程序来制作频率表。它会扫描明文(例如这个答案)，统计每个字母，然后显示使用该字母的文本的百分比。将足够的样本放在一起后，您将拥有自己的频率表!如果你不想自己编译，可以参考维基百科的文章，或者搜索其他信息。

另一件要注意的事情是，当转换为ascii时，我们丢失了一些数据。一些数据变成了无法显示的特殊字符。这呈现了另一种可能的评分机制;有些特殊字符不会出现在键盘输入的字符串中，所以使用了许多特殊字符的字符串不太可能是正确的。

如何编写代码?

至于如何编码解决方案，您将需要用a-z范围内的每个ascii字符对每个十六进制字符进行xor。请注意，'each'使用了两次，因此您可能会在代码中有两个for语句或循环结构。

根据XOR函数的实现方式，减少迭代的一个聪明的方法可能是复制单个ascii字符足够的次数以匹配字符串的长度，然后XOR复制两个值。

这里我用ascii 'a'进行异或:

Input:
    1b37373331363f78151b7f2b783431333d78397828372d363c78373e783a393b3736
Length of input:
    34
Repeat (a in ascii) by length:
    aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
Then XOR:
    input
    repeat
Output:
    zVVRPW^tzJUPRXIVLW]V_[XZVW

---

编辑:

鉴于时间已经过去了很长一段时间，我已经用python实现了一个解决方案。

import string
import re
in_hex = '1b37373331363f78151b7f2b783431333d78397828372d363c78373e783a393b3736'

def take(n, s):
    '''yield n-sized chunks from iterable s'''
    for i in range(0, n, 2):
        yield s[i:i+2]

def hex2str(s):
    '''given an ascii string of single-byte hex literals, interpret as ascii'''
    return bytes.fromhex(s).decode('ascii')

def string_xor(s, c):
     '''given an ascii string s of hexadecimal values, xor each one by char c'''
     c = ord(c)  # dirty dynamic typing
    return ''.join(map(lambda h: chr(ord(h) ^ c), s))

for letter in string.ascii_letters:
    result = string_xor(hex2str(in_hex), letter)
    # remove ascii control chars
    pretty_result = re.sub(r'[x00-x1F]+', '', result)
    # print the result and the corresponding letter used to decode
    print(f'{letter}: {pretty_result}')

成功行:

X: Cooking MC's like a pound of bacon