《加密解密、信息摘要算法收集》由会员分享,可在线阅读,更多相关《加密解密、信息摘要算法收集(32页珍藏版)》请在金锄头文库上搜索。
1、加密解密、信息摘要算法收集加密解密、信息摘要算法收集加密解密、信息摘要算法收集.txt 每个女孩都曾是无泪的天使,当遇到自己喜欢的男孩时,便会流泪一一,于是坠落凡间变为女孩,所以,男孩一定不要辜负女孩,因为女孩为你放弃整个天堂。朋友,别哭,今夜我如昙花绽放在最美的瞬间凋谢,你的泪水也无法挽回我的枯萎加密解密、信息摘要算法收集 作者:未知 文章来源:csdn 点击数:1898 更新时间:2004-9-7 MD5 算法研究 综述 md5 的全称是 message-digest algorithm 5(信息-摘要算法) ,在 90 年代初由 mit laboratory for computer s
2、cience 和 rsa data security inc 的ronald l. rivest 开发出来,经 md2、md3 和 md4 发展而来。它的作用是让大容量信息在用数字签名软件签署私人密匙前被“压缩“成一种保密的格式(就是把一个任意长度的字节串变换成一定长的大整数) 。不管是 md2、md4 还是 md5,它们都需要获得一个随机长度的信息并产生一个 128 位的信息摘要。虽然这些算法的结构或多或少有些相似,但 md2 的设计与 md4 和md5 完全不同,那是因为 md2 是为 8 位机器做过设计优化的,而 md4 和 md5 却是面向 32 位的电脑。这三个算法的描述和 c语言源
3、代码在 internet rfcs 1321 中有详细的描述(http:/www.ietf.org/rfc/rfc1321.txt) ,这是一份最权威的文档,由 ronald l. rivest 在 1992 年 8月向 ieft 提交。 rivest 在 1989 年开发出 md2 算法。在这个算法中,首先对信息进行数据补位,使信息的字节长度是 16 的倍数。然后,以一个 16 位的检验和追加到信息末尾。并且根据这个新产生的信息计算出散列值。后来,rogier 和 chauvaud 发现如果忽略了检验和将产生 md2 冲突。md2 算法的加密后结果是唯一的-既没有重复。 为了加强算法的安全性
4、,rivest 在 1990 年又开发出 md4 算法。md4 算法同样需要填补信息以确保信息的字节长度加上 448 后能被 512 整除(信息字节长度mod 512 = 448) 。然后,一个以 64 位二进制表示的信息的最初长度被添加进来。信息被处理成 512 位 damg?rd/merkle 迭代结构的区块,而且每个区块要通过三个不同步骤的处理。den boer 和 bosselaers 以及其他人很快的发现了攻击 md4 版本中第一步和第三步的漏洞。dobbertin 向大家演示了如何利用一部普通的个人电脑在几分钟内找到 md4 完整版本中的冲突(这个冲突实际上是一种漏洞,它将导致对不
5、同的内容进行加密却可能得到相同的加密后结果) 。毫无疑问,md4 就此被淘汰掉了。 尽管 md4 算法在安全上有个这么大的漏洞,但它对在其后才被开发出来的好几种信息安全加密算法的出现却有着不可忽视的引导作用。除了 md5 以外,其中比较有名的还有 sha-1、ripe-md 以及 haval 等。 一年以后,即 1991 年,rivest 开发出技术上更为趋近成熟的md5 算法。它在 md4 的基础上增加了“安全-带子“(safety-belts)的概念。虽然 md5 比 md4 稍微慢一些,但却更为安全。这个算法很明显的由四个和 md4 设计有少许不同的步骤组成。在md5 算法中,信息-摘要
6、的大小和填充的必要条件与 md4 完全相同。den boer 和 bosselaers曾发现 md5 算法中的假冲突(pseudo-collisions) ,但除此之外就没有其他被发现的加密后结果了。 van oorschot 和 wiener 曾经考虑过一个在散列中暴力搜寻冲突的函数(brute-force hash function) ,而且他们猜测一个被设计专门用来搜索 md5 冲突的机器(这台机器在 1994 年的制造成本大约是一百万美元)可以平均每 24 天就找到一个冲突。但单从 1991 年到 2001 年这 10 年间,竟没有出现替代 md5 算法的 md6 或被叫做其他什么名字
7、的新算法这一点,我们就可以看出这个瑕疵并没有太多的影响 md5 的安全性。上面所有这些都不足以成为 md5 的在实际应用中的问题。并且,由于 md5 算法的使用不需要支付任何版权费用的,所以在一般的情况下(非绝密应用领域。但即便是应用在绝密领域内,md5 也不失为一种非常优秀的中间技术) ,md5 怎么都应该算得上是非常安全的了。 算法的应用 md5 的典型应用是对一段信息(message)产生信息摘要(message-digest) ,以防止被篡改。比如,在 unix 下有很多软件在下载的时候都有一个文件名相同,文件扩展名为.md5 的文件,在这个文件中通常只有一行文本,大致结构如: md5
8、 (tanajiya.tar.gz) = 0ca175b9c0f726a831d895e269332461 这就是 tanajiya.tar.gz 文件的数字签名。md5 将整个文件当作一个大文本信息,通过其不可逆的字符串变换算法,产生了这个唯一的 md5 信息摘要。如果在以后传播这个文件的过程中,无论文件的内容发生了任何形式的改变(包括人为修改或者下载过程中线路不稳定引起的传输错误等) ,只要你对这个文件重新计算 md5 时就会发现信息摘要不相同,由此可以确定你得到的只是一个不正确的文件。如果再有一个第三方的认证机构,用 md5 还可以防止文件作者的“抵赖“,这就是所谓的数字签名应用。 md
9、5 还广泛用于加密和解密技术上。比如在 unix 系统中用户的密码就是以 md5(或其它类似的算法)经加密后存储在文件系统中。当用户登录的时候,系统把用户输入的密码计算成 md5 值,然后再去和保存在文件系统中的 md5 值进行比较,进而确定输入的密码是否正确。通过这样的步骤,系统在并不知道用户密码的明码的情况下就可以确定用户登录系统的合法性。这不但可以避免用户的密码被具有系统管理员权限的用户知道,而且还在一定程度上增加了密码被破解的难度。 正是因为这个原因,现在被黑客使用最多的一种破译密码的方法就是一种被称为“跑字典“的方法。有两种方法得到字典,一种是日常搜集的用做密码的字符串表,另一种是用
10、排列组合方法生成的,先用 md5 程序计算出这些字典项的 md5 值,然后再用目标的 md5 值在这个字典中检索。我们假设密码的最大长度为 8 位字节(8 bytes) ,同时密码只能是字母和数字,共 26+26+10=62 个字符,排列组合出的字典的项数则是 p(62,1)+p(62,2).+p(62,8),那也已经是一个很天文的数字了,存储这个字典就需要 tb 级的磁盘阵列,而且这种方法还有一个前提,就是能获得目标账户的密码 md5 值的情况下才可以。这种加密技术被广泛的应用于 unix 系统中,这也是为什么 unix 系统比一般操作系统更为坚固一个重要原因。 算法描述 对 md5 算法简
11、要的叙述可以为:md5 以 512 位分组来处理输入的信息,且每一分组又被划分为 16 个 32 位子分组,经过了一系列的处理后,算法的输出由四个 32 位分组组成,将这四个 32 位分组级联后将生成一个 128 位散列值。 在 md5 算法中,首先需要对信息进行填充,使其字节长度对512 求余的结果等于 448。因此,信息的字节长度(bits length)将被扩展至 n*512+448,即n*64+56 个字节(bytes),n 为一个正整数。填充的方法如下,在信息的后面填充一个 1 和无数个 0,直到满足上面的条件时才停止用 0 对信息的填充。然后,在在这个结果后面附加一个以 64 位二
12、进制表示的填充前信息长度。经过这两步的处理,现在的信息字节长度=n*512+448+64=(n+1)*512,即长度恰好是 512 的整数倍。这样做的原因是为满足后面处理中对信息长度的要求。 md5 中有四个 32 位被称作链接变量(chaining variable)的整数参数,他们分别为:a=0x01234567,b=0x89abcdef,c=0xfedcba98,d=0x76543210。 当设置好这四个链接变量后,就开始进入算法的四轮循环运算。循环的次数是信息中512 位信息分组的数目。 将上面四个链接变量复制到另外四个变量中:a 到 a,b 到b,c 到 c,d 到 d。 主循环有四
13、轮(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,z) =(x&z)|(y&(z) h(x,y,z) =xyz i(x,y,z)=y(x|(z) (&是与,|是或,是非,是异或) 这四个函数的说明:如果 x、y 和 z 的对
14、应位是独立和均匀的,那么结果的每一位也应是独立和均匀的。 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 mod pq 证明的过程, 会用到费马小定理, 叙述如下: m 是任一质数, n 是任一整数, 则 nm = n mod m (换另一句话说, 如果 n 和 m 互质,
15、 则 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(k(p-1)(q-1)+1) mod pq 1. 如果 a 不是 p 的倍数, 也不是 q 的倍数时, 则 a(p-1) = 1 mod p (费马小定理) = a(
16、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 的倍数时, 则 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 是