数据加密基础及其主.ppt

1,罗森林北京理工大学信息科学技术学院电子工程系,数据加密基础及其主要标准,2,密码学(cryptography)是研究加密和解密变换的一门学科。明文(plaintext)：通常，人们将可懂的文本称为明文。密文(ciphertext,cryptograph):将明文变换成不可懂的形式的文本加密(encipher,encrypt)把明文变换成密文的过程.解密(decipher,decrypt)把密文变换成明文的过程,数据加密的基本概念,3,密码体制(cipher system):完成加密和解密的算法。通常，数据的加密和解密过程是通过密码体制(cipher system)+密钥(keyword)来控制的。,数据加密的基本概念(续),加密,解密,明文,密文,密钥,加密或解密变换,4,由以上介绍可知，数据加密的两个环节分别是加密算法(密码体制)和密钥(密钥管理)密码体制必须易于使用，特别是应当可以在微型计算机是使用；对所允许选择的密钥，加密和解密变换都有必须迅速有效；密码体制的安全性依赖于密钥的安全性，现代密码学不追求加密算法的保密性，而是追求加密算法的完备，即：使攻击者在不知道密钥的情况下，没有办法从算法找到突破口。下面介绍密码体制的基本概念：,数据加密的基本概念(续),5,通常的密码体制采用移位法、代替法和代数方法来进行加密和解密的变换，可以采用一种或几种方法结合的方式作为数据变换的基本模式，下面举例说明：移位法也叫置换法。移位法把明文中的字符重新排列，字符本身不变但其位置改变了。例如最简单的例子：把文中的字母和字符倒过来写。明文：Data security has ebolved tapidly since 1975密文：5791ECNISYLDIPATDEVLOBESAHYTIRUCESATAD或将密文以固定长度来发送 5791ECNI SYLDIPAT DEVLOBES AHYTIRUC ESATAD*,密码体制(cipher system),6,代替法是利用对照的方式，用一个字符来对应另一个字符。例如：按ASCII码的向后移位一次明文：ABCDEFGHIJKLMNOPQRSTU23232密文：BCDEFGHIJKLMNOPQRSTUV34343代数法加密可以对下列两种明文表示法进行相关的变换：1、将明文中的字符按指定的变换方法用数字来代替，然后对这些数字值进行一系列可逆的数学运算，变成密文。2、按照二-十进制，把明文字符的二进制等效值当作一组逻辑和算术运算的输入，产生的二进制结果再变回到二-十进制作为密文。,密码体制(cipher system)(续),7,通常情况下，一个密码体制由以下五个部分组成：明文信息空间M；密文信息空间C；密钥空间K；加密变换Ek:MC，其中kK;解密空间DkM,其中kK;,密码体制(cipher system)(续),8,密码体制分为私用密钥加密技术(对称加密)和公开密钥加密技术(非对称加密)：私用密钥加密，利用一个密钥对数据进行加密，对方接收到数据后，需要用同一密钥来进行解密。这种加密技术的特点是数学运算量小，加密速度快，其主要弱点在于密钥管理困难，而且一旦密钥泄露则直接影响到信息的安全性。由于用同一密钥又叫对称加密公开密钥加密技术，l976年，Diffie和Hellman首次提非对称加密出公开密钥加密体制，即,密码体制(cipher system)(续),9,每个人都有一对密钥，其中一个为公开的，一个为私有的。发送信息时用对方的公开密钥加密，收信者用自己的私用密钥进行解密。公开密钥加密算法的核心是运用一种特殊的数学函数一单向陷门函数，即从一个方向求值是容易的。但其逆向计算却很困难，从而在实际上成为不可行的。公开密钥加密技术它不仅保证了安全性又易于管理。其不足是加密和解密的时间长。鉴两者各自的优缺点，现在有许多密码系统采用二者融合的方法，组成混合密码系统。,密码体制(cipher system)(续),10,RSA加密标准,11,公开密钥算法是在1976年由当时在美国斯坦福大学的迪菲（Diffie）和赫尔曼(Hellman)两人首先。1976年，W.diffie和M.hellman在发表的论文New Direction in Cryptography首次提出了公开密钥密码体制的概念，其中最关键的思想是寻找一个“单向函数”,RSA算法介绍单向函数,12,RSA算法介绍单向函数,什么叫“单向函数”呢？,X,Y,Y=F(m),Y,X,X=F-1(y),不能实现,13,三位数学家(Ronald Rivest,Adi Shamir和Len Adleman)提出了第一个比较完善的公开密钥密码体制，即著名的RSA体制。它既能用于加密也能用于数字签名。,RSA算法介绍,14,RSA算法研制的最初理念与目标是旨在解决DES算法秘密密钥利用公开信道传输分发困难的难题。而实际结果不但很好地解决了这个难题；还可利用RSA来完成对电文的数字签名以对抗电文的否认与抵赖；同时还可以利用数字签名较容易地发现攻击者对电文的非法篡改，以保护数据信息的完整性。在介绍RSA公钥加密算法原理这前，介绍一点相关的数论的知识是必需的。,RSA算法介绍,15,基本的数论知识,定义1：设a,b,m都是整数。如果m|(a-b)，则称a和b模 m同余，记为,m称为同余式的模。,16,RSA公钥密码体制的加密变换步骤：1、随机地选择两个素数p和q（保密）；2、计算r=p*q(公开)3、计算保密的欧拉指示函数(r)=(p-1)*(q-1);4、随机选取正整数e,1e(r)，满足gcd(e,(r)=1,e是公开的加密密钥。5、用Euclid计算d,满足de1(mod(r).d是保密的解密密钥。6、加密变换：对明文mZn，密文为c=me mod r7、加密变换：对明文mZn，密文为m=cd mod r下面证明加密变换和解密变换是一对互为逆变换：,RSA算法原理,下一步,17,在证明解密变换是加密变换的逆变换之前，介绍一下Euler定理和Fermat定理：Euler定理：设m和r都是正整数。如果(1).gcd(m,r)=1(2).r=p*q(3).(r)=(p-1)*(q-1),则m(r)1(mod r)返回Fermat定理：设x和p都是正整数。如果p是素数并且gcd(x,p)=1，则xp-1 1(mod p).返回,RSA算法原理,18,下面来证明解密变换是加密变换的逆变换。因为de1(mod(r)所以存在整数t1使得de=t*(r)+1i 对任意明文1mr，当gcd(m,r)=1时，根据Euler定理，有：,RSA算法原理,19,ii当gcd(m,r)1时，因为r=p*q并且p和q都是素数，所以gcd(m,r)一定为p或者q,不妨设gcd(m,r)=p，则m一定是p的倍数，设m=cp,1cq.因为mq-11(mod q),(Fermat定理)所以(mq-1)t(p-1)1(mod q),即mt*(r)1(mod q),于是存在一个整数s,使得mt*(r)=1+sq,用m=cp同乘上式的两端，有mt*(r)+1=m+msq=m+cpsq=m+csr,RSA算法原理,20,RSA算法原理,因此，mt*(r)+1m(mod r)综上所述，对任意mZn，都有,即解密变换和加密变换是互逆变换。证毕！,一个例子,21,例：设p=11,q=23,则r=pq=1123=253(r)=(p-1)*(q-1)=1022=220.选取加密密钥e=3.显然，gcd(3,220)=1.利用Euclid算法容易求得解密密钥d=147.容易验证31471(mod 220)明文空间Zn=0,1,2,251,252.对于明文m=165,有密文c=1653mod 253=110.对密文c=110,有明文m=110147mod 253=165.,RSA算法的一个实例,返回,22,RSA算法原理,实际计算时运算可以采用重复平方和乘法的快速指数算法(Fast Exponentiation Algorithm)即：c=fastexp(m,e,r)m=fastexp(c,d,r)以一个例子来说明加密和解密的过程：先介绍一种有效检验随机选择的d是否与(r)互素，以及对求同余式,的解e，欧几里得算法提供了一种有效的方法。,23,RSA算法原理,欧几里得算法(Euclid Alogorithm)：若,则a与b的gcd就等于b与c的gcd.如：a=38=2*19,b=26=2*13由于19与13互为素数，所以2是a和b的最大公约数。由欧几里得算法可得同样的结果：(1).38=26*1+12用26除38商为1，余数为12(2).26=12*2+2用12除26商为2，余数为2(3).12=2*6即：38与26的公约数就是26与12的公约数，也是12和2的公约数。,24,用欧几里得的算法，可以证明当p=47,q=61,(r)=2760时，d=167是秘密密钥的候选者：2760=167*16+88(a)167=88*1+79(b)88=79*1+9(c)79=9*8+7(d)9=7*1+2(e)7=2*3+1(f)2=1*2(g)由于2和1互素，所以2760与167互素。,RSA算法原理,25,e公开密钥的计算：1=7-2*3(a)将2=9-7*1(e)式代入(a)中得到1=7-(9-7*1)*3=7*4-9*3(b)将7=79-9*8(d)式代入(b)中得到1=79*4-9*32-9*3=79*4-9*35(c)将9=88-79*1(c)式代入(c)中得到1=79*4-88*35+79*35=79*39-88*35(d)将79=167-88*1(b)式代入(d)中得到1=(167-88*1)*39-88*35=167*39-88*35(e)最后，将88=2760-167*16(a)式代入(e)中得到1=167*39-2760*74+167*16*741=167*1223-2760*34,RSA算法原理,26,根据,得知e=1223是与秘密密钥d=167对应的公开密钥。,RSA算法原理,从上面的过程中可以得到以下数据：p=47(选出的)q=61(选出的)r=p*q=47*61=2867(选出的)(r)=(p-1)*(q-1)=46*60=2760(推导的)d=167(选出的)e=1223(推出的)注：用RSA算法加密的信息，首先要将信息分成一连串的数据块，每个数据块的值不超出r-1，否则就不可能得到唯一的明文表达式。,27,例：对明文“RSA ALGRITHM”的加密：首先将明文转换为数字，例如将明文的每个英文字母用十进制数字的两位数字表示，例如空白=00，A=01，B=02，Z=26。由些得到明文的数据块为：1819010001120715180920081300利用加密变换公式,RSA算法加密实例,可以加密第一个明文数据块1819，将其自乘到e=1223次幂之后，用r=2867去除，取其余数2756作为密文：类似地加密其它明文数据块，得到密文是：2756200105420669234704081815利用解密变换公式，可以将密文恢复为原来的明文。,28,RSA的安全性依赖于大数分解，但是否等同于大数分解一直未能得到理论上的证明，因为没有证明破解RSA就一定需要作大数分解。但是，目前攻击RSA的一些变种算法已被证明等价于大数分解。不管怎样，分解r是最显然的攻击方法。现在，人们已能分解多个十进制位的大素数。因此，模数r必须选得大一些，因具体适用情况而定。当然也可以通过猜测(p-1)*(q-1)的值来攻击RSA。但这种攻击没有分解r容易。有些攻击专门针对RSA的实现。他们不攻击基本的算法，而是攻击协议。仅会使用RSA而不重视它的实现是不够的。实现细节也很重要。这就是对RSA的选择密文攻击。RSA在选择密文攻击面前很脆弱。一般攻击者是将某一信息作一下伪装(Blind)，让拥有私钥的实体签署。然后，经过计算就可得到它所想要的信息。,RSA算法的安全性分析（一）,29,还有一种就是对RSA的公共模数攻击。若系统中共有一个模数，只是不同的人拥有不同的e和d，系统将是危险的。最普遍的情况是同一信息用不同的公钥加密，这些公钥共模而且互质，那末该信息无需私钥就可得到恢复。设P为信息明文，两个加密密钥为e1和e2，公共模数是r，则：C1=Pe1 mod rC2=Pe2 mod r密码分析者知道r、e1、e2、C1和C2，就能得到P。另外，还有其它几种利用公共模数攻击的方法。总之，如果知道给定模数的一对e和d，一是有利于攻击者分解模数，一是有利于攻击者计算出其它成对的e和d，而无需分解模数。解决办法只有一个，那就是不要共享模数r。,RSA算法的安全性分析（二）,30,RSA算法是第一个能同时用于加密和数字签名的算法，也易于理解和操作。RSA是被研究得最广泛的公钥算法，从提出到现在已二十多年，经历了各种攻击的考验，逐渐为人们接受，普遍认为是目前最优秀的公钥方案之一。RSA的安全性依赖于大数的因子分解，但并没有从理论上证明破译RSA的难度与大数分解难度等价。即RSA的重大缺陷是无法从理论上把握它的保密性能如何。,总结,31,但RSA也有它的缺点，主要有：A)产生密钥很麻烦，受到素数产生技术的限制，因而难以做到一次一密。B)分组长度太大，为保证安全性，r 至少也要 600 bits 以上，使运算代价很高，尤其是速度较慢，较对称密码算法慢几个数量级；且随着大数分解技术的发展，这个长度还在增加，不利于数据格式的标准化。,总结,32,陈鲁生,沈世镒.现代密码学,北京.科学出版社,2002刘尊全.刘氏高强度公开加密算法设计原理与装置.北京:清华大学出版社,1996卢开澄，郭宝安 等.计算机系统安全(The Security of Computer System).重庆:重庆出版社,1999,参考资料,33,DES算法,34,数据加密标准DES,1977年美国国家标准局公布了IBM公司研制的一种数据加密算法:数据加密标准(Data Encryption Standard).原定服役十年,由于在这期间，该加密标准没有受到真正的威胁，20多年来一直活跃在国际保密通信的舞台上。近些年，随着计算机技术的提高，已经有了现实的威胁。512位的密钥已经能被破解，但是要花很多的时间，计算量非常大，,35,数据加密标准DES,1024位长度密钥至今没能被破解。DES作为一种高速对称加密算法，仍然具有重要意义。特别是DES（密钥系统）和公钥系统结合组成混合密码系统。使DES和公钥系统（如RSA）能够各自扬长避短，提高了加密系统的安全和效率。,36,DES加密算法,DES是一种分组密码：假定明文m是0和1组成的长度为64bit的符号串，密钥也是64bit的0,1符号串，设：m=m1m2m3m64k=k1k2k3k4k5k64必须说明的是：k只的56bit 有用，k8,k16,k32,k64这位是奇偶校验位，在算法中不起作用。加密过程可表达为：DES(m)=IP-1T16T15T2T1IP(m),37,DES加密算法,下面逐一介绍各个组成部分的功能IP是初始置换，IP-1它的逆置换mIP M设m=m1m2m3m64M=M1M2M3M64置换之后有：M1=m58,M2=m50,M64=m7,38,DES加密算法,现将的下标列表如下585042342618102605244362820124IP:62544638302214664564840322416857494133251791595143352719113615345372921135635547393123157数字代表原m的下标。,39,DES加密算法,IP-1满足IPIP-1IP-1IPIM m若M=M1M2M3M64则m=M40M8M48M25现将IP-1关于m的下标列表于后：,40,DES加密算法,408481656246432397471555236331 IP-1:386461454226230375451453216129364441352206028353431251195927342421150185826331411049175725数字代表原M的下标。,41,DES加密算法,DES的迭代过程流程图：,IP,L0,R0,f,k1,L1=R0,R1=L0f(R0k1),f,k2,L2=R1,R2=L1f(R1k2),R16=L15f(R15k16),L16=R15,IP-1,42,DES加密算法,Li-1(32bit),Ri-1(32bit),f,Li,Ri,ki,第i次迭代过程，如下图：i=1,2,图中：Li-1和Ri-1分别第i-1次迭代结果的左右两部分，各32bit.,Li=Ri-1 Ri=Li-1f(Ri-1,ki)ki是由64位密钥产生的子密钥。ki是48bit,43,DES加密算法,DES的关键在于f(Ri-1,ki)的功能。f 是将32bit的输入转化为32bit的输出。如下图：,s1,s2,s3,s4,s5,s6,s7,s8,E,Ri-1(32bit),(48bit),ki(48bit),P,32bit,32bit,44,DES解密算法,DES的解密过程和DES的加密过程完全类似，只不过将16圈的子密钥序列k1，k2，k3，k4，k5，k16 的顺序倒过来，即第1圈用第16个子密钥k16，第2圈用k15，余此类推，即DES-1=IP-1T1T2T15T16IP容易验证：DES-1(DES(m)=mDES(DES-1(m)=m,45,DES解密算法,证明：由于：DES-1=IP-1T1T2T15T16IPIP-1IP=I所以：DES-1(DES(m)=IP-1T1T2T15T16(T16T15T2T1IP(m).我们看看 T16(T16T15T2T1IP(m)的结果 T16T15T2T1IP(m)表示DES(m)第16圈迭代,46,DES解密算法,后R16 和L16的结果。,R16=L15f(R15k16),L16=R15,DES(m)R16 结果,R16=L15f(R15k16),L16=R15,f,L,R,k16,L=R15 R=L15f(R15,k16)f(R15,k16)=L15,DES-1(DES(m)的第一次迭代,47,DES解密算法,同理：L15=R14 R15=L14f(R14,k15),R15,L15,f,L=R14,R=L14,k15,DES-1(DES(m)的第二次迭代,依此类推DES-1(DES(m)=m得证,48,谢谢,