《网络空间安全概论》课件3密码学基础

1畅销小说《达·芬奇密码》里面出现的密码13-3-2-21-1-1-8-5

ODraconiandevil!（啊，严酷的魔王！）

OhLameSaint!（噢，瘸腿的圣徒！）

LeonardodaVinci!（莱昂纳多·达·芬奇！）

TheMonaLisa!（蒙娜丽莎！）23美剧《绯闻女孩》（GossipGirl）每集开场白都是：WhoamI?That'sasecretI'llnevertell.Youknowyouloveme.XOXO.Gossipgirl.Ifyoulookateachletterlikeitwasrepresentingtwopeoplefromabird'seyeview,the"O"representsthearmsofthosepersonshuggingeachotherwhilethe"X"isevocativeoftwopeoplekissingeachother.4安全与密码学密码学目标机密性数据完整性认证非否认……………5密码学是安全的解吗?密码学与安全是不同的85%安全问题不能用密码学解决（CERT）30-50%是缓冲区溢出5SecurityCryptographyLawOperating

systemsMathematicsNetworkingProgramming

languagesEconomicsPsychologyHuman

computer

interaction6现实世界提供了更多的攻击手法，而不仅仅是密码分析.协议攻击、木马、病毒、电磁辐射监测、物理危害、勒索、操作系统漏洞、应用程序漏洞、硬件漏洞、用户错误、物理窃听、社会工程攻击、垃圾搜索等等。传统密码学古典密码时期：从古代到19世纪末，长达几千年纸、笔或者简单器械实现的替代及换位，是一种艺术（富有创造性的方式、方法）；手工；信使近代密码时期：20世纪初到20世纪50年代，即一、二战时期手工或电动机械实现的复杂的替代及换位，仍是一门艺术；机械；电报通信现代密码学：从20世纪50年代至今分组密码、序列密码以及公钥密码等，有坚实的数学理论基础。成为一门科学；计算机；无线通信、有线通信、计算网络等密码学起源公元前5世纪，古希腊斯巴达出现原始的密码器——Scytale密码：最早的换位密码术大约在4000年以前，在古埃及的尼罗河畔，替换密码隐写术（steganography）剃头刺字（公元前440年古希腊战争）--隐写术的起源隐写术：将消息隐藏在其他消息中—“信息隐藏”隐写墨水/藏头诗/藏尾诗漏格方法（1550年）--卡尔达诺漏格绘画大风渐起，寒流攻击着我们的肌体，预示明天5点的活动开始时会有困难。中国的藏头诗《水浒传》中梁山为了拉卢俊义入伙，“智多星”吴用和宋江便生出一段“吴用智赚玉麒麟”的故事来，利用卢俊义正为躲避“血光之灾”的惶恐心理，口占四句卦歌：

芦花丛中一扁舟，俊杰俄从此地游。

义士若能知此理，反躬难逃可无忧。电影：唐伯虎点秋香现代的信息隐藏信息隐藏(InformationHiding):将秘密信息隐藏于另一非机密的文件内容之中。形式可为任何一种数字媒体，如图像、声音、视频或一般的文档等。首要目标是隐藏的技术要好，也就是使加入隐藏信息后的媒体目标的降质尽可能小，使人无法看到或听到隐藏的数据，达到令人难以察觉的目的101101011010101010100101000101101101101010100101011010101011110000101010100101110101101011010100101001000010011101010011110110111101110111010001+=密码学古典密码学现代密码学置换密码代替密码流密码分组密码公钥密码对称密码非对称密码密码体制的分类经典密码体制都是对称密码体制，密钥由安全信道传递，可分为：替换密码/代换密码（Substitution）—用一个符号代替另一个符号单表替换密码仿射密码（移位代换密码，乘数密码）多表替换密码置换密码/换位密码（Permutation）—对符号进行重新排序14古典密码学替换密码根据预先建立的替换表，将明文依次通过查表，替换为相应字符，生成密文，替换密码的密钥就是替换表单表替换密码：使用一个固定的替换表——明文、密文字符一一对应多表替换密码：使用多个替换表15

16公元前1世纪，著名的恺撒(Caesar)密码被用于高卢战争中，这是一种简单易行的单字母替代密码它是将字母表中的字母依次后移一定的位置得到的明码表：ABCDEFGHIJKLMNOPQRSTUVWXYZ密码表：FGHIJKLMNOPQRSTUVWXYZABCDE

例：英文字母表q＝26，取k＝9，则有如下明文密文字母对应表。(a=0,…,z=25)明文：M＝multiplicativecipher密文：C＝EYVPUFVUSAPUHKSUFLKX

公元16世纪晚期，英国的菲利普斯(Philips)利用频度分析法成功破解苏格兰女王玛丽的密码信，信中策划暗杀英国女王伊丽莎白，这次解密将玛丽送上了断头台電影《伊莉莎白：輝煌年代》单表替代使其密文中单字母出现的频率分布与明文中的相同，因此任何单表替代密码都经不起统计分析。1917-1-17:齐默尔曼电报被“40号房间”截获。2月23日，密电揭开：德国将在1917年2月1日开始‘无限制潜艇战’，用潜艇攻击战时包括中立国在内的海上商运船为阻止美国参战，德国建议墨西哥入侵美国，并承诺帮助墨西哥从美国手中夺回得克萨斯、新墨西哥和亚利桑那三州德国还要墨西哥说服日本共同进攻美国，德国将提供军事和资金援助密电揭开后，美国在4月16日向德国宣战德国方面在一战结束十年之后才知道真相：1923年出版的温斯顿·丘吉尔的著作《世界危机》，提到了英俄在军事方面的合作，指出俄国人在一战中曾经成功地破译了某些德军密码齐默尔曼电报轮转密码机19世纪20年代，开始发明各种机械加密设备用来处理数据的加解密。起初普遍使用的是轮转机和轮转加密算法是由一个用于输入的键盘和一组转轮组成，每个轮转上有26个字母的任意组合。转轮之间由齿轮进行连接，当一个轮转转动时，可以将一个字母转化成为另一个字母262728德国的亚瑟·歇尔比乌斯（ArthurScherbius）发明了“谜”（ENIGMA，恩格玛密码机），用于军事和商业上。1925年，“谜”开始系列生产，在20年间，德国军方购入了3万多台“谜”，亦难倒了“40号房”，成为德国在二次大战的重要工具阿兰·图灵（AlanTuring）英国人

马里安·雷耶夫斯基（MarianRejewski）波兰人亚瑟·歇尔比乌斯（ArthurScherbius）德国人3031一台图灵“炸弹”高2m，长2m，宽1m。图灵的研究于1940年初完成，机器由英国塔布拉丁机械厂制造3233图灵（1912-1954），毕业于剑桥大学国王学院。是英国著名的数学家和逻辑学家，被称为计算机科学之父、人工智能之父，是计算机逻辑的奠基者，提出了“图灵机”和“图灵测试”等重要概念。人们为纪念其在计算机领域的卓越贡献而设立“图灵奖”34图灵奖获得者（部分）：2000年，姚期智(AndrewChi-ChihYao)：计算理论，包括伪随机数生成，密码学与通信复杂度2002年，RonaldRivest，AdiShamir，LenardM.Adleman：公钥密码学（RSA加密算法）2012年，ShafiGoldwasser，SilvioMicali：密码学和复杂理论领域2015年，WhitfieldDiffie，MartinHellman：非对称加密的创始人35图灵奖获得者（部分）：2012年，ShafiGoldwasser，SilvioMicali：密码学和复杂理论领域36其他转轮密码机：TYPEX打字密码机Hagelin（哈格林）密码机TUNNY密码机二战中，英国破解德国的ENIGMA密码机一事于1974年公开，此事件导致美国参战德国被迫用陆、海、空三军进攻英国在得知德军某精锐部队缺乏燃料且能源供给部队没跟上时，及时打击它37日美密码战：在第二次世界大战中，美国人破译了被称为“紫密”的日本“九七式”密码机密码。靠此珍珠港事件(1941年12月7日)中途岛事件(1942年6月3日)山本五十六之死事件(1943年4月18日)38

39

40置换密码体制置换加密（换位密码）：明文字符集保持不变，但顺序被打乱例：明文

COMPUTERGRAPHICSMAYBESLOWBUTATLEASTITSEXPENSIVECOMPUTERGRAPHICSMAYBESLOWBUTATLEASTITSEXPENSIVE

密文:CAELPOPSEEMHLANPIOSSUCWTITSBIVEMUTERATSGYAERBTX41例（深度为2的栅栏技术）：消息“meetmeafterthetogaparty”写出如下形式：

mematrhtgpryetefeteoaat密文是：MEMATRHTGPRYETEFETEOAAT4243逆序（倒序）密码Plain: SIMPLECIPHER

Cipher:REHPICELPMIS几何图形IcameIsawIconquered1949-1976：1949年Shannon（1916-2001，香农）发表《保密系统的信息理论》（“CommunicationTheoryofSecrecySystems”），产生了信息论标志着现代密码学的开始香农：1916-20011.现代密码学的发展44现代密码学1975--现代密码学的开端1975年，对计算机系统和网络进行加密的DES（DataEncryptionStandard，数据加密标准）由美国国家标准局NIST颁布为国家标准—密码学历史上的里程碑

1976年，美国斯坦福大学的Diffie和Hellman两人提出了公钥密码的新思想（密码学的新方向；NewDirectioninCryptography），把密钥分为加密公钥和解密私钥，是密码学的一场革命

1977年，美国的RonaldRivest、AdiShamir和LenAdleman提出第一个较完善的公钥密码体制——RSA体制，是建立在大数因子分解基础上的算法451997年美国国家标准局（NIST）发起征集高级数据加密标准（AES，AdvancedEncryptionStandard）的活动2000年10月，比利时密码学家JoanDaemen和VincentRijmen提出的“Rijndael数据加密算法”被确定为AES算法，作为新一代数据加密标准公钥密码领域，椭圆曲线密码体制ECC由于其安全性高、计算速度快等优点引起了人们的普遍关注和研究，并在公钥密码技术中取得重大进展新的密码技术不断涌现46密码学（Cryptology）：是结合数学、计算机科学、电子与通讯等诸多学科于一体的交叉学科，是研究信息系统安全保密的一门科学密码编码学（Cryptography）：研究密码编制的科学

密码分析学（Cryptanalysis）：研究密码破译的科学472.密码学基本概念密码体制，也称密码系统(Cryptosystem)，由五部分组成：明文空间M—全体明文的集合密文空间C—全体密文的集合密钥空间K—全体密钥的集合。其中每一个密钥K均由加密密钥Ke和解密密钥Kd组成，即K＝

Ke,Kd

加密算法E—一组由M到C的加密变换解密算法D—一组由C到M的解密变换48加密：E(P)=C解密：D(C)=P先加密，后解密：D(E(P))=PMessage45#￥%=-！~&*Message加密E解密D公共信道明文P明文P密文C49KdKe安全信道MCCM攻击者明文加密算法公共信道解密算法明文加密密钥解密密钥密钥K50科克霍夫原则（KerckhoffsPrinciple）：密码系统的安全性不应该取决于不易改变的算法，而应取决于可随时改变的密钥科克霍夫假设：密码分析者知道密码算法，唯一不知道的是密钥WHY？维护短的密钥比维护算法更容易；共享和安全存储短的密钥比共享和安全存储百千倍的程序更容易；算法的细节更容易泄露（逆向工程）一旦密钥泄露，更换密钥比更换算法更容易（定期密钥更新）多用户通信时，使用相同算法但不同的密钥比分别使用不同的算法更容易51密码体制的分类

对称密码体制序列密码分组密码公钥密码体制/非对称密码体制Hash函数+消息认证码MAC数字签名52对称密码体制（SymmetricKeyCryptosystem；单密码体制、传统密码体制）：如果一个密码体制的Kd＝Ke，或由其中一个很容易推出另一个。如同现实生活中的保密箱机制根据对明文和密文的处理方式和密钥的使用不同，可分为：分组密码（Blockcipher）

例如：DES、3DES、AES、IDEA、SMS4等序列密码（流密码，Streamcipher）

例如：RC4、A5、SEAL等5354AliceBobMessengerMessage45#￥%=-！~&*Message加密E解密D公共信道明文P明文P密文C使用一个密钥的加密/解密密钥k（Key）密钥k（Key）55密码分析

56C=E(K,M)Alice(Encrypter)Bob(Decrypter)Hecker(Attacker，Eve)攻击者通过搭线窃听、电磁窃听等方式获得信息（密文、部分明文等）57穷举攻击（强力或蛮力攻击，Bruteforce）：密码分析者采用依次试遍所有可能的密钥对所获密文进行解密，直至得到正确的明文变体：字典攻击统计分析：根据明文、密文和密钥的统计规律来破译密码的方法多适用于对称密码体制数学分析攻击：针对加解密算法的数学基础和某些密码学特性，通过数学求解的方法来破译密码多适用于公钥密码体制3.序列密码密钥流与密钥生成器密钥流算法应该能产生随机性和不可预测性好的密钥序列保持同步是序列密码在实际应用中的关键现实：密钥流都是按密钥生成算法生成，且要求通信双方能产生相同的密钥序列，所以不可能是真随机的——伪随机序列序列密码算法——RC4由MIT的RonRivest于1987年设计的、可变密钥长度、面向字节操作的、使用最为广泛的的序列密码之一；分析显示该密码的周期大于10100RC4目前使用中：SSL（安全套接字）中广泛使用WEPMicrosoftWindowsWPSOfficeMIT计算机科学系的教授，以及RSA数据安全公司的共同创始人耶鲁大学数学系获得学士学位斯坦福大学的计算机科学系获得博士学位在密码学、算法以及计算机和网络安全方面做出了突出贡献最重要的贡献是同AdiShamir和LeonardAdleman（MIT的教授）一起提出了RSA公钥算法，并且和Shamir、Adleman分享了2002年美国计算机协会(ACM)颁发的图灵奖美国国家工程院院士，美国国家科学院院士，美国计算机协会院士，国际密码研究学会院士，美国艺术与科学院院士4.分组密码算法——DES&AES对称密码学的不足1-密钥分配和管理AliceBob加密的消息Hecker(Attacker，Eve)我是黑客，看你怎么把密钥传递给Bob。哈哈！快把密钥传给我啊！急着哪！加密密钥如何传递给Bob哪？63

64

65对称加密体制的不足2—签名和认证问题对称密码体制中，通信双方共享密钥，因此接收方可以伪造原文—不能实现鉴别认证发送方也可以否认—不能实现不可否认性尤其在电子商务等网络应用中，互不认识的网络用户之间进行安全交易时，不能解决陌生人之间的身份认证和交易信息认证问题664.

公钥密码

公钥密码体制（PublicKeyCryptosystem；非对称密码体制、双钥密码体制）：如果在计算上Kd不能由Ke推出，这样将Ke公开也不会损害Kd的安全，于是便可将Ke公开典型的公钥密码体制有：RSAECCSMS2（我国标准，基于ECC）RabinElgamalNTRU6768Problem：如何安全的传递秘密文件？要求：Alice和Bob没有共享密钥AliceBob如何将包裹安全的传递给Bob哪???Messenger69AliceBobMessenger70AliceBobMessenger71AliceBobMessenger结论：现实生活中可以实现没有共享密钥的信息的安全传输但效率太低了（邮差需要来回3次）问题：

密码学中有没有办法实现没有共享密钥的加解密？

一定要以损失效率为代价吗？

Message45#￥%=-！~&*Message加密E解密D公共信道明文P明文P密文C使用两个密钥的加密/解密密钥k1（Key）密钥k2（Key）加密：E

(P)=C解密：D

(C)=P先加密，后解密：D

(E

(P))=P72公钥密码体制示意图发送方A查找接收方B的公钥A采用公钥加密算法以B的公钥加密明文消息A通过不安全信道将密文发送给BB收到密文后用自己的私钥解密获取明文73发送方A接收方B加密算法解密算法不安全信道B的公钥B的私钥密文明文明文74公钥密码（非对称密码）：每个用户都分别拥有两个密钥：加密密钥(公钥)与解密密钥(私钥)，两者并不相同，且由加密密钥得到解密密钥在计算上不可行。加密密钥是公开的类比：任何人只需按一下就可以把锁关上，但只有有钥匙的人才能把锁打开。关锁(加密)是容易的，人人都可以做到，但开锁(解密)只能由有钥匙的人来做。知道关锁的知识无助于开锁75Diffie-Hellman-Merkle76

世界著名的密码技术与安全技术专家，1991年加盟Sun公司，在Sun实验室工作此前，他曾在北方电讯任安全系统经理达20年之久“公钥加密”概念的发明人，被业界公认为信息技术安全事物的权威人士20世纪90年代，主要研究密码技术的公用策略方面，并多次在美国参议院和众议院作证Diffie是马可尼基金会(MarconiFoundation)成员，并且从许多机构--美国电气及电子工程师学会(IEEE)、电子前沿基金会(ElectronicFrontiersFoundation)、美国标准技术研究所(NIST)、美国国家安全局(NSA)、富兰克林研究所(FranklinInstitute)和美国计算机协会(ACM)--获得多种奖项WhitfieldDiffie77

1966年获得纽约大学学士学位1967和1969分别获得斯坦福大学的硕士和博士学位1968-69年IBM在华盛顿的研究中心1969-1971年MIT1971年斯坦福大学公钥密码学的创始人之一MartinE.Hellman公钥密码算法——RSA

78Diffie：1976年，我花一个小时时间完成这篇作品而一夜成名，从那时起，我就以此为生，这篇论文的影响非常巨大例

79例

80公钥密码算法——RSA81密码体制的分类

对称密码体制优点：速度快密钥较短密文往往与明文长度相同对称密码体制缺点：密钥分发需要安全通道密钥量大，难于管理难于解决不可否认问题公钥密码体制优点：密钥分发相对容易密钥管理简单可以实现数字签名公钥密码体制缺点：加解密速度慢密钥较长密文长度往往大于明文长度82混合密码体制明文生成随机对称密钥用对称密钥加密明文用公钥加密对称密钥公钥加密的对称密钥和Hash值对称密钥加密的消息公钥加密的对称密钥和Hash值对称密钥加密的消息用非对称加密的私钥解密对称密钥解密消息对称密钥明文8384混合加密AliceBobMessage两个问题：1.消息真的是来自Alice吗？2.我收到的消息真的是Alice发送的那个消息吗？Hecker(Attacker，Eve)我是黑客，我可以窃听、伪造、删除、修改和插入消息。小心喽！消息的完整性如何保证？5.Hash函数

messageHashfunctionHash函数的安全性

王小云的研究成果作为密码学领域的重大发现宣告了固若金汤的世界通行密码标准MD5大厦轰然倒塌，引发了密码学界的轩然大波会议总结报告写道：“我们该怎么办？MD5被重创了，它即将从应用中淘汰。SHA-1仍然活着，但也见到了它的末日。现在就得开始更换SHA-1了”（Wheredoesthisleaveus?MD5isfatallywounded;itsusewillbephasedout.SHA-1isstillalivebutthevulturesarecircling.AgradualtransitionawayfromSHA-1willnowstart.）中国科学院院士——王小云世界震惊:王小云破解全球两大密码算法2005年2月7日，NIST发表申明，SHA-1没有被攻破，并没有足够的理由怀疑它会很快被攻破，开发人员在2010年前应该转向更为安全的SHA-256和SHA-512算法而仅仅一周之后，王小云就宣布了破译SHA-1的消息。因为SHA-1在美国等国家有更加广泛的应用，密码被破的消息一出，在国际社会的反响可谓石破天惊2005年王小云在Crypto‘05会议上发表FindingCollisionsintheFullSHA-1,宣布了一种攻击方法，用269次操作找到两个独立的消息具有相同散列值换句话说，王小云的研究成果表明从理论上电子签名可以伪造NIST随即宣布废弃SHA-1的意图，到2010年转用其他版本的SHAHash函数的将来我国的Hash函数标准——SM3：杂凑函数标准类似于MD5，首先对消息分组为512bits，不够长则填充对每一个分组实施迭代运算输出256bit的消息摘要Hash函数的应用93手写签名:传统的确认方式，如书信、签约、支付、批复等在网络时代，人们通过网络支付费用、买卖股票，为了保证网上商务活动的安全，需要一个很重要的安全机制——数字签名6.数字签名AliceBob从我账户给Bob转入100万这么大一笔资金，这消息是Alice发的吗？要是过后Alice不承认这笔转账怎么办？Alice，把你要转账的消息签名之后再发给我消息的可靠性和不可否认性？数字签名的目的：保证信息的完整性和真实性，即消息没有被篡改，而且签名也没有被篡改，消息只能始发于所声称的一方一个完善的签名方案应满足以下三个条件：不可否认性：签名者事后不能否认或抵赖自己的签名不可伪造性：其他任何人均不能伪造签名，也不能对接收或发送的信息进行篡改、伪造和冒充公正的仲裁：若当事双方对签名真伪发生争执时，能通过公正的仲裁者验证签名来确定其真伪952024/4/19计算机科学与技术学院96RSA签名

97RSA签名方案图98

比较

Problem:为什么对消息的Hash函数值签名而不是直接对消息签名？99公钥加密通信存在的问题Alice→Bob：我叫Alice，我的公开密钥是Ka，你选择一个会话密钥K，用Ka加密后传送给我。Bob→Alice：使用Ka加密会话密钥K；Alice→Bob：使用K加密传输信息；Bob

→

Alice

：使用K加密传输信息。以上协议能否实现秘密通信？100中间人攻击

AliceBobMalloryKaKmEKm(K,Bob)EKa(K,Bob)101数字证书

用电子手段来证实一个用户的身份及用户对网络资源的访问权限，由认证中心（CertificateAuthority，CA）签发，主要用于数字签名的一个数据文件，它包含用户身份信息、用户公钥信息以及身份验证机构数字签名，即相当于一个网上身份证；从数字证书的作用来分：

1）签名证书

2）加密证书102ITU-TX.509标准。版本V3序列号1234567890签名算法标识（算法、参数）RSA和MD5签发者c=CN，o=JIT-CA有效期（起始日期、结束日期）01/08/00-01/08/07主体c=CN，o=SXCorp，cn=JohnDoe主体公钥信息（算法、参数、公开密钥）56af8dc3a4a785d6ff4/RSA/SHA发证者唯一标识符Value主体唯一标识符Value类型关键程度Value类型…ValueCA的数字签名104基于IBC的安全电子邮件系统使用公钥加密邮件“alice@”我是

“alice@”私钥master-keyCA/PKG基于标识（身份）的密码体制是否可以像PKI系统，由用户自己生成私钥？105秘密共享门限方案。取任何消息，并把它分成n部分，每部分叫做它的“影子”或共享，它们中的任何m部分能够用来重构消息