第二章-密码体系

密码学基础预备知识和先修课程基础知识方面：数论、组合数学、概率论、信息论数字信号处理、复杂性理论网络通信体系与协议动手方面：协议，系统设计和实现编程语言综合方面获取知识的能力综合分析和应用的能力课程的主要内容及安排第一部分：基本概念第二部分：经典密码体制第三部分：现代密码基础第四部分：发展趋势第五部分：密码算法应用问题复习讨论：主要线索基本理论：第一部分基本方法：第二—第四部分面临的挑战：第五部分学习方法和要求学习方法：课堂+动手学习目标要求：密码学的基本原理、准则、技术、及最新研究成果密码学的理论基础和基本实践能力有关密码算法应用的背景知识课堂要求遵守课堂纪律做笔记素质要求政治素质专业素质相关课程•密码学基础：经典密码、现代密码、密钥管理技术•认证理论与技术：身份鉴别和访问控制、数字签名、审计技术•系统安全：防火墙技术、操作系统的安全、病毒•网络安全：安全协议、电子邮件、IP、Web、扫描、攻击、入侵检测•专题接下来主要内容密码学的背景—现实与历史基本概念和术语保密理论破译理论密码学的发展现在的背景-1保密与安全随着计算机的广泛使用，尤其是internet的出现与发展，信息安全受到越来越多人的关注，象社会安全和经济安全等一样作为国家安全的重要组成部份，各国政府都予以高度重视发达国家和地区投入巨资来保护其信息基础建设的安全，增强其综合实力在一些发展中国家（如中国），则更多地依赖于国家政策，来维护自身的信息安全现在的背景-2然而，全球一体化的经济和科技的发展，使得国与国，人与人之间有了更加紧密的依靠和渗透当前国际形势复杂多变，世界范围内黑客对计算机网络的攻击与破坏活动日趋猖獗，一些发达国家正在利用其信息技术、经济和军事优势来达到称霸世界的目的为了更快地发展我国的经济、增强综合国力，维护国家和世界的和平，我们自然不能袖手旁观关注焦点•目前在信息安全领域的关注焦点：⒈密码理论与技术；⒉安全协议理论与技术；⒊安全体系结构理论与技术；⒋信息保障体系⒌信息对抗理论与技术；⒍安全产品。历史背景-1一开始人就具备保守秘密的本能。这是一种很自然的人类行为。这些秘密要么只能由自己掌握，要么由自己和自己允许的人掌握。要想保密，最简单的做法就是不把它告诉别人。在远古，只有少数人才有读书、写字的特权十六世纪以前，秘密书写方法－隐匿法(隐藏讯息本身)与密码法(隐藏讯息意义)自凯撒大帝的年代开始，一直到当代，通信技术在稳步地发展着。从纸张到电报、电传、电话、传真以及E-mail，人和人之间的通信变得如此方便和普遍。与此同时，保障这些通信的安全也逐渐成为一项重要课题。历史背景-2密码学真正成为科学是在19世纪末和20世纪初期，特别是两次世界大战中对军事信息保密传递和破获敌方信息的需求，密码学得到了空前的发展，并广泛的用于军事情报部门的决策在希特勒一上台时，德国就试验并使用了一种命名为“谜”的密码机，“谜”型机能产生220亿种不同的密钥组合，假如一个人日夜不停地工作，每分钟测试一种密钥的话，需要约4.2万年才能将所有的密钥可能组合试完，希特勒完全相信了这种密码机的安全性。然而，英国获知了“谜”型机的密码原理，完成了一部针对“谜”型机的绰号叫“炸弹”的密码破译机，每秒钟可处理2000个字符，它几乎可以破译截获德国的所有情报。后来又研制出一种每秒钟可处理5000个字符的“巨人”型密码破译机并投入使用，至此同盟国几乎掌握了德国纳粹的绝大多数军事秘密和机密，而德国军方却对此一无所知太平洋战争中，美军成功破译了日本海军的密码机，读懂了日本舰队司令官山本五十六发给各指挥官的命令，在中途岛彻底击溃了日本海军，击毙了山本五十六，导致了太平洋战争的决定性转折因此，可以说，密码学为战争的胜利立了大功。密码从军事走向生活应用领域--军事，外交，商业，个人通信，古文化研究等目前，应用重点已经更多的集中在实际应用在生活中有越来越多使用密码的例子。随着科技的发展和信息保密的需求，密码学的应用已融入了日常生活密码学的新问题：信息安全的概念的演变通信保密(COMSEC)：60-70年代信息保密信息安全(INFOSEC)：80-90年代机密性、完整性、可用性、不可否认性等信息保障(IA)：90年代-为什么需要密码?信息的存储：在公开的地方信息的交换：使用非隐秘介质信息的传输：通过不安全信道威胁和防护窃密----保密(数据加密)冒名----身份鉴别抵赖----不可否认性(数字签名)篡改----完整性控制保护与破坏要保护什么？数据(机密、完整、独占)资源身份破坏的方式系统入侵恶意破坏资料窃取现有技术手段加密访问控制，加强网络管理（帐号、口令等）审计防火墙入侵检测其他密码学的基本概念密码学(Cryptology)：是研究信息保密的科学密码编码学(Cryptography)：主要研究对信息进行编码，实现对信息意义的隐蔽密码分析学(Cryptanalytics)：主要研究加密消息的破译或消息的伪造密码学基本术语明文(Plaintext)、密文(Ciphertext)加密(Encryption)、解密(Decryption)密码算法(CryptographyAlgorithm)加密算法(EncryptionAlgorithm)解密算法(DecryptionAlgorithm)密钥(key)密码体制—基本定义密码体制：是一个五元组(P,C,K,E,D)1.P是可能明文的有限集：明文空间2.C是可能密文的有限集：密文空间3.K是一切可能密钥构成的有限集：密钥空间4.任意k∈K，有一个加密算法ek∈E，使得ek：PC：加密变换族(Ek)5.相应的解密算法dk∈D，dk：CP分别为加密解密函数，满足dk(ek(x))=x(这里x∈P)：解密变换族(Dk)密码体制的一般性要求进行明密变换的法则，称为密码的体制。指示这种变换的参数，称为密钥密码体制必须满足以下三个一般性要求：加解密变换对所有密钥都有效—必须；体制必须是简单易行的—易于找到密钥用于逆变换；体制的安全性仅依赖于密钥的保密而不能依靠算法的保密—加解密算法强度。密码算法的安全性要求—保密性EkDkCMMM不容许的保密性要求受保护的解密：不能被破译的EkDkCMM’M不容许的可靠性要求受保护的C’‘密码算法的安全性要求—可靠性加密：不能被伪造的关于密码算法保密性的一般理论理论基础：信息论安全性定义安全性的一般要求唯一解距离五项准则最坏情况假定加密通信的模型密码学的目的：A和B两个人在不安全的信道上进行通信，使破译者O不能理解他们通信的内容A加密机解密机B安全信道密钥源Oxyxkk熵与暧昧度1949年，Shannon以其在信息论方面的基本著作为依据，为密码学提供了理论基础。依据已经收到的密文来得到的明文的不确定性，来度量密码在理论上的保密度。如果不论截取了多少密文，对明文仍然一无所知，则此密码达到完全保密密码算法的安全性无条件安全(Unconditionallysecure)一次一密(Onetimepad)计算上安全(Computationallysecure)破译的代价超出信息本身的价值破译的时间超出了信息的有效期保密度Shannon根据对一给定密文C，密钥K的熵HC(K)来度量密码的保密度，即：对于给定的C，K的不确定度如果Hc(K)=0，则没有不确定度，只要有足够的资源，密码在理论上是可破的。当密文长度N增加时，暧昧度通常下降唯一解距离唯一解距就是使Hc(K)0的最小N，即要唯一确定密钥所必须要的最短密文长度。如果对于很长的N，Hc(K)也用不趋于0，则密码就是绝对安全的，Shannon曾用理想保密一词来描述。也就是说，无论截取多少密文，也确定不了密钥实际安全只要有数百bit明文，大多数密码在理论上是可破的。但，这并不意味着这些密码不安全，因为，要确定明文在计算上的耗费，可能会超过可利用的资源。因此，重要的问题，不在于密码是否绝对安全，而是计算上是否安全完全保密M1M2M3M4C1C2C3C4明文消息密文消息完全保密的例子：pc(M)=p(M)=1/4，pM(C)=p(C)=1/4密钥1234234134124123Shannon的五项准则Shannon于1940年代提出了关于密码体制的著名五项准则保密量密钥的规模加解密运算的简易性错误的扩张消息的扩张最坏情况的条件Shannon的最坏情况条件是：C1：密码分析者具有该密码体制的全部知识C2：密码分析者已得到相当数量的密文C3：密码分析者知道一定数量的，与密文对应的等价明文后续内容破译理论破译历史编码历史破译理论所有现用密码都会在密文中留下一些有关明文的信息(唯一例外)。随着密文长度的增加，明文的不确定性通常会下降，最后到零，此时意味着，有足够的信息来唯一的确定明文，这样，此密码至少在理论上是可破的密码破译术语如果有可能从密文或明密对应文中确定明文或密钥，该密码就是可破的(Breakable)。如果无论截获多少密文，都没有足够信息来唯一确定明文，则该密码是无条件安全的(UnconditionallySecure)。如果使用有效资源对一个密码系统进行分析而未能破译，则称该密码是强的或计算上安全的(ComputationallySecure)密码分析的条件和类型假设破译者O是在已知密码体制的前提下来破译B使用的密钥。这个假设称为Kerckhoff原则。最常见的破解类型如下：唯密文攻击：O具有密文串y。已知明文攻击：O具有明文串x和相应的密文y。选择明文攻击：O可获得对加密机的暂时访问，因此他能选择明文串x并构造出相应的密文串y。选择密文攻击：O可暂时接近密码机,可选择密文串y，并构造出相应的明文x。这一切的目的在于破译出密钥或密文密码破译方法密码破译的基础条件：所有自然语言都有很高的多余度破译原则：遵循观察与经验破译方法：采用归纳与演绎破译步骤：分析、假设、推测和证实古典密码破译方法举例统计密码分析举例--(英文语言)三大要素：语言的频率特征：e连接特征：q,…u,I,e,x,重复特征：th,tion,tious密码破译的发展-1密码破译是随着密码的使用而逐步产生和发展的1412年，波斯人卡勒卡尚迪所编的百科全书中载有破译简单代替密码的方法到16世纪末期，欧洲一些国家设有专职的破译人员，以破译截获的密信。密码破译技术有了相当的发展1863年普鲁士人卡西斯基所著《密码和破译技术》，以及1883年法国人克尔克霍夫所著《军事密码学》等著作，都对密码学的理论和方法做过一些论述和探讨1949年美国人Shannon发表了《秘密体制的通信理论》一文，应用信息论的原理分析了密码学中的一些基本问题密码破译理论的发展-2手工密码的破译：概率论的应用机械密码的破译现代密码的破译：近世代数理论的应用移位寄存器理论的应用背包体制。。。非线性系统理论的应用数学难解性问题—非对称密码计算机及网络的利用—大规模并行处理密码编码的发展-1从密码学发展历程来看，按信息特点，可分为古典密码(以字符为基本加密单元的密码)，以及现代密码(以信息块为基本加密单元的密码)两类，或者按算法的密钥是否可以公开，分为对称密码和非对称密码两类或者按经过算法处理后是否可以还原，分为加解密算法和摘要算法两类密码编码的起源-1可追溯到人类刚刚出现，并且尝试去学习如何通信的时候，为了确保他们的通信的机密，最先是有意识的使用一些简单的方法来加密信息，通过一些(密码)象形文字相互传达信息由于文字的出现和使用，确保通信的机密性就成为一种艺术，古代发明了不少加密信息和传达信息的方法例如我国古代的烽火就是一种传递军情的方法，再如古代的兵符就是用来传达信息的密令就连闯荡江湖的侠士，都有秘密的黑道行话，更何况是那些不堪忍受压迫义士在秘密起义前进行地下联络