python - Playfair Hillclimbing破解

Question

我正在编写一个 python 脚本来破解 playfair 密码，只有密文。首先，我生成大约 30-100 个解密 key 并在密文上运行它们，对每个 key 的有向字母频率进行排名。对于下一代“一代”/迭代，我复制得分最高的那些。然后它们发生变异(字母在 5x5 网格中交换位置)并重新添加到下一次迭代，再次排名，依此类推。

我注意到脚本经常会找到一个局部最大值 - 一个给出类似分布的键，但不是真正的分布。我认为解决该问题的方法是为键的数量引入更多变化(到脚本结束时，所有键都几乎相同)。

我试图通过向每一代添加几个完全随机的 key 来实现它，但它们几乎立即被消除了。什么是更好的方法？我也考虑过模拟退火等策略，但不知道它们会有多大帮助。

编辑:根据要求样本密文(关键:公平竞争的例子)

['p', 'l', 'a', 'y', 'f']
['i', 'r', 'e', 'x', 'm']
['b', 'c', 'd', 'g', 'h']
['k', 'n', 'o', 'q', 's']
['t', 'u', 'v', 'w', 'z']

as el ir ul vi ne uz qk dm kz qe ca qe tb qc pv zb md nv om lo gv qo od er qc zg pv vk ov or iw zg ro nz ge ro af yp qe zi lo rk pr ad xl dl ix cl qr rk dq vu sa zb xv qe ho dm dn ok eb xe do bm iz kd de as kv ef kc rd lv om dm vy km ur et xe aq zb xe tx om rt gh rk hc fg mk py dr qo af zs xv nv ac df ad dl yr do bm ef pm zs lo ce yl ai ca nv ca fy wi dm ov ne tx zb bm kn ul bn ar km uz fo ka ro do gp lo kv dm ml qe zi lo rk pr ad xl tx zb le nv oc py dr lo ca le dx xa mo pr oi yp en dy oc dk zb as kv ix ol pr dr oq pb dr gb eo ak vg xe do df re zb pv nl cr do ya an ad iu dm re dm eo qm dm am pu ad xl nl er nv kz qn oq yg df pb uz fo ya ay dk vu lo gd ex ip ya bp up xv yf nv vk pz dm vq vo vk pr kz ro

Answer 1

应用于加密的爬山算法原理如下:

1. 随机生成一个 key (随机生成一个 25 个字符的字母表)并根据您的二合字母评分确定适合度。称其为“ parent ”
2. 对父级进行一些更改以生成“子级” key (5x5 网格 key 表中的随机交换并不是那么糟糕)并使用您的二合字母评分函数衡量其适合度。
3. 如果 child 比 parent 更健康，让 child 新 parent 并免除旧 parent
4. 回到 (2)，除非最近 1000 次没有改进回到 (1) 的变化

这是避免在有向图评分函数的局部最大值中被阻塞的方法。

如果你想要比爬山更好的结果，你必须开发模拟退火算法。此外，基于 trigrams 或 4-grams 的评分函数具有较少的局部最大值。如果您想更快地破解它，您可以从 Python 转向 C/C++。

HillClimbing 和模拟退火算法可用于破解 Playfair 密码以及所有其他基于 5*5 网格的密码，以及简单替换密码和 Vigenere 密码。

Playfair 密码的一个重要之处在于它很弱:5x5 网格的所有圆形水平或垂直排列都是等效 key 。因此该密码的算法收敛速度更快。

要使父字母表使用以下内容:

alpha='ABCDEFGHIKLMNOPQRSTUVWXYZ'
used=[0]*25;parent=['']*25
for i in range(25):
    j=randrange(25)
    while used[j]:j=randrange(25)
    parent[i]=alpha[j];used[j]=1

公平解密函数:

def DEplayfair(a,key):
l=[];order={}
for k in range(25):order[key[k]]=k
for i in range(0,len(a),2):
    ord1=order[a[i]]
    raw1=ord1//5
    col1=ord1%5
    ord2=order[a[i+1]]
    raw2=ord2//5
    col2=ord2%5
    if raw1==raw2:
        l.append(key[5*raw1 + (col1 + 4)%5])
        l.append(key[5*raw2 + (col2 + 4)%5])
    elif col1==col2:
        l.append(key[col1 + 5*((raw1 + 4)%5)])
        l.append(key[col2 + 5*((raw2 + 4)%5)])
    else:
        l.append(key[5*raw1 + col2])
        l.append(key[5*raw2 + col1])
return ''.join(l)

对于 SA 算法，您可以在以下位置找到 SA 的基本原理: http://en.wikipedia.org/wiki/Simulated_annealing

Playfair 密码在二战期间被美国海岸 guard 队使用，历史上有一个著名的 Playfair 密码: http://practicalcryptography.com/ciphers/playfair-cipher/

PS:您的 playfair 密码示例中的主角的名字是爱丽丝。