信息的加密课件

,管理信息学 杨善林 刘业政编著,第6章 信息的加密,62,信 息 加 密,计算机和通信网络的广泛应用，一方面为人们的生活和工作带来了极大的方便，但另一方面也带来了许多亟待解决的问题，信息安全就是一个突出问题。密码技术是保证信息安全的关键技术。信息安全性主要有两个方面：信息的保密性和认证性。保密的目的是防止对手破译系统中的机密信息。认证的目的有两个，一个是验证信息发送者是真的而不是冒充的；另一个是验证信息的完整性，在处理过程中没有被窜改等。,6.1,密码学的基本概念,密码学由密码编码学与密码分析学两个分支组成。密码编码学是研究如何保证信息保密性与认证性的方法，密码分析学是研究如何破译密码或制造伪信息。,信息加密的,目的,：未授权者不能得到信息。称待加密的信息为,明文,，加密后的信息为,密文,或密码；称将明文变换成密文的过程为,加密,，将密文译成明文的过程为,解密,；称将明文变换成密文的运算方法为,加密算法,，将密文译成明文的运算方法为,解密算法,。,6.1,密码学的基本概念,称用来控制加密算法和解密算法的密钥为,加密密钥,与,解密密钥,。根据密钥的特点，密码体制分为私钥密码体制与公钥密码体制。在,私钥密码体制,中，加密密钥与解密密钥是相同的或从一个容易推出另一个；在,公钥密码体制,中，加密密钥与解密密钥不同或从一个很难推出另一个。根据加密的方式不同，又可将密码分为流密码和分组密码。在,流密码,中，将明文按字符一个一个地加密；在,分组密码,中，将明文分成若干个组，每组含多个字符，一组一组地加密。,6.1,密码学的基本概念,非法攻击密码,被动攻击：未授权者通过各种可能的手段获取密文，并通过各种分析手段推断出明文的过程,(,破译,),。,主动攻击：非法入侵者通过各种手段进入密码通信系统，并通过可能的方法删改、伪造信息以达到破坏密码的通信系统。,破译或攻击密码的方法：,穷举法,是指用各种可能的密钥去试译密文，直到得到有意义的明文的方法。,分析方法,是指通过数学关系式或统计规律找出明文或与明文相关的有用信息的破译方法。,6.1,密码学的基本概念,可破密码：如果一个密码在规定的时间内，通过密文能确定明文或密钥，或通过一定量的明文与密文的对应关系能确定密钥，则称这个密码是可破的；否则，称密码是不可破的。,破译或攻击类型,惟密文攻击,(,Cipher-Text-Only Attack)：,密码分析者有一个或更多的用同一个密钥加密的密文，通过对这些截获的密文进行分析得出明文或密钥。,6.1,密码学的基本概念,已知明文攻击(Know Plaintext Attack)：除要破译的密文外，密码分析者有一些明文和用同一密钥加密这些明文所对应的密文。,选择明文攻击(Chosen Plaintext Attack)：密码分析者可得到所需要的任何明文所对应的密文，这些密文与要破译的密文是用同一个密钥加密得来的。,选择密文攻击(Chosen Cipher-Text Attack)：密码分析者可得到所需要的任何密文所对应的明文，解密这些密文所使用的密钥与要破译的密文的密钥是相同的。,6.1,密码学的基本概念,四种攻击类型的强度按序递增，惟密文攻击最弱，选择密文攻击最强。选择密文攻击主要用于公钥密码体制。,密码通信系统,明文,m,加密器：密文,c,=,E,k,1,(,m,),非法入侵者,密码破译者,加密密钥源,解密密钥源,解密器：,m,=,D,k2,(,c,),明文,m,m,m,k,1,k,2,c,c,c,1,6.1,密码学的基本概念,认证系统：防止消息被攻击者删改或伪造。使发送的信息具有被验证的能力，使接受者或第三者能够识别和确认信息的真伪。,6.2,密码学的复杂性理论,密码学的复杂性理论由算法复杂性与问题复杂性两方面组成，它是比较不同的密码技术与算法的复杂性与安全性的理论依据。,1,.,算法复杂性,时间复杂性和空间复杂性。由算法所需要的最大时间,T,和最大存储空间,V,度量，它们依赖于解决实例时所需要输入数据的长度,n,，,一般表示为,T,(,n,),与,V,(,n,)。,在实际应用中常用平均时间复杂函数与平均空间复杂函数表示算法的复杂性。,6.2,密码学的复杂性理论,算法的复杂性通常用,n,的数量级表示。如果存在正常数,k,1,k,2,及,N,使得对一切,n,N,有：,则称,f,(,n,),与,h,(,n,),为同数量级的，记为,f,(,n,)=,O,(,h,(,n,)。,容易证明，当,f,(,n,),是,n,的,k,次多项式时，则,f,(,n,)=,O,(,n,k,)，,即所有低阶项与常数项可忽略不计。,多项式时间算法：,f,(,n,)=,O,(,n,k,),指数时间算法：,f,(,n,)=,O,(,h,(,n,),)(,1),6.2,密码学的复杂性理论,例 若一台计算机每秒能执行,10,6,条指令，当,n,=10,6,时，若,T,(,n,)=,n,，,则所需计算时间为,1,秒；若,T,(,n,)=,n,2,，,则所需计算时间为,(10,6,),2,/10,6,秒，相当于,11.6,天；若,T,(,n,)= 2,n,，,则所需时间大约为,310,301016,年。由此可见，当,n,很大时，不同类型的算法的复杂性可能差别很大。,2,.,问题复杂性,图灵机（,Turing Machine）：,一种具有无限读写能力并可做无限个并行操作的理想计算机。,6.2,密码学的复杂性理论,P,问题与,NP,问题：如果图灵机每一步操作结果是惟一确定的，则称它为,确定型图灵机,；如果每一步操作结果或下一步操作都可能有多种选择，则称该机为,不确定型图灵机,。在确定型图灵机上可用多项式时间解决的问题，被认为是,易解问题,，易解问题的全体称为,确定型多项式时间可解类,，记为,P。,不确定型图灵机工作分猜测与验证,2,个阶段，所谓一个问题在不确定型图灵机上可用多项式时间解决，是指若图灵机猜测一个解，则它可以在多项式时间内验证,(,不是求出,),此解正确与否。,6.2,密码学的复杂性理论,在不确定型图灵机上可以用多项式时间解决的问题，称为非确定性多项式时间可解问题，简称,NP,问题,，,NP,问题全体称为非确定性多项式时间可解类，仍记为,NP。,显然，,P,NP，,因为在确定型图灵机上多项式时间可解的任何问题在不确定型图灵机上也是多项式时间可解的，此时无需猜测阶段。,例1,背包问题：给定,n,个整数的集合,和一个整数,N,，,决定是否存在一个子集,S,，,使得,S,中的所有数之和为,N,。,解 因为对于一个给定的子集,S,，,可在多项式时间内验证其和是否为,N,。,然而要找,A,的一个子集,S,使其和等于,N,，,其时间复杂性,T,=,O,(2,n,) ，,这是因为,A,共有,2,n,个不同的子集。,6.2,密码学的复杂性理论,1.,流密码,在流密码中，将明文,m,写成连续的符号,m,=,m,1,m,2,，利用密钥流,k,=,k,1,k,2,中的第,i,个元素,k,i,对明文中的第,i,个元素,m,i,进行加密，若加密变换为,E,，则加密后的密文,c,=,E,k,(,m,)=,E,k,1,(,m,1,),E,k,2,(,m,2,),E,ki,(,m,i,)。设与加密变换,E,对应的解密变换为,D,，其中,D,满足,D,ki,(,E,ki,(,m,i,)=,m,i,i,=1,2,，则通过解密运算可译得明文为,m,=,D,k,(,c,)=,D,k,1,(,E,k,1,(,m,1,),D,k,2,(,E,k,2,(,m,2,)=,m,1,m,2,，从而完成一次密码通信。,6.3,私钥密码算法,例,2,设明文、密钥、密文都是,F,2,上的二元数字序列，明文,m=m,1,m,2,，,密钥为,k=k,1,k,2,，,若加密变换与解密变换都是,F,2,中的模,2,加法，试写出加密过程与解密过程。,6.3,私钥密码算法,加密算法,E,解密算法,D,明文,m,i,密文,c,i,=,E,ki,(,m,i,),明文m,i,=,D,ki,(,c,i,),密钥,k,i,密钥,k,i,流密码通信模式框图,解,经加密变换得密文,C=E,k,(,m,),=E,k1,(,m,1,),E,k2,(,m,2,),=,(,k,1,+m,1,),(,k,2,+m,2,),经解密变换得：,D,k,(,c,),=D,k,(,k,1,+m,1,)(,k,2,+m,2,),),=,(,k,1,+k,1,+m,1,)(,k,2,+k,2,+m,2,),由于,k,i,F,2,，则,k,i,+k,i,=0，,i,=1，2，故,D,k,(c)=m,1,m,2,=m,。,由于密钥,k,可由明文,m,与密文,C,进行模,2,加获得，易受到已知明文的攻击。用该密码系统通信就要求每发送一条消息都要产生一个新的密钥即“,一次一密,”。,6.3,私钥密码算法,一次一密,系统是无条件安全保密系统，但很不实用。在实际中，人们设计一个密码系统的目标是一个密钥能用来加密很多消息，或一个密钥能用来加密一条更长的明文，只要求计算上是安全的。所谓,计算上是安全的,是指利用已有的最好的方法破译该系统所需的努力超过了密码分析者的破译能力,(,诸如时间、空间和资金等资源,),或破译该系统的难度等价于解数学上的某个已知难题。,6.3,私钥密码算法,1.,密钥流生成器,如果密钥流经过,d,个符号之后重复，则称该流密码是,周期,的。密钥流元素,k,j,的产生由第,j,时刻流密码的内部状态,s,j,和实际密钥,k,决定，记为,k,j,=f,(,k，,s,j,)。,加密变换,E,kj,与解密变换,D,kj,都是时变的。加密器中存储器的状态,s,随时间变化而变化，用状态转移函数,f,s,表示。如果,f,s,与输入的明文无关，则密钥流,k,j,与明文无关，,j,时刻输出的密文,c,j,=,E,kj,(,m,j,),与,j,时刻之前的明文也无关，称此种流密码为,同步流密码,。,6.3,私钥密码算法,在同步流密码中，只要发送端和接收端有相同的实际密钥和内部状态，就能产生相同的密钥流，此时发送端和接收端的密钥生成器是同步的。一旦不同步，解密工作立即失败。如果状态转移函数,f,s,与输入的明文符号有关，则称该流密码为自同步流密码。目前应用最广泛的流密码是同步流密码。,密钥流生成器：使用线性变换。密钥流生成器的,目的,是由一个短的随机密钥,k,生成一个长的密钥流，再对明文加密或对密文解密。,6.3,私钥密码算法,密钥流不可测性：即要求生成的密钥流具有随机性，从而使密码分析者不可能从截获的,i,比特子段生成大于,i,比特的密码。,构造方法可分为四类：信息论方法、系统论方法、复杂度理论方法和随机化方法。,用已知方法构造出的大多数密钥流生成器已被证明是不安全的，仅有,少数还没有,被证明是不安全的。但现在被认为是安全的密码，都是基于世界上某个数学难题没有解决，一旦这个数学问题被解决，与之同难度的密码系统就不安全了。,6.3,私钥密码算法,2.,收缩密钥流生成器,移位寄存器,n,个小方框是,n,个,寄存器，从左到,右依序为第,1、2、,n,级,寄存器。开始时，若第,i,级内容是,a,n-i,，,则,此寄存器的初始状态是,(,a,0,，a,1,，a,n-1,)。,当加上一个脉冲时同时完成三项工作：,（,1,）,各级内容送给运算器,f(x,0,，x,1,，x,n-1,) ；,（2）,每个寄存器的内容移给下一级，第,n,级内容输出；,（,3,）运算器结果,a,n,=f,(,a,0,，a,1,，a,n-1,),反馈到第一级。,6.3,私钥密码算法,f,(,x,0,，x,1,， ，x,n-1,),此时移位寄存器的状态就是,(,a,1,，a,2,， a,n,)，,而输出是,a,0,。,不断地加脉冲，上述,n,级移位寄存器的输出就是一个,2元(或,q,元),序列：,a,0,，a,1,，a,2,，,在运算器中若,f,(,x,0,，x,1,，x,n-1,),给定，则输出序列完全由初始状态,(,a,0,，a,1,，a,n-1,),确定。当,f(x,0,，x,1,，x,n-1,),为线性函数时，称该移位寄存器为,n,级线性移位寄存器,；否则为,n,级非线性移位寄存器。代数编码中已证明移位寄存器产生的序列都是周期序列，周期都,2,n,。,6.3,私钥密码算法,例3,给定一个,4,级线性移位寄存器如图。给定初状态,(0001),，求该移位寄存器产生的周期序列。,解 易见,f,(,x,0,，x,1,，x,2,，x,3,),= x,0,+x,1,，,因此对,k,4,有,a,k,=a,k-3,+a,k-4,从而该,4,级移位寄存器产生的序列是周期,15,的序列：,1111,移位寄存器,(,SR),可由短的序列生成具有一定规律的长序列。这种序列便可以作为密钥流序列，但抗攻击能力较差。,6.3,私钥密码算法,通常的密钥流生成器都是由若干个移位寄存器并联，并且与特殊的电子电路组合而成,(,如图,),。可通过,SR,1,的输出选择,SR,2,的输出来生成密钥流。,6.3,私钥密码算法,收缩密钥流生成器,SR,1,y,i,(1),y,i,(2),输出,k,i,SR,2,收缩密钥流生成器的,工作模式,输入：参数：两个移位寄存器的级数及反馈函数,密钥：两个移位寄存器的初始状态,(1),移位,SR,1,并产生,y,i,(1),；,同时移位,SR,2,并产生,y,i,(2),；,(2),如果,y,i,(1),=1，,则输出密钥元素,ki,= y,i,(2),；,如果,y,i,(1),=0，,则删去,y,i,(2),，i=1，2， 。,由此收缩生成器产生的密钥流为,k,i,|,i,1。,6.3,私钥密码算法,3,. 分组密码,分组密码,是将明文消息编码表示后的数字序列划分成长为,m,的组,x=,(,x,1,，x,2,，,x,m,)，,各组分别在密钥,k=,(,k,1,，k,2,，,k,t,),的控制下变换成长为,n,的密文,y=,(,y,1,，y,2,，,y,n,),。,6.3,私钥密码算法,分组密码通信模式框图,加密算法,解密算法,明文,x=,(,x,1,，x,2,，x,n,),密文,y=,(,y,1,，y,2,，y,n,),密钥,k=,(,k,1,，k,2,，k,t,),明文,x=,(,x,1,，x,2,，x,n,),密钥,k=,(,k,1,，k,2,，k,t,),分组密码与流密码的,区别,在于输出的每一位数字不是与相应时刻输入的明文数字有关，而是与一组长为,m,的明文数字有关。分组密码的,优点,是容易标准化且容易实现同步，,缺点,是相同的密文组蕴含相同的明文组。在分组密码通信中，通常明文与密文长度相等,(,=,分组长度,),。设明文与密文空间均为,F,2,n,，,密钥空间为,S,k,，,则加密函数,y=E(x,k),和解密函数,x=D(y,k),都是,F,2,n,到,F,2,n,的一个置换。好的分组密码应该难破译、易实现，即,E(x,k),和,D(y,k),都必须很容易计算，但要从方程,y=E(x,k),和,x=D(y,k),中求出,k,应该是一个很困难的问题。,6.3,私钥密码算法,DES（,美国商业部的数据加密标准）算法,DES,算法使用长度为,56,比特的密钥加密长度为,64,比特的明文，获得长度为,64,比特的密文，工作程序：,给定一个明文,x,，,通过一个固定的初始变换,IP,将,x,变换为,x,0,，,记,x,0,=IP(,x,)=,L,0,R,0,，,这里,L,0,是,x,0,的前,32,比特，,R,0,是,x,0,的后,32,比特。,接着进行,16,轮完全相同的运算，在这里数据与密钥相结合。根据下列规则计算,L,i,R,i,，,i,=1，2，16：,L,i,=R,i-1,R,i,=L,i-1,f (R,i-1,，k,i,),6.3,私钥密码算法,函数,f(R,i-1,k,i,),中,R,i-1,是一个长度为32的比特串，,k,i,(,i,=1,16)是一个长度为48的比特串，是密钥,k,的函数；,f,函数值是一个长度为32的比特串；,表示两个比特串的异或。,对比特串,R,16,L,16,应用初始变换IP的,逆变换,IP,-1,，即得密文,y=IP,-1,(,R,16,L,16,)。,DES,的解密采用同一算法实现，,把密文,y,作为输入，倒过来使用,密钥方案，即以逆顺序,k,16,k,1,使用密钥方案，输出的将是明文,x,。,6.3,私钥密码算法,一轮DES加密过程,L,i-1,R,i-1,L,i-,R,i,k,i,f,+,在私钥密码体制中，解密密钥与加密密钥相同或容易从加密密钥导出。存在的问题：,加密密钥的暴露会使系统变得不安全；,在传送密文前，发送者和接收者必须使用一个安全信道预先通信密钥,k,，在实际通信中是很困难的。,1. 公钥密码体制及其设计的基本原理,在公钥密码中，解密密钥和加密密钥不同，从一个难于推出另一个，解密和加密是可分离的，加密密钥是可以公开的。信息可通过编码被加密在一个NP-完全问题之中，以普通方法破译该密码等价于解一个NP-安全问题。,6.4,公钥密码算法,公钥密码体制的基本原理,-,陷门单向函数,(,troop-door one-way function),如果函数,f,(,x,),满足：对,f,(,x,),的定义域中的任意,x,，,都容易计算函数值,f,(,x,)，,而对于,f,(,x,),的值域中的几乎所有的,y,，,即使已知,f,要计算,f,-,-1,(,y,),也是不可行的，则称,f,(,x,),是单向函数,。,若给定某些辅助信息时又容易计算单向函数,f,的逆,f,-1,，,则称,f,(,x,),是一个陷门单向函数。这一辅助信息就是秘密的解密密钥。,公钥密码体制的安全性是指计算安全性，不是无条件的，这是由求,f,-1,的复杂性决定的。,6.4,公钥密码算法,例 设,n,是两个大素数,p,和,q,的乘积，,b,是一个正整数，对,x,Z,n,，,令,f(x),x,b,(mod,n,),，,即,f(x),等于被,n,除所得的余数，人们认为,f(x),是一个从,Z,n,到,Z,n,的单向函数,2,RSA,密码体制,定义,6.1 设,m,，,n,是两个整数，如果正整数,d,满足：,(1),d,整除,m,和,n,，,即,d,|,m,，,d,|,n,;,(2),若,d,|m,且,d,|n，,则,d,|,d,。,则称,d,是,m,与,n,的最大公因数，记为,d,=,(m，n),。,若,(,m，n),=1，,则称,m,与,n,互素。,6.4,公钥密码算法,设,n,是任一自然数，记,1，2，,n,-1,中与,n,互素的数的个数为,(,n,)，,并称,(,n,),为欧拉,(,Euler),函数。,定理,6.1,设,Z,*,n,=,m,|(,m,，,n,)=1，1,m,n,-1，,则对,a,Z,*,n,，,有,a,(,n,),1 (,mod,n,),设,n,=,pq,，,其中,p,与,q,是不同的素数，则,(,n,)=(,p,-1)(,q,-1),定理,6.2,设,p,与,q,是两个不同的素数，,n,=,pq,，,则对任意的,x,Z,n,=0，1，2，,n,-1,及任意的非负整数,k,，,有,x,k,(,n,)+1,x,(mod,n,),6.4,公钥密码算法,RSA,算法,设,p,，,q,是两个不同的奇素数，,n=,pq,，,则,(,n,)=(,p,-1)(,q,-1)，,密钥,k,=(,n,，,p,，,q,，,a,，,b,)|,ab,1(mod,(,n,)，,a,，,b,Z,*,n,),对每一个,k,=(,n，p，q，a，b,)，,定义加密变换为,E,k,(,x,),x,b,(,mod,n,)，,x,Z,n,定义解密变换为,D,k,(,y,),y,a,(,mod,n,)，,y,Z,n,RSA,密码体制是公开加密密钥,n,与,b,，,保密解密密钥,a,以及辅助信息,p,与,q,6.4,公钥密码算法,定理,6.3,设,E,k,与,D,k,分别是,RSA,体制中的加密变换和解密变换，则对一切,x,Z,n,有,D,k,(,E,k,(,x,)=,x,例 设用户,A,选择两个素数,p,=5，,q,=7，,则,n=,pq,=,35，,(,n,)=(5-1)(7-1)=24。,A,取,a,=11,Z,*,35,，,再由,Euclidean,算法求出,b,=,a,-1,(mod(,n,)。,A,公开,n,=35,和,b,=11，,保密,p,=5，,q,=7,和,a,=11。,现在用户,B,想把明文,x,=2,Z,35,发送给,A,。,B,加密明文,x,=2,得密文：,y,=,E,k,(x),x,b,(mod35)2,11,(mod35)=18；,B,在公开信道上将加密后的密文,y,=18,发送给,A,，,当,A,收到密文,y,=18,时，,A,解密可得：,y,a,=18,11,2 (mod35)，,从而,A,得到,B,发送的明文,x,=2。,6.4,公钥密码算法,RSA,算法的安全性是基于分解大整数,n,的困难性。目前大整数分解算法能力：分解,130,位的十进制数,!,基于安全性考虑，用户选择的素数,p,和,q,大约都为,100,位的十进制数，那么,h=,pq,将是,200,位的十进制数。,建立过程：,(1),找到两个大素数,p,与,q,(,p,与,q,相差也很大,);(2),计算,n,和,(,n,);(3),随机选择一个数,b,使得,(,b,(,n,)=1,0,b,(n); (4),利用,Euclidean,算法,计算,a,=,b,-1,(mod(,n,);(5),将,n,与,b,作为他的公钥直接公开，以便让所有想给他发送想保密的信息加密。,6.4,公钥密码算法,1. 数字签名方案概述,数字签名：,适应信息化需要；,异地签名。,数字签名过程：设厂长使用,RSA,密码体制，厂长的加密密钥为,E,k,，,是公开的，解密密钥为,D,k,，,只有厂长本人知道，则,(1),将附上数据,x,的合同发给厂长,；(2),厂长用解密密钥,D,k,对数据,x,作运算,y=,D,k,(x),，,结果为厂长的数字签名；,(3),用厂长的公开加密密钥作运算,x=,E,k,(y)，,如果,x=x,，,则可证实厂长的签名为真；否则为假。因为,E,k,(,D,k,(,x,),D,k,(,E,k,(,x,),x,(,mod,n,)，,而,D,k,是惟一的且只有厂长本人知道,。,6.5,数字签名方案,一般地，一个数字签名方案主要由签名算法,S(),和验证算法,V(),组成。签名者使用一个只有本人知道的,S(),签一个消息,x,得,S(x),，,接受者使用签名者公开的,V(),验证其签名的真伪。,2.,RSA,签名方案,设,p,与,q,是两个不同的素数，,n=,pq,，,(,n,)=(,p,-1)(,q,-1)。,任取一个与,n,互素且小于,n,的数,a,，,由,ab,1(mod,(,n,),求得唯一的解,b,，1,b,n,。,公开,n,与,a,，,保密值,p,，,q,和,b,。,对,x,Z,n,，,定义签名算法,S,(),为,S(x),x,b,(,mod,n,)；,对,y,Z,n,，,定义验证算法,V(),为,V,(,y,),y,a,(,mod,n,)，,则签名为真的充要条件是,V,(,S,(,x,),x,(,mod,n,)。,由于,S,(),只有签名者一人知道，因此只有他能给出真的签名。,6.5,数字签名方案,3. OSS签名方案,选择一个大的自然数,n,，并随机地选择一个自然数,k,使(,k,n,)=1，即,k,与,n,互素。由,h,-k,-2,(mod,n,)计算,h,。公开,n,和,h,，保密,k,，即,n,与,h,是验证密钥，,k,是签字密钥。签名者对信息,x,签名时，再随机选择一个与,n,互素的自然数,m,，签字算法为：,将,S,1,(,x,)与,S,2,(,x,)一起作为签名发送给接受方。验证算法为：,如果,V,(,S,1,(,x,)，,S,2,(,x,),x,(mod,n,)，则签名为真；否则为假。,6.5,数字签名方案,4. 数字签名的发展与挑战,数字签名既可使用私钥密码体制又可使用公钥密码体制，目前研究和使用的都是公钥密码体制。要构造无条件安全的公钥密码体制几乎是不可能的。目前所用的公钥密码体制都是基于以下三种数学疑难问题之一：,（1）由Diffie提出的背包问题：给定一个互不相同的数组成的集合，如何找出一个子集，使其元素之和为,N,。,（2）由Gill提出的离散对数问题：设,p,是素数，,k,与,m,是整数，如何找,x,使下式成立：,k,x,m,(mod,p,),6.5,数字签名方案,6.5,数字签名方案,据介绍，具有,5000,个量子位的量子计算机，可以在,30,秒内解决传统超级计算机要,100,亿年才能解决的大数因子分解问题。由于具有强大的并行处理能力，量子计算机将对现有的保密体系产生根本性的冲击,（3）由Knuth提出的因子分解问题：设,n,是两个不同的大素数乘积，如何分解,n,?,一旦这些数学难题取得突破性进展，将使所有公开密钥体制以及以公开密钥体制为基础的数字签名方案不安全。,6.6,识 别 协 议,1. 识别协议概述,当一个用户,A,需要在某个信息系统中确认自己身份时，一般的做法是输入自己和计算机都知道的一个密码。由于,A,每次进入计算机时都要键入这个密码，而能够访问用户,A,的数据通道的任何人或能访问计算系统的存储器的任何人都可以看到用户,A,的密码，因此系统存在严重的安全问题。需设计一种方案或协议使用户,A,既能进入计算机又不泄露用户,A,的任何识别信息(即身份零知识证明)。,6.6,识 别 协 议,一个安全的识别协议至少应满足以下两个条件(智能卡)：,(1)用户,A,能向验证者,B,证明他的确是A；,(2)用户,A,向验证者,B,证明自己的身份时，没有让验证者,B,获得任何有用的信息，,B,不可能模仿,A,向其他人证明他是用户,A,。,2. Feige-Fiat-Shamir(FFS)识别协议,FFS,识别协议是由一个属于仲裁数字签名方案改进而成的,6.6,识 别 协 议,FFS,识别协议内容,可信仲裁方随机选取一个自然数,n,，,n,必须是两个不同的大素数的乘积，为了确保安全，,n,至少为,512,位长，最好接近,1024,位长。这个作为模数的,n,可以在一组证明者之间共享。可信仲裁方再选取一个自然数,v,，,v,必须是模,n,的平方剩余，即,x,2,v,(mod,n,),有小于,n,的整数解,x,。,而且,v,-1,(mod,n,),存在。,v,作为用户,A,(,证明者,),的公开密钥。再计算：,则,S,作为用户,A,的秘密密钥。,6.6,识 别 协 议,FFS,识别协议设计及通信过程,用户,A,随机选一个数,r,，,r,n,，,计算,x,r,2,(mod,n,)，,并将,x,发送给验证者；,验证者在,0与1,两个数中任选一个数,a,发送给用户,A,，,若,a,=0，,则用户,A,将,r,发送给验证者；若,a,=1，,则用户,A,计算,y,=,rs,(,mod,n,),并将,y,发送给验证者；,如果,a,=0，,则验证者验证同余式,x,r,2,(mod,n,),是否成立，若成立，则证实用户,A,知道 ；如果,a,=1，,则验证者验证同余式,x,vy,2,(mod,n,),是否成立，如果成立，则证实用户,A,知道,6.6,识 别 协 议,如果用户,A,知道 或 ，则验证者认为用户,A,为真；否则为假。这个协议是一次签定合格协议。用户,A,与验证者可以重复这个协议,t,次，直到验证者确信用户,A,知道,S,。(次数太多),3. 改进的FFS识别协议,设,n,是两个不同的大素数的乘积，先选取,k,个不同的数,v,1,，,v,2,，,v,k,，,v,i,是模,n,的平方剩余，且,v,i,-1,(mod,n,)存在，,i,=1，,k,。,v,1,，,v,2,，,v,k,作为用户,A,的公开密钥。再计算：,S,i, ，,i,=1，,k,则,S,1,，,S,2,，,S,k,为用户,A,的秘密密钥。,6.6,识 别 协 议,设计与通信过程,用户,A,选择一个随机数,r，rn，,并计算,x,r,2,(mod,n,)，,用户,A,将运算结果,x,发送给验证者；,验证者随机选取,k,个数,a,1,a,2,a,k,，,每个,a,i,可取,0或1,，并将,(,a,1,a,2,a,k,),发送给用户,A,，,用户,A,收到,(,a,1,a,2,a,k,),后计算：,并将计算结果,y,发送给验证者；,验证者验证同余式 是否成立，若成立，则证明用户,A,知道密钥,S,1,S,2,S,k,。,否则否定用户,A,。,6.6,识 别 协 议,改进后的,FFS,识别协议也可重复多次，直到验证者满意为止。若重复这种识别协议,t,次，验证者被欺骗的概率为,(2,-,kt,),协议设计者建议使用,k,=9，,t,=8，,此时验证者被欺骗的概率几乎为,0。,例 设计一个,FFS,协议。,解,取,n,=57=35，,选择,v,1,=4，,v,2,=11，,v,3,=16，,v,4,=29。,注意,4，11，16，29,满足识别协议的要求，如同余式,x,2,4(mod35),有解,x,=2，,x,=12，,x,=23,或,x,=33，,且49=1(,mod35)，,即4,-1,(,mod35)=9,存在。,11，16，29,可类似的验证。,6.6,识 别 协 议,由同余式,可计算得,S,1,=3，,S,2,=4，,S,3,=9，,S,4,=8。,执行该协议一轮运算如下：,用户,A,选择一个随机数,r,=16，,由于,16,2,(,mod35)=11，,从而用户,A,将11,发给验证者；,验证者随机选择一个二元串,(,a,1,a,2,a,3,a,4,)=(1100),发送给用户,A,；,用户,A,收到,(1100),后可计算如下：,16,S,1,1,S,2,1,S,3,0,S,4,0,= 163,1,4,1,9,0,8,0,=1634=19217(mod35)；,用户,A,将17,发送给验证者；,6.6,识 别 协 议,验证者收到17后，计算如下：17,2,V,1,1,V,2,1,V,3,1,V,4,1,= 2894,1,11,1,16,0,29,0,=1271611(mod35),由于此结果与用户,A,第一次发送的,x,=11安全一样，因此可确认用户,A,知道,S,1,，,S,2,，,S,3,，,S,4.,如果有必要，可要求用户,A,再随机选,r,为其它数，重复上述步骤若干次，直到确信为止。,值得说明的是，如果用户,A,将,S,1,，,S,k,作为数字签名密钥，而将,v,1,，,v,k,作为公开验证密钥便得到的数字签名方案。而该数字签名方案与,RSA,签名方案相比，运算速度比,RSA,要快得多。,6.7,密 钥 管 理,1. 密钥管理的意义,2. 密钥的分类与产生,密钥的种类主要有用户密钥、会话密钥、密钥加密密钥和主机主密钥。,用户密钥,(,k,u,),是一对用户在较长时间段内所专用的秘密密钥；,会话密钥,(,k,s,),是两个通信终端用户在一次通话或交换数据时所用的密钥；,密钥加密密钥,(,k,e,),是对传送的会话密钥进行加密的密钥；,主机主密钥,(,k,m,),是对密钥加密密钥进行加密的密钥，存储在主机处理器中。,6.7,密 钥 管 理,密钥生成：关键是安全性，完全取决于产生密钥的算法，因此这种算法应满足如下要求：,生成密钥的算法应当能保证主机主密钥的产生具有随机性，避免可预测性；,在有,N,个终端的通信网中，即使有一个或数个密钥加密密钥被盗或泄露，生成密钥的算法应当能保证其它用户的密钥加密密钥仍有足够的安全性；,在密钥加密密钥控制下，生成密钥算法可以动态地生成会话密钥。,6.7,密 钥 管 理,3. 密钥的分配,在有,N,个终端的保密通信网络中，由于任意两个用户必须交换密钥，因此要有 个传送密钥的安全信道，即使借助一个可信中心可将安全信道从 降低到,N,个，但每个用户必须存储,N,-1,个密钥，但交换密钥的次数仍为 次。当,N,稍大时传输量与存储量都很大。因此，密钥分配方案应当确保网络的密钥传送次数和每个用户的存储量都尽可能的小，且每一对用户,A,与,B,都能独立地计算一个秘密密钥,K,AB,。,6.7,密 钥 管 理,Blom,密钥分配方案,在有,N,个用户的保密通信网络中，为了方便起见，假定密钥从集合,S,中选出，,S,含有,p,个元素，,p,为素数，,p,N,。,可信中心给每个用户在一个安全的信道上发送,S,中两个元素，每两个用户,A,与,B,都能计算一个密钥,K,AB,=,K,BA,。,安全条件为：任何单个用户,x,(,A,，,B,),不能确定,K,AB,的任何信息。分配方案：,公开一个素数,p,，,每个用户,A,公开一个元素,r,A,S,，,这些元素,r,A,互不相同；,6.7,密 钥 管 理,可信中心随机从,S,中选择三个元素,a,，,b,，,c,(可以相同)，并构造函数,f,(,x,，,y,)=(,a,+,b,(,x,+,y,)+,cxy,)(mod,p,),对每个用户,A,，可信中心计算函数值,g,A,(,x,),f,(,x,r,A,)(mod,p,)，并将,g,A,(,x,)在一个安全信道上传送给,A,；,如果用户,A,与,B,想通信，那么,A,与,B,分别计算密钥如下：,K,A，B,=,f,(,r,A,，,r,B,)=,g,A,(,r,B,)(mod,p,),K,B，A,=,f,(,r,B,，,r,A,)=,g,B,(,r,A,)(mod,p,),由于,f,(,r,A,，,r,B,)=,f,(,r,B,，,r,A,)，故他们可使用共同的密钥,K,AB,=,K,BA,通信。,6.7,密 钥 管 理,可以证明，没有一个用户能确定另外两个用户的密钥的任何信息，即Blom方案对任何单个用户而言是安全的，但任何两个用户,X,，,Y,A，B,都可以确定,K,AB,，即Blom方案对两个用户而言是不安全的。如果要求Blom方案对,k,个不同用户都不能确定,K,AB,，1,k,n,-2，Blom方案如下：,可信中心公开一个素数,p,，并给每个用户在一个安全的信道上发送,S,中,k,+1个元素,r,;,每个用户,A,公开一个元素,r,A,S,，这些元素,r,A,互不相同；,6.7,密 钥 管 理,可信中心选择元素,a,ij,=,a,ji,S,0,i,k,0,j,k,并构造函数,并对每个用户,A,，可信中心计算函数值,g,A,(,x,)=,f,(,x,r,A,)(mod,p,),并将结果,g,A,(,x,)在一个安全信道上传送给,A,；,如果,A,与,B,想通信，,A,，,B,分别计算：,K,AB,=,f,(,r,A,，,r,B,)=,g,A,(,r,B,)(mod,p,),K,BA,=,f,(,r,B,，,r,A,)=,g,B,(,r,A,)(mod,p,),由于,f,(,r,A,r,B,)=,f,(,r,B,r,A,),故,K,AB,=,K,BA,故,A,与,B,可用共同的密钥通信,6.7,密 钥 管 理,4. 密钥保护和秘密共享,密钥保护：常采用分级保护管理法，即大量的数据用少量动态产生的数据加密密钥进行保护，而数据加密密钥又用更少量的、相对不变的主机主密钥来保护。只有极少数密钥以明文形式,存储,在有严密的物理保护的主机密码器件中，其他密钥都以加密后的密码形式存于密码器之外的存,储,器中，简化了密钥管理，改善了密钥的安全性。为了确保密钥安全，在密码设备中都有防窜扰装置，当密封的关键密码器被撬开时，其主密钥和用户密钥都会自动被清除或启动装置自动引爆。,6.7,密 钥 管 理,秘密共享方案：基本要求,将密钥,k,按下述要求分成,n,个共享,k,1,，,k,2,，,k,n,：,(1),已知任意,t,个,k,i,值都容易计算出密钥,k,；,(2),已知任意,r,(,t,-1),个,k,i,的值，都无法计算出密钥,k,。,在秘密共享方案中，将,n,个共享,k,1,，,k,2,，,k,n,分给,n,个不同用户，由于要计算出密钥,k,至少要有,t,个共享，故即使有,r,个共享丢失或,r,个人背叛，都不会危及密钥,k,的安全；且若有,s,个共享被丢失或毁坏，只要有,t,个共享有效，则仍可计算出密钥,k,，,从而恢复密钥。,6.7,密 钥 管 理,Shamir,秘密共享方案,(,Shamir,门限方案,),设,p,是一个素数，共享密钥,k,K,=,Z,p,。,可信中心给,n,(,p,),个共享者,p,i,(1,i,n,),分配共享的过程如下：,(1,) 可信中心在,Z,p,中选择,n,个非零的互不相同的元素,x,1,，,x,2,，,x,n,，,并公开它们；,(2,) 可信中心随机选择一个,t,-1,次多项式：,f,(,x,)=,a,t,-1,x,t,-1,+,a,2,x,2,+,a,1,x,+,k,Z,p,x,并计算,y,i,=,f,(,x,i,)，,i,=1，2，,n,6.7,密 钥 管 理,(3) 可信中心将(,x,1,，,y,1,)，(,x,2,，,y,2,)，(,x,n,，,y,n,)分配给共享者,L,1,，,L,2,，,L,n,，其中,y,i,是,L,i,的秘密共享，,i,=1，2，,n,。,在,Shamir,秘密共享方案中，如果知道,t,个共享，不妨设为,y,1,，,y,2,，,y,t,，,则利用计算数学中的拉格朗日插值公式可计算出多项式,f,(,x,),为：,一旦求出,f,(,x,)，,则,k,=,f,(0)，,从而计算出密钥,k,。,而已知任何,r,个共享，,r,t,-1，,都无法计算出,f,(,x,)，,从而无法计算出,k,。,