密码学实战

维吉尼亚密码

以一道作业题为例子

思路

1.确定m，利用重合指数法，首先猜测m的长度，然后按m将密文分组，取每组的第1，2….n，分别放在一起，形成新的文本，以字典形式表示，key = 组号 ，value = 字符串。

2.计算重合指数，因为key是变化的，每一组需要多右移动一次，因此每一个字符串并非是简单的平移，而是后一个字符要多平移一个，因此需要变换字符串为正常情况来进行重合指数的分析，（就是把每个字符串的字符按索引平移回去）。

3.重合指数的计算，遍历m，分别计算平均重合指数，然后取平均值在0.6以上的（则表明非随机）。

4.确定key，再次利用重合指数法，算出每一个组的每个字符出现的频率，然后利用有意义字符的频率，来进行重合指数的计算（最多尝试26次，即可确定key），注意解出来的并非是key，而是key的逆，也就是说key-26。

5.通过4计算而得的key，平移每个组的字符串，再将其按照一的方式组合回去，即可得到明文。

实现

1.文本预处理

这一步删除掉密文的换行之类,并统一大小写

def pretreatment():
    with open("密文2.txt","r") as f:
        wen = f.read()
    pattern = re.compile('[\n]|\d|\W')
    plain_1 = re.sub(pattern,'',wen).lower()
    return plain_1

2.遍历寻找m

这一步需要两步骤：

1.按m长度的key对密文进行分组，并猜测m的长度

def guess_len_key(crypt):
    """
    guess_len_key函数的主要作用是通过密文猜解密钥长度
    :param crypt: 密文
    :return: 密钥长度以及划为的子串
    """
    l = 1
    d = {}
    while True:
        print("****************************假设密钥长度        为%s***********************************" % l)
        sum_index = 0.0
        for i in range(len(crypt)):
            n = i % l
            if n not in d:
                d[n] = ''
            d[n] += crypt[i]
        sum_index = sum(coincidence_index(d[j]) for j in range(l)) / l
        if sum_index >= 0.06:
            break
        else:
            l += 1
            d = {}
    return l,d

其中比较重要的一个点是重合指数的计算,这里面在计算重合指数之前，需要将每一个子字符串每个字符平移，平移数目为索引。（具体原因在思路已经介绍）

def coincidence_index(text):
    text = shift_text_left(text)
    # 计算字符频率
    frequencies = Counter(text)
    n = len(text)
    
    if n <= 1:
        return 0
    
    # 计算重合指数
    ic = sum(f * (f - 1) for f in frequencies.values()) / (n * (n - 1))
    
    return ic
##平移，需要注意mod26
def shift_text_left(text):
    result = ""
    n = len(text)
    
    for i in range(n):
        char = text[i]
        shift_amount = i  # 当前字符要平移的位数为它的索引i
        new_char = chr((ord(char) - ord('a') - shift_amount) % 26 + ord('a'))
        result += new_char
    
    return result

经过上述过程已经得到按固定组长分割好的特定的子字符串，而每一组相对应为key中的一个字符，且是一个另类的单表循环，只不过排在后面的要多循环一位。经过下属过程处理可以将其转换为一般的单表循环，基本上和shift_text_left函数的道理是一样的

def single(b):
    new = {}
    for key,value in b.items():
        value = shift_text_left(value)
        new[key] = value
    return new

结果展示：

****************************假设密钥长度        为1***********************************
****************************假设密钥长度        为2***********************************
****************************假设密钥长度        为3***********************************
****************************假设密钥长度        为4***********************************
****************************假设密钥长度        为5***********************************
0.07814965986394558
在密钥长度为5的时候得到了最大的重合指数。
要处理的子字符串，已经够single函数的处理
{0: 'ihdndxilhadwidwsdtxllwsslhunptwgdpnthdvvrttrthxihh', 1: 'yklgxefvwvnvynvrkefryvzkrkvziivkiinikjrrlrtfufkyz', 2: 'mnabqpzaiaplipavpavgqabpaxkvinzwvlippboztvptxvgmv', 3: 'ymoaeuityemuzmmpqmmuommuyqfooaneqxemqqufmpzaqmwnq', 4: 'sqvpxwsmixxhxxmxwxprlmrwsvplxvifcittqrrmxxmvvpoyw'}

2.寻找key

遍历每一个字串，然后从0-25给每个字符加偏移量，作为newstr，利用newstr和frequency频率分布表去计算重合指数，找到0.6左右的，那么偏移量则是正确的偏移量，但是这个是解密的偏移量，和key的字符的距离a的距离之后整好为26，因此要是算key需要进一步变换。

frequency = [0.082,0.015,0.028,0.043,0.127,0.022,0.02,0.061,0.07,0.002,0.008,0.04,0.024,0.06,0.075,0.019,0.001,0.06,0.063,0.091,0.028,0.01,0.023,0.001,0.02,0.001]
s = ['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']#字母出现频率
## 计算解密所用的偏移
def crack_key(new,len_key):
    key = ''
    for i in range(len_key):
        substring = new[i]
        print("当前字串为：",new[i])
        for n in range(26):
            dex = quasi_index(substring, n)
            print("假设子串移动{},拟重合指数为{:.4f}".format(s[n],dex))
            if dex >= 0.058:
                key += s[n]
                break
    print("******************************破解的最终密钥为%s*********************************" % key)
    return key
###quasi_index计算重合指数，frequencies[key]所代表的是假的字符，其真实身份得加个偏移n，因此frequency加上偏移n。
def quasi_index(str,n):
    #text = shift_text_left(text)
    # 计算字符频率
    frequencies = dict(Counter(str))
    #print(frequencies)
    sum = 0
    for key,value in frequencies.items():
        sum += frequencies[key]*frequency[ord(s[(ord(key)+n-ord('a'))%26])-ord("a")]
    return sum/len(str)
##得到加密key
key= ''
for i in range(5):
    key+=chr(26-(ord(dekey[i])-ord('a')) + ord('a'))
print(key)

可以得出解密密钥为:

当前字串为： ihdndxilhadwidwsdtxllwsslhunptwgdpnthdvvrttrthxihh
假设子串移动a,拟重合指数为0.0497
假设子串移动b,拟重合指数为0.0495
假设子串移动c,拟重合指数为0.0230
假设子串移动d,拟重合指数为0.0269
假设子串移动e,拟重合指数为0.0373
假设子串移动f,拟重合指数为0.0337
假设子串移动g,拟重合指数为0.0346
假设子串移动h,拟重合指数为0.0464
假设子串移动i,拟重合指数为0.0397
假设子串移动j,拟重合指数为0.0296
假设子串移动k,拟重合指数为0.0390
假设子串移动l,拟重合指数为0.0642
当前字串为： yklgxefvwvnvynvrkefryvzkrkvziivkiinikjrrlrtfufkyz
假设子串移动a,拟重合指数为0.0344
假设子串移动b,拟重合指数为0.0327
假设子串移动c,拟重合指数为0.0359
假设子串移动d,拟重合指数为0.0359
假设子串移动e,拟重合指数为0.0307
假设子串移动f,拟重合指数为0.0429
假设子串移动g,拟重合指数为0.0374
假设子串移动h,拟重合指数为0.0346
假设子串移动i,拟重合指数为0.0376
假设子串移动j,拟重合指数为0.0717
当前字串为： mnabqpzaiaplipavpavgqabpaxkvinzwvlippboztvptxvgmv
假设子串移动a,拟重合指数为0.0348
假设子串移动b,拟重合指数为0.0271
假设子串移动c,拟重合指数为0.0312
假设子串移动d,拟重合指数为0.0465
假设子串移动e,拟重合指数为0.0490
假设子串移动f,拟重合指数为0.0449
假设子串移动g,拟重合指数为0.0314
假设子串移动h,拟重合指数为0.0443
假设子串移动i,拟重合指数为0.0352
假设子串移动j,拟重合指数为0.0390
假设子串移动k,拟重合指数为0.0226
假设子串移动l,拟重合指数为0.0457
假设子串移动m,拟重合指数为0.0322
假设子串移动n,拟重合指数为0.0412
假设子串移动o,拟重合指数为0.0403
假设子串移动p,拟重合指数为0.0413
假设子串移动q,拟重合指数为0.0285
假设子串移动r,拟重合指数为0.0352
假设子串移动s,拟重合指数为0.0599
当前字串为： ymoaeuityemuzmmpqmmuommuyqfooaneqxemqqufmpzaqmwnq
假设子串移动a,拟重合指数为0.0391
假设子串移动b,拟重合指数为0.0357
假设子串移动c,拟重合指数为0.0438
假设子串移动d,拟重合指数为0.0404
假设子串移动e,拟重合指数为0.0371
假设子串移动f,拟重合指数为0.0383
假设子串移动g,拟重合指数为0.0474
假设子串移动h,拟重合指数为0.0407
假设子串移动i,拟重合指数为0.0301
假设子串移动j,拟重合指数为0.0259
假设子串移动k,拟重合指数为0.0471
假设子串移动l,拟重合指数为0.0205
假设子串移动m,拟重合指数为0.0265
假设子串移动n,拟重合指数为0.0337
假设子串移动o,拟重合指数为0.0684
当前字串为： sqvpxwsmixxhxxmxwxprlmrwsvplxvifcittqrrmxxmvvpoyw
假设子串移动a,拟重合指数为0.0297
假设子串移动b,拟重合指数为0.0312
假设子串移动c,拟重合指数为0.0351
假设子串移动d,拟重合指数为0.0426
假设子串移动e,拟重合指数为0.0262
假设子串移动f,拟重合指数为0.0352
假设子串移动g,拟重合指数为0.0358
假设子串移动h,拟重合指数为0.0550
假设子串移动i,拟重合指数为0.0351
假设子串移动j,拟重合指数为0.0387
假设子串移动k,拟重合指数为0.0350
假设子串移动l,拟重合指数为0.0479
假设子串移动m,拟重合指数为0.0371
假设子串移动n,拟重合指数为0.0304
假设子串移动o,拟重合指数为0.0362
假设子串移动p,拟重合指数为0.0378
假设子串移动q,拟重合指数为0.0406
假设子串移动r,拟重合指数为0.0421
假设子串移动s,拟重合指数为0.0470
假设子串移动t,拟重合指数为0.0324
假设子串移动u,拟重合指数为0.0301
假设子串移动v,拟重合指数为0.0427
假设子串移动w,拟重合指数为0.0641
******************************破解的最终密钥为ljsow*********************************
##加密密钥为：
prime

3.恢复文本

此步骤比较简单，通过密钥恢复相应文本，然后再把每一个组融合在一起，完事

def de(dic, key):
    # 遍历字典
    for mykey, value in dic.items():
        # 确保字典键在 key 中存在
        value_list = list(value)   
        # 遍历 value 列表中的每个字符
        for i in range(len(value_list)):
            # 检查字符是否为小写字母，并进行相应偏移
            if 'a' <= value_list[i] <= 'z':
                value_list[i] = chr((ord(value_list[i]) - ord('a') + ord(key[mykey]) - ord('a')) % 26 + ord('a'))
        dic[mykey] = ''.join(value_list)
    return dic
print(new,dekey)
myte = de(new,dekey)
print(myte)
def combine(dic):
    d={}
    for i in range(1000):
        d[i] = ''
        for mykey, value in dic.items():
            if i<len(value):
                d[i]+=value[i]
            else:
                continue
    return d


d = combine(myte)
last = ''
for key,value in d.items():
    last += value

print(last)
得到明文：
themostfamouscryptologistinhistorwoweshisfamelesstowhathedidthantowhathesaidandtothesensationalwayinwhichhesaiditandthiswasmostperfectlyincharacterforherbertosborneyardleywasperhapsthemostengagingarticulateandtechnicoloredpersonalitykkthebusiness

分隔后：
the most famous cryptologist in history owes his fame less to what he did than to what he said and to the sensational way in which he said it and this was most perfectly in character for herbert osborne yardley was perhaps the most engaging articulate and technicolored personality in the business