认识MD5 - webdancer's Blog

认识MD5

webdancer posted @ 2012年4月28日 23:26 in 技术 with tags 算法 , 1281 阅读

     MD5是一种安全哈希算法(secure hash algorithm,SHA);SHA是一种加密哈希函数(cryptographic hash function);加密哈希函数是一种哈希函数(hash function); 哈希函数是一种函数。下面我们就看一下这些概念。

1.函数(function)

     学习过离散数学,我们对函数并不陌生。不严格地说,在定义域上上的值x,都有值域上唯一的值y与之对应,这种映射关系成为函数。简单地说,函数可以将一些数值变换到另外一些数值(当然可以使本身)。注:数学上的函数与编程语言的函数还是有些不同,虽然在程序中的函数,给定输入(参数),可以得到输出(返回值)两者的范畴感觉还是不太一样。

2.哈希函数(hash function)

    散列函数是一种从任何一种数据中创建小的数字“指纹”的方法。哈希函数得到的输出成为散列值。哈希函数是一种特殊的函数,当然满足函数的基本性质,即两个不同的散列值对应的输入时不同的。散列函数把消息或数据压缩成摘要,使得数据量变小,将数据的格式固定下来。不同的输入映射到相同的散列值称“碰撞”。哈希函数如下图所示:

  哈希函数的主要应用有:

  1. 散列表。散列表是一种重要的数据结构,是哈希函数的一个重要应用。使用散列表能够快速的按照关键字查找数据记录。
  2. 加密。一个典型的加密单向函数是“非对称”的,并且由一个高效的散列函数构成。加密算法可以分为两类: 对称加密和非对称加密
  3. 错误校正。使用一个散列函数可以很直观的检测出数据在传输时发生的错误。在数据的发送方,对将要发送的数据应用散列函数,并将计算的结果同原始数据一同发送。在数据的接收方,同样的散列函数被再一次应用到接收到的数据上,如果两次散列函数计算出来的结果不一致,那么就说明数据在传输的过程中某些地方有错误了。
  4. 语音识别,Rabin-Karp 字符串搜索算法等。

3.加密哈希函数(Cryptographic hash function)

     加密哈希函数是一种哈希函数,其满足哈希函数的基本性质:将一个大数据转为一个固定bit的字符串。其输入和输出分别成为:message(消息)和digest(摘要)。其中一个良好的加密哈希函数要求一下几点:

  1. 有消息容易计算摘要。
  2. 有摘要反向得到消息是不可行的(哈希函数不可逆,单向函数)
  3. 消息改变,摘要一定改变(哈希函数不碰撞)
  4. 两个不同的消息,对应不同的摘要(哈希函数不碰撞)

安全哈希函数如下所示:

应用:

  1. 文件或消息完整性验证。
  2. 文件或数据标识。比如git等代码管理系统使用sha1sum来区分不同内容。

4.安全哈希算法(secure hash algorithm,SHA)

     安全散列算法是一种能计算出一个数位讯息所对应到的,长度固定的字串(又称讯息摘要)的算法。SHA家族的五个算法,分别是SHA-1、SHA-224、SHA-256、SHA-384,和SHA-512,由NSA所设计,并由NIST发布;是美国的政府标准。后四者有时并称为SHA-2。

    python的hashlib模块中实现了上述五种SHA算法和更早的md5算法。

image

5.MD5

     MD5即Message-Digest Algorithm 5用于确保信息传输完整一致。是计算机广泛使用的杂凑算法之一 ,主流编程语言普遍已有MD5实现。

    MD5是一种安全哈希算法,但是MD5较老,散列长度通常为128位元,随着计算机运算能力提高,找到“碰撞”是可能的。在加密哈希函数中已经说过,一个良好的加密哈希函数应该不碰撞。2004年,王小云证明MD5数字签名算法可以产生碰撞。

   为什么证明产生碰撞,MD5算法就失效了呢?以前不太理解,下面的解释还是比较清楚地。

   根据密码学的定义,如果内容不同的明文,通过散列算法得出的结果(密码学称为信息摘要)相同,就称为发生了“碰撞”。散列算法的用途不是对明文加密,让别人看不懂,而是通过对信息摘要的比对,判断原文是否被篡改。所以说对摘要算法来说,它只要能找到碰撞就足以让它失效,并不需要找到原文。具一个例子, Linux的用户安全机制,只要得到用户密码文件(其中记录了密码的MD5),然后随便生成一个碰撞的原文(不一定要跟原密码相同),就可以用这个密码登录了。

参考:wikipedia


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter
Host by is-Programmer.com | Power by Chito 1.3.3 beta | © 2007 LinuxGem | Design by Matthew "Agent Spork" McGee