信息论与编码加密编码.pptx

Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,Company name,Company slogan here,WWW.COMPANYSITE.COM|INFOCOMPANYSITE.COM|[phone]|LONG STREET 12345,CITY,COUNTRY,#,Click to edit Master title style,Company name,Company slogan here,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,Click to edit Master title style,WWW.COMPANYSITE.COM|INFOCOMPANYSITE.COM|[phone]|LONG STREET 12345,CITY,COUNTRY,#,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,22.11.2019,#,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,22.11.2019,#,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,22.11.2019,#,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,2019/11/22,#,单击此处编辑母版文本样式,第二级,第三级,第四级,单击此处编辑母版标题样式,Page,#,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,22.11.2019,#,22.11.2019,#,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,Logo,#,Click to edit Master title style,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,Logo,绪论,Contents,1,密码学概述,2,加密编码中的信息论分析,3,古典密码及近代密码,4,现代密码学,5,Logo,密码学其他分支简介,Contents,6,网络通信加密方式,7,密码学理论及应用展望,8,思考题与习题,9,Logo,绪论,信息的传输过程中容易被对手截获，为了对信息进行保密，就需要采用加密编码。加密编码在不断发展、扩展的过程中形成了一门新的学问密码学，它涉及到两部分内容：密码编码和密码分析（破译）。,密码学是一个扩展的概念,对密码学存在的误解,Logo,初次接触密码学的人可能会存在,的,误解,：,以为学了密码学就可以破解qq、邮箱密码之类的，其实这类的密码和密码学的一些情况下是两码事，一些密码都没有采用密码技术，而且破解密码的手法也比较简单,学习了密码学即可用于破解银行的密码，而实际上破解银行的密码一般利用的不是高深的密码学知识，相反，它可能用各种木马，窃取密码。,Logo,5,1.完整性(Integrity),2.可用性(Availability),3.真实性(Authenticity）,除了通过加密实现机密性,(Confidentiality),以外，经过逐步的发展，还可以实现以下安全需求：,4.责任追究性(Accountability）,5.公平性,现代的密码学,7.1 密码学概述,7.1.1 基本专业术语,7.1.2 加密编码算法分类,7.1.3 密码分析及其分类,7.1.4 密码系统的安全性及其分类,7.1.5 加密编码的发展历程,明文（Plaintext）：待伪装或加密的消息（Message）。,密文(Ciphertext)：对明文施加某种伪装或变换后的输出，也可认为是不可直接理解的字符或比特集，密文常用c表示。,解密(decryption)算法则是其相反的过程：由密文转换回明文；加解密包含了这两种算法，一般加密即同时指称加密(encrypt或encipher)与解密(decrypt或decipher)的技术。,密码算法(Cryptography Algorithm)，也简称密码（Cipher），通常是指加、解密过程所使用的信息变换规则，是用于信息加密和解密的数学函数。,密钥（Secret Key或者Key）：密码算法中的一个可变参数，通常是一组满足一定条件的随机序列。,密码系统(Cryptosystem)：是加解密参与的各个要素构成的系统。,7,7.1.1,基本专业术语,密码学的作用：,鉴别,：消息的接收者应该能够确认消息的来源（人、设备等）；入侵者不可能伪装成他人发送伪冒信息。,完整性,：消息的接收者应该能够验证在传送过程中消息没有被修改；入侵者不可能用假冒、篡改的消息代替发送者合法消息。,抗抵赖,：发送者事后不可能虚假地否认他发送的消息。,9,类似于通信系统的模型，香农也建立了保密系统的模型，如下图,7-1,所示：,7.1.2,加密编码算法分类,图,7-1,保密系统模型,10,E,K,（M）=C D,K,（C）=M （7-1）（7-2）,这些函数具有下面的特性（见图7-2）：,D,K,（E,K,（M）=M.,加密和解密运算都使用密钥（即运算都依赖于密钥，并用,K,作为下标表示），这样，加,/,解密函数现在变成：,图,7-2,使用一个密钥的加,/,解密,11,有些算法使用不同的加密密钥和解密密钥（见图7-3），也就是说加密密钥K1与相应的解密密钥K2不同，在这种情况下：,E,K1,（M）=C D,K2,（C）=M （7-3）（7-4）,D,K2,（E,K1,（M）=M,图,7-3,使用两个密钥的加,/,解密,对称加密算法（对称密码算法）有时又叫传统密码（加密）算法、单钥密码（加密）算法、秘密密钥密码（加密）算法，就是加密密钥能够从解密密钥中推算出来，反过来也成立。,12,基于密钥的算法通常有两类：对称加密算法和公开密钥加密算法。,对称算法的加密和解密表示为：,E,K,（,M,）,=,C,D,K,（,C,）,=,M,13,公开密钥算法（也叫非对称算法、双钥算法）是这样设计的：用作加密的密钥不同于用作解密的密钥，而且解密密钥不能根据加密密钥计算出来（至少在合理假定的长时间内）。用公开密钥,K,加密表示为,EK,（,M,）,=C.,虽然公开密钥和私人密钥是不同的，但用相应的私人密钥解密可表示为：,DK,（,C,）,=M,有时消息用私人密钥加密而用公开密钥解密，这用于数字签名，尽管可能产生混淆，但这些运算可分别表示为：,EK,（,M,）,=C,DK,（,C,）,=M,公开密钥算法,密码编码学的主要目的是保持明文（或密钥，或明文和密钥）的秘密以防止偷听者（也叫对手、攻击者、截取者、入侵者、敌手或干脆称为敌人）知晓。这里假设偷听者完全能够接获收发者之间的通信。,密码分析学是在不知道密钥的情况下。恢复出明文的科学。成功的密码分析能恢复出消息的明文或密钥。密码分析也可以发现密码体制的弱点，最终得到上述结果（密钥通过非密码分析方式的丢失叫做泄露。）,14,7.1.3,密码分析及其分类,(1),唯密文攻击,（又称唯密文分析）。密码分析者有一些消息的密文，这些消息都用同一加密算法加密。,已知：C,1,=E,K,（P,1,），C,2,=E,K,（P,2,），C,i,=E,K,（P,i,）,推导出：P,1,，P,2,，P,i,；K或者找出一个算法从C,i+1,=E,K,（P,i+1）,推出P,i+1,。,15,常用的密码分析（攻击）有四类，当然，每一类都假设密码分析者知道所用的加密算法的全部知识：,(2),已知明文攻击,。密码分析者不仅可得到一些消息的密文，而且也知道这些消息的明文。,已知：,P,1,，,C,1=,E,k,（,P,1,），,P,2,，,C,2,=Ek,（,P2,），,Pi,，,Ci=Ek,（,Pi,），,推导出：密钥,k,，或从,Ci+1=Ek,（,Pi+1,）推出,Pi+1,的算法。,（3）,选择明文攻击,。分析者不仅可得到一些消息的密文和相应的明文，而且他们也可选择被加密的明文。,已知：P,1,，C,1,=E,k,（P,1,），P,2,，C,2,=E,k,（P,2,），P,i,，C,i,=E,k,（P,i,）,其中P,1,，P,2,，P,i,是由密码分析者选择的。,16,（,4,）,自适应选择明文攻击,。这是选择明文攻击的特殊情况。密码分析者不仅能选择被加密的明文，而且也能基于以前加密的结果修正这个选择。,（,5,）,选择密文攻击,。密码分析者能选择不同的被加密的密文，并可得到对应的解密的明文，例如密码分析者存取一个防窜改的自动解密盒，密码分析者的任务是推出密钥。,已知：,C,1,，,P,1,=D,k,（,C,1,），,C,2,，,P,2,=D,k,（,C,2,），,C,i,，,P,i,=D,k,（,C,i,），,推导出：,k,。,（,6,）,选择密钥攻击,。这种攻击并不表示密码分析者能够选择密钥，它只表示密码分析者具有不同密钥之间的关系的有关知识。这种方法有点奇特和晦涩，不是很实际。,17,（,7,）,软磨硬泡,(Rubber-hose),攻击,。密码分析者威胁、勒索，或者折磨某人，直到他给出密钥为止。行贿有时称为购买密钥攻击。这些是非常有效的攻击，并且经常是破译算法的最好途径。,全部破译,。密码分析者找出密钥,K,，这样,D,K,（,C,）,=P,。,全盘推导,。密码分析者找到一个代替算法,A,，在不知道密钥,K,的情况下，等价于,D,K,（,C,）,=P,。,实例（或局部）推导,。密码分析者从截获的密文中找出明文。,信息推导,。密码分析者获得一些有关密钥或明文的信息。这些信息可能是密钥的几个比特、有关明文格式的信息等等。,18,Lars Knudsen,把破译算法分为不同的类别，安全性的递减顺序为：,一个密码系统的安全性（security,safety）主要与两个方面的因素有关：,（1）一个是所使用密码算法本身的保密强度。,（2）另外一个方面就是密码算法之外的不安全因素。,因此，密码算法的保密强度并不等价于密码系统整体的安全性。,19,7.1.4,密码系统的安全性及其分类,（,1,）无条件安全性（,unconditional security,）,（,2,）计算安全性（,computational security,）,（,3,）可证明安全性,(provable security),20,评估密码系统安全性主要有三种方法：,（,1,）破译该密码系统的实际计算量（包括计算时间或费用）十分巨大，以至于在实际上是无法实现的。,（,2,）破译该密码系统所需要的计算时间超过被加密信息有用的生命周期。例如，战争中发起战斗攻击的作战命令只需要在战斗打响前需要保密；重要新闻消息在公开报道前需要保密的时间往往也只有几个小时。,（,3,）破译该密码系统的费用超过被加密信息本身的价值。如果一个密码系统能够满足以上准则之一，就可以认为是满足实际安全性的。,21,密码系统要达到计算安全性（实际安全性），就要满足以下准则：,数据复杂性,（,Data Complexity,）。用作攻击输入所需的数据量。,处理复杂性,（,Processing Complexity,）。完成攻击所需要的时间，这个经常叫做工作因素。,存储需求,（,Storage Requirement,）。进行攻击所需要的存储量。,作为一个法则，攻击的复杂性取这三个因数的最小化，有些攻击包括这三种复杂性的折中：存储需求越大，攻击可能越快。,22,不同方式衡量攻击方法的复杂性：,第一阶段,：,1949,年之前，密码学还不是科学而是艺术，密码算法的设计者都是凭借自己的直观设计密码算法。,第二阶段,：,1949,1975,年，密码学成为科学，以,1949,年,Shannon,的“,The Communication Theory of Secret Systems”,为标志。,第三阶段,：,1976,年以后，出现了密码学的新方向,23,7.1.5,加密编码的发展历程,香农对信息的定义是：信息是消除不确定性的东西，对于加密而言，在让接受者获取信息的同时，希望对手能够获取的信息尽量少，这意味着一个密码系统，对于对手的不确定性应该越大越好，可见密码系统的安全性问题可以转化为信息论中熵、条件熵、平均互信息量的问题。一个一般的密码系统，其加密解密可以表示为：,E,K,（,M,）,=C,D,K,（,C,）,=M,对于对手，一般已知密文,C,，欲增强密码系统的不确定性，则可以增加,K,的不确定性，或者说从互信息量的角度，通过,C,获取的关于,M,（或者,K,）的互信息量要小；从另外一个角度，,C,作为条件时，,K,和,M,的不确定性大。,24,7.2,加密编码中的信息论分析,在密码学中有两种疑义度：,1,）对于给定密文,C,，密钥,K,的疑义度可表示为,H(K|C)=,p(k,i,c,j,)log,2,p(k,i,|c,j,),（,7-5,）,2,）对于给定密文,C,，明文,M,的疑义度可表示为,H(M|C)=,p(m,i,c,j,)log,2,p(m,i|,c,j,),25,7.2.1,加密编码中的熵概念,26,破译者的任务是从截获的密文中提取有关明文的信息或从密文中提取有关密钥的信息,I(M,；,C),H(M),H(M/C),I(K,；,C),H(K),H(K/C),H(M/C),和,H(K/C),越大，破译者从密文能够提取出有关明文和密钥的信息就越小。,对于合法的接收者，在已知密钥和密文条件下提取明文信息：,H(M/C,K),0,I(M,；,CK),H(M),H(M/C,K),H(M),疑义度,27,因为,H(K/C),H(M/K,C),H(M/C),H(K/M,C),（,M,和,K,交换）,H(M/C),（熵值,H(K/M,C),总是大于等于零）,H(M/C,K),0,，上式得,H(K/C),H(M/C),即已知密文后，,密钥的疑义度总是大于等于明文的疑义度,。我们可以这样来理解，由于可能存在多种密钥把一个明文消息,M,加密成相同的密文消息,C,，即满足,的,K,值不止一个。但用同一个密钥对不同明文加密而得到相同的密文则较困难,无法解密。,疑义度,28,又因为,H(K),H(K/C),H(M/C),，,则,上式说明，,保密系统的密钥量越少，密钥熵,H(K),就越小，其密文中含有的关于明文的信息量,I(M;C),就越大,。至于破译者能否有效地提取出来，则是另外的问题了。作为系统设计者，自然要选择有足够多的密钥量才行。,疑义度,29,在破译密码时，有时候我们会尝试用一个一个的密钥尝试加密所有的明文，看得到的明文是否有意义，这样就可以在一定的程度上判断密钥是否是正确的。一个密码系统，就是需要让对手看来有更大的自由度，这样他们就无法确定明文。可以认为明文冗余度对于密码系统自由度的销噬。,7.2.2,密码系统的自由度,香农给出的唯一解距离的计算公式：,（7-12）,U为唯一解距离，H（K）为密码体制的熵，D为语言冗余度。根据以上方法得出的唯一解距离都很短。,你认为信息论中的冗余度与在这里的冗余度一样吗？在此距离下是有唯一解吗？,30,7.2.3,唯一解距离与理想保密,31,7.2.4,完善保密与一次一密体制,香农定义了完善保密（完全保密，,Perfect Secrecy,）：对一个密码体制而言，如果对所有明文空间中的任一明文,x,和密文空间中的任一密文,y,，都有,，即截获密文后，明文的概率分布不发生改变，,则称该密码体制具有完善保密性,(Perfect secrecy),。或称该密码体制是完全保密的。,根据密文与明文长度相等是否获得关于明文信息？,32,7.2.5,具有误导功能的低密钥可信度加密算法,如何让错误密钥得到的明文也有意义？,选择题的扩充,一次一密的改进,33,7.2.6,多重不确定的密码体制,现有密码系统中只有密钥是不确定的,密码分析有哪些确定的条件，算法可以让这些条件不确定？,是否可以让算法、加密重数等信息也不确定？,世界上最早的一种密码产生于公元前两世纪。是由一位希腊人提出的，人们称之为棋盘密码，原因为该密码将,26,个字母放在,55,的方格里，,i,j,放在一个格子里，具体情况如下图,7-4,所示：,34,7.3,古典密码及近代密码,7.3.1,常见古典密码,1,2,3,4,5,1,a,b,c,d,e,2,f,g,h,ij,k,3,l,m,n,o,p,4,q,r,s,t,u,5,v,w,x,y,z,图,7-4,棋盘密码,古代密码多数可以通过字母频率攻击来破解，以恺撒密码为例，即使在不知道移位所对应的数字是,3,的情况下（因为可以是其它数字，而要破解的关键就是要找到这个数字），可以通过检查字母出现的频率来推测，比如：,原文：,p a n d a s o f t w a r e,密码：,s d q g d v r i w z d u h,35,7.3.2,古典密码的分析,在这里，“,d”,出现的次数最多，由于英语中最常出现的两个字母是“,a”,和“,e”,，于是可以分别进行检验。在“,e”,的情况下，“,d”,在“,e”,的后面第,25,位，然后用,25,来检验其它字母，出现如下情况：,密码：,s d q g d v r i w z d u h,向后,25,位译码：,t e r h e w s j x a e v i,这个字母序列没有丝毫意义，所以这次尝试不成功。然后再用,3,来试验，可以得到如下结果：,密码：,s d q g d v r i w z d u h,向后,3,位译码：,p a n d a s o f t w a r e,36,1834,年，伦敦大家的实验物理学教授惠斯顿发明了电机，这是通信向机械化、电气化跃进的开始，也是密码通信能够采用在线加密技术提供了前提条件。,对于分组密码，分组长度是固定的，如何对任意长度的明文进行处理才能保证通过密文唯一地得到明文？,37,7.3.3,近代密码,前面两章介绍了古典密码和近代密码，它们的研究还称不上是一门科学。直到,1949,年香农发表了一篇题为“保密系统的通信理论”的著名论文，该文首先将信息论引入了密码，从而把已有数千年历史的密码学推向了科学的轨道，奠定了密码学的理论基础。,38,7.4,现代密码学,有利于对密码算法的安全性进行公开测试评估；,防止密码算法设计者在算法中隐藏后门；,易于实现密码算法的标准化；,有利于使用密码算法产品的规模化生产，实现低成本和高性能。,39,对于商用密码系统而言，将密码算法公开的优点包括：,系统,的保密性不依赖于对加密体制或算法的保密，而仅依赖于密钥的安全性。,满足实际安全性，使破译者取得密文后在有效时间和成本范围内，确定密钥或相应明文在计算上是不可行的。,加密和解密算法应适用于明文空间、密钥空间中的所有元素。如果不能适应，应该进行相应的处理，比如填充。,加密和解密算法能快速有效地计算，密码系统易于实现和使用。,40,一个提供机密性服务的密码系统是实际可用的，必须满足的基本要求：,7.4.1,对称加密算法,对称加密算法分为分组密码和流密码算法。目前世界上较为通用的分组加密算法有AES、IDEA和DES，流密码算法有RC4，A5。这类加密算法的计算速度非常快，因此被广泛应用于对大量数据的加密过程。,1.AES,算法,Rijndael,之所为能当选,AES,，主要是因为：,(1),运算速度快，软硬件实现都表现出非常好的性能；,(2),对内存的需求非常低，很适合于受限制的环境下；,(3),算法可靠，使用非线性结构,S,盒，有足够的安全性；,(4),该算法能有效抵抗差分分析和线性分析攻击；,(5)Rijndael,是一个分组迭代密码，被设计成,128,、,192,、,256,比特三种密钥长度，可用于加密长度,128,、,192,、,256,比特的分组，相应的轮数为,10,、,12,、,14,，分组长度和密钥长度设计灵活。,42,扩展密钥是从密钥矩阵变换而来，之所以称之为“扩展”是因为在,AES,的加密过程中，要对数据进行,Nr+1,次密钥加运算（包括一次初始密钥加运算），每次加密的密钥都不一样，我们将这,Nr+1,次密钥加运算过程中用到的所有的密钥的集合叫做扩展密钥。迭代的轮数,Nr,是变化的，取值是根据,Nb,和,Nk,的值确定的，,AES,算法中给出了它们之间如下的对照表：,43,在进行加密之初，首先要生成每一轮加密的子密钥（轮密钥），而实际上原始密钥（种子密钥）是远远不够的，所以它通过密钥扩展来生成足够的轮密钥。,44,例如：如果,Nb=6,，,Nk=4,那么我们的加密过程应该进行,Nr+1=13,次，那么也就有,13,个扩展密钥。由于这些密钥要和,state_matirx,矩阵做异或运算，所以每个扩展密钥必须转化为一个和,state_matirx,矩阵同维数的加密矩阵才可以进行每个元素一对一的运算。由,Nb,和,Nr,的值，我们可以计算出扩展密钥的整体“长度”，这个长度的单位为,4,个字节。如下公式可以给出：,Nb*,（,Nr+1,）；例如,Nb=6,，,Nr=12,则“长度”为,78,；,Nr,Nb=4,Nb,=6,Nb,=8,Nk,=4,10,12,14,Nk,=6,12,12,14,Nk,=8,14,14,14,表,7-1 Nr,取值表,中间的迭代轮和结尾轮有一定的共同之处，下面介绍中间迭代轮包含,4,个步骤：,字节代换,（,SubBytes,）,透过一个非线性的替换函数，用查找表的方式把每个字节整体替换成对应的字节，也就是说这是一个,8bit,的,S,盒，这个变化具有很好的非线性性。,行移位,（,ShiftRows,）,将矩阵中的每个横列进行左循环移位移位。,列混合,（,MixColumns,）,为了充分混合矩阵中各个直行的操作。这个步骤使用线性转换来混合每行内的四个字节，它是,GF(28),上乘法运算，其中所乘的因子是,3,个固定的数,01,，,03,，,01,。,轮密钥加,（,AddRoundKey,）：矩阵中的每一个字节都与该轮对应的轮密钥（,round key,）做,XOR,运算；每个轮密钥（子密钥）由密钥（又称加密密钥、种子密钥）通过密钥生成方案（,key schedule,）扩展产生。,迭代轮的4个步骤：,考虑到查表比计算更快，时间复杂度低，但是是以空间复杂度为代价的，,AES,加密算法的查表优化：使用,32,或更多,bit,寻址的系统，可以事先对所有可能的输入建立对应表，利用查表来实作,SubBytes,，,ShiftRows,和,MixColumns,步骤以达到加速的效果。这么做需要产生,4,个表，每个表都有,256,个格子，一个格子记载,32bit,的输出；约占去,4KB(4096,字节,),内存空间，即每个表占去,1KB,的内存空间。如此一来，在每个加密循环中，只需要查,16,次表，作,12,次,32bit,的,XOR,运算，以及,AddRoundKey,步骤中,4,次,32bitXOR,运算。,用128bit的密钥（循环次数为10），那么每次加密的分组长为128bit的例子来说明算法，128bit有16个字节，每次加密一个128bit的分组，每次从明文中按顺序取出16个字节假设为a0a1a2a3a4a5a6a7a8a9a10a11a12a13a14a15，这16个字节在进行变换前先放到一个44的矩阵中，形成状态（state）。如下图7-5所示：,a,0,a,4,a,8,a,12,a,1,a,5,a,9,a,13,a,2,a,6,a,10,a,14,a,3,a,7,a,11,a,15,图,7-5,状态图,首先进行一个初始的密钥加运算。,接着进行,开始第一次循环的第一个变换：,SubByte,。字节变换,图,7-6,字节代换查表过程示意图,表中的,S12,为一个字节，可以用两个十六进制（,XY,）,16,来表示，,S12=,（,53,）,16,，下表是根据,XY,来建立的对应,SubByte,输出值的表。,接着是,ShiftRows,步骤：将状态中的各行进行循环移位，第,1,行（对应行值为,0,）不移动，第,2,行左循环移位,1,字节，以此类推，,S,为移动后的字节位置。,图,7-7,行移位示意图,MixColumns,步骤：,S,0c,(02S0c)(03S1c)S2cS3c,，但这个结果可能会超出一个字节的存储范围，所以实际上还要对结果进行处理。,接着是,AddRoundKey,步骤：将密钥编排得到的对应轮的轮密钥与前面的结果进行异或运算。,图,7-8,密钥加示意图,分组密码的工作模式主要有：电子密码本模式,ECB,、密码分组链接模式,CBC,、密码反馈模式,CFB,、输出反馈模式,OFB,、计数器模式,CTR,、密文挪用模式,CTS,等等。,(1)电子密码本模式ECB,优点为,1.简单；,2.有利于并行计算；,3.误差不会被传送；,缺点：,1.不能隐藏明文的模式；,2.可能对明文进行主动攻击；,(2),密码分组链接模式,CBC,优点：,1.不容易主动攻击，安全性好于ECB，适合传输长度长的报文，是SSL、IPSec的标准。,缺点：,1.不利于并行计算；,2.误差传递；,3.需要初始化向量IV。,(3),密码反馈模式,CFB,优点：,1.隐藏了明文模式;,2.分组密码转化为流模式，无需填充处理；,3.可以及时加密传送小于分组的数据;,缺点：,1.不利于并行计算;,2.误差传送：一个明文单元损坏影响多个单元;,3.唯一的IV;,(4),输出反馈模式,OFB,优点：,1.隐藏了明文模式;,2.分组密码转化为流模式;,3.可以及时加密传送小于分组的数据;,缺点：,1.不利于并行计算;,2.对明文的主动攻击是可能的;,3.误差传送：一个明文单元损坏影响多个单元;,RSA,工作原理,任意选取两个不同的大质数,p,和,q,，计算乘积,n=p*q,；,任意选取一个大整数,e,，,e,与,(p-1)*(q-1),互质，整数,e,用做加密密钥。注意：,e,的选取是很容易的，例如，所有大于,p,和,q,的质数都可用。,确定解密密钥,d,：,d*e1 mod,（,p-1,）*（,q-1,）根据,e,、,p,和,q,可以容易地计算出,d,。,公开整数,n,和,e,，但是不公开,d,；,将明文,P(,假设,P,是一个小于,r,的整数,),加密为密文,C,，计算方法为：,CPe mod n,将密文,C,解密为明文,P,，计算方法为：,PCd mod n,(5),计数器模式,CTR,图,7-12 CTR,的模式,7.4.2,公开密钥加密算法,定理7-1 欧拉定理：若n,a为正整数，且n,a互素，则,a(n)1(mod n)（7-15）,其中(n)称为欧拉函数，欧拉定理实际上是费马小定理的推广。可以利用它来简化幂的模运算。,7.4.3 hash,函数,hash函数也称杂凑函数（算法）、散列函数、哈希算法，就是把任意长的输入消息串变化成固定长的输出串的一种函数。这个输出串称为该消息的杂凑值。一般用于产生消息摘要，密钥加密等。,一个安全的杂凑函数应该至少满足以下几个条件：,输入长度是任意的，这是因为明文的长度一般是任意的,;,输出长度是固定的，并且要足够长以保障安全性，根据目前的计算技术应至少取,128bits,长，以便抵抗生日攻击,;,对每一个给定的输入,M,，计算输出即杂凑值,Hash,（,M,）是很容易的；,已知杂凑值,Hash,（,M,）反推,X,，使得,Hash,（,M,）,=Hash,（,X,）在计算上是不可能的（其中,X,不一定等于,M,）；,给定杂凑函数的描述，找到两个不同的输入消息,M1,和,M2,杂凑到同一个值（即,Hash,（,M1,）,=Hash,（,M2,）是计算上不可行的,hash,值的每一,bit,都与,M,的每一,bit,相关，并有高度敏感性。,一个安全的杂凑函数应该至少满足以下几个条件：,7.5,密码学其他分支简介,在密码学中，有许多方案、协议、应用或算法，具有许多特别的功能，它们不一定是关于保密性、认证性的，这些方案虽然有些复杂，我们没有必要一一掌握，但是，有必要了解它们的概念，当需要运用的时候，按照相应的关键词、名称去查阅相关的文献资料即可。,7.5.1,特殊数字签名,盲签名（,blind signature,）,代理签名（,Agent Signature Scheme,）,群签名（,group signature,、又称团体签名）,不可抵赖的数字签名（,undeniable signature,）,指定的确认者签名（,designated confirmer signature,，指定证实人签名）,一次性签名,(One-Time Signature),7.5.2,零知识证明,零知识证明（zero-knowledge proof），是由Goldwasser等人在20世纪80年代初提出的。它指的是证明者能够在不向验证者提供任何有用的信息的情况下，使验证者相信某个论断是正确的。零知识证明实质上是一种涉及两方或更多方的协议，即两方或更多方完成一项任务所需采取的一系列步骤。,7.5.3,秘密共享,秘密共享的思想是将秘密以适当的方式拆分，拆分后的每一个份额由不同的参与者管理，单个参与者无法恢复秘密信息，只有若干个参与者（无需全部参与者）一同协作才能恢复秘密消息。,7.5.4,秘密分割,秘密分割是将某一密码信息k分成片ki给n个人，只有当它们同时给出自己的秘密分片ki，才能恢复信息。它与秘密共享具有相似性，但是，没有秘密共享的要求高，也很容易实现，比如，通过k1k2kn=k即可进行秘密分割,。,7.5.5,阈下信道,阈下信道是指在基于公钥密码技术的数字签名、认证等应用密码体制的输出密码数据中建立起来的一种隐蔽信道，除指定的接收者外，任何其他人均不知道密码数据中是否有阈下消息存在。,7.5.6,比特承诺,比特承诺(Bit Commitment，BC)是密码学中的重要基础协议，其概念最早由1995年图灵奖得主Blum提出。比特承诺方案可用于构建零知识证明、可验证秘密分享、硬币投掷等协议，同时和茫然传送一起构成安全双方计算的基础，是信息安全领域研究的热点。,7.5.7,不经意传输,不经意传输(茫然传送，Oblivious transfer)的第一种形式是在1981年由Michael O.Rabin提出。Oblivious有健忘之意，指的是发送者对于到底传输的哪一消息是不知道的、不经意的、茫然的，现实中要达到这种茫然，似乎很困难，其实可以采用加密来实现。,7.5.8,保密选举,除非有一个协议既能防止欺骗又能保护个人隐私，否则计算机化的投票永远不会在一般选举中使用。理想的协议至少要有这样六项要求：,（,1,）只有经授权的投票者才能投票。,（,2,）每个人投票不得超过一次。,（,3,）任何人都不能确定别人投谁的票。,（,4,）没有人能复制其它人的选票。（这一点证明是最困难的要求。）,（,5,）没有人能修改其他人的选票而不被发现。,（,6,）每个投票者都可以保证他的选票在最后的表中被计算在内。,此外，有些投票方案可能有如下要求：,（,7,）每个人都知道谁投了票及谁没有投。,7.5.9,保密的多方计算,保密的多方计算是一种协议，在这个协议中，一群人可在一起用一种特殊的方法计算许多变量的任何函数。这一群中的每个人都知道这个函数的值，但除了函数输出的明显东西外，没有人知道关于任何其他成员输入的任何事情。,7.5.10,数字现金,数字现金是网络化社会进行电子支付的一种重要的手段，对于电子商务的发展至关重要。有些现金可能是实名的，这个相对容易操作，而有些数字现金是匿名的，这类数字现金协议非常复杂。,7.5.11,电子拍卖,电子拍卖（E-Auction）是传统拍卖形式在线实现。卖方可以借助网上拍卖平台运用多媒体技术来展示自己的商品，这样就可以免除传统拍卖中实物的移动；竞拍方也可以借助网络，足不出户进行网上竞拍。该方式的驱动者是传统的拍卖中间商和平台服务提供商（PSP）。,7.6,网络通信加密方式,网络通信系统中应用密码技术的方式有三种：链路加密、端端加密和节点加密。,(1)链路加密方式,(2)端端加密方式,(3)节点加密方式,7.7,密码学理论及应用展望,在密码学及其相关的信息安全产业发展方面，我们认为：,要重视产品的功能集成和标准化，推出支持多种标准，比如同时支持,PGP,和,PKI,的公钥标准的安全产品。,一些安全相关的产品应该更加多功能、便利化和通用化,政府应该在产业的规范化、标准化和兼容性方面做出更多的工作。,一个产业的推出不一定要一开始就以盈利为目标,积极运用密码技术推进公益事业,信息安全和密码产业涉及到的不仅仅是个人和企业的利益,7.7.1,量子密码学,量子密码学,（,Quantum Cryptography,）是一门很有前途的新领域，许多国家的人员都在研究它，而且在一定的范围内进行了试验。离实际应用只有一段不很长的距离。量子密码体系采用量子态作为信息载体，经由量子通道在合法的用户之间传送密钥。量子密码的安全性由测不准原理和量子不可克隆定理所保证，量子密码也被认为是非常有前途的、不可破译的密码体制。,7.7.2,同态加密,同态加密,（homomorphic encryption）是2009年IBM公司的克雷格金特里（Craig Gentry）的一项关于密码学的突破性的发现：对加密的数据进行处理得到一个输出，将这一输出进行解密，其结果与用同一方法处理未加密的原始数据得到的输出结果是一样的。,7.7.3,数字版权保护技术,在数字化的时代，许多重要的产品都是数字化的，比如软件、视频文件、音频文件、各种文档等等。但是目前看来这方面的保护是非常欠缺的，许多软件采取了一定的保护措施，但是，却很容易就被破解了。这使得数字化作品的开发者没有动力，也没有经济能力去继续开发产品。除了从法律层面来解决问题外，我们也可以应用技术手段来限制版权的滥用。数字版权保护技术可以担当重任。,7.7.4,数字签名应用,数字签名可以进行认证身份且非合法用户不能伪造和签名者不可否认，因而可以取代传统的签名、盖章，取代传统的纸质证书和票据等。除了可以取代传统的签名以外，它还能在数字化、信息化和网络化等独特的领域有着不可替代的作用，如数字化文档的签名等方面，在这些方面显然传统的签名无能为力。,7.7.5,密码技术支撑诚信产业,中国社会诚信非常欠缺，一些涉及到人的食品安全的问题一直屡禁不止，不断涌现，引起很大的关注，而这些失信于人的企业中，也有非常有名的厂家。正是这些问题使得对诚信的需求非常大，急需一种新的产业-诚信产业来规范市场，建立社会信任，而信息技术，特别是密码技术，可以有效支撑这一产业，促进各种产业的透明化和可信任性。,思考题与习题,Hash,函数和纠错编码都是要校验，它们有什么本质性的差别，为什么,hash,函数只能校验，却需要经过复杂的计算，需要很长的,hash,值？,听到密码学这个名词，你认为它主要是干什么的？能否在现有密码学的基础上拓展密码学的概念呢？,密码学往往是实现一些不可思议的问题，一些难题，密码学的许多安全需求就是给我们出难题，这些问题对你有何启发？,思考题与习题,信息系统中压缩、纠错和加密的顺序可以是任意的吗？试着从多方面进行分析，比如压缩的效果、运算量、安全性等？,分组密码和流密码加密后的密文的压缩效果如何，比较两种加密情况下的压缩效果，并且分析加密前后的压缩效果？,思考题与习题,在前面针对密码系统的一些结论中，有些只是针对于常用的、简单的密码体制，对于特别的密码体制不一定成立，寻找这些结论，并且试图打破这些结论，寻找新的密码体制，使得它具有新的安全价值。,密码分析的方法有哪些？,古