信息安全概论课件2

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,密码学根底,华中科技大学 刘开军,2 密码学根底,1.根本概念,明文,未经过处理的原始数据，可以是文本或图片等,密文,明文经过加密处理后所得的数据,加密算法和解密算法,加密和解密时使用的一组变换规那么，加密和解密过程都是在一组密钥的控制下进行的。,2 密码学根底,加密变换通常记为E，解密变换通常记为D.,记明文为X，密文为Y，那么密码系统的模型为：,2 密码学根底,一个密码系统或称密码体制由加密算法、解密算法、明文、密文、密钥加密和解密组成。,密码系统的平安性的根本在于密钥的平安性，加密和解密算法一般是公开的。,2 密码学根底,按执行的操作方式不同，可分为替换密码体制和换位密码体制；,按密钥数量不同，可分为对称密码体制又称为单钥密码体制、私钥密码体制和不对称密码体制又称为公钥密码体制、双钥密码体制。,对称密码体制又分成两类：流密码体制和分组密码体制。,2 密码学根底,对称密码体制的优点是：平安性高，加密速度快。缺点是：密钥管理困难；无法解决消息确认问题；缺乏自动检测密钥泄露的能力。,公钥体制的优点是：简化了密钥管理的问题，可以拥有数字签名等新功能。缺点是：算法一般比较复杂，加密速度慢。,2 密码学根底,密码分析的类型：,惟密文攻击,明文攻击,选择明文攻击,选择密文攻击,自适应选择明文攻击,选择密钥攻击,2 密码学根底,一个好的密码系统应满足以下要求：,破解的难度足够大；,保密性不能依赖于加密和解密算法；,加密和解密算法适用于密钥空间中的所有元素；,易于实现和使用。,2 密码学根底,2.传统密码及其破译,substitution cipher：,Simple substitution cipher;,Honophonic substitution cipher;,Polygram substitution cipher;,Polyalphabetic substitution cipher;,permutation cipher,2 密码学根底,单字母密码体制例如：,例如，明文=important，密钥Key=3;,构造密文字母表,计算密文,明文：important,密文：LPSRUWDQW,明,a,b,c,d,e,f,密,D,E,F,G,H,I,2 密码学根底,Vigenere cipher(polyalphabetic substitution cipher),明文：,密钥：,密文：,其中,2 密码学根底,Permutation cipher:,例如：,明文=it can allow students to get close up views,密钥=5.,将明文字母重排,itcan,allow,stude,ntsto,计算密文.密文=IA SNG OVTLT.,2 密码学根底,这些传统密码体制出现在计算机创造之前，只对英文字母进行加密。破解的方法主要是利用英文的行文规律和字母统计特征，例如字母出现的频度、重复字母的模式和字母组合模式等。,据统计：英文字母e出现的频率为0.127，为最高，其次依次为t 0.091,a 0.082,o 0.075,n 0.067,r 0.060,简单替代密码体制最容易破解，多表代替密码最难破解。成功的密码破解过程通常需要破解者根据具体情况边分析边破解。,2 密码学根底,3.保密系统理论,在保密系统中，发送者信源要将明文数据m通过一个公开的信道传输给接受者。为了防止外界的分析者通过信道窃取到传输的数据，发送者会先加密明文，在信道中传输密文，接受者解密密文得到明文。,一个保密系统由明文空间P、密文空间C、密钥空间K、加密算法E、解密算法D组成，通常记为(P,C,K,E,D)。,保密系统的模型,2 密码学根底,2 密码学根底,2 密码学根底,2 密码学根底,在分析Shannon保密系统模型时，通常假定信道是无干扰的，合法的接受者能够从密文中得到原来的明文。,另一个重要的假设是Kerchhoffs假设，即假设密码分析者知道明文的统计特性、加密体制即加密解密算法、密钥空间及其统计特性。密码分析者不知道通信双方使用的密钥，也不知道或不确知密钥的长度。,2 密码学根底,衡量一个保密系统的平安性有两种方法：,计算平安性实际保密性,如果利用最好的算法的或未知的破译某个密码系统需要至少N一个很大的数次运算，就称该系统是计算上平安的。,目前实际所说的“计算平安性密码系统指的是：利用已有的最好的方法破译该密码系统所需要的努力超出了破译者的破译能力诸如时间、空间、资金等，或者破译该密码系统的难度等价于解数学上的某个难题。,2 密码学根底,无条件平安性完善保密性,如果具有计算资源诸如时间、空间、资金、设备等的密码分析者也无法破译某个密码系统，那么称该系统为无条件平安的。,无条件平安性是保密系统的最高目标，在理论研究上有重要价值。,2 密码学根底,无条件平安保密系统的充分条件：,定理 一个保密系统(P,C,K,E,D)称为完善的无条件保密系统，如果H(P)=H(P|C).,无条件平安保密系统的必要条件：,定理 如果一个保密系统是无条件平安的，那么有H(P)H(K).,2 密码学根底,目前商业上使用的保密系统都是计算上平安的，唯一的无条件平安的保密系统是“一次一密密码(one-time pad cipher)，并不实用。,在实际中，人们设计一个保密系统的目标是希望用一个密钥能用来加密一条相对长的明文串也就是一个密钥能用来加密许多消息，并且至少是计算上平安的。,2 密码学根底,对计算上平安的保密系统，理论上总是可以破解的。当密码分析者截获密文c时，他可以用所有的密钥对其进行解密，得到一个明文集m=Dk(c),kK。在这个集合中，筛选出有意义的明文，并记下对应的密钥。这些密钥通常有多个，但只有一个是正确的密钥，其他的密钥称为伪密钥。,显然，对一个保密系统来说，伪密钥数量越多，破解越困难。在设计保密系统时，应该使伪密钥的期望数的下界尽可能大。,2 密码学根底,2 密码学根底,伪密钥的期望数下界：,定理 假定(P,C,K,E,D)是一个保密系统，|C|=|P|。设RL表示明文自然语言的多余度，那么给定一个充分长长度为n的密文串，伪密钥的期望数Sn满足：,2 密码学根底,一个保密系统的唯一解距离定义为使得伪密钥的期望数等于零的值，记为n0，那么,当截获的密文量大于n0时，原那么上可以破译该密码。当然n0只是一个理论值，一般破译密码需要的密文量远大于n0,2 密码学根底,4.认证系统理论,认证系统的目的是能使发送者通过一个公开的无干扰信道将数据传输给接收者，接收者不仅能收到数据本身，还能验证数据是否来自发送者、是否被入侵者窜改正。,与保密系统不同，认证系统是要防止外界的主动攻击。,2 密码学根底,目前研究的认证模型主要有两种：,无仲裁者的认证系统模型,只有三个参与者：发送者、接收者和入侵者。发送者和接收者相互信任。,有仲裁者的认证系统,有四个参与者：发送者、接收者、入侵者和仲裁者。发送者和接收者相互不信任，但他们都信任仲裁者，仲裁者负责所有的秘密信息并且不能进行欺诈。,无仲裁者的认证系统的模型,2 密码学根底,在认证系统中发送数据的协议是：,发送者和接收者共同选择一个随机密钥k,发送者计算要发送的信源s的认证标签a=ek(s),发送者发送消息(s,a)给接收者,当接收者收到消息(s,a)时，计算a=ek(s)。如果a=a，那么这个消息作为真消息接收；否那么拒绝接收。,2 密码学根底,一个无分裂、没有保密功能的、无仲裁的认证系统可以用(S,A,K,)来描述：,S是所有可能的信源状态构成的有限集，称为信源集；,A是所有可能的认证标签组成的有限集；,K是所有可能的密钥组成的有限集；,称为认证码，是一个算法规那么。对每一个密钥k，信源状态s的认证标签为,2 密码学根底,外界入侵者攻击认证系统时，通常是先观察发送者发出的,r,组消息，分析出关于认证码和密钥的一些信息，然后伪造假消息，希望接收者接受它，我们称这种攻击为,r,阶欺骗攻击。,0阶欺骗攻击称为模仿攻击，1阶欺骗攻击称为代替攻击。这里我们只讨论这两种攻击方式。在一个设计良好的认证系统中，入侵者用模拟攻击和代替攻击成功的概率应尽可能小。,2 密码学根底,设pd0表示入侵者采用模拟攻击时成功的最大概率，设pd1表示入侵者采用代替攻击时成功的最大概率，那么入侵者欺骗成功的概率定义为：,pd=maxpd0,pd1,假设入侵者知道S、K及其概率分布、认证码，但不知道密钥。,2 密码学根底,2 密码学根底,2 密码学根底,2 密码学根底,在得到pd0和pd1后，就可以计算得到入侵者攻击成功的概率为：,pd=max pd0,pd1,模拟攻击成功的概率的下界：,定理：设(S,A,K,)是一个认证系统，那么,pd02 H(K|M)-H(K),这个定理说明，任何认证系统都存在被攻击成功的可能，不存在绝对平安的认证系统。,2 密码学根底,认证系统的平安性与保密系统的平安性一样可分为两类：无条件理论平安性和实际平安性。,实际平安性又可分为：计算平安性和可证明平安性。,2 密码学根底,5.复杂性理论,多项式时间复杂性,指数时间复杂性,NP问题,NP Complete问题,2 密码学根底,