《密码学12古典密码资料课件.ppt》由会员分享，可在线阅读，更多相关《密码学12古典密码资料课件.ppt（73页珍藏版）》请在三一办公上搜索。
1、第1章 密码学引论与古典密码,本章重点： 掌握常用的古典密码的加密解密。学时：4-6学时,2022/12/5,2,1.4 几种古典密码,隐写术置换密码（重点）代替密码（重点）单表代替密码多表代替密码,2022/12/5,3,一、 隐写术,隐写术：将秘密消息隐藏在公开消息中，并通过公开渠道来传送的方法。,两种隐藏明文信息的方法,隐写术密码编码学,2022/12/5,4,eg：诗情画意传“密语”,早妆未罢暗凝眉，迎户愁看紫燕飞，无力回天春已老，双栖画栋不如归。,2022/12/5,5,王先生： 来信收悉，你的盛情真是难以报答。我已在昨天抵达广州。秋雨连绵，每天需备伞一把方能上街，苦矣。大约本月中旬
2、我才能返回，届时再见。,eg：卡丹网格式密码,2022/12/5,6,隐写术特点,简单，掌握密钥后，破译简单。易被攻击。,2022/12/5,7,传统的信息隐藏技术古代信息隐藏的方法可以分为两种: 一种是将机密信息进行各种变换，使非授权者无法理解，这就是密码术; 另一种是将机密信息隐藏起来，使非授权者无法获取，如隐写术等。可以称它们为古代密码术和古代隐写术。 我们可以把它们的发展看成两条线: 一条是从古代密码术到现代密码学; 一条是从古代隐写术到信息隐藏、数字水印、隐通道和匿名通信。古代隐写术包括技术性的隐写术、语言学中的隐写术和用于版权保护的隐写术。,信息隐藏的发展历史,2022/12/5,
3、8,1. 技术性的隐写术技术性的隐写术由来已久。大约在公元前440年，隐写术就已经被应用了。据古希腊历史学家希罗多德记载，一位希腊贵族希斯泰乌斯为了安全地把机密信息传送给米利都的阿里斯塔格鲁斯，怂恿他起兵反叛波斯人，想出一个绝妙的主意:剃光送信奴隶的头，在头顶上写下密信，等他的头发重新长出来，就将他派往米利都送信。类似的方法在20世纪初期仍然被德国间谍所使用。,2022/12/5,9,实际上，隐写术自古以来就一直被人们广泛地使用。隐写术的经典手法实在太多，此处仅列举一些例子: (1) 使用不可见墨水给报纸上的某些字母作上标记来向间谍发送消息。(2) 在一个录音带的某些位置上加一些不易察觉的回声
4、。(3) 将消息写在木板上，然后用石灰水把它刷白。(4) 将信函隐藏在信使的鞋底里或妇女的耳饰中。(5) 由信鸽携带便条传送消息。,2022/12/5,10,(6) 通过改变字母笔画的高度或在掩蔽文体的字母上面或下面挖出非常小的小孔(或用无形的墨水印制作非常小的斑点)来隐藏正文。(7) 在纸上打印各种小像素点组成的块来对诸如日期、打印机进行标识，将用户标识符等信息进行编码。(8) 将秘密消息隐藏在大小不超过一个句号或小墨水点的空间里。(9) 将消息隐藏在微缩胶片中。,2022/12/5,11,(10) 把在显微镜下可见的图像隐藏在耳朵、鼻孔以及手指甲里; 或者先将间谍之间要传送的消息经过若干照
5、相缩影步骤后缩小到微粒状，然后粘在无关紧要的杂志等文字材料中的句号或逗号上。(11) 在印刷旅行支票时使用特殊紫外线荧光墨水。(12) 制作特殊的雕塑或绘画作品，使得从不同角度看会显示出不同的印像。(13) 利用掩蔽材料的预定位置上的某些误差和风格特性来隐藏消息。比如，利用字的标准体和斜体来进行编码，从而实现信息隐藏; 将版权信息和序列号隐藏在行间距和文档的其他格式特性之中; 通过对文档的各行提升或降低三百分之一英寸来表示0或1等。,2022/12/5,12,2. 语言学中的隐写术语言学中的隐写术也是被广泛使用的一种方法。最具代表性的是“藏头诗”，作者把表明真情实意的字句分别藏入诗句之中。如电
6、影唐伯虎点秋香中唐伯虎的藏头诗“我画蓝江水悠悠，爱晚亭上枫叶愁。秋月溶溶照佛寺，香烟袅袅绕经楼。”今天，这一“我爱秋香”的藏头诗句已成经典。又如绍兴才子徐文才在杭州西湖赏月时挥毫写下了一首七言绝句“平湖一色万顷秋，湖光渺渺水长流。秋月圆圆世间少，月好四时最宜秋。”,2022/12/5,13,每句的第一个字连起来正好是“平湖秋月”。我国还有一种很有趣的信息隐藏方法，即消息的发送者和接收者各有一张完全相同的带有许多小孔的掩蔽纸张，而这些小孔的位置是被随机选择并戳穿的。发送者将掩蔽纸张放在一张纸上，将秘密消息写在小孔位置上，移去掩蔽纸张，然后根据纸张上留下的字和空格编写一篇掩饰性的文章。接收者只要把
7、掩蔽纸张覆盖在该纸张上就可立即读出秘密消息。直到16世纪早期，意大利数学家Cardan重新发展了这种方法，该方法现在被称为卡登格子隐藏法。国外著名的例子是Giovanni Boccaccio(13131375年)创作的Amorosa visione，据说是世界上最长的藏头诗，他先创作了三首十四行诗，总共包含大约1500个字母，然后创作另外一首诗，使连续三行诗句的第一个字母恰好对应十四行诗的各字母。,2022/12/5,14,3. 用于版权保护的隐写术版权保护与侵权的斗争从古到今一直在延续着。 Lorrain(16001682年)是17世纪一个很有名的画家，当时出现了很多模仿和假冒他的画，他使用
8、了一个特殊的方法来保护画的版权。他自己创作了一本称为Liber Veritatis的素描集的书，它的页面是交替出现的，四页蓝色后紧接着四页白色，不断重复，大约包含195幅画。,2022/12/5,15,我国是最早发明印刷术的国家，而且许多西方国家也承认印刷术来自中国。书籍作为流通的商品且利润丰厚，在漫长的岁月中不进行版权保护是无法想像的，也是不符合事实的。从法令来看，北宋哲宗绍圣年间(1095年)已有“盗印法”，中国自宋代就确有版权保护的法令。从实物来看，现存宋代书籍中可以证实版权问题。如眉山程舍人宅刊本东都事略，其牌记有: “眉山程舍人宅刊行，已申上司，不许覆板。”这就相当于“版权所有，不准
9、翻印”。1709年英国国会制定的“圣安妮的法令”，承认作者是受保护的主体，这被认为是第一部“版权法”。,2022/12/5,16,数字信息隐藏技术的发展1992年，国际上正式提出信息隐藏的概念; 1996年，在英国剑桥大学牛顿研究所召开了第一届信息隐藏学术会议，标志着信息隐藏学的正式诞生。此后，国际信息隐藏学术会议在欧美各国相继召开，至今已举办九届之多。作为隐秘通信和知识产权保护等的主要手段，信息隐藏从正式提出到现在十多年的时间里引起了各国政府、大学和研究机构的重视，取得了巨大的发展。美国的麻省理工学院、普渡大学、英国的剑桥大学、NEC研究所、IBM研究所都进行了大量的研究。在国内，许多高等院
10、校和研究机构也对信息隐藏技术进行了深入的研究。从1999年开始，我国已召开了六届全国性的信息隐藏学术研讨会。,2022/12/5,17,国家863计划智能计算机专家组会同中国科学院自动化研究所模式识别国家重点实验室和北京邮电大学信息安全中心还召开了专门的“数字水印学术研讨会”。随着理论研究的进行，相关的应用技术和软件也不断推出。如美国Digimarc公司在1995年开发了水印制作技术，是当时世界上唯一一家拥有这一技术的公司，并在Photoshop 4.0和CoreDraw 7.0中进行了应用。日本电器公司、日立制作所、先锋、索尼和美国商用机器公司在1999年宣布联合开发统一标准的基于数字水印技
11、术的DVD影碟防盗版技术。DVD影碟在理论上可以无限制地复制高质量的画面和声音，因此迫切需要有效的防盗版技术。该技术的应用使消费者可以复制高质量的动态图像，但以赢利为目的的大批量非法复制则无法进行。2000年，德国在数字水印保护和防止伪造电子照片的技术方面取得了突破。以制作个人身份证为例，一般要经过扫描照片和签名、输入制证机、打印和塑封等过程。,2022/12/5,18,上述新技术是在打印证件前，在照片上附加一个暗藏的数字水印。具体做法是在照片上对某些不为人注意的部分进行改动，处理后的照片用肉眼看与原来几乎一样，只有用专用的扫描器才能发现水印，从而可以迅速、无误地确定证件的真伪。该系统既可在照
12、片上加上牢固的水印，也可以经改动使水印消失，使任何伪造企图都无法得逞。由欧盟委员会资助的几个国际研究项目也正致力于实用的水印技术研究，欧盟期望能使其成员国在数字作品电子交易方面达成协议，其中的数字水印系统可以提供对复制品的探测追踪。在数字作品转让之前，作品创作者可以嵌入创作标志水印; 作品转让后，媒体发行者对存储在服务器中的作品加入发行者标志;在出售作品拷贝时，还要加入销售标志。,2022/12/5,19,经过多年的努力，信息隐藏技术的研究已经取得了许多成果。从技术上来看，隐藏有机密信息的载体不但能经受人的感觉检测和仪器设备的检测，而且还能抵抗各种人为的蓄意攻击。但总的来说，信息隐藏技术尚未发
13、展到可大规模使用的阶段，仍有不少理论和技术性的问题需要解决。到目前为止，信息隐藏技术还没有形成自身的理论体系。比如，如何计算一个数字媒体或文件所能隐藏的最大安全信息量等。尽管信息隐藏技术在理论研究、技术开发和实用性方面尚不成熟，但它的特殊作用，特别是在数字版权保护方面的独特作用，可以说是任何其他技术无法取代的，信息隐藏技术必将在未来的信息安全体系中独树一帜。,2022/12/5,20,2022/12/5,21,二、 置换密码,又称换位密码，指根据一定的规则重新排列明文。 特点：保持明文的所有字符不变，只是打乱了位置和次序。 分类：列置换密码周期置换密码,2022/12/5,22,1、列置换密码
14、：将明文按照固定宽度n按行写出，而后按照密钥的规则按列换位。,eg1：已知明文是Beijing 2008 Olympic Games，密钥k = 6，e = (14)(56)。,加密过程是：step1:将明文m按照宽度k分行。M= B e i j i n g 2 0 0 8 O l y m p i c G a m e s,step2:将明文m按照e换行，得密文,C= j e i B n i 0 2 0 g O 8 p y m l c i e a m G s,2022/12/5,23,eg2：已知明文是this text，密钥k = 4，e= (2 4 1 3)。,加密过程：将明文按照4个字符一
15、组分组，不足的部分填充*得： this text第2个字符移位到位置4，第4个字符移到位置1，第1个字符移到位置3，第3个字符移到位置2；则密文：“sith txte”,(2)周期置换密码：将明文m按照固定长度分组，对每组的字串按照某个置换重新排位从而得到密文。,2022/12/5,24,练习,ex：已知采用周期置换密码加密，密钥k=6,e=(15623)。如果明文是statek，那么密文是什么？,aKttSe,如何解密？,2022/12/5,25,三、 单表代换密码,就是明文中的字母由其他字母、数字或符号所取代的一种方法。算法：建立一个代换表，加密时将明文字符通过代换表代换为相应的密钥文字。
16、具体的代替表称之为密钥。,2022/12/5,26,eg：设代换的对应关系如下：a b c d e f g h i j k l m n o p q r s t u v w x y zi d m e f z o a p h x b s c q r l t u y j v n w g k从代换的对应关系可知su，ef，yg因此以代换为密钥对security加密得到密文ufmjtpyg,2022/12/5,27,三、单表代换密码,字母与十进制数字的对应关系：,2022/12/5,28,其中：m是明文，c是密文。3是加密所用的密钥，加密时，每个字母向后移3位，解密时，每个字母向前移3位（均为循环移位）
17、。,1、凯撒密码,2022/12/5,29,eg1：通过恺撒（Caesar）密码对明文加密： please,则密文为：sohdvh,2022/12/5,30,eg2：设明文为：security，试用Caesar密码对其进行加密，然后再进行解密。加密过程如字母s对应的数字为18，将18使用加密算法进行加密E3(18) 18+ 3 (mod26) 21数字21对应的字母为v，所以security的密文为vhfxulwb(2) 解密过程D3(21) 21- 3 (mod26) 18,2022/12/5,31,2、移位变换,特点：加密方法简单。 穷举即可破译。,2022/12/5,32,3、基于密钥的
18、单表代换密码,具体算法： 选取一个字符串作为密钥，除去密钥中重复的字母，剩余字母按照顺序写在此字母之后生成字母表。特点：破译难度较高。 密钥更改灵活。,2022/12/5,33,eg：已知密钥为magicnet，对明文help加密。,step1:生成字母表abcd efgh ijkl mnop qrst uvwx yz magi cnet bdfh jklo pqrs uvwx yz,step2：按照字母表替换明文字符。 明文：help 密文：tcho,如何解密？,2022/12/5,34,4、仿射加密扩展的移位变换,加密：,解密：,密钥为025之间的数字对(a,b)。 要求：a与26的最大公
19、约数必须为1，即gcd(a,26)=1。 a-1是a的逆元，即a-1*a(mod26)=1。,2022/12/5,35,eg：仿射加密。设(a,b)=(7,21)，对明文security加密。对vlxijh解密。,s=18, 7*18+21(mod26)=17, sr,e=4, 7*4+21(mod26)=23, ex,c=2, 7*2+21(mod26)=9, cj,y=24, 7*24+21(mod26)=7, yh,security对应的密文：rxjfkzyh,2022/12/5,36,eg：仿射加密。设(a,b)=(7,21)，对明文security加密。对vlxijh解密。,7-1m
20、od26=?,7*15mod26=1,7-1mod26=15,v=21, 15(21-21)mod26=0, va,l=11, 15(11-21)mod26=6, lg,h=7, 15(7-21)mod26=24, hy,vlxijh对应的明文：agency,2022/12/5,37,0-25内所有与26互素元素的乘法逆元,2022/12/5,38,练习,ex:仿射加密。设(a,b)=(3,21)，对明文book加密解密。,单表代换分析,密钥空间增加(26!)，穷举搜索这么多的密钥很困难但这并不表示该密码不容易破解破解这类密码的突破点是由于语言本身的特点是充满冗余的，每个字母使用的频率不相等
21、而单表代换密码没有改变字母相对出现的频率明文字母的统计特性在密文中能够反映出来, 当通过统计密文字母的出现频率，可以确定明文字母和密文字母之间的对应关系,英文字母统计特性,英文单字母的相对频率表,单字母按照出现频率的大小可以分为下面5类： (1) e：出现的频率大约为0.127 (2) t, a, o, I, n, s, h, r：出现的频率大 约在0.06-0.09之间 (3) d, l：出现的频率约为0.04 (4) c, u, m, w, f, g, y, p, b：出现的频率大约在0.015-0.028之间 (5) v, k, j, x, q, z：出现的频率小于0.01,英文字母统计
22、特性,双字母和三字母组合都有现成的统计数据，常见的双字母组合和三字母组合统计表能够帮助破解密文。频率最高的30个双字母（按照频率从大到小排列）： th he in er an re ed on es st en at to nt ha nd ou ea ng as or ti is et it ar te se hi of 频率最高的20个3字母（按照频率从大到小排列）： the ing and her ere ent tha nth was eth for dth hat she ion int his sth ers ver,英文字母统计特性,破解举例,例1 已知下面的密文式由单表代换生产
23、的： UZQSOVUOHXMOPVGPOZPEVSGZWSZOPFPESXUDBMETSXAIZVUEPHZHMDZSHZOWSFPAPPDTSVPQUZWYMXUZUHSXEPYEPOPDZSZUFPOMBZWPFUPZHMDJUDTMOHMQ，试破译该密文首先统计密文中字母出现的频率，然后与英文字母出现频率比较。密文中字母的相对频率统计如下：,破解举例,将统计结果与频率表进行比较，可以猜测密文中P与Z可能是e和t，密文中的S,U,O,M出现频率比较高，可能与明文字母中出现频率相对较高的a, o, I, n, s, h, r这些字母对应密文中出现频率很低的几个字母C,K,L,N,R,I,J可
24、能与明文字母中出现频率较低的字母v, k, j, x, q, z对应。就这样边试边改，最后得到明文如下：it was disclosed yesterday that several informal but direct contacts have been made with political representatives of the viet cong in moscow,破解举例,在尝试过程中，如果同时使用双字母和三字母的统计规律，那么更容易破译密文。如上面的密文中出现最多的双字母是ZW，它可能对应明文双字母出现频率较大的th，那么ZWP就可能是the，这样就更容易试出明文。,破
25、解举例,2022/12/5,47,以一些表依次对明文消息的字母序列进行代换的加密方法。明文中的同一个字母，由于出现的位置不同用不同的字母代替。,四、多表代换密码,2022/12/5,48,1、Playfair密码,算法设计： 将明文字母按照两个字母一组分组，然后将这些组按照字母矩阵替换为密文字母组合。基于一个55字母矩阵该矩阵使用密钥来构造。,2022/12/5,49,1、Playfair密码,矩阵构造方法：从左至右，从上至下依次填入关键词的字母，若字母重复则略过，然后再以字母表顺序依次填入其他的字母。字母I和J被算作一个字母 。表中的第1列看做是第5列的右边1列，第1行看做第5行的下1行。,
26、2022/12/5,50,加密算法：P1、P2同行：对应的C1和C2分别是紧靠P1、P2右端的字母。其中第一列被看作是最后一列的右方。P1、P2同列：对应的C1和C2分别是紧靠P1、P2下方的字母。其中第一行看作是最后一行的下方。P1、P2不同行、不同列：C1和C2是由P1和P2确定的矩形的其它两角的字母，并且C1和P1、C2和P2同行。P1P2：则插入一个字母于重复字母之间，并用前述方法处理.若明文字母数为奇数时：则在明文的末端添加某个事先约定的字母作为填充。,2022/12/5,51,eg1：已知密钥是：PLAYFAIRISADIGRAMCIPHER。如果明文是playfair ciphe
27、r，为其加密。,明文两个一组： pl ay fa ir ci ph er对应密文为: LA YF PY RS MR AM CD,2022/12/5,52,ex：用Playfair算法加密明文“playfair cipher”,密钥是fivestars。,练习,2022/12/5,53,2022/12/5,54,2022/12/5,55,Playfair密码的特点,有676种双字母组合，因此识别各种双字母组合要困难得多。各个字母组的频率要比单字母呈现出大得多的范围，使得频率分析困难得多。Playfair密码仍然使许多明文语言的结构保存完好，使得密码分析者能够利用。,2022/12/5,56,2、
28、维吉尼亚密码,算法设计：设N是某固定的正整数，已知密钥有N个字符，K=(k1,k2,kN)。将明文M按照N个字符一组分段，分为L段，M=(m1,m2,mL)。求密文C，其中Cij=kj+mij,i=L,j=N。,2022/12/5,57,eg：已知密钥字是CIPHER，n6。假定明文串是：this system。,3、相应的密文串将是:vpxzwpubtt,加密过程：1、 密钥字转换为数字为：2 8 15 7 4 172、 将明文串转化为数字串，按6个一组分段，然后加上密钥字模26 。,2022/12/5,58,解密过程：1、 密钥字转换为数字。2、 将密文串转化为数字串，按密钥字个数分组，然
29、后减去密钥字模26 。,A B C D E F G H I J K L M N O P Q R S T U V W X Y Z,A BCDEFGHIJ,A B C D E F G H I J K L M N O P Q R S T U V W X Y ZB C D E F G H I J K L M N O P Q R S T U V W X Y Z AC D E F G H I J K L M N O P Q R S T U V W X Y Z A BD E F G H I J K L M N O P Q R S T U V W X Y Z A B CE F G H I J K L M N
30、O P Q R S T U V W X Y Z A B C DF G H I J K L M N O P Q R S T U V W X Y Z A B C D EG H I J K L M N O P Q R S T U V W X Y Z A B C D E FH I J K L M N O P Q R S T U V W X Y Z A B C D E F GI J K L M N O P Q R S T U V W X Y Z A B C D E F G HJ K L M N O P Q R S T U V W X Y Z A B C D E F G H I ,Vigenere替换表,
31、密钥: deceptive,明文: we are discovered save yourself,密文:,明文,密钥,练习： Vigenere密码,使用Vigenere密码加密单词explanation，密钥为leg。,密钥：legleglegle明文：explanation密文：PBVWETLXOZR,Vigenere密码的安全性,维吉尼亚密码是将每个明文字母映射为几个密文字母 如果密钥字的长度是m，明文中的一个字母能够映射成这m个可能的字母中的一个 密文中字母出现的频率被隐蔽了，它的安全性明显比单表代换密码提高了 维吉尼亚密码的密钥空间比较大，对于长度是m的密钥字，密钥空间为26m 当m
32、=5，密钥空间所含密钥的数量大于1.1x107,2022/12/5,62,3、Hill密码,明文：密文：其中，,2022/12/5,63,矩阵形式：,加密：,解密：,2022/12/5,64,示例,eg1：逆矩阵mod26的含义。,2022/12/5,65,eg2：已知明文为hill ，密钥矩阵如下所示：,（23,8）,明文M=hill,对应数值：7，8，11，11。,C=(7,8) 11 8 mod 26 3 7,（24,9）,C=(11,11) 11 8 mod 26 3 7,密文为：xiyj,2022/12/5,66,解密：,（7,8）,m=(23,8) 7 18 23 11,（11,1
33、1）,m=(24,9) 7 18 23 11,2022/12/5,67,Hill密码的特点：,Hill密码完全隐藏了单字母的频率字母和数字的对应可以改成其它方案，使得更不容易攻击成功能比较好地抵抗频率法的分析，对抗仅有密文的攻击强度较高,2022/12/5,68,练习,ex2：设明文是cybert，使用的密钥如下，为其加密解密。,ex1：已知密钥字是text，n4。对明文this system加密解密。,2022/12/5,69,编程,已知是维吉尼亚加密，设密钥是：but，明文是sorcery，为其加密解密。,总结与思考, 现代密码设计思想,换位密码优缺点总结: 位置变但形态不变代替密码优缺点
34、总结: 形态变但位置不变,将代替密码和移位密码轮番使用,必然可以发挥各自的长处,克服对方的缺点，必然可以设计出安全的密码体制。 这就是现代密码的设计思想，它来源于古典密码！, 一次一密,一次一密是一种理论上不可攻破的密码体制，它使用与信息同样长度的0和1组成的随机序列，一旦密钥使用过一次就丢弃它并且不再使用，加密的过程就是信息和密钥一位一位的模2加，这个过程通常叫做异或，解密过程使用同样的密钥，只需简单地将明文与密钥相加。,总结与思考, 一次一密,举例：明文 0 0 1 0 1 0 0 1密钥 1 0 1 0 1 1 0 0密文 1 0 0 0 0 1 0 1,注意：现代信息系统中的数据存储与交换，绝大部分都是这种01比特流。,总结与思考, 一次一密,为什么说一次一密是不可攻破的密码体制呢？因为从密文中得不到任何关于明文的信息，除非知道密钥。,一次一密的缺点是它需要非常长的密钥，这需要花费相当大的费用去产生和传输，而且一旦一个密钥使用之后，就不能再使用。,总结与思考,
