现代密码学理论与实践概述

1现代密码学理论与实践第一章密码学概述林喜军linxj77@163.com2学习密码学有什么用？学习网络安全应该具备一定的密码学知识仅使用计算机学科的方法无法满足某些安全需求密码学提供了丰富多彩的安全保护手段，可以满足不同的安全需求3实际应用密码技术的领域电子商务、电子政务智能卡3G通信

……影视作品中的密码学4图灵奖历史上的密码学家5获得时间获奖者获奖原因1995M.Blum计算复杂度理论，及其在密码学和程序校验上的应用2000Andrew.C.C.Yao计算理论，包括伪随机数生成，密码学与通信复杂度2002R.L.Rivest

A.Shamir

L.M.Adleman公钥密码学（RSA加密算法）2012S.Goldwasser

S.Micali在密码科学领域里，于计算复杂理论的基础之上，做出变革性工作；并率先发展出新的具有数学可证明安全性的有效机制6教学目标掌握密码学的基本知识和基本原理了解密码技术的应用了解密码学的发展动态7参考文献ModernCryptography:Theory&PracticebyWenboMao

(强烈推荐)

中文版网上可以下载8参考文献(续)HandbookofAppliedCryptographybyA.Menezesetal.(强烈推荐)

网上可以下载9参考文献(续)应用密码学

byB.Schneier

(内容广泛、不够详细，适合当字典用)

网上可以下载10参考文献(续)LectureNotesonCryptographybyS.GoldwasserM.Bellare(高级读物)

麻省理工学院密码学讲义

网上可以下载11参考文献(续)FoundationsofCryprography：BasicTools

byO.Goldreich

(高级读物)

网上可以下载12密码学概述古典密码学对称密码学Hash函数与消息认证现代密码学的理论基础公钥密码学数字签名椭圆曲线与基于身份的密码学安全协议密码学发展动态授课内容重点：2—9章13第一章密码学概述1.1密码学简介1.2密码学发展史1.3关于密码分析的几点说明141.1密码学简介密码学是信息安全的重要组成部分信息安全三要素机密性完整性可用性15机密性确保信息不被非法获取常见威胁窃听盗窃文件社会工程学

……16完整性确保系统或数据被恶意篡改后，我们能够发现导致破坏完整性的原因：合法用户的失误非法用户的篡改17可用性确保系统以足够的能力、预期的方式、可接受的性能提供服务导致破坏可用性的原因设备故障软件错误环境因素人为攻击典型代表：DoS攻击(拒绝服务攻击)18两种攻击形式被动攻击对机密性的破坏主动攻击对完整性和可用性的破坏19攻击者的基本行为窃听-被动攻击攻击者偷看到了Bob发送的信息20攻击者的基本行为(续)篡改-主动攻击攻击者修改了Bob发送的信息21攻击者的基本行为(续)假冒-主动攻击攻击者冒充Bob，与Alice通信22

密码学的主要功能保证机密性防范信息泄露保证完整性防范信息被篡改后，我们还被蒙在鼓里提供非否认服务防范抵赖(否认自己干过的事)23什么是密码学研究内容研究秘密通信组成部分密码编码学研究如何设计密码，以保证信息的安全密码分析学研究如何破译密码(是一把双刃剑)帮助分析密码算法的安全性帮助非法窃取受保护的信息等破坏性工作24密码学的基本术语明文：需要保护的信息加密：隐藏信息的过程密文：加密后的明文解密：从密文恢复出明文的过程密码分析：对密码进行破译的过程25加密E(·)解密D(·)密钥K明文M明文M密文C密钥K安全信道加密：EK(M)=C解密：DK(C)=M=>DK(EK(M))=M秘密通信模型破译AliceBob26需要区别的两个常用术语口令(password)用于“身份认证”——确认对方是否是你要通信的对象通常选择一些容易记忆，又不易被别人猜到的字符串密钥(key)用于“变换明/密文”——作为加解密算法的辅助输入，以保护明文或解密密文通常选择一些随机串27密钥的必要性加解密的时候，为什么需要密钥？为什么不构造一个不需要密钥的密码算法？如果没有密钥，当攻击者知道了算法，他们只需执行该算法就可以恢复你的明文。貌似保密密码算法就可以解决这个问题。事实上，攻击者总能通过各种手段发现你用的是哪个算法。28密码学的基本原则——

柯克霍夫斯原则柯克霍夫斯原则即使密码算法的任何细节已为人所知，只要密钥没有泄漏，它也应该是安全的。另一种表述密码算法的安全性是基于密钥的安全性，而不是基于保密算法的细节。AugusteKerckhoffs1835–1903荷兰语言学家、密码学家29柯克霍夫斯原则的意义何在？意义在于，密码算法很难做到保密知道算法的人可能会叛变——历史上这种事屡见不鲜设计者有个人喜好频繁更换密钥是可能的，但无法频繁更换密码算法(因为设计安全的密码算法相当困难)30密码体制的形式化描述它是一个五元组

(P,C,K,E,D)P(明文空间)：所有可能的明文组成的有限集C(密文空间)：所有可能的密文组成的有限集K(密钥空间)：所有可能的密钥组成的有限集E：所有加密算法组成的有限集D：所有解密算法组成的有限集31注意加密算法(函数)必须是一个单射函数Why?32加密函数不是单射会怎么样？Ek(·)Dk(·)明文空间密文空间x1x2y加密：y=Ek(x1)=Ek(x2)解密：无法判断y究竟还原为x1还是x2DK(y)?=x1?=x2?33怎样的加密体制才算是实用的？必须满足以下两条：容易性：加密函数、解密函数都应该易于计算安全性：对于任何攻击者，即使获得了密文，也不可能恢复出明文、所用的密钥。341.2密码学发展史密码学的发展历程大致经历了三个阶段：古代加密方法（手工阶段）古典密码（机械阶段）现代密码（计算机阶段）

35(1)古代加密方法阶段存于石刻或史书中的记载表明，许多古代文明，包括埃及人、希伯来人、亚述人都在实践中逐步发明了密码系统。从某种意义上说，战争是科学技术进步的催化剂。自从有了战争，人类就面临着通信安全的需求，使得密码技术源远流长。

(密码最早应用于军事和政治领域)36需要区别的两种技术隐写术加密术37隐写术——洋葱法、隐写墨水等38隐写术——剃头，写字，等头发变长39隐写术——情报传递(近现代仍在使用)传递情报用的火柴盒隐写术——藏头/藏尾诗(文章)我康宣，今年一十八岁，姑苏人氏，身家清白，素无过犯。只为家况清贫，鬻身华相府中，充当书僮。身价银五十两，自秋节起，暂存账房，俟三年后支取，从此承值书房，每日焚香扫地，洗砚、磨墨等事，听凭使唤。从头做起。立此契为凭。4041隐写术小结特点：保护的是信息本身(把信息隐藏起来)。缺点：一旦发现隐藏的方法，信息就会暴露。洋葱法——

用火烤古希腊的剃头方法——

把可疑的人剃成秃瓢情报传递——

检查任何可疑的东西，看是否有夹带藏头诗等——

检查诗词的开头和结尾42加密术使用的两种基本技术置换

(易位)代换(替换、代替)43加密术——置换公元前400年，斯巴达人使用的加密工具——Scytale44置换的特点明文中的字符与密文中的相同只是出现的位置发生了变化置换密码的密钥是什么？改变位置的规则45加密术——代换用一张(或多张)代换表，表示明文字母与密文字母的对应关系明文字母：abcdefghijklmnopqrstuvwxyz

密文字母：XZJGLIFKHQNOPMASUTCWDYERBV加密和解密要参照代换表的对应关系

例：

明文：cryptography

密文：JTBSWAFTXSKB46代换的特点明文中出现的字母不一定出现在密文中代换密码的密钥是什么？代换表47加密术小结特点：保护的是信息的内容。不知道密钥，很难恢复出信息。隐写术与加密术的区别隐写术：传递的仍是原来的信息，只是被藏了起来加密术：传递的不是原来的信息(明文)，而是变换后的信息(密文)。实际上，密文携带了明文的信息。48(2)古典密码阶段虽然名字叫“古典密码”，但在近代得到广泛发展和应用古典密码系统已经初步体现出现代密码系统的雏形，它比古代加密方法更复杂。加密方法一般是对文字（字符）的变换使用手工或机械变换的方式实现古典密码的典型代表：单表代换密码、多表代换密码、转轮机密码

(在近代，密码已应用到商业领域)49(3)现代密码阶段密码是非常古老的技术，但真正形成学科还是20世纪70年代的事，这是受计算机科学蓬勃发展的刺激和推动的结果。计算机和电子时代的到来，使得密码设计者轻易摆脱了原先手工设计时易犯的错误，也不用再面对用电子机械方式实现的密码机的高额费用。快速计算机和现代数学，为密码技术提供了新的概念和工具，也给攻击者提供了有力武器。总之，利用计算机可以设计出更为复杂的密码系统。攻击者也可以利用计算机快速破解密码系统。50在这一阶段，密码理论蓬勃发展，密码算法的设计与分析互相促进，出现了大量的密码算法和各种攻击方法。密码技术的应用范围也在不断扩展，出现了许多通用的密码标准(DES、AES、DSS)，促进了网络和技术的不断发展。51密码学史上的重要事件1949年，香农发表论文《保密系统的通信原理》它是密码学的理论基础之一发表30年后才显示出它的价值。1976年，Diffie、Hellman发表论文《密码学的新方向》提出适应网络上保密通信的公钥密码的思想开辟了公钥密码学的新领域可以这么说:“没有公钥密码的研究就没有现代密码学”52密码学史上的重要事件(续)1978年，RSA密码体制出现它是公钥密码领域最杰出的代表，成为事实上的标准，是密码学史上的里程碑1978年，DES(数据加密标准)出现NBS(美国国家标准局,即现在的国家标准与技术研究所NIST)公布美国的数据加密标准,公开它的具体算法，并被用于政府等非机密单位及商业上的保密通信。上述两篇论文和DES的实施，标志密码学理论与技术的革命性变革，宣布了现代密码学的开始。531.3关于密码分析的几点说明密码分析的分类方法：分类依据：攻击者知道信息的多少唯密文攻击：手头只有一些密文，好的现代密码系统对此攻击通常是免疫的。已知明文攻击：已有很多明文/密文对。选择明文攻击：可以任意选择明文，并可获得相应密文。选择密文攻击：可以任意选择密文，并可获得相应明文。

(上述四种方法的攻击强度依次增强)54在实际应用中，破译工作通常是多项技术综合应用的结果下面就这个问题做几点说明.55密码设计vs.密码实现即使图纸上设计完美的楼房，施工的时候不注意，也会变成豆腐渣工程但这与设计本身无关，完全是施工造成的密码也是一样，一个设计上安全的密码算法，在实现时也会引入安全漏洞但这与算法的设计无关，完全是程序编码造成的在本课程中，主要讨论针对算法设计的攻击，而不去涉及算法实现的问题。56恢复明文vs.恢复密钥破译的主要目的在于恢复密钥因为知道了密钥，便可恢复出该密钥加密的所有明文一个安全的密码体制要求：通过密文计算密钥，至少要和计算明文一样困难当然有些时候，破译的目的也在于恢复特定的明文57全部破译vs.部分破译并不一定恢复出整个明文才算成功破译有时候，恢复出明文的部分信息，甚至几个关键单词，也算成功破译。部分破译又往往成为全部破译的突破口在实际应用中，破译往往需要综合多项技术和多方面的信息。58综合破译举例——池步洲生于福建省闽清县。由于家境贫寒，直到10岁才上学，却用3年时间完成全部小学课程。此后考入福州英华书院（今福建师范大学附属中学）。后留学日本，并考入早稻田大学。抗战爆发后，回国抗日。经同学介绍加入中统，他是当时中统内唯一的留日学生。尽管没学过密码破译，却用统计、大胆猜测，以及自己对日本的了解，发现了日军密码的缺陷，破译了大量日军密电珍珠港事件：东风，有雨击毙山本五十六

…1908—20