密码的设计、解密与破译PPT.ppt

,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,密码的设计，解码与破译,密码的设计和使用至少可以追溯到四千多年前的埃及、巴比伦、罗马和希腊，历史极为久远。,古代,隐藏信息的方法主要有两大类：,其一,为,隐藏信息载体，采用隐写术,等；,其二,为,变换信息载体，使之无法为一般人所理解,。,密码学中，信息代码被称为,密码,，加密前的信息被称为,明文,，加密后不为常人所理解的用密码表示的信息称为,密文,(,ciphertext,),，将明文转变成密文的过程被称为,加密,(,enciphering,),，其逆过程则被称为,解密,(,deciphering,),，而用以加密、解密的方法或算法则被称为,密码体制,(,crytosystem,),。,1,记全体明文组成的集合 为,U,，全体密文组成的集合为,V,，称,U,为明文空间，,V,为密文空间。加密常利用某一被称为密钥的东西来实现，它通常取自于一个被称为密钥空间的含有若干参数的集合,K,。按数学的观点来看，加密与解密均可被看成是一种变换：取一,k,K,，,u,U,，令,v,=,k,u,，,v,为明文,u,在密钥,K,下的密文，而解码则要用到,K,的逆变换,K,-1,。由此可见，密码体系虽然可以千姿百态，但其关键还在于,密钥的选取,。,随着计算机与网络技术的迅猛发展，大量各具特色的密码体系不断涌现。离散数学、数论、计算复杂性、混沌、,，许多相当高深的数学知识都被用上，逐步形成了（并仍在迅速发展的）具有广泛应用面的,现代密码学,。,2,早期密码,替代密码,移位密码,代数密码,3,代替法密码,采用另一个字母表中的字母来代替明文中的字母，明文字母与密文字母保持一一对应关系，但采用的符号改变了。加密时，把明文换成密文，即将明文中的字母用密文字母表中对应位置上的字母取代。解密时，则把密文换成明文，即把密文中的字母用明文字母表中对应位置上的字母代回，解密过程是加密过程的逆过程。在代替法加密过程中，密文字母表即代替法密钥，密钥可以是标准字母表，也可以是任意建立的。,1.,代替法密码,明文字母表,ABCDEFGHIJKLMNOPQRSTUVWXYZ,密文字母表,KLMNOPQRSTUVWXYZABCDEFGHIJ,密钥常用一密钥单词或密钥短语生成混淆字母表。密钥单词 或密钥短语可以存放在识别码、通行字或密钥的秘密表格中。,4,混合一个字母表，常见的有两种方法，这两种方法都采用了一个,密钥单词,或一个,密钥短语,。,方法,1,：,a),选择一个密钥单词或密钥短语，例如：,construct,b),去掉其中重复的字母，得：,constru,c),在修改后的密钥后面接上从标准字母表中去掉密钥中已有的字母后剩下的字母，得：,明文字母表,ABCDEFGHIJKLMNOPQRSTUVWXYZ,密文字母表,CONSTRU,ABDEFGHIJKLMPQVWXYZ,在设计密钥时，也可在明文字母表中选择一个特定字母，然后从该特定字母开始写密钥单词将密钥单词隐藏于其中。例如，对于上例，选取特定字母,k,，则可得：,明文字母表,ABCDEFGHIJKLMNOPQRSTUVWXYZ,密文字母表,KLMPQVWXYZ,CONSTRU,ABDEFGHIJ,5,方法,2,：,a),选择一个密钥单词或密钥短语，例如：,construct,b),去掉其中重复的字母，得：,constru,c),这些字母构成矩阵的第一行，矩阵的后续各行由标准字母表中去掉密钥单词的字母后剩下的字母构成,d),将所得矩阵中的字母按列的顺序排出,得：,cugmyoahpznbiqsdjvrtekwrflx,按照此方法产生的字母表称为,混淆字母表,。,还可以使用,混淆数,。混淆数由以下方法产生：,a),选一密钥单词或密钥短语，例如：,construct,b),按照这些字母在标准字母表中出现的相对顺序给它们编号，对序列中重复的字母则自左向右编号，得 ：,construct,143675928,c),自左向右选出这些数字，得到一个混淆数字组,:143675928,，混淆字母表由从小到大的顺序取矩阵中相应列得出。,为增加保密性，在使用代替法时还可利用一些其他技巧，如单字母表对多字母表、单字母对多字母、多重代替等。,6,2,.,移位密码体制,移位密码,采用移位法进行加密，明文中的字母重新排列，本身不变，只是位置改变了。,早在,4000,多年前，古希腊人就用一种名叫“天书”的器械来加密消息。该密码器械是用一条窄长的草纸缠绕在一个直径确定的圆筒上，明文逐行横写在纸带上，当取下纸带时，字母的次序就被打乱了，消息得以隐蔽。收方阅读消息时，要将纸带重新绕在直径与原来相同的圆筒上，才能看到正确的消息。在这里圆筒的直径起到了密钥的作用。,以上移位较易被人破译，为打破字母表中原有的顺序还可采用所谓路线加密法，即把明文字母表按某种既定的顺序安排在一个矩阵中，然后用另一种顺序选出矩阵中的字母来产生密文表。,7,例如，对明文：,THE HISTORY OF ZJU IS MORE THAN ONE HUNDRED YEARS,.,以,7,列矩阵表示如下：,THEHIST,ORYOFZJ,UISMORE,THANONE,HUNDRED,YEARS,再按事先约定的方式选出密文。例如，如按列选出，得到密文：,touthyhrihueeysanahomndrifoorsszrnetjeed,使用不同的顺序进行编写和选择，可以得到各种不同的路线加密体制。对于同一明文消息矩阵，采用不同的抄写方式，得到的密文也是不同的。,当明文超过规定矩阵的大小时，可以另加一矩阵。当需要加密的字母数小于矩阵大小时，可以在矩阵中留空位或以无用的字母来填满矩阵。,8,移位法也可和代替法结合使用，并使用约定的单词或短语作密钥，以进一步加强保密性，这就是,钥控列序加密法,。,例如,，用密钥单词,construct,对明文,MATHEMATICAL MODELING IS USEFUL,加密：,CONSTRUCT,1 4 36 7 5 928,MATHEMATI,CALMODELI,NGI S USEFU,L,按混淆数的顺序选出各列，得到密文：,MCNLTLFTLIAAGMDSHMSEOSIIUAEE,移位法的使用可重复多次，只进行一次移位加密的称为一,次移位法,，经多次移位的则称 为,多次移位法,9,代替法与移位法密码的,破译,对窃听到的密文进行分析时，,穷举法,和,统计法,是最基本的破译方法 。,穷举分析法,就是对所有可能的密钥或明文进行逐一试探，直至试探到“正确”的为止。此方法,需要事先知道密码体制或加密算法,（但不知道密钥或加密具体办法）。破译时需将猜测到的明文和选定的密钥输入给算法，产生密文，再将该密文与窃听来的密文比较。如果相同，则认为该密钥就是所要求的，否则继续试探，直至破译。以英文字母为例，当已知对方在采用代替法加密时，如果使用穷举字母表来破译，那么对于最简单的一种使用单字母表单字母单元代替法加密的密码，字母表的可能情况有,26,！,种，可见，单纯地使用穷举法，在实际应用中几乎是行不通的，只能与其它方法结合使用。,10,统计法,是根据统计资料进行猜测的。在一段足够长且非特别专门化的文章中，字母的使用频率是比较稳定的。在某些技术性或专门化文章中的字母使用频率可能有微小变化。,在上述两种加密方法中字母表中的字母是一一对应的，因此，在截获的密文中各字母出现的概率提供了重要的密钥信息。根据权威资料报道，可以 将,26,个英文字母按其出现的频率大小较合理地分为五组：,t,a,o,i,n,s,h,r;,e;,d,l;,c,u,m,w,f,g,y,p,b;,v,k,j,x,q,z;,不仅单个字母以相当稳定的频率出现，,相邻字母对,和,三字母对,同样如此。,11,按,频率大小,将双字母排列如下：,th,he,in,er,an,re,ed,on,es,st,en,at,to,nt,ha,nd,ou,ea,ng,as,or,ti,is,er,it,ar,te,se,hi,of,使用最多的三字母按频率大小排列如下：,The,ing,and,her,ere,ent,tha,nth,was,eth,for,dth,统计的章节越长，统计结果就越可靠。对于只有几个单词的密文，统计是无意义的。,下面介绍一下统计观察的三个结果：,a),单词,the,在这些统计中有重要的作用；,b),以,e,，,s,，,d,，,t,为结尾的英语单词超过了一半；,c),以,t,，,a,，,s,，,w,为起始字母的英语单词约为一半。,对于,a),，如果将,the,从明文中删除，那么,t,的频率将要降到第二组中其他字母之后，而,h,将降到第三组中，并且,th,和,he,就不再是最众多的字母了。,以上对英语统计的讨论是在仅涉及,26,个字母的假设条件下进行的。实际上消息的构成还包括间隔、标点、数字等字符。总之，破译密码并不是件很容易的事。,12,2,.,希尔密码,代替密码与移位密码的一个致命弱点是,明文字符,和,密文字符,有相同的,使用频率,，破译者可从统计出来的字符频率中找到规律，进而找出破译的突破口。要克服这一缺陷，提高保密程度就必须改变字符间的一一对应。,1929,年，希尔利用线性代数中的矩阵运算，打破了字符间的对应关系，设计了一种被称为希尔密码的代数密码。为了便于计算，希尔首先将字符变换成数，例如，对英文字母，我们可以作如下变换：,ABC DE FG H I J K L M N O P Q R S T U V W X Y Z,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 0,将密文分成,n,个一组，用对应的数字代替，就变成了一个个,n,维向量。如果取定一 个,n,阶的非奇异矩阵,A,（此矩阵为主要密钥），用,A,去乘每一向量，即可起到加密的效果，解密也不麻烦，将密文也分成,n,个一组，同样变换 成,n,维向量，只需用,A,逆去乘这些向量，即可将他们变回原先的明文。,13,定理,1,若 使得,(mod26),，则必有,=1,，其,中 为 与,26,的最大公因子。,在具体实施时，我们很快会发现一些困难：,(1),为了使数字与字符间可以互换，必须使用取自,025,之间的整数,(2),由线性代数知识，其中,为,A,的伴随矩阵。由于使用了除法，在求,A,的逆矩阵时可能会出现分数。不解决这些困难，上述想法仍然无法实现。解决的办法是引进同余运算，并用乘法来代替除法，（如同线性代数中用逆矩阵代替矩阵除法一样）。,1 3 5 7 9 11 15 17 19 21 23 25,1 9 21 15 3 19 7 23 11 5 17 25,14,例,1,取,a=3,用希尔密码体系加密语句,THANK YOU,步,1,将,THANK YOU,转换成 （,20,，,8,，,1,，,14,，,11,，,25,，,15,，,21,）,步,2,每一分量乘以,3,并关于,26,取余得 （,8,，,24,，,3,，,16,，,7,，,23,，,19,，,11,）,密文为,HXCPG WSK,现在我们已不难将方法推 广到,n,为一般整数的情况了,只需在乘法运算中结合应用取余，求逆矩阵时用逆元素相乘来代替除法即可。,15,例,2,取,A,=,则,(,具体求法见,后,),用,A,加密,THANK YOU,再用 对密文解密,用矩阵,A,左乘各向量加密（关 于,26,取余）得,得到密文,JXCPI WEK,解,:(,希尔密码加 密,),用相应数字代替字符，划分为两个元素一,组并表示为向量：,16,（,希尔密码解密,）,用,A,-1,左乘求得的向量，即可还原为原来的向量。,(,自行验证,),希尔密码是以,矩阵 法,为基础的，明文与密文的对应由,n,阶矩阵,A,确定。矩阵,A,的阶数是事先约定的，与明文分组时每组字母的字母数量相同，如果明文所含字数与,n,不匹配，则最后几个分量可任意补足。,A,-1,的求法,方法,1,利用公式 ，例如，若取 ，,则,(mod26),，即,方法,2,利用高斯消去法。将矩阵,(A,E),中的矩阵,A,消为,E,，则原先的,E,即被消成了,A,-1,，,17,如,，,(,用,9,乘第二行并取同 余,),，,第一行减去第二行 的,2,倍并取同余，得,，,左端矩阵已化为单位阵，故右端矩阵即为,A,-1,希尔密码系统的解密依赖于以下几把钥匙 （,key,）：,Key1,矩阵,A,的阶数,n,，即,明文是按几个字母来,划分的。,Key2,变换矩阵,A,，只有知,道了,A,才可能推算出,Key3,明文和密文由字母表,转换成,n,维向量所对,应的非负整数表（上,面，为方便起见，我,们采用了字母的自然,顺序）。,18,希尔密码体系为破译者设置了多道关口，加大了破译难度。破译和解密是两个不同的概念，虽然两者同样是希望对密文加以处理而得到明文的内容，但是他们有一个最大的不同,破译密码时，解密必需用到的钥匙未能取得，破译密码的一方需要依据,密文的长度,，,文字的本身特征,，以及,行文习惯,等等各方面的信息进行破译。破译密码虽然需要技术，但更加重要的是“猜测”的艺术。“猜测”的成功与否直接决定着破译的结果。,破译希尔密码的关键是猜测文字被转换成成几维向量所对应的字母表是怎样的，更为重要的是要设法获取加密矩阵,A,。,（,希尔密码的破译,）,由线性代数的知识可以知道，矩阵完全由一组基的变换决定，对 于,n,阶矩阵,A,，只要猜出密文 中,n,个线性无关的向量,(,i=1,2,n,),对应的明文,(,i=1,2,n,),是什么，即可确定,A,，并将密码破译。,19,在实际计算中，可以利用以下方法：,令,则,，,取矩阵,Q|P,经过一系列初等行变换，将由密文决定的,n,维矩阵,Q,化为,n,阶单位阵,I,的时候，由明文决定的矩阵,P,自动化为,(,A,-1,),T,，即：,20,例,5,有密文如下,:,goqbxcbuglosnfal,;,根据英文的行文习惯以及获取密码的途径和背景，猜测是两个字母为一组的希尔密码，前四个明文字母是,dear,，试破译这段秘文。,解,：前两组明文字 母,de,和,ar,对应的二维向量是：,按同一对应整数表，密文中对应这两组的二维向量是：,，,，,由此可得,，对应上例则有,21,利用这一逆矩阵，可对截获密文进行解密，破译出的电文是,Dear Mac God forbid,.,这只是对最简单情况进行的举例，如果加密矩阵的阶数大于,2,，需要的密文应该有较长长度，所需的计算量也是很大的。破译的关键是猜中,n,及,n,个独立的,n,维向量，其后求解加密矩阵的计算量仅为,O,(,n,2,),。,希尔密码体制中有两个要素非常重要：,第一,是字母 与,n,维向量进行转换所依据的非负整数表，本节中所举的是最自然的情况；当然如果依据其它的整数表也是完全可以进行的，其情况将会更复杂一些，破译的难度就会增大。,第二,个要素是加密矩阵，如何定义、求解这个矩阵对于密码的加密和破译更加关键。唯一的要求是加密时应选择行列式值与,26,无公因子的矩阵。,22,RSA,公开密钥体制,传统的密码通讯只能在事先约定的双方间进行，双方必须掌握相同的密钥，而密钥的传送必须使用另外的“安全信道”。这样如果要使,n,个用户都能够秘密的交换信息，则每个用户将需要用个密钥，这种巨大的密钥量给密钥的分配与管理带来了极大的困难；此外在有些情况下，事先约定密钥还是不可能的。,公开密钥体制的提出就是为了从根本上解决上述问题。,其,基本思想,是：,把密钥划分为公开密钥和秘密密钥两部分，两者互为逆变换，但几乎不可能从公开密钥推出秘密密钥。每个使用者均有自己的公开及秘密密钥。,虽然只要能解密的密文，从理论上讲,都是可破译的，但如果破译所需要,的工作量过大，要求花费的时间过,长，以致超过了保密期限，则该密,码系统应当被认为是安全可靠的。,23,定义,1,设,n,为一正整数，将小于,n,且与,n,互素的正整数个数记为,(n),，,称之为欧拉（,Euler L.,）,函数。,不难证明：若,p,，,q,为两个相异素数，,n=pq,，则,(n)=(p-1)(q-1),令,p,q,为随机选取的两个大素数（大约为十进制,100,位或更大）,n=pq,n,是公开的，而,p,q,则是保密的。仅知道欧拉函数,(n)=(p-1)(q-1),，,但如果不知道因式分解就不能用这个公式计算。随机选取一个数,e,，,e,为小于,(n),且与它互素的正整数。利用辗转相除法，可以找到整数,d,和,r,，使,ed+r(n)=1,即,ed 1 (mod(n),数,n,e,和,d,分别称为,模,、,加密密钥,和,解密密钥,。数,n,和,e,组成公开密钥的,加密密钥,，而其余的项,p,q,(n),和,d,组成了秘密陷门。很显然，陷门信息包含了四个相关的项。,24,若知道,(n),则由,pq=n,p+q=n-(n)+1,可知,p,q,是二次方 程,x+(n)-n-1)x+n=0,的根，可以算出,p,和,q,，从而将,n,因式分解。所以,RSA,体制的安全性与因式分解密切相关，若能知道,n,的因子分解，该密码就能被破译。因此，要选用足够大的,n,，使得在当今的条件下要分解它足够困难。,为加密消息,m,，首先将它分为小于,n,（对二进制数据，选取小于,n,的,2,的最大次方幂）的数据块，也就是说，如果,p,和,q,都为十进制,100,位的素数，则,n,刚好在,200,位以内，因此每个消息块的长度也应在两百位以内。加密消息,c,由类似划分的同样长度的消息块组成。加密公式为,(,mod n,),25,要解密消息，取每一个加密块,c(I),并计算,(,mod n,),由公式,ed 1 (mod(n),我们有,ed=1-r(n),因此,(mod n),其中,r,为某一整数。这里利用了,欧拉定理,:,1(mod n),根据以上公式从密文恢复出了明文。,那么,RSA,公开密钥体,制是怎样使用的呢？请,看下例！,26,设使用者取定,p=47,，,q=59,则,N=pq=2773,(n)=(p-1)(q-1)=2668.,取素数,e=17,，显然它与,(n),互素，加密者知道,p,、,q,的值，易得出,d=157,。将,(e,n)=(17,2773),作为公开密钥发布；严守机密的秘密密钥是,(157,2773).,现在有人要向此使用者传送一段（英文）明文信息，例如：,I love chongqing university,将这段文字转换为数字，不计大小写，每两个词之间为一个空格符号，空格符对应数字,00,，每个英文字母对应表征其在字母表中位置的两位数字，例如：,A,对应,01,，,B,对应,02,，,，,Z,对应,26,，等等。再从头向后，将每四位数字划归一组，不足时补充空格。如此得到以下十四组数字：,0900 1215 2205 0003 0815 1407 1709,1407,0021 1409 2205 1819 0920 2500,每一组数字视为一个数，用公开密钥,(17,2773),对其加以变换,27,以第一个数为例，由于,n=2773,比这里任何可能出现的四位数字均大，故只需计算每一数字在模,2773,下的,17,次幂。我们有,900 1510 (mod 2773).,在以上整个过程中，为减少计算量应随时注意取模。这样,900,对应的密码是,1510,。以这一方法得到的密文电码是：,1510 0417 1524 2216 0905 0819 1352,0819 0306 1521 3965 1834 2219 3321,解密过程与此类似，只不过使用密钥,(,157,2773,),，直接计算很烦琐，但用计算机处理这一问题却非常简单。,本例中将四位数字划分为一组，是为了使每组的数字不超过,n=2773,.,当使用一个很大的,n,时，每次完全可以处理一个位数更多的数码组。只要相应的整数小于,n,即可。,28,