维吉尼亚密码解密

维吉尼亚密码解密

该解密过程我们通过实验进行验证，原文是一篇英文文章，**为随机输入数。

• 原文：
  When it comes to online shopping different people holds different ideas towards it Some people seem extremely enjoy the way of buying things online because theyfeel online shopping is so convenient Some just do not believe that they can buygood quality commodities from Internet As far as I am concerned I think onlineshopping creates lots of benefits to people Firstly buying things online is a way of saving time Compared with the traditional wayof shopping we have no need to go out to pick up our favorite goods from storeto store Just a click we can have things in our shopping cart and just waitfor the goods to be delivered to us To this extent not only we can save thetime of finding things from store to store but we do not need to spend time ontransportation Thus we can save lots of time to enjoy fun Secondly buying things online can save our money People buy commodities by Internet notonly because it saves us time but also we can save lots of money It is oftenseen that some people just go to the physical store to check out thecommodities they want to buy and then they would search for their favoritecommodities online and take the order People do this just because they knowthat online goods are usually cheaper than the goods displayed in shop windowbecause online shop have no need to pay the rent So people are more inclinedto buying things from online store Thirdly convenience is the last but not least thing of shopping online Since we canbuy things online there is no need to go out to look for things we want to buy What we need to do is to simply sit before our computer search for thingswe want to buy click our favorite thing and then pay our order by our bankcard And then you just need to wait for your goods to be delivered to yourhomeInconclusion shopping online is a convenient time-saving and money saving wayof buying things Therefore we can benefit a lot from shopping online That is the reason of why shopping online has developed faster and faster in recentyears

• **:
  ldgsdbd

• 密文：
  Hkkf lu fzpkk wp ryoofh tkzsvaqh gtilwufqe skgsmh srrvv elqikjhow tgksv urhdxvv jw Drsw sfraok khfp pazjhnhwb kfmpb ekk odz rq eaqloj ekofjt ryoofh chndakh ukpblwhm ryoofh tkzsvaqh ld vu uroypqowqu Vzpk bxtw or tgw chwlknh uklw zzhz flq hmbhrzg wmdmleb igpnrolzaht icrs Aquhcqkl Dt ilu gk L bp nrtuhsqpg O lkjqv rtdlohdkuhsjqr fxwduhd oulv pi mhtwijwd wu hhpswh Lautwwb hmbjqr wnaqhv zqraqf ld d csb pi ddbaqh wtpk Urnslukv zjws wnw wsdolzarodw zgqrg vsrvhloj hh nsyf qz qkwg ur rr umw ur alic xq rfu lsyputwk yrpgd ixgp twzuklr twzuk Bxtw l frafl zp fgf kbyp wnaqhv tq umu tkzsvaqh fluz sqe mfvz odjwqrx lkf jzrjk wp ep gkdlwhchj lr vv Er zzlt hiwkfw ore rtdb xh ndt kdwh ekkllnh zi laqelyj zzlojd ixgp twzuk lr twzuk txu zp gu fru qphj lr tspqj llnh zqzjdovarxldulzq Zzxt zp fgf vbyp oulv pi elsw wp hymuq ivq Dhigqeoj eaqloj ekofjt ryoofh ddy vgnh pxc pufhz Sprvdh cxj fueppgtwowv cb Tqzwuohe qulrooj ekudvvp lz kdwhd xy llnh mxz sotr hh isq tdgh rgwt rq pufhz Le ly giuhyvkwq uklw ygpf sprvdh kxdw mg wp wsh vzbtlndr kwpup wu ukffv ral wihnrserelelkk wihj zgfw ur mxe sqe wsht lkfb hradg thluiz ipu ekkau gdgrxawffzpsggjwthy gqmlyh gfg udvh zzh puohx Hhpswh jg wild makw chndakh ukpb qfrxwsdz gqmlyh mgrev luk mvvdwoe ukfdahx lkbq ekk yrpgd goksmdjhj aq tkzs caqerhekudvvp rtdloh dkuh kbyp qu fhfg er vsb ukp ukfw Tr ahuhof dch sguf lyfraqfger hmbjqr wnaqhv quue rootqk kwpup Wnaueoj fufyfqthtuh jv ekk ddtw mxz fru opdyl wilyj ux virasofj pqwltw Vjqnh cw fbqmxe lkjqrv ufojqp wnwuf ld qu fhfg er mg rvw er rgrl izu zzlojd zk odow er hmb Xklw cw qfho wu vr jv er yapqoj vol efizuk gxs fzpvmwfu dhgjfi izu zzlojdzk odow er hmb dotfq gxs ilyujluh ekofj bqo wnwq qdj raj rsgpu hq rvu mdtcfbuo Dtv wihy bum mvve qkwg ur hdol ipu jraj jprov zg ef gpoonhsho wu qrvusrswLofzqidxtlzq yzrqstqm gqmlyh ok d dryykflfqe woeh-tdglty dog xrtwb tdglty zbbzi hmbjqr wnaqhv Ekkjhgrch cw fbq mhtwijw l oul isrx vngsqlyj ufojqp Wnsw jv ekk jhbvzq ux zib dkuhsjqr rtdloh sdy vhwhwrvwg gddwkj dog qdylhs ly ukuhowjhgjv

• 解密，最重要的一个点就是**，找到合适的突破口进行**是解密的关键所在。

分析：针对于维吉尼亚密码的解密，首先得分析该类型密码的破绽，存在哪些漏洞，维吉尼亚是简单分组密码，其原理是通过一组**，对密文进行加密，对密文进行一定长度的循环凯撒密码加密，所以易知对维吉尼亚密码的解密得分为两个步骤，第一步解得**长度，第二部解得明文。

一、解**长度

思路：

1. 重要公式：
   如下图所示：
   
   采用计算CI重合指数的方法，即在英文中，常用语句的字母的出现频率大致是确定的，我们可以通过计算解密所得的明文字母频数与标准的字母频数进行比对，判断是否解密成功，其中CI=0.065。
   上式中，L为总的字母个数，N为指定字母的个数，i即指a～z。

2.密文分组：
将密文按照**的长度k，分为k个分组，即每相隔k个字母的明文是通过同一个字母加密所得，即将密文分片所得的k个分组，相当于k个凯撒密码加密，故提供给我们频数分析的可能性。

以下分析代码：

• 去掉密文空格

def q_blackspace(str):
    cipher = ''
    for i in range(len(str)):
        if str[i].isalpha():
         cipher+=str[i]
        else :
         cipher=cipher
    return cipher

• 密文分组

def divid(str,i):
    text = ['', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '','', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '','', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '','', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '']
    for k, v in enumerate(str):
       text[k%i]+=v
    return text     

• 计算CI’并求其与CI差距

def every_cii(str):
 count={'a':0,'b':0,'c':0,'d':0,'e':0,'f':0,'g':0,'h':0,'i':0,'j':0,'k':0,'l':0,'m':0,'n':0,'o':0,'p':0,'q':0,'r':0,'s':0,'t':0,'u':0,'v':0,'w':0,'x':0,'y':0,'z':0}
 ci_num=0
 num=0
 str=str.lower()      #改为小写
 for i in str:
         count[i]+=1     #从a到z计数，并存在count列表中
 for m in 'abcdefghijklmnopqrstuvwxyz':
    num+=(count[m]*(count[m]-1))/(len(str)*(len(str)-1));#从a到z循环，计算该字符串的ci指数
 ci_num=abs(num-0.065);     #为方便，求出其去标准频率的0.065的差距，利于后期排序

• 遍历得每种**长度的情况

def ave_ci(str,ci_arr):
    r=0
    for i in range(1,27):
      text=divid(str,i)
      for ii in range(i):
        r += every_cii(text[ii])
      r=r/i
      ci_arr.insert(i-1, (i,r))
    return ci_arr   #计算每种分组长度的可能，并以二元组的形式存在数组ci_arr中

• 主调函数、排序

def dec_len(str):
    ci_arr=[]
    mess_result=ave_ci(q_blackspace(str),ci_arr)
    result=sorted(mess_result, key=lambda x:x[1])   #对ci_arr进行排序，从小到大
    print result

• 针对密文的输出结果：

[(14, 0.006145054975616411), (7, 0.0066786142877426225), (21, 0.009346994590347445), (15, 0.020496316611014594), (1, 0.020755158080306743), (22, 0.021177951472325547), (18, 0.021387070670065667), (19, 0.021402737909189836), (27, 0.021812779379314584), (17, 0.021889818114162848), (20, 0.021890164975258367), (16, 0.022055466450444584), (23, 0.022170841249776075), (8, 0.022205866795625494), (25, 0.02223927433246826), (9, 0.022355999442721926), (24, 0.022575681155529447), (10, 0.02278650023855121), (12, 0.022911937844760505), (11, 0.023123366409123335), (26, 0.02364588606820494), (13, 0.023844513807850264), (6, 0.024844463837975974), (5, 0.025976129585119932), (4, 0.028644750196721906), (2, 0.03109063141414911), (3, 0.031255491803577985)]

我们按照计算结果排序，看出最有可能的**长度为14、7、21。故可以大胆猜测**长度为7，而我们的真实**长度确实是7。

二、解**

思路：

• 确定**长度
  根据第一步得到**长度，可以减轻**的计算量，在本次实验中长度为7。
• 重要公式
  如下图所示：
  
  L与N的含义不变，f是英文字母出现的标准频率，此时为CI’。
• 在按照**长度将密文分组后，针对每个分组便是凯撒密码的**求解，每组密码都是相同位移加密，故对每组密码进行a～z的**并排序。

以下分析代码：

• 去空格、分组等函数不变
• 计算CI’

def c(str): #标准的字母频数，用以比较分析
 count={'a':0,'b':0,'c':0,'d':0,'e':0,'f':0,'g':0,'h':0,'i':0,'j':0,'k':0,'l':0,'m':0,'n':0,'o':0,'p':0,'q':0,'r':0,'s':0,'t':0,'u':0,'v':0,'w':0,'x':0,'y':0,'z':0}
 alp_fre = {'a': 0.08167, 'b': 0.01492, 'c': 0.02782, 'd': 0.04253, 'e': 0.12702, 'f': 0.02228,  'g': 0.02015, 'h': 0.06094, 'i': 0.06966, 'j': 0.00153, 'k': 0.00772, 'l': 0.04025,  'm': 0.02406, 'n': 0.06749, 'o': 0.07507, 'p': 0.01929, 'q': 0.00095, 'r': 0.05987,  's': 0.06327, 't': 0.09056, 'u': 0.02758, 'v': 0.00978, 'w': 0.02360, 'x': 0.00150,   'y': 0.01974, 'z': 0.00074}
 ci_num_grap=0
 num=0
 str=str.lower()
 for i in str:
    count[i]+=1
 for m in 'abcdefghijklmnopqrstuvwxyz':
    num+=(count[m]/len(str))*alp_fre[m];        #计算CI'指数
 ci_num_grap=abs(num-0.065);     #与标准0.065的差距，方便后期排序
 return ci_num_grap

• 凯撒***密（主调函数）

def guess_message(s,i):
   str= q_blackspace(s)   #去空格 
   text=[]
   text=divid(str,i)  #分组
   for i in range(i):
     alp_arr = []
     for num in range(26):
          txt = ''
          for m in range(len(text[i])):     #每个分组都是凯撒加密，对每个分组进行**
              txt+=chr(((ord(text[i][m])-ord('a')-num)%26)+ord('a'))
          ci_num = c(txt)
          alp_arr.insert(0,(chr(num+ord('a')),ci_num))  #插入结果分组
     result = sorted(alp_arr, key=lambda x: x[1])     #根据CI'指数排序
     print result

• 输出结果

[('l', 0.0028151489361702142), ('w', 0.01695459574468086), ('v', 0.020135319148936168), ('a', 0.02172829787234043), ('h', 0.02254395744680851), ('m', 0.023144382978723406), ('z', 0.023236680851063833), ('p', 0.02548000000000001), ('y', 0.025681063829787243), ('k', 0.026282468085106377), ('r', 0.026378595744680863), ('s', 0.027296127659574475), ('e', 0.027852297872340427), ('f', 0.028252127659574466), ('x', 0.028422212765957446), ('i', 0.02867919148936171), ('g', 0.02926451063829788), ('q', 0.029289191489361703), ('b', 0.030023914893617033), ('d', 0.03063591489361702), ('n', 0.03116272340425532), ('u', 0.03165570212765958), ('t', 0.03230587234042553), ('c', 0.03262438297872341), ('j', 0.03343795744680851), ('o', 0.03472736170212766)]
[('d', 0.0004848085106382988), ('o', 0.01968795744680852), ('n', 0.02099000000000001), ('z', 0.021403787234042557), ('q', 0.02149289361702128), ('e', 0.02387591489361702), ('h', 0.025493234042553208), ('s', 0.02551612765957447), ('k', 0.025694127659574476), ('r', 0.025970680851063827), ('j', 0.026326723404255327), ('m', 0.026786936170212765), ('x', 0.026916255319148936), ('y', 0.026944042553191494), ('c', 0.02780897872340425), ('w', 0.02802514893617021), ('p', 0.028341617021276598), ('a', 0.028703276595744683), ('t', 0.02941331914893619), ('g', 0.030611829787234042), ('u', 0.03222493617021277), ('b', 0.03243293617021276), ('i', 0.032574765957446815), ('f', 0.033024808510638305), ('l', 0.033432553191489356), ('v', 0.03583234042553192)]
[('g', 0.0020319574468085078), ('r', 0.016677914893617043), ('c', 0.01918076595744681), ('h', 0.020081063829787235), ('k', 0.02188148936170213), ('q', 0.022576127659574473), ('t', 0.02387144680851063), ('v', 0.024599106382978735), ('w', 0.025092255319148944), ('s', 0.025486382978723403), ('d', 0.025580808510638306), ('m', 0.02766578723404256), ('u', 0.027908680851063836), ('z', 0.02847242553191489), ('a', 0.02856753191489362), ('n', 0.029236255319148946), ('b', 0.029299829787234048), ('o', 0.02976829787234042), ('f', 0.03001263829787234), ('x', 0.031122808510638297), ('p', 0.03175225531914894), ('i', 0.03197574468085106), ('j', 0.03290365957446809), ('e', 0.035402680851063836), ('l', 0.03622059574468085), ('y', 0.03670540425531915)]
[('s', 0.0015771063829787269), ('h', 0.019892340425531924), ('d', 0.020941617021276608), ('w', 0.022975574468085104), ('o', 0.02317863829787234), ('t', 0.023362680851063834), ('m', 0.023416765957446815), ('f', 0.024127957446808526), ('y', 0.024156340425531914), ('c', 0.024386425531914897), ('i', 0.02639659574468086), ('z', 0.026916723404255327), ('n', 0.02729280851063831), ('r', 0.0273184255319149), ('b', 0.027386638297872336), ('g', 0.027873957446808505), ('x', 0.02923910638297872), ('u', 0.030183276595744678), ('e', 0.030257914893617024), ('j', 0.030411404255319144), ('l', 0.030578680851063827), ('a', 0.03198051063829786), ('v', 0.032655531914893614), ('p', 0.03389285106382979), ('q', 0.03457191489361702), ('k', 0.03503821276595745)]
[('d', 0.0007325106382978508), ('o', 0.01972697872340426), ('z', 0.020366808510638303), ('q', 0.021672978723404256), ('e', 0.02206017021276597), ('s', 0.02367463829787235), ('x', 0.023870340425531912), ('h', 0.024320723404255326), ('p', 0.024980723404255327), ('n', 0.02522740425531915), ('j', 0.025481191489361697), ('t', 0.025830170212765964), ('y', 0.02752987234042554), ('m', 0.02859693617021277), ('k', 0.02866246808510639), ('w', 0.02893187234042552), ('i', 0.02911536170212766), ('c', 0.0297431914893617), ('u', 0.029938893617021282), ('r', 0.030100340425531925), ('f', 0.030192638297872346), ('l', 0.031682638297872344), ('a', 0.03176238297872341), ('b', 0.03415812765957446), ('v', 0.035863404255319156), ('g', 0.03725225531914894)]
[('b', 0.0021237179487179486), ('c', 0.020288589743589748), ('q', 0.02133303418803418), ('f', 0.02167102564102564), ('m', 0.022011538461538464), ('p', 0.02211538461538462), ('a', 0.022412991452991457), ('l', 0.022545470085470087), ('o', 0.023863162393162406), ('x', 0.02489200854700855), ('h', 0.025614102564102577), ('v', 0.027244829059829057), ('n', 0.027753418803418792), ('r', 0.02778816239316239), ('g', 0.028158888888888886), ('i', 0.028315299145299143), ('w', 0.029228888888888888), ('u', 0.030092350427350437), ('j', 0.031249914529914526), ('t', 0.03126111111111111), ('d', 0.03181431623931624), ('k', 0.03248611111111111), ('y', 0.0326451282051282), ('s', 0.03267200854700855), ('e', 0.0343425641025641), ('z', 0.0360859829059829)]
[('d', 0.0008901709401709368), ('o', 0.018358461538461525), ('s', 0.019933675213675214), ('z', 0.021666410256410258), ('e', 0.02207884615384615), ('h', 0.02285346153846155), ('q', 0.023031581196581198), ('n', 0.023857991452991452), ('c', 0.025614273504273505), ('r', 0.02577615384615385), ('p', 0.027002179487179492), ('y', 0.027380512820512827), ('j', 0.027981282051282044), ('t', 0.028960470085470084), ('x', 0.029061410256410264), ('k', 0.029211111111111118), ('u', 0.030038547008547002), ('i', 0.030122051282051282), ('w', 0.03014696581196582), ('f', 0.030301923076923074), ('m', 0.03083205128205127), ('a', 0.031139316239316234), ('v', 0.033120170940170945), ('l', 0.03382452991452992), ('g', 0.03412427350427351), ('b', 0.03448252136752137)]

能够看出，每个分组最可能解密字母在第一位，即**为‘ldgsdbd’，与设置的**完全相同，即完成维吉尼亚密码解密。

总结：

1. CI重合指数法是解密关键所在，密文中隐藏字母频数信息是维吉尼亚密码最大的缺陷，我们便抓住这点进行***密。
2. CI指数的计算公式不仅仅是简单的字母频数平方，得稍作变通，初期我将CI计算公式弄错，始终得不到正确结果。
3. 维吉尼亚密码解密分为两个步骤更为简单，求解**长度，其次求解**，否则一次性**计算量相当大，就如本实验，两次**，计算次数是26+50（假设**长度最大为50），而一次**的话，计算次数是26×50，计算量明显减轻。