3个著名加密算法(MD5、RSA、DES)的解析.doc

1、MD5的全称是 Message-Digest Algorithm 5，在90 年代初由 MIT 的计算机科学实验室和 RSA Data Security Inc 发明，经 MD2、MD3和 MD4发展而来。MD5将任意长度的 “字节串”变换成一个128bit 的大整数，并且它是一个不可逆的字符串变换算法，换句话说就是，即使你看到源程序和算法描述，也无法将一个 MD5的值变换回原始的字符串，从数学原理上说，是因为原始的字符串有无穷多个，这有点象不存在反函数的数学函数。MD5的典型应用是对一段 Message(字节串) 产生 fingerprint(指纹)，以防止被“篡改” 。举个例子，你将一段话

2、写在一个叫 readme.txt 文件中，并对这个 readme.txt 产生一个 MD5的值并记录在案，然后你可以传播这个文件给别人，别人如果修改了文件中的任何内容，你对这个文件重新计算 MD5时就会发现。如果再有一个第三方的认证机构，用 MD5还可以防止文件作者的“ 抵赖”，这就是所谓的数字签名应用。MD5还广泛用于加密和解密技术上，在很多操作系统中，用户的密码是以 MD5值（或类似的其它算法）的方式保存的， 用户 Login 的时候，系统是把用户输入的密码计算成 MD5值，然后再去和系统中保存的 MD5值进行比较，而系统并不“知道”用户的密码是什么。RSA 是第一个既能用于数据加密也能用

3、于数字签名的算法。它易于理解和操作，也很流行。算法的名字以发明者的名字命名：Ron Rivest, Adi Shamir 和 Leonard Adleman。但 RSA 的安全性一直未能得到理论上的证明。它经历了各种攻击，至今未被完全攻破。 DES 算法 美国国家标准局1973年开始研究除国防部外的其它部门的计算机系统的数据加密标准，于 1973年5月15日和1974年8 月27日先后两次向公众发出了征求加密算法的公告。 1977年1月，美国政府颁布：采纳 IBM 公司设计的方案作为非机密数据的正式数据加密标准（DES?Data Encryption Standard） 。 1.加密算法之 M

4、D5算法在一些初始化处理后，MD5以512位分组来处理输入文本，每一分组又划分为 16个32位子分组。算法的输出由四个32位分组组成，将它们级联形成一个 128位散列值。 首先填充消息使其长度恰好为一个比512位的倍数仅小64位的数。填充方法是附一个1在消息后面，后接所要求的多个0，然后在其后附上64位的消息长度（填充前） 。这两步的作用是使消息长度恰好是512 位的整数倍（算法的其余部分要求如此） ，同时确保不同的消息在填充后不相同。 四个32位变量初始化为： A=0x01234567 B=0x89abcdef C=0xfedcba98 D=0x76543210 它们称为链接变量（chain

5、ing variable） 接着进行算法的主循环，循环的次数是消息中512位消息分组的数目。 将上面四个变量复制到别外的变量中：A 到 a，B 到 b，C 到 c，D 到 d。 主循环有四轮（MD4只有三轮） ，每轮很相拟。第一轮进行16次操作。每次操作对 a，b ，c 和 d 中的其中三个作一次非线性函数运算，然后将所得结果加上第四个变量，文本的一个子分组和一个常数。再将所得结果向右环移一个不定的数，并加上 a，b，c 或 d 中之一。最后用该结果取代 a，b，c 或d 中之一。 以一下是每次操作中用到的四个非线性函数（每轮一个） 。 F(X,Y,Z)=(X&Y)|(X)&Z) G(X,Y,

6、Z)=(X&Z)|(Y&(Z) H(X,Y,Z)=XYZ I(X,Y,Z)=Y(X|(Z) (&是与,|是或,是非,是异或) 这些函数是这样设计的：如果 X、Y 和 Z 的对应位是独立和均匀的，那么结果的每一位也应是独立和均匀的。 函数 F 是按逐位方式操作：如果 X，那么 Y，否则 Z。函数 H 是逐位奇偶操作符。 设 Mj 表示消息的第 j 个子分组（从0 到15 ） ，= n 的话, 就将 a 表成 s 进位 (s 若 p, q 是相异质数, rm = 1 mod (p-1)(q-1), a 是任意一个正整数, b = am mod pq, c = br mod pq, 则 c = a

7、mod pq 证明的过程, 会用到费马小定理, 叙述如下: m 是任一质数, n 是任一整数, 则 nm = n mod m (换另一句话说, 如果 n 和 m 互质, 则 n(m-1) = 1 mod m) 运用一些基本的群论的知识, 就可以很容易地证出费马小定理的. 因为 rm = 1 mod (p-1)(q-1), 所以 rm = k(p-1)(q-1) + 1, 其中 k 是整数 因为在 modulo 中是 preserve 乘法的 (x = y mod z and u = v mod z = xu = yv mod z), 所以, c = br = (am)r = a(rm) = a

8、(k(p-1)(q-1)+1) mod pq 1. 如果 a 不是 p 的倍数, 也不是 q 的倍数时, 则 a(p-1) = 1 mod p (费马小定理) = a(k(p-1)(q-1) = 1 mod p a(q-1) = 1 mod q (费马小定理) = a(k(p-1)(q-1) = 1 mod q 所以 p, q 均能整除 a(k(p-1)(q-1) - 1 = pq | a(k(p-1)(q-1) - 1 即 a(k(p-1)(q-1) = 1 mod pq = c = a(k(p-1)(q-1)+1) = a mod pq 2. 如果 a 是 p 的倍数, 但不是 q 的倍数

9、时, 则 a(q-1) = 1 mod q (费马小定理) = a(k(p-1)(q-1) = 1 mod q = c = a(k(p-1)(q-1)+1) = a mod q = q | c - a 因 p | a = c = a(k(p-1)(q-1)+1) = 0 mod p = p | c - a 所以, pq | c - a = c = a mod pq 3. 如果 a 是 q 的倍数, 但不是 p 的倍数时, 证明同上 4. 如果 a 同时是 p 和 q 的倍数时, 则 pq | a = c = a(k(p-1)(q-1)+1) = 0 mod pq = pq | c - a =

10、c = a mod pq Q.E.D. 这个定理说明 a 经过编码为 b 再经过解码为 c 时, a = c mod n (n = pq). 但我们在做编码解码时, 限制 0 = a n, 0 = c n, 所以这就是说 a 等於 c, 所以这个过程确实能做到编码解码的功能. 二、RSA 的安全性 RSA 的安全性依赖于大数分解，但是否等同于大数分解一直未能得到理论上的证明，因为没有证明破解 RSA 就一定需要作大数分解。假设存在一种无须分解大数的算法，那它肯定可以修改成为大数分解算法。目前， RSA 的一些变种算法已被证明等价于大数分解。不管怎样，分解 n 是最显然的攻击方法。现在，人们已能

11、分解多个十进制位的大素数。因此，模数 n 必须选大一些，因具体适用情况而定。 三、RSA 的速度 由于进行的都是大数计算，使得 RSA 最快的情况也比 DES 慢上倍，无论是软件还是硬件实现。速度一直是 RSA 的缺陷。一般来说只用于少量数据加密。 四、RSA 的选择密文攻击 RSA 在选择密文攻击面前很脆弱。一般攻击者是将某一信息作一下伪装( Blind)，让拥有私钥的实体签署。然后，经过计算就可得到它所想要的信息。实际上，攻击利用的都是同一个弱点，即存在这样一个事实：乘幂保留了输入的乘法结构： ( XM )d = Xd *Md mod n 前面已经提到，这个固有的问题来自于公钥密码系统的最

12、有用的特征-每个人都能使用公钥。但从算法上无法解决这一问题，主要措施有两条：一条是采用好的公钥协议，保证工作过程中实体不对其他实体任意产生的信息解密，不对自己一无所知的信息签名；另一条是决不对陌生人送来的随机文档签名，签名时首先使用 One-Way HashFunction 对文档作 HASH 处理，或同时使用不同的签名算法。在中提到了几种不同类型的攻击方法。 五、RSA 的公共模数攻击 若系统中共有一个模数，只是不同的人拥有不同的 e 和 d，系统将是危险的。最普遍的情况是同一信息用不同的公钥加密，这些公钥共模而且互质，那末该信息无需私钥就可得到恢复。设 P 为信息明文，两个加密密钥为 e1

13、和 e2，公共模数是 n，则： C1 = Pe1 mod n C2 = Pe2 mod n 密码分析者知道 n、e1 、e2 、C1和 C2，就能得到 P。 因为 e1和 e2互质，故用 Euclidean 算法能找到 r 和 s，满足： r * e1 + s * e2 = 1 假设 r 为负数，需再用 Euclidean 算法计算 C1(-1)，则 ( C1(-1) )(-r) * C2s = P mod n 另外，还有其它几种利用公共模数攻击的方法。总之，如果知道给定模数的一对 e 和 d，一是有利于攻击者分解模数，一是有利于攻击者计算出其它成对的 e和 d，而无需分解模数。解决办法只有一

14、个，那就是不要共享模数 n。 RSA 的小指数攻击。 有一种提高 RSA 速度的建议是使公钥 e 取较小的值，这样会使加密变得易于实现，速度有 所提高。但这样作是不安全的，对付办法就是 e 和 d 都取较大的值。 RSA 算法是第一个能同时用于加密和数字签名的算法，也易于理解和操作。RSA 是被研究得最广泛的公钥算法，从提出到现在已近二十年，经历了各种攻击的考验，逐渐为人们接受，普遍认为是目前最优秀的公钥方案之一。RSA 的安全性依赖于大数的因子分解，但并没有从理论上证明破译 RSA的难度与大数分解难度等价。即 RSA 的重大缺陷是无法从理论上把握它的保密性能如何，而且密码学界多数人士倾向于因

15、子分解不是 NPC 问题。 RSA 的缺点主要有： A)产生密钥很麻烦，受到素数产生技术的限制，因而难以做到一次一密。B)分组长度太大，为保证安全性，n 至少也要 600 bits 以上，使运算代价很高，尤其是速度较慢，较对称密码算法慢几个数量级；且随着大数分解技术的发展，这个长度还在增加，不利于数据格式的标准化。目前，SET( Secure Electronic Transaction )协议中要求 CA 采用比特长的密钥，其他实体使用比特的密钥。3.加密算法之 DES 算法一、DES 算法 美国国家标准局1973年开始研究除国防部外的其它部门的计算机系统的数据加密标准，于 1973年5月1

16、5日和1974年8月27日先后两次向公众发出了征求加密算法的公告。加密算法要达到的目的（通常称为 DES 密码算法要求）主要为以下四点： 提供高质量的数据保护，防止数据未经授权的泄露和未被察觉的修改； 具有相当高的复杂性，使得破译的开销超过可能获得的利益，同时又要便于理解和掌握； DES 密码体制的安全性应该不依赖于算法的保密，其安全性仅以加密密钥的保密为基础； 实现经济，运行有效，并且适用于多种完全不同的应用。 1977年1月，美国政府颁布：采纳 IBM 公司设计的方案作为非机密数据的正式数据加密标准（DES?Data Encryption Standard） 。 目前在国内，随着三金工程尤

17、其是金卡工程的启动，DES 算法在 POS、ATM 、磁卡及智能卡（IC 卡） 、加油站、高速公路收费站等领域被广泛应用，以此来实现关键数据的保密，如信用卡持卡人的 PIN 的加密传输，IC 卡与 POS 间的双向认证、金融交易数据包的 MAC 校验等，均用到 DES算法。 DES 算法的入口参数有三个： Key、Data 、Mode 。其中 Key 为8个字节共64 位，是 DES 算法的工作密钥；Data 也为8个字节64位，是要被加密或被解密的数据； Mode 为 DES 的工作方式，有两种：加密或解密。 DES 算法是这样工作的：如 Mode 为加密，则用 Key 去把数据 Data

18、进行加密， 生成 Data 的密码形式（64位）作为 DES 的输出结果；如 Mode 为解密，则用 Key 去把密码形式的数据 Data 解密，还原为 Data 的明码形式（64 位）作为 DES 的输出结果。在通信网络的两端，双方约定一致的Key，在通信的源点用 Key 对核心数据进行 DES 加密，然后以密码形式在公共通信网（如电话网）中传输到通信网络的终点，数据到达目的地后，用同样的 Key 对密码数据进行解密，便再现了明码形式的核心数据。这样，便保证了核心数据（如 PIN、MAC 等）在公共通信网中传输的安全性和可靠性。 通过定期在通信网络的源端和目的端同时改用新的 Key，便能更进

19、一步提高数据的保密性，这正是现在金融交易网络的流行做法。 DES 算法详述 DES 算法把64位的明文输入块变为64位的密文输出块，它所使用的密钥也是64位，整个算法的主流程图如下： 其功能是把输入的64位数据块按位重新组合，并把输出分为 L0、R0两部分，每部分各长32位，其置换规则见下表： 58,50,12,34,26,18,10,2,60,52,44,36,28,20,12,4, 62,54,46,38,30,22,14,6,64,56,48,40,32,24,16,8, 57,49,41,33,25,17, 9,1,59,51,43,35,27,19,11,3, 61,53,45,37

20、,29,21,13,5,63,55,47,39,31,23,15,7, 即将输入的第58位换到第一位，第 50位换到第2 位，.，依此类推，最后一位是原来的第 7位。L0、R0 则是换位输出后的两部分，L0 是输出的左32位，R0 是右32 位，例：设置换前的输入值为D1D2D3.D64，则经过初始置换后的结果为： L0=D58D50.D8；R0=D57D49.D7 。 经过16次迭代运算后。得到 L16、R16，将此作为输入，进行逆置换，即得到密文输出。逆置换正好是初始置的逆运算，例如，第1位经过初始置换后，处于第40位，而通过逆置换，又将第40 位换回到第1位，其逆置换规则如下表所示： 4

21、0,8,48,16,56,24,64,32,39,7,47,15,55,23,63,31, 38,6,46,14,54,22,62,30,37,5,45,13,53,21,61,29, 36,4,44,12,52,20,60,28,35,3,43,11,51,19,59,27, 34,2,42,10,50,18,58 26,33,1,41, 9,49,17,57,25, 放大换位表 32, 1, 2, 3, 4, 5, 4, 5, 6, 7, 8, 9, 8, 9, 10,11, 12,13,12,13,14,15,16,17,16,17,18,19,20,21,20,21, 22,23,24

22、,25,24,25,26,27,28,29,28,29,30,31,32, 1, 单纯换位表 16,7,20,21,29,12,28,17, 1,15,23,26, 5,18,31,10, 2,8,24,14,32,27, 3, 9,19,13,30, 6,22,11, 4,25, 在 f(Ri,Ki)算法描述图中，S1,S2.S8为选择函数，其功能是把6bit 数据变为4bit 数据。下面给出选择函数 Si(i=1,2.的功能表： 选择函数 Si S1: 14,4,13,1,2,15,11,8,3,10,6,12,5,9,0,7, 0,15,7,4,14,2,13,1,10,6,12,11,

23、9,5,3,8, 4,1,14,8,13,6,2,11,15,12,9,7,3,10,5,0, 15,12,8,2,4,9,1,7,5,11,3,14,10,0,6,13, S2: 15,1,8,14,6,11,3,4,9,7,2,13,12,0,5,10, 3,13,4,7,15,2,8,14,12,0,1,10,6,9,11,5, 0,14,7,11,10,4,13,1,5,8,12,6,9,3,2,15, 13,8,10,1,3,15,4,2,11,6,7,12,0,5,14,9, S3: 10,0,9,14,6,3,15,5,1,13,12,7,11,4,2,8, 13,7,0,9,3

24、,4,6,10,2,8,5,14,12,11,15,1, 13,6,4,9,8,15,3,0,11,1,2,12,5,10,14,7, 1,10,13,0,6,9,8,7,4,15,14,3,11,5,2,12, S4: 7,13,14,3,0,6,9,10,1,2,8,5,11,12,4,15, 13,8,11,5,6,15,0,3,4,7,2,12,1,10,14,9, 10,6,9,0,12,11,7,13,15,1,3,14,5,2,8,4, 3,15,0,6,10,1,13,8,9,4,5,11,12,7,2,14, S5: 2,12,4,1,7,10,11,6,8,5,3,15,1

25、3,0,14,9, 14,11,2,12,4,7,13,1,5,0,15,10,3,9,8,6, 4,2,1,11,10,13,7,8,15,9,12,5,6,3,0,14, 11,8,12,7,1,14,2,13,6,15,0,9,10,4,5,3, S6: 12,1,10,15,9,2,6,8,0,13,3,4,14,7,5,11, 10,15,4,2,7,12,9,5,6,1,13,14,0,11,3,8, 9,14,15,5,2,8,12,3,7,0,4,10,1,13,11,6, 4,3,2,12,9,5,15,10,11,14,1,7,6,0,8,13, S7: 4,11,2,14,15,0,8,13,3,12,9,7,5,10,6,1, 13,0,11,7,4,9,1,10,14,3,5,12,2,15,8,6,