高中数学选修5-3(密码学算法基础)选修课密码学1课件.ppt

1、密码学初探邢星 xing.creature_杭州第七中学,Zhofrph Wr Wkh Frxuvh Ri Fubswrorjb,Welcome To The Course Of Cryptology,农户、鸡 快吃吧，这是你最后一顿！ 鸡躺倒并留遗书： 爷已吃老鼠药，你们别想吃爷了，爷也不是好惹的。,当对手知道了你的决定之后，就能做出对自己最有利的决定。 纳什均衡理论,保密、信息安全很重要,“要让三个人保住秘密，其中两个人必须死亡！” 本杰明富兰克林,电视剧暗算语录,电视剧暗算关于破译密码的语录 说到底密码玩的是欺骗，是躲藏，是暗算。 兵不厌诈，密码是兵器，是兵器中的暗器， 是人间最大的狡诈

2、。 研制和破译密码的人都是撒旦。 研制密码的事业，就是一项接近疯子的事业。 你越接近疯子，你越接近天才。 葬送于密码界的天才，是所有科学领域里概率 最高的。密码是天才的屠宰场。,电视剧暗算关于破译密码的语录 破译密码是听死人的心跳声。破译密码是男人生孩子、女人长胡子。破译密码是释读天书，看懂无字之书。 破译密码, 比用沙子搓一根绳子还难，比用空气铸一把利剑还难，比用火点燃水还难。正常情况下，这都是不可能的，我们就是要把这种不可能变成可能。 破译密码呢，就跟男女之间谈恋爱一样，不是说你谈多了就一定能谈成。关键是看你有没有感情，有没有缘份。,电视剧暗算关于破译密码的语录 所有的密码都可以演变成一道

3、或者几道超难的数学题。 破译技术作为一门数学科学，尖锐而深邃的数学能力，跟良好心理素质是一样必要又重要的。两者犹如一对飞翔的翅膀，缺一不可。 它需要你悟出世界上最高级的谜和最低级的谜。除了必要的知识、经验、技术之外，还需 要远在星辰之外的好运气。,密 码 学,学：学科，应用数学，数学在信息保护中的应用 码：编码，信息从一种形式到另一种形式的转变 密：秘密，目的是使信息处于秘密的状态,学科认识,引言 密码学简介,密码学是一门古老而年轻的科学，在当今的信息时代，大量敏感信息如法庭记录、私人文档、软件源代码、银行交易、保险单据等常常通过公共通信设施或计算机网络来进行交换。 为了保证这些信息的私密性、

4、完整性、真实性，必须使用技术手段对其进行处理。 私密性:对信息处理后，保证让他人不能读懂。 真实性:对信息处理后，保证他人不能篡改信息（改了之后会被接收者发觉）。 完整性:对信息处理后，保证他人不能从原始信息中删除或插入其它信息（删除或插入后会被接收者发觉）。,密码学常识,密码学（cryptology）作为数学的一个分支，是密码编码学和密码分析学的统称。 使消息保密的技术和科学叫做密码编码学 （cryptography) 破译密文的科学和技术就是密码分析学 （cryptanalysis） 明文：是作为加密输入的原始信息，即消息的原始形式，通常用m或p表示。所有可能明文的有限集称为明文空间，通常

5、用M或P来表示。,密文：是明文经加密变换后的结果，即消息被加密处理后的形式，通常用c表示。所有可能密文的有限集称为密文空间，通常用C来表示。 密钥：是参与密码变换的参数，通常用k表示。一切可能的密钥构成的有限集称为密钥空间，通常用K表示。 加密算法：是将明文变换为密文的变换函数，相应的变换过程称为加密，即编码的过程（通常用E表示，即c=Ek(p)）。 解密算法：是将密文恢复为明文的变换函数，相应的变换过程称为解密，即解码的过程（通常用D表示，即p=Dk(c)）。,原始部落间的秘密通信,隐写术,密码学发展历史,信息载体：奴隶的头,剃光, 信息传递：长出头发的奴隶,密码学的发展历程大致经历了三个阶

6、段：古代加密方法、古典密码和近代密码 一、古代加密方法（手工阶段）,公元前400年，古斯巴达人 用一条带子缠绕在一根木棍上， 沿木棍纵轴方向写好明文， 解下来的带子上就只有杂乱无章的密文字母。 解密者只需找到相同直径的木棍， 再把带子缠上去，沿木棍纵轴方向即可读出有意义的明文。 这种叫做“天书”的器械堪称人类历史上最早使用的密码器械。,密码学发展历史,诗情画意传“密语”,早妆未罢暗凝眉， 迎户愁看紫燕飞， 无力回天春已老， 双栖画栋不如归。,密码学发展历史,水洗尘埃道未甞，甘于名利两相忘。 心怀六洞丹霞客，口诵三清紫府章。 十里采莲歌达旦，一轮明月桂飘香。 日高公子还相觅，见得山中好酒浆。,洗

7、尘埃道未甞于名利两相忘怀六洞丹霞客诵三清紫府章里采莲歌达旦轮明月桂飘香高公子还相觅得山中好酒浆,密码学发展历史,白居易游紫霄宫,王先生： 来信收悉，你的盛情真是难以报答。我已在昨天抵达广州。秋雨连绵，每天需备伞一把方能上街，苦矣。大约本月中旬我才能返回，届时再见。,王先生： 来信收悉，你的盛情真是难以报答。我已在昨天抵达广州。秋雨连绵，每天需备伞一把方能上街，苦矣。大约本月中旬我才能返回，届时再见。,密码学发展历史,卡丹网格式密码,隐写术（信息隐藏）的另外一些例子,悠扬琴声奏响“进军号角” 显微镜里传递情报 魔术般的密写术 网络与数字幽灵 量子技术隐形传递信息 ,密码学发展历史,隐写术的优点,

8、能够被某些人使用而不容易被发现他们间在进行秘密通信 加密则很容易被发现谁与谁在进行秘密通信，这种发现本身可能具有某种意义或作用,隐写术的缺点,形式简单但构造费时，要求有大量的开销来隐藏相对较少的信息 一旦该系统的构造方法被发现，就会变得完全没有价值 隐写术一般无稳健性,代替：明文中的字母由其他字母、数字或符号所取代的一种方法，具体的代替方案称为密钥。,密码学发展历史,二、古典加密方法（代替密码、换位密码）,公元前1世纪，著名的恺撒密码(古罗马统帅恺撒:约公元前10044) 被用于高卢战争中， 这是一种简单易行的单字母替代密码。,密码学发展历史,9世纪，阿拉伯的阿尔.金迪 提出频度分析的方法来解

9、密， 通过分析计算密文字符出现的频率来破译密码。 16世纪晚期，苏格兰女王玛丽 密码信，策划暗杀英国女王伊丽莎白。 英国的菲利普斯 利用频度分析法成功破解 这次解密将玛丽送上了断头台。,密码学发展历史,16世纪中期，意大利的卡尔达诺 发明了卡尔达诺漏格板， 覆盖在密文上，可从漏格中读出明文， 这是较早的一种分置式密码。,追杀令：YOU KILL AT ONCE,情书,密钥,16世纪晚期， 法国的维吉尼亚Vigenere 提出著名的维吉尼亚方阵密表、维吉尼亚密码， 这是一种多表加密的替代密码， 可使阿尔.金迪和菲利普斯的频度分析法失效。,密码学发展历史,密码学发展历史,维吉尼亚方阵密表,19世纪

10、， 英国的巴贝奇、普鲁士的卡西斯基Kasiski 发展了更复杂的频度分析法， 可破解维吉尼亚密码,密码学发展历史,密码学发展历史,17世纪， 英国著名的哲学家 弗朗西斯培根 学问的发展 最早给密码下了定义： “所谓密码应具备三个必要的条件，即 易于翻译、第三者无法理解、在一定场合下不易引人生疑。”,密码学发展历史,1883年，荷兰密码学家A.Kerckhoffs密码设计规则军事密码学： G 密码系统应该是计算安全的； G 密钥由通信双方事先约定好，并根据一定协议进行更换； G 密码系统应该易于使用；G 密码系统应该精确而有效； G 除了密钥，密码系统的所有细节都为对手所知。 Kerckhoff

11、s原则在今天看来仍然具有十分重要的现实意义。,11世纪 兵书武经总要 中国历史上第一部有关密码的记述 介绍了一个小型却名副其实的密码本。,密码学发展历史,密码学发展历史,劉邦打下天下之後，害怕韓信造反，所以打算把他殺了。 又怕他帶的士兵太多，所以問了一下韓信目前帶了多少兵？ 韓信感覺氣氛詭異，因此回答： 兵不知數，三三數之剩二，五五數之剩三，七七數之剩二 這個回答讓劉邦不知所措，連軍師張良一下子也算不出， 想到一个数136,0128 (一百多万)，不敢輕舉妄動。 韓信所帶的兵，人數可以少到23人， 當然也可能是千萬人， 通解為23+105t 105=3,5,7 中国剩余定理 成也萧何，败也萧何

12、。吕后用萧何诱杀韩信,密码学发展历史,一战前，密码研究还只限于一个小领域，没有得到各国应有的重视。 第一次世界大战是世界密码史上的第一个转折点。 随着战争的爆发，各国逐渐认识到密码在战争中发挥的巨大作用， 积极给予大力扶持，使密码很快成为一个庞大的学科领域。 第一次世界大战进行到关键时刻， 英国破译密码的专门机构“40号房间” 利用缴获的德国密码本破译了著名的“齐默尔曼电报”， 促使美国放弃中立参战，改变了战争进程。,密码学发展历史,第二次世界大战爆发后， 世界各国开始重视对密码破译的研究工作， 纷纷成立专门的研究和破译机构，在战争中发挥重要的作用。 德国潜艇指挥部德尼茨的B机关泄露了太多的军

13、事情报。 波兰人和英国人破译了德国著名的“恩格玛”密码机密码， 德国的许多重大军事行动对盟军都不成为秘密。,Enigma密码(1),Enigma密码(2),图灵的贡献 1937年英国对德宣战，布莱切利公园 1940，“炸弹” 一小时破译一个密码,1944年6月4日， 德国U-505潜艇受到美海军特遣大队反潜深炸弹攻击， 受伤浮起后，美军冲入无线电室， 缴获了密码机和大量明、密报， 并秘密将U-505潜艇拖回美国。 德军误认为U-505潜艇沉没海底而未换密码。 在欧战结束前的11个月里，依靠破译的密码， 美军和同盟国军队共击沉德国潜艇300多艘，平均每天一艘， 同时大大减少了自己船只的损失，对战

14、争的胜利产生了重大影响。,密码学发展历史,美军成功地破译了日本的通讯密码， 从而导致日本在中途岛海战中失利， 既报了珍珠港的一箭之仇，又使太平洋战场的局面得到彻底扭转。 二战期间，美军破译日本海军密码多达75种，由于密码被破译， 日本总吨数约三之二的商船被美国潜艇击沉， 给日本军队带来了严重的战争后果。,密码学发展历史,山本五十六之死 “山本五十六于1943年4月13日下午5时55分到所罗门岛视察”的日程 用称为“紫密”的日本“九七式”密码机加密，播给第一基地部队等。 美军截获，通过破译JN25密码的专用IBM设备破译出。 尼米兹上将经研究决定出击： 4月13日7时25分出动18架战斗机将山本

15、座机击落 偷袭珍珠港的元凶日本舰队总司令山本五十六死亡 5月21日日本才广播这一消息。,密码学发展历史,密码学发展历史,二战结束后，一位深知战时密码破译价值的美国官员说， 密码破译使第二次世界大战缩短了几年。这种说法虽有些夸张， 但重要情报的破译确实影响了战争的进程，挽救了成千上万的生命。 第二次世界大战促进了密码的飞速发展。 由于密码对于战争的胜负具有越来越重要的影响， 各国不惜花大量的人力物力进行密码的研究和破译。 密码的编制结构更加科学，编制方法愈加复杂， 各种密码的保密性出现了飞跃性的提高。 在此期间，许多国家开始使用密码机进行加密， 密码告别人工加密，走向机械加密的开始。,1948年

16、以前的密码技术可以说是一种艺术，而不是一种科学， 那时的密码专家是凭直觉和信念来进行密码设计和分析的， 而不是靠推理证明。 1948年，C. E. Shannon(19162002) 在贝尔系统技术杂志上发表论文通信的数学理论， 创立了著名的新理论信息论， 标志着密码术到密码学的转变。,密码学发展历史,20世纪70年代中期，密码学界发生了两件跨时代的大事： Diffie和Hellman发表的题为“密码学新方向”文章， 提出了“公钥密码”新体制，冲破了传统“单钥密码”体制的束缚。 传统密码体制主要功能是信息的保密， 双钥(公钥)密码体制不但赋予了通信的保密性， 而且还提供了消息的认证性 新的双钥

17、密码体制无需事先交换秘密钥就 可通过不安全信道安全地传递信息， 大大简化了密钥分配的工作量。 双钥密码体制适应了通信网的需要， 为保密学技术应用于商业领域开辟了广阔的天地。,密码学发展历史,20世纪70年代中期，密码学界发生了两件跨时代的大事： 美国国家标准局NBS于1977年公布实施美国数据加密标准DES， 保密学史上第一次公开加密算法，并广泛应用于商用数据加密 这两件引人注目的大事揭开了保密学的神秘面纱， 标志着保密学的理论与技术的划时代的革命性变革 为保密学的研究真正走向社会化作出了巨大贡献， 同时也为保密学开辟了广泛的应用前景。 从此，掀起了现代密码学研究的高潮。,密码学发展历史,自从

18、人类有了战争，就有了密码。 自古以来，通信安全保密 在国家的军事和安全部门 一直受到十分广泛的关注。 从原始的手工作业 到采用机械设备、电器机械设备，进而发展 到今天的以使用电子计算机及微电子技术为标志的电子时代。,密码学简史(小结),密码学的作用和意义,历史上的战争，特别是两次世界大战， 对于保密学的理论与技术 的发展起了巨大的推动作用。 在通信安全、保密、密码分析上的优势， 被认为是赢得历史上许多主要军事冲突 (包括二次世界大 战)胜利的关键因素之一。,密码学的作用和意义,我们正在步入一个崭新的信息社会， 信息在社会中的地位和作用越来越重要， 信息就是生命 “9.11” 信息就是时间 “1

19、37670348315732568089372384837 mod 13” 信息就是财富 “炒股” 每个人的生活都与信息的产生、存储、处理和传递密切相关 “谁掌握了信息，控制了网络，谁就将拥有整个世界！” 信息的安全与保密问题成了人人都关心的事情， 使密码学脱去神秘的面纱， 成为大家感兴趣并为更多人服务的科学。,信息空间中的侦察与反侦察、截获和反截获、 破译和反破译、破坏和反破坏 的斗争愈演愈烈： 军事上的电子对抗：1991年初海湾战争空前大规模的电子战 信息空间中的信息大战正在俏情而积极地酝酿中， 小规模的信息战一直在不断地出现、发展和扩大。 信息战是 信息化社会发展的必然产物。 商业上的情

20、报战 随着Internet、Intranet、 Extranet， 特别是电子商务的发展而步入了新的阶段。 近年来，在网络上所进行的各犯罪活动出现了逐年上升的趋势， 由此所造成的经济损失是十分巨大的。,密码学的作用和意义,Internet的全球性、开放性、无缝连通性、共享性、动态性发展， 任何人都可以自由接入Internet，其中有善者，也有恶者。 恶者会采用各种攻击手段进行破坏活动： 整天在试图穿透别人的系统、窃取重要情报、 捣毁别人的信箱、倾泻信息拉圾、 散布破坏性信息、施放病毒、 进行网络欺诈、发动黑客战等。 给国家、单位和个人的信息安全带来极大的威胁。 Internet一方面成为人们离

21、不开的信息工具， 同时它也成为公开的攻击对象目标。,密码学的作用和意义,全球计算机病毒已达8万多种，每天要产生5-10种新病毒。 曾肆虐全球、具有里程碑意义的红色代码和尼姆达病毒， 改写了病毒的形态和病毒的传播历史，步入了混合型病毒时代。 1999年4月26日，受CIH病毒的侵害， 我国有36万多台计算机受到破坏，经济损失达12亿元。 2003年24-26日轰动世界的Slammer病毒，利用SQL漏洞发起攻击 数小时后已使南韩网络不堪负重， 亚洲、北美的Web网站和Internet业务提供商不能正常工作 星期六使美国最大的自动柜员机(ATM)网络中断， 直到午后很久，所有的13000 ATM都不能使用。,密码学的作用和意义,2003下半年出现“冲击波” 病毒， 受感染的主机超过40万台，并 曾一度使加拿大航空系统瘫痪。 Slammer病毒和“冲击波” 病毒都是攻击型混合病毒。,密码学的作用和意义,美国的信息