第二讲-数据加密-对称加密算法重点课件.ppt

1、 密码学与信息加密 内容提要本章介绍密码学的基本概念。介绍加密领域中两种主流的加密技术：DES加密（Data Encryption Standard）RSA加密（Rivest-Shamir-Adleman）并用程序实现这两种加密技术的算法。最后介绍目前常用的加密工具PGP（Pretty Good Privacy），使用PGP产生密钥，加密文件和邮件。密码学概述密码学是一门古老而深奥的学科，对一般人来说是非常陌生的。长期以来，只在很小的范围内使用，如军事、外交、情报等部门。计算机密码学是研究计算机信息加密、解密及其变换的科学，是数学和计算机的交叉学科，也是一门新兴的学科。随着计算机网络和计算机通

2、讯技术的发展，计算机密码学得到前所未有的重视并迅速普及和发展起来。在国外，它已成为计算机安全主要的研究方向。 密码技术的发展简介 密码学的历史比较悠久，在四千年前，古埃及人就开始使用密码学的历史比较悠久，在四千年前，古埃及人就开始使用密码来保密传递消息。密码来保密传递消息。两千多年前，罗马国王两千多年前，罗马国王Julius Caesare（恺撒）就开始使用（恺撒）就开始使用目前称为目前称为“恺撒密码恺撒密码”的密码系统。但是密码技术直到本的密码系统。但是密码技术直到本20世纪世纪40年代以后才有重大突破和发展。年代以后才有重大突破和发展。密码技术的发展简介007收到遇害同事的字条，上面写着4

3、FEFKKILJK81IP，根据事先约定，已知c=3，q=H，问该同事要传递什么信息给007？ Do not trust hary密码技术的发展简介最早影响世界的加密技术诞生于战争年代，由德国人发明，用于传递攻击信息；而最早影响世界的解密技术，也诞生于战争年代，由英美开发出来破译德国人的攻击信息。Enigma Machine “闪电战”的提出者，德国装甲部队之父，納粹德国的海因茨古德里安(Heinz Guderian)将军在指挥车上。在照片的左下方我们可以看见一台恩尼格码机 密码技术的发展简介20世纪世纪70年代后期，由于计算机、电子通信年代后期，由于计算机、电子通信的广泛使用，现代密码学得到

4、了空前的发展。的广泛使用，现代密码学得到了空前的发展。加密、解密的定义所谓“加密”，就是对原内容为明文的文件或数据按某种算法进行处理，使其成为不可读的 “密文”的过程密文只能在经过相对应的反向算法处理恢复原来数据的过程，这就是“解密”目的：通过这样的途径来达到保护数据不被非法人窃取、阅读 消息和加密遵循国际命名标准，加密和解密可以翻译成：遵循国际命名标准，加密和解密可以翻译成：“Encipher（译成密码）（译成密码）”和和“（Decipher）（解译密码）（解译密码）”。也可以这样命名：。也可以这样命名：“Encrypt（加（加密）密）”和和“Decrypt（解密）（解密）”。消息被称为明文

5、。用某种方法伪装消息以隐藏它的内容的过程称为加密，消息被称为明文。用某种方法伪装消息以隐藏它的内容的过程称为加密，加了密的消息称为密文，而把密文转变为明文的过程称为解密，图加了密的消息称为密文，而把密文转变为明文的过程称为解密，图1表表明了加密和解密的过程。明了加密和解密的过程。加密解密明文密文原始明文明文 密文明文用M（Message，消息）或P（Plaintext，明文）表示，它可能是比特流、文本文件、位图、数字化的语音流或者数字化的视频图像等。密文用C（Cipher）表示，也是二进制数据，有时和M一样大，有时稍大。通过压缩和加密的结合，C有可能比P小些。加密函数E作用于M得到密文C，用数

6、学公式表示为：E（M）=C。解密函数D作用于C产生M，用数据公式表示为：D（C）=M。先加密后再解密消息，原始的明文将恢复出来，D（E（M）=M必须成立。鉴别、完整性和抗抵赖性 除了提供机密性外，密码学需要提供三方面的功能：鉴别、完整性和抗除了提供机密性外，密码学需要提供三方面的功能：鉴别、完整性和抗抵赖性。这些功能是通过计算机进行社会交流，至关重要的需求。抵赖性。这些功能是通过计算机进行社会交流，至关重要的需求。鉴别：消息的接收者应该能够确认消息的来源；入侵者不可能伪装成他鉴别：消息的接收者应该能够确认消息的来源；入侵者不可能伪装成他人。人。完整性：消息的接收者应该能够验证在传送过程中消息没

7、有被修改；入完整性：消息的接收者应该能够验证在传送过程中消息没有被修改；入侵者不可能用假消息代替合法消息。侵者不可能用假消息代替合法消息。抗抵赖性：发送消息者事后不可能虚假地否认他发送的消息。抗抵赖性：发送消息者事后不可能虚假地否认他发送的消息。算法和密钥 密钥用K表示。K可以是很多数值里的任意值，密钥K的可能值的范围叫做密钥空间。加密和解密运算都使用这个密钥，即运算都依赖于密钥，并用K作为下标表示，加解密函数表达为：E（M , k）=CD（C , k）=MD（E（M , k）, k）=M，如图所示。加密解密明文密文原始明文密钥密钥有些算法使用不同的加密密钥和解密密钥，也就是说加密密钥K1与相

8、应的解密密钥K2不同，在这种情况下，加密和解密的函数表达式为：E（M，K1）=CD（C，K2）=M函数必须具有的特性是，D（E（M，K1），K2）=M，如图所示。加密解密明文密文原始明文加密密钥解密密钥对称算法基于密钥的算法通常有两类：1.对称算法2.公开密钥算法（非对称算法）在对称算法中，加解密的密钥是相同的。对称算法要求发送者和接收者在安全通信之前，协商一个密钥。对称算法的安全性依赖于密钥，泄漏密钥就意味着任何人都能对消息进行加解密。对称算法的加密和解密表示为：E（M，K）=CD（C，K）=M公开密钥算法公开密钥算法（非对称算法）的加密的密钥和解密的密钥不同，而且解密密钥不能根据加密密钥计

9、算出来之所以叫做公开密钥算法，是因为加密密钥能够公开，即陌生者能用加密密钥加密信息，但只有用相应的解密密钥才能解密信息。加密密钥叫做公开密钥（简称公钥），解密密钥叫做私人密钥（简称私钥）。公开密钥K1加密表示为：E（M，K1）=C。公开密钥和私人密钥是不同的，用相应的私人密钥K2解密可表示为：D（C，K2）=M。有人用邮箱作为比喻，任何人都可以从邮箱的信封人口塞进信件，但是取信的权力却仅仅在于持有邮箱钥匙的人的手上。这个众人皆知的信封入口就是“公钥”（Public Key），而你持有的邮箱钥匙就是“私钥”（Private Key）这种算法规定，对方给你发送数据前，可以用“公钥”加密后再发给你，

10、但是这个“公钥”也无法解开它自己加密的数据，即加密过程是单向的，这样即使数据被途中拦截，入侵者也无法对其进行破解，能还原数据内容的只有“私钥”的持有者，这就是“非对称密钥”加密算法，也称为“公共密钥算法”，DES对称加密技术DES(Data Encryption Standard)算法，于1977年得到美国政府的正式许可，是一种用56位密钥来加密64位数据的方法。定义：用56位密钥来对64位数据块进行16轮编码的加密方法DES算法的历史美国国家标准局1973年开始研究除国防部外的其它部门的计算机系统的数据加密标准，最终选用了IBM公司设计的方案作为非机密数据的正式数据加密标准加密算法要达到的目

11、的有四点提供高质量的数据保护，防止数据未经授权的泄露和未被察觉的修改；具有相当高的复杂性，使得破译的开销超过可能获得的利益，同时又要便于理解和掌握；DES密码体制的安全性应该不依赖于算法的保密，其安全性仅以加密密钥的保密为基础；实现经济，运行有效，并且适用于多种完全不同的应用。DES算法的安全性 DES算法正式公开发表以后，引起了一场激烈的争论。1977年Diffie和Hellman提出了制造一个每秒能测试106个密钥的大规模芯片，这种芯片的机器大约一天就可以搜索DES算法的整个密钥空间，制造这样的机器需要两千万美元。1993年R.Session和M.Wiener给出了一个非常详细的密钥搜索机

12、器的设计方案，它基于并行的密钥搜索芯片，此芯片每秒测试5107个密钥，当时这种芯片的造价是10.5美元，5760个这样的芯片组成的系统需要10万美元，这一系统平均1.5天即可找到密钥，如果利用10个这样的系统，费用是100万美元，但搜索时间可以降到2.5小时。 DES算法的安全性 1997年1月28日，美国的RSA数据安全公司在互联网上开展了一项名为“密钥挑战”的竞赛，悬赏一万美元，破解一段用56比特密钥加密的DES密文。计划公布后引起了网络用户的强力响应。一位名叫Rocke Verser的程序员设计了一个可以通过互联网分段运行的密钥穷举搜索程序，组织实施了一个称为DESHALL的搜索行动，成

13、千上万的志愿者加入到计划中在计划实施的第96天，即挑战赛计划公布的第140天，1997年6月17日晚上10点39分，美国盐湖城Inetz公司的职员Michael Sanders成功地找到了密钥，在计算机上显示了明文：“ Strong cryptography makes the world a safer place”一个数量级概念赢得彩票头等奖并在同一天被闪电杀死的可能性1/255 DES算法的安全性 DES算法的原理 DES算法的入口参数有三个：Key、Data、Mode。其中Key为8个字节共64位，是DES算法的工作密钥；Data也为8个字节64位，是要被加密或被解密的数据；Mode为

14、DES的工作方式有两种：加密或解密。DES算法是这样工作的：如Mode为加密，则用Key去把数据Data进行加密，生成Data的密码形式（64位）作为DES的输出结果；如Mode为解密，则用Key去把密码形式的数据Data解密，还原为Data的明码形式（64位）作为DES的输出结果。DES算法的实现步骤DES算法实现加密需要三个步骤：第一步：变换明文。对给定的64位比特的明文x，首先通过一个置换IP表来重新排列x，从而构造出64位比特的x0，x0=IP(x)=L0R0，其中L0表示x0的前32比特，R0表示x0的后32位。第二步：按照规则迭代。规则为Li = Ri-1Ri = Li f(Ri-

15、1,Ki) （i=1,2,316）经过第一步变换已经得到L0和R0的值，其中符号 表示的数学运算是异或，f表示一种函数运算，主要由S盒置换构成，Ki是一些由密钥编排函数产生的比特块。f和Ki将在后面介绍。第三步：对L16R16利用IP-1作逆置换，就得到了密文y加密过程如图所示。输入64位比特明文IP置换表L0R0Li = Ri-1 Ri = Lif(Ri-1,Ki)（i=1,2,16）迭代16次IP逆置换表输出64位比特密文从图中可以看出，DES加密需要四个关键点：1、IP置换表和IP-1逆置换表。2、函数f。3、子密钥Ki。4、S盒的工作原理。（1）IP置换表和IP-1逆置换表输入的64位

16、数据按置换IP表进行重新组合，并把输出分为L0、R0两部分，每部分各长32位，其置换IP表如表所示。58501234261810260524436282012462544638302214664564840322416857494133251791595143352719113615345372921135635547393123157将输入64位比特的第58位换到第一位，第50位换到第二位，依此类推，最后一位是原来的第7位。L0、R0则是换位输出后的两部分，L0是输出的左32位，R0是右32位。比如：置换前的输入值为D1D2D3D64，则经过初始置换后的结果为：L0=D58D50.D8，R0

17、=D57D49.D7经过16次迭代运算后。得到L16、R16，将此作为输入，进行逆置换，即得到密文输出。逆置换正好是初始置的逆运算例如，第1位经过初始置换后，处于第40位，而通过逆置换IP-1，又将第40位换回到第1位，其逆置换IP-1规则表所示。逆置换表IP-1 40848165624643239747155523633138646145422623037545135321612936444125220602835343115119592734242105018582633141949175725（2）函数f函数f有两个输入：32位的Ri-1和48位Ki，f函数的处理流程如图5所示。32位R

18、i-1E变换48位KiS1S7S6S5S4S3S2S8P变换32位输出48位48位32位E变换的算法是从Ri-1的32位中选取某些位，构成48位。即E将32比特扩展变换为48位，变换规则根据E位选择表，如表所示。3212345456789891011121312131415161716171819202120212223242524252627282928293031321Ki是由密钥产生的48位比特串，具体的算法下面介绍。将E的选位结果与Ki作异或操作，得到一个48位输出。分成8组，每组6位，作为8个S盒的输入。每个S盒输出4位，共32位，S盒的工作原理将在第第四步介绍。S盒的输出作为P变换

19、的输入，P的功能是对输入进行置换，P换位表如表所示。1672021291228171152326518311028241432273919133062211425（3）子密钥ki假设密钥为K，长度为64位，但是其中第8、16、24、32、40、48、64用作奇偶校验位，实际上密钥长度为56位。K的下标i的取值范围是1到16，用16轮来构造。构造过程如图所示。64位密钥字符串KPC1变换C0C16LS16D2LS2D0C2LS2D1C1LS1LS1D16LS16PC2变换PC2变换PC2变换48位K148位K1648位K256比特28比特28比特子密钥ki （密钥生成（密钥生成Ki）KPC-1C

20、0 D0LS1LS1C1 D1LS2LS2LS16LS16C16 D16PC-2PC-2K1K16 子密钥ki首先，对于给定的密钥K，应用PC1变换进行选位，选定后的结果是56位，设其前28位为C0，后28位为D0。PC1选位如表所示。57494133251791585042342618102595143352719113605244366355473931231576254463830221466153453729211352820124第一轮：对C0作左移LS1得到C1，对D0作左移LS1得到D1，对C1D1应用PC2进行选位，得到K1。其中LS1是表示第一轮左移的位数，各轮循环左移位数如

21、表所示。下表中的第一列是LS1，第二列是LS2，以此类推。左移的原理是所有二进位向左移动，原来最左边的比特位移动到最右边1122222212222221PC2如表所示14171124153281562110231912,42681672720132415231374755304051453348444939563453464250362932第二轮：对C1，D1作左移LS2得到C2和D2，进一步对C2D2应用PC2进行选位，得到K2。如此继续，分别得到K3，K4K16。（4） S盒的工作原理首先回顾一下S盒变换在函数f中的位置：32位Ri-1E变换48位KiS1S7S6S5S4S3S2S8P变

22、换32位输出48位48位32位（4）S盒的工作原理S盒以6位作为输入，而以4位作为输出，现在以S1为例说明其过程。假设输入为A=a1a2a3a4a5a6，则a2a3a4a5所代表的数是0到15之间的一个数，记为：k=a2a3a4a5；由a1a6所代表的数是0到3间的一个数，记为h=a1a6。在S1的h行（范围03），k列（范围015）找到一个数B，B在0到15之间，用4位二进制表示，为B=b1b2b3b4，这就是S1的输出。练习：已知A101110 求 BDES算法的解密过程是一样的，区别仅仅在于第一次迭代时用子密钥K15，第二次K14、最后一次用K0，算法本身并没有任何变化。DES的算法是对

23、称的，既可用于加密又可用于解密。取16进制明文X：0123456789ABCDEF密钥K为：133457799BBCDFF1去掉奇偶校验位以二进制形式表示的密钥是00010010011010010101101111001001101101111011011111111000应用IP，我们得到：L0=11001100000000001100110011111111L1=R0=11110000101010101111000010101010然后进行16轮加密。最后对L16, R16使用IP-1得到密文：85E813540F0AB405DES加密的一个例子加密的一个例子DES算法的应用误区 DES算

24、法具有比较高安全性，到目前为止，除了用穷举搜索法对DES算法进行攻击外，还没有发现更有效的办法。56位长的密钥的穷举空间为256，这意味着如果一台计算机的速度是每一秒种检测一百万个密钥，则它搜索完全部密钥就需要将近2285年的时间，可见，这是难以实现的，当然，随着科学技术的发展，当出现超高速计算机后，我们可考虑把DES密钥的长度再增长一些，以此来达到更高的保密程度。DES算法的程序实现根据DES算法的原理，可以方便的利用C语言实现其加密和解密算法。程序在VC+6.0环境下测试通过DES算法的程序实现设置一个密钥匙为数组char key8=1,9,8,0,9,1,7,2，要加密的字符串数组是st

25、r=Hello，利用Des_SetKey(key)设置加密的密钥，调用Des_Run(str, str, ENCRYPT)对输入的明文进行加密，其中第一个参数str是输出的密文，第二个参数str是输入的明文，枚举值ENCRYPT设置进行加密运算。程序执行的结果如图所示。RSA算法的原理 1976年，Diffie和Hellman在文章“密码学新方向（New Direction in Cryptography）”中首次提出了公开密钥密码体制的思想，1977年，Rivest、Shamir和Adleman三个人实现了公开密钥密码体制，现在称为RSA公开密钥体制，它是第一个既能用于数据加密也能用于数字签

26、名的算法。这种算法易于理解和操作，算法的名字以发明者的名字命名：Ron Rivest， Adi Shamir和Leonard Adleman。但RSA的安全性一直未能得到理论上的证明。它经历了各种攻击，至今未被完全攻破。RSA体制RSA体制可以简单描述如下：（1）、生成两个大素数p和q。（2）、计算这两个素数的乘积n=pq。（3）、计算小于n并且与n互质的整数的个数，即欧拉函数(n)=(p-1)(q-1)。（4）、选择一个随机数b满足1b(n)，并且b和(n)互质，即gcd(b, (n)=1。（5）、计算ab=1 mod (n)。（6）、保密a，p和q，公开n和b。利用RSA加密时，明文以分组

27、的方式加密：每一个分组的比特数应该小于log2n比特。加密明文x时，利用公钥(b, n)来计算c=xb mod n就可以得到相应的密文c。解密的时候，通过计算ca mod n就可以恢复出明文x。选取的素数p和q要足够大，从而乘积n足够大，在事先不知道p和q的情况下分解n是计算上不可行的。常用的公钥加密算法包括：RSA密码体制、ElGamal密码体制和散列函数密码体制（MD4、MD5等）。RSA算法的安全性 RSA的安全性依赖于大数分解，但是否等同于大数分解一直未能得到理论上的证明，因为没有证明破解 RSA就一定需要作大数分解。假设存在一种无须分解大数的算法，那它肯定可以修改成为大数分解算法。目

28、前， RSA 的一些变种算法已被证明等价于大数分解。不管怎样，分解n是最显然的攻击方法。现在，人们已能分解多个十进制位的大素数。因此，模数n必须选大一些，因具体适用情况而定 RSA算法的速度 由于进行的都是大数计算，使得RSA最快的情况也比DES慢上倍，无论是软件还是硬件实现。速度一直是RSA的缺陷。一般来说只用于少量数据加密。RSA算法是第一个能同时用于加密和数字签名的算法，也易于理解和操作。RSA是被研究得最广泛的公钥算法，从提出到现在已近二十年，经历了各种攻击的考验，逐渐为人们接受，普遍认为是目前最优秀的公钥方案之一。作业进一步学习掌握DES加密原理收集/查阅/编写DES加密程序，并调试运行