第7章密码体制的安全性测度课件.ppt

1、1第第7 7章章 密码体制的安全性测度密码体制的安全性测度n7.1 密码基本知识密码基本知识n7.2 古典密码体制n7.3 现代密码体制n7.4 密码体制的安全性测度27.1 7.1 密码基本知识密码基本知识n1949年，香农发表了论文“密码体制的通信理论”n利用数学方法对信息源、密钥源、接收和截获的密文进行了数学描述和定量分析，提出了通用的密钥密码体制模型，奠定了现代密码学的基础。3密码技术的发展史n1.隐写术和手工密码变换：代替和换位n2.1920年，弗纳姆密码：自动加解密的诞生n3.二战时0075密码本：非对称密码的萌芽n4.1975年，DES诞生：现代分组码形成n5.1976年，RSA

2、密码诞生：公钥密码概念被提出4密码体制n1.密码学：密码编码学和密码分析学。n2.密码体制：它是一组规则、算法、函数或程序，使保密通信双方能够正确的、容易的进行加密和解密，包括密码算法、明文、密文和密钥。n3.保密通信系统：由密码体制、信源、信宿和攻击者构成5加解密在信息传输系统模型中信源信源编码信源译码信宿信道编码信道信道译码+加密编码解密译码噪声源SUCXYVSn6保密通信系统模型7密码体制的组成n1.明文空间Pn2.密文空间Cn3.密钥空间K：包括加密密钥ke和解密密钥kdn4.加密算法E：加密变换的集合n5.解密算法D：解密变换的集合PcDpCpEckkkCcPpdekkde)(,)(

3、)(是一个密钥，则，为密文，为明文，设8密码体制n什么是好的密码体制？n1.已知密文和加密密钥时，计算密文很容易；n2.在不知道解密密钥时，由密文推知明文相当困难；n密码算法的安全等级n1.无条件安全：也叫理论安全n2.计算安全：也叫实际安全9密码分析攻击（六种）n密码分析攻击是指在不知道密钥的情况下，利用密码体制的弱点，恢复出明文或密钥：n1.唯密文攻击；n2.已知明文攻击；n3.选择明文攻击；n4.自适应选择明文攻击；n5.选择密文攻击；n6.选择密钥攻击；10第第7 7章章 密码体制的安全性测度密码体制的安全性测度n7.1 密码基本知识n7.2 古典密码体制古典密码体制n7.3 现代密码

4、体制n7.4 密码体制的安全性测度11古典密码体制n作为密码学发展的初级阶段，古典密码简单、安全性，一般都采用替代和置换的方法n替代：将明文中的字母用其它字母、数字或符号进行取代；替代算法就是密钥。n置换：也叫换位，明文的字母保持不变，但是顺序被打乱了。n古典密码分为三类：单表密码、多表密码和多字母代换密码（即换位密码）12古典密码的分类n1.单表密码单表密码对明文中所有的字母都使用同一个映射，并且映射是一一对应的。n1.凯撒（Caesar）密码：将明文中每个字母用字母后面的第三个字母进行代替。n2.使用密码词（组）的单表代替密码：使用一个单词或词组，去掉重复字母作为密钥，再将字母表中其它字母

5、置于密钥之后，构造出字母替代表。13古典密码的分类n2.多表密码n单表密码的缺陷是明文中单个字母的概率分布与密文的相同。多表密码使用多个映射来隐藏单字母的出现频率，但是每个映射仍然是一对一映射。多表密码将明文字符划分为长度相同的消息单元，即明文组，对同一明文分组中不同位置的字母进行不同的代替，即相当于使用了多张字母代替表，当然它也可以对不同明文组进行不同的代替，从而使同一个字符对应不同的密文，改变了单表密码中密文与明文字母的唯一对应性。147.2.2多表密码普莱费尔密码定的某个字母。，则在明文末端添加约若明文字母个数为奇数，并用前述方法处理；的字母于重复字母之间，则插入一个事先约定若同行；和，

6、和且角的字母，确定的矩形的其它两个和是由，列，则不在同一行也不在同一，若密时反向）；是最后一行的下方（解行被看作下方的字母。其中第一和分别是紧靠，在同一列，则对应密文，若密时反向）；是最后一列的右方（解列被看作右端的字母。其中第一和分别是紧靠，在同一行，则对应密文，若加密如下：，处理。每一对明文字母被当作被算为一个字母，即和其它字母。字母依次填入，然后在以字母表顺序去除重复的字母填关键词的字母左至右、从上至下依次从来构造，构建方法是：密钥个关键词字母矩阵，该矩阵由一组合。它基于一个换为密文双字母对待，并将这些单元转的双字母作为一个单元普莱费尔密码将明文中5.PP.4PCPCPPCCPP3.PP

7、CCPP2.PPCCPP1.PPIJJI)()(552122112121212121212121212115普莱费尔密码例7.2.5ar,mu,hs,ea/,monarchyMONARparmuhseaCHYBDEFGI JKLPQSTRM CM BP IMUVWXZ例，密钥是，则构造的字母矩阵如下如果明文是首先分组：对应密文为：普莱费尔密码的缺点是：它保持了明文语言的完好结构，几百字的密文就足以使用统计分析破译。区分普莱费尔密码和单表密码的有效方法是：统计文本中每个字母出现的频率，看频率曲线是否平稳。167.2.3换位密码n换位密码n换位就是重新排列明文消息中字母，以打破密文的结构特性，它交

8、换的不是字符本书，而是字符被书写的位置n一种换位的处理方法是：将明文按行写在格纸上，然后按列的方式读出结果，即为密文，为了增加变化的复杂性，可以设定读出列的不同次序（该次序即为密钥）n例7.2.8n换位密码中，虽然字母顺序被打乱了，但是密文和明文中字母出现的频率相同，密码分析者可以很容易辨别，但如果将换位密码和其它密码技术相结合，则可以得到十分有效的密码编码方案。17第第7 7章章 密码体制的安全性测度密码体制的安全性测度n7.1 密码基本知识n7.2 古典密码体制n7.3 现代密码体制现代密码体制n7.4 密码体制的安全性测度18现代密码体制n古典密码体制：代替和换位；实际应用中是两种方法的

9、组合运用，但密码的安全强度不够高。n为了适应现代信息安全的需要，现代密码技术得到了快速发展：n对称加密：如DES、AES等n非对称加密（也称公钥加密）：如RSAn消息摘要：如MD-1、MD-5等19现代密码体制n1.对称加密n加密和解密使用相同的密钥，用户必须让使用者知道密钥，密钥由双方共同保密。n2.非对称加密（公钥体制）n它使用一对关联密码：公开密钥和所有密钥，公钥任何人都知道，私钥只有主人知道，因此加密由一个密钥完成，解密由另一个密钥完成。公钥体制可实现加密、会话密钥分配和数字签名。n3.消息摘要n消息摘要用于防止信息被改动，使用摘要函数，函数的输入可以是任意大小的消息，输出是固定长度的

10、摘要，即数字指纹，对数字指纹用私钥加密，就成为数字签名（利用公钥可对数字签名解密，因为私钥只有签名的人才有，所以解密后即可证明加密人的身份问题）207.3.1对称密码n对称密码的特点是加密和解密使用同一个密钥，按加密模式分为：n分组密码：将原文按固定大小进行分组，然后加密，典型算法有DES、3DES、IDEA、AES、RC2和RC5等等n序列密码（流密码）：对流式数据进行加密，如实时的语音和视频流数据的加密传输，典型算法有RC4、SEAL和A5等。n对称密钥体制的基本要素：明文、加密算法、密钥、解密算法、明文和攻击者217.3.1对称密码n对称密钥体制安全性的要求：n1.加密算法必须足够安全，

11、可以公开。对算法的唯密文破译计算上不可行n2.密钥的安全性：密钥必须保密并有足够大的密钥空间n对称密码算法的优点：加解密速度快、实用性强；缺点是密钥分发困难；多用户通信时，密钥总数增长太快，导致密钥分发更加复杂；通信双方无法在线建立信任关系；数字签名困难（发送方可以否认发送，接收方可伪造签名）221.数据加密算法DESnDES(Data Encryption Standard)是最著名的对称算法，也是美国国家标准局曾采用的数据加密标准，虽然已经破译，但是其简单扩展的3-DES仍然是目前广泛使用的分组密码算法之一。nDES算法公开，分组长度为64位，密钥长度56位，算法分为3部分：初始置换和末置

12、换、子密钥产生、乘积变换。233.国际数据加密算法（IDEA）nIDEA(International Data Encryption Algorithm)与DES一样，也是一种迭代分组加密算法。分组长度为64位，8轮迭代，还有一轮输出变换。它的加、解密密钥不完全相同，但由加密密钥可以推出解密密钥，因此它仍然属于常规的对称密码体制。IDEA的密钥长度在目前技术条件下具有足够的安全长度。247.3.2 非对称密码n1.公钥密码体制的提出n1976年Diffie和Hellman提出公钥密码体制概念，有效克服了对称密码体制中密钥管理和分配的缺陷，并提出了数字签名的创新概念。由于具有两个密钥：公钥，用于

13、加密或签名验证，可以公开；私钥，用于解密或数字签名，需要保密。n非对称密码不再基于简单的代替和换位操作，而是建立在难解的数学问题上将信息通过编码加密在一个NP-完全问题中，破译等价于解这个NP-完全问题，同时需要一个陷门单向函数f。所谓陷门单向函数是只一单向函数f，它的逆函数在计算上通常是不可行的，但如果有辅助信息（即私钥）的帮助，其逆函数的计算又很容易，辅助信息就是秘密的“陷门”。n公钥算法基于的常见数学难题有:大整数分解问题、背包问题、有限域的乘法群上的离散对数问题和椭圆曲线上的离散对数问题。251.公钥密码体制的提出n公钥密码体制的优点n1.用户只需保管自己的私钥，管理方便；n2.密钥分

14、配简单，无需秘密通道或复杂协议来传送密钥。公钥可通过公开渠道获得。n3.可实现数字签名。n公钥密码体制的缺点n1.加、解密速度较慢；n2.同等安全强度下，公钥密码体制下的密钥长度要长一些。262.公钥密码体制的基本原理n公钥密码体制加密的算法基于单向陷门函数s1.2.y3.12f1 2 3ff2-1-1p单向陷门函数f的定义：给定x，计算y=f(x)是容易的；给定，计算x=f(y)是不可行的；存在一个辅助条件，计算x=f(y)是容易的。满足条件 和 的函数 是单向函数，同时满足、的函数是单向陷门函数，即是陷门信息。当用单向陷门函数 作为加密函数时，可将 公开，即相当于公钥K，被保密，用作解密密

15、钥，即私钥K。由单向陷门函数的条件 可知由截获的密文计算明文是不可能的。272.公钥密码体制的基本原理n公钥密码算法的条件：n1.产生一对密钥是容易的；n2.已知公钥和明文。产生密文在计算上是可行的；n3.接受方利用私钥来解密在计算上是可行的；n4.对于攻击者，利用公钥来推断私钥在计算上是不可行的；n5.已知公钥和密文，恢复明文在计算上是不可行的；n6.加密和解密的顺序可交换（可选条件）。282.公钥密码体制的基本原理n公钥密码体制下的保密通信和数字签名bbbbaaaaAliceBobAliceBobD(C)D()m,Alice:AliceAllSD()All(S)(D()mpsspsppsp

16、spsKKKKKKKK用公钥密码实现保密，密码对（K，K）,公钥K 公开，私钥K 保密向发生信息，保密通信过程如下BobC=E(m)E(m)数字签名过程操作顺序和加密相反如向大家出示签名mEEm29RSA算法ed512pqnnpq,1(mod)d(en)(dp)RSARSAcm(mod n)RASmc(mod n)ps首先选取两个比特的随机素数、，计算模 和（n）:（n）=(p-1)(q-1)然后选取参数e，根据ed（n）求参数。将，作为公钥K，将，q 作为私钥K。因此，算法可以表示为:加密：解密：30RSA算法（例）e577RSA(5)(77)m19cm(mod n)19(mod119)66

17、(mod119)(mod n)66(mopsd例7.3.1选取p=7，q=17，计算参数显然n=pq=119，且（n）=(p-1)(q-1)=96取e=5，则d=77，（5*77=385=4*9611mod 96）则公钥K，119，私钥K，7，17对明文进行加密：则接收到密文c=66之后，对其进行解密：m=cd119)19(mod119)31RSA算法n4.RSA算法的安全性nRSA算法的安全性取决于从公钥(e，n)中计算出私钥(d，p，q)的困难程度：即依赖于分解大合数n的难度，只要能够将已知的n分解为p和q的乘积，即可破解RSA。因此为了保证RSA算法的安全，n必须足够大，一般认为长102

18、4位二进制。n5.RSA的速度与不足n由于大数运算，RSA的速度最多是DES的1/1000。因此RSA只用于少量数据的加密，比如通信双方交换的对称密钥。nRSA缺点：n产生密钥受到素数产生技术的限制，算法有可能产生的不是素数；n分组长度太长，即n太大，使运算速度降低n随大数分解技术的发展，n需要不断增加，不利于数据格式的标准化。32第第7 7章章 密码体制的安全性测度密码体制的安全性测度n7.1 密码基本知识n7.2 古典密码体制n7.3 现代密码体制n7.4 密码体制的安全性测度密码体制的安全性测度337.4密码体制的安全性测度n评价密码体制的安全有多种标准，通常可分为两类：理论安全和实际安

19、全n理论安全指密码攻击者无论拥有多少金钱、资源和工具都无法破译密码，如香农证明过的一次一密的密码体制是完全保密的密码体制。n和实际安全指攻击者破译代价超过了信息本身的价值或在现有条件下破译所花费时间超过了信息的有效期n本节所讲述的是狭义的信息安全，主要指保密性，即信息内容不会被泄漏。其实除了保密性外，安全性还有完整性、抗否认性和可用性。347.4.1完善保密性n从信息论的角度来证明密码体制的保密性n对于一般保密通信系统，用P，C，K分别表示明文、密文和密钥空间，H(P)，H(C)，H(K)分别代表明文、密文和密钥空间的熵，H(P/C)和H(K/C)分别代表已知密文的条件下对明文和密钥的疑义度，

20、从唯密文攻击角度来看，密码分析的任务是从截获的密文中提取有关明文或密钥的信息：nI(P；C)=H(P)H(P/C)nI(K；C)=H(K)H(K/C)n显然，H(P/C)和H(K/C)越大，攻击者从密文中获得的明文和密钥信息就越少。357.4.1完善保密性n合法用户掌握解密的密钥，收到密文后，通过解密运算可以恢复出明文，则必有H(P/CK)0，因此nI(P；CK)=H(P)H(P/CK)H(P)n说明用户在掌握密钥并已知密文的情况下，可以提取全部明文信息。n定理：对任意密码系统，有n I(P；C)=H(P)H(K)n定理说明。密码体制的密钥空间越大，从密文中提取有关明文的信息量就越小，即密钥空

21、间越大，破译越困难。如果I(P；C)=0，说明攻击者不能从密文提取任何有关明文的信息，此时就是所谓的理论安全，称密码系统是完善保密的或无条件安全的。n如果密钥空间大于明文空间，即H(K)=H(P),则I(P；C)必为0367.4.2唯一解距离n唯一解距离V0是攻击者在进行唯密文攻击时必须处理的密文量的理论下界。当攻击者获得的密文量大于这个界限是，密码有可能破译，如果小于它，则密码在理论上是不可破译的。N000NCcccYYH(K/c cc)H(K/c cc)NH(K/C)0I(KC)H(K)H(K/C)H(K)IHH(P)HH(P)12N1 2N+11 2N设给定 长密文序列，其中 为密文字母表。根据条件熵的性质有随着 的增大，密钥的疑义度在减少，也就是说截获的密文信息越多，从中提取有关密钥的信息就越多。当 时；密钥被完全确定，从而实现破译。如果代表明文信息变差，和分别代表明文00H(K)VI最大熵和明文熵。可以证明，唯一解距离即是破译密码所需的最小密文长度值得注意的是，唯一解距离它只是破译所需最小密文数量的理论下界，到达这个下界不代表一定能破译，但达不到则一定不能破译。