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