由一道Vigenere想到的造轮子

Posted on | | 次阅读

插播广告，这是crypto-online

  • 前几次的密码学课程上，几乎每次上课前都会做几道题目（其中包括去解一些古典密码，如Vigenere等）emmm… ，所以就想做一个关于常见古典密码加解密的工具，而碰巧得知编程语言中的 “网红” javascript有一个强大的加解密库 —— CryptoJS，就萌生了建个线上加解密的小站。完全代码见github，还在建设中，大家如果有一些好的想法和建议，欢迎指点交流 ^ _ ^

广告打完了，扯一扯正题

  • 在写crypto-online之前，密码学老师给我们发了一道破解Vigenere的题，异或加密，让我们没事儿的时候做一做。

  • 这题是这样的，已知十六进制编码的密文，密钥长度1-13字节，每一位都是0-255 随机的ascii（密钥可以不在可打印字符内）

  • 在假设密钥长度为n的情况下，常规套路都是将密文分成n段，统计词频 

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    c = '''
    十六进制密文
    '''
    cl = [ c[i:i+2] for i in range(0, len(c), 2) ]
    # 先将连续的十六进制密文分割，形成元素均为十六进制数的列表

    from collections import Counter
    # 导入Counter模块，统计词频

    count = [ cl[i::n] for i in range(n) ]
    # cl[i::n] 将cl列表中的n个元素分为一组，且将每组中下标为i的元素组合成一个列表，count 为n个列表组成的列表

  • 然后就是将count中每个列表的词频最高的元素与' '或'e'（英文中词频较高的字符）异或，得出密钥

  • 但在这里，密钥长度未知，幸运地是咱们知道其长度，我想到的是通过异或后的明文反馈，如果前密钥长度个字符的ascii在32～126范围中，那么我们可以把密钥长度、密钥保留下来，再进行后续解密处理。

  • 做题的时候突然想，词频说到底是概率，并不是所有文章的最高词频都是' '或'e'，因此，如果采用通过明文反馈的方法，未免会落下许多可能情况（例如密钥长度为7，每个位都应该至少与' ', 'e', 't'异或，那么就得考虑至少3^7种可能）

    开始造轮子吧

  • 首先，再次明确一下需要解决的问题，假设有一个空间chs = [ ' ', 'e', 't' ]，密钥长度为7，我们需要配出3^7两两互不相同的组合

  • 这问题很像排列组合，itertools中的permutations就是解决排列组合的问题，但是显然与本需求不符，不知道python里还有没有其他库提供这种方法，作为一个渣渣，只能自己造轮子了。。。

  1. 定义高词频列表：chs = [ ' ', 'e', 't' ]

  2. 假设现在有了词频统计结果，每组的最高词频记录在列表里：words

  3. 让words里的每个元素分别和chs所有元素异或，保存：ch_xor_word = map(lambda x:[ str( int(x, 16)^ord(ch) ) for ch in chs ], words)

  4. 下面定义两个函数： 

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23

    def combine(x, y):
        tmp = []
        for i in x:
            for j in y:
                tmp.append([i, j])
        return tmp

    # 将内嵌列表展开，代码参考这篇博客 http://blog.csdn.net/vola9527/article/details/68964144
    def flatten(list_in):
        list_out = []
        while 1:
            if list_in == []:
                break
            for index, val in enumerate(list_in):
                if type(val) is types.ListType:
                    list_in = val + list_in[index+1:]
                    break
                else:
                    list_out.append(val)
                    list_in.pop(index)
                    break
        return list_out

  5. 最后一步：ans = map( flatten, reduce(combine, ch_xor_word) )

  • 解释一下第5步，举个例子：

    1
    2
    3
    4
    # 先看一下flatten的具体作用
    >>> test0 = [ ['a', 'b'], 'c', [ 'd', ['e', 'f'] ], 'g' ]
    >>> flatten(test0)
    >>> [ 'a', 'b', 'c', 'd', 'e', 'f', 'g' ]
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    # 结合combine和reduce
    >>> ch_xor_word = [ 
    ... ['182' , '143', '156' ], 
    ... [ '145', '194', '128' ], 
    ... [ '21', '103', '97' ]
    ... ]

    >>> un_flatten = reduce(combine, ch_xor_word)
    [[['182', '145'], '21'], [['182', '145'], '103'], [['182', '145'], '97'], [['182', '194'], '21'], [['182', '194'], '103'], [['182', '194'], '97'], [['182', '128'], '21'], [['182', '128'], '103'], [['182', '128'], '97'], [['143', '145'], '21'], [['143', '145'], '103'], [['143', '145'], '97'], [['143', '194'], '21'], [['143', '194'], '103'], [['143', '194'], '97'], [['143', '128'], '21'], [['143', '128'], '103'], [['143', '128'], '97'], [['156', '145'], '21'], [['156', '145'], '103'], [['156', '145'], '97'], [['156', '194'], '21'], [['156', '194'], '103'], [['156', '194'], '97'], [['156', '128'], '21'], [['156', '128'], '103'], [['156', '128'], '97']]

    >>> map( flatten, un_flatten )
    [['182', '145', '21'], ['182', '145', '103'], ['182', '145', '97'], ['182', '194', '21'], ['182', '194', '103'], ['182', '194', '97'], ['182', '128', '21'], ['182', '128', '103'], ['182', '128', '97'], ['143', '145', '21'], ['143', '145', '103'], ['143', '145', '97'], ['143', '194', '21'], ['143', '194', '103'], ['143', '194', '97'], ['143', '128', '21'], ['143', '128', '103'], ['143', '128', '97'], ['156', '145', '21'], ['156', '145', '103'], ['156', '145', '97'], ['156', '194', '21'], ['156', '194', '103'], ['156', '194', '97'], ['156', '128', '21'], ['156', '128', '103'], ['156', '128', '97']]

  • 结合reduce的类似递归的特性，轮子造完了，好像有点蠢。。。

后记

  • 在写这篇博文的时候，又想到了一种方法，可以将[ ' ', 'e', 't' ]视为三进制，假设密钥长度仍然为7：

  1. 定义一个集合：

    1
    chs = { '0': ' ', '1': 'e', '2': 't' }

  2. 自定义一个十进制转三进制的函数：

    1
    2
    3
    4
    5
    6
    7
    def ten2three(num):
        l = []
        while num>0:
            num, bit = divmod( num, 3 )
            l.append(str(bit))
        l.reverse()
        return ''.join(l)

  3. 最后，得到3^7=2187种两两不同的组合:

    1
    2
    3
    4
    >>> test0 = map(lambda x:''.join([ chs[i] for i in ten2three(x).zfill(7) ]), range(0, 3**7) )
    >>> from collections import Counter
    >>> len(Counter(test0))
    2187

分割线。。。
果然还是太菜了，itertools 提供了product方法，目的是生成笛卡尔积，这正是要解决的问题，还是以chs = [ ' ', 'e', 't' ]来看:

所以说，为了防止造更多轮子，还是应当把官方文档一些常用库过一遍～

对于Vigenere密钥长度的爆破

  • 前段时间看到过一篇文章，讲述的是针对Vigenere唯密文爆破密钥长度，采用的方法是通过计算两个等长字符串的汉明距离，并进行归一化处理，得到的最小值最有可能和密钥长度相关。
  • 比如说，密钥长度n在2～100之间，取密文的前n个字符连接成的字符串与第n+1～2n个字符连接成的字符串，计算两者的汉明距离，并进行归一化处理。统计2～100之间所有的情况，并对结果进行排序，与最小值相关的n可认为最接近真实密钥长度。
  • 试了下我遇到的这道题，从1～13里取值，确实得到密钥长度为7。知道了密钥长度，再结合词频统计的结果，就不难得出答案了。