2015第八屆挑戰(zhàn)賽一階段優(yōu)秀集含abcd題

編號(hào)專用頁(yè)參賽隊(duì)伍的參賽隊(duì)號(hào)：（請(qǐng)各個(gè)參賽隊(duì)提前填寫(xiě)好競(jìng)賽統(tǒng)一編號(hào)（由競(jìng)賽送至評(píng)委團(tuán)前編號(hào)競(jìng)賽評(píng)閱編號(hào)（由競(jìng)賽評(píng)委團(tuán)評(píng)閱前進(jìn)行編號(hào)數(shù)學(xué)建模網(wǎng)絡(luò)賽第一階段 替換式自動(dòng)化破譯算關(guān)鍵 頻率時(shí)間復(fù)雜度單字母加密自動(dòng)化破 要古典是學(xué)的，它是由基于字符的算法構(gòu)成，可用并機(jī)械操作實(shí)現(xiàn)加。目前行之有效的方法則是頻率分析法，但是利用傳統(tǒng)頻率分15-24的長(zhǎng)單詞庫(kù)群和字母長(zhǎng)1-8字典庫(kù)群，使模型可實(shí)現(xiàn)單詞的快速搜索和匹配。模型一的算法分為三個(gè)模塊：（1）頻率：先統(tǒng)計(jì)密文中單字母、雙字母組合頻率并分組，再對(duì)分組頻率進(jìn)行匹配，從而確定最高頻字母t,h,e。目越少，故匹配成功后正確率很高。（3）動(dòng)態(tài)逐詞：先將已破譯密鑰字母實(shí)例統(tǒng)計(jì)驗(yàn)證，該算法破譯大約5萬(wàn)字母數(shù)的文章，用時(shí)僅2.75s。多篇加密文章，得出密鑰字母正確個(gè)數(shù)穩(wěn)定在20個(gè)左右，密鑰字母的正確率均F(n)=(C2+2)n+C1O(n)，其C1,C2是依賴于字典庫(kù)總詞數(shù)的參賽隊(duì)號(hào):所選題目 Decryptionmethodisfrequency ysis,buttheuseoftraditionalfrequencyysismethod,withlargecomputation,thecomputationtimeislong, andsoonneedtoomuchhumanintervention.Sothispaperproposesandecryptionalgorithm,encryptionmethodofsinglelettertheencryptedModel1:Wehavetoimprovethetraditionalmethod,anewautomaticdecryptionmodelisestablished,notonlycansubstantiallyreducecomputingtime,andcanbeaccurateandefficientdecodingciphertext.Firstwehavethedataneededtomeasureoutthemodelofthemodel,theletterslengthof15to24longwordsdictionarylibrary1-8ofthedictionary,inthemodel1isdividedintothreesteps:(1)thefrequencyofcipherattackfirst,andthestatisticalfrequencyofsingleletters,doublelettercombinationsandgrou,andthengroupedfrequencymatching,ysisofbasictodeterminethehighestfrequencyofthelettere,he,th,todeterminet,h,e,(2)longwordsonciphertextattacks,namelyinthecrackofasmallamountofhighfrequencylettersaftergenerationintotheciphertext,extractthelongestwordinlongwordsdictionarylibrarymatchinggraduallydecipheringsecretkeymoreletters.Becauseofthelongerthewords,thelessthenumber,soafterthesuccessofthematchingaccuracyishigher.(3)thelastwillbethekeyletterssubstitutioncipher,andtheciphertextwiththewordfortheunitofthescan.Matchthewordsinadictionaryinthelibraryonebyone,getthesimilarwords;Accumulatedeachsimilarwordmatchingletterssecretkeyagain,untiltherecordnumberofsecretkeyletter>=24,eventuallytoeverysecretkeyletters,selectthehighestcumulativenumberofmatchingastheultimatesecretkey,outputthecompletekey.Verifiedbymulti-instancestatistics,thedecryptionalgorithmtodecipherthenumberofarticlesabout50000letters,itonlyneeds2.75s.Model2:Toevaluatethemodeladecryptionalgorithmdecodingabilityofthemodel,wefromthefollowingtwoaspects:(1)consideringtheaccuracyofthealgorithmdecoding;Testedmuchofthearticle,throughthestatisticcanbeconcludedthatthekeyletterscorrectnumberstabilityin20,thekeyletterscorrectlyabout80%,averagelettersinfullaccuracyofabout96%(2)breakthetimecomplexityofcipheralgorithm.Thelessasthenumberofletters,decodingtimegrowswiththeincreaseofthenumberofletters.Whilethenumberoflettersafterreachingacertainthreshold,decodingtimetendstobestable.Becausemodelalgorithmonlyneedtoextractthepartialwordsinthearticletheamountofinformationthatcanbedecodedkey.Articletherestoftheworddoesnotaffectthealgorithmdecodingtime,sothelongerthearticles,perunittimedecodingefficiencyishigher.Tosumup,thismodelcanefficientlyaccuraytodecrypttheciphertext,algorithmfasttimeshortly, esthetraditionalfrequencyysismethodtime-consuming,thedisadvantageofoperationefficiencyisnothigh.Inaddition,wealsotheimprovementandpopularizationofdirectionaswellastheadvantagesanddisadvantagesofthemodelarediscussed.attacksimecomplexitSingleencyptioAutoatic背

一、問(wèn)題重述一系列嚴(yán)重的問(wèn)題，就是其中突出的一個(gè)。由于網(wǎng)絡(luò)中著許多重要、敏感數(shù)據(jù)，因此，已經(jīng)越來(lái)越受到人們的關(guān)注。為確保信息的安全性，人們?cè)诩夹g(shù)上主要采用學(xué)的方法。問(wèn)題的提出二、模型假發(fā)生的長(zhǎng)度變化。（如動(dòng)詞ing形式和ed形式）三、符號(hào)說(shuō)fi表示26個(gè)字母按照字母表順序的第i個(gè)字表示密鑰中第i個(gè)字表示W(wǎng)i所對(duì)應(yīng)的明C表示i個(gè)密鑰是否正確，用0,1區(qū)分正確PQZF四、模型的建立與求解模型一的分析與求解模型一的分析在學(xué)中，有許多的的編制密鑰的方法，其中較為簡(jiǎn)單的是替換式，夠自動(dòng)化，減少運(yùn)算時(shí)間，更加精確高效破譯密文（模型步驟見(jiàn)下圖）。圖1：模型一的問(wèn)題分析圖模型的準(zhǔn)備（一首先在題目中所給COCA語(yǔ)料庫(kù)[1]中所有的參考文章，將超過(guò)百篇英文文章合并。我們?cè)谡Z(yǔ)料庫(kù)中統(tǒng)計(jì)長(zhǎng)度l15l24的單詞，建立對(duì)應(yīng)單詞長(zhǎng)度為l的長(zhǎng)單詞字典庫(kù)，為模型算法中長(zhǎng)單詞做準(zhǔn)備。同時(shí)，我們?cè)龠x用一本常用英文字典[3](大小630kb)，建立常用英文單詞字典庫(kù)（后稱字典庫(kù)）。并且，將字典庫(kù)也拆分成單詞長(zhǎng)度為l1l8的字典庫(kù)（二）在語(yǔ)料庫(kù)中,對(duì)26個(gè)英文字母分別進(jìn)頻，可以發(fā)現(xiàn)各字母出現(xiàn)的表126個(gè)英文字母在英語(yǔ)語(yǔ)料庫(kù)中出現(xiàn)的頻率ABCDEFGHIJKLMNOPQRSTUVWXYZ----表2：各英語(yǔ)字母頻率分組極高頻率字母組E次高頻字母組(0.06~TAOINSH中等頻率字母組D低頻率字母組(0.015~CUMWFGYP甚低頻率字母組(VKJXQ母數(shù)近2000萬(wàn)計(jì)得到雙字母雙字母組合情況過(guò)多(2626種)并圖2：雙字母組合頻率前十（3）表3：雙字母組合的頻率分極高頻率雙字母組t h次高頻雙字母組(0.015~ineran中頻率雙字母組onaten（五）最后，在語(yǔ)料庫(kù)中，統(tǒng)計(jì)出3個(gè)字母單詞的出現(xiàn)次數(shù)，得到3個(gè)字母單詞出現(xiàn)次數(shù)的前七位（測(cè)試基數(shù)為10000）。表4：3個(gè)字母單詞的出現(xiàn)次數(shù)（單位：次由上表分析，可以得出theand這兩個(gè)單詞的出現(xiàn)頻率為35.42%16.65%，所占的比例相對(duì)較大，因此the和and模型的建立通過(guò)以上模型準(zhǔn)備，我們建立了長(zhǎng)單詞字典庫(kù)（15l24）和英文單詞字典庫(kù)（1l8），并將長(zhǎng)單詞字典庫(kù)按照字母的個(gè)數(shù)進(jìn)行劃分，如單位長(zhǎng)度為15的劃分成一個(gè)組。另外對(duì)英語(yǔ)單詞字典庫(kù)也進(jìn)行了同樣的分組，這樣可以方圖3：模型一流程圖（一）頻率Wi表示密鑰中第iwiWi所對(duì)應(yīng)的明文，其中 W26，1 w26 w ...W 26 26其中表示的是密文轉(zhuǎn)化成明文的算法，是可逆的，1是明文轉(zhuǎn)化成密Step2：統(tǒng)計(jì)頻率分組之后，將模型準(zhǔn)備中相應(yīng)的頻率進(jìn)行匹配，自然密文中字母頻率最高的3個(gè)及雙字母組合頻率最高的3個(gè)對(duì)應(yīng)明文中出現(xiàn)頻率最高的3個(gè)字母和雙字母組合，這樣就可以確定出密文中出現(xiàn)頻率較高的一部分字母，不妨假設(shè)字母aeio頻率流程圖如下圖4：頻率流程（二）長(zhǎng)單詞Step4：最長(zhǎng)的單詞經(jīng)過(guò)之前的匹配破譯就是*o**e**ia*i*e，其中*號(hào)Step5：然后篩選出長(zhǎng)度為L(zhǎng)的長(zhǎng)單詞字典庫(kù)中所有符合*o**e**ia*i*Step6：再針對(duì)這幾十個(gè)備選單詞，進(jìn)行字母位置規(guī)律的匹配。我們利用ksddhfkrymrbh中dd字母位置及其他字母的重復(fù)性，篩選找到唯一匹配成功的單詞commercialize，也就成功破譯出相應(yīng)的配對(duì)kc,d 至此最長(zhǎng) 圖5：長(zhǎng)單詞流程（三）動(dòng)態(tài)逐詞文單詞中對(duì)應(yīng)位置的密鑰匹配字母對(duì)，直至已記錄的密鑰字母>=24時(shí)，停止對(duì)Step8:最后將剩余的2個(gè)字母相互交換位置或保持不變，得到完全密鑰，動(dòng)態(tài)逐 圖6：動(dòng)態(tài)逐詞流程模型的求解:表5：明文與密文高頻單、雙字母對(duì)照表明文中出現(xiàn)頻率最高密文中出現(xiàn)頻率最高ethdgj位的是thhe，而e和he中的e互相對(duì)應(yīng)相等，那么所對(duì)應(yīng)的密文也應(yīng)該是相同utohde。Step2:其次搜索密文中最長(zhǎng)的單詞（記長(zhǎng)度為L(zhǎng)）進(jìn)行長(zhǎng)單詞，將以例如：對(duì)單詞密文tdgwudqgwwdfwnorjjdf進(jìn)行已破譯高頻字母密鑰，替換變成*e**te****e*******e*。再提取該單詞與長(zhǎng)單詞詞庫(kù)中同長(zhǎng)度的英語(yǔ)單詞進(jìn)行比對(duì)，必須滿足較少且比對(duì)位置精確因而能直換出其他*號(hào)的部分。Step3：L1L215step2的破譯過(guò)程，abcd ef ghijklm nopqrstuvwxyz tog wu Step411個(gè)已破譯的字母代回到原來(lái)的密文，得到未完全破譯的單hZYe。遍歷文中所有未完全破譯的單詞，將每一個(gè)未完全破譯的單詞代EX：將滿足h**e形式的單詞放入英文字典中進(jìn)行比對(duì)，可以得到以下hugehidehopehavehivehireherehome假設(shè)單詞從左至右的字母位置的順序?yàn)?,2,3,4，則*2,3，通過(guò)匹6h**e形式單詞的明/密文轉(zhuǎn)換ZYZYZYZY從上表可以看出h**e符合這種規(guī)律的單詞可以有多種組合形式。在完成所表7：明文和密文個(gè)字母之間轉(zhuǎn)換Z1876Z543Z382Y3572Y496數(shù)可以基本判定密文Z對(duì)應(yīng)的明文i和密文Y對(duì)應(yīng)的明文v。依次類推我們遍歷的方式則是該字母的密鑰。進(jìn)而可以確定具體的單詞。4.1.3.1模型結(jié)論分析abcd ef ghijklm nopqrstuvwxyz nhid syglpboutvczkewaxqrjmWhenAllanBloomwroteTheClosingoftheAmericanMind,hewasprobablynotthinkingofthe"closedmind"undertheimageofacontraceptive.Stilllesswouldanyonebelikelytothinkofthe"openmind"thatway.8qgdtfooftnovvuqkvwdwgdhoveltyvswgdfudklhftulti,gdqfeckvnfnojtvwwgltbltyvswgd"hovediulti"atidkwgdlufydvsfhvtwkfhdcwlxd.ewlooodeeqvaoiftjvtdndolbdojwvwgltbvswgd"vcdtulti"wqfj.圖9：英文文章密文最后加密后的密文運(yùn)用我們模型進(jìn)行后得到whenallanbloomwrotetheclosingoftheamericanminj,hewasprobablunotthinkingofthe"closejminj"dnjertheimageofacontraceptive.stilllesswodljanuonebelikelutothinkofthe"openminj"thatwau.圖10：英文文章之后，密文中的字母（第一排）所對(duì)應(yīng)的后字母（第二排abcd ef ghijklm nopqrstuvwxyz nhid syglpboutvczkewaxqrjm下圖框出的55個(gè)字母由于出現(xiàn)頻率 cdefghijklmn qrstuvwxyz hidsyglpbout zkewaxqrjm cjefghixklmn qrstdvwyuz密文所得的明文字母表。其中26個(gè)字母已有21個(gè)字母被確定出來(lái)，未確定的都是低頻字母。僅占所有文章字母的2.1%。完全不會(huì)影響讀者的閱讀，因此這個(gè)模型所出來(lái)的文章準(zhǔn)確率較高，能夠較為精準(zhǔn)完全解出密文。模型二的分析與求解模型二的分析模型二的建立

圖7：模型二的問(wèn)題分析流程圖C C ,第i個(gè)字母 ,第i個(gè)字母不正確PQYPart3：通過(guò)破譯每萬(wàn)字母的所需時(shí)間作為衡量標(biāo)準(zhǔn)，以衡量算法文模型二的求解（一）算法破譯準(zhǔn)確 20個(gè)左右，密鑰字母的正確率約80%，全文平均字母正確率約為的閱讀。（見(jiàn)下表11）表11：密鑰字母匹配數(shù)及密問(wèn)字母正確率IssueIssueIssueIssueIssue密鑰字母匹配個(gè)密文字母正確IssueIssueIssueIssueIssue密鑰字母匹配個(gè)密文字母正確（二）時(shí)間復(fù)雜度分Step1:導(dǎo)入密文，對(duì)所有字母統(tǒng)一化(轉(zhuǎn)化為全小寫(xiě))，所消耗的時(shí)間為nStep2:掃描整篇密文計(jì)算每個(gè)字母出現(xiàn)頻率及字母兩兩組合出現(xiàn)的頻率所消耗的時(shí)間為n。Step3:確定出高頻字母后，對(duì)文中最長(zhǎng)單詞進(jìn)行替換并與字典進(jìn)行比對(duì)，所消耗時(shí)間為C1（常數(shù)）。Step4:再次對(duì)密文從頭開(kāi)始掃描，每掃入一個(gè)單詞代入英語(yǔ)詞典庫(kù)進(jìn)行對(duì)比，所消耗時(shí)間為C2n。綜上，則F(n)(C22)nC1，所以時(shí)間復(fù)雜度滿足O(n),其中C1C2是依賴12：10篇文章中程序運(yùn)行時(shí)間和密文字母數(shù)IssueIssueIssueIssueIssue程序運(yùn)行時(shí)間密文字母IssueIssueIssueIssueIssue程序運(yùn)行時(shí)間密文字母我們還探討了程序運(yùn)行時(shí)間和密文字母數(shù)的關(guān)系，通過(guò)畫(huà)圖，可 8：同一篇文章破譯時(shí)間隨字母數(shù)量的變化情35,000后，程序運(yùn)行時(shí)間相對(duì)穩(wěn)定，因?yàn)槿绻麑?duì)全文的每一個(gè)單詞進(jìn)行掃模型的優(yōu)點(diǎn)

五、模型的優(yōu)缺點(diǎn)與評(píng)價(jià)推廣試出來(lái)的頻率相當(dāng)穩(wěn)定。（單詞基數(shù)大概為2000萬(wàn)）率所得到的破譯具有較高可信度。我們算法的成功率為96.16%，因?yàn)檫@些字母都是極低頻的字母，所以不能完全所有字母，但是絕大多數(shù)未破譯字母完全可以通過(guò)人為干預(yù)識(shí)別本模型擁有最優(yōu)的時(shí)間復(fù)雜度O(n)，對(duì)于較長(zhǎng)的密文能在短時(shí)間（10s 模型的缺點(diǎn)模型的改進(jìn)[1]

六、參考文獻(xiàn)[2]，基于頻率分析的替代破譯方法及其程序?qū)崿F(xiàn)，福建電腦，第期，2006 [4]G.Navarro,M.Raffinot,FlexiblePatternMatchinginStrings(柔性字符七、附一．圖表

表12雙字母組合頻率最高前10[len,wit]=size(b);jieb2zeros(len,wit);%加密后的文章fori=1:lenwhile(b(i)>=65&&b(i)<=90)b(i)=b(i)-'A'+'a';begin %finalrendprim(1:26);%隨機(jī)生成加密所對(duì)字母表fori=1:lenif(b(i)>=97&&b(i)elsejieb2(i)=b(i);fidfopen('w_acad_20110mi.txt','w');%加密后的文章到出[len,wit]loadword15.mat;loadword16.mat;loadword17.mat;loadword18.mat;loadword19.mat;loadword20.mat;loadword21.mat;loadword23.mat;loadloadword_len2.mat;loadword_len3.mat;loadword_len4.mat;loadword_len5.mat;loadword_len6.mat;loadword_len7.mat;loadword_len8.mat;fori=1:lenwhile(b(i)>=65&&b(i)<=90)b(i)=b(i)-'A'+'a';level=przeros(1,26);%每個(gè)字母在所有中的出現(xiàn) fori=1:lenif((b(i)>=97&&b(i)<=122))pr(b(i)-'a'+1)= cum=cum+1;pripr/cum;%每個(gè)字母在所有中的頻sor_pri=front=rear=maxL=0;if((b(front)<97||b(front)>122)&&(b(front+1)>=97&&b(front+1)<=122))rear=front;if((b(front)>=97&&b(front)<=122)&&(b(front+1)>=97||if(maxL<front-rear)maxL=front-rear;front=frontfrontrearcount=zeros(1,6);%最長(zhǎng)長(zhǎng)度的單詞出現(xiàn)的次數(shù)max1=0; two_als=zeros(26,26); count3=0; forfront=1:len-1x=b(front);y=b(front+1)if((x<97||x>122)&&(y>=97&&y<=122))rear=front;if(x>='a'&&x<='z')&&(y>='a'&&if((x>=97&&x<=122)&&(y<97||y>122))max1=front-rear;ifmax1>maxL-5switchcasemaxL-count(1)=count(1)+1;forj=1:max1dL1(count(1),(j))=b(rear+count(2)=count(2)+1;forj=1:max1dL2(count(2),(j))=b(rear+count(3)=count(3)+1;forj=1:max1dL3(count(3),(j))=b(rear+count(4)=count(4)+1;forj=1:max1dL4(count(4),(j))=b(rear+casemaxL-count(5)=count(5)+1;forj=1:max1dL5(count(5),(j))=b(rear+count(6)=count(6)+1;forj=1:max1dL6(count(6),(j))=b(rear+

sor_two_als=sort(two_als);[m_two_als,n_two_alsfind(two_als>sor2_two_als(end-3),3m,n表示最高頻率的3個(gè)字母所在的位置 %forifn_al(i)==n_two_als(j)level(n_two_als(j))=level(m_two_als(j))=

%forifn_two_als(i)==m_two_als(j)&&level(n_two_als(j))==5;level(m_two_als(i))=20;

fork=6:-switchcasecasecasecasecasecasecasecasecasecaseswitchcasecasecasecasecasecaseflagzeros(1,maxL);%所有標(biāo)記比對(duì)的地方ifcount(k)forforx=Y1(i)-iflevel(x)flag(i)=1;

[count_word,count_wo] %count_wordforj=1:count_wordfori=1:maxLflag1=ififY(j,i)~=xflag1=0;

ifforifx=Y1(i)-

maxL=maxL-flag_level=zeros(1,26);%記錄翻譯完成字母的個(gè)數(shù),只要有替換出結(jié)果,就標(biāo)記forifflag_level(i)= level2=[]; count_level2=zeros(1,26);%記錄替換的次front=1;rear=maxL=count_word_len1=0; while(front<=len-1)if((b(front)<97||b(front)>122)&&(b(front+1)>=97&&b(front+1)<=122))rear=front;if((b(front)>=97&&b(front)<=122)&&(b(front+1)>=97||count_word_len1=front-ifcount_word_len1>=6&&count_word_len1<=8switchcount_word_len1casefori=1:2X(i)= X1(i)=X(i);casefori=1:3X(i)= X1(i)=X(i);casefori=1:4X(i)=

X1(i)=X(i);case5fori=1:5X(i)= X1(i)=X(i);casefori=1:6X(i)= X1(i)=X(i);c