第八章 密码学与信息加密 内容提要n本章介绍密码学的基本概念。n介绍加密领域中两种主流的加密技术：nDES加密（Data Encryption Standard）nRSA加密（Rivest-Shamir-Adleman）n并用程序实现这两种加密技术的算法。 最后介绍目前常用的加密工具PGP（ Pretty Good Privacy），使用PGP产生密 钥，加密文件和邮件。密码学概述n密码学是一门古老而深奥的学科，对一般人来 说是非常陌生的。长期以来，只在很小的范围 内使用，如军事、外交、情报等部门。计算机 密码学是研究计算机信息加密、解密及其变换 的科学，是数学和计算机的交叉学科，也是一 门新兴的学科。n随着计算机网络和计算机通讯技术的发展，计 算机密码学得到前所未有的重视并迅速普及和 发展起来。在国外，它已成为计算机安全主要 的研究方向。密码技术简介 n密码学的历史比较悠久，在四千年前，古埃及人就开 始使用密码来保密传递消息。n两千多年前，罗马国王Julius Caesare（恺撒）就开 始使用目前称为“恺撒密码”的密码系统。但是密码技 术直到本20世纪40年代以后才有重大突破和发展。n特别是20世纪70年代后期，由于计算机、电子通信的 广泛使用，现代密码学得到了空前的发展。消息和加密n遵循国际命名标准，加密和解密可以翻译成：“Encipher（译成 密码）”和“（Decipher）（解译密码）”。也可以这样命名： “Encrypt（加密）”和“Decrypt（解密）”。n消息被称为明文。用某种方法伪装消息以隐藏它的内容的过程称 为加密，加了密的消息称为密文，而把密文转变为明文的过程称 为解密，图8-1表明了加密和解密的过程。明文 密文n明文用M（Message，消息）或P（Plaintext，明文） 表示，它可能是比特流、文本文件、位图、数字化的 语音流或者数字化的视频图像等。n密文用C（Cipher）表示，也是二进制数据，有时和M 一样大，有时稍大。通过压缩和加密的结合，C有可能 比P小些。n加密函数E作用于M得到密文C，用数学公式表示为：E （M）=C。解密函数D作用于C产生M，用数据公式表 示为：D（C）=M。先加密后再解密消息，原始的明 文将恢复出来，D（E（M）=M必须成立。鉴别、完整性和抗抵赖性 n除了提供机密性外，密码学需要提供三方面的功能：鉴别、完整 性和抗抵赖性。这些功能是通过计算机进行社会交流，至关重要 的需求。n鉴别：消息的接收者应该能够确认消息的来源；入侵者不可能伪 装成他人。n完整性：消息的接收者应该能够验证在传送过程中消息没有被修 改；入侵者不可能用假消息代替合法消息。n抗抵赖性：发送消息者事后不可能虚假地否认他发送的消息。算法和密钥 n现代密码学用密钥解决了这个问题，密钥用K表示。K 可以是很多数值里的任意值，密钥K的可能值的范围叫 做密钥空间。加密和解密运算都使用这个密钥，即运 算都依赖于密钥，并用K作为下标表示，加解密函数表 达为：nEK（M）=CnDK（C）=MnDK（EK（M）=M，如图8-2所示。n有些算法使用不同的加密密钥和解密密钥，也就是说加密密钥K1 与相应的解密密钥K2不同，在这种情况下，加密和解密的函数表 达式为：nEK1（M）=CnDK2（C）=Mn函数必须具有的特性是，DK2（EK1（M）=M，如图8-3所示。对称算法n基于密钥的算法通常有两类：对称算法和公开 密钥算法（非对称算法）。对称算法有时又叫 传统密码算法，加密密钥能够从解密密钥中推 算出来，反过来也成立。n在大多数对称算法中，加解密的密钥是相同的 。对称算法要求发送者和接收者在安全通信之 前，协商一个密钥。对称算法的安全性依赖于 密钥，泄漏密钥就意味着任何人都能对消息进 行加解密。对称算法的加密和解密表示为：nEK（M）=CnDK（C）=M公开密钥算法n公开密钥算法（非对称算法）的加密的密钥和解密的密钥不同，而且 解密密钥不能根据加密密钥计算出来，或者至少在可以计算的时间内 不能计算出来。n之所以叫做公开密钥算法，是因为加密密钥能够公开，即陌生者能用 加密密钥加密信息，但只有用相应的解密密钥才能解密信息。加密密 钥叫做公开密钥（简称公钥），解密密钥叫做私人密钥（简称私钥） 。n公开密钥K1加密表示为：EK1（M）=C。公开密钥和私人密钥是不同 的，用相应的私人密钥K2解密可表示为：DK2（C）=M。DES对称加密技术nDES(Data Encryption Standard)算法，于1977年得到 美国政府的正式许可，是一种用56位密钥来加密64位 数据的方法。DES算法的历史n美国国家标准局1973年开始研究除国防部外的其它部 门的计算机系统的数据加密标准，于1973年5月15日 和1974年8月27日先后两次向公众发出了征求加密算 法的公告。n加密算法要达到的目的有四点。n提供高质量的数据保护，防止数据未经授权的泄露和未被察 觉的修改；n具有相当高的复杂性，使得破译的开销超过可能获得的利益 ，同时又要便于理解和掌握；nDES密码体制的安全性应该不依赖于算法的保密，其安全性仅 以加密密钥的保密为基础；n实现经济，运行有效，并且适用于多种完全不同的应用。DES算法的安全性 nDES算法正式公开发表以后，引起了一场激烈的争论 。1977年Diffie和Hellman提出了制造一个每秒能测试 106个密钥的大规模芯片，这种芯片的机器大约一天就 可以搜索DES算法的整个密钥空间，制造这样的机器 需要两千万美元。n1993年R.Session和M.Wiener给出了一个非常详细的密 钥搜索机器的设计方案，它基于并行的密钥搜索芯片 ，此芯片每秒测试5107个密钥，当时这种芯片的造 价是10.5美元，5760个这样的芯片组成的系统需要10 万美元，这一系统平均1.5天即可找到密钥，如果利用 10个这样的系统，费用是100万美元，但搜索时间可以 降到2.5小时。可见这种机制是不安全的。DES算法的安全性 n1997年1月28日，美国的RSA数据安全公司在互联网上 开展了一项名为“密钥挑战”的竞赛，悬赏一万美元， 破解一段用56比特密钥加密的DES密文。计划公布后 引起了网络用户的强力响应。一位名叫Rocke Verser 的程序员设计了一个可以通过互联网分段运行的密钥 穷举搜索程序，组织实施了一个称为DESHALL的搜索 行动，成千上万的志愿者加入到计划中，在计划实施 的第96天，即挑战赛计划公布的第140天，1997年6月 17日晚上10点39分，美国盐湖城Inetz公司的职员 Michael Sanders成功地找到了密钥，在计算机上显示 了明文：“The unknown message is: Strong cryptography makes the world a safer place”。DES算法的原理 nDES算法的入口参数有三个：Key、Data、 Mode。其中Key为8个字节共64位，是DES算 法的工作密钥；Data也为8个字节64位，是要 被加密或被解密的数据；Mode为DES的工作方 式有两种：加密或解密。nDES算法是这样工作的：如Mode为加密，则用 Key去把数据Data进行加密，生成Data的密码 形式（64位）作为DES的输出结果；如Mode为 解密，则用Key去把密码形式的数据Data解密 ，还原为Data的明码形式（64位）作为DES的 输出结果。DES算法的实现步骤nDES算法实现加密需要三个步骤：n第一步：变换明文。对给定的64位比特的明文x，首先 通过一个置换IP表来重新排列x，从而构造出64位比特 的x0，x0=IP(x)=L0R0，其中L0表示x0的前32比特， R0表示x0的后32位。n第二步：按照规则迭代。规则为nLi = Ri-1nRi = Lif(Ri-1,Ki) （i=1,2,316）n经过第一步变换已经得到L0和R0的值，其中符号表示 的数学运算是异或，f表示一种置换，由S盒置换构成 ，Ki是一些由密钥编排函数产生的比特块。f和Ki将在 后面介绍。n第三步：对L16R16利用IP-1作逆置换， 就得到了密文y。加密过程如图8-4所示 。n从图中可以看出，DES加密需要四个关键点：1、IP置 换表和IP-1逆置换表。2、函数f。3、子密钥Ki。4、S 盒的工作原理。（1）IP置换表和IP-1逆置换表n输入的64位数据按置换IP表进行重新组合 ，并把输出分为L0、R0两部分，每部分各 长32位，其置换IP表如表8-1所示。5 85 01 23 42 61 81 026 05 24 43 62 82 01 246 25 44 63 83 02 21 466 45 64 84 03 22 41 685 74 94 13 32 51 7915 95 14 33 52 71 91 136 15 34 53 72 92 11 356 35 54 73 93 12 31 57n将输入64位比特的第58位换到第一位，第50位换到第二位，依此 类推，最后一位是原来的第7位。L0、R0则是换位输出后的两部 分，L0是输出的左32位，R0是右32位。比如：置换前的输入值为 D1D2D3D64，则经过初始置换后的结果为：L0=D58D50.D8 ，R0=D57D49.D7。n经过16次迭代运算后。得到L16、R16，将此作为输入，进行逆置 换，即得到密文输出。逆置换正好是初始置的逆运算，例如，第 1位经过初始置换后，处于第40位，而通过逆置换IP-1，又将第 40位换回到第1位，其逆置换IP-1规则表8-2所示。逆置换表IP-1 4 084 81 65 62 46 43 23 974 71 55 52 36 33 13 864 61 45 42 26 23 03 754 51 35 32 16 12 93 644 41 25 22 06 02 83 534 31 15 11 95 92 73 424 21 05 01 85 82 63 314 194 91 75 72 5（2）函数fn函数f有两个输入：32位的Ri-1和48位Ki，f函数的处理 流程如图8-5所示。nE变换的算法是从Ri-1的32位中选取某些位，构成48位。即 E将32比特扩展变换为48位，变换规则根据E位选择表，如 表8-3所示。3 212345456789891 01 1 1 21 31 21 31 41 51 61 71 61 71 81 92 02 12 02 1 2 22 32 42 52 42 52 62 72 82 92 82 93 03 13 21nKi是由密钥产生的48位比特串，具体的算法下面介绍。将E的 选位结果与Ki作异或操作，得到一个48位输出。分成8组，每 组6位，作为8个S盒的输入。n每个S盒输出4位，共32位，S盒的工作原理将在第第四步介绍 。S盒的输出作为P变换的输入，P的功能是对输入进行置换， P换位表如表8-4所示。1 672 02 12 91 22 81 711 52 32 651 83 11 0 282 41 43 22 7391 91 33 062 21 142 5n（3）子密钥kin假设密钥为K，长度为64位，但是其中第8、16、24、32、40、 48、64用作奇偶校验位，实际上密钥长度为56位。K的下标i的取 值范围是1到16，用16轮来构造。构造过程如图8-6所示。n首先，对于给定的密钥K，应用PC1变换进行选位，选 定后的结果是56位，设其前28位为C0，后28位为D0。 PC1选位如表8-5所示。5 74 94 13 32 51 7915 85 04 23 42 61 81 025 95 14 33 52 71 91 136 05 24 43 66 35 54 73 93 12 31 576 25 44 63 83 02 21 466 15 34 53 72 92 11 352 82 01 24n第一轮：对C0作左移LS1得到