古典密码学介绍

中 国 地 质 大 学 古典密码学介绍

课程名称：趣味密码学 教师姓名：刘 勇 姓 名： 肖 国 栋 班 级 ： 052098j-18 学 号： 20091002670 专 业： 土 木 工 程 所在院系：工 程 学 院 日 期： 2011 年 12 月

目 录

前 言 ………………………………………………………………1 第一章 古典密码学概念和意义…………………………………..3 第二章 古典密码学发展历史……………………………………..5 第三章 古典密码学内容及分类…………………………………..8

第一节 代换密码 ………………………………………………………………..9 第二节 置换密码.................................................................................................11

第四章 几种典型的古典密码……………………………………..13

第一节 滚筒密码和掩格密 ……………………………………………………...13 第二节 棋盘密码…………………………………………………………………14 第三节 移位代换密码……………………………………………………………15 第四节 Playfair密码……………………………………………………………..15 第五节 圆盘密码………………………………………………………………….18 第六节 维吉尼亚密码…………………………………………………………….19

参考文献…………………………………………………………….20

前 言

随着科学技术的迅猛发展，人们对信息安全和保密的重要性认识不断提高，在信息安全中起着举足轻重作用的密码学也就成为信息安全中不可或缺的重要部分。密码学的研究前景十分广阔，这个总是秘而不宣的重要角色，在未来发展中将起到不可估量的作用。1985年Koblitz和Miller提出将椭圆曲线用于公钥密码体制，他们第一次用椭圆曲线成功地实现了已有的一些公钥密码算法包括Differ-Hellman算法。现在椭圆曲线密码体制不仅是一个重要的理论研究领域，而且已经作为民用信息安全技术走向产业化。在信息技术领域的保密通信、数字签名、秘密共享、消息认证、密钥管理，人工智能密码学，量子密码学，安全电子商务系统，电子现金系统，电子选举系统，电子招投标系统，电子彩票系统等，密码学都在发挥着不为人知的作用。

而古典密码学则是在密码学发展中占据着举足重轻的地位。

本文将针对古典密码学进行简单的介绍，而让人们更加向往密码学这个神奇的世界。本文的目标是帮助人们认

识和理解古典密码学。

第一章主要介绍古典密码学的概念：什么是古典密码学及其有什么特点？除此之外，对研究古典密码学的意义也进行了一定的介绍；第二章则是讲述古典密码学在密码学发展进程中的历史；第三章对古典密码学内容作了阐述，并对古典密码的分类作了分类：代换密码和置换密码；第四章则是对几种典型的古典密码进行介绍，并举出一些例子，以加深人们对古典密码的认识。

本论文对我自己是一种初步尝试，涉及的专业性的知识可能认识不够，加上水平所限，不可避免存在疏漏和不足，忘老师与予批评指正。

第一章

古典密码学概念和意义

古典密码概念：

在计算机出现以前，密码学的算法主要是通过字符之间代替或

易位实现的，我们称这些密码体制为古典密码。古典密码学主要是指20世纪40年代之前的密码编码和密码分析技术，特别是1935年到1940年。这期间，由于军事、数学、通讯等相关技术的发展，特别是两次世界大战中对军事信息保密传递和破获敌方信息的需求，密码学得到了空前的发展，并广泛的用于军事情报部门的决策其中包括：易位密码、代替密码（单表代替密码、多表代替密码等）。 这些密码算法大都十分简单，现在已经很少在实际应用中使用了。由于密码学是涉及数学、通讯、计算机等相关学科的知识，就我们现有的知识水平而言，只能初步研究古典密码学的基本原理和方法。但是对古典密码学的研究，对于理解、构造和分析现代实用的密码都是很有帮助的。

古典密码学意义：

由于古典密码学是密码学的分支，所以它具有密码通用的功能

和作用。

密码是通信双方按约定的法则进行信息特殊变换的一种重要保密手段。依照这些法则，变明文为密文，称为加密变换；变密文为明文，称为脱密变换。密码在早期仅对文字或数码进行加、脱密变换，随着通信技术的发展，对语音、图像、数据等都可实施加、脱密变换。

密码学是在编码与破译的斗争实践中逐步发展起来的，并随着先进科学技术的应用，已成为一门综合性的尖端技术科学。它与语言学、数学、电子学、声学、信息论、计算机科学等有着广泛而密切的联系。它的现实研究成果，特别是各国政府现用的密码编制及破译手段都具有高度的机密性。

例如在希特勒一上台时，德国就试验并使用了一种命名为“谜”的密码机，“谜”型机能产生220亿种不同的密钥组合，假如一个人日夜不停地工作，每分钟测试一种密钥的话，需要约4.2万年才能将所有的密钥可能组合试完，希特勒完全相信了这种密码机的安全性。然而，英国获知了“谜”型机的密码原理，完成了一部针对“谜”型机的绰号叫“炸弹”的密码破译机，每秒钟可处理2000个字符，它几乎可以破译截获德国的所有情报。后来又研制出一种每

秒钟可处理5000个字符的“巨人”型密码破译机并投入使用，至此同盟国几乎掌握了德国纳粹的绝大多数军事秘密和机密，而德国军方却对此一无所知；太平洋战争中，美军成功破译了日本海军的密码机，读懂了日本舰队司令官山本五十六发给各指挥官的命令，在中途岛彻底击溃了日本海军，击毙了山本五十六，导致了太平洋战争的决定性转折。

因此，我们可以说，密码学为战争的胜利立了大功。在当今密码学不仅用于国家军事安全上，人们已经将重点更多的集中在实际应用，在你的生活就有很多密码，例如为了防止别人查阅你文件，你可以将你的文件加密；为了防止窃取你钱物，你在银行账户上设置密码，等等。随着科技的发展和信息保密的需求，密码学的应用将融入了你的日常生活。

第二章

古典密码学的发展历史

密码学的发展历程大致经历了三个阶段：古代加密方法、古典密码和近代密码。

1.古代加密方法（手工阶段）

源于应用的无穷需求总是推动技术发明和进步的直接动力。存于石刻或史书中的记载表明，许多古代文明，包括埃及人、希伯来人、亚述人都在实践中逐步发明了密码系统。从某种意义上说，战争是科学技术进步的催化剂。人类自从有了战争，就面临着通信安全的需求，密码技术源远流长。

古代加密方法大约起源于公元前440年出现在古希腊战争中的隐写术。当时为了安全传送军事情报，奴隶主剃光奴隶的头发，将情报写在奴隶的光头上，待头发长长后将奴隶送到另一个部落，再次剃光头发，原有的信息复现出来，从而实现这两个部落之间的秘密通信。

公元前400年，斯巴达人就发明了“塞塔式密码”，即把长条纸螺旋形地斜绕在一个多棱棒上，将文字沿棒的水平方向从左到右书写，写一个字旋转一下，写完一行再另起一行从左到右写，直到写完。解下来后，纸条上的文字消息杂乱无章、无法理解，这就是密文,但将它绕在另一个同等尺寸的棒子上后，就能看到原始的消息。这是最早的密码技术。

我国古代也早有以藏头诗、藏尾诗、漏格诗及绘画等形式，将要表达的真正意思或“密语”隐藏在诗文或画卷中特定位置的记载，一般人只注意诗或画的表面意境，而不会去注意或很难发现隐藏其

中的“话外之音”。比如：我画蓝江水悠悠，爱晚亭枫叶愁。秋月溶溶照佛寺，香烟袅袅绕轻楼

2.古典密码（机械阶段）

古典密码的加密方法一般是文字置换，使用手工或机械变换的方式实现。古典密码系统已经初步体现出近代密码系统的雏形，它比古代加密方法复杂，其变化较小。古典密码的代表密码体制主要有：单表代替密码、多表代替密码及转轮密码。

3.近代密码（计算机阶段）

密码形成一门新的学科是在20世纪70年代，这是受计算机科学蓬勃发展刺激和推动的结果。快速电子计算机和现代数学方法一方面为加密技术提供了新的概念和工具，另一方面也给破译者提供了有力武器。计算机和电子学时代的到来给密码设计者带来了前所未有的自由，他们可以轻易地摆脱原先用铅笔和纸进行手工设计时易犯的错误，也不用再面对用电子机械方式实现的密码机的高额费用。总之，利用电子计算机可以设计出更为复杂的密码系统。

尽管古典密码体制受到当时历史条件的限制，没有涉及到非常高深或者复杂的理论，但在其慢长的发展演化过程中，已经充分表现出了现代密码学的两大基本思想-代替和换位，而且还将数学的方

法引入到密码分析和研究中。这为后来密码学成为系统的学科以及相关学科的发展奠定了坚实的基础，如计算机科学、复杂性理论等等。

可见古典密码学在密码学发展过程中扮演了不可磨灭的角色。

第三章

古典密码学内容及分类

密码学内容：

密码学(Cryptogra phy现代准确的术语为“密码编制学”，简称“编密学”，

与之相对的专门研究如何破解密码的学问称之为“密码分析学”。密码学是主要研究通信安全和保密的学科，他包括两个分支：密码编码学和密码分析学。密码编码学主要研究对信息进行变换，以保护信息在传递过程中不被敌方窃取、解读和利用的方法，而密码分析学则于密码编码学相反，它主要研究如何分析和破译密码。这两者之间既相互对立又相互促进。密码的基本思想是对机密信息

进行伪装。一个密码系统完成如下伪装：加密者对需要进行伪装机密信息（明文）进行伪装进行变换（加密变换），得到另外一种看起来似乎与原有信息不相关的表示（密文），如果合法者（接收者）获得了伪装后的信息，那么他可以通过事先约定的密钥，从得到的信息中分析得到原有的机密信息（解密变换），而如果不合法的用户（密码分析者）试图从这种伪装后信息中分析得到原有的机密信息，那么，要么这种分析过程根本是不可能的，要么代价过于巨大，以至于无法进行。 古典密码学分类：

古典密码有着悠久的历史，从古代一直到计算机出现以前，古典密码学主要有两大基本方法：

①代替密码：就是将明文的字符替换为密文中的另一种的字符，接收者只要对密文做反向替换就可以恢复出明文。

②置换密码(又称易位密码)：明文的字母保持相同，但顺序被打乱了。

第一节 代换密码

代换密码（代替密码）就是明文中每一个字符被替换成密文中的另外一个字符，代替后的各字母保持原来位置。对密文进行逆替换就可恢复出明文。有四种类型的代替密码：

（1）单表代替密码：就是明文的一个字符用相应的一个密文字符代替。加密过程中是从明文字母表到密文字母表的一一映射。

（2）同音代替密码：它与简单代替密码系统相似，唯一的不同是单个字符明文可以映射成密文的几个字符之一，例如A可能对应于5、13、25或56，“B”可能对应于7、19、31或42，所以，同音代替的密文并不唯一。

（3）多字母组代替密码：字符块被成组加密，例如“ABA”可能对应于“RTQ”，ABB可能对应于“SLL”等。

（4）多表代替密码：由多个简单的代替密码构成，例如，可能有5个被使用的不同的简单代替密码，单独的一个字符用来改变明文的每个字符的位置。

多字母代替密码是字母成组加密，在第一次世界大战中英国人就采用这种密码。字母成对加密。把Huffman编码用作密码，这是一种不安全的多字母代替密码。

多表代替密码。维吉尼亚密码是多表代替密码的例子。

多表代替密码有多个单字母密钥，每一个密钥被用来加密一个明文字母。第一个密钥加密明文的第一个字母，第二个密钥加密明文的第二个字母等等。在所有的密钥用完后，密钥又再循环使用，若有20个单个字母密钥，那么每隔20个字母的明文都被同一密钥加密，这叫做密码的周期。在经典密码学中，密码周期越长越难破译，使用计算机就能够轻易破译具有很长周期的代替密码。

凯撒密码就是单表代替密码，它的每一个明文字符都由其右边第3个（模26）字符代替（A由D代替，B由E代替,W由Z代替,X由A代替，Y由B代替，Z由C代替）。

单表代替密码是很容易破译的，因为它没有把明文的不同字母的出现频率掩盖起来。可以使用统计攻击。

第二节 置换密码

置换密码，又称换位密码 ：明文的字母保持相同，但顺序被打乱了。

置换只不过是一个简单的换位，每个置换都可以用一个置换矩阵Ek来表示。每个置换都有一个与之对应的逆置换Dk。置换密码的特点是仅有一个发送方和接受方知道的加密置换（用于加密）及对应的逆置换（用于解密）。它是对明文L长字母组中的字母位置进行重新排列，而每个字母本身并不改变。

第四章

几种典型的古典密码

本章将对前面所叙述的内容进行举例说明。通过例子对古典密码学有更好的认识。

第一节 滚桶密码和掩格密码

滚桶密码

在古代为了确保他们的通信的机密，先是有意识的使用一些

简单的方法对信息来加密。如公元六年前的古希腊人通过使用一根叫scytale的棍子，将信息进行加密。送信人先将一张羊皮条绕棍子螺旋形卷起来（如图），然后把要写的信息按某种顺序写在上面，接着打开羊皮条卷，通过其他渠道将信送给收信人。如果不知道棍子的宽度（这里作为密匙）就是不容易解密里面的内容的，但是收信人可以根据事先和写信人的约定，用同样的scytale的棍子将书信解密。

掩格密码

16世纪米兰的物理学和数学家Cardano发明的掩格密码，可以事先设计好方格的开孔，将所要传递的信息和一些其他无关的符号

组合成无效的信息，使截获者难以分析出有效信息。

第二节 棋盘密码

世界上最早的一种密码产生于公元前两世纪。是由一位希腊人提出的，人们称之为

棋盘密码，原因为该密码将26个字母放在5×5的方格里，i,j放在一个格子里，具体情 况如下表所示

1 2 3 4 5 1 a b c d e 2 f g h i,j k 3 l m n o p 4 q r s t u 5 v w x y z

这样，每个字母就对应了由两个数构成的字符αβ，α是该字母所在行的标号，β是列

标号。如c对应13，s对应43等。如果接收到密文为

43 15 13 45 42 15 32 15 43 43 11 22 15

则对应的明文即为secure message。

第三节 移位代换密码

移位代换密码的典型代表就是凯撒密码。 凯撒（Caesar）密码

据记载在罗马帝国时期，凯撒大帝曾经设计过一种简单的移位

密码，用于战时通信。这种加密方法就是将明文的字母按照字母顺序，往后依次递推相同的字母，就可以得到加密的密文，而解密的过程正好和加密的过程相反。

例如：明文 battle on Sunday 密文 wvoogz gi Npiyvt (将字母依次后移5位)

再例如如果我们令26个字母分别对应于整数01～26 则凯撒加密方法实际上是进行了一次数学取模为26的同余运算，即 其中m是明文对应的数据，c是与明文对应的密文数据，k是加密用的参数，也叫密钥。

比如：battle on Sunday对应数据序列为：020120201205 1514 192114040125

若取密钥k为5时，得密文序列为： 070625251710 2019 240019090604

第四节 ｐｌａｙｆａｉｒ密码

Playfair密码（英文：Playfair cipher 或 Playfair

square）是一种替换密码，1854年由查尔斯·惠斯通（Charles Wheatstone）的英国人发明。经莱昂·普莱费尔提倡在英国军地和政府使用。

它有一些不太明显的特征：密文的字母数一定是偶数；任意两个同组的字母都不会相同，如果出现这种字符必是乱码和虚码。

它使用方便而且可以让频度分析法变成瞎子，在1854到1855年的克里米亚战争和1899年的布尔战争中有广泛应用。但在1915年的一战中被破译了。

它依据一个5*5的正方形组成的密码表来编写，密码表里排列有25个字母。如果一种语言字母超过25个，可以去掉使用频率最少的一个。如，法语一般去掉w或k，德语则是把i和j合起来当成一个字母看待。英语中z使用最少，可以去掉它。

在这个5*5的密码表中，共有5行5列字母。第一列（或第一行）是密钥,其余按照字母顺序。密钥是一个单词或词组，若有重复字母，可将后面重复的字母去掉。当然也要把使用频率最少的字母去掉。如：密钥是Live

and learn,去掉后则为liveandr。如果密钥过长可占用第二列或行。如密钥crazy dog，可编制成： C R A Y D O G B E F H I J K L M N P Q S T U V W X 然后将明文每两个字母组成一对。如果成对后有两个相同字母紧挨或最后一个字母是单个的，就插入一个字母X。如，communist，应成为co,mx,mu,ni,st。 对明文加密规则如下： 1．若p1 p2在同一行，对应密文c1 c2分别是紧靠p1 p2 右端的字母。其中第一列被看做是最后一列的右方。如，按照前表，ct对应oc 2．若p1 p2在同一列，对应密文c1 c2分别是紧靠p1 p2 下方的字母。其中第一行被看做是最后一行的下方。 3．若p1 p2不在同一行，不在同一列，则c1 c2是由p1 p2确定的矩形的其他两角的字母（至于横向替换还是纵向替换要事先约好，或自行尝试）。如，按照前表，wh对应tk或kt。 如，依照上表，明文where there is life,there is hope. 可先整理为：wh er et he re is li fe th er ei sh op ex

然后密文为：kt yg wo ok gy nl hj of cm yg kg lm mb wf

将密文变成大写，然后几个字母一组排列。

如5个一组就是KTYGW OOKGY NLHJO FCMYG KGLMM BWF

第五节 圆盘密码

由于凯撒密码加密的方法很容易被截获者通过对密钥赋值（1～25）的方法破解，人们有进一步将其改善，只要将字母按照不同的顺序进行移动就可以提高破解的难度，增加信息的保密程度。如15世纪佛罗伦萨人Alberti发明圆盘密码就是这种典型的利用单表置换的方法加密的方法。如图在两个同心圆盘上，内盘按不同（杂乱）的顺序填好字母或数字，而外盘按照一定顺序填好字母或数字，转动圆盘就可以找到字母的置换方法，很方便的进行信息的加密与解密。凯撒密码与圆盘密码本质都是一样的，都属于单表置换，即一个明文字母对应的密文字母是确定的，截获者可以分析对字母出现的频率，对密码体制进行有效的攻击。

第六节 维吉尼亚密码

维吉尼亚（Vigenere）密码为了提高密码的破译的难度，人们有发明一种多表置换的密码，即一个明文字母可以表示为多个密文字母，多表密码加密算法结果将使得对单表置换用的简单频率分析方法失效，其中维吉尼亚密码就是一种典型的加密方法。维吉尼亚密码是使用一个词组（语句）作为密钥，词组中每一个字母都作为移位替换密码密钥确定一个替换表，维吉尼亚密码循环的使用每一个替换表完成明文字母到密文字母的变换，最后所得到的密文字母序列即为加密得到的密文，具体过程如下： 设密钥 ，明文 ，加密变换 其中

例如，M＝data security，k＝best。可以先将M分解为长为4的序列data secu rity

每一节利用密钥k＝best加密得密文c=Ek(M)=EELT TIUN SMLR。

当密钥k取的词组很长时，截获者就很难将密文破解。

参考文献

１. [美]Ｒｉｃｈａｒｄ Ｓｐｉｌｌｍａｎ，经典密码学与现代密码学，清华大学出版社,２００５ ２．宋震，密码学，中国水利水电出版社，２００２ ３.[以]戈德里克（Goldreich,O.），密码学基础，温巧燕 杨义先译, 人民邮电出版社，２００３ ４. ,[美]Wade Trappe Lawre,密码学概论（中文版），人民邮电出版社,２００４