信息安全专题讲座-02

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第二章 经典密码学,加密通信的模型,Alice,加密机,解密机,Bob,安全信道,密钥源,Oscar,x,y,x,k,密码学的目的,：,Alice,和,Bob,两个人在不安全的信道上进行通信，而破译者,Oscar,不能理解他们通信的内容。,定义,:(密码体制）,它是一个五元组（,P,C,K,E,D,),满足条件：,（1）,P,是可能明文的有限集；（明文空间）,（2）,C,是可能密文的有限集；（密文空间）,（3）,K,是一切可能密钥构成的有限集；（密钥空间）,*（4）任意,有一个加密算法 和相应的解密算法,，使得 和 分别为加密解密函数，满足,。,注：1,*,.,Alice,要将明文,在不安全信道上发给,Bob，,设,X=x,1,x,2,x,n,其中,Alice,用加密算法,e,k,作,y,i,=e,k,(x,i,),1,i,n,结果的密文是,Y,=,y,1,y,2,.y,n,在信道上发送，,Bob,收到后解密：,x,i,=d,k,(y,i,),得到明文,X=x,1,x,2,x,n.,。,2,*,.,加密函数,e,k,必须是单射函数，就是一对一的函数。,3,*,.若,P=C,，,则,e,k,为一个置换。,4,*,.好的密钥算法是唯密钥而保密的。,5,*,.,若,Alice,和,Bob,在一次通信中使用相同的密钥，那么这个加密体制为对称的，否则称为非对称的。,1.移位密码体制,设,P=C=K=Z,/(26),对,定义,同时,d,k,(y)=y-k,(mod 26),注1,*,：26个英文字母与模26剩余类集合0,.,25建立一一对应：,A B C D E F G H I J K L M N O P Q R S T U V W X Y Z,0,1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25,2,*,.,当,k=3,时，为,Caesar,密码：,若明文：,meet me after the toga party,密文：,PHHW PH DIWHO WKH WRJD SDUWB,实际算法为：有,同时有，,d,3,(,y,)=,y,-3(mod 26),3,*,.一个密码体制要是实际可用必须满足的特性,每一个加密函数,e,k,和每一个解密函数,d,k,都能有效地计算。,破译者取得密文后，将不能在有效的时间内破解出密钥,k,或明文,x,。,一个密码体制是安全的必要条件穷举密钥搜索将是不可行的，即密钥空间将是非常大的。,2.替换密码体制,设,P=C=Z,/(26)，,K,是由26个符号0，1,.,25的所有可能置换组成。任意,，,定义,d,(,y,)=,-1,(,y,)=,x,-1,是,的逆置换。,注：,1,*,.,置换,的表示：,2,*,密钥空间,K,很大，|,K,|=26!410,26,，,破译者穷举搜索是不行的，然而，可由统计的方式破译它。,3,*,移位密码体制是替换密码体制的一个特例，它仅含26个置换做为密钥空间,3.仿射密码体制,替换密码的另一个特例就是仿射密码。,加密函数取形式为,要求唯一解的充要条件是,gcd(a,26)=1,该体制描述为：,设,P=C=Z,/(26),对,定义,e,k,(,x,)=,ax,+,b,(mod 26),和,d,k,(,y,)=,a,-1,(,y-b,)(mod 26),例子，设,k,（7，3），,注意到7,-1,(,mod 26)=15,加密函数是,e,k,(,x,)=7,x,+3,相应的解密函数是,d,k,(,y,)=15(,y,-3)=15,y,-19,易见,d,k,(,e,k,(,x,)=,d,k,(7,x,+3)=15(7,x,+3)-19,=,x,+45-19,=,x,(mod 26),若加密明文：,hot，,首先转换字母,h,o,t,成为数字7,14,19,然后加密：,解密：,4.维吉尼亚密码,(,Vigenere),设,m,为一固定的正整数，定义,P=C=K=,(,Z,/(26),m,对一个密钥,K,（,k,1,k,2,k,m,),定义,e,k,(,x,1,x,2,x,m,)=(,x,1,+k,1,x,2,+k,2,x,m,+k,m,)=,y,d,k,(,y,1,y,2,y,m,)=(,x,1,-k,1,x,2,-k,2,x,m,-k,m,)=,x,这里的所有的运算都是在（,mod 26),中进行的。,注：维吉尼亚密码是多表替换体制，分析起来更困难。密钥空间大，如当,m,=5,时，密钥空间所含密钥的数量是1.110,7,5.,Hill,密码体制,设,为某个固定的正整数，,P=C=,(,Z,/(26),m,K,=,Z,/(26),上的,m,m,可逆矩阵,对每一个,定义,e,k,(,x,)=,xK,(mod 26),和,d,k,(,y,)=,yK,-1,(mod 26),注：明文与密文都是,m,元的向量,（,x,1,x,2,x,m,);(y,1,y,2,y,m,)，Z/(26),为同余类环。在这个环上的可逆矩阵,A,mxm,是指行列式,detA,mxm,的值,Z,*,/(26),它为,Z/(26),中全体可逆元的集合。,Z,*,/(26)=a,Z/(26)|(a,26)=1，,Z,*,/(26)=1,3,5,7,9,11,15,17,19,21,23,25,例子：当,m=2,时，明文元素,x=(x,1,x,2,),密文元素,y=(y,1,y,2,),(y,1,y,2,)=(x,1,x,2,),K,事实上,y,i,为,x1,x2,的线性组合，,y,1,=11x,1,+3x,2,;y2=8x,1,+7x,2,，,一般，将取,mm,的矩阵,K,作为我们的密钥：有,y=(y,1,y,2,y,m,)=(x,1,x,2,x,m,),换言之，,y=xK;,且有,x=yK,-1,若,K=,可得,K,-1,=,若对明文,july,加密，它分成2个元素（,j,u),(l,y),分别对应于（9,20）,（11,24）,有,（9,20）,（9960,72140）（3,4）,且,（11,24）,(12172,88168)（11,22）,于是对 july加密的结果为DELW。为了解密，B,ob,计算,且,因此，得到了正确的明文“,july”,6.置换密码体制,设,m,为固定的正整数，,P=C=(Z/(26),m,K,是由1,2,.,m,的所有置换构成，对一个密钥,K，,定义,e,(x,1,x,2,.,x,m,)=(x,(1),.,x,(m),),和,d,(y,1,y,2,.,y,m,)=(y,(1),.,y,(m),),这里,1,为,的逆置换。,注：这里的加密与解密仅仅用了置换，无代数运算。,例子：,设,m=6,取密钥,而,若给定的明文是：,cryptography,首先找分成6个字母长的,明文组：,crypto|graphy,求得的密文是：,YTCOPRAHGYPR,注：事实上，置换密码是,Hill,密码的特例。给定一个集合1,2,.,m,的置换矩阵,(,置换矩阵是每一行和每一列刚好在一个,“,1,”,，而其余元素为,“,0,”,的矩阵。),对上面例子决定的置换,对应：,密码分析,假设破译者,Oscar,是在已知密码体制的前提下来破译,Bob,使用的密钥。这个假设称为,Kerckhoff,原则。最常见的破解类型如下：,1.唯密文攻击：,Oscar,具有密文串,y.,2.,已知明文攻击:,Oscar,具有明文串,x,和相应的密文,y.,3.,选择明文攻击：,Oscar,可获得对加密机的暂时访问，因此他能选择明文串,x,并构造出相应的密文串,y。,4.,选择密文攻击:,Oscar,可暂时接近密码机,可选择密文串,y，,并构造出相应的明文,x.,5.,这一切的目的在于,破译出密钥,