Vigenere 密码破译

from my csdn blog

信息安全原理 hw1-2

Vignere: ktbueluegvitnthuexmonveggmrcgxptlyhhjaogchoemqchpdnetxupbqntietiabpsmaoncnwvoutiugtagmmqsxtvx

• 第一步：位移法求解key的长度

  • 这段密文约有200个字母，先假设key<=20

  • 位移20次，每次位移后计算与原密文对应相同的字母个数，即s[i]==s[i+j]，i为位置，j为位移量

cipher = 'ktbueluegvitnthuexmonveggmrcgxptlyhhjaogchoemqchpdnetxupbqntietiabpsmaoncnwvoutiugtagmmqsxtvxaoniiogtagmbpsmtuvvihpstpdvcrxhokvhxotawswquunewcgxptlcrxtevtubvewcnwwsxfsnptswtagakvoyyak'

def find_key_length(cipher):
    '''shift and fing the most repeats of the cipher'''
    MAX_LEN_REP = 10
    shift = [ None ]
    length = len(cipher)
    for i in range(1, length//MAX_LEN_REP):
        repeat = 0
        for j in range(length):
            repeat += 1 if cipher[j]==cipher[(j+i)%length] else 0
        shift.append(repeat)

    for i in range(1, length//MAX_LEN_REP):
        print('{0:2} '.format(i), end='')
    print()
    for i in range(1, length//MAX_LEN_REP):
        print('{0:2} '.format(shift[i]), end='')
    print()

find_key_length(cipher)

amrzs@ubuntu:security$ python3 vigenere.py 
 1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 
 9  4 13  9  4 12  8 11  7  7  2 12  4  3 12  9  5 

从结果可以看出，3 6 8 12 15 重复字母数相对偏高，这些字母的公因子约为3，于是说密钥长度为3的可能性非常大

• 第二步：

  • 获取key长度之后，将文本分为key长度份，即s[0],s[3],s[6]……为一份，s[1],s[4],s[7]……为第二份，剩下的为第三份

  • 接下来将每份进行频率分析(Frequency Analysis)

def frequency_analysis(cipher, keyLen, k):
    '''find the kth part alpha frequency, k in range(keyLen)'''
    length = len(cipher)
    keyDict = {}
    for alpha in range(ord('a'), ord('a')+26):
        keyDict[chr(alpha)] = 0
    for i in range(length):
        keyDict[cipher[i]] += 1 if i % keyLen == k else 0

    for alpha in range(ord('a'), ord('a')+26):
        print(' {0} '.format(chr(alpha)), end='')
    print()
    for alpha in range(ord('a'), ord('a')+26):
        print('{0:2} '.format(keyDict[chr(alpha)]), end='')
    print()

frequency_analysis(cipher, 3, 0) #0, 1, 2

程序第一部分结果：

amrzs@ubuntu:security$ ipython3 vigenere.py 
 a  b  c  d  e  f  g  h  i  j  k  l  m  n  o  p  q  r  s  t  u  v  w  x  y  z 
 2  0  6  0  1  1  7  1  3  1  1  0  1  2  2  8  4  0  0  5  4  7  3  0  2  0 

可以看出 p8, g7, v7, c6 频率较高，而普通英语文本中 e, t, a, i, n, o频率也较高

而一份维吉尼亚密码相当于一个凯撒密码，即位移相同字符数

那么可以断定 明文 -> 密文 即为 e ->g, t ->v, a -> c, n->p

所以key的第一个字符为c

接下来就是第二第三部分：

程序稍作修改

frequency_analysis(cipher, 3, 1)
frequency_analysis(cipher, 3, 2) 

具体判断过程与上面一样，key的第二的字母为a，第三个为t，则key为cat

既然知道了密钥，那就把明文破译出来吧

key = 'cat'

def decoding_vigenere(cipher, key):
    '''decoding vigenere cipher with key'''
    def getKeyDict(alpha):
        shift = ord(alpha) - ord('a')
        keyDict = {}
        for i in range(ord('a'), ord('a')+26):
            keyDict[chr(i)] = chr(i + shift) if i + shift <= ord('z') else chr(i + shift -26)
        #exchang the key and value
        keyDict = dict(map(lambda t:(t[1], t[0]), keyDict.items()))
        return keyDict

    keyLen = len(key)
    cipLen = len(cipher)
    keyList = [getKeyDict(key[i]) for i in range(keyLen)]
    plainText = ''

    for i in range(cipLen):
        plainText += keyList[i % keyLen][cipher[i]]

    print(plainText)

decoding_vigenere(cipher, key)

开始的时候把key算出来直接用了，程序运行的结果就是把密文又加密了一遍

在程序中稍作改动，把每个位移的字典key反转（交换键和值），程序运行结果是：

amrzs@ubuntu:security$ ipython3 vigenere.py 
itisessentialtoseekoutenemyagentswhohavecometoconductespionageagainstyouandtobribethemtoserveyougivetheminstructionsandcareforthemthusdoubledagentsarerecruitedandusedsuntzutheartofwar

看看到底是什么

it is essential to seek out enemy agents who have come to conduct espionage against you and to bribe them to serve you give them instructions and care for them thus doubled agents are recruited and used sun tzut heart of war