2015第八届挑战赛二阶段优秀集

第八届“认证杯”数学中国数学建模网络赛编号专用页参赛队伍的参赛队（请各个参赛队提前填写好482竞赛统一编号（由竞赛送至评委团前编号竞赛评阅编号（由竞赛评委团评阅前进行编号2015年第八届“认证杯”数学中国数学建模网络赛第一阶段 带有噪声干扰信道传输替换式破关键 多目标优化模型频率分析算法模拟仿真检验函 要针对带有噪声干扰信道传输替换式破译问题，首先对噪声干扰概率进行项，通过编程仿真得出密文。37次，得到密文与明文的字符对应法则如下。并且把结果从定性明文abcdefghijklmtIoudebwvyknh明文nopqrstuvwxyz暗文xspvjzgcImqfr123456789（由组委会填写参赛队号:（由组委会填写所选题目:BThisstudyissubstitutioncipherdecipheringproblemswithnoisechanneltransmission,themaincharactertoestablishmultipleobjectivefunctionsaccordingtofrequency,usingfrequencyysisalgorithmforsolvingthecorrespondencebetweenciphertextandintextcharacterForchanneltransmissionsubstitutioncipherdecipheringproblemswithnoise,thefirstofthenoiseprobabilityprocessing,characterduringtransmission,disruptionfrequencyincreases,theprobabilitythatthefrequencyofcharactersappearinceoftheciphertextcharactertransmissioninterference,andtheprobabilityofinterferenceequallytothethreeitems,theciphertextobtainedbysimulationSecondobjectivefunction,throughbetweentheciphertextandthedifferencebetweentheminimumfrequencyofnormalEnglishcharactersintextwordandthewordlibrarymaterialthanthedifferencebetweentheumwordsimilarity,andoneminustheintextandthenormalEnglish26charactersandtheminimumfrequencythreeastheobjectivefunction;thecharacterfrequency,theciphertexttransmissionprobabilityandotherfactorstoestablishfourconstraints,theestablishmentofmulti-objectiveoptimizationEnglishcharactersinnormalusefrequency,basedonasinglecharacter,twocharactersright,asinglecharacterasahighfrequencystatisticsinitialsdesignafrequencyysisalgorithm.TheninaccordancewiththerulesoftheEnglishwordformationandgrrstatisticsstart,manualintervention37timestoobtainCharactercorrespondingciphertextandintextrulefollowsabcdefghijklmtIoudebwvyknhnopqrstuvwxyzxspvjzgcImqfrTheencryptedtext10timestoget10differentciphertext,usingthemodelanddesignofalgorithms,willbeconvertedintointextciphertext,usingtestfunction,obtainingdifferentciphertextcorrespondingintextbesttestvalues.123456789Finallytestfunction,BetestedfunctionvalueisFitness0.865312,testingthevalidityofthefinalintext。:Multi-objectiveoptimizationmodel Besttestfunction Frequencyysis-Algorithm问题重述问题背这个映射方法被称为表，拿到表的人就能够将密文破译成明文。单字母替换加密是在古代就使用过的一种加密方法，但由于其容易被，所以在现代单字母替换加密的破译方法有频率分析等。这种和破译方法在小说中也组合进行分析，才能完整地破译。问题相关信1p1p2p3需要解决的问问题假设与符号说明问题假假设三：在简单的替换中，明文中的每一个字母都被另一个字母替换,E都会被替换成X.一个X的密文消息会向破译者暗示X替换E。符号说SF表示第 个字符在密文中出现的频DF表示第 个字符在正常英文中出现的频表示第 个字符在明文中出现的频表示两个单词对比有nM SkM(M1,M2 Mi) 且(MiZ261ji)S(S1,S2 Si) 且(CjZ261ji)kk1 k26 且(kiZ26问题分析针对第二阶段问题，首先是替换式在传输过程中受到传输信道的干扰，即26AZ组成的字符串，通过wiki找到单个字母和双字符组在英文中出现的频率，e是最常见的单字母，th是最为常见的双字母组，而the则为最为常见的三字母组，先将密文中出现应频率进行求差，并对A~Z26个字符频率差进行求和并取绝对值，最后用1减去求数据处理单字母频率统字母频率。其是可古典的频率分析在英语中最常见的字母是eWiki百科单字母数据【1，通过数据排列得到单字母频率统计[6]（图1）如下：。eta inshr cumwfgypbv xq首字母频率tashtashwiobmf ldpnegryu kqx低外，其他字母为首字母的频率都相对较稳定徘徊在8%-1%之间。双字母频率统计者两个音节，或者两个词构成的双字母组。这种组被用在最成功的一种语音识别的语言模型中。Wiki百科双字母数据【2，下面列出了英语里最常见的双字母组（3）如下：………图3：双字母频率统计排序[7] inanndonhast te se 分布图划分为高频率、中频率、低频率三份，其中高频率出现的双字母为：“TH”对字符频率的拟合

单字母出现频率的拟合曲

双字母出现频率的拟合曲出现出现频

出现出现频00 字母表中字母的顺

第X个双字母1模型的密文的生成

问题的求解应的概率为p1,p2p3,p4p41p1p2p3，在通信过程中，每个 p1=p2=p3=jp j jpj

p4 约束条件建立约束条件一约束条件二

0SFiDFi文各字符重复频率之和应该等于100%，SFi约束条件三因为第二阶段的密文没有间隔与标点符号，每一篇密文中的字符都应该是0i SFiA~约束条件四之和应该等于1。且正常传输的概率应该大于其余三种受到干扰概率之和。4pj 综上所述，得到约束条件为：

pjj

SFi4 pjj0SFiDFi0i

SFiA~目标函数建立

pj

minMatch|SFiDFi式中：SFi表示第i个字符在密文中出现的频率，DFi表示第i个字符在maxSimilarity

n式中，Sn表示两个单词对比有n个字符相同，Dm表示单词的求差，并对A~Z26个字符频率差进行求和并取绝对值，最后用1减去求和的值。

Fitness1|DF(i)CF(i)式中：DF(i)表示第i个字符在密文中在正常英文出现的频率，CF(i)表示第i个字符在明文中出现的频率。最佳检验函数值越大，就表示密文转成明文的maxSimilarityDDm

minMatch|SFiDFi n Fitness1|DF(i)CF(i)综合以上对约束条件和目标函数的建立，得到多目标优化模型

SFi4 pjj0SFiDFi0i

SFiA~ pj

maxSimilarityDDm

minMatch|SFiDFi n

Fitness1|DF(i)CF(i)破译替换式的频率分析算Step2：在Step1中得到密文最大频率字母对应的关系，然后根据双字母对找出密模型的求解本文采用频率分析法，利用编程统计密文中字符出现的频率，并将越高。计算求解得到明文与暗文替换的字符如下（图abcdefghijklmtIoudebwvyknhnopqrstuvwxyzxspvjzgcImqfr结果分结果的定性分析单字母出现频率的拟合曲线样本样本原稿密文出现频率出现频率0 字母表中字母的顺序双字母出现频率的拟合曲线样本样本原稿密文出现出现频率0

X个双字母对结果定量分析模拟仿真分析通过字符在信道传输过程中，受到干扰的概率的约束，运用编程模拟仿真文本加密的方式，生成不同的密文。然后运用中建立的模型和设计的123456789检值 567模型的评价优缺模型的改进及推广模型的确性。有分析显示字母频率就像词频，不同作者或写作的作品中往往各不相同。当为x射线（x-rays）撰文时，文章中就会有大量的字母X。而撰写用x射线治疗卡塔尔（Qatar）的斑马（zebras）X、QZ就模型的参考文献【1】何晓琴，一种新式Vigenere的破译和研究[J].计算机科学第40卷,12期【2】巩延文，马尔可夫链蒙特卡洛方法在学中的应用[J],哈尔滨工业大学,2013年6月【3】王彩霞，分析中几种方法的研究及其设计与实现[J],西学,2004【4】，学中布尔函数性质研究[J],交通大学,2012年9【5】龚洁中，遗传算法在分析中的应用研究[J],交通大学,2007附%%导入样本txt文件，用作词fori=1:26%%fori=1:length(Y1)%%%%%forj=1:10%%% plot(z1,X1,'k*',z1,y1,'r-');%%%%symstfor%%%%%%%forj=1:10%%% plot(z,X,'k*',z,y1,'r-');%%%%symstforifC(j)>=65&&C(j)<=90%%globalM;globalN;fork=1:length(C)fprintf('原文是：\ns\nA)fprintf('密文是：\ns\nD)%%txt文件%%模拟密文传输过程中出现的干扰 %