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

上传人:sk****8 文档编号:3538996 上传时间:2019-06-03 格式:DOC 页数:12 大小:73.50KB
下载 相关 举报
3个著名加密算法(MD5、RSA、DES)的解析.doc_第1页
第1页 / 共12页
3个著名加密算法(MD5、RSA、DES)的解析.doc_第2页
第2页 / 共12页
3个著名加密算法(MD5、RSA、DES)的解析.doc_第3页
第3页 / 共12页
3个著名加密算法(MD5、RSA、DES)的解析.doc_第4页
第4页 / 共12页
3个著名加密算法(MD5、RSA、DES)的解析.doc_第5页
第5页 / 共12页
点击查看更多>>
资源描述

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,

展开阅读全文
相关资源
相关搜索

当前位置:首页 > 教育教学资料库 > 精品笔记

Copyright © 2018-2021 Wenke99.com All rights reserved

工信部备案号浙ICP备20026746号-2  

公安局备案号:浙公网安备33038302330469号

本站为C2C交文档易平台,即用户上传的文档直接卖给下载用户,本站只是网络服务中间平台,所有原创文档下载所得归上传人所有,若您发现上传作品侵犯了您的权利,请立刻联系网站客服并提供证据,平台将在3个工作日内予以改正。