第1章_古典密码体制2

1、12古代传递消息的方法v1 烽火、狼烟v2 驿站v3 信鸽、信猴、漂流瓶v4马拉松3 烽火台 在中国古代，为了传递军事情报，人们曾设立过烽火台，利用火与烟传递信息。烽火台白天烧狼粪，夜间点柴草。传说烧狼粪时有很大的浓烟直冲蓝天，在白天比火光更易被人发现，因此烽火有时又被称为狼烟。当发现敌情时，燃起烽火，台台相传，一直传到军营。在2700多年前，中国周朝时的烽火告警系统就已经很完备了。 4马拉松v马拉松长跑项目，就是为了纪念一位2000多年前为传送捷报而牺牲的英雄设立的。公元前490年，希腊军队在马拉松平原击退波斯王大流士一世军队的入侵。传令兵菲迪皮茨一口气从马拉松镇跑到首都雅典报告喜讯，当他跑

2、完42.195千米的路程，赶到雅典广场说完捷报之后，就精疲力竭，倒地而死。为了纪念这位战士的英雄事迹，1896年，在世界第一届奥运会上，他跑过的距离被作为一个长跑比赛项目列入运动会。 5PhaistosPhaistos圆盘，一种直径约为圆盘，一种直径约为160mm160mm的的Cretan-MnoanCretan-Mnoan粘土圆盘，始于公元前粘土圆盘，始于公元前1717世纪。表面有明显字间空世纪。表面有明显字间空格的字母，至今还没有破解。格的字母，至今还没有破解。第1阶段古典密码62020世纪早期密码机世纪早期密码机7保密通信的功罪v100年前，1894年的中日甲午海战，中国惨败，其本质是由

3、于清政府的腐败，但其中一个重要的具体原因，是日方在甲午战争前就破译了清政府使用的密电码。日方破译的电报多达一百余则，对清政府的决策、海军的行踪等了如指掌，因而日方不仅在海战中取得了胜利，还迫使清政府签订“马关条约”，割让辽东半岛、台湾及澎湖列岛，赔偿军费白银2亿两。8保密通信的功罪v1917年1月，正当第一次世界大战进入第三个年头时，英国海军破译机关截收到了德国外长齐默尔曼签发的一份密报，经过一个多月的辛勤劳作，终于在2月下旬完全破开了那份密报。密报称，德国将在欧洲进行无限制的潜艇战，意思是说，中立国家的船队也在其打击目标之列，同时指出，若美国不再保持中立，就要求墨西哥与德国结盟，对美宣战。英

4、国外交部在权衡了种种利弊后，到2月22日将此密报交给了美国政府，德国政府的阴谋激怒了开战以来一直保持中立并且在三个月前还声明继续保持中立的美国人，五个星期后美国对德宣战，出兵西线，既避免了在美国本土燃起战火，又加速了协约国的胜利。9保密通信的功罪v1941年12月，日本取得了突袭珍珠港、摧毁美国太平洋舰队主力的重大胜利，为了完全控制太平洋，并设法诱出在珍珠港的美国舰队残部予以彻底消灭，日本制定了于1942年6月突然攻击夏威夷前哨中途岛的计划。10保密通信的功罪v当时日本海军使用的是日本最高级的密码体制紫密，它的第二版本JN25b自1940年12月1日启用后应在1942年4月1日内第三版本JN2

5、5c替换。但由于舰船分散在广阔的海域不停地转移，给分发新的版本增添许多困难，因此替换工作延期到5月1日，后因同样的原因再延期个月，到6月1日启用新版本。这就使盟国破译人员有充分的时间更透彻地破解JY25b。5月27日，山本的作战命令已基本上被破译，美国太平洋舰队司令尼米兹海军上将发布作战计划，将3艘航空母舰部署在敌舰不可能侦察到的海域，战斗打响时也以突然攻击的方式打击日军的突击舰队。6月4日，日军4艘巨型航空母舰在一日之内相继被炸沉从此日本海军由进攻转为防御，最终走向失败。11保密通信的功罪v1943年春天，山本五十六为了控制不断恶化的残局，亲自前住所罗门群岛基地巡视，以鼓舞士气。在视察前五天

6、，1943年4月13日，日军第八舰队司令将山本行将视察的行程、时间表，用JN25体制加密后播发给有关基地，以作好迎接的准备，尽管该体制的所用版本在4月1日刚换过，但美国破译人员根据过去的经验，迅速地破译了这份密报，美军决定在空中打掉山本的座机，使日军失去一位战略家，沉重地打击日军士气。经过精心组织，周密安排，终于使山本五十六在飞往视察地途中，被美军飞机击落，葬身于丛林深处。12密码学起源密码学起源v大约在大约在40004000年以前，在古埃及的尼罗河畔，一位擅年以前，在古埃及的尼罗河畔，一位擅长书写者在贵族的基碑上书写铭文时有意用加以变长书写者在贵族的基碑上书写铭文时有意用加以变形的象形文字而

7、不是普通的象形文字来写铭文，从形的象形文字而不是普通的象形文字来写铭文，从而揭开了有文字记载的密码史。这篇颇具神秘感的而揭开了有文字记载的密码史。这篇颇具神秘感的碑文，已具备了密码的基本特征：把一种符号碑文，已具备了密码的基本特征：把一种符号( (明明文文) )用另一种符号用另一种符号( (密文密文) )代替代替13古典密码加密方法v代替密码；v置换密码；v代替密码和置换密码的结合。14代替密码v代替密码（substitution cipher）：明文中的每个字符被替换成密文中的另一个字符。v对密文逆替换就恢复出明文。简单代替，即单字母密码，如Caesar密码； 多码代替密码（每个明文字母可以

8、密文中的多个字母来代替，而每个密文字母也可以表示多个明文字母）； 多字母代替密码（字符块被成组加密，例如“ABA”可能对应于“RTQ”，ABB可能对应于“SLL” ）；多表代替密码，如Vigenre密码。15置换密码v置换密码（置换密码（permutation cipher）：又称换）：又称换位密码（位密码（transposition cipher） ，并没有，并没有改变明文字母，只改变了这些字母的出现顺改变明文字母，只改变了这些字母的出现顺序。序。16古典密码学古典密码学17古典密码学分类（流密码）（流密码）（分组密码）（分组密码）古典密码学古典密码学置换密码置换密码代替密码代替密码多字母代

9、替多字母代替单字母代替单字母代替单表代替单表代替多表代替多表代替18v公元前公元前5 5世纪，古斯巴达人使用了一种叫做世纪，古斯巴达人使用了一种叫做“天天书书”的器械，这是人类历史上最早使用的密码的器械，这是人类历史上最早使用的密码器械。器械。“天书天书”是一根用草纸条、皮条或羊皮是一根用草纸条、皮条或羊皮纸条紧紧缠绕的木棍。密信自上而下写在羊皮纸条紧紧缠绕的木棍。密信自上而下写在羊皮纸条上。然后把羊皮纸条解开送出。把羊皮纸纸条上。然后把羊皮纸条解开送出。把羊皮纸条重新缠在一根直径和原木棍相同的木棍上，条重新缠在一根直径和原木棍相同的木棍上，这样字就一圈圈跳出来。这样字就一圈圈跳出来。 密码学

10、起源密码学起源19v一种早期的 希腊变换密码v一张纸条环绕在一个圆柱上 v消息沿着圆柱横写v纸条上的字母看起来是一些随机字母v并不十分安全，密钥是纸条和圆柱的宽度密码学起源密码学起源20v公元前1世纪古罗马凯撒大帝时代曾使用过一种“替代式密码”，在这种密码中，每个字母都由其后的第三个字母（按字母顺序）所代替。这种替代式密码直到第二次大战时还被日本海军使用。v公元前4世纪前后，希腊著名作家艾奈阿斯在著作城市防卫论中就曾提到一种被称为“艾奈阿斯绳结”的密码。它的作法是从绳子的一端开始，每隔一段距离打一个绳结，而绳结之间距离不等，不同的距离表达不同的字母。21v六韬龙韬阴符武王问太公曰：引兵深入诸侯

11、之地，三军猝有缓急，或利或害。吾将以近通远，从中应外，以给三军之用。为之奈何？太公曰：主与将，有阴符。凡八等：有大胜克敌之符，长一尺；破军杀将之符，长九寸；降城得邑之符，长八寸；却敌报远之符，长七寸；誓众坚守之符，长六寸；请粮益兵之符，长五寸；败军亡将之符，长四寸；失利亡士之符，长三寸。诸奉使行符，稽留者，若符事泄，闻者告者，皆诛之。八符者，主将秘闻，所以阴通言语，不泄中外相知之术。敌虽圣智，莫之通识。武王曰：善哉。22v六韬龙韬阴书武王问太公曰：引兵深入诸侯之地，主将欲合兵，行无穷之变，图不测之利。其事繁多，符不能明；相去辽远，言语不通。为之奈何？太公曰：诸有阴事大虑，当用书，不用符。主以书

12、遗将，将以书问主。书皆一合而再离，三发而一知。再离者，分书为三部；三发而一知者，言三人，人操一分，相参而不知情也。此谓阴书。敌虽圣智，莫之能识。武王曰：善哉。23v 在古代还出现过一种被称为“叠痕法”的密码，使用时先把信纸折叠几下（上下及左右），然后铺平信纸，将传递的信息按顺序一个个分开，写在折痕的交叉点上，每一个交叉点写一个字。然后再在空白位置上填上公开的普通信文，普通信文与秘密信文的文字通顺地连贯在一起。为了防止被敌人察觉，使用这种密码需要在编公开信文上下些功夫。如果在秘密信文上再用些暗语式密码，那么敌人就更难看出破绽了。v宋曾公亮、丁度等编撰武经总要“字验”记载，北宋前期，在作战中曾用一

13、首五言律诗的40个汉字，分别代表40种情况或要求，这种方式已具有了密码本体制的特点。24v 暗号。简单地说，暗号就是通过用物件的状态或人的行为来传达事先约定的信息如窗台上的花瓶、手中拿着的报纸、口中昨着的曲子，可分别代表“现在安全”、“我是你要找的人”、“我在找自己人”等明确的信息v 隐语。暗号是把信息变换为物件或动作，隐语则是把信息变换成与此信息完全无关的(但有意义的)语言据说，1941年，日本偷袭珍珠港前两星期，美国情报人员曾截获一次重要的电话对话那是两名分别在东京和华盛顿的日本高级官员之间的通话这段对话里“小孩出生”的真正意思是“发动战争” 在华盛顿的日本人：是不是真的有个小孩要出生了?

14、在东京的日本人：是的而且看来马上就要出生了在华盛顿的日本人：这个小孩真的要生了吗?是在哪个方向呢?2526诗情画意传“密语”v早妆未罢暗凝眉，迎户愁看紫燕飞，无力回天春已老，双栖画栋不如归。27诗情画意传“密语”v水洗尘埃道未甞，v甘于名利两相忘。v心怀六洞丹霞客，v口诵三清紫府章。v十里采莲歌达旦，v一轮明月桂飘香。v日高公子还相觅，v见得山中好酒浆。28v机时得到桃园洞 忘钟鼓響停始彼 尽闻会佳期觉仙 作惟女牛底星人 而静织郎弹斗下 机诗赋又琴移象 观道归冠黄少棋 l牛郎织女会佳期，月下弹琴又赋诗。寺静惟闻钟鼓響，音停始觉星斗移。多少黄冠归道观，见幾而作尽忘机。几时得到桃源洞，同彼仙人下象

15、棋。 诗情画意传“密语”29流 童 八 仙 争 合 影 碧 花 含 露 旁 万 幽 卧 雨 染 赵 州 树 信 虹 好 色 十 流 滚 哼 飞 沾 春 分 车 雪 小 照 游 驾 自 队 球 放 梦 夙 圆 桥 古 访 牛 十分春色染赵州，川流车队自驾游。 方沾好雨花含露，路旁万树滚雪球 求访古桥圆夙梦，夕照飞虹卧碧流。 儿童八仙争合影，景幽信哼小放牛。当代诗人刘顺承游赵州桥也写了一首旋读诗:30好 处 深 居 近 翠 峦 音 亲 邀 客 待 闲 秀 清 室 喜 来 归 吟 耸 玉 净 席 残 兴 恣 岩 漱 窗 终 阑 酒 取 飞 泉 寒 陪 聚 宴 欢 涧 宜 桧 竹 松 边 水 寒泉漱玉

16、清音好，好处深居近翠峦。 峦秀耸岩飞涧水，水边松竹桧宜寒。 寒窗净室亲邀客，客待闲吟恣取欢。 欢宴聚陪终席喜，喜来归兴酒阑残南山幽居对客31唐伯虎的卖身契v我康宣，今年一十八岁，姑苏人氏，身家清白，素无过犯。只v为家况清贫，卖身华相府中，充当书僮。身价银五十两，自v秋节起，暂存帐房，以三年后支取，从此承值书房，每日焚v香扫地，洗砚、磨墨等事，听凭使唤。从头做起。立此契凭。 v 32v 吴用智赚玉麒麟吴用智赚玉麒麟 v卢花滩上有扁舟，卢花滩上有扁舟， 俊杰黄昏独自游。俊杰黄昏独自游。v义到尽头原是命，义到尽头原是命， 反躬逃难必无忧。反躬逃难必无忧。 33隐写术的优点v能够被某些人使用而不容易被

17、发现他们间在进行秘密通信v加密则很容易被发现谁与谁在进行秘密通信，这种发现本身可能具有某种意义或作用 34隐写术的缺点v形式简单但构造费时，要求有大量的开销来隐藏相对较少的信息v一旦该系统的构造方法被发现，就会变得完全没有价值v隐写术一般无稳健性35v传说，古时候有一对夫妻，男的名叫李石匠，传说，古时候有一对夫妻，男的名叫李石匠，女的叫张小花。李石匠靠手艺赚钱，张小花在女的叫张小花。李石匠靠手艺赚钱，张小花在家纺纱织布。一年，李石匠参加修建石桥，因家纺纱织布。一年，李石匠参加修建石桥，因工程紧张，十一个月也没回家一次。张小花独工程紧张，十一个月也没回家一次。张小花独自在家只有纺车做伴。一天石匠

18、工地回来一个自在家只有纺车做伴。一天石匠工地回来一个工友路过她家，她托这个工友给丈夫带去一封工友路过她家，她托这个工友给丈夫带去一封书信。书信。 36v1616世纪卡尔达诺发明世纪卡尔达诺发明 “卡尔达诺漏格卡尔达诺漏格板板”漏格板是一张用硬质材料漏格板是一张用硬质材料( (如硬纸、如硬纸、羊皮、金属等羊皮、金属等) )做成的板，上面挖了一些长做成的板，上面挖了一些长方形的孔，即漏格方形的孔，即漏格37王先生： 来信收悉，你的盛情真是难以报答。我已在昨天抵达广州。秋雨连绵，每天需备伞一把方能上街，苦矣。大约本月中旬我才能返回，届时再见。王先生： 来信收悉，你的盛情真是难以报答。我已在昨天抵达广

19、州。秋雨连绵，每天需备伞一把方能上街，苦矣。大约本月中旬我才能返回，届时再见。38v“谜谜”（ENIGMA）密码）密码德国人德国人Arthur Scheribius人发明人发明德国人将其改装为军用型，使之更为复杂可靠德国人将其改装为军用型，使之更为复杂可靠1926年开始使用年开始使用“ENIGMA”，陆军则于，陆军则于1928年开始使用。年开始使用。 1933年，纳粹最高统帅部通信部决定将年，纳粹最高统帅部通信部决定将“ENIGMA”作为德国国防军新式闪击部队的作为德国国防军新式闪击部队的通信装置。通信装置。 1940年，盟军破译年，盟军破译ENIGMA39密码机发展过程v为了简化加密/解密过

20、程，导致密码设备出现。vJefferson cylinder, 1790s被研制成功，包含36个 圆盘，每个圆盘有个随机字母表v 1920年还被美国军队使用。40vWheatstone disc, by Wadsworth in 1817, and Wheatstone in 1860s, comprised two concentric wheels to generate a polyalphabetic cipher。密码机发展过程41v随着密码技术的提高，要求有更高级的密码装置，高级密码装置可以实现更复杂的密码，这些装置在二战时期广泛使用。v 例： the German Enigma,

21、v the Swedish Hagelin (below) and the Japanese Purple密码机发展过程42v以一种形式写下消息，以另一种形式读取消息 vI came I saw I conquered(1)几何图形密码43练习vSuccess in dealing with unkown cipherv密文：SALNOWKIEUCDNNNRCUGNCEIWHIEHPTISS44 最早的一种密码是在公元前2世纪，由一位希腊人提出来的。他将26个字母排列在一个55的方格里，其中i和j填在同一格。abcdefghijklmnopqrstuvwxyz(2)棋盘密码棋盘密码(代替代替)

22、45每个字母对应下列表格中的一个数。比如c对应13，r对应42等等。1112131415212223242531323334354142434445515253545546使用这种密码可以将明文：Please send moneys转换为密文：35 31 15 11 43 15 43 15 33 14 32 34 33 15 54 43在古代这种棋盘密码曾得到广泛的应用。47练习v1、将dealing with 利用棋盘密码加密。v密文：1415113124332252244423v2、已知密文为4315331423153135，求明文。v明文为：sendhelp48(3)恺撒密码恺撒密码 4

23、9恺撒密码字母表恺撒密码一种置换密码，通过将字母按顺序推后3位起到加密作用 。v恺撒密码的加密算法是：c=E(m)=(m+3) mod 26 50Alice要将明文“watch out for brutus”加密成密文，传给Bob。51改进的恺撒加密算法v恺撒加密算法的位移量是3，如果将位移量设置为任何整数，则恺撒密码的改进算法可以写为(KAISER 变换) ：加密算法：c=E(m)=(m+k)mod(26)解密算法：p=D(c)=(c-k)mod(26)v改进的恺撒加密算法有25个可能的密钥k 52改进的恺撒密码加密示例改进的恺撒密码加密示例Alice与Bob协定编码方式为明文字母后移4位，

24、即加密密钥及解密密钥同为k=4。钥Alice将明文“gaul is divided into three part”转为数字代码：（6，0，20，11，8，18，3，8，21，8，3，4，3，8，13，19，14，19，7，17，4，4，15，0，17，19）。使用加密函数E（m） m+k=m+4（mod 26）计算得：（10，4，24，15，12，22，7，12，25，12，7，8，7，12，17，23，18，23，11，21，8，8，19，4，21，23）即密文“K，E，Y，P，M，W, H, M, Z，M，H，I，H，M，R，X，S，X，L，V，I，I，T，E，V，X”。 53改进的恺撒

25、密码解密示例改进的恺撒密码解密示例Bob收到密文“KEYPMWHMZMHIHMRXSXLVIITEVX”= （ 10，4，24，15，12，22，7，12，25，12，7，8，7，12，17，23，18，23，11，21，8，8，19，4，21，23 ）使用解密函数D（c）c-k=c-4（mod 26）计算，并考虑空格，可还原明文：（6，0，20，11，8，18，3，8，21，8，3，4，3，8，13，19，14，19，7，17，4，4，15，0，17，19）=“gaul is divided into three part”。 54v恺撒密码是单字母密码，仅仅采用了简单替换技术，其优点是算法

26、简单，便于记忆。缺点是结构过于简单，密码分析员只使用很少的信息就可预言加密的整个结构。因此这种密码的密度是很低的，只需简单地统计字频就可以破译。55练习v1、 k=5时，将data security 利用的caesar密码加密。v密文：IFYFXJHZWNYDv2、已知密文为UQJFXJXJSIRTSJDX且 k=5，求明文。v明文为：please send moneysv3、 已知密文为UQJFXJXJSIRTSJDX,求明文56(4)仿射密码仿射密码26 mod)m()(21kkmE57仿射密码示例仿射密码示例Alice与Bob事先协定一把密钥K=(3,8)其中gcd(3,26)=1E(.

27、)maffine(0,5,5,8,13,4)(8,23,23,6,21,20)IXXGVUc E(m)3m8 (mod26)1D(c)3 (c8)9(c8) (mod26)D(.)cIXXGVU(8,23,23,6,21,20)(0,5,5,8,13,4)affinem 58练习v1、 k1=17,k2=10时，将equal 利用仿射变换密码加密。v密文：AWMKPv2、已知密文为JKVK且 k1=17,k2=10，求明文。v明文为：data59v以不同的行写下消息字母 v按行读取消息v Plain: I came I saw I conquered v I A E S W C N U R D

28、 v C M I A I O Q E E vCipher: IAESW CNURD CMIAI OQEE vPlain: All men are created equal(5)轨道栏杆密码 Rail Fence cipher60v把明文的前一半写成一行，后一半写在上一行的下面一行，由左向右按列读取v Plain: He that will not work shall not eat vC:HOERTKHSAHTAWLILLNLONTOETAWT(5)轨道栏杆密码 Rail Fence cipher61v三行栅栏密码v Plain： time past cannot be called ba

29、ck againvC: TESAOELDCGNIPTNTCLBKAMACNBAEAAI(5)轨道栏杆密码 Rail Fence cipher62v解密v C： SADNISIUEFIHIDSKHNOGNTTTOLGTNUTYv破译：v1、C：TEOGSDYUTAENNHLNETAMSHVAEDv2、C:LAOANCVOHSEOGGTDEEGEFNNOSSMLDERRDGDCAIITTAISv3、C:云风深渐星娥偷碧天心母烛长落沉应灵海夜屏影河晓嫦悔青夜(5)轨道栏杆密码 Rail Fence cipher63v1、ACDNSILAPNCIETWLHPCv 2、NHGDFUTHAHITOIIII

30、LOENOLRTNSFCTTMWWLY练习64(6) 倒序密码v 在置换密码体制中，明文中的字或字母被重新排列，字或字母本身不变，但位置发生了改变，形成密文，又称为易位密码易位密码。v 最简单的易位密码是采用报文倒置法，即将报文按字的顺序依次倒置，并截成固定长度的字母组，形成密文，也称为倒序法.v也可先将明文分成几个字母一组，再将每一组按照相反的顺序书写。65v明文：明文：never accept failure no matter how often it visits youv密文：密文：UOYS TISI VTIN ETFO WOHR ETTA MONE RULI AFTP ECCA R

31、EVENv密文2： 五个字母一组vnever accep tfail ureno matte rhowo fteni vTvisi tsyouvREVEN PECCA LIAFT ONERU ETTAM OWOHR INETF ISIVT UOYST66v解密：解密：v密文：密文：DAEHTUTNEVDFOERNICNANEMGv明文： 五个字母一组vthe adventure of dancing menv特点： 简单，缺点是不安全，很容易被识破。67福尔摩斯探案集之人形密码 v希尔顿最近结婚了，他给福尔摩斯发去了一封信，信中有一张纸是他在花园中发现的，这张纸是用跳舞的棒形小人所写的。686

32、9707172737475767778（7） Playfair密码密码v最著名的多表代换密码是Playfair密码，它把明文中的双字母音节作为一个单元并将其转换成密文的双字母音节。v这个密码实际上是由英国科学家Charles Wheatstone于1854年发明的，但是却挂着他的朋友Baron Playfair的名字。在英国的外事机构中，Baron Playfair在密码方面的成就是首屈一指的。v例如使用的密钥词是playfair，建立下列矩阵。playfirbcdeghkmnoqstuvwXZ79v对明文按如下规则一次加密两个字母一次加密两个字母：v1. 如果一组的两个字母是相同的，那么在它

33、们之间加一个填充字母，比如x。例如balloon先把它变成ba lx lo on 这样四个字母对。v2. 落在矩阵同一行的明文字母对中的字母由其右边的字母来代换，每行中最右边的一个字母就用该行中最左边的第一个字母来代换，比如ar变成LB。v3. 落在矩阵同一列的明文字母对中的字母由其下面的字母来代换，每列中最下面的一个字母就用该列中最上面的第一个字母来代换，比如mu变成EZ。v4. 其他的每组明文字母对中的字母按如下方式代换：该字母所在行为密文所在行，另一字母所在列为密文所在列。比如hs变成KQ，ea变成HP。80vM: meet at the school housevC: EGMNFQQM

34、KNBKSVVRGQXNKUvC: ITXSDCWTQZ 密钥为：ciphersvM：howareyou81v Playfair密码相对于简单的单表密码是一个巨大的进步。首先，因为有26个字母，故有2626=676个字母对，因此对单个字母对进行判断要困难得多。而且，单个字母的相对频率比字母对的相对频率在统计规律上要好。这样利用频率分析字母对就更困难一些。v 因为这些原因，Playfair密码在很长一段时间内被认为是牢不可破的。第一次世界大战中英军就使用它作为陆军的战时加密体制，并且在第二次世界大战中，美军及其他一些盟国军队仍在大量使用。82v 尽管Playfair密码被认为是较安全的，它仍然是

35、相对容易攻破的，因为它的密文仍然完好地保留了明文语言的大部分结构特征。 v 如果频率分布的信息完全被加密过程隐藏了，那么密文的频率曲线应该是一条水平线水平线，惟密文密码分析由此下手将一无所获。Playfair密码虽然有比明文稍平坦的频率分布曲线，但是仍然透露了大量的信息给密码分析者。 83（8） 乘积密码v 是一种替换与变换合用的密码，一般情况下，手工破译是非常困难的。v 一种有名的乘积密码“ADFGX cipher” 在第一次世界大战中使用。84ADFGX 乘积密码 v 这样命名是因为变换仅依赖与 ADFGX，在WW1有德国人使用，并被英国人破译。v 方法：使用一个固定的替换表，把每个明文字

36、母映射成一个字母对 (row-col index)，再用一个带密钥的块变换把每个对分解，利用带密钥的块变换写下所有字母对，写出密文（按块密码形式）。85ADFGX 初始矩阵 v A D F G X A P G C E N D B Q O Z R F S L A F T G M D V I W X K U Y X H 86v m: kaiser wilhelm 关键字：cipherv C: XFGXGGDFFFGGGAAXXAFAGAGXDD v解密：FA XX DX GD GA AF AG DF AF XF GG GG XG 关键字：CREATv明文：kaiser wilhelm87ADFGV

37、Xv v 方法：使用一个固定的替换表，把每个明文字母映射成一个字母对 (row-col index)，再用一个带密钥的块变换把每个对分解，利用带密钥的块变换写下所有字母对，写出密文（按块密码形式）。88ADFGVX Substitution Table v A D F G V X A K Z W R 1 F D 9 B 6 C L 5 F Q 7 J P G X G E V Y 3 A N V 8 O D H 0 2 X U 4 I S T M 89ADFGVX 加密举例 vPlaintext: PRODUCTCIPHERS vIntermediate Text: v FG AG VD VF

38、XA DG XVv DG XF FG VG GA AG XG v带密钥的块变换矩阵： vD E U T S C H Keyv2 3 7 6 5 1 4 Sorted OrdervF G A G V D V vF X A D G X V vD G X F F G V vG G A A G X G vCiphertext: DXGX FFDG GXGG VVVG VGFG GDFA AAXA90练习vencrypt and then decrypt by hand, the text below using the ADFGVX cipher with a key of CIPHER: v v 7

39、73 soliders were killed.91 利用预先设计的利用预先设计的固定固定代替规则代替规则, ,对明文对明文逐逐字符字符或或逐逐字符组字符组进行代替的密码进行代替的密码. .字字符组称为一个代替单位符组称为一个代替单位. . 这里这里代替规则代替规则又称为又称为代替函数代替函数、代替表代替表或或S S盒。盒。它的它的固定性固定性是指这个代替规则与是指这个代替规则与密密钥因素钥因素和被加密的明文字符的和被加密的明文字符的序号序号无关。即无关。即相同的相同的明文字符组产生明文字符组产生相同的相同的密文字符组密文字符组. .（9）单表代替密码）单表代替密码92 例例1: 1: 汉字和

40、符号的区位码汉字和符号的区位码( (单表代替单表代替) ) 93例例2 2 以十进制数为代替单位的代替函数则明文则明文晨五点总攻晨五点总攻 先变换为区位码先变换为区位码 1931 4669 2167 5560 2505 再被加密成密文 4624 1996 8497 0095 8050单表代替的缺点:明文字符相同,则密文字符也相同9 , 2 , 1 , 09 , 2 , 1 , 0:S105,4,8,2,1, 0,9,7,3,6S假设明文 0 1 2 3 4 5 6 7 8 9密文 5 4 8 2 1 0 9 7 3 6即代替表为即代替表为: :94v信息与计算科学v48374702517528

41、38436731384907v计算机密码学v28384367279035603475490795qkmmEckmod)()(加密变换加密变换:1, 2 , 1 , 0qZq 例例3 3 加法密码加法密码 选定选定常数常数 q 和和 k. . 明文空间明文空间= =密文空间密文空间= =qkccDmkmod)()(解密变换解密变换：9690,10mod) 3()(3mmmEc加密变换为加密变换为： 特别地特别地,若取若取q =10 和和 k=3, ,则则解密变换为解密变换为：90,10mod) 3()(3cccDm 此时此时, ,明文明文: :晨五点总攻晨五点总攻 变换为区位码变换为区位码193

42、1 4669 2167 5560 2505后就被加密成密文4264 7992 5490 8893 5838 缺点: 密文差 = 明文差10mod)(10mod)3() 3(10mod) 3(10mod) 3(21212121mmmmmmcc97单字母替代单字母替代 v如果明码字母表是由26个符号组成，则该字母表存在有26！41026种单字母替代密码。 v讨论该类型的一种简单密码 ，这个密码以一个密钥开始，该密钥是明码字母表中的一个串 。v举例：Southeast University 98v密钥短语密码本 1v密钥短语密码本 299练习v密钥为southeastuniversity,利用第二组

43、密码本加密：vHelp I am lost 100（10）Vigenre密码密码12nm(m ,m ,m )mod2612nk(k ,k ,k )mod261122nnE(m)mk(mk ,mk ,mk ) (mod 26)1122nnD(c)ck(ck ,ck ,ck ) (mod 26)101Vigenre密码密码示例示例例： Alice欲使用Vigenre密码加密法与Bob通信，其中他们已事先约定双方用密钥k(21,4,2,19,14)明文：m=ciphertext明文明文ciphertext明文代码明文代码 281574171942319密钥密钥2142191421421914模加法值

44、模加法值 23121701812236167密文密文XMRASMXGQH102103练习v密钥为king, 加密：vWhere there is a will,there is a wayv密文：GPRXOBUKBMVYKEVRVBUKBMVYKENEv密文：GLAMAHXJQWOXXZVIFV,密钥为friendv明文：business is business104105Beaufort方阵v加密：v解密：1122nnE(m)mk1(mk1,mk1,mk1) (mod 26) 1122nnD(c)ck1(ck1,ck1,ck1) (mod 26) 明文：data 密钥：best密文：BVAG

45、密文：QZJA 密钥：best明文：secu106（11） Hill密码密码 v另一个有趣的多表代换密码是Hill密码，它是1929年由数学家Lester Hill发明的。加密算法将m个连续的明文字母替换成m个密文字母，这是由m个线性方程决定的 。v例如m=3时，C=KP mod 26c1c2c3k11 k12 k13k12 k22 k23k31 k32 k33p1p2p3mod 26107v明文：blockcipherv分组：blo ckc iph erx-(1 11 14)( 2 10 2 )(8 15 7 )(4 17 23 ）v初始矩阵：1 2 34 5 611 9 8v密文：RBZM

46、UEPYONOMv逆矩阵：22 5 16 17 2415 13 1108v解密则使用K的逆矩阵K -1：vP K -1 CK K -1 PPv同Playfair密码相比，Hill密码的优点是完全隐藏了单字母的频率特性。实际上，Hill用的矩阵越大所隐藏的频率信息越多。 v 尽管Hill密码足以抗惟密文攻击，但是它较易被已知明文攻击破解。对于一个mm的Hill密码，假如我们有m个明密文对，每个长度都是m，那么可以得到mm的明文矩阵X和密文矩阵Y，且有Y=KX。v 若X可逆，则K=YX -1。若X不可逆，则找到一个可逆的X即可。v 109单表古典密码的统计分析单表古典密码的统计分析原理原理：明文的

47、统计规律在密文中能够反映出：明文的统计规律在密文中能够反映出 来，故信息泄露大。来，故信息泄露大。多表古典密码的统计分析多表古典密码的统计分析原理原理：密钥相同时，相同的明文对应相同的：密钥相同时，相同的明文对应相同的 密文。密文。频率攻击法110v单一字母替代编码在公元1世纪开始到10世纪使用广泛。v随着统计学和概率的发展，破解单一字母替代编码非常容易。因为在语言中不同字母出现的概率不同，有些字母常见，有些字母则很少出现。111单一字母密码破译单一字母密码破译 v任意替换具有26！41026 可能的key，大于56位DES的密钥空间，但是使用基于语言统计规律仍可破译。 112113最常用，出

48、现频率在百分之一以上的有14个音节，它们是：de shi yi bu you zhi le ji zhe wo yen li ta dao的是 一 不有之 了机 这我们 里 他 到次常用音节有33个，它们是：zhong zi guo shang ge men he wei ye da gong jian jiu xiang zhu lai sheng di zai ni xiao ke yao wu yu jie jin chan zuo jia xian quan shuo 114从三亿汉字的母体材料中，抽样二千五百万字进行双音节词词频统计，结果是：频率在一万次以上的双音节词有33个：我们三

49、万次以上可以 他们 二万次以上进行 没有 工作 人民 生产 这个 发展 就是 问题 国家 中国 这样 革命 自己 不能 由于 这些 所以 因此 作用 一般 什么 如果 情况 必须 方法 因为 主要 要求 社会115仿射密码破译v例：FMXVED KAPHFE RBNDKR XRSREF MORUDS DKDVSH VUFEDK APRKDL YEVLRH HRHA B C D E F G H IJK L M N O P Q R S T U V W X Y Z2 1 0 7 5 4 0 5 0 0 5 2 2 1 1 2 0 8 3 0 2 4 0 2 1 0vAlgorithm are qui

50、te general definitions of arithmetic processes116 单表置换单表置换117下面以一个例子说明密码分析是如何进行的。已知密文G J X X N G G O T Z N U COT W M O H Y J T K T A M T X O B Y N FG OG I N U G J F N Z V Q H Y N G N E A J F H Y O T W G O T H Y N A F Z NF T U I N Z B N E G N L N E U T X N X U F N E J C I N H Y A Z G A E UT U C Q G O

51、 G O T H J O H O A T C J X K H Y N U V O C O H O U H C N UG H H A F N U Z H Y N C U T W J U W N A E H Y N A FOWOT U C H N PH O G L N F Q Z N G O F U V C N V J H T A H N G G NTHOU C G J X YO G H Y N A B N T O T W G N T H N T X N A E B U F K N F YO H HGIUT J U C E A F H Y N G A C J H O A T A E I O C O

52、 H U F Q X O B Y N F G 从大量非技术性的英文书籍、报刊、文章中摘取适当长度的章节进行统计，发现英文字母在各个文章中出现的频率几乎相同。 118119120121122123124单字母单字母中e出现次数最多，t,a,o出现较多。双字母双字母中th,he,in,er,an,re,ed,on,es,st,en,at,to,nt,ha,nd,ou,a,ng,as,or,ti,is,et,it,ar出现频率较高。三字母三字母中：the,ing,and,her,ent出现频率较高。125因此可将英文字母分为以下几组：高频率组：e,t,a,o,n,i,r,s,h.(=0.0528)中频率组：d,l,u,c,m.低频率组：p,f,y,w,g,b,v极低组：j,k,q,x,z 对密文字母进行统计，出现的频率如下：A b c d e f g h I j k l m n o p q r16 5 13 0 7 17 23 26 5 12 3 2 2 36 25 1 5 0 s t u v w x y z 0 22