delphij's Chaos

选择chaos这个词是因为~~实在很难找到一个更合适的词来形容这儿了……

04 Sep 2012

多次使用同一个一次性密码本的破解

正确地使用一次性密码本进行加密,在理论上是无法破解的。需要注意的是,许多对称式加密算法本质上是通过一定的算法来将密钥作为伪随机数发生器的种子来产生(近似于)一次性密码本的序列,因此类似的问题也需要予以重视:不要重复使用同一个一次性密码本(或密钥)来加密不同的明文数据。

以基本的一次性密码本加密算法,即按字节做 XOR 来看,由于在这个算法中明文和密文的字节位置是一一对应的,很明显,同一个位置的两份密文之间做 XOR,可以知道两份明文之间的 XOR 值(因为在这个过程中,密钥 k 被 XOR 消去了)。

假如明文碰巧又没有做任何压缩处理,实际上我们可以用程序来穷举出部分的密码本,并逐步解出全部明文。具体方法大致如下:

首先是尝试初步地破解。明文如果是英文的话,出现空格或e的可能性非常地高。对于每一条明文的同一个位置的内容,假定明文内容是空格,可以得到密钥可能是 密文 XOR 0x20,然后用这个可能的密钥去解其它的密文。假如解出来的明文都是字母、数字、标点或空格的话,则说明这个密钥很可能就是真正的密钥。用程序可以迅速对此作出判断。

接下来是找一组常见的英文单词。通常来说,the, to, then 这样的单词出现的频率非常高,因此,以它们作为突破口。以 the 为例,加上前后的空格,一共是5个字符。用穷举的方法去搜索每一个密文串来解出可能的密钥,然后再用这个密钥尝试解密其它密文在同一位置的字符串。如果解密出来的字符串看起来都像是英文(这里可以设置比较严苛的条件,例如只允许出现大小写字母、标点和数字),则记下密钥的位置和内容。反复搜索高频词,就可以恢复相当一部分明文的内容。

接下来,根据已知的明文内容去猜测可能的未知明文内容,并使用猜测的内容去尝试算出可能的密钥解密其它密文数据。

一些想法:

  1. 不要反复使用同一个一次性密码本,或者同一个对称密钥;
  2. 加密之前应先做压缩;
  3. 类似全盘加密这样的应用,密文也是需要保护的。