论文部分内容阅读
摘 要：密码破译是密码学研究领域的一个重要分支，也是目前信息安全研究的一个热点方向。本文主要研究单字母替换式的密文破译问题，建立了针对长篇文字的基于频率分析的破译模型。
在判断单词的存在性时，本文将来自COCA的近3.6亿的词汇库构建成一个字典树，不但节省了运行内存，也提高了计算效率。根据英文字母出现频率的差异性，采用频率分析法。在对密文的单字、每个单词的字头字尾等进行分析后，与实际的字母出现频率进行比较，可以确定如E、A、T、H等高频字母的密文，再采用穷举法遍历所有密钥。
关键词：字典树;频率分析;随机优化;穷举
1 问题重述
历史上有很多密码的编制方法，有单表替代密码、仿射密码、秘钥短语密码等。其中较为简单的是替换式密码，也就是将文中出现的字符一对一的替换成其他的符号。对于拼音文字而言，最简单的形式是单字母的替换加密，也就是以每个字母为一个单位，将每个字母替换成另外的字母或者其他的符号。这个映射叫做密码表，拥有密码表的人能够轻易将密文破译成明文。
现在假设明文是由英文字母写成的，并且密码表是针对26个字母的，每个单词之间的空格、标点符号都保留。针对已经获得的一些由单字母加密方法得到的密文。要求我们团队建立合理的数学模型，设计一个算法来自动化的破译密文。
2 模型基本假设与符号说明
2.1基本假设
（1）假设明文与密文是由英文字母写成的，并且密码表仅针对26个英文字母;
（2）假设每个单词之间的空格、标点符号都保留;
（3）假设COCA的语言资料库数据量够大，足以用于判别一个单词的正误。
3 问题分析
对于长篇密文的破解，频率分析法是比较有效的。根据26个不同字母的使用频率的差异，我们对大量英文文献进行统计，得到各字母出现频率的大小，并且可以进一步可以将它们分成极高频率字母组、次高频率字母组、中等频率字母组、低频率字母组和甚低频率字母组。接着，对所要破译的密文中每个字母出现的频率进行统计，得到密文中各字母所对应的明文字母的组类。
在英文单词中，每个单词的字头和字尾也有不同的出现频率，所以我们接着对密文进行相应的频数进行统计，得到更为范围更小的密文中各字母所对应的明文字母集合。
此时，因此利用穷举法尝试遍历可能的密码进行解密。
4 模型建立与求解
4.1基于频率分析的破译模型
4.1.1模型建立
我们从COCA[1]中获取了一长篇文章，随机进行编码后得到密文，并对密文进行破解。根据英文字母出现频率的显著差异性，采用了频率分析法，统计出密文中每个字母的频数，对照实际英文字母出现频率表，可以确定a，e等高频字母对应的密文。
类似的，英文单词的字头和字尾也有不同的出现频率，接着对密文进行字头、字尾分析。此时，不能确定的密文字母其所对应的明文字母集合中元素个数与一开始相比也明显减少，因此利用穷举法尝试遍历进行解密。
4.1.2模型求解
根据对大量英文文献的统计，我们可以发现，各字母出现的相对频率非常稳定。然后可以进一步根据各字母的频率的大小将英文字母进行如下分组。
极高频率字母组：E;次高频率字母组：T、A、O、I、N、S、R、H;中等频率字母组：L、D;低频率字母组：C、U、M、G、P、F、W、Y、B;甚低频率字母组：V、K、J、X、Z、Q。
根据密文中字母的出现频率高低，我们将他们进行归类得到：
密文中的字母R对应于明文中的字母E;次高频率字母B、H、C、O、M、A、Y、V很可能对应于集合{T、A、O、I、N、S、R、H};中等频率字母E、T很可能对应于集合{L、D};低频率字母组P、S、L、F、D、I、W、K、N很可能对应于集合{C、U、M、G、P、F、W、Y、B};甚低频率字母J、U、Q、X、G、Z很可能对应集合{V、K、J、X、Z、Q}。
4.2字头、字尾分析
通过查找资料，可以找出字头最频繁的十个字母为：T、A、S、I、W、O、H、B、C、M;字尾最频繁的十个字母为：E、S、T、D、N、R、Y、O、G、A。对密文中字头、字尾[3]出现的频数进行统计。
根据所得数据，密文的次高频率字母B、H、C、O、M、A、Y、V中，B、C、M、H字头和字尾都很频繁出现的字母，它们很可能对应于集合{T、A、O、S}中的明文字母;Y、A出现在字尾，而在字头则出现较少，则它可能是明文字母中N或R;O、V出现在字头，而在字尾则出现较少，则它可能是明文字母中I或H。
4.3穷举
上述分析结束后，我们可以确定了9个密文字母对应的明文，最终各组类中不能确定的17个字母如下表：
表1 最终各组类中不能确定的字母
<E：＼123456＼速读·下旬201510＼Image＼表六.png>
下面我们采用穷举法进行解密。
相比较直接穷举法需要进行的26的阶乘的计算量，本算法的计算量为：，约为，远远小于。密文破解速率是可以接受的。求解得到的明文与对应的密文如下：
表2密钥对应表
<E：＼123456＼速读·下旬201510＼Image＼表七.png>
5 模型优缺点
5.1模型优点
本文的模型准备中构建的字典树，避免了在海量词汇库中逐一搜索以判断一个单词正误的复杂性，大大降低了算法的计算量。
5.2模型缺点
破译算法没有从密文本身的性质出发考虑，而密文的结构对破译效率有比较显著的影响，鉴于密文种类的多样性不作考虑，此处有所欠缺。
参考文献：
[1]Full-textcorpusdata，http：//corpus.byu.edu/full-text/formats.asp，2015年4月18日
[2]吴干华.基于频率分析的代替密码破译方法及其程序实现[J]，福建电脑，09：125-127，2006
[3]立早.初等密码分析学——数学方法（续一）第二章一般的单表代替[J]，通信保密，02：65-74，1980
在判断单词的存在性时，本文将来自COCA的近3.6亿的词汇库构建成一个字典树，不但节省了运行内存，也提高了计算效率。根据英文字母出现频率的差异性，采用频率分析法。在对密文的单字、每个单词的字头字尾等进行分析后，与实际的字母出现频率进行比较，可以确定如E、A、T、H等高频字母的密文，再采用穷举法遍历所有密钥。
关键词：字典树;频率分析;随机优化;穷举
1 问题重述
历史上有很多密码的编制方法，有单表替代密码、仿射密码、秘钥短语密码等。其中较为简单的是替换式密码，也就是将文中出现的字符一对一的替换成其他的符号。对于拼音文字而言，最简单的形式是单字母的替换加密，也就是以每个字母为一个单位，将每个字母替换成另外的字母或者其他的符号。这个映射叫做密码表，拥有密码表的人能够轻易将密文破译成明文。
现在假设明文是由英文字母写成的，并且密码表是针对26个字母的，每个单词之间的空格、标点符号都保留。针对已经获得的一些由单字母加密方法得到的密文。要求我们团队建立合理的数学模型，设计一个算法来自动化的破译密文。
2 模型基本假设与符号说明
2.1基本假设
（1）假设明文与密文是由英文字母写成的，并且密码表仅针对26个英文字母;
（2）假设每个单词之间的空格、标点符号都保留;
（3）假设COCA的语言资料库数据量够大，足以用于判别一个单词的正误。
3 问题分析
对于长篇密文的破解，频率分析法是比较有效的。根据26个不同字母的使用频率的差异，我们对大量英文文献进行统计，得到各字母出现频率的大小，并且可以进一步可以将它们分成极高频率字母组、次高频率字母组、中等频率字母组、低频率字母组和甚低频率字母组。接着，对所要破译的密文中每个字母出现的频率进行统计，得到密文中各字母所对应的明文字母的组类。
在英文单词中，每个单词的字头和字尾也有不同的出现频率，所以我们接着对密文进行相应的频数进行统计，得到更为范围更小的密文中各字母所对应的明文字母集合。
此时，因此利用穷举法尝试遍历可能的密码进行解密。
4 模型建立与求解
4.1基于频率分析的破译模型
4.1.1模型建立
我们从COCA[1]中获取了一长篇文章，随机进行编码后得到密文，并对密文进行破解。根据英文字母出现频率的显著差异性，采用了频率分析法，统计出密文中每个字母的频数，对照实际英文字母出现频率表，可以确定a，e等高频字母对应的密文。
类似的，英文单词的字头和字尾也有不同的出现频率，接着对密文进行字头、字尾分析。此时，不能确定的密文字母其所对应的明文字母集合中元素个数与一开始相比也明显减少，因此利用穷举法尝试遍历进行解密。
4.1.2模型求解
根据对大量英文文献的统计，我们可以发现，各字母出现的相对频率非常稳定。然后可以进一步根据各字母的频率的大小将英文字母进行如下分组。
极高频率字母组：E;次高频率字母组：T、A、O、I、N、S、R、H;中等频率字母组：L、D;低频率字母组：C、U、M、G、P、F、W、Y、B;甚低频率字母组：V、K、J、X、Z、Q。
根据密文中字母的出现频率高低，我们将他们进行归类得到：
密文中的字母R对应于明文中的字母E;次高频率字母B、H、C、O、M、A、Y、V很可能对应于集合{T、A、O、I、N、S、R、H};中等频率字母E、T很可能对应于集合{L、D};低频率字母组P、S、L、F、D、I、W、K、N很可能对应于集合{C、U、M、G、P、F、W、Y、B};甚低频率字母J、U、Q、X、G、Z很可能对应集合{V、K、J、X、Z、Q}。
4.2字头、字尾分析
通过查找资料，可以找出字头最频繁的十个字母为：T、A、S、I、W、O、H、B、C、M;字尾最频繁的十个字母为：E、S、T、D、N、R、Y、O、G、A。对密文中字头、字尾[3]出现的频数进行统计。
根据所得数据，密文的次高频率字母B、H、C、O、M、A、Y、V中，B、C、M、H字头和字尾都很频繁出现的字母，它们很可能对应于集合{T、A、O、S}中的明文字母;Y、A出现在字尾，而在字头则出现较少，则它可能是明文字母中N或R;O、V出现在字头，而在字尾则出现较少，则它可能是明文字母中I或H。
4.3穷举
上述分析结束后，我们可以确定了9个密文字母对应的明文，最终各组类中不能确定的17个字母如下表：
表1 最终各组类中不能确定的字母
<E：＼123456＼速读·下旬201510＼Image＼表六.png>
下面我们采用穷举法进行解密。
相比较直接穷举法需要进行的26的阶乘的计算量，本算法的计算量为：，约为，远远小于。密文破解速率是可以接受的。求解得到的明文与对应的密文如下：
表2密钥对应表
<E：＼123456＼速读·下旬201510＼Image＼表七.png>
5 模型优缺点
5.1模型优点
本文的模型准备中构建的字典树，避免了在海量词汇库中逐一搜索以判断一个单词正误的复杂性，大大降低了算法的计算量。
5.2模型缺点
破译算法没有从密文本身的性质出发考虑，而密文的结构对破译效率有比较显著的影响，鉴于密文种类的多样性不作考虑，此处有所欠缺。
参考文献：
[1]Full-textcorpusdata，http：//corpus.byu.edu/full-text/formats.asp，2015年4月18日
[2]吴干华.基于频率分析的代替密码破译方法及其程序实现[J]，福建电脑，09：125-127，2006
[3]立早.初等密码分析学——数学方法（续一）第二章一般的单表代替[J]，通信保密，02：65-74，1980