1

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

我注意到脚本经常找到一个局部最大值——一个给出类似分布的键，但不是真正的交易。我认为解决该问题的方法是为密钥的数量引入更多变化（在脚本结束时，它们几乎都相同）。

我试图通过向每一代添加几个完全随机的密钥来实现它，但它们几乎立即被淘汰。有什么更好的方法呢？我也想过模拟退火之类的策略，但不知道它们会有多大帮助。

编辑：按要求提供示例密文（关键：playfair 示例）

['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 vine uz qk dm kz qe ca qe tb qc pv zb md nv om lo gv qo od er qc zg pv vk ov 或 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

4

2 回答 2

3

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

  1. 随机制作一个密钥（随机制作 25 个字符的字母表）并根据您的二合字母评分确定适合度。称它为“父母”</li>
  2. 对父级进行一些更改以生成一个“子”键（5x5 网格键表中的随机交换还不错）并使用您的 digraphs 评分函数测量其适合度。
  3. 如果孩子比父母更健康，让孩子成为新的父母并放弃旧的父母
  4. 返回 (2)，除非最后 1000 次更改没有改进，在这种情况下返回 (1)

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

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

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

Playfair 密码的重要一点是它很弱：5x5 网格的所有圆形水平或垂直排列都是等效密钥。因此，该密码的算法收敛速度更快。

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

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

playfair解密功能：

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 密码在二战期间被美国海岸警卫队使用，并且有一个著名的历史 Playfair 密码： http: //practicalcryptography.com/ciphers/playfair-cipher/

PS：您的游戏密码示例中的主角的名字是爱丽丝。

于 2014-02-15T14:39:21.863 回答
0

如果我正确阅读了您的问题，您会改变您的一代，但您不会重新组合它。也许你可以这样做：

  1. 第 0 代是随机密钥。
  2. 选择 n 个排名最高的键，其余的都死掉。
  3. 将幸存者相互杂交。重组时发生低百分比突变。
  4. 冲洗并重复。

重组可能如下所示：

  1. 父母是A和B，他们产生n个后代。
  2. 对于每个后代，选择 0 <= x <= y < 25（可能带有约束 y - x > c）。后代的密钥是 A[:x] + B[x:y] + A[y:]。
于 2014-01-01T20:41:07.347 回答