代换密码解密

请解密以下代换密码的密文:
JGRMQOYGHMVBJWRWQFPWHGFFDQGFPFZRKBEEBJIZQQOCIBZKLFAFGQVFZFWWE
OGWOPFGFHWOLPHLRLOLFDMFGQWBLWBWQOLKFWBYLBLYLFSFLJGRMQBOLWJVFP
FWQVHQWFFPQOQVFPQOCFPOGFWFJIGFQVHLHLROQVFGWJVFPFOLFHGQVQVFILE
OGQILHQFQGIQVVOSFAFGBWQVHQWIJVWJVFPFWHGFIWIHZZRQGBABHZQOCGFHX

首先我们要知道代换密码的定义,代换密码就是使用substitution来进行加密的算法。通过查询资料,知道攻击方法主要有:
①穷举法:在密钥空间较小的情况下,采用暴力破解方式攻击方法。
②频率统计:在密文长度足够长的时候,可使用词频分析。
③爬山法:选择性地尝试不同解密密钥,然后给每一个解密出来的明文标记上一个适应度。若解密出来的明文越接近我们的日常用的英语,它的适应度就越高;若解密出来的明文越难读懂或者越不像我们日常用的英语,则其适应度越低。

本来我已经选择用频率分析的方法去做,然后得出未解密的字母频率为:
[('F', 37), ('Q', 26), ('W', 21), ('G', 19), ('L', 17), ('O', 16), ('V', 15), ('H', 14), ('B', 12), ('P', 10), ('I', 9), ('J', 9), ('R', 7), ('Z', 7), ('M', 4), ('E', 4), ('C', 3), ('K', 3), ('A', 3), ('Y', 3), ('D', 2), ('S', 2), ('X', 1)]
解密后的字母频率为:[('E', 37), ('T', 26), ('S', 21), ('R', 19), ('N', 17), ('O', 16), ('H', 15), ('A', 14), ('I', 12), ('M', 10), ('C', 9), ('U', 9), ('Y', 7), ('L', 7), ('P', 4), ('F', 4), ('G', 3), ('B', 3), ('D', 3), ('V', 3), ('X', 2), ('W', 2), ('K', 1)]
发现跟自然语言中的26个字母出现的频率不接近,所以可以知道是适应度的问题,不能求出一个最佳的答案,故使用“爬山法”。

最后决定用爬山法完成以上代换密码的解密。有关quadgram statistics的适应度计算方法的详细介绍可点击这里。
(备注:quadgrams.txt和ngram_score.py可也在上面的链接中的文章最下方获取。其中ngram_score.py所用的函数不适用于python3.0,因为我试过T_T)

算法步骤:
①随机生成一个key,称为parentkey,用它解密得对应的明文m1,对明文计算适应度d1
②随机交换parentkey中的两个字符得到子密钥child,解密出对应的明文m2并计算适应度d2
③若d1<d2,则child成为新的parentkey
④不断循环进行步骤②③直到最后的1000次循环中不再有更高的适应度生成
⑤回到①重新生成parentkey继续迭代寻找,或者由操作者终止程序
重新执行①,是为了防止②③的操作使结果陷入局部最优的困境。对于生成的明文的适应度的比较,其实可以看作是对不同解密密钥的比较,解密出来的明文的适应度越高,对应的密钥就更好。
quadgram statistics的适应度计算方法

算法思路:
因为整个密文都只是大写英文字母,所以并不需要进行字符转换操作。解密的时候,在生成了key之后,将key放入一个字典变量中,字典中每个变量都是“密文字符:明文字符”的映射对,从而对密文的字符进行一个接着一个地转换。循环嵌套有两层,外层是每次随机生成一个起始的parentkey,里层进行爬山法,每次随机交换parentkey里的两个元素以解密,最后每次外层循环都判断一次是否找到更优的密钥。

以下是main.py主程序:

# -*- coding: UTF-8 -*-
import random
from ngram_score import ngram_score
#参数初始化
ciphertext = 'JGRMQOYGHMVBJWRWQFPWHGFFDQGFPFZRKBEEBJIZQQOCIBZKLFAFGQVFZFWWEOGWOPFGFHWOLPHLRLOLFDMFGQWBLWBWQOLKFWBYLBLYLFSFLJGRMQBOLWJVFPFWQVHQWFFPQOQVFPQOCFPOGFWFJIGFQVHLHLROQVFGWJVFPFOLFHGQVQVFIEOGQILHQFQGIQVVOSFAFGBWQVHQWIJVWJVFPFWHGFIWIHZZRQGBABHZQOCGFHX'
 
parentkey = list('ABCDEFGHIJKLMNOPQRSTUVWXYZ')
#只是用来声明key是个字典
key = {'A':'A'}
#读取quadgram statistics
fitness = ngram_score('quadgrams.txt')
parentscore = -99e9
maxscore = -99e9
j = 0
 
print('---------------------------start---------------------------')
while 1:
  j = j+1
  #随机打乱key中的元素
  random.shuffle(parentkey)
  #将密钥做成字典
  for i in range(len(parentkey)):
    key[parentkey[i]] = chr(ord('A')+i)
    #用字典一一映射解密
  decipher = ciphertext
  for i in range(len(decipher)):
    decipher = decipher[:i] + key[decipher[i]] + decipher[i+1:]
  parentscore = fitness.score(decipher)#计算适应度
  #在当前密钥下随机交换两个密钥的元素从而寻找是否有更优的解
  count = 0
  while count < 1000:
    a = random.randint(0,25)
    b = random.randint(0,25)
    #随机交换父密钥中的两个元素生成子密钥,并用其进行解密
    child = parentkey[:]
    child[a],child[b] = child[b],child[a]
    childkey = {'A':'A'}
    for i in range(len(child)):
      childkey[child[i]] = chr(ord('A')+i)
    decipher = ciphertext
    for i in range(len(decipher)):
      decipher = decipher[:i] + childkey[decipher[i]] + decipher[i+1:]
    score = fitness.score(decipher)
    #此子密钥代替其对应的父密钥,提高明文适应度
    if score > parentscore:
      parentscore = score
      parentkey = child[:]
      count = 0
    count = count+1
  #输出该key和明文
  if parentscore > maxscore:
    maxscore = parentscore
    maxkey = parentkey[:]
    for i in range(len(maxkey)):
      key[maxkey[i]] = chr(ord('A')+i)
    decipher = ciphertext
    for i in range(len(decipher)):
      decipher = decipher[:i] + key[decipher[i]] + decipher[i+1:]
 
    print ('Currrent key: '+''.join(maxkey))
    print ('Iteration total:', j)
    print ('Plaintext: ', decipher)

算法结果:


20180108115149670.png
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 214,658评论 6 496
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 91,482评论 3 389
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 160,213评论 0 350
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 57,395评论 1 288
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 66,487评论 6 386
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 50,523评论 1 293
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 39,525评论 3 414
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 38,300评论 0 270
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 44,753评论 1 307
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 37,048评论 2 330
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 39,223评论 1 343
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 34,905评论 5 338
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 40,541评论 3 322
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,168评论 0 21
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,417评论 1 268
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 47,094评论 2 365
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 44,088评论 2 352

推荐阅读更多精彩内容

  • 题目: 请解密以下代换密码的密文: JGRMQOYGHMVBJWRWQFPWHGFFDQGFPFZRKBEEBJI...
    FALLING_SKY阅读 7,494评论 3 2
  • [toc] 常见编码 1.ASCII编码 ASCII编码大致可以分作三部分组成: 第一部分是:ASCII非打印控制...
    William92阅读 3,988评论 0 1
  • 对课程期末考试的个人复习总结 一、概述 三个目标(CIA):机密性(防泄漏),完整性(防篡改),可用性其他性质:真...
    okcOu阅读 2,777评论 3 1
  • 代换密码的密码分析 使用单表代换密码,对于给出的密文进行分析并得到结果,了解加密解密过程 密文信息如下:AHNFC...
    柳妹要努力阅读 2,144评论 0 0
  • 1. 常用加密算法可以分为单向加密和双向加密。 (1)单向加密: 只提供单向加密不能解密,不可逆的过程。通常用来存...
    刘小刀tina阅读 7,489评论 0 0