对重复使用同一密钥的密文进行解密

September 14, 2014 | 08:09 密码学

最近在Coursera上报班开始学习Crpytography I,第一个星期的课程看完,还是收获良多的。下面就是关于第一周作业的一些思考。

对于流密码(Stream Cipher)来说,很重要的一点便是不要多次使用同一密钥对信息进行加密。我们知道,流密码的加密方式是用\(\oplus\)(异或)运算,对于使用同一密钥进行加密的密文,我们可以使用简单的异或运算将密钥消掉,大致的算法如下,其中\(c_0\)、\(c_1\)表示密文(cipher text),\(p_0\)、\(p_1\)表示明文(plaintext),\(k\)表示密钥(key):

$$ c_0 = p_0 \oplus k$$ $$ c_1 = p1 \oplus k$$ $$ c_0 \oplus c_1 = p_0 \oplus p_1$$

而得到这个\(p_0 \oplus p_1\),有什么用呢?在我们掌握一些额外信息的基础上,会很容易加以尝试来破解掉这个加密的。以作业中的条件为例,我们事先得知明文会是一系列英文句子,使用ASCII编码。在ASCII表中,英文字符的分布为:A(0x41)-Z(0x5a)、a(0x61)-z(0x7a),我们暂且称之为“字符区间”。不难发现,对于任意两个字母char0、char1,它们异或的结果都是落在0x00-0x3b上的。而对于一段英文中最容易出现的字符——空格来说,由于它的ASCII码是0x20,它与其他字母异或的结果落在0x41-0x5a和0x61-0x7a这个区间,仍然是在“字符区间”内,只不过大小写调换了。发现了这一点非常重要,我们可以通过将某一密文和其他密文一一进行异或运算,分析结果中出现的在“字符区间”的字节,说明这一字节中,很有可能两条密文中的某一条,出现了空格。我们将其他位用“X”来表示,这一位用空格来表示,形成这样一个直观的数据:

XX XX XXXX X XXX XX XXX X XXX XX XXX XXXXXX XX XX X XXXX

XX XX X XXXX XX XX XXX X XX XX XX X XXXXXXXXX X XX XXXXXX

XX XX XXXXXX XX XXXXX X XXX XXXXXX XXX XXXXX XXXXXX X XXXX

XX XX X XXX XXXXXX X XXX X X XXXX XXX X XXXX XXXXXX XXXX X

XX XX XX XXXXXXX X XX X XXXX XX XX X XXXXX X X XXXXXXXX X

XX XX XX XXXXXXX X XX X XXXX X XXX XXX XXXXXXXXX XX XXXX X

XXXXXXXXXX XX XX XX XXX X XX X XX XX X XXXXX XX XXX XX XX X

X XXXX XXX XX X XXXXXX XXXXXXX X XXXXX X XXXXXX XXX XX XXX

X X X XXXXX XXX XXXXXX X X X X XXXXXXXX XXXX X XX XXXXX

对于某一条密文,如果它在某个位置处,与其他密文的异或结果,都是或大多是落在“字符区间”内的话,很有可能该密文在此处的明文对应为空格。相反,如果只有一两个异或结果落在“字符区间”,这一位很有可能不是空格,而是与该条密文做异或运算的那条密文在此处为空格。于是我们将所有异或结果存储到一个数组中,分析每一位上,哪条密文的对应明文,最有可能是空格。

得到这个结果后,就很容易从不同密文中选择空格位,再与空格(0x20)异或后,还原成密钥片段。对于无法分析的一些字节,可以暂时用空格来代替。至此,我们便得到了准密钥。

下面的工作,当然就是把准密钥代入到密文中,进行解码。最初的结果很难做到完美无瑕,根据密文的规模、内容等不同,很可能会出现一些错误的字符。通过分析,不难看出,我们的筛选空格位的算法,可能会存在以下问题:

  • 该位上没有明文是空格
  • 该位上多个明文出现空格,空格相异或反而不会落到“字符区间”
  • 存在一些出字母外的特殊符号(逗号、冒号、句号等)

不过没关系,我们可以将得到的准密钥代入所有的密文中,对文字进行上下文、词义的分析,从而找到这些错误位置上的正确密钥。

具体实现的话,我写了一个Python的脚本,比较粗糙,没怎么优化。不过考虑到课程的Honor Code,暂时就不详细说明了,会在合适的时候进行优化再贴出来。

Creative Commons BY-NC-ND 3.0