古典密码学理论分析

古典密码学理论分析[摘要]密码学有悠久而迷人的历史。研究古典密码学的起源与发展，介绍主要的代表人物，对古典密码学中的典型算法进行分析。[关键词]密码加密破解古典密码理论算法中图分类号：B81文献标识码：A文章编号：1671－7597（2009）0320186－02一、引言“人类使用密码的历史几乎与使用文字的时间一样长”《破译者》。密码学(Cryptograph)，一词来源于古希腊语Kruptos(hidden)+graphein(towrite)，准确的现代术语是“密码编制学”简称“编密学”，与之相对的专门研究如何破解密码的学问称之为“密码分析学”。密码学则包括密码编制学和密码分析学这两个相互独立又相互依存的分支。密码学经历了从古典密码学到现代密码学的演变。许多古典密码虽然已经经受不住现代手段的攻击，但是它们对现代密码学的研究是功不可没的，其思想至今仍然被广泛使用[1]。二、古典密码学的主要代表人物1．费斯图。他的圆盘理论是古典密码学的主要代表之一，在粘土圆盘的表面刻上带有空格的字母，成为最初人类的加密方式，这种方式至今还无人能破戒。2．凯撒。凯撒密码是把字母用该字母的后面三个字母代替。但这种密码容易被破解。3．阿辛地。阿辛地对古典密码学的贡献是成功的破解了凯撒密码。4．莱昂?巴蒂斯塔。多表密码理论的创始人，发明了比替代密码更加先进的多表密码加密方法，是古典密码学发展的一个重大的进步。5．维吉尼亚。维吉尼亚是古典密码理论发展上的一个重要里程碑，他的理论又被称为多字母编码。6．亚瑟?谢尔比乌斯，理查德?里特。他们发明了“奇谜机”，把多表加密理论成功的用机械原理实现，为以后计算机加密开创了先河。这些人物是古典密码发展中的推动性人物，他们不但使古典密码理论不断的向前发展，更为以后密码学的发展奠定了基础，无疑贡献是巨大的。三、古典密码学的主要算法1．人类最早的文字历史可以追溯到公元前2000年公元前1650年的费斯图(Phaistos)圆盘，一种直径约为160mm的Cretan-Mnoan粘土圆盘，表面有明显字间空格的字母，至今还没有破解。加密作为保障数据安全的一种方式，埃及人是最先使用特别的象形文字作为信息编码的，随着时间推移，巴比伦、美索不达米亚和希腊文明都开始使用一些方法来保护他们的书面信息。古希腊墓碑的名文志、隐写术都是古老的加密方法，这种加密方法已体现了密码学的若干要素，但只能限制在一定范围内使用[2]。2．公元前5世纪，古希腊斯巴达出现原始的密码器，用一条带子缠绕在一根木棍上，沿木棍纵轴方向写好明文，解下来的带子上就只有杂乱无章的密文字母。解密者只需找到相同直径的木棍，再把带子缠上去，沿木棍纵轴方向即可读出有意义的明文。这是最早的换位密码术。3．人类第一次有史料记载的加密信息的使用是公元前58年到公元前51年，朱里叶斯?凯撒（公元前101公元前44年）征服了高卢，他的《高卢战记》里记载了因对通信官不信任，而与部下所用的密码凯撒密码。凯撒密码是把字母表中的每个字母用该字母后面第三个字母进行代替。例如，我们可以从明文得到密文（veni,vidi,vici,“我来，我见，我征服”是凯撒征服本都王法那西斯后向罗马元老院宣告的名言）[2]：明文：veni,vidi,vici密文：YHAL,YLGL,YLFL既然字母表是循环的，因此Z后面的字母是A。能够通过列出所有可能性定义如下所示的变换：明文：abcdefghijklmnopqrstuvwxyz密文：defghijkImnopqrstuvwxyzabc如果为每一个字母分配一个数值，并用字母P替代，每个密文字母用字母C替代则该算法能表示如下：C=E(p)=(p+3)mod26移位可以是任何量，因此通用的凯撒密码算法是：C=E(p)=(p+k)mod26其中k在1到25的范围取值。对应解密算法是：p=D(C)=(C-k)mod26但这样单一的字母替代法容易被攻破，九世纪阿拉伯人首先发现了破解简单“替代密码”的方法：因为字母替代法反映了原来字母表的频率数据，你只需要去计算每一个密码字所出现的频率，然后与英文字母在日常应用中出现的频率做比对。譬如频率最大的英文字母是E，那在密码信息中经常出现密码字很有可能就是E，在对相近频率的字母进行代人测算后，很容易就破解出真实信息。16世纪英国伊丽莎白女王时期，苏格兰玛丽女王被囚禁，在狱中仍通过密码书信与外面保持联系。企图勾结亲信贵族发动谋反，不料英格兰国务大臣掌握了那套密码术，一下把谋反者们全部逮捕，并把玛丽女王送上了断头台。玛丽女王用的编码法就是这样的方法：只是将每一个英文字母系统性地以不同的字母进行对应取代。为改进这种加密方法，先后出现了多种变种算法，比如：（1）多名码代替就是将明文字母表中的字符映射为密文字母表中的多个字符。多名码简单代替早在1401年就由DuchyMantua公司使用。在英文中，元音字母出现频率最高，降低对应密文字母出现频率的一种方法就是使用多名码，如e可能被密文5,13或25替代。（2）多音码代替就是将多个明文字符代替为一个密文字符。比如将字母“i”和“J”对应为“K”，“v”和“w”代替为“L”。最古老的这种多字母加密始见于1563年由波他的《密写评价》(Defurtioisliterarumnods)一书。（3）多表代替即由多个简单代替组成，也就是使用了两个或两个以上的代替表。比如使用有5个简单代替表的代替密码，明文的第一个字母用第一个代替表，第二个字母用第二个表，第三个字母用第三个表，以此类推，循环使用这五张代替表。多表代替密码由莱昂?巴蒂斯塔于1568年发明，著名的维吉尼亚密码、博福特密码和希尔密码均是多表代替密码。其中，16世纪法国外交官BlaisedeVigenere(1523-1596)维吉尼亚密码法(Vigenerecypher)的发明在密码史上是一个重要里程碑，它的原理是在26个字母矩阵中在约定某个关键词的前提下，对讯息字母进行编码，每个字母变成和关键词一样长度的矩阵中所对应的字母，因此这一编码又被称为多字母(poly-alphabetic)编码。这使得频率分析法对此束手无措，当时堪称无敌。直到几百年后1863年一位名叫Kasiski的普鲁士少校首次从关键词的长度着手将它破解。现代计算机模型的先驱巴贝奇(CharlesBabbage)通过仔细分析编码字母的结构也将其破获，不过Vigener法至今仍有一定的适用性并对人类历史的发展产生了重大影响[3]。4．1918年，德国发明家亚瑟?谢尔比乌斯(ArthurScherbius)和他的朋友理查德?里特(RichardRitter)创办了谢尔比乌斯和里特公司并发明了著名的Enigma（希腊文，意指“谜一般神秘难解之事”）又称“奇谜机”。实际上它是维吉尼亚密码的一种实现。它主要利用机械运动和简单电子线路：有一个键盘和若干转轮，每个转轮由绝缘的圆形胶板组成，胶板正反两面边缘线上有金属凸块，每个金属凸块上标有字母，字母的位置相互对齐。胶板正反两面的字母用金属连线接通，形成一个置换运算。不同的转轮固定在一个同心轴上，它们可以独立自由转动，每个转轮可选取一定的转动速度。例如，一个转轮可能被导线连通以完成用F代替A，用U代替B，用L代替C等等。为了防止密码分析，有的转轮密码机还在每个转轮上设定不同的位置号，使得转轮的位置、转轮的数量、转轮上的齿轮结合起来，增大机器的周期。一份德国报告称：“谜”型机能产生220亿种不同的密钥组合，假如一个人日夜不停地工作，每分钟测试二种密钥的话，需要约4.2万年才能将所有的密钥可能组合试完。希特勒完全相信了这种密码机的安全性，十年间，德国军队装备了大约三万台Enigma。然而，英国获知了“谜”型机的原理，启用了数理逻辑天才、现代计算机设计思想的创始人，年仅26岁的图灵(AlanMathisonTuring1912-1954)。1939年8月，在图灵领导下完成了一部针对“谜”型机的密码破译机，每秒钟可处理2000个字符，人们给它起了个绰号叫“炸弹(Bomb)”。半年后，它几乎可以破译截获德国的所有情报。后来又研制出一种每秒钟可处理5000个字符的“巨人(Colossus)”型密码破译机，1943年投入使用。至此，同盟国几乎掌握了希特勒德国的绝大多数军事秘密，加速了德军的失败。同一时期，美国人使用的是瑞典人哈格林设计的哈格林密码机（美国军方称为M-209），它是一种齿数可变的齿轮装置，有六个密钥轮，一个印字轮。太平洋战争中美军破译了日本海军的密码机，截获了日本舰队司令官山本五十六发给各指挥官的命令，在中途岛彻底击溃了日本海军，不久又击毙了山本五十六，形成了太平洋战争的决定性转折[4]。四、总结20世纪中叶以前，由于条件所限，密码技术的保密性基于加密算法的秘密，因此称之为古典密码体制或受限(restricted)的密码算法。尽管古典密码体制受到当时历史条件的限制，没有涉及非常高深或者复杂的理论，但在其漫长的发展演化过程中，已经充分表现出了现代密码学的两大基本思想“代替”和“换位”，而且还将数学的方法引入到密码分析和研究中。这为后来密码学成为系统的学科以及相关学科的发展奠定了坚实的基础。参考文献：[1]冯运波、杨义先，密码学的发展与演变[J].信息网络安全，2001年，07期.[2]RichardSpillman著，叶阮健、曹英、张长富译，经典密码学与现代密码学[M].北京：清华大学出版社，2005.[3]WadeTrappe,LawrenceC.Washington（美）著，邹红霞、许鹏文译，密码学概论[M].北京：人民邮电出版社，2004.[4]章照止，现代密码学基础[M].北京：北京邮电大学出版社，2004.作者简介：于红梅，女，汉族，山东省青岛市人，硕士，高级讲师，主要研究方向：信息安全、计算机软件开发。